Teralogic, Inc.

Picsurf, Inc.

Rongxiang Yi

Charles K Chui

Lefan Zhong

James M Spring

A unified system and method for encoding an array of data. If the data array is comprised of DCT data, then coefficients from corresponding positions in the data array are mapped into a common blocks in a second data array so as to group similarly valued coefficients. If the data array is comprised of wavelet data and the wavelet tile is greater than a predetermined size, then the wavelet tile coefficients are mapped into a second array so as to combine coefficients from the same wavelet family. After the DCT or wavelet coefficients have been mapped, the DC coefficients are encoded using a differential pulse code modulation (DPCM) process. The maximum number of bits required to represent any coefficient in each block family in the data array is determined. The difference between the maximum number of bits required to represent any coefficient in the entire data array and each of the block family maximums is determined and encoded. Each block family is then successively divided into an upper leftmost block and a sub-family, and difference values between maximum numbers of component block groupings are determined and encoded. This process is then repeated until the selected sub-family comprises a single block. Whenever a sub-family is processed, if the sub-family is entirely filled with zero data it is so identified in the output data and no further processing of the sub-family is required. After all of the sub-families have been processed, the blocks are bit mask coded. After all the coefficients in a block have been processed, the bit mask is encoded. When blocks of a predetermined size are encountered, the method outputs the value of the coefficients in the block. A data decoder and method retraces the encoded data so as to reverse the process performed by the encoding method.

System and method for unified DCT and wavelet data coding

A data encoder and method utilizes a node list for storing a list of nodes in the data array to be processed, a branch list for storing a list of tree branches in the data array to be processed and a set list for storing a list of data sets. The method begins by initially storing in the node list node identifiers representing a predefined set of nodes in the data array, corresponding to coefficients generated by a last iteration of a data decomposition procedure. Also, it initially stores in the branch list branch identifiers representing tree branches corresponding to a predefined subset of the nodes initially listed in the node list. Each such tree branch has an associated root node and a branch depth value indicating how many node layers intervene between the root node and the nodes of the tree branch closest to the root node. The set list is initially empty, and a parameter called the LayerLimit value is also initialized. For successively smaller values of m, where m is a positive integer, a set of data encoding steps are repeatedly performed so as to process all nodes, branches and sets in the lists. A magnitude flag is output for each node, branch and set to indicate whether or not it is or contains a node whose absolute value is equal to or larger than 2.sup.m-1, and for each node, branch and set that is equal to or larger than 2.sup.m-1 further processing is performed.

System and method for tree ordered coding of sparse data sets

A data encoding system and method successively generates compressed data on a bit plane by bit plane basis, starting with the bit position of the most significant non-zero bit for the node in the data array having the largest absolute value, and then encoding the data in the array for progressively less significant bits. All the nodes in the data array are represented initially by blocks of nodes on a block list, and later in the processing by nodes on two node lists. Whenever a block contains a node whose most significant bit is on the bit plane currently being processed, the block will be subdivided recursively until all the nodes in the block whose most significant bit in on the current bit plane are placed in a node list. Data bits representing an m.sup.th least significant bit of the block and node values are written to the compressed data file first, where m is the minimum number of bits required to represent the node having the largest absolute value in the entire data array being encoded. Data bits for successively less significant bit planes are written to the compressed data file until a bit plane stop point is reached. The bit plane stop point may be predefined, user selected, or procedurally selected (e.g., in accordance with available bandwidth for transmitting compressed image data).

System and method for scalable coding of sparse data sets

A data encoder and method successively analyzes successively smaller blocks of a specified data array. Data blocks are analyzed in a predefined order, and corresponding entries identifying data blocks containing at least one non-zero value are stored in that same order in a list of blocks. Whenever a data block is processed, if the data block is entirely filled with zero data it is so identified in the output data and no further processing of the subblock is required. Otherwise, if the size of the data block is greater than a predefined minimum block size (e.g., 2.times.2), the block is divided into smaller data blocks and those smaller data blocks are put on the list of blocks for further processing. Finally, if the size of a data block that is being processed is the predefined minimum block size, values representing all the data items in that data block are written into the output data. Information identifying the number of bits required to encode the maximum data value in each data block is written into the output data in the same order that the blocks are analyzed, thereby enabling a decoder procedure to determine the number of data bits used to encode each data value stored in the output data. A data decoder and method retraces the encoded data so as to reverse the process performed by the encoding method. The encoder and decoder can be implemented in either hardwired logic or computer software.

Growing community of inventors

Sunnyvale, CA, United States of America

Rongxiang Yi