# US 2005/0232501 A1 · Predictive lossless coding of images and video

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

- Number: US 2005/0232501 A1
- Document ID: US20050232501A1
- Status: Published application
- Kind: A1
- Application number: 10/826,842
- Filed: 2004-04-15
- Published: 2005-10-20
- Earliest claimed: 2004-04-15
- Assignees: Microsoft Corporation
- Inventors: Kunal Mukerjee
- Web page: https://patentgrep.com/patent/US20050232501A1

## CPC

- H04N 19/14: Coding unit complexity, e.g. amount of activity or edge presence estimation (H04N19/146 takes precedence)
- 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/13: Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
- H04N 19/176: the region being a block, e.g. a macroblock
- H04N 19/46: Embedding additional information in the video signal during the compression process (H04N19/517, H04N19/68, H04N19/70 take precedence)
- H04N 19/593: involving spatial prediction techniques
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

Predictive lossless coding provides effective lossless image compression of both photographic and graphics content in image and video media. Predictive lossless coding can operate on a macroblock basis for compatibility with existing image and video codecs. Predictive lossless coding chooses and applies one of multiple available differential pulse-code modulation (DPCM) modes to individual macro-blocks to produce DPCM residuals having a closer to optimal distribution for run-length, Golomb Rice RLGR entropy encoding. This permits effective lossless entropy encoding despite the differing characteristics of photographic and graphics image content.

## Claims

### Claim 1

A method for lossless coding of image and video media, comprising:
splitting input image data into block portions;
for an individual one of the block portions, selecting one of multiple available differential pulse code modulation (DPCM) prediction modes to apply to the block portion that out of the available DPCM prediction modes yields a closer to optimal symbol distribution of an entropy encoder;
applying the selected DPCM prediction mode to the block portion; and
entropy encoding DPCM residuals of the block portion.

### Claim 2 (depends on 1)

The method of claim 1 further comprising:
converting the input image data into a YCoCg color space format.

### Claim 3 (depends on 1)

The method of claim 1 wherein the entropy encoding is run-length, Golomb-Rice coding.

### Claim 4 (depends on 1)

The method of claim 1 further comprising encoding the DPCM prediction mode selected for the block portion using run-length, Golomb-Rice coding.

### Claim 5 (depends on 1)

The method of claim 1 further comprising encoding the DPCM prediction mode and DPCM residuals with separate run-length, Golomb-Rice coding contexts.

### Claim 6 (depends on 1)

The method of claim 1 further comprising:
determining whether application of the selected DPCM prediction mode to the block portion produces all zero valued DPCM residuals; and
encoding an indication that the block portion is flat instead of entropy encoding DPCM residuals of the block portion.

### Claim 7 (depends on 1)

The method of claim 1 wherein the selecting the DPCM prediction mode comprises:
determining whether the DPCM prediction mode yielding the closer to optimal symbol distribution for entropy coding is sufficiently close to the optimal symbol distribution for entropy coding; and
if not sufficiently close, applying no DPCM to the macro-block before the entropy encoding.

### Claim 8 (depends on 1)

The method of claim 1 wherein the DPCM prediction modes comprise modes designed to produce an optimal distribution for entropy coding for block portions whose image content is predominantly a horizontal major edge, a vertical major edge, ramp diagonal edges, bands, and banded horizontal ramps.

### Claim 9 (depends on 1)

The method of claim 1 wherein the DPCM prediction modes comprise:
a first mode in which a pixel's value is subtracted from its left neighboring pixel;
a second mode in which a pixel's value is subtracted from its top neighboring pixel;
a third mode in which a pixel's value is subtracted from a minimum or maximum of its left and top neighboring pixels;
a fourth mode in which a pixel's value is subtracted from an average of its top and top right neighboring pixels;
a fifth mode in which a pixel's value is subtracted from its top-left neighboring pixel;
a sixth mode in which the difference between a pixel's top and top-left neighboring pixels is subtracted from its left neighboring pixel; and
a seventh mode in which a pixel's value is subtracted from an average of the pixel's left and top neighboring pixels.

### Claim 10

A media system providing predictive lossless coding of image or video media content, the system comprising:
a macro-block division process for separating input image data into macro-blocks;
a multi-mode differential pulse code modulation (DPCM) process operating on an individual macro-block of the input image data to choose one of multiple DPCM prediction modes that produces a residual distribution for the macro-block to more closely match an optimal run-length, Golomb-Rice (RLGR) entropy coding distribution, and applies the chosen DPCM prediction mode to the macro-block; and
an entropy coding process for performing a run-length, Golomb-Rice coding of the DPCM residuals of the macro-block.

