Digital data compression system including zerotree coefficient coding

• US 5,315,670 A
• Filed: 11/12/1991
• Issued: 05/24/1994
• Est. Priority Date: 11/12/1991
• Status: Expired due to Term

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Shapiro, Jerome M.
• Primary Examiner(s): Moore, David K.
• Application Number:
  US07/790,860
• Time in Patent Office: 924 Days
• Field of Search: 382/49, 382/56, 358/261.2, 358/261.1, 358/261.3, 358/427, 358/426, 358/432, 358/433, 381/31, 381/45, 381/49
• US Class Current: 382/240
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree
• CPC Class Codes: H04N 19/00 Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/647 using significance based coding, e.g. Embedded Zerotrees of Wavelets [EZW] or Set Partitioning in Hierarchical Trees [SPIHT]

Abstract

A data processing system augments compression of non-zero values of significant coefficients by coding entries of a significance map independently of coding the values of significant non-zero coefficients. A dedicated symbol represents a zerotree structure encompassing a related association of insignificant coefficients within the tree structure, thereby compactly representing each tree of insignificant coefficients. The zerotree symbol represents that neither a root coefficient of the zerotree structure nor any descendant of the root coefficient has a magnitude greater than a given reference level. The zerotree structure is disclosed in the context of a pyramid-type image subband processor together with successive refinement quantization and entropy coding to facilitate data compression.

Claims

1. A system for processing digital data comprising a plurality of image representative data elements, said system including:

means responsive to said data elements for providing coefficients representing data elements;

means for evaluating said coefficients to determine significant and insignificant coefficients;

means responsive to evaluated coefficients from said evaluating means for generating a zerotree structure of data representative coefficients, said tree structure having a path from an insignificant single root coefficient generated at a coarse level of information to insignificant descendant coefficients generated at all levels of relatively finer information, where coarse information is image information in a low frequency subband derived from image information over a given spatial area, and finer information is image information in relatively higher frequency subbands derived from image information over a relatively smaller spatial area;

first means for generating a symbol representing a related association of insignificant coefficients within said tree structure along said path encompassing said root coefficient and said descendant coefficients of said tree structure, said first means including means for comparing coefficients to a reference level so that said symbol represents that neither said root coefficient nor any descendant thereof has a magnitude greater than said reference level;

second means for generating a symbol representing a significant coefficient;

means for producing a dominant list of entries corresponding to insignificant coefficients, and a subordinate list of entries corresponding to significant coefficients; and

means for coding said symbols generated by said first and second generating means to produce an output bitstream;

wherein

said evaluating means evaluates each coefficient associated with respective entries of said dominant and subordinate lists at successively finer thresholds for progressively refining the contents of said dominant and subordinate lists.

2. A system according to claim 1, wherein said thresholds are successively halved.

3. A system for processing digital data representing an image composed of picture elements, said system including:

transform means for decomposing said image into a plurality of image representative subbands at each of plural decomposition levels, said transform means producing coefficients representing prescribed characteristics of picture elements;

means for evaluating said coefficients to determine significant and insignificant coefficients;

means responsive to evaluated coefficients from said evaluating means for generating a zerotree structure of data representative coefficients, said tree structure having a path from an insignificant single root coefficient generated at a coarse level of information to insignificant descendant coefficients generated at all levels of relatively finer information, where coarse information is image information in a low frequency subband derived from image information over a given spatial area, and finer information is image information in relatively higher frequency subbands derived from image information over a relatively smaller spatial area;

first means for generating a symbol representing a tree structure encompassing a related association of insignificant coefficients from plural decomposition levels within said tree structure along said path encompassing said root coefficient and said descendant coefficients, said first means including means for comparing coefficients to a reference level so that said symbol represents that neither said root coefficient nor any descendant thereof has a magnitude greater than said reference level;

second means for generating a symbol representing a significant coefficient;

means for producing a dominant list of entries corresponding to insignificant coefficients and a subordinate list of entries corresponding to significant entries; and

means for coding said symbols generated by said first and second generating means to produce an output bitstream;

wherein

said evaluating means evaluates each coefficient associated with respective entries of said dominant and subordinate lists at successively finer thresholds for progressively refining the contents of said dominant and subordinate lists.

4. Decoder apparatus for processing a coded digital symbol datastream representing data elements for providing output symbols representing significant and insignificant coefficients of a tree structure having a path from a coefficient generated at a level of coarse information to coefficients generated at levels of relatively finer information, said decoder apparatus comprising;

first means for evaluating said symbol datastream to determine if a symbol is a first symbol representing a significant coefficient, or a second symbol representing an insignificant coefficient;

second means for evaluating said second symbol to determine if said second symbol is a zerotree symbol representing a zerotree structure wherein a root coefficient and all descendant coefficients are insignificant and do not exhibit a magnitude greater than a given reference level, said zerotree structure having a path from an insignificant single root coefficient generated at a coarse level of information to insignificant descendant coefficients generated at levels of relatively finer information, where coarse information is image information in a low frequency subband derived from image information over a given spatial area, and finer information is image information in relatively higher frequency subbands derived from image information over a relatively smaller spatial area;

third means coupled to an output of said first means for generating a dominant list of entries corresponding to insignificant coefficients as a function of occurrences of said second symbol, and a subordinate list of entries corresponding to significant coefficients as a function of occurrences of said first symbol; and

means for processing each coefficient associated with respective entries of said dominant and subordinate lists at successively finer thresholds for progressively refining the contents of said dominant and subordinate lists.

5. Decoder apparatus for processing a coded digital symbol datastream representing digital data elements for providing output symbols representing significant and insignificant coefficients of a tree structure having paths from coefficients generated at a level of coarse information to coefficients generated at a level of relatively finer information, said digital data representing an image decomposed into plural image representative subbands at each of plural decomposition levels, with image representative subbands having associated coefficients each respectively representing multiple picture elements, said tree structure encompassing a related association of coefficients from plural decomposition levels;

said decoder apparatus comprising;

first means for evaluating said symbol datastream to determine if a symbol is a first symbol representing a significant coefficient, or a second symbol representing an insignificant coefficient;

second means for evaluating said second symbol to determine if said second symbol is a zerotree symbol representing a zerotree structure wherein a root coefficient and all descendant coefficients are insignificant and do not exhibit a magnitude greater than a given reference level, said zerotree structure having a path from an insignificant single root coefficient generated at a coarse level of information to insignificant descendant coefficients generated at levels of relatively finer information, where coarse information is image information in a low frequency subband derived from image information over a given spatial area, and finer information is image information in relatively higher frequency subbands derived from image information over a relatively smaller spatial area; and

third means responsive to an output of said first means for generating a dominant list of entries corresponding to insignificant coefficients as a function of occurrences of said second symbol, and a subordinate list of entries corresponding to significant coefficients as a function of occurrences of said first symbol;

wherein

said first evaluating means evaluates each coefficient associated with respective entries of said dominant and subordinate lists at successively finer thresholds for progressively refining the contents of said dominant and subordinate lists.