IP Library Granted Patent US 12,382,059
Granted Patent B2
US 12,382,059 · App. 18/604,341 · Granted Aug 5, 2025

Method and system for picture segmentation using columns

Inventor: Michael Horowitz (Austin, TX)
Assignee: Dolby Laboratories Licensing Corporation
H04N19/139C12N9/0071C12P7/14C12P17/14C12Y114/00H04N19/103H04N19/105H04N19/117H04N19/137H04N19/159H04N19/172H04N19/174H04N19/196H04N19/436H04N19/44H04N19/46H04N19/50H04N19/61H04N19/70H04N19/80H04N19/82H04N19/91
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,382,059
App. No.
18/604,341
Granted
Aug 5, 2025
Kind
B2
Abstract

Described is picture segmentation through columns and slices in video encoding and decoding. A video picture is divided into a plurality of columns, each column covering only a part of the video picture in a horizontal dimension. All coded tree blocks (“CTBs”) belonging to a slice may belong to one or more columns. The columns may be used to break the same or different prediction or in-loop filtering mechanisms of the video coding, and the CTB scan order used for encoding and/or decoding may be local to a column. Column widths may be indicated in a parameter set and/or may be adjusted at the slice level. At the decoder, column width may be parsed from the bitstream, and slice decoding may occur in one or more columns.

Claims (18)

1. An encoder for encoding a bitstream of coded pictures, comprising:

one or more processors and one or more storage devices storing instructions that are operable, when executed by the one or more processors, to cause the one or more processors to perform operations comprising:

receiving an uncoded picture;

encoding the uncoded picture into the bitstream as a first coded picture,

wherein the first coded picture comprises a plurality of coded tree blocks (CTBs),

wherein the first coded picture is segmented into at least two columns and at least two slices,

wherein each CTB belongs to both a respective column and a respective slice,

wherein a slice boundary in the first coded picture is not equal to a column boundary in the first coded picture and wherein all CTBs belonging to a first slice are located in exactly one column, and

wherein encoding the uncoded picture is performed using multiple columns and multiple slices, and wherein encoding the uncoded picture comprises:

for a slice of the multiple slices, encoding the CTBs in the slice in an order that is based on the respective columns to which the CTBs in the slice belong, and

breaking in-loop filtering within the first slice at a column boundary between adjacent columns of the multiple columns;

encoding, in a first picture parameter set in the bitstream, a value for a number of columns N minus one for the first coded picture of the bitstream; and

encoding, in the first picture parameter set in the bitstream, column width parameters pertaining to leftmost N−1 columns of the first coded picture, the column width parameters being measured in units of CTBs having a first size,

wherein the column width parameters pertaining to the leftmost N−1 columns determine a width of a rightmost column of the first coded picture, and

wherein the width of the rightmost column of the first coded picture is calculated using a width of the first coded picture and the column width parameters pertaining to the N−1 leftmost columns for the first coded picture.

2. The encoder of claim 1 , wherein the column width of at least one column is variable between at least two rows of CTBs in the first coded picture.

3. The encoder of claim 2 , wherein the variability is controlled by coding the column width in a slice header.

4. The encoder of claim 1 , wherein encoding the CTBs in the slice in an order that is based on the respective columns to which the CTBs in the slice belong comprises encoding the plurality of CTBs following a scan order of CTBs, according to which the plurality of CTBs are encoded sequentially by column from left-to-right across a plurality of columns, and sequentially by CTB from left-to-right and top-to-bottom within each of the plurality of columns.

