N-dimensional data compression using set partitioning in hierarchical trees

• US 20040170335A1
• Filed: 12/29/2003
• Published: 09/02/2004
• Est. Priority Date: 09/14/1995
• Status: Abandoned Application

• Current Assignee: Amir Said, William Abraham Pearlman
• Original Assignee: Amir Said, William Abraham Pearlman
• Inventors: Said, Amir, Pearlman, William Abraham
• Application Number:
  US10/747,877
• Publication Number:
  US 20040170335A1
• Time in Patent Office: Days
• US Class Current: 382/240
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree

Abstract

A data structure in a computer memory for use in encoding and decoding an N-dimensional subband decomposition of data points includes, after initialization, three lists: a list of insignificant sets of points (LIS); a list of significant points (LSP); and a list of insignificant points (LIP). The LIS is populated with sets, each of the sets being designated by a root node within the N-dimensional subband decomposition and having a corresponding tree structure of points within the N-dimensional subband decomposition, which tree structure of points is organized as descendants and offspring of the root node but not including the root node, the LIP is populated with points from within the highest designated subband of the N-dimensional subband decomposition, while the LSP is initially empty. The data structure permits encoding and decoding of any N-dimensional data set, i.e., any data set where N is a positive integer. Method and software for employing this data structure are also described.

Claims

1. A method for one of encoding and decoding a N-dimensional data set, comprising:

(a) subband decomposing the N-dimensional data set to thereby generate a N-dimensional subband decomposition;

(b) initializing a list of insignificant set of points (LIS), a list of significant points (LSP), and a list of individual insignificant points (LIP);

(c) populating the LIS with sets, each of the sets being designated by a root node within the N-dimensional subband decomposition and having a corresponding tree structure of points within the N-dimensional subband decomposition, which tree structure of points is organized as descendants and offspring of the root node but not including the root node;

(d) populating the LIP with points from within the highest designated subband of the N-dimensional subband decomposition;

(e) evaluating the descendants of the root node of each of the sets for significance;

(f) for each root node of a respective one of the sets having at least one significant descendant, evaluating descendants of the offspring of the root node for significance; and

(g) if the root node has at least one significant descendant of offspring, then adding additional sets corresponding to each of the offspring of the root node to the LIS as a root node thereof; and

(h) moving one of the points from the LIP to the LSP when a coefficient associated with a point is greater than or equal to the predetermined threshold;

wherein;

N is a positive integer;

the LSP initially comprises an empty set;

a first generation of the descendants comprise the offspring;

a significant descendent of the descendants of the root node has a coefficient greater than or equal to a predetermined threshold; and

a significant descendant of the offspring of the root node has a coefficient greater than or equal to the predetermined threshold.

2. The method as recited in claim 1, wherein the method comprises an encoding method, which further comprises the steps of:

outputting a sign representing a coefficient of the point;

outputting a significance value for each point within the LIP, the significance value indicating whether a coefficient of the point within the LIP is greater than or equal to the predetermined threshold.

3. The method as recited in claim 1, wherein the method comprises a decoding method, which further comprises the steps of:

receiving a sign representing a coefficient of the point;

receiving a significance value for each point within the LIP, the significance value indicating whether a coefficient of the point within the LIP is greater than or equal to the predetermined threshold.

4. The method as recited in claim 1, wherein the method comprises an encoding method, which further comprises the steps of:

for each root node of the LIS having at least one significant descendant, evaluating the offspring of the root node for significance; and

immediately outputting a significance value for each offspring of the root node, the significance value indicating whether the offspring is significant.

5. The method as recited in claim 4, further comprising the steps of:

for each significant offspring of the root node, adding the significant offspring to the LSP; and

outputting a sign of the coefficient of the significant offspring.

6. The encoding method as recited in claim 5, wherein:

an insignificant offspring of the root node has the coefficient less than the predetermined threshold, and

the method further comprises the step of, for each insignificant offspring of the root node, adding the insignificant offspring to the LIP.

7. The encoding method as recited in claim 1, wherein N=1, and the 1-dimensional data set corresponds to audio data.

8. The encoding method as recited in claim 1, wherein N=1, and the 1-dimensional data set corresponds to biological data signals.

9. The encoding method as recited in claim 1, wherein N=2, and the 2-dimensional data set corresponds to still image data.

10. The encoding method as recited in claim 1, wherein N=3, and the 3-dimensional data set corresponds to an image sequence.

11. The encoding method as recited in claim 10, wherein the image sequence comprises volume imagery.

12. A data structure in a computer memory for use in encoding and decoding an N-dimensional subband decomposition of data points, the data structure comprising a list (LIS) consisting of insignificant sets of points, a list (LSP) consisting of significant points and a list (LIP) consisting of insignificant points,

wherein:

N is a positive integer;

for each set of the LIS, the data structure includes a root node and a set type identifier, the set type identifier defining generations of descendants associated with the root node within the set of the LIS, wherein a first generation of descendants comprise offspring of the root node.

