Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
1998-07-17
2001-05-22
Boudreau, Leo H. (Department: 2721)
Image analysis
Image compression or coding
Transform coding
C382S240000, C375S240180, C358S438000
Reexamination Certificate
active
06236762
ABSTRACT:
The present invention relates generally to systems and methods for lossless compression and reconstruction of data, such as the quantized coefficients of a DCT or wavelet transformed image, that is sparsely populated by non-zero data, and particularly to a system and method for efficiently identifying and encoding portions of a DCT or wavelet transformed data set occupied by zero and near-zero values.
BACKGROUND OF THE INVENTION
Sparsely populated data sets are utilized in numerous technical fields. The present invention was developed for efficiently encoding image data that has been transformed by successive applications of wavelet transforms or discrete cosine transforms (DCT), but is equally applicable to other types of sparsely populated data sets. Image data that has been transformed by successive applications of these transforms tends to have large portions occupied by zero and near-zero values, especially if the data is subjected to a data quantization step prior to encoding. Prior art encoding techniques include methods that require all the transform coefficients for an image to be processed together. These techniques require large amounts of memory and are therefore ill-suited for smaller electronic image equipment such as digital cameras.
The primary goals of the present invention are to provide an encoding methodology that (A) encodes wavelet and DCT data with as few data bits as possible, (B) determines the maximum number of data bits required to encode sub-arrays that include at least some non-zero data, and (C) encodes non-zero data with the minimum number of data bits required to losslessly store such data.
Other goals of the present invention are to provide an encoding methodology that uses memory very efficiently, and one that is suitable for implementation in a range of different hardware (i.e., electronic circuitry).
SUMMARY OF THE INVENTION
In summary, the present invention is 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 (e.g., 32×32), 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. A block family is then selected and divided into an upper leftmost block and a sub-family. The difference between the maximum number of bits required to represent any coefficient in the family and the maximum number for the sub-family is determined and encoded. The sub-family is then successively divided into an upper leftmost block and a sub-family. In each iteration, the difference between the maximum number of bits required to represent any coefficient in the parent sub-family and the maximum number for the child sub-family is determined and encoded. For each sub-family where the parent sub-family maximum number equals the child sub-family maximum number, the difference between the parent sub-family maximum number and the maximum number for the upper leftmost block in the parent sub-family is 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. Each data entry in the block is compared with the maximum number of bits required to represent a coefficient in the block. If the data entry equals the maximum number the corresponding bit mask entry is set to one, otherwise it is set to zero. The difference between each data entry and the maximum number for the block is also encoded. After all the coefficients in a block have been processed, the bit mask is encoded. When blocks of a predetermined size (e.g., 1×1) are encountered, the method outputs the value of the coefficients in the block.
The data decoding method retraces the encoded data so as to reverse the process performed by the encoding method. The bits of the encoded data are read, in order, in a single pass from the first bit to the last. After the last data bit in the encoded data has been processed, if the data was mapped in the encoding process, then the data entries are mapped back to reconstruct the encoded data array. As the encoded data is read, entries are added to a block list to identify data blocks that will be processed later, along with the data indicating the maximum number of bits needed to encode the data in those data blocks. Data blocks are analyzed in the order they appear in the encoded data. Whenever a data block is processed, if the data block is entirely filled with zero data, the relevant portion of the reconstructed data array is filled with zero data values. Otherwise, data block identifiers are added to the block list until data blocks of a predetermined minimum size (e.g., 1×1) are encountered, at which point the data values in each such data block are decoded and output to the reconstructed data array. The encoder and decoder can be implemented in either hardwired logic or computer software.
REFERENCES:
patent: 5412741 (1995-05-01), Shapiro
patent: 5682152 (1997-10-01), Wang et al.
patent: 5740277 (1998-04-01), Katto
patent: 5748116 (1998-05-01), Chui et al.
patent: 5748786 (1998-05-01), Zandi et al.
patent: 5764807 (1998-06-01), Pearlman et al.
patent: 5886651 (1999-03-01), Chui et al.
patent: 5887084 (1999-03-01), Wober et al.
patent: 6101279 (2000-08-01), Nguyen et al.
Chui Charles K.
Spring James M.
Yi Rongxiang
Zhong Lefan
Boudreau Leo H.
Pennie & Edmonds LLP
PicSurf, Inc.
Sherali Ishrat
LandOfFree
System and method for unified DCT and wavelet data coding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for unified DCT and wavelet data coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for unified DCT and wavelet data coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2539822