Assignments (8)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Aug 16, 2024
From: DOLBY INTERNATIONAL AB
To: DOLBY LABORATORIES LICENSING CORPORATION
Reel/Frame 068316/0952 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Aug 16, 2024
From: HOROWITZ, MICHAEL
To: EBRISK VIDEO INC.
Reel/Frame 068316/0562 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Aug 16, 2024
From: EBRISK VIDEO, INC.
To: FISH DIVE, INC.
Reel/Frame 068316/0635 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Aug 16, 2024
From: FISH DIVE, INC.
To: DOLBY INTERNATIONAL AB
Reel/Frame 068316/0830 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 17, 2024
From: HOROWITZ, MICHAEL
To: EBRISK VIDEO INC.
Reel/Frame 067746/0018 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 17, 2024
From: FISH DIVE, INC.
To: DOLBY INTERNATIONAL AB
Reel/Frame 067747/0357 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 17, 2024
From: EBRISK VIDEO, INC.
To: FISH DIVE, INC.
Reel/Frame 067747/0590 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 17, 2024
From: DOLBY INTERNATIONAL AB
To: DOLBY LABORATORIES LICENSING CORPORATION
Reel/Frame 067747/0685 →
Continuity (8)
Continuation 18097019 · Jan 13, 2023
Continuation 17833115 · Jun 6, 2022
Continuation 17174728 · Feb 12, 2021
Continuation 16290764 · Mar 1, 2019
Continuation 14561480 · Dec 5, 2014
Continuation 13336675 · Dec 23, 2011
Provisional Application 61427569 · Dec 28, 2010
Related Publication 20240364894A1 · Oct 31, 2024
References Cited (131)
US 4949388A · Bhaskaran · 1990 [cited by applicant]
US 5638128A · Hoogenboom et al. · 1997 [cited by applicant]
US 5724451A · Shin et al. · 1998 [cited by applicant]
US 5995167A · Fukushima et al. · 1999 [cited by applicant]
US 6263023B1 · Ngai · 2001 [cited by applicant]
US 7162093B2 · Regunathan et al. · 2007 [cited by applicant]
US 7289562B2 · Yan et al. · 2007 [cited by applicant]
US 8831097B2 · Jung et al. · 2014 [cited by applicant]
US 8995525B2 · Wiegand · 2015 [cited by applicant]
US 9060174B2 · Horowitz · 2015 [cited by applicant]
US 9313505B2 · Horowitz · 2016 [cited by applicant]
US 9369722B2 · Horowitz · 2016 [cited by applicant]
US 9794573B2 · Horowitz · 2017 [cited by applicant]
US 9967563B2 · Hsu · 2018 [cited by examiner]
US 10225558B2 · Horowitz · 2019 [cited by applicant]
US 10244239B2 · Horowitz · 2019 [cited by applicant]
US 10986344B2 · Horowitz · 2021 [cited by applicant]
US 11356670B2 · Horowitz · 2022 [cited by applicant]
US 11582459B2 · Horowitz · 2023 [cited by applicant]
US 11949878B2 · Horowitz · 2024 [cited by applicant]
US 20020071489A1 · Ramanzin · 2002 [cited by applicant]
US 20040101059A1 · Joch et al. · 2004 [cited by applicant]
US 20050008079A1 · Boon et al. · 2005 [cited by applicant]
US 20050008240A1 · Banerji et al. · 2005 [cited by applicant]
US 20050053158A1 · Regunathan et al. · 2005 [cited by applicant]
US 20050141620A1 · Hattori · 2005 [cited by applicant]
US 20050286634A1 · Duvivier · 2005 [cited by applicant]
US 20060115001A1 · Wang et al. · 2006 [cited by applicant]
US 20060146734A1 · Wenger et al. · 2006 [cited by applicant]
US 20070104269A1 · Xue et al. · 2007 [cited by applicant]
US 20070280345A1 · Tu et al. · 2007 [cited by applicant]
US 20070280346A1 · Tu et al. · 2007 [cited by applicant]
US 20070291978A1 · Kim et al. · 2007 [cited by applicant]
US 20080151997A1 · Oguz · 2008 [cited by applicant]
US 20080170629A1 · Shim et al. · 2008 [cited by applicant]
US 20080219349A1 · Huang · 2008 [cited by examiner]
US 20080267287A1 · Hannuksela · 2008 [cited by applicant]
US 20090010331A1 · Jeon et al. · 2009 [cited by applicant]
US 20090010334A1 · Ueda et al. · 2009 [cited by applicant]
US 20090028448A1 · Colomosse et al. · 2009 [cited by applicant]
US 20090141814A1 · Yin · 2009 [cited by applicant]
US 20090245349A1 · Zhao et al. · 2009 [cited by applicant]
US 20090304086A1 · Shi · 2009 [cited by applicant]
US 20090316793A1 · Yang et al. · 2009 [cited by applicant]
US 20090323809A1 · Raveendran · 2009 [cited by applicant]
US 20100128797A1 · Dey · 2010 [cited by examiner]
US 20100128803A1 · Divorra Escoda et al. · 2010 [cited by applicant]
US 20100135416A1 · Huang et al. · 2010 [cited by applicant]
US 20100158401A1 · Shiraishi et al. · 2010 [cited by applicant]
US 20100189181A1 · Zheng et al. · 2010 [cited by applicant]
US 20100254458A1 · Amon · 2010 [cited by applicant]
US 20100296585A1 · Matsuura · 2010 [cited by examiner]
US 20100303153A1 · Kadono · 2010 [cited by applicant]
US 20110116545A1 · Zan · 2011 [cited by applicant]
US 20120044994A1 · Suzuki · 2012 [cited by applicant]
US 20120082244A1 · Chen et al. · 2012 [cited by applicant]
US 20120106622A1 · Huang · 2012 [cited by applicant]
US 20120106629A1 · Zheng et al. · 2012 [cited by applicant]
US 20120163452A1 · Horowitz · 2012 [cited by applicant]
US 20120163453A1 · Horowitz · 2012 [cited by applicant]
US 20120183074A1 · Fuldseth · 2012 [cited by applicant]
US 20150092842A1 · Horowitz · 2015 [cited by applicant]
US 20150237352A1 · Horowitz · 2015 [cited by applicant]
US 20150245025A1 · Horowitz · 2015 [cited by applicant]
US 20180367798A1 · Horowitz · 2018 [cited by applicant]
US 20190208212A1 · Horowitz · 2019 [cited by applicant]
US 20210243449A1 · Horowitz · 2021 [cited by applicant]
US 20220394271A1 · Horowitz · 2022 [cited by applicant]
US 20230242954A1 · Horowitz · 2023 [cited by applicant]
CA 2314333 · 2002 [cited by applicant]
CN 1286572 · 2001 [cited by applicant]
CN 1397138 · 2003 [cited by applicant]
CN 1477852 · 2004 [cited by applicant]
CN 1482808 · 2004 [cited by applicant]
CN 1520189 · 2004 [cited by applicant]
CN 1756363 · 2006 [cited by applicant]
CN 1774934 · 2006 [cited by applicant]
CN 1965321 · 2007 [cited by applicant]
CN 101004641 · 2007 [cited by applicant]
CN 101115195 · 2008 [cited by applicant]
CN 101252694 · 2008 [cited by applicant]
CN 101325698 · 2008 [cited by applicant]
CN 101345083 · 2009 [cited by applicant]
CN 101389021 · 2009 [cited by applicant]
CN 101490968 · 2009 [cited by applicant]
CN 101490969 · 2009 [cited by applicant]
CN 101543076 · 2009 [cited by applicant]
CN 101682786 · 2010 [cited by applicant]
CN 101740082 · 2010 [cited by applicant]
CN 101822054 · 2010 [cited by applicant]
CN 101924938 · 2010 [cited by applicant]
EP 2528331 · 2012 [cited by applicant]
JP 2009049460 · 2009 [cited by applicant]
WO WO2003094530 · 2003 [cited by applicant]
WO WO2006024922 · 2006 [cited by applicant]
WO WO2008057308 · 2008 [cited by applicant]
WO WO2010039731 · 2010 [cited by applicant]
WO WO2011089798 · 2011 [cited by applicant]
WO WO2013060250 · 2013 [cited by applicant]
WO WO2013060250A1 · 2013 [cited by examiner]
Bossen, “Common test conditions and software reference configurations,” JCT-VC Document JCTVC-B300, Geneva, Jul. 2010, 12 pages. [cited by applicant]
Bross et al., “WD4: Working Draft 4 of High-Efficiency Video Coding,” Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11, JCTVC-F803_d0, 6th Meeting: Torino, IT, Jul. 14-22, 2… [cited by applicant]
Bross et al., “WD5: Working Draft 5 of High-Efficiency Video Coding,” Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11, G1103_d0, 7th Meeting: Geneva, CH, Nov. 26-20, 2011, … [cited by applicant]
Coban et al., “Unification of picture partitioning schemes,” Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11, 7th Meeting: Geneva, CH, 21-30, dated Nov. 2011, 4 pages. [cited by applicant]
Dhondt et al., “Flexible macroblock ordering as a content adaption tool in H.264/AVC,” Proceedings of SPIE, Oct. 24, 2005, 6015:601506-1-601506-9. [cited by applicant]
EP Extended European Search Report in European Appln. No. 11853888.3, dated Jun. 2, 2015, 5 pages. [cited by applicant]
EP Notice of Opposition in European Appln. No. 11853888.3, dated Feb. 4, 2021, 50 pages. [cited by applicant]
EP Office Action in European Appln. No. 11853888.3, dated Sep. 15, 2021, 43 pages. [cited by applicant]
EP Opposition Proceedings in European Appln. No. 11853888.3, dated Oct. 26, 2021, 55 pages. [cited by applicant]
European Search Report issued in EP11852303.4 on Jun. 2, 2015, 6 pages. [cited by applicant]
Extended European Search Report in European Appln. No. 20166614.6, dated Jul. 21, 2020, 4 pages. [cited by applicant]
Extended European Search Report in European Appln. No. 22154252.5, dated Jun. 13, 2022, 8 pages. [cited by applicant]
Fuldseth et al., “Tiles,” Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11, JCTVC-E408_r1, 5th Meeting: Geneva, CH, Mar. 16-23, 2011, 14 pages. [cited by applicant]
International Bureau of WIPO, International Search Report and Written Opinion of International Searching Authority dated Apr. 17, 2012, issued in respect of International Application No. PCT/CA2011/001412, 10 pages. [cited by applicant]
International Bureau of WIPO, International Search Report and Written Opinion of International Searching Authority dated Mar. 20, 2012, issued in respect of International Application No. PCT/CA2011/001411, 8 pages. [cited by applicant]
International Preliminary Report on Patentability in International Application No. PCT/CA2011/001411, dated Jul. 2, 2013, 5 pages. [cited by applicant]
International Preliminary Report on Patentability in International Application No. PCT/CA2011/001412, dated Jul. 2, 2013, 7 pages. [cited by applicant]
ITU-T Recommendation H.263 version 2 (H.263+), “Video coding for low bit rate communication,” 1998, 167 pages. [cited by applicant]
ITU-T Recommendation H.264 and ISO/IEC 14496-10, “Advanced Video Coding for Generic Audiovisual Services,” Mar. 2010, 676 pages. [cited by applicant]
JCT-VC, “Test Model under Consideration Software 0.9-ahg-slices,” retrieved on Dec. 11, 2014, retrieved from the Internet: URL: https://hevc.hhi.fraunhofer.de/svn/svn_HEVCSoftware/branches/0.9-ahg-slices/, 1 page. [cited by applicant]
JCT-VC, “Test Model Under Consideration”, Apr. 15, 2010. [cited by applicant]
Misra et al., “Entropy slices for parallel entropy coding,” JCT-VC Document, JCTVC-C256, Guangzhou, Oct. 2010, 6 pages. [cited by applicant]
Seitner et al., “Evaluation of data-parallel splitting approaches for H.264 decoding,” Proceedings of the 6th International Conference on Advances in Mobile Computing and Multimedia, Nov. 2008, 10 pages. [cited by applicant]
Sjoberg and Wennersten, “Fine granularity slices,” JCT-VC Document, JCTVC-C154, Guangzhou, Oct. 2010, 4 pages. [cited by applicant]
Sullivan et al., “Overview of the High Efficiency Video Coding (HEVC) Standard,” IEEE Transactions on Circuits and Systems for Video Technology, Dec. 2012, 22(12):1649-1668. [cited by applicant]
Sun et al., “A highly efficient parallel algorithm for H.264 encoder based on Macro-Block region partition,” Proceedings of 3rd International HPCC, Sep. 26-28, 2007, pp. 577-585. [cited by applicant]
Wang et al., “A Novel Macro-Block Group Scheme of AVS Coding for Many-Core Processor',” Journal of Signal processing Systems, Oct. 2011, 12 pages. [cited by applicant]
Wang et al., “Dependency and loop filtering control over tile boundaries,” Document: JCTVC-G317, JCT-VC of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11, 7th Meeting: Geneva, CH, Nov. 21-30, 2011, 7 pages. [cited by applicant]
Wenger and Horowitz, “Flexible Macroblock ordering (FMO),” JVT-C089, May 2002, 22 pages. [cited by applicant]
Zhou, “Sub-picture based raster scanning coding order for HEVC UHD video coding,” JCTVC-B062, Geneva, Jul. 2010, 4 pages. [cited by applicant]
[No Author Listed], “Video coding for low bit rate communication; H.263 Annex U (Nov. 2000); Enhanced reference picture selection mode,” ITU-T Standard Superseded, International Telecommunication Union, Geneva, CH, H.26… [cited by applicant]