# US 2015/0146975 A1 · Lossless color image compression adaptively using spatial prediction or inter-component prediction

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0146975 A1
- Document ID: US20150146975A1
- Status: Published application
- Kind: A1
- Application number: 14/236,290
- Filed: 2013-03-15
- Published: 2015-05-28
- Earliest claimed: 2013-03-15
- Assignees: EMC Corporation
- Applicants: EMC Corporation
- Inventors: Alexey Valentinovich Romanovskiy; Marat Ravilevich Gilmutdinov; Nikolay Dmitrievich Egorov; Victor Anatolievich Yastrebov; Dmitry Vadimovich Novikov; Roman Alexandrovich Sokolovskiy
- Web page: https://patentgrep.com/patent/US20150146975A1

## CPC

- H04N 19/103: Selection of coding mode or of prediction mode
- H04N 19/105: Selection of the reference unit for prediction within a chosen coding or prediction mode, e.g. adaptive choice of position and number of pixels used for prediction
- H04N 19/136: Incoming video signal characteristics or properties
- H04N 19/154: Measured or subjectively estimated visual quality after decoding, e.g. measurement of distortion (use of rate-distortion criteria H04N19/147)
- H04N 19/182: the unit being a pixel
- H04N 19/186: the unit being a colour or a chrominance component
- H04N 19/593: involving spatial prediction techniques
- H04N 19/14: Coding unit complexity, e.g. amount of activity or edge presence estimation (H04N19/146 takes precedence)
- H04N 19/91: Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
- H04N 19/93: Run-length coding
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

An improved lossless image compression technique involves adaptively selecting between spatial prediction and inter-component prediction techniques depending on which allows better results for any given component of a digital image pixel.

## Claims

### Claim 1

A method performed by a computing device, the method comprising:
receiving an image file, the image file having a set of pixels arranged in a grid, each pixel of the set of pixels having a plurality of color components;
for each pixel of a subset of the set of pixels:
for a first color component of the plurality of color components:
predicting a value of the first color component of that pixel using a first prediction technique to yield a first predicted color value, the first prediction technique including median edge detection; and
computing a difference between the first predicted color value and the value of the first color component to yield a first error value for that pixel;
for a second color component of the plurality of color components, the second color component being distinct from the first color component:
predicting a value of the second color component of that pixel using the first prediction technique to yield a second predicted color value;
predicting the value of the second color component of that pixel using a second prediction technique to yield a third predicted color value, the second prediction technique lacking median edge detection, the second prediction technique utilizing inter-component prediction with respect to the first color component;
selecting whichever of the second predicted color value and the third predicted color value is closer to the value of the second color component to yield a selected predicted color value; and
computing a difference between the selected predicted color value and the value of the second color component to yield a second error value for that pixel; and
encoding the first error value for that pixel and the second error value for that pixel in a compressed color image output stream; and
writing the compressed color image output stream to persistent storage as an output compressed image file.

### Claim 2 (depends on 1)

The method of claim 1 wherein the method further comprises, for each pixel of the subset of the set of pixels:
for a third color component of the plurality of color components, the third color component being distinct from the first color component and the second color component:
predicting a value of the third color component of that pixel using the first prediction technique to yield a fourth predicted color value;
predicting the value of the third color component of that pixel using the second prediction technique to yield a fifth predicted color value, the second prediction technique utilizing inter-component prediction with respect to the first color component;
predicting the value of the third color component of that pixel using the second prediction technique to yield a sixth predicted color value, the second prediction technique utilizing inter-component prediction with respect to the second color component;
estimating an error for the fifth predicted color value based on a sum of first color component error values for a set of pixels adjacent to that pixel, the sum being weighted according to a Euclidian distance of each adjacent pixel from that pixel;
estimating an error for the sixth predicted color value based on a sum of second color component error values for the set of pixels adjacent to that pixel, the sum being weighted according to the Euclidian distance of each adjacent pixel from that pixel;
computing a weighted average of the fifth predicted color value and the sixth predicted color value, the fifth predicted color value being weighted by the estimated error for the sixth predicted color value and the sixth predicted color value being weighted by the estimated error for the fifth predicted color value, to yield an average color value;
selecting whichever of the fourth predicted color value and the average color value is closer to the value of the third color component to yield another selected predicted color value; and
computing a difference between the other selected predicted color value and the value of the third color component to yield a third error value for that pixel; and
encoding the third error value for that pixel in the compressed color image output stream.

