System and method for segmentation dependent lossy and lossless compression for higher quality

• US 6,198,850 B1
• Filed: 06/12/1998
• Issued: 03/06/2001
• Est. Priority Date: 06/12/1998
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Banton, Martin E.
• Primary Examiner(s): Lee, Thomas D.
• Assistant Examiner(s): Chen, Wenpeng
• Application Number:
  US09/096,190
• Time in Patent Office: 998 Days
• Field of Search: 382/232, 382/239, 382/244, 382/248, 382/234, 382/180, 382/176, 382/173, 358/430, 358/450, 358/462, 358/453, 358/467, 395/114, 395/112
• US Class Current: 382/239
• CPC Class Codes: H04N 1/41 Bandwidth or redundancy reduction by scanning H04N1/17 ; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: H04N 1/411 for the transmission or storage or reproduction of two-tone pictures, e.g. black and white pictures
• CPC Class Codes: H04N 19/12 Selection from among a plurality of transforms or standards, e.g. selection between discrete cosine transform [DCT] and sub-band transform or selection between H.263 and H.264
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock

Abstract

A method and system takes advantage of both lossy and lossless compression techniques to increase processing speed and efficiency, and to decrease required image storage space. In the system and method, the input image data is divided into pixel blocks. Segmentation tags are used to determine if 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, then lossy compression is performed on the pixel block. An artificial block is generated and losslessly compressed. The artificial block includes pixels having values that will be losslessly compressed by a large compression 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 in the selected or predetermined areas of the pixel block, then that block is sent to a buffer to be losslessly compressed. An artificial block is generated and lossy compressed. The artificial block includes pixels having values that will be lossy compressed by a large compression ratio.

Claims

1. An image data processing system, comprising:

a segmenter that receives image data and segments the image data into lossy and lossless data;

a first storage device that temporarily stores the segmented lossless data;

an artificial lossless data generator that generates artificial lossless data based on a value stored in the first storage device;

an artificial lossy data generator that generates artificial lossy data based on a value stored in a second storage device;

a lossless compressor that compresses the lossless data stored in the first storage device and the artificial lossless data generated by the artificial data generator;

a lossy compressor that compresses the lossy data segmented by the segmenter and the artificial lossy data generated by the artificial lossy data generator; and

a third storage device that stores the compressed lossy and lossless data,

wherein the artificial lossless data generator generates artificial lossless data based on a value of a last pixel in each scanline in a previously compressed lossless data block.

2. The image data processing system of claim 1, wherein the artificial lossy data generator generates artificial lossy data based on an average value of pixels in a previously compressed lossy data block.

3. The image data processing system of claim 1, wherein the segmenter segments Z×

Z blocks of image data, where Z is an integer greater than 1.

4. The image data processing system of claim 1, wherein the lossy and lossless data is stored in third storage device such that each block of compressed lossy data has a corresponding artificial block of compressed lossless data, and each block of compressed lossless data has a corresponding artificial block of compressed lossy data.

5. The image data processing system of claim 4, wherein the segmenter generates a segmentation tag to identify actual compressed data blocks from artificial compressed data blocks.

6. An image data processing system, comprising:

a memory that stores lossy compressed image data and losslessly compressed image data, the lossy compressed image data including artificial and actual lossy data and the losslessly compressed image data including artificial and actual losslessly data;

a lossy decompressor that decompresses the lossy compressed image data stored in the memory;

a lossless decompressor that decompresses the lossless compressed image data stored in the memory; and

a selector that selects the actual lossy and lossless data to be output from the artificial lossy and lossless data;

wherein the selector selects the actual lossy and lossless data to be output based on a difference in at least one value between decompressed blocks of lossy compressed image data.

7. The image data processing system of claim 6, wherein the lossy and lossless compressed image data is stored in the memory such that each block of actual lossy data has a corresponding block of artificial lossless data, and each block of actual lossless data has a corresponding artificial block of artificial lossy data.

8. The image data processing system of claim 7, wherein the selector uses segmentation tags to identify actual compressed data blocks from artificial compressed data blocks.

9. A method for processing image data, comprising:

segmenting the image data into lossy and lossless data;

temporarily storing the segmented lossless data in a first storage device;

generating artificial lossless data based on a value stored in the first storage device;

generating artificial lossy data based on a value stored in a second storage device;

compressing the lossless data stored in the first storage device and the artificial lossless data generated in the generating step;

compressing the lossy data segmented in the segmenting step and the artificial lossy data generated in the generating step; and

