Quadtree-structured walsh transform coding

• US 5,768,434 A
• Filed: 06/07/1995
• Issued: 06/16/1998
• Est. Priority Date: 11/15/1993
• Status: Expired due to Term

• Current Assignee: National Semiconductor Corporation (Texas Instruments, Inc.)
• Original Assignee: National Semiconductor Corporation (Texas Instruments, Inc.)
• Inventors: Ran, Xiaonong
• Primary Examiner(s): Couso, Yon
• Assistant Examiner(s): DEL ROSSO, GERARD DOMNICK
• Application Number:
  US08/479,888
• Time in Patent Office: 1,105 Days
• Field of Search: 382/281, 382/282, 382/232, 382/240, 382/248, 382/250
• US Class Current: 382/240
• CPC Class Codes: H04N 11/042 Codec means
• CPC Class Codes: H04N 19/119 Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks
• 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/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/137 Motion inside a coding unit, e.g. average field, frame or block difference
• 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/154 Measured or subjectively estimated visual quality after decoding, e.g. measurement of distortion use of rate-distortion criteria H04N19/147
• CPC Class Codes: H04N 19/17 the unit being an image region, e.g. an object
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• 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/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding

Abstract

Two dimensional data structures are represented by quadtree codes with embedded Walsh transform coefficients. The quadtree code permits both variable block size inherent in quadtrees, and the calculational simplicity of Walsh transform descriptions of nearly uniform blocks of data. Construction of the quadtree is calculationally simple for implementation in a digital system which does a bottom-up determination of the quadtree because Walsh transform coefficients and a measure of the distortion can be recursively calculated using only Walsh transform coefficients from the previous level in the quadtree. Uniform step size quantization, which is optimal for variable length coding and generalized gaussian distributions, permits fast encoding and decoding of quadtree code.

Claims

1. A method for displaying an image which is represented by a quadtree code, the method comprising the steps of:

storing a portion of a quadtree code in a memory, the quadtree code including values which indicate leaf nodes and values which indicate a fixed number of coefficients for each of the leaf nodes. wherein the leaf nodes correspond to blocks in a quadtree partition of the image. and for each leaf node, the coefficients for that leaf node are Walsh transform coefficients of a matrix of pixel values which represents a block corresponding to that leaf node;

determining, from the quadtree code, Walsh transform coefficients for a selected one of the leaf nodes;

performing an inverse Walsh transformation on a matrix containing the Walsh transform coefficients for the selected leaf node, to generate pixel values which indicate colors for pixels in a block that corresponds to the selected leaf node; and

displaying a portion of the image by displaying the pixels with colors as indicated by the generated pixel values.

2. The method of claim 1, wherein displaying the pixels with colors comprises displaying the pixels with shades of gray.

3. The method of claim 1, wherein the blocks comprise pixels on a video display screen.

4. The method of claim 1, wherein displaying the pixels comprises printing with a printer.

5. The method of claim 1, wherein displaying the pixels further comprises using each pixel value generated by the inverse Walsh transformation as a color component in a pixel map of the image.

6. A method for representing a visual image as digital signals, the method comprising the steps of:

representing the image as a two-dimensional array of values, each value indicating a color for a pixel within the image;

partitioning the two-dimensional array to form a quadtree partition, the guadtree partition comprising blocks of data representing portions of the image;

generating signals which identify the blocks in the quadtree partition; and

generating, for each block in the quadtree partition, signals which indicate a fixed number of Walsh transform coefficients representing that block.

7. The method of claim 6, wherein partitioning the two-dimensional array to form a quadtree partition, comprises:

forming an intermediate partition of the two dimensional array, the intermediate partition containing four blocks which when combined form a merged block;

determining a measure of additional error caused by representing the merged block with the fixed number of Walsh transform coefficients instead of separately representing each of the four blocks with the fixed number of Walsh transform coefficients; and

replacing the four blocks in the intermediate partition with the merged block if the additional error is less than a threshold value.

8. The method of claim 7, wherein the additional error and the fixed number of Walsh transform coefficients for the merged block are determined from the fixed number of Walsh transform coefficients for each of the four blocks in the intermediate partition.

9. The method of claim 6, wherein the steps of generating signals comprises transmitting digital signals.

10. The method of claim 6, wherein the steps of generating signals further comprises storing in a memory the values indicated by the signals.

