N-dimensional data compression using set partitioning in hierarchical trees

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;
• the LIP is populated with points from within the highest designated subband of the N-dimensional subband decomposition;
• and
• the LSP is initially empty.

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.

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.

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.

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.

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, 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.

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 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,
• wherein:
• the LIP is populated with points from within the highest designated subband of the N-dimensional subband decomposition;
• and
• the LSP is initially empty.

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 3-dimensional 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 Sth subband decomposition group and having a corresponding tree structure of points within the Sth 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 Sth 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 Sth subband decomposition group;
• and
• output interleaved data based on the S predetermined sequences of the output data, wherein S is a positive integer.