Storage and retrieval of large digital images

• US 5,710,835 A
• Filed: 11/14/1995
• Issued: 01/20/1998
• Est. Priority Date: 11/14/1995
• Status: Expired due to Term

• Current Assignee: Los Alamos National Security LLC (Government of the United States of America)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Bradley, Jonathan N.
• Primary Examiner(s): Bost, Dwayne
• Assistant Examiner(s): JOHNSON, BRIAN
• Application Number:
  US08/557,475
• Time in Patent Office: 798 Days
• Field of Search: 382/232, 382/240, 382/260, 382/261, 382/263, 382/264, 382/278, 382/298, 382/276, 382/282, 348/397, 348/398, 348/403, 348/411, 364/572
• US Class Current: 382/233
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/167 Position within a video image, e.g. region of interest [ROI]
• CPC Class Codes: H04N 19/1883 the unit relating to sub-band structure, e.g. hierarchical level, directional tree, e.g. low-high [LH], high-low [HL], high-high [HH]
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/635 characterised by filter definition or implementation details
• CPC Class Codes: H04N 19/645 by grouping of coefficients into blocks after the transform
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

Image compression and viewing are implemented with (1) a method for performing DWT-based compression on a large digital image with a computer system possessing a two-level system of memory and (2) a method for selectively viewing areas of the image from its compressed representation at multiple resolutions and, if desired, in a client-server environment. The compression of a large digital image I(x,y) is accomplished by first defining a plurality of discrete tile image data subsets T_ij (x,y) that, upon superposition, form the complete set of image data I(x,y). A seamless wavelet-based compression process is effected on I(x,y) that is comprised of successively inputting the tiles T_ij (x,y) in a selected sequence to a DWT routine, and storing the resulting DWT coefficients in a first primary memory. These coefficients are periodically compressed and transferred to a secondary memory to maintain sufficient memory in the primary memory for data processing. The sequence of DWT operations on the tiles T_ij (x,y) effectively calculates a seamless DWT of I(x,y). Data retrieval consists of specifying a resolution and a region of I(x,y) for display. The subset of stored DWT coefficients corresponding to each requested scene is determined and then decompressed for input to an inverse DWT, the output of which forms the image display. The repeated process whereby image views are specified may take the form an interaction with a computer pointing device on an image display from a previous retrieval.

Claims

1. A method for selectively viewing areas of an image at multiple resolutions in a computer having a primary memory for data processing and a secondary memory for data storage, the method comprising the steps of:

storing a complete set of image data array I(x,y) representing said image in a first secondary memory of said computer;

defining a plurality of discrete tile image data T_ij (x,y) subsets, where said complete set of image data I(x,y) is formed by superposition of said discrete tile image data T_ij (x,y);

performing one or more discrete wavelet transformation (DWT)-based compression processes on each said tile image data T_ij (x,y) in a selected sequence to output each said discrete tile image data T_ij (x,y) as a succession of DWT coefficients in a succession of subband sets, where one subband of each set is a low-resolution representation of said discrete tile image data T_ij (x,y) to form a sequence of low-resolution representations of said image data array I(x,y) to selected resolutions;

maintaining updated sums of said DWT coefficients from said discrete tile image T_ij (x,y) to form a seamless DWT of said image and storing said sums in a first primary memory location of said computer;

periodically compressing said sums and transferring said compressed sums to a second secondary memory to maintain sufficient memory in said primary memory for data processing, wherein said second secondary memory contains stored DWT wavelet coefficients;

selecting a viewing set of said image data array I(x,y) to be viewed at a desired resolution;

determining a viewing subset of said stored DWT wavelet coefficients that support said viewing set of said image data at said desired resolution; and

forming from said subset of said stored DWT wavelet coefficients a computer display of said viewing set of said image data at said desired resolution.

