Progressive JPEG decoding

• US 6,259,820 B1
• Filed: 02/25/1998
• Issued: 07/10/2001
• Est. Priority Date: 10/06/1997
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Research Institute, Inc. (NEC Corporation)
• Inventors: Stone, Harold S.
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): AZARIAN, SEYED H
• Application Number:
  US09/030,496
• Time in Patent Office: 1,231 Days
• Field of Search: 382/250, 382/251, 382/252, 382/253, 382/233, 382/240, 382/248, 358/432
• US Class Current: 382/250
• CPC Class Codes: H04N 19/60 using transform coding

Abstract

This invention enables progressively higher resolution images of a JPEG compressed image to be produced in a cost effective manner during the JPEG decompression process. The operation count is very low when images of {fraction (1/64)}th, {fraction (1/16)}th, and ¼th of full resolution are to be produced without doing a full JPEG decompression. The low resolution images are useful for high speed search, and the ability to produce them without doing full decompression is an important factor in making such search practical.

Claims

1. An apparatus for generating one or more images at various levels of decompression directly from a fully compressed baseline JPEG encoded image, said apparatus comprising:

means for generating a matrix of disjoint subarrays of size n×

n, each of said subarrays is a two-dimensional DCT of a corresponding subarray of elements from said compressed baseline JPEG encoded image;

means for extracting one or more elements from each of said disjoint subarrays in accordance with a desired level of decompression and arranging said extracted elements in a predetermined order corresponding to an order of elements in a disjoint subarray from which they were extracted; and

,

means for arranging said extracted elements of predetermined order to generate a decompressed version of said original image, each said decompressed image having an image resolution a fraction of a resolution of an original image.

2. The apparatus of claim 1, wherein for a zeroth level of decompression, said means for extracting elements includes extracting all zero frequency components from each said disjoint subarrays of said matrix.

3. The apparatus of claim 2, wherein said zeroth level of decompression produces an image having {fraction (1/64)}th the resolution of said fully JPEG compressed image.

4. The apparatus of claim 1, wherein for a first level of decompression, said means for extracting elements includes extracting four elements at predefined locations from each said disjoint subarrays.

5. The apparatus of claim 4, wherein said first level of decompression produces an image having {fraction (1/16)}th the resolution of said fully JPEG compressed image.

6. The apparatus of claim 1, wherein for a second level of decompression, said means for extracting elements includes extracting sixteen elements at predefined locations from each said disjoint subarrays.

7. The apparatus of claim 6, wherein said second level of decompression produces an image having ¼

th the resolution of said fully JPEG compressed image.

8. An apparatus for generating one or more images at intermediate levels of decompression, at a zeroth level of decompression, and at a final level of decompression, each said intermediate level of decompression obtained directly from a fully compressed baseline JPEG encoded image, said apparatus comprising:

means for progressively calculating images to achieve a desired intermediate level of decompression, said means utilizing information obtained from an intermediate level image generated for a decompression level immediately prior to the desired level of decompression to enable generation of images in a minimum of operations.

9. The apparatus of claim 8, wherein for said zeroth level of decompression, said progressive calculation means generates an image having {fraction (1/64)}th the resolution of said original JPEG compressed image.

10. The apparatus of claim 8, wherein for a first intermediate level of decompression, said progressive calculation means generates an image having {fraction (1/16)}th the resolution of said original JPEG compressed image.

11. The apparatus of claim 8, wherein for a second intermediate level of decompression, said progressive calculation means generates an image having ¼

th the resolution of said original JPEG compressed image.

12. The apparatus of claim 8, wherein said progressive calculation means comprises:

means for generating a matrix of disjoint subarrays of size n×

n, each subarray being a two-dimensional discrete cosine transform of a corresponding subarray of elements from a said compressed JPEG encoded image;

means for extracting one or more elements from each of said disjoint subarrays in accordance with a desired level of decompression, and arranging said extracted elements in a predetermined order corresponding to an order of elements in a disjoint subarray from which they were extracted; and

,

means for combining said extracted elements of predetermined order to generate a decompressed version of said original image, each said decompressed image having an image resolution a fraction of a resolution of an original image.

13. The apparatus of claim 12, wherein a size “

n”

of disjoint subarrays is eight, said means for extracting elements at said zeroth level of decompression includes means for extracting a zero frequency component from each disjoint subarrays.

14. The apparatus of claim 13, wherein said means for extracting elements at said a first level of decompression include means for extracting four elements at predefined locations from each said disjoint subarrays.

15. The apparatus of claim 14, wherein said means for extracting elements at said first level of decompression includes means for averaging a group of sixteen pixels at predefined locations from said original image, said apparatus including processing means for transforming said n×

n matrix into four disjoint blocks.

16. The apparatus of claim 15, wherein said processing means includes means for multiplying an n×

n subarray by a cross product of a predefined 2×

8 matrix.

17. The apparatus of claim 16, wherein for a second level of decompression, said means for extracting elements includes extracting sixteen elements at predefined locations from each said disjoint subarrays, said group of sixteen elements including said four elements and zero frequency components from each said disjoint subarrays.

18. The apparatus of claim 17, wherein said processing means includes means for multiplying said original n×

n matrix by an first operator matrix having a submatrix equivalent to said predefined 2×

8 matrix.

19. The apparatus of claim 18, wherein said first operator matrix is a matrix having a factorization of a form (H₂×

H₂×

H₂×

H₂) (T₂×

T₂) (W×

W), where H₂ is a Hadamard matrix of order 2 and T₂ is an 8×

4 matrix and W is a 8×

8 matrix.

