Method apparatus and system for compressing data that wavelet decomposes by color plane and then divides by magnitude range non-dc terms between a scalar quantizer and a vector quantizer

• US 6,865,291 B1
• Filed: 06/24/1996
• Issued: 03/08/2005
• Est. Priority Date: 06/24/1996
• Status: Expired due to Fees

• Current Assignee: WDE Incorporated
• Original Assignee: WDE Incorporated
• Inventors: Zador, Andrew Michael
• Primary Examiner(s): Coles, Edward L.
• Assistant Examiner(s): RAHIMI, IRAJ A
• Application Number:
  US08/668,753
• Time in Patent Office: 3,179 Days
• Field of Search: 382/166, 382/240, 382/237, 382/233, 382/232, 382/235, 382/244, 382/245, 382/246, 382/247, 382/248, 382/250, 382/251, 382/253, 382/164, 382/260, 382/264, 382/268, 382/275, 382/269, 382/302, 382/299, 382/300, 358/538, 358/426, 358/427, 358/428, 358/429, 358/432, 358/433, 348/398, 348/422, 348/397, 348/390, 348/386, 348/391, 345/202
• US Class Current: 382/166
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• 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/30 using hierarchical techniques, e.g. scalability H04N19/63 takes precedence
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/647 using significance based coding, e.g. Embedded Zerotrees of Wavelets [EZW] or Set Partitioning in Hierarchical Trees [SPIHT]
• CPC Class Codes: H04N 19/65 using error resilience
• CPC Class Codes: H04N 19/89 involving methods or arrangements for detection of transmission errors at the decoder
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

An apparatus and method for image data compression performs a modified zero-tree coding on a range of image bit plane values from the largest to a defined smaller value, and a vector quantizer codes the remaining values and lossless coding is performed on the results of the two coding steps. The defined smaller value can be adjusted iteratively to meet a preselected compressed image size criterion or to meet a predefined level of image quality, as determined by any suitable metric. If the image to be compressed is in RGB color space, the apparatus converts the RGB image to a less redundant color space before commencing further processing.

Claims

1. A method of compressing a digital image to obtain a compressed image data set for subsequent reconstruction, comprising the steps of:

(i) determining if the digital image is a color image in RGB color space and converting any determined RGB color images to a less redundant color space;

(ii) performing a wavelet decomposition upon each of the color planes of the image in said less redundant color space to obtain a transform of DC and non-DC terms;

(iii) lossless coding the DC terms;

(iv) converting the transform to sign and magnitude format and selecting a division point comprising a pair of bit-planes which separate the non-DC terms into first and second ranges based upon absolute magnitudes, the first range comprising the values of the transform which are greater in magnitude than those values in the second range of the transform;

(v) employing a scalar quantizer to encode the values in the first range;

(vi) employing a vector quantizer to encode the values in the second range, the selection of chrominance vector components being based on Cr-Cb pairs at a given pixel location in transform space yielding two-dimensional vectors to reduce redundancy in color and scale/spatial location of the transform; and

(vii) coding the resulting data set with a lossless entropy encoder to obtain a compressed image data set.

2. The method according to claim 1 wherein said division point is selected by iteratively applying said scalar quantizer and said vector quantizer to ranges defined by at least two pairs of bit-planes and comparing each of the results of said applications and selecting the division point wherein the results are closest to a predefined criteria.

3. The method according to claim 2 wherein said predefined criteria is expressed in terms of an image quality metric.

4. The method according to claim 3 wherein said image quality metric is a mean square error metric.

5. The method according to claim 3 wherein said image quality metric is the L₁ norm metric.

6. The method according to claim 3 wherein said image quality metric is a peak signal to noise ratio metric.

7. The method according to claim 2 wherein said predefined criteria are expressed in terms of the size of the compressed image data for a selected image quality.

8. The method according to claim 2 wherein, before selecting said division point, data is depleted from said transform by removing or more severely quantizing data representing image elements which are otherwise imperceptible by the human visual system due to masking by other information in the image according to one or more predetermined visual sensitivity rules.

9. The method according to claim 1 wherein said scalar quantizer is a zero-tree type coder.

10. The method described in claim 9 wherein the subordinate pass is performed in such a way that permits vector coding of similar amplitude subordinate data, such that for all newly significant transform pixels in the previous bit plane dominant pass, the absolute value of the pixel, from the current bit plane to the lowest bit plane assigned to the zero-tree coder, is sent to the subordinate data stream at once for entropy coding or for grouping into vectors to be dealt with be a subsequent vector quantizer.

11. The method described in claim 9 wherein a single dominant pass encodes all zero trees and their root addresses whose data-roots are present in any bit plane assigned to the zero-tree coder and wherein a single subordinate pass encodes the magnitudes of the significant data to a preselected level of accuracy as determined by hierarchy, adjacent pixel rounding error, and compression considerations.