### Claim 3 (depends on 2)

The method of claim 2 wherein predicting the value of the third color component of that pixel using the second prediction technique to yield the fifth predicted color value includes:
computing a first difference between a third color component of a pixel immediately to the left of that pixel and a third color component of a pixel immediately diagonally above and to the left of that pixel;
computing a second difference between a first color component of the pixel immediately to the left of that pixel and a first color component of the pixel immediately diagonally above and to the left of that pixel;
computing a third difference between the first difference and the second difference;
computing a fourth difference between a third color component of a pixel immediately above that pixel and the third color component of the pixel immediately diagonally above and to the left of that pixel;
computing a fifth difference between a first color component of the pixel immediately above that pixel and the first color component of the pixel immediately diagonally above and to the left of that pixel;
computing a sixth difference between the fourth difference and the fifth difference;
computing a seventh difference between the first color component of that pixel and the first color component of the pixel immediately diagonally above and to the left of that pixel;
if the third difference and the sixth difference are both greater than zero or both less than zero, then setting the fifth predicted color value to be a sum of:
the third color component of the pixel immediately diagonally above and to the left of that pixel;
the seventh difference; and
an absolute value of whichever of the third difference and the sixth difference has a larger absolute value; and
otherwise, setting the third predicted color value to be a sum of:
the third color component of the pixel immediately diagonally above and to the left of that pixel;
the seventh difference; and
the third difference; and
the sixth difference.

### Claim 4 (depends on 3)

The method of claim 3 wherein predicting the value of the third color component of that pixel using the second prediction technique to yield the sixth predicted color value includes:
computing an eighth difference between a second color component of the pixel immediately to the left of that pixel and a second color component of the pixel immediately diagonally above and to the left of that pixel;
computing a ninth difference between the first difference and the eighth difference;
computing a tenth difference between a second color component of the pixel immediately above that pixel and the second color component of the pixel immediately diagonally above and to the left of that pixel;
computing an eleventh difference between the fourth difference and the tenth difference;
computing a twelfth difference between the second color component of that pixel and the second color component of the pixel immediately diagonally above and to the left of that pixel;
if the ninth difference and the eleventh difference are both greater than zero or both less than zero, then setting the sixth predicted color value to be a sum of:
the third color component of the pixel immediately diagonally above and to the left of that pixel;
the twelfth difference; and
an absolute value of whichever of the ninth difference and the eleventh difference has a larger absolute value; and
otherwise, setting the sixth predicted color value to be a sum of:
the third color component of the pixel immediately diagonally above and to the left of that pixel;
the twelfth difference; and
the ninth difference; and
the eleventh difference.

### Claim 5 (depends on 2)

The method of claim 2 wherein:
the first color component is a green component;
the second color component is a red component; and
the third color component is a blue component.

### Claim 6 (depends on 1)

The method of claim 1 wherein predicting the value of the second color component of that pixel using the second prediction technique to yield the third predicted color value includes:
computing a first difference between a second color component of a pixel immediately to the left of that pixel and a second color component of a pixel immediately diagonally above and to the left of that pixel;
computing a second difference between a first color component of the pixel immediately to the left of that pixel and a first color component of the pixel immediately diagonally above and to the left of that pixel;
computing a third difference between the first difference and the second difference;
computing a fourth difference between a second color component of a pixel immediately above that pixel and the second color component of the pixel immediately diagonally above and to the left of that pixel;
computing a fifth difference between a first color component of the pixel immediately above that pixel and the first color component of the pixel immediately diagonally above and to the left of that pixel;
computing a sixth difference between the fourth difference and the fifth difference;
computing a seventh difference between the first color component of that pixel and the first color component of the pixel immediately diagonally above and to the left of that pixel;
if the third difference and the sixth difference are both greater than zero or both less than zero, then setting the third predicted color value to be a sum of:
the second color component of the pixel immediately diagonally above and to the left of that pixel;
the seventh difference; and
an absolute value of whichever of the third difference and the sixth difference has a larger absolute value; and
otherwise, setting the third predicted color value to be a sum of:
the second color component of the pixel immediately diagonally above and to the left of that pixel;
the seventh difference; and
the third difference; and
the sixth difference.