11. The method of claim 6, wherein:

a series of partitions of the two-dimensional array contains a partition corresponding to each value of an index I with N<

I<

M, wherein the partition corresponding to each value of the index I contains 4^I non-intersecting blocks of data from the two-dimensional array, N and M are integers with N<

M, and for each integer J with N<

J<

M, each block in a partition corresponding to J equals a union of four blocks in a partition corresponding to J+1;

each block in the partition corresponding to the integer M consists of x² values, x being a power of two;

each block in the partition corresponding to an integer M-1 consists of 4*x² values; and

partitioning the two-dimensional array to form the quadtree partition, further comprises the steps of;

performing a Walsh transform on each block of the partition corresponding to the integer M to derive y Walsh transform coefficients, where y is an integer less than or equal to x² ;

determining an error for each block in the partition corresponding to the integer M-1, wherein the error depends on a first set of 4*x² values generated by an inverse Walsh transform of a 2x-by-2x matrix having at most y non-zero coefficients, and a second set of 4*x² values generated by inverse Walsh transforms of four x-by-x matrices, each of the four x-by-x matrices containing the y Walsh transform coefficients derived for a block which is in the partition corresponding to M and is a subset of the block for which the error is being determined; and

including in the quadtree partition four blocks from the partition corresponding to the integer M, wherein a union of the four blocks equals a block having an error greater than a predetermined threshold value.

12. The method of claim 11, wherein the step of partitioning the two-dimensional array to form the quadtree partition further comprises the steps of:

(a) forming an intermediate partition initially consisting of all the blocks in the partition corresponding to the integer M;

(b) selecting a partition from the series of partitions, wherein the selected partition corresponds to an integer K-1, and K is the smallest integer such that a partition corresponding to K contains a block which is also contained in the intermediate partition;

(c) determining an error for each block which is both in the selected partition and equal to a union of four blocks in the intermediate partition, wherein the error indicates an incremental difference between values in the block in the selected partition and values generated by an inverse Walsh transform of a matrix having no more than x² non-zero coefficients;

(d) removing from the intermediate partition each set of four blocks which has a union equal to a block that is in the selected partition and has an error determined in step (c) to be less that the predetermined value;

(e) inserting into the intermediate partition each block that equals a union of a set of four blocks which were removed in step (d); and

(f) if after step (e) the intermediate partition contains a block from the selected partition then repeating steps (b) through (f), otherwise selecting the intermediate partition as the quadtree partition.

13. The method of claim 12, wherein step (c) further comprises determining a sum of squares of differences between values in the block of the selected partition and corresponding values generated by the inverse Walsh transform of the matrix having no more than x² non-zero coefficients.

14. The method of claim 12, wherein step (c) further comprises determining a sum of absolute values of differences between values in the block of the selected partition and corresponding values generated by the inverse Walsh transform of the matrix having no more than x² non-zero coefficients.

15. The method of claim 12, wherein step (c) further comprises determining a largest absolute difference between a value in the block of the selected partition and a corresponding value generated by the inverse Walsh transform of the matrix having no more than x² non-zero coefficients.

16. The method of claim 6, wherein the step of generating signals which identify the blocks in the quadtree partition comprises the sequential steps of:

providing a signal for each block which is in a first partition from a series of uniform partitions, wherein the signal for a block has a first value if the block is in the quadtree partition and has a second value otherwise; and

for each block in a second partition from the series of uniform partitions;

providing a signal having the first value if the block in the quadtree partition; and

providing a signal having the second value if the block is not in the quadtree partition and is not a subset of a block in the quadtree partition.

17. The method of claim 6, wherein:

a series of partitions of the two-dimensional array contains a partition corresponding to each value of an index I with N<

I<

M, wherein the partition corresponding to each value of the index I contains 4^I non-intersecting blocks of data from the two-dimensional array, wherein N and M are integers with N<

M, and wherein for each integer J with N<

J<

M, each block in a partition corresponding to J equals a union of four blocks in a partition corresponding to J+1; and

generating signals which identify the blocks in the quadtree partition further comprises the sequential steps of;

providing a signal having a first value for each of a sequence of one or more blocks, wherein no two blocks in the sequence of blocks are in the same partition in the series of partitions, each block in the sequence is a subset of preceding block, and none of the blocks in the sequence is in the quadtree partition; and

providing a signal having a second value for a block which is in the quadtree partition and is a subset of the last block of the sequence.

