Source: https://patents.justia.com/patent/10694186
Timestamp: 2020-08-07 22:27:37
Document Index: 30796897

Matched Legal Cases: ['Application No. 1155606', 'Application No. 201510562762', 'Application No. 201510562762', 'Application No. 201611156281', 'Application No. 201611156278', 'Application No. 201611156265', 'Application No. 201611156261', 'Application No. 201611156270', 'Application No. 7080', 'Application No. 10', 'Application No. 10', 'Application No. 10', 'Application No. 10', 'Application No. 2018', 'Application No. 10', 'Application No. 10', 'Application No. 201611156281', 'Application No. 201611156281']

US Patent for Method of coding and decoding images, coding and decoding device and computer programs corresponding thereto Patent (Patent # 10,694,186 issued June 23, 2020) - Justia Patents Search
Justia Patents Block CodingUS Patent for Method of coding and decoding images, coding and decoding device and computer programs corresponding thereto Patent (Patent # 10,694,186)
Jun 7, 2019 - Dolby Labs
This Application is a continuation of U.S. application Ser. No. 16/012,658, filed Jun. 19, 2018, which is a continuation of U.S. application Ser. No. 15/486,660, filed Apr. 13, 2017, U.S. Pat. No. 10,033,999, which is a continuation of U.S. application Ser. No. 15/008,614, filed Jan. 28, 2016, now issued on May 23, 2017 as U.S. Pat. No. 9,661,335, which is a continuation of U.S. application Ser. No. 14/662,395, filed Mar. 19, 2015, now issued on Apr. 19, 2016 as U.S. Pat. No. 9,319,693, which is a division of U.S. application Ser. No. 14/492,750, filed Sep. 22, 2014, now issued on Jun. 28, 2016 as U.S. Pat. No. 9,380,308, which is a continuation of U.S. application Ser. No. 14/128,949, filed Apr. 21, 2014, now issued on Apr. 19, 2016 as U.S. Pat. No. 9,319,692, which is a Section 371 National Stage Application of International Application No. PCT/FR2012/051391, filed Jun. 20, 2012, which is published as WO 2012/175870 on Dec. 27, 2012, not in English, which claims priority to French Application No. 1155606, filed on Jun. 24, 2011, and for which the entire contents of each of the above-identified applications are hereby expressly incorporated by reference into the present application.
The invention can thus, in particular, be applied to video coding implemented in current video coders (MPEG, H.264, etc.) or forthcoming video coders (ITU-T/VCEG (H.265) or ISO/MPEG (HVC)).
arithmetic coding: the coder, such as described initially in the document J. Rissanen and G. G. Langdon Jr, “Universal modeling and coding,” IEEE Trans. Inform. Theory, vol. IT-27, pp. 12-23, January 1981, uses, to code a symbol, a probability of occurrence of this symbol;
During the coding of a given symbol b that may equal 0 or 1, the learning of the probability pi of occurrence of this symbol is updated for a current block MBi in the following manner
where a is a predetermined value, for example 0.95 and pi-1 is the symbol occurrence probability calculated upon the last occurrence of this symbol.
The document, which is available at the Internet address http://research.microsoft.comlen-us/um/people/jinVlpaper_2002/msri_jpeg.htm on the date of 15 Apr. 2011, describes a method for coding still images compliant with the JPEG2000 compression standard. According to this method, the still image data undergo a discrete wavelet transform followed by a quantization, thereby making it possible to obtain quantized wavelet coefficients with which are respectively associated quantization indices. The quantization indices obtained are coded with the aid of an entropy coder. The quantized coefficients are previously grouped into rectangular blocks called code-blocks, typically 64×64 or 32×32 in size. Each code-block is thereafter coded independently by entropy coding. Thus, the entropy coder, when it undertakes the coding of a current code-block, does not use the symbol occurrence probabilities calculated during the coding of previous code-blocks. The entropy coder is therefore in an initialized state at each start of coding of a code-block. Such a method exhibits the advantage of decoding the data of a code-block without having to decode the neighboring code-blocks. Thus for example, a piece of client software may request a piece of server software to provide the compressed code-blocks needed solely by the client to decode an identified sub-part of an image. Such a method also presents the advantage of permitting the parallel encoding and/or decoding of the code-blocks. Thus, the smaller the size of the code-blocks, the higher the level of parallelism. For example, for a level of parallelism fixed at two, two code-blocks will be coded and/or decoded in parallel. In theory, the value of the level of parallelism is equal to the number of code-blocks to be coded of the image. However, the compression performance obtained with this method is not optimal having regard to the fact that such coding does not exploit the probabilities arising from the immediate environment of the current code-block.
According to a second example, the state variables of the entropy coding module are the strings of symbols contained in the translation table of an LZW (Lempel-Ziv-Welch) entropy coder, well known to the person skilled in the art, and described at the following Internet address on the date of 21 Jun. 2011: http J/en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch.
DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS A First Embodiment of the Coding Part
With reference to FIG. 2A, the first coding step C1 is the segmenting of an image IE of a sequence of images to be coded into a plurality of blocks or macro-blocks MBi as represented in FIG. 4A or 4B. Said macro-blocks are able to contain one or more symbols, said symbols forming part of a predetermined set of symbols. In the examples represented, said blocks MB have a square shape and all have the same size. As a function of the size of the image which is not necessarily a multiple of the size of the blocks, the last blocks on the left and the last blocks at the bottom may not be square. In an alternative embodiment, the blocks can be for example of rectangular size and/or not aligned with one another.
With reference to FIG. 2A, the third coding step C3 consists in the coding of each of said subsets of blocks SE1 to SE6, the blocks of a subset under consideration being coded according to a predetermined order of traversal PS, which is for example of sequential type. In the examples represented in FIGS. 4A and 4B, the blocks of a current subset SEk (1≤k≤P) are coded one after another, from left to right, as indicated by the arrow PS.
According to a second variant, such a coding is of the parallel type and is distinguished from the first variant of sequential coding, solely by the fact that it is implemented by a predetermined number R of coding units UCk (1≤k≤R), with R=2 in the example represented in FIG. 3C. Such parallel coding is known to engender a substantial acceleration of the coding method.
With reference to FIG. 2A, the fourth coding step C4 is the production of L sub-streams F1, F2, . . . , Fm, . . . , FL (1≤m≤L≤P) of bits representing the processed blocks compressed by the aforementioned coding unit UC or each of the aforementioned coding units UCk, as well as a decoded version of the processed blocks of each subset SEk. The decoded processed blocks, denoted SED1, SED2, . . . , SEDk, . . . , SEDP, of a subset under consideration may be reused by the coding unit UC represented in FIG. 3A or each of the coding units UCk represented in FIG. 3C, according to a synchronization mechanism which will be detailed further on in the description.
In the course of a following sub-step C344, there is undertaken the quantization of the transformed block MBt1 according to a conventional quantization operation, such as for example a scalar quantization. A block of quantized coefficients MBq is then obtained.
In the course of a following sub-step C346, there is undertaken the dequantization of the block MBq1 according to a conventional dequantization operation, which is the operation inverse to the quantization performed in step C344. A block of de-quantized coefficients MBDq1 is then obtained.
In the course of a following sub-step C347, there is undertaken the inverse transformation of the block of de-quantized coefficients MBDq which is the operation inverse to the direct transformation performed in step C343 hereinabove.
A decoded residual block MBDr1 is then obtained.
If such is not the case, there is undertaken, in the course of step C39, the selection of the next block MBi to be coded in accordance with the order of traversal represented by the arrow PS in FIG. 4A or 4B.
With reference to FIG. 5A, the first decoding step D1 is the identification in said stream F of the L sub-streams F1, F2, . . . , Fm, . . . , FL containing respectively the P subsets SE1, SE2, . . . , SEk, . . . , SEP of previously coded blocks or macro-blocks MBi as represented in FIG. 4A or 4B. For this purpose, each sub-stream Fm in the stream F is associated with an indicator intended to allow the decoder DO to determine the location of each sub-stream Fm in the stream F. As a variant, on completion of the aforementioned coding step C3, the coder CO orders the sub-streams F1, F2, . . . , Fm, . . . , FL in the stream F, in the order expected by the decoder DO, thereby avoiding the insertion into the stream F of the sub-stream indicators. Such a provision thus makes it possible to reduce the cost in terms of bitrate of the data stream F.
With reference to FIG. 5A, the second decoding step D2 is the decoding of each of said subsets of blocks SE1, SE2, SE3 and SE4, the blocks of a subset under consideration being coded according to a predetermined sequential order of traversal PS. In the example represented in FIG. 4A or 4B, the blocks of a current subset SEk (1≤k≤P) are decoded one after another, from left to right, as indicated by the arrow PS. On completion of step D2, the decoded subsets of blocks SED1, SED2, SED3, . . . , SEDk, . . . , SEDP are obtained.
However, so as to be able to benefit from a multiplatform decoding architecture, the decoding of the subsets of blocks is of parallel type and is implemented by a number R of decoding units UDk (1≤k≤R), with for example R=4 as represented in FIG. 6A. Such a provision thus allows a substantial acceleration of the decoding method. In a manner known per se, the decoder DO comprises a buffer memory MT which is adapted to contain the symbol occurrence probabilities such as progressively reupdated in tandem with the decoding of a current block.
If such is not the case, there is undertaken, in the course of step D29, the selection of the next block MBi to be decoded in accordance with the order of traversal represented by the arrow PS in FIG. 4A or 4B.
The coding unit UC codes the rows SE1, SE2, SE3, SE4, SE5 and SE6 sequentially. In the example represented, rows SE1 to SE4 are fully coded, row SE5 is in the course of being coded and row SE6 has not yet been coded. Having regard to the sequentiality of the coding, the coding unit UC is adapted for delivering a stream F which contains the sub-streams F1, F2, F3, F4 ordered one following after another, in the order of coding of the rows SE1, SE2, SE3 and SE4. For this purpose, the sub-streams F1, F2, F3 and F4 are symbolized with the same hatching as that which respectively symbolizes the coded rows SE1, SE2, SE3, SE4. By virtue of the emptying steps at the end of the coding of said coded rows and of the reinitialization of the interval of probabilities on commencing the coding or the decoding of the next row to be coded/decoded, the decoder DO, each time that it reads a sub-stream so as to decode it, is in an initialized state and can therefore, in an optimal manner, decode in parallel the four sub-streams F1, F2, F3, F4 with decoding units UD1, UD2, UD3 and UD4 which can for example be installed on four differentplatforms.
1. A method for entropy decoding, the method comprising:
receiving, by a decoder, a data stream representative of a coded image;
identifying, in the data stream, a plurality of rows of consecutive blocks of quantized coefficients of transformed residual values for the coded image;
initializing one or more state variables for entropy decoding a current block in a current row of the plurality of rows;
entropy decoding the current block based on the one or more state variables for entropy decoding the current block,
wherein when the current block is a first block in the current row in a decoding order for decoding the coded image and the current row is not the first row of the plurality of rows in the decoding order, the one or more state variables for decoding the current block are initialized based on one or more state variables of a predetermined entropy decoded block,
wherein the predetermined entropy decoded block is a second block in the decoding order in a row of consecutive blocks other than the current row,
wherein entropy decoding a block comprises partitioning an interval into a plurality of sub-intervals where the sub-intervals represent probabilities of occurrence of symbols, and
wherein when the current block is a last block in the current row in decoding order, the interval is reinitialized;
predictive decoding the current block with respect to at least one previously decoded block;
obtaining a quantized residual block using syntax elements corresponding to the entropy decoding of the current block; and
dequantizing the quantized residual block to obtain a decoded dequantized block.
2. The method of claim 1, wherein entropy decoding the current block comprises decoding of the syntax elements related to the current block.
3. The method of claim 2, wherein predictive decoding the current block comprises predictive decoding the current block using the syntax elements.
4. A method for coding an image, the method comprising:
grouping the blocks into a predetermined number of rows of blocks;
coding, using an entropy coding module, a current block of the rows of blocks, wherein the coding comprises: when the current block is a first block in an encoding order of a row that is not the first row of the image in the encoding order: determining probabilities of symbol occurrence obtained by coding a predetermined block of at least one other row, wherein the predetermined block is the second block in the encoding order in the other row; initializing state variables of the entropy coding module with the determined probabilities; and coding the current block, wherein coding the current block includes quantization of a transformed block obtained by transformation of a residual block that is produced by subtracting a predicted block from the current block, wherein the predicted block is an approximation of the current block obtained using predictive coding; when the current block is a last block in the encoding order of the row that is not the first row of the image in the encoding order: emptying a buffer memory corresponding to the entropy coding module, comprising extracting untransmitted bits from the buffer memory and writing the untransmitted bits to a data stream destined for a decoding module; and initializing state variables of the entropy coding module, including initializing an interval to a range between a high bound and a low bound; and
generating at least one data stream for the image.
6480537 November 12, 2002 Agarwal et al.
9042457 May 26, 2015 Hayashi
9271012 February 23, 2016 Henry et al.
9319692 April 19, 2016 Henry et al.
9319693 April 19, 2016 Henry et al.
9319694 April 19, 2016 Henry et al.
9338469 May 10, 2016 Amon
9380308 June 28, 2016 Henry et al.
9560380 January 31, 2017 Henry et al.
9628818 April 18, 2017 Henry et al.
9648325 May 9, 2017 Baeza
9654783 May 16, 2017 Henry et al.
9661335 May 23, 2017 Henry et al.
9848196 December 19, 2017 Henry et al.
1003399 July 2018 Henry et al.
1036231 July 2019 Henry et al.
1038278 August 2019 Henry et al.
20060008079 January 12, 2006 Daemen et al.
20080279182 November 13, 2008 Hafeez et al.
20090175331 July 9, 2009 Karczewicz et al.
20090225234 September 10, 2009 Ward et al.
20090279613 November 12, 2009 Suzumura
20100052956 March 4, 2010 Choo et al.
20100215030 August 26, 2010 Agrawal et al.
20120183074 July 19, 2012 Fuldseth
20120314944 December 13, 2012 Ninan et al.
20140334557 November 13, 2014 Schierl et al.
1527610 September 2004 CN
1547854 November 2004 CN
1717050 January 2006 CN
101198051 June 2008 CN
101411197 April 2009 CN
101491097 July 2009 CN
101653003 February 2010 CN
101981934 February 2011 CN
2006141037 June 2006 JP
2006279574 October 2006 JP
2007142637 June 2007 JP
2009111605 May 2009 JP
2014525187 September 2014 JP
2015516747 June 2015 JP
1020140131926 November 2014 KR
WO2008036237 March 2008 WO
WO2010063184 June 2010 WO
WO2011/045339 April 2011 WO
WO2011042645 April 2011 WO
WO-2011045339 April 2011 WO
WO2011046339 April 2011 WO
WO2011/052142 May 2011 WO
WO2012/175870 December 2012 WO
WO2013153226 October 2013 WO
WO2013010997 January 2016 WO
Felix et al. “Wavefront Parallel Processing” JCT-VC, Mar. 18, 2011.
Huang et al., “Ordered Entropy Slices for Parallel CODEC,” ITU-T SG 16 Q.6 Video Coding Experts Group 38th Meeting. VCEG-AL25 rev.1, Jul. 5, 2009, pp. 1-10.
International Preliminary Report on Patentability issued in PCT/FR2012/051391, dated Dec. 23, 2013, 7 pages (in French).
International Preliminary Report on Patentability issued in PCT/FR2012/050380 dated Sep. 13, 2013, 6 pages (in French).
International Search Report issued in PCT/FR2012/050380 dated May 8, 2012, with English translation, 7 pages.
International Search Report issued in PCT/FR2012/051391, dated Aug. 9, 2012, with English translation, 7 pages.
Lee, et al., “High-Efficiency Video Compression Framework Based on Flexible Unit Representation,” Proceedings of the second APSIPA Annual Summit and Conference, Dec. 17, 2010, pp. 6523-631.
Li, “Image Compression—The Mechanics of the JPEG 2000,” http://research.microsoft.com/en-us/um/people/jinl/papers_2002/ms . . . , 20 pages.
Marpe et al., “Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard”, IEEE Transactions on Circuits and Systems for Video Technology, IEEE Service Center, Piscataway, NJ, USA, vol. 13, No. 7, Jul. 1, 2003 (Jul. 1, 2003 ), pp. 620-636, XP011099255.
Marpe et al., “Improved CABAC”, 15. VCEG Meeting; 58; MPEG Meeting; Dec. 4-6, 2011; Pattaya, Th; (Video Coding Experts Group of ITU-T SG.16), No. VCEG-018, Nov. 28, 2001 (Nov. 28, 2001), pp. 1-6, XP030003351.
Marpe et al., “Context-based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard,” IEEE Trans. on CSVT, Jul. 2003, vol. 13, No. 7, pp. 620-636.
Saito and 1 other, “HD-SDI H.264 Super-Low Delay Encoder/Decoder ‘EHH-1000E/D’ and its application,” Eizo Joho Industrial, No. Feb. 2009 (vol. 41, No. 2), Sangyo Kaihatsukiko Inc., Feb. 1, 2009, pp. 15 to 20, ISSN: 1346-1362.
Schwarz H. et al., CABAC and Slices 4. JVT Meeting; Jul. 22-26, 2002; Klagenfurt, Austria; (Joint Video Team of ISO/IEC MPEG & ITO/T VCEG-ISO/IEC JTC1/SC29/WG11 and ITU-T SG. 16 0.6), No. JVT-D020r1 Jul. 22, 2002 (Jul. 22, 2002), pp. 1-17, XP002671680.
Sharp, “Entropy slices for parallel entropy decoding,” ITU-I SG16 Meeting, Apr. 22, 2008-May 2, 2008, Geneva, pp. 1-9 (Apr. 14, 2008).
Sze et al., “Massively Parallel CABAG,” 38th VCEG Meeting, 89 MPEG Meeting, Jul. 1, 2009-Jul. 8, 2009, London, Geneva (Video Coding Experts Group of ITU-T SG. 16), pp. 1-10 (Jul. 3, 2009).
Chinese Office Action in Chinese Application No. 201510562762.5, dated May 23, 2018, 19 pages.
Chinese Office Action in Chinese Application No. 201510562762.5, dated Sep. 5, 2017.
CN Office Action Issued in Chinese Application No. 201611156281.5, dated Dec. 4, 2018, 13 pages.
CN Office Action Issued in Chinese Application No. 201611156278.3, dated Oct. 8, 2018, 17 pages.
CN Office Action Issued in Chinese Application No. 201611156265.6 dated Dec. 3, 2018, 14 pages.
CN Office Action Issued in Chinese Application No. 201611156261.8, dated Dec. 3, 2018, 14 pages.
CN Office Action Issued in Chinese Application No. 201611156270.7, dated Dec. 3, 2018, 14 pages.
IN Office Action Issued in Indian Application No. 7080/CHENP/2013, dated Mar. 25, 2019, 19 pages.
Korean Notice of Allowance in Korean Application No. 10-2016-7018776, dated Jan. 23, 2018, 13 pages (with English translation).
Korean Office Action in Korean Application No. 10-2016-7018759, dated Nov. 28, 2017, 10 pages (with English translation).
Korean Office Action in Korean Application No. 10-2017-7037608, dated Feb. 12, 2018, 6 pages (with English translation).
Kr Office Action Issued in Korean Application No. 10-2017-7037608, dated Dec. 17, 2018, 86 pages.
Notice of Allowance issued in U.S. Appl. No. 14/128,949 dated Jan. 5, 2016, 5 pages.
Notice of Allowance issued in U.S. Appl. No. 14/492,546 dated Oct. 15, 2015, 41 pages.
Notice of Allowance issued in U.S. Appl. No. 14/492,750 dated Jan. 20, 2016, 10 pages.
Notice of Allowance issued in U.S. Appl. No. 14/662,395 dated Dec. 18, 2015, 5 pages.
Office Action issued in CN 2012-80021355.8 dated Mar. 29, 2016, with English Translation.
Office Action issued in JP2014-516422 dated Jan. 6, 2016, with English translation, 20 pages.
Office Action issued in U.S. Appl. No. 14/003,014 dated Dec. 2, 2015, 39 pages.
Office Action issued in U.S. Appl. No. 14/128,949 dated Apr. 10, 2015, 19 pages.
Office Action issued in U.S. Appl. No. 14/128,949 dated Aug. 31, 2015, 11 pages.
Office Action issued in U.S. Appl. No. 14/492,546 dated Feb. 4, 2015, 29 pages.
Office Action issued in U.S. Appl. No. 14/492,750 dated Apr. 13, 2015, 17 pages.
Office Action issued in U.S. Appl. No. 14/492,750 dated Aug. 7, 2015, 11 pages.
Office Action issued in U.S. Appl. No. 14/662,395 dated Aug. 31, 2015, 12 pages.
Office Action issued in U.S. Appl. No. 14/662,395 dated May 7, 2015, 19 pages.
Office Action issued in U.S. Appl. No. 14/662,463 dated May 6, 2015, 20 pages.
Office Action issued in U.S. Appl. No. 14/662,463 dated Sep. 1, 2015, 12 pages.
Written Opinion issued in PCT/FR2012/051391, dated Aug. 9, 2012, with English Translation, 14 pages.
Written Opinion of the International Searching Authority issued in PCT/FR2012/050380 dated May 8, 2012, with English translation, 11 pages.
Clare et al., “Wavefront and Cabac Flush: Different Degrees of Parallelism Without Transcoding,” Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11 6th Meeting: Torino, IT, Jul. 14-22, 2011, [JCTVC-F275], ITU-T, Jul. 1, 2011, JCTVC-F275 (version 1), pp. 1-11.
Moccagatta, “Arbitrary Slice Order and Flexible Macroblock Order Impact of AVC Compliance and Implementation Complexity,” Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG (ISO/IEC JTC1/SC29/WG11 and ITU-T SG16 Q.6) 4th Meeting: Klagenfurt, Austria, Jul. 22-26, 2002, [JVT-D115], ITU-T, Jan. 17, 2005, pp. 1-9.
JP Office Action in Japanese Application No. 2018-145539, dated Sep. 3, 2019, 9 pages (with English translation).
Korean Notice of Allowance in Korean Application No. 10-2018-7002895, dated Jun. 26, 2019, 8 pages (with English translation).
KR Office Action Issued in Korean Application No. 10-2019-7021045, dated Aug. 9, 2019, (with English translatation).
Misra et al., “Entropy Slices for Parallel Entropy Coding,” JCTVC-C256, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11, 3rd Meeting: Guangzhou, CN, Oct. 7-15, 2010, 6 pages.
CN Office Action Issued in Chinese Application No. 201611156281.5, dated Sep. 17, 2019, 4 pages.
CN Office Action Issued in Chinese Application No. 201611156281.5, dated Sep. 17, 2019, 12 pages (with English translation).
Patent number: 10694186
Patent Publication Number: 20190297323
Primary Examiner: James T Boylan
Application Number: 16/435,317
International Classification: H04N 19/13 (20140101); H04N 19/70 (20140101); H04N 19/196 (20140101); H04N 19/50 (20140101); H04N 19/503 (20140101); H04N 19/51 (20140101); H04N 19/61 (20140101); H04N 19/593 (20140101); H04N 19/124 (20140101); H04N 19/137 (20140101); H04N 19/174 (20140101); H04N 19/44 (20140101); H04N 19/436 (20140101); H04N 19/625 (20140101); H04N 19/176 (20140101); H04N 19/91 (20140101); H04N 19/136 (20140101); H04N 19/119 (20140101);