Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
2002-04-15
2003-03-04
Lee, Young (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
Reexamination Certificate
active
06529553
ABSTRACT:
BACKGROUND OF THE INVENTION
A process for determining whether a block of pixels to be compressed is either of two types of image data, or contains a boundary between the types, so that the lossy compressor used to compress the block will be optimized for the first or second type of data, or for a transition between the two.
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 a printing system which uses HVQ, the data is supplied to the lossy compressor in blocks of pixels, each block being text, contone, halftone, etc. So that the compressor may configure itself optimally for the kind of data being received, the front end may supply to the compressor a mask which determines the boundaries between different kinds of data, and printing hints which specify which configuration should be used for the data that falls within each mask. In this system the mask edges must be aligned with the block edges.
The system can be improved by a system for determining if there is a boundary within a block, which can be referred to as a transition block. For example, if a boundary between a text character and a contone picture runs through a block, then a printing hint will be sent to the compressor, and table values optimized for transition blocks can be selected for that block. This would improve system performance by allowing the compressor to operate with less loss.
REFERENCES:
patent: 4553172 (1985-11-01), Yamada et al.
patent: 4679094 (1987-07-01), Rutherford et al.
patent: 4745473 (1988-05-01), Hall
patent: 4797945 (1989-01-01), Suzuki et al.
patent: 5140417 (1992-08-01), Tanaka et al.
patent: 5253058 (1993-10-01), Gharavi et al.
patent: 5272529 (1993-12-01), Frederiksen
patent: 5339164 (1994-08-01), Lim
patent: 5410350 (1995-04-01), Kato et al.
patent: 5452104 (1995-09-01), Lee
patent: 5517327 (1996-05-01), Nakatani et al.
patent: 5541594 (1996-07-01), Huang et al.
patent: 5602589 (1997-02-01), Vishwanath et al.
patent: 5689588 (1997-11-01), Rombola et al.
patent: 5751865 (1998-05-01), Micco et al.
patent: 5757852 (1998-05-01), Jericevic et al.
patent: 5764802 (1998-06-01), Simon
patent: 5767978 (1998-06-01), Revankar et al.
patent: 5831678 (1998-11-01), Proctor
patent: 5870502 (1999-02-01), Bonneau et al.
patent: 5999710 (1999-12-01), Smith et al.
patent: 6078696 (2000-06-01), Nguyen et al.
patent: 6154572 (2000-11-01), Chaddha
patent: 6205252 (2001-03-01), Nguyen et al.
patent: 0 358 815 (1990-03-01), None
patent: 06 141187 (1994-05-01), None
patent: 0 605 893 (1994-07-01), None
patent: 0 701 375 (1996-03-01), None
patent: 0 856 988 (1998-08-01), None
patent: WO 91 01609 (1991-02-01), None
Lo, S-C B., Li, Huai, Krasner, B. H., Freedman, M. T., Mun, S. K., A Contour Coding And Full-Frame Compression Of Discrete Wavelet And Cosine Transforms Oct. 1995, p. 9-12, vol. 2 Image Processing, 1995. Proceedings., International Conference on.
Minami, S., “CCITT H.261 Compatible Mixed Bit Rate Coding of Video for ATM Networks” Jun. 1992, p. 537-543, Communications, 1992. ICC '92, IEEE International Conference.
Smith, B C, Rowe, L.A., “Compressed Domain Processing of JPEG-Encoded Images” Real-Time Imaging, GB, Academic Press, Limited, vol. 21, No. 1, Feb. 1, 1996, pp. 3-17.
Claproth Abraham E.
Lin Weili
Nguyen Kien T.
Nguyen Uoc H.
Lee Young
Xerox Corporation
LandOfFree
HVQ compression for image boundaries 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 for image boundaries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and HVQ compression for image boundaries will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3020072