Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
1998-06-12
2001-03-06
Lee, Thomas D. (Department: 2724)
Image analysis
Image compression or coding
Adaptive coding
C382S234000, C382S173000, C358S438000
Reexamination Certificate
active
06198850
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
This invention relates to image segmentation and compression. In particular, the invention is directed to using segmentation information to enable compression and decompression of image data by both lossless and lossy techniques.
2. Description of Related Art
JPEG (Joint Photographic Experts Group) is recognized as a good technique for compressing contones and filtered high frequency halftones. This lossy compression technique is especially effective in compressing color images. Compressing images in a luminance/chrominance space and using the fact that the human visual system does not need the same resolution for color information as it does for intensity results in high compression ratios.
However, lossy techniques are not well suited for compressing and decompressing text images. The linear transforms used in lossy techniques have difficulty compressing sharp edges. Consequently, these edges tend to blur and soften through multiple compression and decompression operations.
Lossless compression techniques, such as Lempel Ziv (LZ), are better suited for compressing text and low frequency halftone images. These lossless compression techniques provide high compression ratios and compression processing speeds, and are also advantageous for image data that contains significant amounts of repeated data. However, lossless compression techniques are not as efficient when compressing a high frequency halftone, contone or background image where high resolution is not required.
SUMMARY OF THE INVENTION
This invention provides a method and system to take advantage of both lossy and lossless compression techniques in order to increase processing speed and efficiency, and to decrease required image storage space.
In the system and method according to this invention, the input image data is divided into pixel blocks. Segmentation tags are used to determine if a pixel block contains sharply defined images, such as text or low frequency halftone. If the answer is “no,” i.e., a selected or predetermined number of the pixels are not classified as text or low frequency halftone, or the pixels classified as text or low frequency halftone occur only in selected or predetermined areas of the block, e.g., an isolated pixel is determined to be text but all of the other pixels in the block are determined as contone, then lossy compression is performed on the pixel block. An artificial pixel block is generated and put into a buffer to be losslessly compressed. The artificial block includes pixels of constant value. This creates areas in the file to be losslessly compressed that will compress by a large ratio.
If the answer is “yes,” i.e., there are at least the selected or predetermined number of pixels in the pixel block that should be processed as text or low frequency halftone, and/or the pixels classified as text or low frequency halftone do not occur only in selected or predetermined areas of the pixel block, then that block is sent to a buffer to be losslessly compressed. An artificial pixel block is generated that includes pixels of the same value. The artificial block is put into a buffer to be compressed using a lossy technique. This creates areas in the file to be compressed with lossy techniques that will compress by a large ratio.
In one preferred embodiment, JPEG is used as the lossy compression technique, while Lempel Ziv (LZ) is used as the lossless compression technique. In JPEG, 8 pixel×8 pixel blocks of the image are compressed. In the method and system of this invention, if the current block is compressed using the lossy JPEG technique, a single block of 8 pixels in 8 scanlines are compressed. In contrast, if the current block is compressed using the lossless LZ technique, each of the 8 scanlines are compressed separately in the compressed block.
Thus, when the current block is JPEG compressed, in the artificial block to be LZ compressed, the value stored for each line is chosen to match the value of the last pixel in that corresponding scanline in the preceding losslessly compressed 8×8 block. In contrast, when the current block is LZ compressed, in the artificial block to be JPEG compressed, the value is chosen to be the average of the 64 pixels in the last block that was JPEG compressed. Because JPEG decodes the direct current (DC) value of a block as a difference from the previous JPEG-compressed block's DC value and because with all pixels in the 8×8 block having the same value there will be no frequency components beyond the DC component, this procedure will create areas in the buffer file to be JPEG compressed that will compress by a large ratio.
These and other features and advantages of this invention are described in or are apparent from the following detailed description of the preferred embodiment.
REFERENCES:
patent: 5414527 (1995-05-01), Koshi et al.
patent: 5455680 (1995-10-01), Shin
patent: 5552898 (1996-09-01), Deschuytere
patent: 5586200 (1996-12-01), Devaney et al.
patent: 5619594 (1997-04-01), Melen
patent: 5659635 (1997-08-01), Komatsu et al.
patent: 5982937 (1999-11-01), Accad
patent: 5999710 (1999-12-01), Smith et al.
Chen Wenpeng
Lee Thomas D.
Oliff & Berridg,e PLC
Xerox Corporation
LandOfFree
System and method for segmentation dependent lossy and... 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 segmentation dependent lossy and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for segmentation dependent lossy and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2472461