US 7,248,744 B2Granted

Vector quantization of images

AssigneeThe University Court of the University of Glasgow

InventorWilliam Paul Cockshott

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method of compressing an image is described in which digital data signals in a 2-dimensional images are formed into an image data pyramid with a number of layers and each layer is processed to give a compressed encoding in an ordered list. The encoding with the largest quality gain factor is selected first and added to a compressed representation of the data array. This is repeated for the next largest gain factor and so on until a predetermined maximum is reached. Each layer of the image data pyramid corresponds to different frequency bands, the vector quantizations of these layers will only minimally interfere with one another. This allows a simple ordering of all possible gain contributions made by the compressed encodings, to the compressed representation. This in turn allows a straightforward selection of the compressed encodings having the largest quality gain factors, for compiling the compressed representation of the image.

Claims10

Dependent claims

A method of compressing an array of data entries, the array representing a two-dimensional image, the method comprising the steps of:

(a) forming an image data pyramid from the array of data entries, said pyramid having a plurality of layers, a first and lowermost layer of said layers comprising said array of data entries, and each subsequent higher layer comprising a data array representing the image using less data, and having smaller dimensions, than the previous layer;
(b) processing each layer of the image data pyramid so as to obtain:
a set of compressed encodings for each layer, wherein each said compressed encoding can be uncompressed to provide an approximation of a block of image data derived from a respective layer of the image data pyramid;
and a respective quality gain factor associated with each said compressed encoding;
(c) creating an ordered list of the compressed encodings, ordered sequentially according to the quality gain factors associated therewith;
(d) selecting the compressed encoding associated with the largest quality gain factor and adding this compressed encoding to a compressed representation of the data array;
(e) selecting the compressed encoding associated with the next largest quality gain factor and adding this compressed encoding to the compressed representation of the original image data array;
and
(f) recursively repeating step (e) for the remaining compressed encodings until the number of bits in the compressed representation reaches a predetermined maximum.

6 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/221,335Filed 6 Mar 2001
Priority: GB 00055158 Mar 2000
Published: US 2004/0096117 A120 May 2004
Granted: 24 Jul 2007
Term ends: Not estimatedThe source records don’t support an estimate.

Classification8 codes

H04N 19/94
Using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals: vector quantisation
H04N 19/129
Characterised by the element, parameter or selection affected or controlled by the adaptive coding: scanning of coding units, e.g. zig-zag scan of…
H04N 19/63
Using transform coding: using sub-band based transform, e.g. wavelets
H04N 19/64
Using sub-band based transform, e.g. wavelets: characterised by ordering of coefficients or of bits for transmission