Multiresolution compressed image management system and method

• US 6,041,143 A
• Filed: 04/14/1998
• Issued: 03/21/2000
• Est. Priority Date: 04/14/1998
• Status: Expired due to Term

• Current Assignee: Qualcomm, Inc.
• Original Assignee: TeraLogic, Inc. (Cubic Corporation)
• Inventors: Zhang, Lefan, Chui, Charles K.
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US09/060,398
• Time in Patent Office: 707 Days
• Field of Search: 382/232, 382/236, 382/239, 382/240, 382/242, 382/243, 382/246, 382/248
• US Class Current: 382/232
• CPC Class Codes: G06T 3/4084 in the transform domain, e.g. fast Fourier transform [FFT] domain scaling
• CPC Class Codes: H04N 19/102 characterised by the element, parameter or selection affected or controlled by the adaptive coding
• CPC Class Codes: H04N 19/162 User input
• CPC Class Codes: H04N 19/17 the unit being an image region, e.g. an object
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 21/44 Processing of video elementary streams, e.g. splicing a video clip retrieved from local storage with an incoming video stream or rendering scenes according to encoded video stream scene graphs
• CPC Class Codes: H04N 21/440263 by altering the spatial resolution, e.g. for displaying on a connected PDA
• CPC Class Codes: H04N 21/4728 for selecting a Region Of Interest [ROI], e.g. for requesting a higher resolution version of a selected region

Abstract

In a multiresolution image processing system images are stored in files that contain thumbnail data as well as a full image data structure. The image data is preferably wavelet or wavelet-like transform coefficients, generated by applying a wavelet or wavelet-like transform to an image multiple times. Data representing mid-level resolution images are generated on the fly by extracting from the full image data structure only the data needed for the user or application selected resolution level. If the user has selected a subset of the image for viewing at a higher resolution level, a corresponding mid-level resolution image is constructed by extracting from the full image data structure the data needed for the user specified image portion at the user or application selected resolution level. The full image data structure is preferably encoded and stored in a manner allowing the image data for mid-level resolution images to be efficiently extracted without having to compute or recompute any image coefficients. By storing only thumbnail data and the full image data in an image file, and producing image data structures for other resolution levels on the fly, the storage requirements for image files are reduced. Since the image data structures for other resolution levels can be generated with minimal computational resources in a small fraction of a second, in most implementations the user will not be adversely affected by the non-inclusion of the other resolution levels in the image file.

Claims

1. Image processing apparatus, for use in conjunction with an image display device, the image processing apparatus comprising:

a memory device for storing data, including a first image data structure, the first image data structure including a first array of wavelet transform coefficients corresponding to a full resolution image;

a data processor coupled to the memory device;

a multiresolution image management procedure, executable by the data processor, including instructions for generating an image at any of a plurality of selectable resolution levels, the instructions including;

image reconstruction instructions for applying an inverse wavelet or wavelet-like transform to a specified set of image data so as to generate image data for displaying a corresponding image on the image display device; and

image data extraction instructions, for use when an image resolution level lower than full resolution is selected, wherein the image data extraction instructions generate a second image data structure from the first image data structure by extracting a subset of the wavelet transform coefficients from the first array and storing the extracted subset in a second array in the second image data structure;

wherein the image reconstruction instructions operate on the second image data structure when an image resolution level lower than full resolution is selected and operate on the first image data structure when a full image resolution is selected.

7. The image processing apparatus of claim 1, the multiresolution image management procedure including:

image cropping instructions for enabling a user to select a cropped portion of an image displayed on the image display device, wherein the displayed image has been generated from data in the first data structure or in the second data structure; and

cropped image data extraction instructions for generating a third image data structure from the first image data structure by extracting from the first array a subset of the wavelet transform coefficients corresponding to the cropped portion of the displayed image and storing the extracted subset in a third array in the third image data structure.

8. The image processing apparatus of claim 1, wherein

the first array includes a set of tree structures, each representing a tree of wavelet coefficients at respective positions in a wavelet or wavelet-like transform coefficient array;

and

the image data extraction instructions include instructions for copying a portion of each of the tree structures into the second array, wherein the copied portion is determined in accordance with the selected resolution level.

2. Image processing apparatus, for use in conjunction with an image display device, the image processing apparatus comprising:

a memory device for storing data, including a first image data structure, the first image data structure including a first array of wavelet transform coefficients corresponding to a full resolution image;

a data processor coupled to the memory device;

a multiresolution image management procedure, executable by the data processor, including instructions for generating an image at any of a plurality of selectable resolution levels, the instructions including;