12. The method described in claim 11 wherein the data roots are pre-sorted in each hierarchy by average absolute magnitudes of triads to reduce entropy.

13. The method according to claim 1 wherein said vector quantizer is a lattice-type coder.

14. The method according to claim 1 wherein said vector quantizer is an Equitz PNN-type coder.

15. The method according to claim 1 wherein said conversion of a determined RGB image to a less redundant color space includes the step of determining color space statistics for said determined RGB image including the mean, maximum, and minimum in each orthogonal plane of the color space to allow the reconstruction of said determined RGB image to be calibrated.

16. The method according to claim 1 wherein said wavelet decomposition is performed iteratively on subbands of said image to further reduce image correlation.

17. The method defined in claim 1 wherein step (ii) further comprises the step of framing the image data with a data border of preselected width, the values of data in said border selected such that the values decrease smoothly and continuously from the gradient at the edges of the image to a value representing a flat 50% gray at each edge of the frame.

18. The method defined in claim 1 wherein step (iii) the DC terms are arranged in a rectilinear array and the lossless coding is delta coding which is performed on a row by row basis of said array, with the first data element in each row being unencoded as a reference and, when coding of said rows is completed, delta coding the first column of said array with the first pixel in said column being unencoded as a reference.

19. The method described in claim 1 step (vi) wherein the selection of components of the vectors is made in such a way that triads of pixels are grouped so that a vector represents three pixels in the transform, each pixel representing the same spatial location in each of three orientation blocks of a single level, and this scale, of the image transform pyramid, thereby decorrelating the redundancy of the pyramid'"'"'s three orientation analysis.

20. The method described in claim 1 step (vi) wherein adjacent pixels to be handled by the vector quantizer, identified as representing smoothly varying data, and quantized such that they are rounded in opposite directions are tagged in the vector stream so that the receiver can locally optimally re-smooth such pixels appropriately, without the overhead of general smoothing filters at the receiver and thereby without the incurred quality loss of smoothing edges and textures to repair dents and bruises.

21. The method described in claim 1 step (v) wherein adjacent, smooth-data pixels near edges, to be handled by the zero-tree coder, which would otherwise suffer from opposite rounding are sent in the zero-tree data with sufficient accuracy to reconstruct smoothly.

22. The method described in claim 1 step (ii) wherein color subsampling is employed to gain additional compression and wherein such subsampling which would induce mis-registration of the color data on the luminance data is corrected at the receiver by bleeding colors back into registration with luminance edges after performing the inverse wavelet transform.

23. The method described in claim 1 wherein in step (iii) the lossless coding is delta coding.

24. The method described in claim 1 wherein step (ii) further comprises performing a second wavelet decomposition on at least the largest level of non-DC terms resulting from the first wavelet decomposition and step (iv) is performed on the resulting transform.

25. The method of claim 1 wherein said less redundant color space is Y-Cr-Cb color space.

26. Apparatus for compressing a digital image to obtain a compressed image data set for subsequent reconstruction, comprising:

means to detect and convert digital image from RGB colour space to a less redundant color space;

means to perform a wavelet decomposition of each color plane of said image in said less redundant color space to obtain a transform of DC and non-DC terms;

means to losslessly encode said DC terms;

means to convert said transform to a sign and magnitude format and to select a division point comprising a pair of bit planes which separate the non-DC terms into first and second ranges, based upon absolute magnitudes, the first range comprising values of the transform which are greater in magnitude than those in the second range of the transform;

scalar quantizer means to encode the values in said first range;

vector quantizer means to encode the values in said second range and to produce two dimensional vectors, the selection of chrominance vector components being based on Cr-Cb pairs at a given pixel location in transform space to reduce redundancy in color and scale/spatial location of the transform; and

means to losslessly encode the resulting data set to obtain a compressed image data set.

27. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for implementing a digital image compression apparatus, the computer readable program code means in said article of manufacture comprising:

computer readable program code for causing said computer to detect and convert digital image data from RGB color space to a less redundant color space;

computer readable program code means for causing said computer to perform a wavelet decomposition of each color plane of said image in said less redundant color space to obtain a transform of DC and non-DC terms;

computer readable program code means for causing said computer to losslessly encode said DC terms;

computer readable programs code means for causing said computer to convert said transform to a sign and magnitude format and to select a division point comprising a pair of bit planes which separate the non-DC terms into first and second ranges, based upon absolute magnitudes, the first range comprising values of the transform which are greater in magnitude than those in the second range of the transform;

computer readable program code means for causing said computer to perform a scalar quantization to encode the values in said first range;

computer readable program code means for causing said computer to perform a vector quantization to encode the values in said second range and to produce two dimensional vectors, the selection of chrominance vector components being based on Cr-Cb pairs a given pixel location in transform space to reduce redundancy in color and scale/spatial location of the transform; and

computer readable program code means for causing said computer to losslessly encode the resulting data set to obtain a compressed image data set.