Coded data generation or conversion – Digital code to digital code converters
Reexamination Certificate
2001-12-06
2003-12-16
JeanGlaude, Jean Bruner (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
C341S051000, C382S239000
Reexamination Certificate
active
06664902
ABSTRACT:
This patent specification contains material that is subject to copyright protection. The copyright owner has no objection to the reproduction of this patent specification or related materials from associated patent office files for the purposes of review, but otherwise reserves all copyright whatsoever.
1. Field of the Invention
The present invention relates to digital image compression and in particular to image compression in raster image processing systems where memory resources are limited.
2. Background
Image compression is widely used in color raster image processing systems such as those found in printers. Image compression is used in these systems to reduce the amount of memory required to store raster images in the stages between pixel generation and the time when the final output has been delivered from the printer. Reducing the amount of memory reduces the total system cost.
In color printing environments the total uncompressed size of a generated pixel images is often large and it is advantageous to avoid storing the entire image. Such pixel images are typically generated in raster or band order. In particular, pixels, scanlines, groups of scanlines, or tiles, are emitted in a stream from a raster image processor (RIP) that has as input an object graphic description of the page to be printed. In some simple cases this raster image data stream may be fed directly to a print engine. But in many circumstances this is not possible. This may be because the print engine requires real-time data delivery, because the image must be kept in case error recovery is required, or because the image must be kept for printing later in a duplexing system. Many other reasons exist. In systems where the raster image data must be kept, it is often fed to a compressor in a pipeline fashion such that intermediate storage between the RIP and the compressor is small compared with the total uncompressed image size. The output of the compressor is also considerably smaller than the uncompressed image size.
Many compression schemes can be used in this environment. One widely used method for color images is the baseline method of the Joint Photographic Experts Group (JPEG) standard. However compression using baseline JPEG standard and other methods suffers a number of serious flaws that make their use difficult in systems with limited memory resources. Existing compression schemes all exhibit one or more of the following flaws when presented with streamed input data:
The memory available to receive the compression data can be over-run. Compression schemes are typically highly data-dependent and without knowing details of the input data ahead of time it is not possible to predict what size output buffer will be required to accept the compressed data. This is a serious problem for systems with limited memory resources. Allocating a large output buffer is typically wasteful, and often still not a guarantee that the compressed data will fit. Some schemes exist that limit total compressed size by maintaining a sufficiently high compression factor on local regions of the image, but in these schemes it is not possible to trade off one part of the image that compresses well against another that does not.
For lossy compression schemes (such as baseline JPEG) the degree of loss must be selected ahead of time. Control of the degree of perceptual degradation (in short, loss) is a common method of controlling the output compression size. But this must generally be selected consistently across a whole image to achieve consistent visual quality, and must be selected at the start of the compression operation.
The image may become unnecessarily compressed. Where a high-loss setting is used for a compression operation, it may transpire that the image data compressed well and a less-lossy setting could have been used in comparison with the system's available memory. A less-lossy setting would have resulted in higher final image quality which is advantageous.
The compression scheme may require random access to, or multiple passes over, the uncompressed image data. Some compression schemes exist that overcome one or more of the earlier problems by using either random access to the uncompressed image data or by performing multiple passes over it. But this is disadvantageous because it requires storage either of the uncompressed image data or of the original data that is used to generate the image data.
U.S. Pat. No. 5,761,345 publishes an image processing apparatus initially storing variable length codes corresponding to a significant frequency component, and variable length codes corresponding to a less significant frequency component. If while storing the variable length codes into the storage means, it is detected that the storage means is full (with variable length codes), the control means makes room for the storage of further variable length codes corresponding to the more significant frequency component by cancelling variable length codes stored in the storage means, which correspond to the less significant frequency component. However, the image processing apparatus suffers from the disadvantage in that it makes inefficient use of the storage means and the decompressed image may have relatively low image quality.
U.S. Pat. No. 5,748,786 publishes a method for one-pass compression into a fixed size buffer. The methods use a reversible DWT with embedded coding. The method suffers from the disadvantage in that it requires significant amount of input image line buffering, and a high cost to implement the suggested entropy coder with current technology, particularly when many such parallel encoders/decoders ate required in a real time application.
U.S. Pat. No. 5,815,097 publishes a method for a one-pass spatially embedded coder. The method, avoiding so called costly transform domain techniques (such as JPEG/DCT methods), supports fixed rate and fixed size applications for one-pass encoding and decoding. That is the image is compressed into a fixed size buffer, in one-pass, with a relatively small working line buffer, without the need to buffer the entire input image. However, by avoiding so called costly transform domain techniques, the method suffers from the disadvantage in that it either makes inefficient use of the storage means and the decompressed image may have relative low image quality, or requires the use of sophisticated and costly arithmetic coders, whose cost is high in current technology, particularly when many such parallel encoders/decoders are required in a real time application.
These problems may also occur in many other related raster image processing systems such as digital cameras and scanners.
SUMMARY OF THE INVENTION
It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements.
According to one aspect of the invention, there is provided a method of storing coded image data of an image in a storage of fixed memory size, wherein the image comprises a plurality of pixels and the method comprises the steps of arranging the image into a plurality of bands each comprising a predetermined number N of consecutive lines of pixels; buffering and processing said bands one by one in turn, wherein the processing step comprises the following sub-steps for each currently buffered said band: arranging the current band into a plurality of blocks of pixels of size M×M, wherein M is equal to said predetermined number N; transforming said blocks of pixels to produce respective blocks of transform coefficients; partitioning the blocks of transform coefficients into a plurality of partitions wherein each partition comprises data from each said block of transform coefficients and at least one partition comprises data from at least one but not all bit-planes of each said block of transform coefficients, and wherein the plurality of partitions comprise a perceptually significant partition and a perceptually insignificant partition and partitions of varying perceptually significance there between; coding each said partit
Andrew James Philip
Bell Peter Leslie
Clark James David
Long Timothy Merrick
Moore Kevin John
LandOfFree
Storing coding image data in storage of fixed memory size does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Storing coding image data in storage of fixed memory size, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Storing coding image data in storage of fixed memory size will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3172151