image reconstruction instructions for applying an inverse wavelet or wavelet-like transform to a specified set of image data so as to generate image data for displaying a corresponding image on the image display device; and

image data extraction instructions, for use when an image resolution level lower than full resolution is selected, wherein the image data extraction instructions generate a second image data structure from the first image data structure by extracting a subset of the wavelet transform coefficients from the first array and storing the extracted subset in a second array in the second image data structure;

wherein the image reconstruction instructions operate on the second image data structure when an image resolution level lower than full resolution is selected and operate on the first image data structure when a full image resolution is selected;

wherein

the first array includes a sequence of subarrays, each representing a rectangular set of wavelet coefficients in a respective region of a wavelet or wavelet-like transform coefficient array;

the image data extraction instructions include instructions for copying a subset of the subarrays in the first array into the second array, without modification thereof, wherein the subarray subset is determined in accordance with the selected resolution level.

3. The image processing apparatus of claim 2, wherein

the image data extraction instructions include instructions for partially copying a second subset of subarrays in the first array into the second array, the wavelet coefficients represented by each subarray in the second subset including some wavelet coefficients associated with the selected resolution level and some wavelet coefficients not associated with the selected resolution level;

and

each subarray in the second subset is partially copied by decoding the subarray to generate a rectangular set of wavelet coefficients, replacing with zero values the wavelet coefficients in the rectangular set that are not associated with the selected resolution level, re-encoding the rectangular set of wavelet coefficients and storing the re-encoded set of wavelet coefficients in the second array.

4. The image processing apparatus of claim 2, wherein the subarray subset is determined in accordance with the selected resolution level and a user specified subregion of the image corresponding to the first array.

5. The image processing apparatus of claim 2, wherein

the first image data structure includes a thumbnail data structure containing an array of wavelet transform coefficients corresponding to a low resolution image;

the multiresolution image management procedure including instructions for displaying the decoding the thumbnail data structure and displaying the low resolution image.

6. The image processing apparatus of claim 2, the multiresolution image management procedure including:

image cropping instructions for enabling a user to select a cropped portion of the low resolution image; and

cropped image data extraction instructions for generating a third image data structure from the first image data structure by extracting from the first array a subset of the wavelet transform coefficients corresponding to the cropped portion of the low resolution image and storing the extracted subset in a third array in the third image data structure.

9. A method of processing image data, for use in conjunction with an image display device, the steps of the method comprising:

storing a first image data structure, the first image data structure including a first array of wavelet or wavelet-like transform coefficients corresponding to a full resolution image;

generating a second image data structure from the first image data structure by extracting a subset of the wavelet or wavelet-like transform coefficients from the first array and storing the extracted subset in a second array in the second image data structure; and

applying an inverse wavelet or wavelet-like transform to the wavelet or wavelet-like transform coefficients in the second image data structure so as to generate image data for displaying a corresponding image on the image display device;

wherein

the first array includes a sequence of subarrays, each representing a rectangular set of coefficients in a respective region of a wavelet or wavelet-like transform coefficient array;

the second image data structure generating step includes copying a subset of the subarrays in the first array into the second array, without modification thereof, wherein the subarray subset is determined in accordance with a selected resolution level.

10. The method of claim 9, wherein

the second image data structure generating step includes partially copying a second subset of subarrays in the first array into the second array, the wavelet or wavelet-like coefficients represented by each subarray in the second subset including some coefficients associated with the selected resolution level and some coefficients not associated with the selected resolution level;

and

each subarray in the second subset is partially copied by decoding the subarray to generate a rectangular set of wavelet or wavelet-like coefficients, replacing with zero values the coefficients in the rectangular set that are not associated with the selected resolution level, re-encoding the rectangular set of coefficients and storing the re-encoded set of coefficients in the second array.

11. The method of claim 9, wherein the subarray subset is determined in accordance with the selected resolution level and a user specified subregion of the image corresponding to the first array.

12. The method of claim 9, wherein

the first image data structure includes a thumbnail data structure containing an array of wavelet or wavelet-like transform coefficients corresponding to a low resolution image;

the method includes decoding the thumbnail data structure and displaying the low resolution image.

13. The method of claim 12, including

enabling a user to select a cropped portion of the low resolution image;

and

generating a third image data structure from the first image data structure by extracting from the first array a subset of the wavelet or wavelet-like transform coefficients corresponding to the cropped portion of the low resolution image and storing the extracted subset in a third array in the third image data structure.

14. The method of claim 9, including:

enabling a user to select a cropped portion of an image displayed on the image display device, wherein the displayed image has been generated from data in the first data structure or in the second data structure; and

