Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
1999-09-16
2003-08-12
Johnson, Timothy M. (Department: 2625)
Image analysis
Image compression or coding
Adaptive coding
C382S228000, C382S251000
Reexamination Certificate
active
06606415
ABSTRACT:
TECHNICAL FIELD OF INVENTION
This invention relates in general to the field of Raster Image Processing, and more specifically to a feedback approach that automatically controls the image compression ratios required to minimize the memory requirements for Raster Image Processors employed in generating a bitmap representation of a composite page.
BACKGROUND OF 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. Before display or printing, the vector-based representation of the page is converted to a bitmap representation at the desired resolution by a process called Rasterisation.
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″ 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.
If the available frame buffer memory is less than this limit, an alternate strategy must be followed. The page is divided into smaller portions or bands, with the band size being determined by the available frame buffer memory. Each band is then rendered to bitmap form and passed on to the exposure, printing or display module to make space for the subsequent bands.
Since 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, such real-time rendering may not be possible for some complex bands. 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.
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.
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, and some pages will compress much more than others. Since the amount of memory and the page size are fixed, a method must be found to guarantee that all pages can be rendered and printed in real time.
SUMMARY OF THE INVENTION
This invention shows a feedback algorithm designed to select and enforce a target compression ratio that will guarantee that the system will be capable of rendering any input page, irrespective of the complexity, within the available memory limitations.
The feedback methods shown apply to a block-based, hybrid compression method. The image to be rendered is first segmented into non-overlapping blocks of pixels. Each block is then classified as Solids, Text (saturated or unsaturated), or image areas. The compression method applied to each block is then selected based on the class of the block, according to the following criteria:
Differential Pulse Code Modulation (DPCM) is used to code solids
Block Truncation Coding (BTC) is used for text
Image blocks may be coded using DPCM, DCT (Discrete Cosine
Transform), BTC or a combination of these methods. The image blocks may also be decimated previous to coding.
Runs of repeating solids are compressed using run length coding.
The highest compression ratio is achieved using DPCM on blocks classified as solids. Accordingly, adjusting the threshold used in classifying the blocks as solids will modulate the effective compression ratio, and by increasing the number of solids the compression ratio is also increased.
If the target compression ratio is not met by using the feedback mechanism, a fall back strategy may be employed. In this case, the entire band must be decimated by 2:1, followed by BTC. Since decimated bands do not visibly stand out from other bands that have not been decimated, this decision may be made on a band by band basis.
The feedback compression approach shown can be very efficiently implemented on a parallel processor such as the Texas Instruments TMS320C80 family.
REFERENCES:
patent: 5379355 (1995-01-01), Allen
patent: 5414527 (1995-05-01), Koshi et al.
patent: 6330363 (2001-12-01), Accad
Brady III W. James
Johnson Timothy M.
Marshall, Jr. Robert D.
Telecky , Jr. Frederick J.
Texas Instruments Incorporated
LandOfFree
Feedback control for hybrid compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Feedback control for hybrid compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Feedback control for hybrid compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3095581