18. The method of claim 17, wherein generating signals which identify the blocks in the quadtree partition further comprises providing a signal having a value for a block which is in a same partition as the block for which the second value was provided and is a subset of the last block of the sequence.

19. The method of claim 6, wherein generating signals which identify the blocks in the quadtree partition further comprises providing signals with values that indicate which blocks from a series of uniform partitions are in the quadtree partition, wherein the values that indicate blocks are provided in a walking-the-tree order.

20. The method of claim 6, wherein the two-dimensional array represents a difference image.

21. The method of claim 6, wherein each value in the two-dimensional array represents an intensity for a pixel within the image.

22. A method for transmitting signals which represents an image, the method comprising the steps of:

generating a representation of the image, the representation including a two-dimensional array of values;

partitioning the two-dimensional array into 4^I non-intersecting blocks, each block containing N² values of an N-by-N matrix corresponding to the block, wherein I is a positive integer, and N is a non-negative power of two;

selecting from the 4^I blocks a set of four neighboring blocks which together include (2N)² values that constitute a first 2N-by-2N matrix;

determining, for each of the four neighboring blocks, M Walsh transform coefficients of the N-by-N matrix corresponding to the block, where M is an integer less than or equal to N² ;

determining M Walsh transform coefficients of the first 2N-by-2N matrix;

measuring a differences between a second 2N-by-2N matrix and a third 2N-by-2N matrix, wherein the second 2N-by-2N matrix is generated by an inverse Walsh transform of four N-by-N matrices, each of which contains M Walsh transform coefficients for a corresponding one of the four neighboring block, and the third 2N-by-2N matrix is generated by an inverse Walsh transformation of a 2N-by-2N matrix containing the M Walsh transform coefficients of the first 2N-by-2N matrix; and

transmitting digital signals which represent the image by indicating the M Walsh transform coefficients for the four neighboring blocks when the difference is greater than a threshold value.

23. The method of claim 22, wherein measuring the difference further comprises determining a sum of squares of differences between values in the second 2N-by-2N matrix and corresponding values in the third 2N-by-2N matrix.

24. The method of claim 22, wherein measuring the difference further comprises determining a sum of absolute values of differences between values in the second 2N-by-2N matrix and corresponding values in the third 2N-by-2N matrix.

25. The method of claim 22, wherein measuring the difference further comprises determining a largest absolute difference between a value in the first 2N-by-2N matrix and a corresponding value in the second 2N-by-2N matrix.

26. An apparatus for encoding an image, comprising:

a memory;

an input device coupled to the memory, the input device receiving a signal which represents the image as a two-dimensional data structure, wherein the input device stores the two-dimensional data structure in the memory; and

a processor coupled to the memory, wherein the processor comprises;

means for generating a quadtree partition of a two-dimensional data structure stored in the memory, the quadtree partition consisting of blocks from a series of partitions of the two-dimensional data structure, wherein the blocks in the quadtree partition are selected according to errors introduced by representing the blocks with a fixed number of Walsh transform coefficients per block;

means for generating a code which indicates which of the blocks of the series of partitions are in the quadtree partition of the two-dimensional data structure; and

means for generating the fixed number of Walsh transform coefficients for each block in the quadtree partition.

27. The apparatus of claim 26, wherein the means for generating a quadtree partition comprises:

means for initializing an intermediate partition to equal a first partition from the series of partitions; and

means for pruning the intermediate partition by;

determining an error for each block which is in a second partition from the series of partitions and equals a union of four blocks in the intermediate partition, wherein the error determined for a block indicates a combined difference between values in the block and values generated by an inverse Walsh transform of a matrix having at most a predetermined number of non-zero coefficient;

removing from the intermediate partition each set of four blocks which have a union equal to a block that is in the second partition and has a determined error less than a predetermined value; and

inserting into the intermediate partition each block which is in the second partition and has a determined error less than the predetermined value.

28. The apparatus of claim 26, wherein for each block in a first partition from the series of partitions, the means for generating a code generates a first symbol if the block in the quadtree partition of the image and generates a second symbol if block which is and not in the quadtree partition.

29. The apparatus of claim 26, wherein the means for generating a code provides values that indicate which blocks from the series of partitions are in the quadtree partition, wherein the values, that indicate which blocks are in the quadtree partition, are provided in a walking-the-tree order.