Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
2000-04-11
2003-02-18
Wu, Jingge (Department: 2623)
Image analysis
Image compression or coding
Lossless compression
C382S233000
Reexamination Certificate
active
06522784
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to image processing, and specifically to methods of image compression.
BACKGROUND OF THE INVENTION
Various methods of image compression are known in the art. These methods can be categorized generally as lossy and lossless. When lossless compression is used, the original image can be reproduced exactly upon decompression. In general, however, lossy methods achieve higher compression ratios, i.e., smaller compressed image files for a given original image.
One of the most popular methods for lossless compression of gray-scale and color images is the Lempel-Ziv-Welch (LZW) algorithm. This algorithm is described in U.S. Pat. Nos. 4,558,302 and 5,642,112, whose disclosures are incorporated herein by reference. LZW compression uses a dictionary for storing strings of data characters encountered in the input to the algorithm. The input stream, typically a sequence of pixel values in an image, is searched by comparing segments of the input stream to the strings stored in the dictionary in order to find the longest matching string. The dictionary is then augmented by storing an extended string, comprising the longest matching string with the addition of the next input data character following the longest matching segment in the input stream. This procedure continues until the entire image has been compressed.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide improved methods, apparatus and products for image compression.
It is a further object of some aspects of the present invention to provide a method for improving the compression ratio that can be achieved using existing compression algorithms.
In preferred embodiments of the present invention, the pixels in an input image are reordered prior to compression, so as to generate a reordered image having a reduced overall variance. “Overall variance” in this context means a sum or mean of the absolute differences between neighboring pixels in the image. Compression algorithms known in the art, such as the above-mentioned LZW algorithm, typically achieve substantially higher compression ratios when the overall variance is low. Therefore, when the reordered image is compressed, the output image file is substantially smaller than would be achieved without reordering, even taking into account the additional data needed to restore the pixels to their original order following decompression.
In some preferred embodiments of the present invention, the pixel values in the input image are quantized to a selected number of levels. The original pixel values in the image are then reordered so as to group them by their respective quantized values, while keeping the pixels within each group in the order in which they appeared in the input image. The quantized image and the reordered image are both compressed, using any suitable compression algorithm or algorithms known in the art. Preferably, lossless algorithms are used. Most preferably, different algorithms are applied to the quantized image and to the reordered image, chosen so as to maximize the compression ratio in each case. To reconstruct the image, the quantized and reordered images are decompressed. Each pixel in the quantized image is then replaced by its value taken from the reordered image, and the input image is thus reconstructed.
There is therefore provided, in accordance with a preferred embodiment of the present invention, a method for compression of an input image that includes a plurality of pixels having respective input pixel values, including:
quantizing the input pixel values so as to generate respective quantized pixel values;
generating a quantized image by substituting the quantized pixel values for the respective input pixel values in the input image;
reordering the input pixel values in the input image so as to generate a reordered image in which the input pixel values are grouped by their respective quantized values; and
compressing the quantized image and the reordered image so as to generate a compressed output image file.
Preferably, quantizing the input pixel values includes dividing the input pixel values into a selected number of ranges, and assigning the pixels whose values are in each of the ranges to a corresponding one of the quantized values.
In a preferred embodiment, quantizing the input pixel values includes quantizing the input pixel values into first and second numbers of quantization levels, and
generating the quantized image and reordering the input pixels values include generating a respective quantized image and reordered image for each of the first and second numbers of quantization levels, and
compressing the quantized image and the reordered image includes selecting one of the first and second numbers for use in generating the compressed output image file dependent upon which of the first and second numbers gives the smallest output image file.
Preferably, reordering the input pixel values includes copying the input pixel values to the reordered image sequentially according to an order in which the pixels appear in the input image. Most preferably, copying the input pixel values to the reordered image includes copying the input pixel values in raster order. Further preferably, the quantized pixel values include at least first and second quantized values, and copying the input pixel values to the reordered image includes copying the values such that in the reordered image, the pixels belonging to the first quantized value appear in the raster order of the input image, followed in the raster order by the pixels belonging to the second quantized value.
Preferably, compressing the quantized and reordered images includes applying a lossless compression algorithm to at least one of the images, such as a Lempel-Ziv-Welch algorithm.
In preferred embodiments, the method includes storing the output image file in a memory or, alternatively or additionally, transmitting the output image file over a communication link.
There is also provided, in accordance with a preferred embodiment of the present invention, a method for compression of an input image that includes a plurality of pixels having respective input pixel values, including:
reordering the pixels in the input image so as to generate a reordered image having a reduced overall variance relative to the input image; and
compressing the reordered image so as to generate a compressed output image file.
There is further provided, in accordance with a preferred embodiment of the present invention, a method for decompressing a compressed image file that includes a compressed quantized image and a compressed reordered image, wherein the quantized image was generated by substituting quantized pixel values for input pixel values of a plurality of pixels in an input image, and wherein the reordered image was generated by grouping the input pixel values by their respective quantized values, the method including:
decompressing the quantized image and the reordered image; and
replacing the quantized value of each of the pixels in the decompressed quantized image with a corresponding one of the input pixel values taken from the decompressed reordered image so as to reconstruct the input image.
Preferably, the quantized values include at least first and second quantized values, and replacing the quantized value of each of the pixels includes:
scanning the decompressed quantized image to find the pixels having the first quantized value;
replacing each of the pixels having the first quantized value in sequence with a successive one of the input pixels values taken from the decompressed reordered image;
scanning the decompressed quantized image to find the pixels having the second quantized value; and
replacing each of the pixels having the second quantized value in sequence with a successive one of the input pixels values taken from the decompressed reordered image.
There is moreover provided, in accordance with a preferred embodiment of the present invention, apparatus for compression of an input image that includes a plurality of p
LandOfFree
Enhanced compression of gray-level images does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Enhanced compression of gray-level images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enhanced compression of gray-level images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3149755