# US 7,050,642 B2 · Method and apparatus for video compression using microwavelets

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

- Number: US 7,050,642 B2
- Document ID: US7050642B2
- Status: Granted
- Kind: B2
- Application number: 10/856,606
- Filed: 2004-05-27
- Published: 2004-11-04
- Granted: 2006-05-23
- Earliest claimed: 1994-05-19
- Assignees: NeXT Software, Inc.
- Inventors: Peter N. Graffagnino
- Web page: https://patentgrep.com/patent/US7050642B2

## CPC

- H04N 19/90: using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals
- H04N 19/186: the unit being a colour or a chrominance component
- H04N 19/593: involving spatial prediction techniques
- H04N 19/63: using sub-band based transform, e.g. wavelets
- H04N 19/645: by grouping of coefficients into blocks after the transform
- H04N 19/10: using adaptive coding
- H04N 19/124: Quantisation
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

A method and apparatus are disclosed for symmetrically compressing and decompressing video information in real time by coupling block and wavelet techniques. In the compression pipeline, the image is divided into blocks comprising 2k×2k pixels (in the preferred embodiment, k=1). The average color of each block is computed. The system computes an average luminance for each block and differential luminances of each pixel of the plurality of pixels of each block. A first plurality of frequency details of each block are determined by Haar transforming the differential luminances. The system computes an average color difference between each block and the preceding block, and quantizes the average color difference and the first plurality of frequency details using Lloyd-Max quantization. In an alternate embodiment, skip codes are generated for blocks having the same quantized average color difference and second plurality of frequency details. The quantized average color difference and a second plurality of frequency details are encoded using variable length codes. The system employs lookup tables to decompress the compressed image and to format output pixels. The output of the compression pipeline containing variable length codes is decoded into fixed-length codes, which are then decoded using a first lookup table into three device-independent components that represent each block. The three components index a second lookup table containing precomputed RGB values that include precomputed display dependent formatting to produce the output image. In the alternate embodiment, skip codes contained in the output of the variable length decoder are decoded.

## Claims

### Claim 1

A method for compressing an image of a first color space, wherein said image is divided into a plurality of blocks, comprising the steps of:
computing an average color of a block of said plurality of blocks, said block comprising a plurality of pixels;
computing an average luminance of said block dependent on said average color and a differential luminance of each pixel of said plurality of pixels of said block;
providing a first plurality of frequency details of said block by transforming said differential luminance of each pixel of said plurality of pixels of said block;
computing an average color difference between said block and a previous block;
quantizing said average color difference and said first plurality of frequency details; and
encoding said quantized average color difference and a second plurality of frequency details, wherein said second plurality of frequency details is less than or equal to said first plurality of frequency details.

### Claim 2

A method for compressing image data comprising:
obtaining image data;
obtaining a plurality of data blocks from said image data; and
processing said plurality of data blocks using at least one wavelet method to compress said image data with successive computation results from said plurality of data blocks, wherein processing said plurality of data blocks comprises:
computing an average color of each of said data blocks;
computing an average luminance for each of said data blocks;
computing a differential luminance of each pixel;
computing a first plurality of frequency details of each of said data blocks;
computing an average color difference between each of said data blocks and a preceding data block; and
quantizing said average color difference and said first plurality of frequency details.

### Claim 3 (depends on 2)

The method of claim 2 wherein obtaining said image data comprises obtaining a stream of video data.

### Claim 4 (depends on 2)

The method of claim 2 wherein each of said plurality of data blocks comprises:
a plurality of pixels in an array having a dimension equal to two (2) to the power of “k” pixels, wherein “k” defines an integer number.

### Claim 5 (depends on 4)

The method of claim 4 wherein “k” is one (1).

### Claim 6 (depends on 2)

The method of claim 2 wherein computing said first plurality of frequency details comprises:
using a Haar transform.

### Claim 7 (depends on 2)

The method of claim 2 wherein quantizing said average color difference and said first plurality of frequency details comprises:
using Lloyd-Max quantization.

### Claim 8 (depends on 2)

