Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
1998-12-03
2001-08-28
Chang, Jon (Department: 2623)
Image analysis
Image compression or coding
Transform coding
C382S251000, C375S240240
Reexamination Certificate
active
06282322
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to systems and methods for increasing compression of data streams containing image data, and in particular to systems and methods that increase compression by predicting values for certain low frequency coefficients of pixel block transforms.
2. Description of the Related Art
Many important image compression methods process images as independent blocks of pixels. For example, such families of compression standards as JPEG, MPEG, H.320, and so forth, specify a step involving discrete cosine transformation (“DCT”) of independent, non-overlapping 8×8 blocks of pixels in the source image followed by quantization of the resulting transform coefficients. See, e.g., Jack, 1996,
Video Demystified,
HighText Interactive Inc., San Diego, Calif. The quantized transform coefficients are transmitted from a transmitter-encoder to a receiver-decoder.
Such transformation and quantization together achieve compression by exploiting the significant regularities and correlations that typically occur between the values of pixels in 8×8 blocks. However, such methods ignore any regularities and correlations that may occur between pixels in different pixel blocks which are treated as independent by these methods.
Certain work has been reported which attempts to recognize image regularities at scales of a pixel block or larger. Exemplary of these are Pennebaker et al., 1993,
JPEG Still Image Compression,
Van Nostrand Reinhard, chap. 16, which discloses fitting quadratic surfaces to the average values of pixels (equivalent to the “DC”, or lowest order, transform coefficient) in adjacent blocks, a computationally complex process; Lakhani, 1996, “Improved Image Reproduction from DC Components”, Opt. Eng. 35:3449-2452, which discloses equations for predicting low frequency transform coefficients from DC coefficients that are improved from those in the JPEG standard; and Jeon et al., 1995, Blocking Artifacts Reduction in Image Coding Based on Minimum Block Boundary Discontinuity, Proc SPIE 2501:189-209, which discloses a complex and computationally expensive iterative method for interpolating pixels in order to zero block boundary discontinuities.
This reported work suffers from one or more problems, such as not being directed to maximally improving image compression, ignoring or at best inadequately treating regularities that may exist at scales in an image greater than a pixel block, requiring excessive computational resources, and so forth. What is needed, therefore, is a computationally efficient method and system directed primarily to achieving increased data compression by exploiting additional regularities and correlations in images not exploited by known compression methods and standards.
Citation of a reference herein, or throughout this specification, is not to construed as an admission that such reference is prior art to the Applicant's invention of the invention subsequently claimed.
SUMMARY OF THE INVENTION
The objects of the present invention are to provide improvements generally applicable to certain types of encoders and decoders for image-containing data of all types which overcome the above identified problems in the current art.
Encoder/decoder pairs to which the present invention is applicable are those that, during image compression transform the image from the spatial domain, where the image is represented as a spatial array of pixels, to a transform domain, where the image is represented as coefficients of the basis functions used in the transform method, followed by quantization of the resulting transform coefficients. During decompression, the decoder reverses these steps. In particular, relevant encoder/decoder pairs divide the spatial domain image into a plurality of non-overlapping sub-blocks of pixels and perform the transformation/inverse transformation independently on each sub-block in the image.
In the relevant types of encoder/decoder pairs, the improvement of the present invention includes, in the encoder, an additional step which predicts certain low-order, or the low-frequency (“LF”), transform coefficients. The predicted LF coefficients are then subtracted from the actual LF transform coefficients to form LF difference coefficients, which are quantized and transmitted to the decoder. In the decoder, these steps are reversed, namely, the LF coefficients are again predicted, and the predicted coefficients are added to the transmitted quantized LF difference coefficients to arrive at the original LF coefficients, up to quantization errors.
The LF coefficient prediction according to the present invention is based on the fact that image-data compression, in addition to that already realized by sub-block transformation and quantization, can be achieved by capturing regularities and correlations between pixel values present in adjacent sub-blocks (“inter-block regularities”). These inter-block regularities can be advantageously exploited by predicting LF transform coefficients to be those that are necessary to smooth differences between adjacent sub-blocks so that the image is smooth at sub-block boundaries. In a preferred embodiment, the differences between adjacent sub-blocks are represented by differences in the average intensities of the adjacent sub-blocks.
In detail, these objects are achieved by the following embodiments of the present invention. In a first embodiment, the present invention includes a method for compressing an image presented as image data in the form of a pixel array comprising: transforming a plurality of pixel blocks to transform coefficients in a frequency domain, wherein the pixel blocks are rectangular, non-overlapping, and the plurality of pixel blocks covers the pixel array, and wherein the transform coefficients represent each pixel block and include a zero frequency transform coefficient, one or more selected low frequency transform coefficients, and remaining transform coefficients, predicting for each pixel block the selected low frequency transform coefficients from a linear combination of the zero frequency transform coefficient of the pixel block and of the zero frequency transform coefficients of pixel blocks orthogonally adjacent to the pixel block, subtracting for each pixel block the predicted selected low frequency transform coefficients from the selected low frequency transform coefficients to form difference transform coefficients, quantizing for each pixel block the difference coefficients and the remaining transform coefficients, and representing the image by compressed image data comprising the zero frequency transform coefficient, the quantized difference coefficients, and the quantized remaining coefficients for each of the plurality of pixel blocks.
In a first aspect of the first embodiment, the step of predicting for each pixel block further comprises: determining an interpolating pixel array having interpolating pixel values linearly interpolating differences between the zero frequency transform coefficient of the pixel block and the zero frequency transform coefficients of pixel blocks orthogonally adjacent to the pixel block, transforming the interpolating pixel array to transform coefficients in the frequency domain, and selecting the predicted selected low frequency transform coefficients as the corresponding transform coefficients of the interpolating pixel array.
In a second aspect of the first embodiment, the step of selecting selects the predicted selected low frequency transform coefficients as those transform coefficients present in an upper left square sub-array of size three-by-three of the transformed interpolating pixel array, excluding the zero frequency transform coefficient of the transformed interpolating pixel array. In a third aspect of the first embodiment, the pixel values of the interpolating pixel array are weighted sums of differences between the zero frequency transform coefficient of the pixel block and the zero frequency transform coefficient of each pixel block orthogonally adjacent to the p
Chang Jon
Gross Russell
Philips Electronics North America Corp.
Wu Jingge
LandOfFree
System and method for compressing and decompressing 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 System and method for compressing and decompressing images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for compressing and decompressing images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2446831