Data compression using set partitioning in hierarchical trees

• US 5,764,807 A
• Filed: 09/14/1995
• Issued: 06/09/1998
• Est. Priority Date: 09/14/1995
• Status: Expired due to Term

• Current Assignee: Primacomp, Inc.
• Original Assignee: Primacomp, Inc.
• Inventors: Pearlman, William Abraham, Said, Amir
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Johnson, Timothy M.
• Application Number:
  US08/527,863
• Time in Patent Office: 999 Days
• Field of Search: 382/240, 348/397, 348/398, 348/408, 348/437, 348/438, 341/79
• US Class Current: 382/240
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree

Abstract

A data compression technique includes a subband decomposition of a source image followed by coding of the coefficients of the resultant subband decomposition for storage and/or transmission. During coding, three ordered lists are used comprising a list of significant pixels (LSP), a list of insignificant pixels (LIP) and a list of insignificant sets of pixels (LIS). The pixels in the LIP are tested, and those that are significant at a current quantization level are moved to the LSP. Similarly, sets are sequentially evaluated following the LIS order, and when a set is found to be significant it is removed from the LIS and partitioned into new subsets. The new subsets with more than one element are added back to the end of the LIS, while the single-coordinate sets are added to the end of the LIP or to the end of the LSP, depending whether they are insignificant or significant, respectively.

Claims

1. A method for use in encoding and decoding a subband decomposition of a data set, said method comprising the steps of:

(a) creating a list (LIS) consisting of insignificant sets of points, each set of said LIS being designated by a root node within said subband decomposition and having a corresponding tree structure of points within said subband decomposition, said corresponding tree structure of points being organized only as descendants and offspring of said root node and not including the root node, wherein a first generation of said descendants comprise said offspring;

(b) evaluating said descendants of said root node of each set of said LIS for significance, wherein a significant descendent of said descendants of said root node has a coefficient at least equal to a predetermined threshold;

(c) for each root node of said LIS having at least one significant descendant, evaluating descendants of said offspring of said root node for significance, wherein a significant descendant of said offspring of said root node has a coefficient at least equal to said predetermined threshold; and

(d) if said root node has at least one significant descendant of offspring, then adding additional sets corresponding to each of said offspring of said root node to said LIS as a root node thereof.

2. The method of claim 1, wherein prior to said step (b), said method includes creating a list of significant points (LSP), said LSP initially comprising an empty set, and creating and keeping a list (LIP) consisting of individual insignificant points, said LIP initially comprising points from within a highest designated subband of said subband decomposition.

3. The method of claim 2, wherein prior to said step (b), said method includes one of outputting and inputting a significance value for each point within said LIP, said significance value indicating whether a coefficient of said point within said LIP is at least equal to said predetermined threshold.

4. The method of claim 3, wherein for each point in the LIP, after said one of outputting and inputting the significance value for the point within the LIP, if the coefficient of the point is at least equal to said predetermined threshold, moving the point from the LIP to the LSP and one of outputting and inputting a sign of the coefficient of the point.

5. The method of claim 2, wherein prior to said step (c) for each root node of said LIS having at least one significant descendant, evaluating said offspring of said root node for significance, wherein a significant offspring has a coefficient at least equal to said predetermined threshold, and one of immediately outputting and inputting a significance value for each offspring of said root node, said significance value indicating whether said offspring is significant.

6. The method of claim 5, further comprising, for each significant offspring of said root node, adding said significant offspring to said LSP and one of outputting and inputting a sign of the coefficient of said significant offspring.

7. The method of claim 5, wherein an insignificant offspring of said root node has said coefficient less than said predetermined threshold, and wherein said method further comprises, for each insignificant offspring of said root node, adding said insignificant offspring to said LIP.

8. The method of claim 1, wherein each set of said LIS has a set type identifier comprising one of a type A and a type B, said type A designating said set as all descendants of the root node of said set, said type B designating said set as all of the descendants of the root node of said set excluding the offspring of said root node, and wherein said step (a) includes designating each set of said LIS as said type A.

9. The method of claim 8, wherein said step (d) comprises, if said root node has at least one significant descendant of offspring, adding each offspring of said root node to said LIS as a root node thereof, said offspring having said type A set type identifier corresponding thereto within said LIS.

10. The method of claim 9, wherein said step (d) further comprises, if said root node has at least one significant descendant of offspring, removing said root node from said LIS.

11. The method of claim 8, wherein said step (c) comprises, for each root node of said LIS having at least one significant descendant of offspring, changing said set type identifier of the set comprising said root node to said type B.

12. The method of claim 11, wherein said step (d) comprises, for each set within said LIS comprising said type B, outputting a significance indicator corresponding to said set, said significance indicator indicating whether a coefficient of any point within said set is at least equal to said predetermined threshold.

13. A computer program comprising a computer useable medium having computer readable program code therein for use in encoding and decoding a subband decomposition of a data set, said computer readable program code in said computer program comprising:

first computer readable program code for causing a computer to affect creating a list (LIS) consisting of insignificant sets of points, each set of said LIS being designate by a root node within said subband decomposition and having a corresponding tree structure of points within said subband decomposition, said corresponding tree structure being organized only as descendants and offspring of said root node and not including said root node, wherein a first generally of said descendants comprise said offspring;

second computer readable program code for causing a computer to affect evaluating said descendants of said root node of each set of said LIS for significance, wherein a significant descendent of said descendants of said root node has a coefficient at least equal to said predetermined threshold;

third computer readable program code for causing a computer to affect for each root node of said LIS having at least one significant descendant, evaluating descendants of said offspring of said root node for significance, wherein a significant descendant of said offspring of said root node has a coefficient at least equal to said predetermined threshold; and

fourth computer readable program code for causing a computer to affect adding additional sets corresponding to each of said offspring of said root node to said LIS as a root node thereof when said root node has at least one significant descendant of offspring.