Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
1999-09-10
2003-03-04
Johnson, Timothy M. (Department: 2623)
Image analysis
Image compression or coding
Adaptive coding
C382S233000, C358S462000
Reexamination Certificate
active
06529633
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 lossless compression and an efficient method of real time decompression of the compressed image.
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 ratio available, but are computationally too intensive to be used on the whole page.
SUMMARY OF THE INVENTION
The invention described herein presents a block-based hybrid compression method. The image to be compressed is first segmented into equal size, non-overlapping blocks of pixels. Each block is then classified as either SOLID, TEXT, SATURATED TEXT or IMAGE. This classification may be done by a number of methods. One of these methods is by determination of the Block Truncation Coding parameters of the block, and using these parameters for classification. Another, much simpler method is shown in this invention that does not require computing the BTC parameters.
After classification, the blocks may be compressed using a variety of algorithms such as Block Truncation Coding, Run Length Coding, Differential Pulse Code Modulation, or Discrete Cosine Transform. The method of compression is chosen depending on the classification of the block, as different classes lend themselves to more or less compression efficiency with the different algorithms.
Since the decompression of the image must take place in real time, the computationally simplest algorithm should be selected. A new compression/decompression algorithm is shown in this invention that significantly speeds up the decoding process of IMAGE blocks compressed using Differential Pulse Code Modulation by compressing the data in away that will allow the decompressor to decode a multiplicity of pixels at one time. Tuning parameters are available that will allow additional reduction of the decoding time at the expense of reduced compression ratios. This algorithm is particularly well suited to efficiently execute on a highly parallel Digital Signal Processor (DSP) such as the Texas Instruments TMS320C8X family of DSP's by fully utilizing the inherent parallelism of the processor.
REFERENCES:
patent: 4196448 (1980-04-01), Whitehouse et al.
patent: 4547811 (1985-10-01), Ochi et al.
patent: 4668995 (1987-05-01), Chen et al.
patent: 5345317 (1994-09-01), Katsuno et al.
patent: 5708919 (1998-01-01), Yamada et al.
patent: 6285458 (2001-09-01), Yada
patent: 6285796 (2001-09-01), Acharya et al.
Delph, 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).
Easwar Venkat V.
Payne Ralph E.
Brady III W. James
Johnson Timothy M.
Marshall, Jr. Robert D.
Telecky , Jr. Frederick J.
Texas Instruments Incorporated
LandOfFree
Parallel difference coding method for lossless 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 Parallel difference coding method for lossless compression..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel difference coding method for lossless compression... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3044063