Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1998-06-29
2002-10-22
Lee, Young (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
Reexamination Certificate
active
06470052
ABSTRACT:
BACKGROUND OF THE INVENTION
A method of combining the HVQ compression and decompression of image pixels with ninety degree rotation so that both can be accomplished in less time, and using less hardware, than if both operations were done separately.
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. 1a 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 256K by 64 bit LUT which outputs the bit pattern of the entire 8-pixel block.
In the field of image rotation it is frequently necessary that an image scanned into the system in one orientation, such as protrait, must be printed in another orientation, such as landscape. Therefore, there is a need for ninety degree rotation hardware or software. One solution to this problem is to design a memory that can be loaded or read from vertically or horizontally. Then, to rotate the pixels in a block, the block is loaded into the memory one column at a time, and read out one row at a time. Of course, this requires additional circuitry or software, as well as additional operating time.
SUMMARY OF THE INVENTION
In a system which requires data compression as well as image rotation, the HVQ compression hardware can be modified to also produce image rotation at little added cost and operating time. To explain this by using a numerical example, assume an input set of eight pixels that is four high and two wide. This can be compressed into a single output code word. However, in the decoder, when this is applied to the look-up table, it would be just as simple to have there produced eight pixels that are arranged as two high by four wide to produce an image that is the rotated image of the input.
REFERENCES:
patent: 4797945 (1989-01-01), Suzuki et al.
patent: 5452104 (1995-09-01), Lee
patent: 5751865 (1998-05-01), Micco et al.
patent: 6078696 (2000-06-01), Nguyen et al.
patent: 6154572 (2000-11-01), Chaddha
patent: 0 701 375 (1996-03-01), None
Brian C. Smith and Lawrence A. Rowe, Compressed Domain Processing of JPEG-encoded images, 1996, pp. 1-17.
Claproth Abraham E.
Hackett Arnold
Nguyen Kien T.
Nguyen Uoc H.
Lee Young
Xerox Corporation
LandOfFree
HVQ compression combined with orthogonal rotation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with HVQ compression combined with orthogonal rotation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and HVQ compression combined with orthogonal rotation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2961998