US 6,785,425 B1 · Method and system for compression of images

Abstract

A Simple Inter Color Lossless Image Coder (SICLIC) for the compression of colored images is provided. The color image is treated as several interlaced gray level images that correspond to respective distinct color planes. The compression scenario utilizes three main steps, such as selection of the predictor, context forming with bias cancellation and coding. SICLIC implements predictors, context forming and encoder techniques that exploit the intra- and inter-color plane correlations in an effective and relatively computationally inexpensive manner. The predictor is selected on the basis of the right selection of the contribution of each color plane between the intra- and inter-plane predictors obtained as a weight average of contribution from different color planes. SICLIC processes the image in two modes—regular mode and run mode. A special care is taken to ensure a proper treatment of joint runs, which occur simultaneously in all color planes.

Claims31

Dependent claims

A method for obtaining substantially lossless compression of a color digitized image that is composed of three distinct gray level images, which correspond to respective distinct color planes;

each of said gray level images includes pixels, the method comprising the steps of:
(a) compressing a first gray level image that corresponds to a first color plane, utilizing an intra-color prediction;
(b) for the second gray level image relative to said first gray level image, performing repeatedly:
(i) calculating a predicted value of a pixel on the basis of inter-color correlations between at least one adjacent pixel in the second gray level image and at least one adjacent element in the first gray level image;
(ii) comparing the predicted value and the real value of the element so as to produce residual value;
(iii) determining the context of said element, wherein said determining includes constructing parallel context spaces;
providing an inter-color neighborhood composed of inter-color elements and constructed on the basis of the inter-color correlations stipulated in step b(i);
and calculating the context of said element from values of gradients determined by calculating the difference between adjacent inter-color elements in said neighborhood;
(iv) quantizing said context;
(v) updating a quantized context related bias residue;
(vi) comparing the residual value and the bias residual value to produce a bias-free residual value;
and
(vii) coding said bias-free residual value;
and
(c) for the third gray level image, performing said steps b(i) to b(vii) relative to either or both of said first gray level image and second gray level image,
wherein the predicted value of a pixel in the second gray level image is determined in either vertical or horizontal directions, or both vertical and horizontal directions taken as a weighted function, in accordance with the following algorithmic expressions:
Ŷi,jv=Di−1,j+Xi,j=Yi−1,j+(Xi,j−Xi−1,j),
and
Ŷi,jh=Di,j−1+Xi,j=Yi,j−1+(Xi,j−Xi,j−1),
wherein said inter-color neighborhood stands for:
Di−1,j, Di,j−1 and said Xi,j stands for the corresponding pixel in said first gray level image.

18 more elements

A method for obtaining substantially lossless compression of a color digitized image that is composed of three distinct gray level images, which correspond to respective distinct color planes;

each of said gray level images includes pixels, the method comprising the steps of:
(a) compressing a first gray level image that corresponds to a first color plane, utilizing an intra-color prediction;
(b) for the second gray level image relative to said first gray level image, performing repeatedly;
(i) calculating a predicted value of a pixel on the basis of inter-color correlations between at least one adjacent pixel in the second gray level image and at least one adjacent element in the first gray level image
(ii) comparing the predicted value and the real value of the element so as to produce residual value;
(iii) determining the context of said element;
(iv) quantizing said context;
(v) updating a quantized context related bias residue;
(vi) comparing the residual value and the bias residual value to produce a bias-free residual value;
and
(vii) coding said bias-free residual value;
(c) for the third gray level image, performing said steps b(i) to b(vii) relative to either or both of said first gray level image and second gray level image;
the method wherein step b(i) includes:
(A) providing an inter-color neighborhood composed of inter-color elements;
each element is produced by computing the difference value between the value of an adjacent pixel in said first gray level image and the value of corresponding adjacent pixel in said second gray level image;
(B) predicting the value of a pixel by calculating a linear combination of said elements and the value of the corresponding pixel in said first gray level image.

13 more elements

A method for obtaining substantially lossless compression of a color digitized image that is composed of three distinct gray level images, which correspond to respective distinct color planes;

