Progressive JPEG decoding

Details Progressive JPEG decoding Progressive JPEG decoding

1998-02-25

2001-07-10

Johns, Andrew W. (Department: 2621)

Image analysis

Image compression or coding

Transform coding

C382S250000

Reexamination Certificate

active

06259820

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is related generally to the field of image encoding and more particularly to JPEG compression/decompression schemes and methods. It is specifically directed to a methodology of production of low resolution thumbnails directly, at low cost, without doing a full JPEG decompression.
2. Discussion of the Prior Art
The Joint Photographic Experts Group (JPEG) has promulgated a standard for still image compression, known as the JPEG standard, which employs a Discrete Cosine Transform-based algorithm. The JPEG standard is described in a number of publications, including the following references the contents and disclosures of which are incorporated by reference herein: Wallace, “The JPEG Still Picture Compression Standard,” IEEE Transactions on Consumer Electronics, Vol. 34, No. 4, pp. 30-44 (April, 1991); Feig, E., and Winograd, S., “Fast algorithms for the discrete cosine transform,” IEEE Trans. on Signal Processing., Vol. 40, no. 9, pp. 2174-2193, (September, 1992). Stone, H. S., “Progressive wavelet correlation using Fourier methods,” Submitted for publication to IEEE Trans. on Signal Processing, 1996.
As shown in FIG.
1
(
a
), in the JPEG compression method implementing sequential encoding, the original image is divided into blocks of pixels, each block typically containing 8×8 or 16×16 original image samples. Each 8×8 block of pixels is input to a DCT-encoder element
10
having a forward discrete cosine transform processor
12
that performs a Discrete Cosine Transform (DCT) on each pixel block, producing a representation of the input block as DCT coefficients corresponding to frequencies and amplitudes, rather than corresponding directly to color information. These coefficients are then quantized, or rounded off, by a quantizer element
14
in accordance with a quantization table
16
, and DC coding is performed that employs a difference algorithm over all quantized blocks in the image, in a selected scan order. This difference algorithm subtracts a “DC” or zero frequency term corresponding to the mean pixel value of a block, from the DC term of the preceding block. The difference coefficients are then scanned in a different order, such as a zigzag order, and the non-zero coefficients (i.e., blocks in which a difference from the preceding block occurred) are coded to indicate the number of preceding zero coefficients (i.e., the number of pixel blocks in which no change occurred) and also the value of the non-zero difference. An additional compression step known as entropy encoding is performed by encoder element
18
to achieve a more compact coding of the quantized DCT elements. Entropy encoding schemes specified by the JPEG standard include Huffman coding and arithmetic coding, with the optional implementation of entropy encoding tables
19
. The output
20
of the DCT encoder
10
is a data stream of compressed image data.
It should be understood that the key feature of JPEG compression is that an image is first segmented into disjoint 8×8 pixel blocks, each of which is replaced by its 2-D DCT. In such a representation, the high frequencies tend to have very small coefficients enabling JPEG quantization to drive most of these coefficients to zero. This enables fewer bits to be stored after encoding.
Decompression is performed by reversing the compression process, producing the displayable image. As shown in FIG.
1
(
b
), this typically involves inputting the compressed image data into a DCT decoder including an entropy decoder block
27
for decoding the compressed image data stream, e.g., in accordance with a Huffman decoding technique. At the output of the entropy decoder the same data structure that the encoder
10
had at the end of the DCT transform is created. Then, a dequantization block
28
for dequantizing the image samples, and an inverse discrete cosine transform processor
29
for performing an inverse discrete cosine transform taking the decoded 64 DCT coefficients and reconstructing the original image.
Besides the sequential encoding method described, the JPEG standard sets forth other largely incompatible encoding techniques. For instance, in a progressive encoding technique, the image is encoded in multiple scans for applications in which the transmission time is long and viewers prefer to watch the image build up in multiple coarse-to-clear passes. In hierarchical encoding, the image is encoded at multiple resolutions, so that lower-resolution versions may be accessed without first having to decompress the image at its full resolution. Particularly, the hierarchical mode implements “pyramidal” encoding of an image at multiple resolutions, each differing in resolution from its adjacent encoding, e.g., by a factor of two, in either horizontal or vertical dimensions or both. While enabling multiple decompression levels, the hierarchical scheme set forth in the standard requires that each additional level be stored in the compressed image.
As is known, the usefulness of decompression algorithms is determined by the number and the speed of mathematical computations performed to obtain the identifiable decompressed image. Typically, in image searching applications, it is required that each image is fully decompressed before the target image is located, which is a costly proposition as many computations are required to achieve full decompression.
It would thus be highly desirable to provide a means for achieving intermediate levels of decompression of a compressed JPEG image without having to encode the image at multiple resolutions.
Furthermore, it would be desirable to achieve multiple levels of decompression of an image that has been encoded according to the sequential (lossy) encoding standard. In such a technique, one or more decompressed “thumbnail” images may be produced, each thumbnail being observable and useful for searching applications, without the necessity of achieving full JPEG decompression of the original image.
SUMMARY OF THE INVENTION
This invention is a method and apparatus for producing low resolution decompressed images directly, at low cost, without doing a full JPEG decompression. The new algorithm is expected to be used in a context such as image searching where the thumbnails are required but the full decompressed image is not. The larger details of the original image are still visible on the lower resolution decompressed images consequently, it is not necessary to perform a complete JPEG decompression to determine if the image contains those details.
In one dimension, the method of the invention implements a factorization of the inverse DCT of order eight (8) into three phases. At the end of the first phase, two disjoint transforms of order four (4) are produced, and similarly, at the end of the second phase four transforms of order two (2) are produced. The third and final phase produces the original image data in the time or pixel domain.
In two dimensions, the inverse DCT is a two-dimensional transform of 8×8 subimages where the first component is the average of the 8×8 subimage, the second phase produces four (4) terms each of which are averages of four disjoint 4×4 subimages, the third produces 16 terms each of which is the average of 16 disjoint subimages, and the last produces all 64 terms or pixels in the 8×8 regional image, i.e., 64 subimages of size 1×1.


REFERENCES:
patent: 5293228 (1994-03-01), Marti
patent: 5600373 (1997-02-01), Chui et al.
patent: 5867602 (1999-06-01), Zandi et al.
patent: 5915027 (1999-06-01), Cox et al.
Lim, Two-Dimentsional Signal and Image Processing, Englewood-Cliffs, NJ: Prentice Hall, 1990.
Stone, “Progressive wavelet correlation using Fourier methods”, Submitted for publication to IEEE Transactions on Signal Processing, 1996.
Vetterli, et al. “Tradeoffs in the computation of mono-and multi-dimensional DCT's”, Proc. IEEE Int. Conf. Acoust, Speech, and Signal Processing, pp. 999-1002, 1989.
Wallace, “The JPEG still-picture compression standard,” CACM, vol. 34, No.

Affiliated with

Also associated with

Rating

Progressive JPEG decoding does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Progressive JPEG decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Progressive JPEG decoding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2486675