The method of claim 2 further comprising:
generating skip codes for blocks that are similar with respect to said average color difference and a second plurality of frequency details.

### Claim 9 (depends on 8)

The method of claim 8 further comprising:
using said skip codes in a lookup table.

### Claim 10 (depends on 9)

The method of claim 9 wherein said lookup table is further used for decompressing said image data.

### Claim 11 (depends on 2)

The method of claim 2 further comprising:
using variable length codes to encode said plurality of data blocks.

### Claim 12

A computer program product embodied in a computer readable medium having computer readable program code embodied therein for compressing image data, said computer program product comprising:
program code configured to cause a computer to obtain image data;
program code configured to cause a computer to obtain a plurality of data blocks from said image data; and
program code configured to cause a computer to process said plurality of data blocks using at least one wavelet method to compress said image data with successive computation results from said plurality of data blocks, wherein said program code configured to cause a computer to process said plurality of data blocks comprises:
program code configured to cause a computer to compute an average color of each of said data blocks;
program code configured to cause a computer to compute an average luminance for each of said data blocks;
program code configured to cause a computer to compute a differential luminance of each pixel of said plurality of pixels;
program code configured to cause a computer to compute a first plurality of frequency details of each of said data blocks;
program code configured to cause a computer to compute an average color difference between each of said data blocks and a preceding block; and
program code configured to cause a computer to quantize said average color difference and said first plurality of frequency details.

### Claim 13 (depends on 12)

The computer program product of claim 12 wherein said program code configured to cause a computer to obtain said image data comprises:
program code configured to cause a computer to obtain a stream of video data.

### Claim 14 (depends on 12)

The computer program product of claim 12 wherein each of said plurality of data blocks comprises:
a plurality of pixels in an array having a dimension equal to two (2) to the power of “k” pixels, wherein “k” defines an integer number.

### Claim 15 (depends on 14)

The computer program product of claim 14 wherein “k” is one (1).

### Claim 16 (depends on 12)

The computer program product of claim 12 wherein said program code configured to cause a computer to compute said first plurality of frequency details comprises:
program code configured to cause a computer to use a Haar transform.

### Claim 17 (depends on 12)

The computer program product of claim 12 wherein said program code configured to cause a computer to quantize comprises:
program code configured to cause a computer to use Lloyd-Max quantization.

### Claim 18 (depends on 12)

The computer program product of claim 12 further comprising:
program code configured to cause a computer to generate skip codes for blocks that are similar with respect to said average color difference and a second plurality of frequency details.

### Claim 19 (depends on 18)

The computer program product of claim 18 further comprising:
program code configured to cause a computer to use said skip codes in a lookup table.

### Claim 20 (depends on 19)

The computer program product of claim 19 wherein said lookup table is further used by program code configured to cause a computer to decompress said image data.

### Claim 21 (depends on 12)

The computer program product of claim 12 further comprising:
program code configured to cause a computer to use variable length codes to encode said plurality of data blocks.

### Claim 22

An apparatus for compressing image data comprising:
an image divider configured to receive image data and provide a plurality of data blocks;
an averaging block configured to receive said plurality of data blocks and provide an average color value and an average luminance value for each of said data blocks;
a differential block configured to receive said average color value, said average luminance value and a plurality of luminance values associated with each of said data blocks, said differential block further configured to provide a differential luminance value for each pixel and a differential color value for each of said plurality of data blocks;
a transformation block configured to receive a plurality of said differential luminance values associated with each of said data block and provide frequency-based data;
a quantizer configured to receive said differential color value and said frequency-based data, and provide quantized color and frequency data; and
a variable length encoder configured to receive said quantized color and frequency data, and provide encoded data.

### Claim 23 (depends on 22)

The apparatus of claim 22, further comprising:
a skip code generator configured to receive said quantized color and frequency data and provide a skip code when a block of said quantized color and frequency data is similar to a previous block of said quantized color and frequency data.

### Claim 24 (depends on 22)

The apparatus of claim 22, wherein said quantizer uses Lloyd-Max quantization.

### Claim 25 (depends on 22)

The apparatus of claim 22, wherein said transformation block implements a Haar transform.