Image compression method and apparatus employing distortion adaptive tree search vector quantization with avoidance of transmission of redundant image data
First Claim
1. In a Vector quantization encoder of the type that employs a tree structured codebook to vector quantize input vectors and sequentially transmits vector quantized data for input vectors to a remote decoder for reconstructing a substantial representation of each input vector therefrom, the codebook having plural levels of codevectors, each codevector being representative of a possible input vector and there being an identification (ID) code associated with each codevector, the codevectors at each successive level representing possible input vectors with greater accuracy than codevectors at a preceding level, a method comprising the steps of:
- a) comparing a representation of a previous input vector that has already been vector quantized to a current input vector to obtain a first measure of difference between the representation of the previous input vector and the current input vector;
b) transmitting to the decoder an instruction to reconstruct a substantial representation of the current input vector from vector quantized data already stored in the decoder for the previous input vector only when the first measure of difference is less than a threshold value, but otherwise performing the following steps for the current input vector;
c) processing the current input vector and selecting an initial level of the codebook;
d) comparing the processed input vector to the codevectors at the selected level of the codebook and selecting the codevector that most closely resembles the processed input vector;
e) obtaining a second measure of difference between the processed input vector and the selected codevector;
f) transmitting an indication of the ID code associated with the selected codevector only if the second measure of difference is less than the threshold value, but otherwise selecting a next level of the codebook and repeating steps (d) and (e) until either the second measure of difference is less than the threshold value or a last level of the codebook has been employed, then transmitting the indication of the ID code associated with the finally selected codevector, the transmitted indication being the vector quantized data for the current input vector;
wherein vector quantized data for the current input vector need not be transmitted to reconstruct a representation of the current input vector at the decoder when the first measure of difference is less than the threshold value.
3 Assignments
0 Petitions
Accused Products
Abstract
A variable rate vector quantization apparatus and method employs a tree structured codebook. Code vectors are selected from different levels of the codebook according to the value of a threshold. The value of the threshold is periodically adjusted according to the fullness of a buffer that stores vector quantized data to be transmitted. According to the invention, vector quantized data for redundant, or similar, vectors is not transmitted. Rather, a "copy last vector" instruction is transmitted for these vectors to achieve further data compression. A method of mean removal from vectors to be vector quantized is also disclosed.
-
Citations
54 Claims
-
1. In a Vector quantization encoder of the type that employs a tree structured codebook to vector quantize input vectors and sequentially transmits vector quantized data for input vectors to a remote decoder for reconstructing a substantial representation of each input vector therefrom, the codebook having plural levels of codevectors, each codevector being representative of a possible input vector and there being an identification (ID) code associated with each codevector, the codevectors at each successive level representing possible input vectors with greater accuracy than codevectors at a preceding level, a method comprising the steps of:
-
a) comparing a representation of a previous input vector that has already been vector quantized to a current input vector to obtain a first measure of difference between the representation of the previous input vector and the current input vector; b) transmitting to the decoder an instruction to reconstruct a substantial representation of the current input vector from vector quantized data already stored in the decoder for the previous input vector only when the first measure of difference is less than a threshold value, but otherwise performing the following steps for the current input vector; c) processing the current input vector and selecting an initial level of the codebook; d) comparing the processed input vector to the codevectors at the selected level of the codebook and selecting the codevector that most closely resembles the processed input vector; e) obtaining a second measure of difference between the processed input vector and the selected codevector; f) transmitting an indication of the ID code associated with the selected codevector only if the second measure of difference is less than the threshold value, but otherwise selecting a next level of the codebook and repeating steps (d) and (e) until either the second measure of difference is less than the threshold value or a last level of the codebook has been employed, then transmitting the indication of the ID code associated with the finally selected codevector, the transmitted indication being the vector quantized data for the current input vector; wherein vector quantized data for the current input vector need not be transmitted to reconstruct a representation of the current input vector at the decoder when the first measure of difference is less than the threshold value. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 48, 49)
-
-
27. In a vector quantization encoder of the type employing a tree structured codebook having plural levels of codevectors representative of possible input vectors to be processed by the encoder, each input vector being indicative of a block of data, the codebook being stored in a memory and each codevector having an associated memory address, and wherein the encoder transmits vector quantized data for input vectors to a remote decoder and the decoder reconstructs substantial representations of each input vector from the transmitted vector quantized data, a method comprising the steps of:
-
a) providing at the encoder an input vector to be processed; b) determining a mean of the input vector and transmitting data indicative of the mean to the decoder; c) obtaining a first measure of difference between the input vector and the mean, and comparing the first measure of difference to a threshold value; d) performing steps (i) and (ii) below only when the first measure of difference exceeds the threshold value, but otherwise proceeding to step (e); (i) selecting a codevector from the codebook based upon a processed version of the input vector and the threshold value; and
,(ii) transmitting to the decoder data indicative of the address associated with the selected codevector; the data transmitted in step (b) and, when performed, step (d)(ii), being the vector quantized data, the decoder reconstructing a representation of the input vector from the transmitted vector quantized data, e) providing at the encoder another input vector and obtaining a second measure of difference between said another input vector and at least a representation of the input vector provided in step (a), the input vector provided in step (a) defining a previous vector; f) transmitting to the decoder at least an instruction to employ the vector quantized data transmitted for the previous vector to reconstruct a substantial representation of the said another input vector only if the second measure of difference is less than the threshold value, but otherwise performing steps (b) through (d) for said another input vector. - View Dependent Claims (28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39)
-
-
40. A variable rate method for vector quantizing input vectors and transmitting vector quantized data to a remote decoder for reconstruction of substantial representations of each input vector comprising the steps of:
-
a) providing, in a memory, a tree structured codebook;
b) receiving data indicative of an image to be compressed, organizing the image data into blocks, and converting each block to a multi-dimensional input vector;c) determining a scalar mean value of each input vector and interpolating, from the scalar mean values, a mean vector for each input vector; d) selecting an input vector; e) obtaining a first measure difference between the selected input vector and the mean vector for the selected input vector; f) storing in a FIFO buffer only an indication of the scalar mean value of the selected input vector only if the first measure of difference is less than a threshold value then selecting another input vector and returning to step (e), but proceeding to step (g) if the first measure of difference is greater than the threshold; g) constructing a representation of a previous input vector that has already been vector quantized and obtaining a second measure of difference between the selected input vector and the representation of the previous input vector; h) storing in the FIFO buffer both an indication of the scalar mean value of the selected input vector and an instruction to the decoder to reproduce a substantial representation of the selected input vector from vector quantized data already stored in the decoder for the previous input vector only if the second measure of difference is less than the threshold then selecting another input vector and returning to step (e), but proceeding to step (i) if the second measure of difference is greater than the threshold; i) constructing from the selected input vector a secondary vector having a mean at least once removed and defining a residual vector, there being stored in the codebook a plurality of codevectors at a plurality of levels, each codevector being representative of a possible residual vector and each successive level of codevectors representing possible residual vectors in greater detail than a preceding level of codevectors, there being a memory address associated with each codevector; j) selecting an initial level in the codebook; k) comparing the residual vector to the codevectors at the selected level and selecting the codevector that most closely resembles the residual vector; l) obtaining a third measure of difference between the selected codevector and the residual vector, and comparing the third measure of difference to the threshold; m) defining the selected codevector as a finally selected codevector and proceeding directly to step (o) if either the third measure of difference is less than the threshold or a last level of the codebook has been employed, but proceeding to step (n) if the third measure of difference exceeds the threshold; n) selecting the next level in the codebook and repeating steps (k) through (m); o) storing an indication of the address of the finally selected codevector in the FIFO buffer, selecting another input vector, and returning to step (e), at least the address indications having variable length; p) transmitting the indications and instructions stored in the FIFO buffer to the decoder at a fixed data rate; and
,q) maintaining a measure of unused FIFO buffer capacity and periodically adjusting the threshold by automatically increasing the threshold value when the measure of unused FIFO buffer capacity indicates that unused capacity is decreasing and automatically decreasing the threshold value when the measure of unused FIFO buffer capacity indicates that unused capacity is increasing, adjustment of the threshold ensuring that the buffer does not empty or overflow as a result of storing variable length indications but transmitting the same at a fixed data rate, and wherein address indications are not stored in the FIFO buffer or transmitted to the decoder when the first or second measure of difference is less than the threshold. - View Dependent Claims (41, 42, 43, 44)
-
-
45. Data compression apparatus comprising:
-
a) first means for receiving a multi-dimensional vector representative of a block of data to be compressed; b) a tree structured codebook having plural levels of codevectors, each codevector being representative of a possible vector and the codevectors at each successive level representing possible vectors in greater detail than codevectors at a preceding level, each codevector having a unique address associated therewith; c) a controller for selecting one of the codevectors in the codebook based upon the vector and a threshold value according to a distortion adaptive vector quantization technique; d) second means for transmitting data indicative of the address of the selected codevector; and
,e) third means for obtaining a measure of difference between the vector received by the first means and a representation of a previous vector and for providing, based upon the measure of difference and the threshold value, an indication to a remote vector quantization decoder that the vector received by the first means is substantially similar to the previous vector and may be copied therefrom.
-
-
46. In a vector quantization encoder of the type employing a tree structured codebook having plural levels of codevectors representative of possible input vectors to be processed by the encoder, each input vector being indicative of a block of data, the codebook being stored in a memory and each codevector having an associated memory address, and wherein the encoder transmits vector quantized data for input vectors to a remote decoder and the decoder reconstructs substantial representations of each input vector from the transmitted vector quantized data, a method comprising the steps of:
-
a) providing at the encoder an input vector to be processed; b) determining a mean of the input vector and transmitting data indicative of the mean to the decoder; c) obtaining a first measure of difference between the input vector and the mean, and comparing the first measure of difference to a threshold value; d) performing steps (i) and (ii) below only when the first measure of difference exceeds the threshold value, but otherwise proceeding to step (e); (i) selecting a codevector from the codebook based upon a processed version of the input vector and the threshold value; and
,(ii) transmitting to the decoder data indicative of the address associated with the selected codevector; the data transmitted in step (b) and, when performed, step (d)(ii), being the vector quantized data, the decoder reconstructing a representation of the input vector from the transmitted vector quantized data, e) providing at the encoder another input vector, determining the mean of said other input vector and performing at least steps (c) and d(i) for said other input vector to obtain a codebook address for said other input vector; f) comparing the address for said other input vector to the address for the input vector provided in step (a) and transmitting to the decoder an instruction to substantially copy the input vector reconstructed from the vector quantized data transmitted in step (b) and, when performed, step (d)(i), to reconstruct a representation of said other input vector if the addresses are substantially identical but otherwise performing the following steps; g) obtaining a second measure of difference between said other input vector and the input vector provided in step (a); h) transmitting to the decoder an instruction to substantially copy the input vector reconstructed from the vector quantized data transmitted in step (b) and, when performed, step (d)(ii), to reconstruct a representation of said other input vector only if the second measure of difference is less than the threshold value, but otherwise transmitting the vector quantized data for said other input vector.
-
-
47. Data compression apparatus comprising:
-
a) first means for receiving a multi-dimensional vector representative of a block of data to be compressed; b) a tree structured codebook having plural levels of codevectors, each codevector being representative of a possible vector and the codevectors at each successive level representing possible vectors in greater detail than codevectors at a preceding level, each codevector having a unique address associated therewith; c) a controller for selecting one of the codevectors in the codebook based upon the vector and a threshold value according to a distortion adaptive vector quantization technique;
d) second means for transmitting data indicative of the address of the selected codevector; and
,e) third means for comparing an address associated with a previous vector received by the first means to an address associated with a current vector received by the first means and, when the addresses are substantially identical, for providing an indication that the current vector is substantially similar to the previous vector and may be copied therefrom, but when the addresses are not substantially identical, for obtaining a measure of difference between the current vector and the previous vector and for providing, when the measure of difference is less than the threshold value, an indication that the current vector is substantially similar to the previous vector and may be copied therefrom.
-
-
50. A decoder for use at a reception site of vector quantization data, wherein the vector quantization data originates from an encoding site employing a tree search vector quantization data compressor for compressing digital data indicative of at least intensity values of pixels of images to be transmitted to recipients by converting input vectors indicative of a block of pixels to addresses of a first codebook in the compressor, the first codebook having plural levels of codevectors representative of possible input vectors and each successive level representing codevectors with a greater accuracy than a preceding level of codevectors, the encoding site transmitting, for each input vector, data indicative of a mean of at least selected ones of the input vectors and one of either (i) data indicative of an address of the codevector found to most closely approximate each input vector or, (ii) an instruction to copy a representation of a previous input vector, the decoder comprising:
-
a) a second codebook being substantially identical in content to the first codebook; b) a memory for storing at least the means and address data transmitted by the encoder for at least a current and a previous frame of image data; c) a controller for retrieving codevectors from the second codebook based upon the address data stored in the memory, the controller being responsive to each received instruction to employ address data for the previous frame stored in the memory to retrieve a codevector, defining a previous frame codevector, from the second codebook and to employ the previous frame codevector as a representation of an input vector in the current frame, but the controller, in selected instances, otherwise employing address data for the current frame to retrieve a codevector from the second codebook to obtain a representation of the input vector; d) at least one converter for converting each codevector to NTSC format image data and for providing the NTSC format image data at an output thereof for substantially reproducing an image that was input to the encoding site. - View Dependent Claims (51, 52, 53, 54)
-
Specification