13. The data structure as recited in claim 12, wherein N=1, and the 1-dimensional data set corresponds to speech.

14. The data structure as recited in claim 12, wherein N=1, and the 1-dimensional data set corresponds to a biological data signal.

15. The data structure as recited in claim 12, wherein N=2, and the 2-dimensional data set corresponds to still image data.

16. The data structure as recited in claim 12, wherein N=3, and the 3-dimensional data set corresponds to an image sequence.

17. The data structure as recited in claim 16, wherein the image sequence comprises video.

18. A data structure in a computer memory for use in encoding and decoding an N-dimensional subband decomposition of data points, said data structure, after initialization, comprising at least three lists including a list of insignificant sets of points (LIS), a list of significant points (LSP), and a list of insignificant points (LIP);

wherein;

N is a positive integer;

the LIS is populated with sets, each of the sets being designated by a root node within the N dimensional subband decomposition and having a corresponding tree structure of points within the N-dimensional subband decomposition, which tree structure of points is organized as descendants and offspring of the root node but not including the root node;

the LIP is populated with points from within the highest designated subband of the N-dimensional subband decomposition; and

the LSP is initially empty.

19. The data structure as recited in claim 18, wherein N=1, and the 1-dimensional data set corresponds to biological signal data.

20. The data structure as recited in claim 18, wherein N=2, and the 2-dimensional data set corresponds to still image data.

21. The data structure as recited in claim 18, wherein N=3, and the 3-dimensional data set corresponds to an image sequence.

22. A record medium storing a computer program including computer readable program code therein for converting a general purpose computer to one of an encoded and decoder apparatus for respectively encoding and decoding an N-dimensional data set, the computer program comprising:

first computer readable program code for permitting the general purpose computer to subband decompose the N-dimensional data set to thereby generate an N-dimensional subband decomposition;

second computer readable program code for causing the general purpose computer to create a list (LIS) consisting of insignificant sets of points, each set of the LIS being designated by a root node within the N-dimensional subband decomposition and having a corresponding tree structure of points within the N-dimensional subband decomposition, the corresponding tree structure being organized as descendants and offspring of the root node and not including the root node, wherein a first generation of the descendants comprise the offspring;

third computer readable program code for causing the general purpose computer to evaluate the descendants of the root node of each set of the LIS for significance, wherein a significant descendent of the descendants of the root node has a coefficient greater than or equal to the predetermined threshold;

fourth computer readable program code for causing the general purpose computer to affect for each root node of the LIS having at least one significant descendant, evaluating descendants of the offspring of the root node for significance, wherein a significant descendant of the offspring of the root node has a coefficient greater than or equal to the predetermined threshold; and

fifth computer readable program code for causing the general purpose computer to affect adding additional sets corresponding to each of the offspring of the root node to the LIS as a root node thereof when the root node has at least one significant descendant of offspring,

wherein N is a positive integer.

23. The record medium as recited in claim 22, wherein N=1, and the 1-dimensional data set corresponds to audio data.

24. The record medium as recited in claim 22, wherein N=2, and the 2-dimensional data set corresponds to still image data.

25. The record medium as recited in claim 22, wherein N=3, and the 3-dimensional data set corresponds to an image sequence.

26. Software for encoding an N-dimensional data set, the software instantiating functions that permit a general purpose computer to:

generate a subband decomposition for the N-dimensional data set to thereby generate an N-dimensional subband decomposition;

generate at least three lists including a list of insignificant sets of points (LIS), a list of significant points (LSP), and a list of insignificant points (LIP), where the LIS is populated with sets, each of the sets being designated by a root node within the N-dimensional subband decomposition and having a corresponding tree structure of points within the N-dimensional subband decomposition, which tree structure of points is organized as descendants and offspring of the root node but not including the root node, the LIP is populated with points from within the highest designated subband of the N-dimensional subband decomposition, and the LSP is initially empty, and

output data corresponding to sorting of the LIS, the LSP, and the LIP in a predetermined sequence,

wherein N is a positive integer.

27. The software as recited in claim 26, wherein N=1, and the 1-dimensional data set corresponds to biological data.

28. The software as recited in claim 26, wherein N=2, and the 2-dimensional data set corresponds to still image data.

29. The software as recited in claim 26, wherein N=3, and the 3-dimensional data set corresponds to an image sequence.

30. The software as recited in claim 26, wherein the output data permits complete embeddedness to thereby permit progressive fidelity transmission of the indicia corresponding to the N-dimensional subband decomposition.

31. The software as recited in claim 26, wherein the output data permits precise rate control to thereby permit constant bit-rate (CBR) traffic.

32. The software as recited in claim 26, wherein the output data permits multiresolution scalability.

33. The software as recited in claim 26, wherein the output data includes at least quantization level data, and both data corresponding to points in the N-dimensional subband decomposition determined to be significant and a respective sign of the coefficient of the points.