### Claim 11 (depends on 10)

The media system of claim 10 further comprising a color space conversion process for converting the input image data prior to a YCoCg color space format prior to coding.

### Claim 12 (depends on 10)

The media system of claim 10 wherein the DPCM prediction modes comprise modes designed to produce distributions close to the optimal RLGR entropy coding distribution for macro-blocks whose image content is predominantly a horizontal major edge, a vertical major edge, ramp diagonal edges, bands, and banded horizontal ramps.

### Claim 13 (depends on 10)

The media system of claim 10 wherein the DPCM prediction modes comprise:
a first mode in which a pixel's value is subtracted from its left neighboring pixel;
a second mode in which a pixel's value is subtracted from its top neighboring pixel;
a third mode in which a pixel's value is subtracted from a minimum or maximum of its left and top neighboring pixels;
a fourth mode in which a pixel's value is subtracted from an average of its top and top right neighboring pixels;
a fifth mode in which a pixel's value is subtracted from its top-left neighboring pixel;
a sixth mode in which the difference between a pixel's top and top-left neighboring pixels is subtracted from its left neighboring pixel; and
a seventh mode in which a pixel's value is subtracted from an average of the pixel's left and top neighboring pixels.

### Claim 14

A computer-readable storage medium having computer-executable program instructions stored thereon for operative upon execution in computer media processing system to perform a method of encoding image or video data, the method comprising:
converting image data to a YCoCg color space format;
splitting the image data into macro-blocks;
for a macro-block of the image data, determining which from a group of available DPCM prediction modes produces residuals closest to an optimal distribution for RLGR coding;
if such determined DPCM prediction mode produces residuals whose distribution is sufficiently close to the optimal distribution, applying the DPCM prediction mode to the macro-block; and
RLGR entropy encoding the residuals of the macro-block.

### Claim 15 (depends on 14)

The computer-readable storage medium of claim 14 wherein the method further comprises:
determining whether application of the determined DPCM prediction mode to the macro-block produces flat residuals; and
if so, encoding the macro-block as a flat macro-block mode indication without the RLGR entropy encoding the residuals of such flat macro-block.

### Claim 16 (depends on 15)

The computer-readable storage medium of claim 15 wherein the method further comprises:
RLGR entropy encoding the macro-block mode indication using a separate RLGR coding context than for RLGR entropy encoding the residuals.

### Claim 17 (depends on 15)

The computer-readable storage medium of claim 15 wherein the method further comprises:
determining whether the DPCM prediction mode producing a residual distribution closest to the optimal distribution produces a residual distribution sufficiently close to the optimal distribution; and
if not sufficiently close, RLGR entropy encoding the macro-block without applying the DPCM prediction mode to the macro-block.

### Claim 18

A method of decoding predictive losslessly coded data of an image or video, comprising:
RLGR entropy decoding a macro-block mode, a DPCM prediction mode and DPCM residuals for each of a plurality of macro-blocks using separate RLGR coding contexts;
where the macro-block mode of a macro-block is a flat macro-block mode, decoding the macro-block's pixels using a DPCM demodulation that is an inverse of the RLGR-decoded DPCM prediction mode of all zero residuals;
otherwise, where the DPCM prediction mode of the macro-block is a no DPCM prediction mode, decoding the macro-block's pixels without DPCM demodulation;
otherwise, de-modulating the RLGR-decoded DPCM residuals using a DPCM demodulation that is an inverse of the RLGR-decoded DPCM prediction mode; and
assembling the macro-blocks to form a decoded image data.

### Claim 19 (depends on 18)

The method of claim 18 comprising:
converting the decoded image data from a YCoCg color space format to a displayable color space format.

### Claim 20

A predictive-lossless coded image or video decoder, comprising:
a run-length Golomb-Rice (RLGR) entropy decoder operating to decode RLGR-encoded DPCM residuals and DPCM prediction mode of a macro-block;
a DPCM demodulator for applying an inverse of the DPCM prediction mode to the DPCM residuals; and
a macro-block reassembler for assembling the macro-block with other decoded macro-blocks to form data of a reconstructed image.

### Claim 21 (depends on 20)

The predictive-lossless coded image or video decoder of claim 20, comprising:
an inverse YCoCg converter for converting the reconstructed image from a YCoCg color space to a color space suited for displaying the image.