### Claim 7 (depends on 1)

The method of claim 1 wherein predicting the value of the first color component of that pixel using the first prediction technique to yield the first predicted color value includes:
(a) setting a spatial preliminary predicted value by:
if a maximum of a first color component of a pixel immediately to the left of that pixel and a first color component of a pixel immediately above that pixel does not exceed a first color component of a pixel immediately diagonally above and to the left of that pixel, then setting the spatial preliminary predicted value to a minimum of the first color component of the pixel immediately to the left of that pixel and the first color component of the pixel immediately above that pixel;
otherwise, if the first color component of the pixel immediately diagonally above and to the left of that pixel does not exceed the minimum of the first color component of the pixel immediately to the left of that pixel and the first color component of the pixel immediately above that pixel, then setting the spatial preliminary predicted value to a maximum of the first color component of the pixel immediately to the left of that pixel and the first color component of the pixel immediately above that pixel; and
otherwise, setting the spatial preliminary predicted value to the first color component of the pixel immediately to the left of that pixel plus the first color component of the pixel immediately above that pixel minus the first color component of the pixel immediately diagonally above and to the left of that pixel;
(b) setting a left preliminary predicted value by:
computing a first difference between a first color component of a pixel immediately to the left of that pixel and a first color component of a pixel immediately diagonally above and to the left of that pixel;
computing a second difference between a first color component of a pixel two pixels to the left of that pixel and a first color component of a pixel immediately to the left of the pixel immediately diagonally above and to the left of that pixel;
computing a third difference between the first difference and the second difference;
computing a fourth difference between a first color component of a pixel immediately above that pixel and the first color component of the pixel immediately diagonally above and to the left of that pixel;
computing a fifth difference between the first color component of the pixel immediately diagonally above and to the left of that pixel and the first color component of the pixel immediately to the left of the pixel immediately diagonally above and to the left of that pixel;
computing a sixth difference between the fourth difference and the fifth difference;
computing a seventh difference between the first color component of the pixel immediately to the left of that pixel and the first color component of the pixel immediately to the left of the pixel immediately diagonally above and to the left of that pixel;
if the third difference and the sixth difference are both greater than zero or both less than zero, then setting the left preliminary predicted color value to be a sum of:
the first color component of the pixel immediately diagonally above and to the left of that pixel;
the seventh difference; and
an absolute value of whichever of the third difference and the sixth difference has a larger absolute value; and
otherwise, setting the left preliminary predicted color value to be a sum of:
the first color component of the pixel immediately diagonally above and to the left of that pixel;
the seventh difference; and
the third difference; and
the sixth difference;
(c) setting a top preliminary predicted value by:
computing an eighth difference between the first color component of the pixel immediately diagonally above and to the left of that pixel and a first color component of a pixel immediately above the pixel immediately diagonally above and to the left of that pixel;
computing a ninth difference between the first difference and the eighth difference;
computing a tenth difference between a first color component of a first color component of a pixel two pixels above that pixel and the first color component of the pixel immediately above the pixel immediately diagonally above and to the left of that pixel;
computing an eleventh difference between the fourth difference and the tenth difference;
computing a twelfth difference between the first color component of the pixel immediately above that pixel and the first color component of the pixel immediately above the pixel immediately diagonally above and to the left of that pixel;
if the ninth difference and the eleventh difference are both greater than zero or both less than zero, then setting the top preliminary predicted color value to be a sum of:
the first color component of the pixel immediately diagonally above and to the left of that pixel;
the twelfth difference; and
an absolute value of whichever of the ninth difference and the eleventh difference has a larger absolute value; and
otherwise, setting the top preliminary predicted color value to be a sum of:
the first color component of the pixel immediately diagonally above and to the left of that pixel;
the twelfth difference; and
the ninth difference; and
the eleventh difference;
(d) setting a final preliminary predicted value by:
if the spatial preliminary predicted value is between the left preliminary predicted value and the top preliminary predicted value, then setting the final preliminary predicted value to be the spatial preliminary predicted value; and
otherwise, setting the final preliminary predicted value to whichever of the left preliminary predicted value and the top preliminary predicted value is closer in value to the spatial preliminary predicted value; and
(e) setting the first predicted color value by:
estimating an error for the spatial preliminary predicted value based on a sum of spatial preliminary predicted value error values for a set of pixels adjacent to that pixel, the sum being weighted according to a Euclidian distance of each adjacent pixel from that pixel;
estimating an error for the final preliminary predicted value based on a sum of final preliminary predicted value error values for the set of pixels adjacent to that pixel, the sum being weighted according to the Euclidian distance of each adjacent pixel from that pixel; and
computing a weighted average of the spatial preliminary predicted value and the final preliminary predicted value, the spatial preliminary predicted value being weighted by the estimated error for the final preliminary predicted value and the final preliminary predicted value being weighted by the estimated error for the spatial preliminary predicted value, to yield the first predicted color value.

