Image compression method and apparatus employing distortion adaptive tree search vector quantization
First Claim
Patent Images
1. In a vector quantization data compression system employing a tree search vector quantization codebook having plural levels of codevectors representative of possible input vectors to be processed by the system, each input vector being indicative of a block of data to be compressed, each codevector having an associated identification (ID) code, a method comprising the steps of:
- a) receiving an input vector and determining a mean value of the received input vector;
b) transmitting data indicative of the mean value;
c) determining a difference value indicative of a difference between the input vector and the mean value, and comparing the difference value to a threshold value;
d) performing the following additional steps when the difference value exceeds the threshold value;
(i) selecting a codevector from the codebook based upon a processed version of the input vector and the threshold value; and
,ii) transmitting data indicative of the ID code associated with the selected codevector.
1 Assignment
0 Petitions
Accused Products
Abstract
A variable rate vector quantization method employs a tree structured codebook. The level of the codebook from which codevectors are selected is determined by a threshold. The threshold varies according to the fullness of a buffer which stores vector quantized data to be transmitted.
-
Citations
82 Claims
-
1. In a vector quantization data compression system employing a tree search vector quantization codebook having plural levels of codevectors representative of possible input vectors to be processed by the system, each input vector being indicative of a block of data to be compressed, each codevector having an associated identification (ID) code, a method comprising the steps of:
-
a) receiving an input vector and determining a mean value of the received input vector; b) transmitting data indicative of the mean value; c) determining a difference value indicative of a difference between the input vector and the mean value, and comparing the difference value to a threshold value; d) performing the following additional steps when the difference value exceeds the threshold value; (i) selecting a codevector from the codebook based upon a processed version of the input vector and the threshold value; and
,ii) transmitting data indicative of the ID code associated with the selected codevector. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 77, 78)
-
-
11. In a tree search, variable rate vector quantization data compression system of the type that converts a block of input data to a multi-dimensional input vector, and having a codebook with plural levels of codevectors, each codevector being representative of a possible input vector for converting each input vector to 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) processing the input vector and selecting an initial level of the codebook; b) comparing the processed vector to the codevectors at the selected level of the codebook and selecting the codevector that most closely resembles the processed vector; c) obtaining a measure of difference, if any, between the processed vector and the selected codevector; d) transmitting an indication of the ID code associated with the selected codevector only if the measure of difference is less than a threshold value, but otherwise selecting a next level of the codebook and repeating steps (b) and (c) until either the measure of difference is less than the threshold value or a last level of the codebook is reached, then transmitting the indication, each ID code having a length that, on average, is shorter than a length of its associated codevector. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 79)
-
-
31. In a data compression system of the type converting input data to multi-dimensional input vectors each representing a block of data, a method comprising:
-
a) determining a mean value of each input vector and, transmitting data indicative of the mean value; b) providing, in a memory, a tree-search vector quantization codebook having plural levels of codevectors, there being a residual vector defined by each input vector, each codevector being representative of a possible residual vector and each successive level of codevectors representing possible residual vectors with greater accuracy than a preceding level of codevectors, there being a memory address associated with each codevector; c) obtaining a measure of difference between the mean value and the input vector and comparing the measure of difference to a threshold value and performing the following additional steps only if the measure of difference exceeds the threshold value; d) removing the mean value from the vector to obtain the residual vector defined by the input vector and selecting an initial level in the codebook; e) comparing the residual vector to the codevectors at the selected level and selecting the codevector at the selected level that most closely resembles the residual vector; f) calculating a distortion value representative of a difference, if any, between the selected codevector and the residual vector, and comparing the distortion value to the threshold value; g) selecting the next level in the codebook if the distortion value exceeds the threshold value and repeating steps (e) and (f) until either (1) the distortion value does not exceed the threshold value, or (2) a last level of the codebook has been reached, to obtain a finally selected codevector; and
,h) transmitting an indication of at least the address associated with the finally selected codevector, each transmitted indication having a length that is on average shorter than a length of the finally selected codevector. - View Dependent Claims (32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51)
-
-
52. Variable rate vector quantization data compression method comprising the steps of:
-
a) 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; b) determining a mean value of the input vector; c) assigning a compression code to the mean value according to a lossless compression technique and storing the compression code in a first-in first-out (FIFO) buffer; d) providing, in a memory, a tree-search vector quantization codebook having plural levels of codevectors, there being a residual vector defined by each input vector, each codevector being representative of a possible residual vector and each successive level of codevectors representing the possible residual vectors in greater detail than a preceding level of codevectors, there being a memory address associated with each codevector; e) assigning a compression code to each possible address, each compression code having a length that is substantially inversely proportional to a predetermined likelihood that the codevector associated with the address corresponding to the compression code will be selected; f) obtaining a measure of difference between the input vector and the mean value and comparing the measure of difference to a threshold value and performing steps (f1) through (f5) below only if the measure of difference exceeds the threshold value; f1) removing the mean value from the input vector to obtain the residual vector defined by the input vector and selecting an initial level in the codebook; f2) comparing the residual vector to the codevectors at the selected level and selecting the codevector that most closely resembles the residual vector; f3) obtaining a measure of difference, if any, between the selected codevector and the residual vector, and comparing the measure of difference between the selected codevector and the residual vector to the threshold value; f4) selecting the next level in the codebook if the measure of difference obtained in step (f3) exceeds the threshold value; f5) repeating steps (f1) through (f4) until either (1) the measure of difference does not exceed the threshold value, or (2) a last level of the codebook has been reached, to obtain a finally selected codevector and storing the compression code for the address of the finally selected codevector in the FIFO buffer; g) repeating steps (b) through (f) for each new input vector while sequentially transmitting each compression code stored in the FIFO buffer at a fixed data rate; and
,h) maintaining a measure of unused FIFO buffer capacity and periodically adjusting the threshold value 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 value ensuring that the buffer does not empty or overflow as a result of storing variable length compression codes but transmitting the same at a fixed data rate. - View Dependent Claims (53, 54, 55, 56, 57, 58, 59, 60, 80)
-
-
61. In a cable television system, a method of communicating temporally spaced image frames representing moving images to be displayed on a subscriber set, each image frame comprising a matrix of pixels and each pixel within each image frame having at least an associated intensity value, the method comprising the steps of:
-
a) digitizing the intensity values for the pixels within each image frame and formatting the digital intensity values corresponding to a rectangular block of pixels within the image frame to a multi-dimensional input vector; b) processing the input vector; c) providing, in a memory located at a transmitter location of cable television signals, a first tree-search vector quantization codebook having plural levels of codevectors each representative of a possible processed vector for converting each processed vector to a memory address associated with each codevector, the codevectors at each successive level representing possible processed vectors in greater detail than codevectors at a preceding level; d) selecting an initial level in the codebook; e) comparing each processed vector to the codevectors at the selected level and selecting the codevector at the selected level that most closely resembles the processed vector; f) calculating a measure of difference, if any, between the selected codevector and the processed vector, and comparing the measure of difference to a threshold value; g) selecting the next level in the codebook if the measure of difference exceeds the threshold value and repeating steps (e) and (f) until either (1) the measure of difference does not exceed the threshold value, or (2) a last level of the codebook has been reached, to obtain a finally selected codevector; h) temporarily storing indications of at least addresses associated with finally selected codevectors, the indications having lengths that are variable and on average shorter than lengths of the finally selected codevectors; i) serially transmitting the stored indications at a substantially fixed data rate; and
,j) automatically adjusting the threshold value based upon a condition of the stored indications only either (1) between image frames or (2) within image frames to ensure that storage and subsequent transmission of the indications does not result in an empty or overflow storage condition as a result of storing variable length indications and transmitting the same at a fixed data rate. - View Dependent Claims (62, 63, 64, 65, 66, 67, 68, 81)
-
-
69. 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 search vector quantization 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 measure of difference between the vector and a threshold value; and
,d) second means for transmitting data indicative of the address of the selected codevector. - View Dependent Claims (70, 71, 72, 73, 74, 75, 82)
-
-
76. A decoder for use by subscribers of a pay television system employing, at an encoding site, 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 the subscribers 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 data indicative of addresses of codevectors found to most closely approximate input vectors, the decoder comprising:
-
a) a second codebook being substantially identical in content to the first codebook; b) first means for receiving the transmitted data and for providing the received data in a form suitable for addressing the second codebook at an output thereof; c) second means for selecting codevectors from the second codebook based upon the output of the first means; and
,d) third means for converting the selected codevectors to NTSC image data and for providing the NTSC image data at an output thereof for substantially reproducing an image input to the encoding site.
-
Specification