Method, apparatus and system for compressing data

Claim 3

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 adjacent bit-planes or pair of adjacent amplitudes and comparing each of the results of said applications and selecting the division point wherein the results are closest to a predefined criteria.

Claim 4

The method according to claim 1 wherein said division point is selected by assuming that the histogram is the result of two curves, one a large spike and the second a shallow gaussian, and placing the thresholds symmetrically about the center of the histogram outside the crossovers of the two curves.

Claim 5

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

Claim 6

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

Claim 7

The method according to claim 4 wherein said image quality metric is the L 1 norm metric.

Claim 8

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

Claim 9

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.

Claim 10

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

Claim 11

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

Claim 12

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

Claim 13

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.

Claim 14

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.

Claim 15

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

Claim 16

The method according to 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.

Claim 17

The method according to 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.

Claim 18

The method according to 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 thus scale) of the image transform pyramid, thereby decorrelating the redundancy of the pyramid's three orientation analysis.

Claim 19

The method according to claim 1, where in step (vi) the selection of components of the vectors is performed such that 2×2 quads identical to child vectors are defined as vectors if they possess data below the threshold, where these quads appear identically in each of Y, Cr, and Cb spaces.

Claim 20

The method described in claim 1 step (vi) wherein the selection of chrominance vector components is based on Cr-Cb pairs at a given pixel location in transform space yielding two-dimensional vectors to reduce the redundancy in color and scale/spatial location of the transform.

Claim 21

The method described in claim 18 wherein the selection of chrominance vector components is based on Cr-Cb pairs from each of the horizontal, vertical and diagonal blocks of a selected scale of the transform at a given spatial location yielding six-dimensional vectors to reduce the redundancy in color and scale/spatial location of the transform.

Claim 22

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.

Claim 23

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.

Claim 24

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.

Claim 25

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 by a subsequent vector quantizer.

Claim 26

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 sufficient accuracy as determined by hierarchy, adjacent pixel rounding error, and compression considerations.

Claim 27

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

Claim 28

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

Claim 29

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.

Claim 30

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

Claim 31

Apparatus for compressing a digital image to obtain a compressed image data set for subsequent reconstruction, comprising: means to detect and convert digital image data from RGB color 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 one of a pair of adjacent bit planes and a pair of adjacent amplitudes 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 means to losslessly encode the resulting data set to obtain a compressed image data set.

Claim 32

Apparatus for compressing a digital image to obtain a compressed image data set for subsequent reconstruction, comprising: means to detect and convert digital image data from RGB color 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 one of a pair of adjacent bit planes and a pair of adjacent amplitudes 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 means to losslessly encode the resulting data set to obtain a compressed image data set.

Claim 35

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 codes 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 program 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 computer readable program code means for causing said computer to losslessly encode the resulting data set to obtain a compressed image data set.

Claim 36

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 codes 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 program 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 computer readable program code means for causing said computer to losslessly encode the resulting data set to obtain a compressed image data set.