### Claim 8 (depends on 1)

The method of claim 1 wherein encoding includes employing arithmetic coding.

### Claim 9 (depends on 1)

The method of claim 1 wherein encoding includes employing variable length coding.

### Claim 10 (depends on 1)

The method of claim 1 wherein encoding includes employing 2-dimensional run coding.

### Claim 11 (depends on 10)

The method of claim 10 wherein employing 2-dimensional run coding includes encoding adaptively-sized square blocks of pixels which all have zero first error values as single entries.

### Claim 12 (depends on 1)

The method of claim 1 wherein encoding includes employing context modeling.

### Claim 13

A data storage apparatus comprising:
a host interface;
memory;
persistent storage; and
a processor, the processor being configured to perform the operations of:
receiving an image file into memory from the host interface, the image file having a set of pixels arranged in a grid, each pixel of the set of pixels having a plurality of color components;
for each pixel of a subset of the set of pixels:
for a first color component of the plurality of color components:
predicting a value of the first color component of that pixel using a first prediction technique to yield a first predicted color value, the first prediction technique including median edge detection; and
computing a difference between the first predicted color value and the value of the first color component to yield a first error value for that pixel;
for a second color component of the plurality of color components, the second color component being distinct from the first color component:
predicting a value of the second color component of that pixel using the first prediction technique to yield a second predicted color value;
predicting the value of the second color component of that pixel using a second prediction technique to yield a third predicted color value, the second prediction technique lacking median edge detection, the second prediction technique utilizing inter-component prediction with respect to the first color component;
selecting whichever of the second predicted color value and the third predicted color value is closer to the value of the second color component to yield a selected predicted color value; and
computing a difference between the selected predicted color value and the value of the second color component to yield a second error value for that pixel; and
encoding the first error value for that pixel and the second error value for that pixel in a compressed color image output stream; and
writing the compressed color image output stream to the persistent storage as output compressed image file.

### Claim 14

A computer program product comprising a non-transitory computer-readable storage medium storing a set of instruction, which, when executed by a computer, cause the computer to perform the following operations:
receiving an image file, the image file having a set of pixels arranged in a grid, each pixel of the set of pixels having a plurality of color components;
for each pixel of a subset of the set of pixels:
for a first color component of the plurality of color components:
predicting a value of the first color component of that pixel using a first prediction technique to yield a first predicted color value, the first prediction technique including median edge detection; and
computing a difference between the first predicted color value and the value of the first color component to yield a first error value for that pixel;
for a second color component of the plurality of color components, the second color component being distinct from the first color component:
predicting a value of the second color component of that pixel using the first prediction technique to yield a second predicted color value;
predicting the value of the second color component of that pixel using a second prediction technique to yield a third predicted color value, the second prediction technique lacking median edge detection, the second prediction technique utilizing inter-component prediction with respect to the first color component;
selecting whichever of the second predicted color value and the third predicted color value is closer to the value of the second color component to yield a selected predicted color value; and
computing a difference between the selected predicted color value and the value of the second color component to yield a second error value for that pixel; and
encoding the first error value for that pixel and the second error value for that pixel in a compressed color image output stream; and
writing the compressed color image output stream to persistent storage as an output compressed image file.