20. The apparatus of claim 19, wherein for a final level of decompression, said extracted elements include a set of 64 elements corresponding to all positions from said disjoint subarray.

21. The apparatus of claim 20, wherein said processing means includes means for multiplying said original n×

n matrix by a second operator matrix (H₈×

H₈) (V×

V), said multiplying step including means enabling utilization of data generated from a result of computing (T₂×

T₂) (W×

W), where H₈ is a Hadamard matrix of order 8 and V is a predefined 8×

8 matrix.

22. The apparatus of claim 20, wherein said original JPEG compressed image has been Huffman encoded, said apparatus including means for performing Huffman decoding on said original n×

n matrix.

23. A method for generating one or more decompressed images at various levels of decompression directly from a fully compressed baseline JPEG encoded image, said compressed baseline JPEG encoded image represented as blocks of discrete cosine transformed pixels of an original image, said method comprising the steps of providing a progressive operator for calculating images at a desired level of decompression, each calculating step utilizing information obtained from a calculation of an image at a decompression level immediately prior to the desired level of decompression to enable generation of images in a minimum of operations.

24. The method for generating one of more decompressed images of claim 23, wherein said progressive operator is of a form H₈V where H₈ is a Hadamard matrix of order eight and V is a predefined 8×

8 matrix.

25. The method for generating one or more decompressed images of claim 23, wherein said progressive operator is factored according to a form (H₂×

I₄) (I₂×

(H₂×

I₂) (I₄×

H₂) V, where H₂ is a Hadamard matrix of order two, V is a predefined 8×

8 matrix, I₄ and I₂ are identity matrices of rank four and two, respectively.

26. The method for generating one or more decompressed images of claim 23, wherein at a zeroth level of decompression, said calculating step includes the step of calculating V, where V is a predefined 8×

8 matrix.

27. The method for generating one or more decompressed images of claim 26, wherein at a first level of decompression, said calculating step includes the step of calculating (I₄×

H₂)V H₂), V, where H₂ is a Hadamard matrix of order to and I₄ is an identity matrix of rank four.

28. The method for generating one or more decompressed images of claim 27, wherein at a second level of decompression, said calculating step includes the step of calculating (I₃×

(H₂×

I₂) (I₄×

H₂) V H₂) V, where I₂ is an identity matrix of rank two.

29. The method for generating one or more decompressed images of claim 28, wherein at a final level of decompression, said calculating step includes the step of calculating (H₂×

I₄) (I₂×

(H₂×

I₂) (I₄×

H₂) V.

30. A method for generating one or more decompressed images at various levels of decompression directly from a fully compressed baseline JPEG encoded image, comprising the steps of:

(a) retrieving a fully compressed baseline JPEG encoded image;

(b) generating a matrix of disjoint subarrays of size n×

n, each subarray being a two-dimensional DCT of a corresponding subarray of said compressed baseline JPEG encoded image;

(c) extracting one or more elements from each of said disjoint subarrays in accordance with a desired level of decompression, and arranging said extracted elements in a predetermined order corresponding to an order of a disjoint subarray from which said elements came; and

(d) generating said image corresponding to a desired level of decompression from said extracted one or more elements.

31. A method according to claim 30, wherein said original JPEG compressed image has been Huffman encoded, said method further including after retrieving step (a), the step of preprocessing said compressed JPEG image according to a Huffman decoding.

32. A method according to claim 30, wherein a size “

n”

of said disjoint subarrays is eight, and for a zeroth level of decompression, said extracting step includes the step of extracting only one element from each of said subarrays.

33. A method according to claim 32, wherein said extracted only one element corresponds to element located at position (0,0) of said disjoint subarray.

34. A method according to claim 32, wherein for a first level of decompression, said extracted elements include a set of four elements at predefined locations from each of said disjoint subarrays, said group of four elements including a zero frequency component from each said disjoint subarray.

35. A method according to claim 34, wherein at said first level of decompression, said extracting step includes averaging a group of sixteen pixels at predefined locations from said n×

n matrix corresponding to said original image, to obtain four disjoint blocks.

36. A method according to claim 35, wherein said locations for extracting said four components include positions (0,0), (4,0), (0,4) and (4,4) of said disjoint subarray.

37. A method according to claim 35, wherein at a second level of decompression, said extracted elements include a set of sixteen elements at predefined locations from each said disjoint subarrays, said group of sixteen elements including said four elements and zero frequency components from each said disjoint subarrays.

38. A method according to claim 37, wherein “

n”

=eight (8) and at said first level of decompression, said extracting step includes the step of multiplying each n×

n subarray by a cross product of a predefined 2×

8 matrix.

39. A method according to claim 38, wherein for said second level of decompression, said extracting step includes multiplying said original n×

n matrix by a first operator matrix having a submatrix equivalent to said predefined 2×

8 matrix.

40. A method according to claim 39, wherein said first operator matrix is a matrix having a factorization of a form (H₂×

H₂×

H₂×

H₂) (T₂×

T₂) (W×

W), where H₂ is a Hadamard matrix of order 2 and T₂ is an 8×

4 matrix and W is a 8×

8 matrix.

41. A method according to claim 40, wherein for a final level of decompression, said extracted elements include a set of 64 elements corresponding to all positions from said disjoint subarray.

42. A method according to claim 41, wherein said extracting step includes the step of multiplying said original n×

n matrix by a second operator matrix (H₈×

H₈) (V×

V), said multiplying step further including utilizing data generated from a result of computing (T₂×

T₂) (W×

W) of said first operator matrix, where H₈ is a Hadamard matrix of order eight and V is a predefined 8×

8 matrix.