Embedded block coding with optimized truncation

• US 6,778,709 B1
• Filed: 03/12/1999
• Issued: 08/17/2004
• Est. Priority Date: 03/12/1999
• Status: Expired due to Term

• Current Assignee: Dolby International AB (Dolby Laboratories Incorporated)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Taubman, David S.
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US09/267,248
• Time in Patent Office: 1,985 Days
• Field of Search: 358/426, 358/432, 358/426.01, 358/426.13, 358/426.14, 382/232-233, 382/239, 382/240, 382/248-253, 375/240.05, 375/240.11, 375/240.18, 375/240-1-2, 348/394.1, 348/395.1, 348/398.1, 348/405.1, 348/408.1, 348/420.1
• US Class Current: 382/240
• CPC Class Codes: H04N 19/647 using significance based coding, e.g. Embedded Zerotrees of Wavelets [EZW] or Set Partitioning in Hierarchical Trees [SPIHT]
• CPC Class Codes: H04N 19/70 characterised by syntax aspects related to video coding, e.g. related to compression standards
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding

Abstract

A multi-layer embedded bitstream is generated from a subband decomposition by partitioning each subband of the decomposition into a plurality of blocks; and encoding the blocks of each subband. The blocks of each subband are coded independently of each other. Resulting is a block bitstream corresponding to each block. Truncation points may be identified on the block bitstreams, and selected portions of the block bitstreams may be concatenated, layer-by-layer, to form the single-layer or multi-layer bitstream. Syntax information may also be added to the multi-layer bitstream. An image can be reconstructed from the embedded bitstream at a desired bit-rate or resolution by reading the syntax information, randomly accessing desired portions of the block bitstreams, decoding the randomly accessed portions, dequantizing the decoded portions, and applying an inverse transform to the dequantized portions.

Claims

1. A method for processing a plurality of subbands of a subband decomposition, the method comprising:

partitioning each subband into a plurality of disjoint blocks;

dividing each block into a plurality of disjoint sub-blocks; and

coding the blocks bit-plane by bit-plane, the blocks of each subband being coded independently of each other;

wherein a given bit-plane of a block is coded by arithmetically coding the bit-plane bit of each sub-block that is significant with respect to the given bit-plane.

2. The method of claim 1, wherein transform coefficients of the blocks are quantized prior to coding, a constant base quantization being used as a step size.

3. The method of claim 1, wherein a multi-level quad tree decomposition is performed on each block to identify significant transform coefficients in the blocks.

4. The method of claim 1, wherein each bit-plane is coded in multiple passes, sub-blocks containing significant coefficients with respect to a previous bit-plane being coded on all but a final pass, sub-blocks containing significant coefficients with respect to a current bit-plane being coded on the final pass.

5. The method of claim 4, wherein the multiple passes include a Forward Significance Propagation coding pass, a Backward Significance Propagation coding pass, a Magnitude Refinement coding pass, and a Normalization coding pass.

6. The method of claim 4, wherein the bit-plane coding is performed by using arithmetic coding operations including Zero Coding, Run-Length Coding, Sign Coding and Magnitude Refinement.

7. The method of claim 1, further comprising generating a block bitstream for each block;

gathering distortion statistics about each of the blocks as the blocks; and

using the distortion statistics to identify candidate truncation points for each of the block bitstreams.

8. The method of claim 7, wherein a given bitstream is truncated by determining rate-distortion slopes at different truncation points of the given bitstream.

9. The method of claim 8, wherein distortion reduction incurred during a single coding pass is determined by the steps including summing outputs of f_s(·

) whenever a sample becomes significant and by summing outputs of f_m(·

) whenever a magnitude is refined.

10. The method of claim 1, wherein context during the coding is shared among sub-blocks of a block.

11. A method for processing a plurality of subbands of a subband decomposition, the method comprising:

partitioning each subband into a plurality of disjoint blocks;

coding the blocks of each subband, a block bitstream being generated for each block;

ordering a plurality of the block bitstreams into a layered, embedded bitstream; and

adding a block bitstream syntax to the layered bitstream, the syntax allowing different types of processing to be performed on the same block bitstreams.

12. The method of claim 11, wherein the layered bitstream includes multiple layers, wherein each layer corresponds to a discrete bit rate, and wherein portions of the block bitstreams are ordered according to bit rate.

13. The method of claim 11, wherein the layered bitstream includes multiple layers, wherein the layers correspond to different levels of image resolution, and wherein portions of the block bitstreams are ordered according to image resolution.

14. The method of claim 11, wherein the bitstream syntax includes a plurality of tag bocks for each layer, each tag block identifying portions of corresponding block bitstreams, the tag blocks being organized according to a tag tree structure.

