Image analysis – Image compression or coding – Parallel coding architecture
Reexamination Certificate
1998-06-29
2001-03-20
Au, Amelia M. (Department: 2723)
Image analysis
Image compression or coding
Parallel coding architecture
C382S240000, C382S253000
Reexamination Certificate
active
06205252
ABSTRACT:
A method of optimizing the compression ratio of a compression apparatus or method by splitting the data words into two segments of most and least significant bits, and applying different compression methods to each segment.
When data must be transmitted or stored it is usually compressed first, to reduce the transmission time or storage requirement. This is especially true of image data which can consist of four color separations of 8-bit pixels.
One method of compression is “hierarchical vector quantization” (HVQ), where a block of data can be reduced to a single codeword in a number of steps. This method is described in U.S. Pat. No. 5,602,589, and is incorporated by reference herein. This procedure can be explained most clearly by the use of a numerical example in connection with
FIG. 1
a
of that patent. Assume that a 2 by 4 pixel block, 8 bits per pixel, is to be compressed to one 9-bit number. First, each pair of pixels is applied to a stage 1 look up table (LUT) containing 9-bit code words, each code word being associated with a two-pixel bit pattern. The table is set up so that if an exact match of the input pixel bits is not available, then a codeword associated with the closest match is output instead. The ultimate output of this stage 1 is four codewords, each describing the closest match to the bit pattern of the two input pixels. Since the exact match frequently is not possible, this compression is inherently lossy to some extent. The output of the first stage is four 9-bit codewords.
Assuming this amount of compression is not sufficient, these four codewords, each representing the bit pattern of a 1 by 2 pixel block are next applied to two stage 2 tables, resulting in a total of two 9-bit output codewords, each representing the bit pattern of a 2 by 2 pixel block. If the compression is still insufficient, these two are applied to the stage 3 table to yield the final output word, which is associated with a 2 by 4 pixel block. It can now be seen that this method is hierarchical in that a plurality of stages are used, it involves vectors since the input pixels have a directional relationship with each other, and is quantized in that a number of levels can be implemented to achieve any degree of compression.
For decompression, each codeword is simply applied to a 256 K by 64 bit LUT which outputs the bit pattern of the entire 8-pixel block.
SUMMARY OF THE INVENTION
In the prior art, it is understood that if two different kinds of data are to be compressed, it is most efficient to separate the data, text and contone, for example, and apply a different compression algorithm to each, to optimize the process. Here, the procedure is to separate each data word into its most and least significant parts, and apply a different compression procedure to each part. If an HVQ process is being used for both parts, the compression ratio for each part can be different to optimize the entire process.
With specific reference to HVQ compressors being used to compress 8-bit image pixels, the improvement of the basic HVQ circuit would be to divide each 8-bit pixel into three most significant bits (MSB's) and five least significant bits (LSB's), for example. Each channel is compressed by an HVQ compressor, and the final output of the decompressors are summed in an adder, mux, etc, to recombine them. The advantage of this procedure is that a different amount of compression can be applied to each portion. The three MSB's for example, contain the most crucial data, and so a less lossy compression of, for example, 4 to 1, can be applied while, for the LSB's, a greater loss can be absorbed so a compression of 16 to 1 can be used. The result is either less loss or greater compression, compared to the original system. This procedure improves the system performance of a compressor using HVQ, but can be used on systems using other compression algorithms as well.
REFERENCES:
patent: 4745473 (1988-05-01), Hall
patent: 5140417 (1992-08-01), Tanaka et al.
patent: 5253058 (1993-10-01), Gharavi
patent: 5339164 (1994-08-01), Lim
patent: 5689588 (1997-11-01), Rombola et al.
patent: 5764802 (1998-06-01), Simon
Minami, CCITT H.261 Compatible Mixed Bit Rate Coding of Video for ATM Networks, 6/1992. p. 537-543, Communications, 1992, ICC '92, IEEE International Conference.*
Lo et al., A contour coding and full-frame compression of discrete wavelet and cosine transforms, 10/1995, p. 9-12, vol. 2. Image Processing, 1995. Proceedings., International Conference on.
Claproth Abraham E.
Kang Sang-Chul
Lee Chia-hao
Nguyen Kien T.
Nguyen Uoc H.
Au Amelia M.
Cunha Robert
Johnson Timothy M.
Xerox Corporation
LandOfFree
Two channel HVQ (hierarchical vector quantization) compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Two channel HVQ (hierarchical vector quantization) compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two channel HVQ (hierarchical vector quantization) compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2504723