each of said gray level images includes pixels, the method comprising the steps of:
(a) compressing a first gray level image that corresponds to a first color plane, utilizing an intra-color prediction;
(b) for the second gray level image relative to said first gray level image, performing repeatedly:
(i) calculating a predicted value of a pixel on the basis of inter-color correlations between at least one adjacent pixel in the second gray level image and at least one adjacent element in the first gray level image;
(ii) comparing the predicted value and the real value of the element so as to produce residual value;
(iii) determining the context of said element;
(iv) quantizing said context;
(v) updating a quantized context related bias residue;
(vi) comparing the residual value and the bias residual value to produce a bias-free residual value;
and
(vii) coding said bias-free residual value;
(c) for the third gray level image, performing said steps b(i) to b(vii) relative to either or both of said first gray level image and second gray level image,
wherein said prediction step on the basis of inter-color correlation stipulated in said step b(i) includes predicting the value of said element by calculating a non-linear combination of said inter-color elements and the value of the corresponding pixel in said first gray level image;
wherein the predicted value of a pixel in the second gray level image is determined in either vertical or horizontal directions, or both vertical and horizontal directions taken as a weighted function;
the predicted value of a pixel are calculated in accordance with the following algorithmic expressions:
Y ^ i , j v = ( Y i - 1 , j ) t · ( X i , j 1 + X i - 1 , j ) p ⁢ ⁢ and Y ^ i , j h = ( Y i , j - 1 ) u · ( X i , j 1 + X i , j - 1 ) s ,
wherein the exponents p, t, s, and u, take the values from the set of real numbers, Yi−1,j is one of the pixel in the neighborhood to the left the pixel Yij, Yi−1 j is one of the pixels in the neighborhood above the pixel Yij, the elements Xij, Xi−1 j and Xi,j−1 are the corresponding pixels in the first gray level image.

14 more elements

A method for obtaining substantially lossless compression of a color digitized image that is composed of three distinct gray level images, which correspond to respective distinct color planes;

each of said gray level images includes pixels, the method comprising the steps of:
(a) compressing a first gray level image that corresponds to a first color plane, utilizing an intra-color prediction;
(b) for the second gray level image relative to said first gray level image, performing repeatedly:
(i) calculating a predicted value of a pixel on the basis of inter-color correlations between at least one adjacent pixel in the second gray level image and at least one adjacent element in the first gray level image;
(ii) comparing the predicted value and the real value of the element so as to produce residual value;
(iii) determining the context of said element;
(iv) quantizing said context;
(v) updating a quantized context related bias residue;
(vi) comparing the residual value and the bias residual value to produce a bias-free residual value;
and
(vii) coding said bias-free residual value;
(c) for the third gray level image, performing said steps b(i) to b(vii) relative to either or both of said first gray level image and second gray level image,
the method further comprising additional distinct gray level image, constituting fourth gray level image that correspond to fourth distinct color plain;
said method further comprising the step of:
for the fourth gray level image, performing said steps b(i) to b(vii) relative to either one or more than said first gray level image, said second gray level image or said third gray level image, wherein said steps include:
(A) initializing 256 contexts for use in the black prediction, where each context contains a single predictor value k (context), an averaged prediction residual and a number of the prediction residuals;
(B) for k component of each pixel (c, m, y, k) performing repeatedly,
(i) computing the intra-plane predictor for k by using the intra-plane gradient context method (LOCO);
(ii) computing the minimum integral value CMYmin normalized to the largest value of Fcc, Fmm, and Fyy, where Fc, Fm, and Fy are numbers between 0 and 1, normalizing CMYmin to the largest value of Fcc, Fmm, and Fyy, and multiplying, by 255, to obtain an integral black prediction context between 0 and 255;
(iii) using the predictor value, k (i.e., f(CMYmin), if a predictor value exists in the black prediction context CMYmin), and updating the averaged prediction residual and the number of the prediction residuals for every context;
(iv) storing the actual value of k as the predictor k (f(CMYmin)) for this context if no predictor value exists in the CMYmin context;
(v) selecting a predictor according to the better of the two context-based average prediction residuals and encode the associated residual;
(C) adding a list consisting of the 256 predictor values contained in the 256 black prediction contexts into the compressed data stream for use by the decompression procedure.