2. A method according to claim 1, wherein the step of performing one or more DWT of each said tile image data includes the step of setting all image data value to zero outside said tile image data to form a tile data array that is supported only over said tile image data subset T_ij (x,y) and performing said DWT over said entire tile data array.

3. A method according to claim 1, where said selected sequence for performing said DWT compression on said tile image data T_ij (x,y) is to compress tile image data T_i-1,j (x,y) and T_i,j-1 (x,y) before compressing T_ij (x,y).

4. A method according to claim 2, where said selected sequence for performing said DWT compression on said tile image data T_ij (x,y) is to compress tile image data T_i-1,j (x,y) and T_i,j-1 (x,y) before compressing T_ij (x,y).

5. A method according to claim 1, wherein the step of maintaining updated sums of said DWT coefficients includes the step of retrieving updated sums of DWT coefficients for T_i-1,j (x,y) and T_i,j-1 (x,y) and adding to coefficients for T_ij (x,y).

6. A method according to claim 2, wherein the step of maintaining updated sums of said DWT coefficients includes the step of retrieving updated sums of DWT coefficients for T_i-1,j (x,y) and T_i,j-1 (x,y) and adding to coefficients for T_ij (x,y).

7. A method according to claim 3, wherein the step of maintaining updated sums of said DWT coefficients includes the step of retrieving updated sums of DWT coefficients for T_i-1,j (x,y) and T_i,j-1 (x,y) and adding to coefficients for T_ij (x,y).

8. A method according to claim 4, wherein the step of maintaining updated sums of said DWT coefficients includes the step of retrieving updated sums of DWT coefficients for T_i-1,j (x,y) and T_i,j-1 (x,y) and adding to coefficients for T_ij (x,y).

9. A method according to claim 1, wherein the step of selecting a viewing set of said image data I(x,y) to be viewed at a selected resolution comprises the steps of specifying a set of coordinates (x,y) from said image data array I(x,y) and reading related stored information that includes the number of resolution levels for said subband sets, image width and height, supports and coefficient values for synthesis filters, and an offset table describing the locations of table data and compressed data records.

10. A method according to claim 1, wherein the step of selecting a viewing subset of said stored DWT wavelet coefficients includes the step of extracting wavelet coefficients corresponding to said viewing set and the corresponding synthesis filters for decompressing said wavelet coefficients.

11. A method according to claim 1, further including the step of establishing a cache memory for storing decompressed wavelet coefficients for each said computer display that is formed.

12. A method according to claim 11, wherein the step of selecting a viewing subset of said stored DWT wavelet coefficients includes a first step of determining whether said coefficients are stored in said cache memory.

26. A method according to claim 1, wherein the step of selecting a viewing subset of said DWT wavelet coefficients includes the step of extracting wavelet coefficients corresponding to said viewing set and the corresponding synthesis filters for decompressing said wavelet coefficients.

13. A method for compressing a large digital image for storage in a computer memory, the method comprising the steps of:

storing a complete set of image data array I(x,y) representing said image in a first memory location of said computer;

defining a plurality of discrete tile image data T_ij (x,y) subsets of said I(x,y), where said I(x,y) is formed by superposition of said T_ij (x,y);

performing on a computer one or more discrete wavelet transformation (DWT)-based compression processes over each said tile image data T_ij (x,y) in a selected sequence to output each said T_ij (x,y) as a succession of DWT coefficients in a succession of subband sets, where one subband of each set is a low-resolution representation of said T_ij (x,y) to form a sequence of low-resolution representations of said I(x,y) to selected resolutions; and

maintaining updated sums of said DWT coefficients from said discrete tile image T_ij (x,y) to form a seamless DWT of said I(x,y) and storing said sums in a second memory location of said computer.

14. A method according to claim 13, further including the step of:

periodically compressing said sums and transferring said compressed sums to a second secondary memory to maintain sufficient memory in said primary memory for data processing.

