Source: https://patents.google.com/patent/US7933337?oq=6233682
Timestamp: 2018-04-25 04:08:47
Document Index: 50016253

Matched Legal Cases: ['art 3', 'art 3', 'Application No. 565593', 'Application No. 565593', 'Application No. 2006280178', 'Application No. 200680029296', 'art 2', 'art 2', 'Application No. 2006280178', 'Application No. 2008', 'Application No. 200680029296', 'Application No. 2008105032', 'Application No. 200680029296']

US7933337B2 - Prediction of transform coefficients for image compression - Google Patents
Prediction of transform coefficients for image compression Download PDF
US7933337B2
US7933337B2 US11203009 US20300905A US7933337B2 US 7933337 B2 US7933337 B2 US 7933337B2 US 11203009 US11203009 US 11203009 US 20300905 A US20300905 A US 20300905A US 7933337 B2 US7933337 B2 US 7933337B2
US11203009
US20070036224A1 (en )
FIG. 4 is a diagram of a 4×4 transform block structure illustrating DC and DCAC coefficients.
The 2D data encoder 200 produces a compressed bitstream 220 that is a more compact representation (for typical input) of 2D data 210 presented as input to the encoder. For example, the 2D data input can be an image, a frame of a video sequence, or other data having two dimensions. The 2D data encoder tiles 230 the input data into macroblocks, which are 16×16 pixels in size in this representative encoder. The 2D data encoder further tiles each macroblock into 4×4 blocks. A “forward overlap” operator 240 is applied to each edge between blocks, after which each 4×4 block is transformed using a block transform 250. This block transform 250 can be the reversible, scale-free 2D transform described by Srinivasan, U.S. patent application Ser. No. 11/015,707, entitled, “Reversible Transform For Lossy And Lossless 2-D Data Compression,” filed Dec. 17, 2004. The overlap operator 240 can be the reversible overlap operator described by Tu et al., U.S. patent application Ser. No. 11/015,148, entitled, “Reversible Overlap Operator for Efficient Lossless Data Compression,” filed Dec. 17, 2004; and by Tu et al., U.S. patent application Ser. No. 11/035,991, entitled, “Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform,” filed Jan. 14, 2005. Alternatively, the discrete cosine transform or other block transforms and overlap operators can be used. Subsequent to the transform, the DC coefficient 260 of each 4×4 transform block is subject to a similar processing chain (tiling, forward overlap, followed by 4×4 block transform). The resulting DC transform coefficients and the AC transform coefficients are quantized 270, entropy coded 280 and packetized 290.
As discussed above, the encoder 200 tiles the input image or picture into macroblocks. In an exemplary implementation, the encoder 200 tiles the input image into 16×16 macroblocks in the Y channel (which may be 16×16, 16×8 or 8×8 areas in the U and V channels depending on the color format). Each macroblock color plane is tiled into 4×4 regions or blocks. Therefore, a macroblock is composed for the various color formats in the following manner for this exemplary encoder implementation:
FIGS. 4, 5 and 6 illustrate examples of various transform blocks in the representative encoder/decoder. FIG. 4 illustrates a 4×4 transform block for blocks in the luminance channel of the various formats, as well as the chrominance channels of a YUV 4:4:4 color format image. FIG. 5 shows a 422 chroma low pass block format, which contains the transform block coefficients from the inner stage transform of the chroma channel of a YUV 422 color format image. FIG. 6 shows a 420 chroma low pass block containing the coefficients from the inner stage transform of the chroma channel of a YUV 4:2:0 color format image.
1. The DC coefficients (of the inner transform) are predicted based on DC coefficients from causal neighboring blocks based at least in part on color information when available.
2. The DCAC coefficients of the inner transform use a prediction direction derived from that of the DC coefficients, and also rely on out-of-macroblock information.
3. The prediction of DCAC coefficients of the inner transform is skipped (i.e. 0 is used as the predictor) when the current and predicting macroblocks have different quantizers.
4. The prediction of DCAC coefficients of the outer transform is performed purely within the macroblock.
5. The prediction direction of the outer transform DCAC coefficients is derived from DCAC coefficients of the inner transform of the same macroblock.
In the description below, the predictive transform coefficient coding is described as being performed on the quantized transform coefficients (e.g., the transform coefficients after quantization 270 in the encoder 200 of FIG. 2, and before de-quantization 330 in the decoder 300 of FIG. 3). However, it should be understood that alternative implementations of the predictive transform coefficient coding technique could be performed on the unquantized transform coefficients (or on dequantized values on the decoder side).
1. DC prediction, which is the prediction of DC coefficients of the inner transform,
2. Low pass DCAC prediction, which is the prediction of DCAC coefficients of the inner transform, and
3. High pass DCAC prediction, which is the prediction of DCAC coefficients of the outer transform.
2.1 DC Prediction
As described above, the representative encoder 200 (FIG. 2) tiles an image into macroblocks of 16×16 pixels, and further tiles the macroblocks into transform blocks of 4×4 pixels each. The outer stage transform is applied to the transform blocks, producing blocks containing 4×4 transform coefficients as shown in FIG. 4 (for the luminance channel, as well as the chrominance channels of a YUV 4:4:4 color format image). The DC coefficients in these 16 transform coefficient blocks of the macroblock are separated (forming a 4×4 block), and an inner stage of the transform is applied to this block. The resulting inner stage transform block again has 4×4 coefficients. The DC coefficient (labeled ‘0’) of this inner stage transform block is referred to herein as the DC coefficient of the macroblock. The DCAC coefficients (‘1,’ ‘2,’ ‘3,’ ‘4,’ ‘8,’ and ‘12’) of the inner stage transform block are referred to herein as the low pass DCAC coefficients of the macroblock. This macroblock structure can be varied in alternative encoders and decoder employing the predictive transform coefficient coding.
1. Predict from left (i.e., the predictor for the DC coefficient of the macroblock is the DC coefficient of the macroblock to its left, or predictor=DC [left_MB]).
2. Predict from top (i.e., the predictor is the DC coefficient of the macroblock above it, predictor=DC [top_MB])
3. Predict from left and top (i.e., the predictor is an average of the DC coefficients of the macroblocks to its left and above, predictor=(DC [left_MB]+DC [top_MB])/2)
4. Null predict (i.e., no prediction, predictor=0)
The encoder determines which prediction mode to use for a macroblock according to the procedure illustrated by the pseudo-code listing 1000 in FIG. 10. In the listing 1000, the value [mx,my] is an index of the current macroblock in an image (or an image tile, if tiling is used) in terms of an offset number of macroblocks in horizontal (x) and vertical directions (y) starting from a top, left macroblock at [0,0].
1. Predict from left (i.e., the predictor for the low pass DCAC coefficients of the macroblock is the corresponding DCAC coefficient of the macroblock to its left, or predictor=DCAC [left_MB])—in which case coefficients marked ‘4’, ‘8’ and ‘12’ alone are predicted;
2. Predict from top (i.e., the predictor is the corresponding low pass DCAC coefficient of the macroblock above it, predictor=DCAC [top_MB])—in which case coefficients marked ‘1’ , ‘2’ and ‘3’ alone are predicted; and
3. Null predict (no predication, or predictor=0).
The encoder determines which prediction mode to use for a macroblock according to the procedure illustrated by the pseudo-code listing 1100 in FIG. 11. In the illustrated procedure, the encoder determines which low pass DCAC prediction mode is used based on the DC prediction mode of the macroblock, together with the quantizer indices of the current macroblock and macroblock that is the DC predictor. This rule ensures that the prediction of inner transform DCAC coefficients does not take place across macroblocks with different quantizers. Further, DCAC is predicted only if one direction is dominant, which is derived per the DC prediction mode procedure detailed above (i.e., the DC prediction mode is “predict from left” or “predict from top” when horizontal or vertical dominance is found).
1. Predict from left (i.e., the predictor for the high pass DCAC coefficient of the block is the correspondingly-located high pass DCAC coefficient of the block to its left, or predictor=DCAC [left_MB], as illustrated for left-predicted DCAC coefficients of macroblock 1300 in FIG. 13);
2. Predict from top (i.e., the predictor is the corresponding location, high pass DCAC coefficient of the block above it, predictor =DCAC [top_MB], as illustrated for top-predicted DCAC coefficients of macroblock 1400 in FIG. 14); and
In the representative encoder/decoder, the same mode is applied to all blocks within a macroblock for which in-macroblock prediction is possible (but, alternative implementations need not apply the same mode to all blocks in a macroblock). In other words, no prediction is made for high pass DCAC coefficients of blocks that have no valid reference within the macroblock, even though the “predict from left” or “predict from top” mode is selected for the macroblock.
US11203009 2005-08-12 2005-08-12 Prediction of transform coefficients for image compression Active 2029-10-06 US7933337B2 (en)
US11203009 US7933337B2 (en) 2005-08-12 2005-08-12 Prediction of transform coefficients for image compression
KR20087003318A KR101247042B1 (en) 2005-08-12 2006-08-03 Prediction of transform coefficients for image compression
EP20060789459 EP1922874A4 (en) 2005-08-12 2006-08-03 Prediction of transform coefficients for image compression
CA 2617632 CA2617632C (en) 2005-08-12 2006-08-03 Prediction of transform coefficients for image compression
PCT/US2006/030563 WO2007021613A3 (en) 2005-08-12 2006-08-03 Prediction of transform coefficients for image compression
JP2008526092A JP5065272B2 (en) 2005-08-12 2006-08-03 Prediction of transform coefficients for image compression
RU2008105032A RU2406255C2 (en) 2005-08-12 2006-08-03 Forecasting conversion ratios for image compression
CN 200680029296 CN101243685B (en) 2005-08-12 2006-08-03 Coding method, processing method and processing device for digital media data
US20070036224A1 true US20070036224A1 (en) 2007-02-15
US7933337B2 true US7933337B2 (en) 2011-04-26
ID=37742497
US11203009 Active 2029-10-06 US7933337B2 (en) 2005-08-12 2005-08-12 Prediction of transform coefficients for image compression
US (1) US7933337B2 (en)
EP (1) EP1922874A4 (en)
JP (1) JP5065272B2 (en)
KR (1) KR101247042B1 (en)
CN (1) CN101243685B (en)
CA (1) CA2617632C (en)
RU (1) RU2406255C2 (en)
WO (1) WO2007021613A3 (en)
US20090238481A1 (en) * 2008-03-21 2009-09-24 Novatek Microelectronics Corp. Method and apparatus for generating coded block pattern for highpass coefficients
US20110182357A1 (en) * 2008-06-24 2011-07-28 Sk Telecom Co., Ltd. Intra prediction method and apparatus, and image encoding/decoding method and apparatus using same
US20120128066A1 (en) * 2009-08-06 2012-05-24 Panasonic Corporation Encoding method, decoding method, encoding device and decoding device
JP4761566B2 (en) * 2006-12-13 2011-08-31 キヤノン株式会社 The image processing apparatus, method and program, and medium
JP5061330B2 (en) * 2008-05-12 2012-10-31 株式会社メガチップス Image processing apparatus
JP5015088B2 (en) * 2008-08-06 2012-08-29 株式会社リコー Image processing apparatus, image processing method, a computer program, and an information recording medium
WO2010041858A3 (en) 2008-10-06 2010-07-22 Lg Electronics Inc. A method and an apparatus for decoding a video signal
US20120127002A1 (en) * 2009-08-06 2012-05-24 Youji Shibahara Coding method, decoding method, coding apparatus, and decoding apparatus
KR20120046728A (en) * 2009-08-06 2012-05-10 파나소닉 주식회사 Encoding method, decoding method, encoding device and decoding device
KR20110015356A (en) * 2009-08-07 2011-02-15 한국전자통신연구원 Video encoding and decoding apparatus and method using adaptive transform and quantization domain that based on a differential image signal characteristic
EP2526696A4 (en) * 2010-01-22 2014-06-04 Thomson Licensing Method and device for encoding an image block of an image and corresponding decoding method and device
CN102447895B (en) * 2010-09-30 2013-10-02 华为技术有限公司 Scanning method, scanning device, anti-scanning method and anti-scanning device
US20130003838A1 (en) * 2011-06-30 2013-01-03 Futurewei Technologies, Inc. Lossless Coding and Associated Signaling Methods for Compound Video
US6173080B2 (en)
EP0833520A2 (en) 1996-09-30 1998-04-01 Hyundai Electronics Industries Co., Ltd. Video predictive coding apparatus and method
RU2123769C1 (en) 1993-04-09 1998-12-20 Сони Корпорейшн Method and device for encoding images and information medium for storing images
US5959674A (en) 1996-09-21 1999-09-28 Samsung Electronics Co., Ltd. Prediction method for discrete cosine transform coefficients
US6173080B1 (en) 1996-09-21 2001-01-09 Samsung Electronics Co., Ltd. Prediction method for discrete cosine transform coefficient
GB2341031B (en) 1998-08-31 2001-05-02 Daewoo Electronics Co Ltd Method and apparatus for adaptively coding video signals
US6925249B1 (en) 2000-07-28 2005-08-02 Microsoft Corporation System and method for storing compressed data onto a storage medium
US20080198933A1 (en) 2007-02-21 2008-08-21 Microsoft Corporation Adaptive truncation of transform coefficient data in a transform-based ditigal media codec
EP1465431B1 (en) 1996-09-20 2015-07-15 AT&T Corp. Video coder providing implicit coefficient prediction and scan adaption for image coding and intra coding of video
JPH0360293A (en) * 1989-07-28 1991-03-15 Victor Co Of Japan Ltd Method and apparatus for compressing video signal and method and apparatus for expanding video signal
EP0645930B1 (en) 1993-04-09 2000-06-14 Sony Corporation Method and apparatus for coding image
"ISO/IEC 11172-3, Information Technology-Coding of Moving Pictures and Associated Audio for Digital Storage Media at Up to Ab out 1.5 Mbit/s-Part 3: Audio," 154 pp. (1993).
"ISO/IEC 11172-3, Information Technology—Coding of Moving Pictures and Associated Audio for Digital Storage Media at Up to Ab out 1.5 Mbit/s—Part 3: Audio," 154 pp. (1993).
Advanced Television Systems Committee, "ATSC Standard: Digital Audio Compression (AC-3), Revision A," 140 pp. (1995).
De Agostino et al., "Parallel Algorithms for Optimal Compression using Dictionaries with the Prefix Property," Proc. Data Compression Conference '92, IEEE Computer Society Press, pp. 52-62 (1992).
Examination Report and Notice of Acceptance of Complete Specification dated Mar. 22, 2010, from New Zealand Patent Application No. 565593, 1 pp.
Examination Report dated Sep. 24, 2009, from New Zealand Patent Application No. 565593, 2 pp.
Examiner's First Report dated Oct. 31, 2008, from Australian Patent Application No. 2006280178, 2 pp.
First Office Action dated Apr. 10, 2009, from Chinese Patent Application No. 200680029296.3, 11 pp.
Gersho et al., "Vector Quantization and Signal Compression," pp. 259-305 (1992).
Gibson et al., Digital Compression for Multimedia, "Chapter 7: Frequency Domain Coding," Morgan Kaufmann Publishers, Inc., pp. 227-262 (1998).
Gill et al., "Creating High-Quality Content with Microsoft Windows Media Encoder 7," 4 pp. (2000) [Downloaded from the World Wide Web on May 1, 2002].
Hui et al., "Matsushita Algorithm for Coding of Moving Picture Information," ISO/IEC-JTC1/SC29/WG11, MPEG91/217, 76 pp. (Nov. 1991).
International Search Report and Written Opinion for PCT/US06/30563, dated Oct. 17, 2007, 8 pages.
International Search Report and Written Opinion for PCT/US06/30566 dated Sep. 28, 2007.
ISO/IEC, "ISO/IEC 11172-2, Information Technology-Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to About 1.5 Mbit/s-Part 2: Video," 112 pp. (1993).
ISO/IEC, "ISO/IEC 11172-2, Information Technology—Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to About 1.5 Mbit/s—Part 2: Video," 112 pp. (1993).
Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, "Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification (ITU-T Rec. H.264, ISO/IEC 14496-10 AVC)," 253 pp. (May 2003).
Najafzadeh-Azghandi, "Perceptual Coding of Narrowband Audio Signals," Thesis, 139 pp. (Apr. 2000).
Notice of Acceptance dated Dec. 7, 2009, from Australian Patent Application No. 2006280178, 2 pp.
Notice of Rejection dated Oct. 28, 2010, from Japanese Patent Application No. 2008-526092, 6 pp.
Notice of the Third Office Action dated Apr. 26, 2010, from Chinese Patent Application No. 200680029296.3, 8 pp.
Official Decision of Grant dated Jun. 15, 2007, from Russian Patent Application No. 2008105032, 20 pp.
OPTX International, "New Screen Watch(TM) 4.0 Clikc and Stream(TM) Wizard from OPTX International Makes Workplace Communication Effortless," 1 p., document marked Sep. 24, 2001 [Downloaded from the World Wide Web on Sep. 22, 2005].
OPTX International, "New Screen Watch™ 4.0 Clikc and Stream™ Wizard from OPTX International Makes Workplace Communication Effortless," 1 p., document marked Sep. 24, 2001 [Downloaded from the World Wide Web on Sep. 22, 2005].
OPTX International, "OPTX Improves Technology-Based Training with Screen Watch™ 3.0. Versatile Screen Capture Software Adds High Color and Live Webcast Support," 1 p., document marked Feb. 15, 2001 [Downloaded from the World Wide Web on Sep. 22, 2005].
Printouts of FTP directories from http://ftp3.itu.ch, 8 pp. [Downloaded from the World Wide Web on Sep. 20, 2005].
Schaar-Mitrea et al., "Hybrid Compresion of Video with Graphics in DTV Communication Systems," IEEE Trans. on Consumer Electronics, pp. 1007-1017 (2000).
Second Office Action dated Dec. 4, 2009, from Chinese Patent Application No. 200680029296.3, 13 pp.
Techsmith Corporation, "Camtasia v.3.0.1—README.TXT," 19 pp. (Jan. 2002).
Wien et al., "16 Bit Adaptive Block Size Transforms," JVT-C107r1, 54 pp.
Zhang, "Robust Decoding for Reduced Error Propagation of DC/AC Prediction Errors," 2001 Proceedings of Workshop and Exhibition on MPEG-4, 2001, 4 pages.
US8711945B2 (en) * 2006-09-22 2014-04-29 Canon Kabushiki Kaisha Methods and devices for coding and decoding images, computer program implementing them and information carrier enabling their implementation
US9313525B2 (en) 2008-06-24 2016-04-12 Sk Telecom Co., Ltd. Intra prediction method and apparatus, and image encoding/decoding method and apparatus using same
US9319714B2 (en) 2008-06-24 2016-04-19 Sk Telecom Co., Ltd. Intra prediction method and apparatus, and image encoding/decoding method and apparatus using same
US8976862B2 (en) * 2008-06-24 2015-03-10 Sk Telecom Co., Ltd. Intra prediction method and apparatus, and image encoding/decoding method and apparatus using same
US9300981B2 (en) 2008-06-24 2016-03-29 Sk Telecom Co., Ltd. Intra prediction method and apparatus, and image encoding/decoding method and apparatus using same
US20070036224A1 (en) 2007-02-15 application
CA2617632A1 (en) 2007-02-22 application
WO2007021613A2 (en) 2007-02-22 application
KR101247042B1 (en) 2013-03-25 grant
EP1922874A4 (en) 2011-08-31 application
CA2617632C (en) 2014-04-22 grant
RU2406255C2 (en) 2010-12-10 grant
JP2009505496A (en) 2009-02-05 application
CN101243685A (en) 2008-08-13 application
KR20080042816A (en) 2008-05-15 application
EP1922874A2 (en) 2008-05-21 application
CN101243685B (en) 2015-06-17 grant
JP5065272B2 (en) 2012-10-31 grant
WO2007021613A3 (en) 2007-12-06 application
RU2008105032A (en) 2009-08-20 application
US7305139B2 (en) 2007-12-04 Reversible 2-dimensional pre-/post-filtering for lapped biorthogonal transform
US20050238096A1 (en) 2005-10-27 Fractional quantization step sizes for high bit rates
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:SRINIVASAN, SRIDHAR;TU, CHENGJIE;REEL/FRAME:016447/0071