Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
1999-09-10
2003-05-20
Johnson, Timothy M. (Department: 2625)
Image analysis
Image compression or coding
Adaptive coding
C382S228000, C382S245000, C358S001150
Reexamination Certificate
active
06567559
ABSTRACT:
TECHNICAL FIELD OF INVENTION
This invention relates in general to the field of image compression and decompression, and more particularly to a method of compressing an image to a specified compression ratio where the image consists of text, graphics and image objects and then decompressing the image in real time.
BACKGROUND OF THE INVENTION
When printing a document, the page to be printed is typically composed electronically using software like QuarkXpress, Framemaker, etc. Internally the page is stored in a vector based graphical representation by these composition tools. This representation is then usually converted to another representation called a Page Description Language (PDL). Some composition tools generate the PDL directly. To print the page, the PDL representation is sent to the printer directly, or through a network. Before display or printing, a Raster Image Processor (RIP) must convert the PDL representation of the page to a raster (bitmap) representation at the desired resolution.
This conversion process can usually be divided into two stages: interpretation and rendering. Interpretation is the process where the original page description is reduced to a series of drawing primitives called the display list. Rendering is the process where these drawing primitives are converted to a bitmap in the frame buffer.
At high resolutions, a significant amount of memory is required to store this bitmap image. As an example, an 8.5″×11″ (i.e. A4 size) page at a resolution of 600 Dots per Inch (dpi), 8 bits/pixel and 4 color planes will require 128 MB of frame buffer memory.
In order to reduce the memory requirement, the page may be divided into smaller portions or bands, with the band size being determined by the available frame buffer memory. Each band is then converted to bitmap form and passed on to the exposure module of the printer to make space for the subsequent bands.
Since in a typical non-impact printer the exposure module has to be fed with bitmap data at regular intervals, each band must be rendered in a predefined time. As rendering is computationally intensive and is influenced by the page content, such real-time rendering may not be possible for complex bands. In some cases real-time rendering may not be possible even though the bands are not complex. If the available memory is limited, there may not be sufficient room to store the original display list and other information required for rendering the page. If this is the case, each band must be pre-rendered, compressed and stored. After all the bands have been processed and compressed, they are decompressed in real time and fed to the exposure module.
There are various methods that may be employed to compress the rendered image. To maintain maximum image quality, a lossless or low loss method is preferred. Unfortunately, the amount of compression attainable with most of these methods is highly dependent on the page content—some pages will compress much more than others. Since the amount of memory and the page size are fixed, a method must be found that guarantees that all pages can be rendered and printed in real time. In addition, the requirement that the page be decompressed in real time also restricts the compression method selected to one of relatively low complexity. As an example, Direct Cosine Transform (DCT) based methods are very efficient in terms of compression available, but are computationally too intensive to be used on the whole page.
SUMMARY OF THE INVENTION
The invention described here presents a block-based hybrid compression method. The image to be compressed is first segmented into p×q non-overlapping blocks of pixels. Each block is then analyzed by preparing the block for Block Truncation Coding (BTC). First the mean and the alpha (first absolute central moment) is computed, the block is then BTC coded, and the error between the original and coded block is calculated. Based on these parameters the block is classified, and the best compression method is selected on a block by block basis. The salient steps of this process are as follows:
Compute BTC parameters for the block
Classify block as SOLID, TEXT, SATURATED TEXT or Image using the BTC parameters
Differential Pulse Code Modulation (DPCM) is used to compress SOLID blocks
Consecutive SOLID blocks (Runs) are compressed using Run Length Coding
Block Truncation Coding (BTC) is used for TEXT.
Decimation is performed on IMAGE blocks, followed by BTC. Alternatively, DPCM or Discrete Cosine Transform (DCT) based compression methods may be used.
Compression ratio control is achieved by the selection of the appropriate compression method for each block. Additional control parameters are available, such as the use of lossy or lossless DPCM compression, the selection of the Quantizer Step Size when lossy DPCM compression is selected, and the use of the Discrete Cosine Transform (DCT) algorithm on selected image blocks.
The Hybrid Compression Method described in the invention can be very efficiently implemented on a parallel processing Digital Signal Processor such as the Texas Instruments TMS320C80 family.
REFERENCES:
patent: 5592569 (1997-01-01), Li
patent: 5659362 (1997-08-01), Kovac et al.
patent: 5940132 (1999-08-01), Kondo et al.
patent: 6151409 (2000-11-01), Chen et al.
patent: 6285458 (2001-09-01), Yada
Delp, E.J., et al.,Image Compression Using Block Truncation Coding,IEEE Transactions on Communications, COM-27 (9), pp. 1335-1342, (1979).
Lema, M.D., et al.,Absolute Moment Block Truncation Coding and Its Application to Color Images,IEEE Transactions on Communications, COM-32 (10), pp. 1148-1157, (1984).
Brady III W. James
Johnson Timothy M.
Marshall, Jr. Robert D.
Telecky , Jr. Frederick J.
Texas Instruments Incorporated
LandOfFree
Hybrid image compression with compression ratio control does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hybrid image compression with compression ratio control, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid image compression with compression ratio control will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3065981