Image and video compression using sparse orthonormal transforms

• US 8,437,564 B2
• Filed: 08/05/2008
• Issued: 05/07/2013
• Est. Priority Date: 08/07/2007
• Status: Active Grant

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Inventors: Harmanci, Oztan, Guleryuz, Onur G., Sezer, Osman G.
• Primary Examiner(s): Alavi, Amir
• Assistant Examiner(s): CESE, KENNY A
• Application Number:
  US12/186,439
• Publication Number:
  US 20090060362A1
• Time in Patent Office: 1,736 Days
• Field of Search: 382232-253
• US Class Current: 382/248
• CPC Class Codes: H04N 19/12 Selection from among a plurality of transforms or standards, e.g. selection between discrete cosine transform [DCT] and sub-band transform or selection between H.263 and H.264
• CPC Class Codes: H04N 19/122 Selection of transform size, e.g. 8x8 or 2x4x8 DCT; Selection of sub-band transforms of varying structure or type
• CPC Class Codes: H04N 19/129 Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO]
• CPC Class Codes: H04N 19/139 Analysis of motion vectors, e.g. their magnitude, direction, variance or reliability
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/19 using optimisation based on Lagrange multipliers
• CPC Class Codes: H04N 19/192 the adaptation method, adaptation tool or adaptation type being iterative or recursive
• CPC Class Codes: H04N 19/196 being specially adapted for the computation of encoding parameters, e.g. by averaging previously computed encoding parameters processing of motion vectors H04N19/513
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/463 by compressing encoding parameters before transmission
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/619 the transform being operated outside the prediction loop
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets

Abstract

A method and apparatus is disclosed herein for performing compression with sparse orthonormal transforms. One method includes receiving a block of data; classifying the block of data based on directional structure; selecting one of a plurality of available directional, orthonormal transforms to apply to the block based on results of classifying the block; and applying the selected transform to the block to generate a plurality of coefficients, thereby producing a compressed version of the block.

Claims

1. A method comprising:

receiving a block of data;

classifying the block of data based on sparsity structure to obtain a block class;

selecting one of a plurality of available directional, sparse orthonormal transforms to apply to the block based on the block class of the block, the sparse transform having a one-to-one correspondence to the block class, and wherein sparse transforms of the plurality of directional, sparse orthonormal transforms are created for each block class by an iterative process, wherein for each iteration of the iterative process that creates the sparse transforms for each block class, the iterative process first optimizes the sparse transforms and coefficients for the transforms, and then reclassifies optimal transforms based on rate distortion; and

applying the selected transform to the block to generate a plurality of coefficients, thereby producing a compressed version of the block.

2. The method defined in claim 1 wherein results of classifying the block include block classification information indicative of a classification of the block.

3. The method defined in claim 2 further comprising sending the block classification information to a decoder.

4. The method defined in claim 3 wherein the block is part of an intra frame being compressed.

5. The method defined in claim 2 further comprising encoding the block classification information using a quadtree.

6. The method defined in claim 2 wherein results of classifying the block include block classification information, and further comprising a decoder deriving the block classification information indicative of a classification of the block from frame prediction.

7. The method defined in claim 6 further comprising predicting and conditionally encoding the classification information based on side-information that is determined and transmitted for the past frames.

8. The method defined in claim 6 wherein the decoder derives the block classification information when decompressing inter frames.

9. The method defined in claim 2 further comprising performing block based prediction of coefficients based on the block classification information and direction information.

10. The method defined in claim 1 wherein the data representing the block comprises a vector of transform coefficients.

11. The method defined in claim 10 wherein the vector of transform coefficients comprises one of a group consisting of a vector of lapped transform coefficients, a vector of wavelet transform coefficients, and a vector of Fourier transform coefficients.

12. The method defined in claim 11 wherein the block has a size of K×

K and the vector of transform coefficients has a second size of K²×

1, where K is an integer.

13. The method defined in claim 1 wherein one or more transforms of the plurality of directional transforms are created by an iterative process in which blocks of training data are classified and then subjected to the application of transforms repeatedly.

14. The method defined in claim 1 wherein the plurality of available transforms includes a DCT transform.

15. The method defined in claim 1 wherein the plurality of available transforms comprises transforms optimized for various quantization and block size parameters.

16. The method defined in claim 1 wherein each of the block classifications is associated with one of the plurality of available transforms.

17. The method defined in claim 16 wherein the block classifications and plurality of transforms are jointly and iteratively optimized in a rate-distortion sense.

18. The method defined in claim 1 further comprising:

reordering transform coefficients prior to encoding.

19. The method defined in claim 18 wherein each of the plurality of available transforms is associated with a distinct zig-zag pattern, and further comprising reordering transform coefficients comprises applying a zig-zag pattern associated with the transform coefficients.

20. The method defined in claim 18 further comprising:

quantizing the plurality of coefficients to produce quantized coefficients; and

entropy coding the quantized coefficients.

21. The method defined in claim 20 wherein the quantized coefficients comprise predicted coefficients.

22. The method defined in claim 18 further comprising:

generating prediction coefficients for the block;

computing residual coefficients as a difference between the prediction coefficients and the plurality of coefficients;

quantizing the residual coefficients to produce quantized coefficients; and

entropy coding the quantized coefficients.

23. The method defined in claim 1 wherein the block of data comprises one selected from a group consisting of an image and video.

25. The method defined in claim 1 further comprising:

generating side information that includes designed transforms and directional classification information; and

sending the side information to a decoder.

24. A method comprising:

receiving a block of data;

classifying the block of data based on sparsity structure to obtain a block class, wherein classifying the block of data based on sparsity structure comprises classifying the block selecting a Lagrange multiplier λ

based on a target distortion level and solving an equation for the block, where the equation is;

26. An article of manufacture having one or more non-transitory computer readable storage media storing instructions which, when executed by a system, cause the system to perform a method comprising:

receiving a block of data;

classifying the block of data based sparsity structure to obtain a block class;

selecting one of a plurality of available directional, sparse orthonormal transforms to apply to the block based on the block class of the block, the sparse transform having a one-to-one correspondence to the class, and wherein sparse transforms of the plurality of directional, sparse orthonormal transforms are created for each block class by an iterative process, wherein for each iteration of the iterative process that creates the sparse transforms for each block class, the iterative process first optimizes the sparse transforms and coefficients for the transforms, and then reclassifies optimal transforms based on rate distortion; and

applying the selected transform to the block to generate a plurality of coefficients, thereby producing a compressed version of the block.

27. A decoding process comprising:

receiving a compressed codestream;

determining a block classification for a group of coefficients in the compressed codestream;

selecting one of a plurality of available directional, sparse orthonormal inverse transforms based on the block classification, the sparse transform having a one-to-one correspondence to the block classification, and wherein sparse transforms of the plurality of directional, sparse orthonormal inverse transforms are created for each block classification by an iterative process, wherein for each iteration of the iterative process that creates the sparse transforms for each block class, the iterative process first optimizes the sparse transforms and coefficients for the transforms, and then reclassifies optimal transforms based on rate distortion; and

applying the selected inverse transform to the group of coefficients.

28. The decoding process defined in claim 27 further comprising deriving block classification information from frame prediction.

29. The decoding process defined in claim 27 wherein information indication of the block classification is encoded using a quadtree.