20 more elements

A method of decompression of a color image composed of three distinct color planes using a decoder, the method comprising:

(i) retrieving the compressed color image;
and
(ii) decoding at least one color pixel from data of compressed image, comprising the steps of:
(a) determining the context of at least one pixel by performing the steps that include:
(1) providing intra-color and inter-color neighborhoods constructed on the basis of the intra-color and inter-color correlations, wherein the intra-color and inter-color neighborhoods are composed of intra-color pixels and inter-color elements;
and
(2) determining the context of said pixel and element based on values of at least one gradient between at least two pixels and at least one gradient between at least two elements in said neighborhoods;
(b) calculating predicted values of a pixel and element on the basis of inter-color correlation between at least two adjacent pixels and between at least two adjacent elements, wherein the adjacent pixel is at least one pixel of the intra-color consolation and the adjacent element is at least one element in the second gray level image and corresponding at least one adjacent element in the first gray level image;
(c) accessing a context-specific code table and retrieving residual values from the table in response to encoded data, said residual vanities corresponding to intra- and inter-plane contexts;
(d) combining the residual values with the predicted values for at least one pixel and at least one element in order to obtain an actual value of said color pixel,
wherein the predicted value of a pixel in the second gray level image is determined in either vertical or horizontal directions, or both vertical and horizontal directions taken as a weighted function, in accordance with the following algorithmic expressions:
Y ^ i , j v = D i - 1 , j + X i , j = Y i - 1 , j + ( X i , j - X i - 1 , j ) , ⁢ and Y ^ i , j h = D i , j - 1 + X i , j = Y i , j - 1 + ( X i , j - X i , j - 1 ) ,
wherein said inter-color neighborhood stands for:
Di−1, j, Di,j−1 and said Xij stands for the corresponding pixel in said first gray level image.

11 more elements

A method of decompression of a color image composed of three distinct color planes using a decoder, the method comprising:

(i) retrieving the compressed color image;
and
(ii) decoding at least one color pixel from data of compressed image, comprising the steps of:
(a) determining the context of at least one pixel by performing the steps that include:
(1) providing intra-color and inter-color neighborhoods constructed on the basis of the intra-color and inter-color correlations, wherein the intra-color and inter-color neighborhoods are composed of intra-color pixels and inter-color elements;
and
(2) determining the context of said pixel and element based on values of at least one gradient between at least two pixels and at least one gradient between at least two elements in said neighborhoods;
(b) calculating predicted values of a pixel and element on the basis of inter-color correlation between at least two adjacent pixels and between at least two adjacent elements, wherein the adjacent pixel is at least one pixel of the intra-color conelation and the adjacent element is at least one element in the second gray level image and corresponding at least one adjacent element in the first gray level image
(c) accessing a context-specific code table and retrieving residual values from the table in response to encoded data, said residual values corresponding to intra- and inter-plane contexts;
(d) combining the residual values with the predicted values for at least one pixel and at least one element in order to obtain an actual value of said color pixel,
wherein the predicted value of a pixel in the second gray level image is determined in either vertical or horizontal directions, or both vertical and horizontal directions taken as a weighted function, the predicted value of a pixel are calculated in accordance with the following algorithmic expressions:
Y ^ i , j v = ( Y i - 1 , j ) t · ( X i , j 1 + X i - 1 , j ) p and Y ^ i , j h = ( Y i , j - 1 ) u · ( X i , j 1 + X i , j - 1 ) s ,
wherein the exponents p, i, s, and u, take the values from the set of real numbers, Yi−1j is one of the pixel in the neighborhood to the left the pixel Yij, Y1−1,j is one of the pixels in the neighborhood above the pixel Yij, the elements Xij, Xi−1j and Xij−1 are the corresponding pixels in the first gray level image.

10 more elements

Dependencies are inferred from the claim text.

Method and system for compression of images

Life of this patent

Method and system for compression of images

Life of this patent

Abstract

Claims31