34. A method for one of encoding and decoding a 3-dimensional data set composed of multiple color planes, comprising:

(a) subband decomposing the color planes to thereby generate a sequence of transformed color planes;

(b) initializing a list of insignificant set of points (LIS), a list of significant points (LSP), and a list of individual insignificant points (LIP);

(c) populating the LIS with sets, each of the sets being designated by a root node, corresponding to a coefficient in the lowest frequency subband of a selected one of the transformed color planes and having a corresponding tree structure of points within one of the same transformed color plane and branching to one or more coefficients in another one of the transformed color planes, which tree structure of points is organized as descendants and offspring of the root node but not including the root node;

(d) populating the LIP with points from within the lowest frequency subbands of the sequence of transformed color planes;

(e) evaluating the descendants of the root node of each of the sets for significance;

(f) for each root node of a respective one of the sets having at least one significant descendant, evaluating descendants of the offspring of the root node for significance; and

(g) if the root node has at least one significant descendant of offspring, then adding additional sets corresponding to each of the offspring of the root node to the LIS as a root node thereof; and

(h) moving one of the points from the LIP to the LSP whenever a coefficient associated with a point is greater than or equal to the predetermined threshold;

wherein;

the 3-dimensional data set comprises a color embedded bit-stream generated from an integer number of the color planes;

the LSP initially comprises an empty set;

a first generation of the descendants comprise the offspring;

a significant descendent of the descendants of the root node has a coefficient greater than or equal to a predetermined threshold; and

a significant descendant of the offspring of the root node has a coefficient greater than or equal to the predetermined threshold.

35. Software for encoding a 3-dimensional data set including an integer number of color planes, the software instantiating functions that permit a general purpose computer to:

generate a subband decomposition of the color planes from the 3-dimensional data set, wherein respective portions of the color planes are organized into an embedded color bit-stream, to thereby generate a 3-dimensional subband decomposition;

generate at least three lists including a list of insignificant sets of points (LIS), a list of significant points (LSP), and a list of insignificant points (LIP), where the LIS is populated with sets, each of the sets being designated by a root node within the sequence of transformed color planes and having a corresponding tree structure of points within the sequence of transformed color planes, to which tree structure of points is organized as descendants and offspring of the root node but not including the root node, the LIP is populated with points from within the highest-designated, lowest-frequency subbands of the sequence of the transformed color planes, and the LSP is initially empty; and

output data corresponding to sorting of the LIS, the LSP, and the LIP in a predetermined sequence.

36. The software as recited in claim 35, wherein the output data permits complete embeddedness to thereby permit progressive fidelity transmission of the indicia corresponding to the 3-dimensional subband decomposition.

37. The software as recited in claim 35, wherein the output data permits multiresolution scalability.

38. An encoding process for compressing a video sequence including successive frames organized into a groups of frames (GOF), each frame being decomposed by a 3-dimensional wavelet transform producing a predetermined number of successive resolution levels, the encoding process transforming an original set of picture elements (pixels) corresponding to the GOF into wavelet transform coefficients encoded with a binary format and constituting a hierarchical pyramid, the coefficients being organized into a spatio-temporal orientation tree rooted in the lowest frequency resulting from the 3-dimensional wavelet transform and completed by an offspring in the higher frequency subbands, the process comprising:

ordering the coefficients of the tree into partitioning sets involving the pixels and to corresponding to respective levels of significance in accordance with. magnitude testing permitting classification of the significance information in three ordered lists including a list of insignificant sets (LIS), a list of insignificant pixels (LIP) and a list of significant pixels (LSP), the tests being carried out in order to divide the original set of pixels into the partitioning sets according to a division process that continues until each significant coefficient is encoded within the binary representation, and the spatio-temporal orientation tree defining the spatio-temporal relationship inside the hierarchical pyramid; and

outputting the binary representation corresponding to the ordered coefficients.

39. Software for encoding a 3-dimensional data set corresponding to an image sequence, the software instantiating functions that permit a general purpose computer to:

generate a subband decomposition for the 3-dimensional data set to thereby generate an 3dimensional subband decomposition;

divide the 3-dimensional subband decomposition into S subband decomposition groups based on at least one of their respective spatial and temporal relationships;

for each of the S subband decomposition groups,

generate at least three lists including a list of insignificant sets of points (LIS), a list of significant points (LSP), and a list of insignificant points (LIP), where the LIS is populated with sets, each of the sets being designated by a root node within the S^th subband decomposition group and having a corresponding tree structure of points within the S^th subband decomposition group, which tree structure of points is organized as descendants and offspring of the root node but not including the root node, the LIP is populated with points from within the highest designated subband of the S^th subband decomposition group, and the LSP is initially empty,

and then

output data corresponding to sorting of the LIS, the LSP, and the LIP in a predetermined sequence for the S^th subband decomposition group; and

output interleaved data based on the S predetermined sequences of the output data, wherein S is a positive integer.