storing the compressed lossy and lossless data in a third storage device;

wherein the generating step generates artificial lossless data based on a value of a last pixel in each scanline in a previously compressed lossless data block.

10. The method for processing image data of claim 9, wherein the generating step generates artificial lossy data based on an average value of pixels in a previously compressed lossy data block.

11. The method for processing image data of claim 9, wherein the segmenting step segments Z×

Z blocks of image data, where Z is an integer greater than 1.

12. The method for processing image data of claim 9, wherein the storing step stores lossy and lossless data such that each block of compressed lossy data has a corresponding artificial block of compressed lossless data, and each block of compressed lossless data has a corresponding artificial block of compressed lossy data.

13. The method for processing image data of claim 12, wherein the segmenting step uses segmentation tags to identify actual compressed data blocks from artificial compressed data blocks.

14. A method for processing image data, comprising:

decompressing compressed lossy image data;

decompressing compressed lossless image data; and

selecting the actual lossy and lossless data to be output from artificial lossy and lossless data;

wherein the selecting step selects the actual lossy and lossless data to be output based on a difference in at least one value between decompressed blocks of lossy compressed image data.

15. The method for processing image data of claim 14, wherein the selecting step selects the actual data to be output based on segmentation tags to used to identify actual compressed data blocks from artificial compressed data blocks.

16. A method for processing image data, comprising:

segmenting the image data into lossy and lossless data;

temporarily storing the segmented lossless data in a first storage device;

generating artificial lossless data based on a value stored in the first storage device;

generating artificial lossy data based on a value stored in a second storage device;

compressing the lossless data stored in the first storage device and the artificial lossless data generated in the generating step;

compressing the lossy data segmented in the segmenting step and the artificial lossy data generated in the generating step; and

storing the compressed lossy and lossless data in a third storage device;

decompressing the compressed lossy data;

decompressing the compressed lossless data; and

selecting the actual lossy and lossless data to be output from the artificial lossy and lossless data;

wherein the selecting step selects the actual lossy and lossless data to be output based on a difference in at least one value between decompressed blocks of lossy compressed image data.

17. An image data processing system, comprising:

a segmenter that receives image data and segments the image data into lossy and lossless data;

a first storage device that temporarily stores the segmented lossless data;

an artificial lossless data generator that generates artificial lossless data based on a value stored in the first storage device;

an artificial lossy data generator that generates artificial lossy data based on a value stored in a second storage device;

a lossless compressor that compresses the lossless data stored in the first storage device and the artificial lossless data generated by the artificial data generator;

a lossy compressor that compresses the lossy data segmented by the segmenter and the artificial lossy data generated by the artificial lossy data generator; and

a third storage device that stores the compressed lossy and lossless data,

wherein the artificial lossy data generator generates artificial lossy data based on an average value of pixels in a previously compressed lossy data block.

18. The image data processing system of claim 17, wherein the segmenter segments Z×

Z blocks of image data, where Z is an integer greater than 1.

19. The image data processing system of claim 17, wherein the lossy and lossless data is stored in third storage device such that each block of compressed lossy data has a corresponding artificial block of compressed lossless data, and each block of compressed lossless data has a corresponding artificial block of compressed lossy data.

20. The image data processing system of claim 19, wherein the segmenter generates a segmentation tag to identify actual compressed data blocks from artificial compressed data blocks.

21. A method for processing image data, comprising:

segmenting the image data into lossy and lossless data;

temporarily storing the segmented lossless data in a first storage device;

generating artificial lossless data based on a value stored in the first storage device;

generating artificial lossy data based on a value stored in a second storage device;

compressing the lossless data stored in the first storage device and the artificial lossless data generated in the generating step;

compressing the lossy data segmented in the segmenting step and the artificial lossy data generated in the generating step; and

storing the compressed lossy and lossless data in a third storage device,

wherein the generating step generates artificial lossy data based on an average value of pixels in a previously compressed lossy data block.

22. The method for processing image data of claim 21, wherein the segmenting step segments Z×

Z blocks of image data, where Z is an integer greater than 1.

23. The method for processing image data of claim 21, wherein the storing step stores lossy and lossless data such that each block of compressed lossy data has a corresponding artificial block of compressed lossless data, and each block of compressed lossless data has a corresponding artificial block of compressed lossy data.

24. The method for processing image data of claim 23, wherein the segmenting step uses segmentation tags to identify actual compressed data blocks from artificial compressed data blocks.