15. The method of claim 11, wherein the bitstream syntax includes a sequence of code bits for each layer, each sequence of code bits identifying the block bitstream portions that are included from each subband, each sequence of code bits further providing information concerning the maximum bi-depth, truncation point, and number of code bytes being sent for each included code block.

16. Apparatus for generating an embedded bitstream from image data, the apparatus comprising:

a transform engine for performing a frequency-based transform of the image data, each frequency-based component produced by the transform including a plurality of disjoint blocks of transform coefficients; and

a coding engine for dividing each block into a plurality of disjoint sub-blocks; and

coding the blocks bit-plane by bit-plane independently of other blocks within the same component, wherein a given bit-plane of a block is coded by arithmetically coding the bit-plane bit of each sub-block that is significant with respect to the given bit-plane.

17. The apparatus of claim 16, wherein the coding engine uses a multi-level quad tree decomposition to determine whether each sub-block contains significant coefficients.

18. The apparatus of claim 16, wherein each bit-plane is coded in multiple passes, sub-blocks containing significant coefficients with respect to a previous bit-plane being coded on all but a final pass, sub-blocks containing significant coefficients with respect to a current bit-plane being coded on the final pass.

19. The apparatus of claim 18, wherein the multiple passes include a Forward Significance Propagation coding pass, a Backward Significance Propagation coding pass, a Magnitude Refinement coding pass, and a Normalization coding pass.

20. The apparatus of claim 18, wherein the bit-plane coding is performed by using arithmetic coding operations including Zero Coding, Run-Length Coding, Sign Coding and Magnitude Refinement.

21. The apparatus of claim 16, wherein the coding engine also generates a block bitstream for each block;

gathers distortion statistics about each of the blocks as the blocks are being coded; and

, after the blocks have been coded, uses the distortion statistics to identify candidate truncation points for each of the block bitstreams.

22. The apparatus of claim 21, wherein a given bitstream is truncated by determining rate-distortion slopes at different truncation points of the given bitstream.

23. The apparatus of claim 22, wherein distortion reduction incurred during a single coding pass is determined by the steps including summing outputs of f_s(·

) whenever a sample becomes significant and by summing outputs of f_m(·

) whenever a magnitude is refined.

24. The apparatus of claim 16, wherein the coding engine quantizes transform coefficients of the blocks prior to coding, a constant base quantization being used as a step size.

25. Apparatus for generating an embedded bitstream from image data, the apparatus comprising:

a transform engine for performing a frequency-based transform of the image data, each frequency-based component produced by the transform including a plurality of disjoint blocks of transform coefficients; and

a coding engine for coding the blocks independently of other blocks within the same component, the coding engine generating an individual bitstream for each block, the coding engine ordering a plurality of block bitstreams into a layered, embedded bitstream, and adding a block bitstream syntax to the layered bitstream, the syntax allowing different types of processing to be performed on the same block bitstreams.

26. The apparatus of claim 25, wherein the layered bitstream includes multiple layers, wherein each layer corresponds to a discrete bit rate, and wherein portions of the block bitstreams are ordered according to bit rate.

27. The apparatus of claim 25, wherein the layered bitstream includes multiple layers, wherein the layers correspond to different levels of image resolution, and wherein portions of the block bitstreams are ordered according to image resolution.

28. The apparatus of claim 25, wherein the bitstream syntax includes a plurality of tag bocks for each layer, each tag block identifying portions of corresponding block bitstreams, the tag blocks being organized according to a tag tree structure.

29. The apparatus of claim 25, wherein the bitstream syntax includes a sequence of code bits for each layer, each sequence of code bits identifying the block bitstream portions that are included from each subband, each sequence of code bits further providing information concerning the maximum bit-depth, truncation point, and number of code bytes being sent for each included code block.

30. A method for processing a plurality of subbands of a subband decomposition, the method comprising:

partitioning each subband into a plurality of disjoint blocks;

coding the blocks bit-plane by bit-plane, the blocks of each subband being coded independently of each other; and

generating a block bitstream for each block;

gathering distortion statistics about each of the blocks as the blocks are being coded; and

using the distortion statistics to identify candidate truncation points for each of the block bitstreams.

31. The apparatus of claim 30, wherein each bitstream is truncated by determining rate-distortion slopes at different truncation points of the given bitstream.

32. The apparatus of claim 30, wherein distortion reduction incurred during a single coding pass is determined by steps including summing outputs of f_s(·

) whenever a sample becomes significant and by summing outputs of f_m(·

) whenever a magnitude is refined.