Image analysis – Image compression or coding
Reexamination Certificate
1998-12-18
2001-08-07
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Reexamination Certificate
active
06272252
ABSTRACT:
BACKGROUND OF THE INVENTION
A circuit for compressing and decompressing image data in real time prior to printing, and more specifically, forming the image into 8 by 8 pixel blocks prior to transmission from the image generator to the printer so that the compression ratio can be improved by deleting un-needed blocks prior to transmission.
Image generators can produce pages having a variety of image material such as text, computer generated graphics and pictorial data in the form of multi-bit pixels. If this material is to be stored or transmitted, it should be compressed first to reduce system requirements. Normally, the material is separated into its component parts, so that each type of data is compressed by an algorithm that is most efficient for it.
Possible compression algorithms are of two varieties, lossless and lossy. Image data such as computer generated graphics and text are easily compressed using some kind of run length encoding, and can be efficiently compressed without the loss of data. On the other hand, pictorial data does not compress well and it is therefore difficult to know beforehand exactly what the compression ratio will be.
However, to support a high speed printer, a minimum compression ratio must be guaranteed. That is, the transmission rate, the page per minute rate of the printer, and the compression ratio of the data are related. For example, at a known print rate and data transmission rate, a minimum rate of compression will be required so that the printer will never exceed the rate at which data is delivered to it. Thus, a minimum guaranteed compression is required. As stated, pictorial data is the problem, and to increase the compressability of this data, greater rates of compression have been achieved by using an algorithm that allows some loss of data. One common lossy compression algorithm is the industry standard JPEG compression algorithm. This algorithm takes advantage of both vertical and horizontal patterns of data in 8 by 8 pixel blocks to produce its compression.
Normally, data is sent between systems on a scan line basis, while this algorithm compresses data by blocks. To reconcile these two requirements, data is normally sent to the compresser one scan line at a time, the compresser waits until it has received a band of 8 scan lines, divides the band into blocks, compresses the blocks one at a time, reassembles the compressed data block into scan lines, and transmits the compressed data one scan line at a time.
Similarly, the receiver accumulates scan lines until it has a band of blocks, decompresses them one at a time, and assembles 8 decompressed scan lines, which can be sent to a final destination such as a printer.
Frequently, text or graphics are printed over JPEG compressed pictures. These are compressed and decompressed one scan line at a time and can be assembled with the associated decompressed picture scan lines. The resultant overall compression ratio is satisfactory for many purposes, but a further improvement would be desirable.
SUMMARY OF THE INVENTION
In the system described above, some of the compressed data is eventually not used to create a printed page output. For example, between lines and in the spaces between letters of text that is being printed over a background picture, the text data will not be used. Similarly, picture data that lies entirely within a character mask will not be used. Thus the compression could be further increased if this data was not compressed and transmitted.
This is accomplished by separating the text as well as the picture data into 8 by 8 pixel blocks prior to compression. Then, each block is inspected to determine if a boundary between text and picture data occurs within the current block. If there is a boundary, then both types of data are needed, and both are compressed. However, if there is no boundary, then only one type of data is required, and the other type need not be compressed and transmitted. In this way, the compression can be improved.
REFERENCES:
patent: 4827349 (1989-05-01), Ogata et al.
patent: 5432620 (1995-07-01), Watanabe et al.
patent: 5473444 (1995-12-01), Sakano et al.
patent: 5629737 (1997-05-01), Menez et al.
patent: 5680477 (1997-10-01), Asada
patent: 5689346 (1997-11-01), Noda et al.
patent: 5745178 (1998-04-01), Hartung et al.
patent: 5764803 (1998-06-01), Jacquin et al.
patent: 5768403 (1998-06-01), Suzuki et al.
patent: 5768441 (1998-06-01), Yoshizawa et al.
patent: 5875262 (1999-02-01), Asada
Blurfrushan Farzin
Cheung Li-Fung
Eldridge George L.
Henning Tom
Phong San A.
Couso Jose L.
Xerox Corporation
LandOfFree
Segmenting image data into blocks and deleting some prior to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Segmenting image data into blocks and deleting some prior to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Segmenting image data into blocks and deleting some prior to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2455897