generating a third image data structure from the first image data structure by extracting from the first array a subset of the wavelet or wavelet-like transform coefficients corresponding to the cropped portion of the displayed image and storing the extracted subset in a third array in the third image data structure.

15. A computer program product for use in conjunction with a computer controlled system having memory and an image display device, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

an image storage module for storing data, including a first image data structure, in the memory of the computer controlled system, the first image data structure including a first array of wavelet transform coefficients corresponding to a full resolution image, the first array including a sequence of subarrays, each representing a rectangular set of wavelet coefficients in a respective region of a wavelet or wavelet-like transform coefficient array;

a multiresolution image management module, including instructions for generating an image at any of a plurality of selectable resolution levels, the instructions including;

image reconstruction instructions for applying an inverse wavelet or wavelet-like transform to a specified set of image data so as to generate image data for displaying a corresponding image on the image display device; and

image data extraction instructions, for use when an image resolution level lower than full resolution is selected, wherein the image data extraction instructions generate a second image data structure from the first image data structure by extracting a subset of the wavelet transform coefficients from the first array and storing the extracted subset in a second array in the second image data structure, the image data extraction instructions including instructions for copying a subset of the subarrays in the first array into the second array, without modification thereof, wherein the subarray subset is determined in accordance with the selected resolution level;

wherein the image reconstruction instructions operate on the second image data structure when an image resolution level lower than full resolution is selected and operate on the first image data structure when a full image resolution is selected.

16. The computer program product of claim 15, wherein

the image data extraction instructions include instructions for partially copying a second subset of subarrays in the first array into the second array, the wavelet coefficients represented by each subarray in the second subset including some wavelet coefficients associated with the selected resolution level and some wavelet coefficients not associated with the selected resolution level;

and

each subarray in the second subset is partially copied by decoding the subarray to generate a rectangular set of wavelet coefficients, replacing with zero values the wavelet coefficients in the rectangular set that are not associated with the selected resolution level, re-encoding the rectangular set of wavelet coefficients and storing the re-encoded set of wavelet coefficients in the second array.

17. The computer program product of claim 15, wherein the subarray subset is determined in accordance with the selected resolution level and a user specified subregion of the image corresponding to the first array.

18. The computer program product of claim 15, wherein

the first image data structure includes a thumbnail data structure containing an array of wavelet transform coefficients corresponding to a low resolution image;

the multiresolution image management module including instructions for displaying the decoding the thumbnail data structure and displaying the low resolution image.

19. The computer program product of claim 15, the multiresolution image management module including:

image cropping instructions for enabling a user to select a cropped portion of the low resolution image; and

cropped image data extraction instructions for generating a third image data structure from the first image data structure by extracting from the first array a subset of the wavelet transform coefficients corresponding to the cropped portion of the low resolution image and storing the extracted subset in a third array in the third image data structure.

20. A computer program product for use in conjunction with a computer controlled system having memory and an image display device, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

an image storage module for storing data, including a first image data structure, in the memory of the computer controlled system, the first image data structure including a first array of wavelet transform coefficients corresponding to a full resolution image;

a multiresolution image management module, including instructions for generating an image at any of a plurality of selectable resolution levels, the instructions including;

image reconstruction instructions for applying an inverse wavelet or wavelet-like transform to a specified set of image data so as to generate image data for displaying a corresponding image on the image display device; and

image data extraction instructions, for use when an image resolution level lower than full resolution is selected, wherein the image data extraction instructions generate a second image data structure from the first image data structure by extracting a subset of the wavelet transform coefficients from the first array and storing the extracted subset in a second array in the second image data structure;

wherein the image reconstruction instructions operate on the second image data structure when an image resolution level lower than full resolution is selected and operate on the first image data structure when a full image resolution is selected.

21. The computer program product of claim of 20, wherein the multiresolution image management module includes:

image cropping instructions for enabling a user to select a cropped portion of an image displayed on the image display device, wherein the displayed image has been generated from data in the first data structure or in the second data structure; and

cropped image data extraction instructions for generating a third image data structure from the first image data structure by extracting from the first array a subset of the wavelet transform coefficients corresponding to the cropped portion of the displayed image and storing the extracted subset in a third array in the third image data structure.

22. The computer program product of claim of 20, wherein

the first array includes a set of tree structures, each representing a tree of wavelet coefficients at respective positions in a wavelet or wavelet-like transform coefficient array;

and

the image data extraction instructions include instructions for copying a portion of each of the tree structures into the second array, wherein the copied portion is determined in accordance with the selected resolution level.