15. A method according to claim 13, wherein the step of performing one or more DWT of each said tile image data includes the step of setting all image data value to zero outside said tile image data to form a tile data array that is supported only over said tile image data subset T_ij (x,y) and performing said DWT over said entire tile data array.

16. A method according to claim 13, where said selected sequence for performing said DWT compression on said tile image data T_ij (x,y) is to compress tile image data T_i-1,j (x,y) and T_i,j-1 (x,y) before compressing T_ij (x,y).

17. A method according to claim 15, where said selected sequence for performing said DWT compression on said tile image data T_ij (x,y) is to compress tile image data T_i-1,j (x,y) and T_i,j-1 (x,y) before compressing T_ij (x,y).

18. A method according to claim 13, wherein the step of maintaining updated sums of said DWT coefficients includes the step of retrieving updated sums of DWT coefficients for T_i-1,j (x,y) and T_i,j-1 (x,y) and adding to coefficients for T_ij (x,y).

19. A method according to claim 14, wherein the step of maintaining updated sums of said DWT coefficients includes the step of retrieving updated sums of DWT coefficients for T_i-1,j ((x,y) and T_i,j-1 (x,y) and adding to coefficients for T_ij (x,y).

20. A method according to claim 15, wherein the step of maintaining updated sums of said DWT coefficients includes the step of retrieving updated sums of DWT coefficients for T_i-1,j (x,y) and T_i,j-1 (x,y) and adding to coefficients for T_ij (x,y).

21. A method for selectively viewing areas of an image at multiple resolutions in a computer having a primary memory for data processing and a secondary memory for data storage, the method comprising the steps of:

storing a complete set of image data array I(x,y) representing said image in a first secondary memory of said computer;

defining a plurality of discrete tile image data T_ij (x,y) subsets, where said complete set of image data I(x,y) is formed by superposition of said discrete tile image data T_ij (x,y);

performing one or more discrete wavelet transformation (DWT)-based compression processes on each said tile image data T_ij (x,y) in a selected sequence to output each said discrete tile image data T_ij (x,y) as a succession of DWT coefficients in a succession of subband sets, where one subband of each set is a low-resolution representation of said discrete tile image data T_ij (x,y) to form a sequence of low-resolution representations of said image data array I(x,y) to selected resolutions;

selecting a viewing set of said image data array I(x,y) to be viewed at a desired resolution;

determining a viewing subset of said DWT wavelet coefficients that support said viewing set of said image data at said desired resolution; and

forming from said subset of said DWT wavelet coefficients a computer display of said viewing set of said image data at said desired resolution.

22. A method according to claim 21, wherein the step of performing one or more DWT of each said tile image data includes the step of setting all image data value to zero outside said tile image data to form a tile data array that is supported only over said tile image data subset T_ij (x,y) and performing said DWT over said entire tile data array.

23. A method according to claim 21, where said selected sequence for performing said DWT compression on said tile image data T_ij (x,y) is to compress tile image data T_i-1,j (x,y) and T_i,j-1 (x,y) before compressing T_ij (x,y).

24. A method according to claim 22, where said selected sequence for performing said DWT compression on said tile image data T_ij (x,y) is to compress tile image data T_i-1,j (x,y) and T_i,j-1 (x,y) before compressing T_ij (x,y).

25. A method according to claim 21, wherein the step of selecting a viewing set of said image data I(x,y) to be viewed at a selected resolution comprises the steps of specifying a set of coordinates (x,y) from said image data array I(x,y) and reading related stored information that includes the number of resolution levels for said subband sets, image width and height, supports and coefficient values for synthesis filters, and an offset table describing the locations of table data and compressed data records.

27. A method according to claim 21, further including the step of establishing a cache memory for storing decompressed wavelet coefficients for each said computer display that is formed.

28. A method according to claim 27, wherein the step of selecting a viewing subset of said DWT wavelet coefficients includes a first step of determining whether said coefficients are stored in said cache memory.