Progressive transmission of vector quantized data
First Claim
1. In a tree search, variable rate vector quantization data compression system of the type the organizes an image frame into blocks of input data, and converts each 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, the codevectors at each successive level representing possible input vectors with greater accuracy than codevectors at a preceding level, each codevector having an associated address, a method comprising the steps of:
- a) for each input vector, automatically selecting a plurality of codevectors, each codevector being selected from a different level of the codebook;
b) for a first one of the selected codevectors, transmitting data indicative of the address associated therewith; and
,c) for each of the other selected codevectors, transmitting data indicative of at least a portion of the address of each other selected codevectors that, in combination with previously transmitted address data, uniquely identifies each other selected codevector.
3 Assignments
0 Petitions
Accused Products
Abstract
A distortion adaptive vector quantization method is employed to select, for each input vector, several codevectors from a tree structured codebook. The first codevector defines a basis signal, and each subsequent codevector defines an enchancement signal. The basic signal is indicative of the full codebook address from which the first codevector was selected. Each enhancement signal is indicative of only so much of the additional address bits that are required, in combination with the basic signal, to identify the address of the codebook from which the subsequent codevectors were selected. The basic signal and each enhancement signal are transmitted to a decoder which may employ only the basic signal, or the basic signal and one or more of the enhancement signals to reproduce the input vector. The reproduction quality of the input vector increases with the number of enhancement signals chosen.
-
Citations
37 Claims
-
1. In a tree search, variable rate vector quantization data compression system of the type the organizes an image frame into blocks of input data, and converts each 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, the codevectors at each successive level representing possible input vectors with greater accuracy than codevectors at a preceding level, each codevector having an associated address, a method comprising the steps of:
-
a) for each input vector, automatically selecting a plurality of codevectors, each codevector being selected from a different level of the codebook; b) for a first one of the selected codevectors, transmitting data indicative of the address associated therewith; and
,c) for each of the other selected codevectors, transmitting data indicative of at least a portion of the address of each other selected codevectors that, in combination with previously transmitted address data, uniquely identifies each other selected codevector. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. In a tree search, variable rate vector quantization data compression system of the type that organizes an image frame into blocks of input data, and converts each 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, the codevectors at each successive level representing possible input vectors with greater accuracy than codevectors at a preceding level, each codevector having an associated address, the addresses increasing in length with each subsequent level of the codebook, a method comprising the steps of:
-
a) defining first and second threshold values wherein the first threshold value is indicative of a tolerable distortion between a representation of the input vector and a codebook vector and the second threshold value is indicative of a level of the codebook from which a codevector should be selected if the distortion is greater than the first threshold value; b) providing first and second buffers, there being a buffer corresponding to each threshold value; c) for each input vector, automatically selecting, based upon the threshold values, a plurality of codevectors, each codevector being selected from a different level of the codebook, each buffer being assigned to one of the selected codevectors; d) for a first codevector selected for each input vector, storing data indicative of the address associated therewith in the buffer assigned to the first selected codevector; e) for each subsequent codevector selected for each input vector, storing, in its assigned buffer, data indicative of at least a portion of the address associated therewith that, in combination with address data stored in other buffers, uniquely identifies the subsequent codevectors; and
,f) transmitting the address data from the buffers while periodically adjusting the threshold values based upon a measure of unused capacity of their corresponding buffer. - View Dependent Claims (12, 13, 14)
-
-
15. 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, the codevectors at each successive level representing possible input vectors with greater accuracy than codevectors at a preceding level, each codevector having an associated address, each address having a length that increases with each subsequent level of the codebook, a method comprising the steps of:
-
a) defining a plurality of distortion threshold values and an equal plurality of codebook level threshold values, there being a codebook level threshold value corresponding to each distortion threshold value; b) selecting a first one of the distortion threshold values and the corresponding one of the codebook level threshold values, and defining the same as current distortion threshold and current codebook level threshold values, respectively; c) receiving and processing an input vector, selecting an initial level of the codebook, and defining the initial level as a current level; d) comparing the processed input vector to the codevectors at the current level of the codebook and selecting the codevector at the current level that most closely resembles the processed input vector; e) obtaining a measure of distortion between the processed input vector and the selected codevector; f) storing an indication of the address associated with the selected codevector only if the measure of distortion is less than the current distortion threshold value, but otherwise selecting a next level of the codebook; g) redefining the current level as the next level selected in step (f); h) repeating steps (d)-(g) until either the measure of distortion is less than the current distortion threshold value or a level of the codebook subsequent to the current level is not less than the current codebook level threshold value, then storing the indication; i) selecting a next one of the distortion threshold values and the corresponding one of the codebook level threshold values and redefining the current distortion threshold and codebook level threshold values as the selected distortion threshold and codebook level threshold values, respectively; j) selecting a next level of the codebook and redefining the current level as the next level selected in this step (j); k) comparing the processed input vector to the codevectors at the current level of the codebook and selecting the codevector at the current level that most closely resembles the processed input vector; l) obtaining a measure of distortion between the processed input vector and the selected codevector; m) proceeding to step (n) if either the measure of distortion is less than the current distortion threshold value or a level of the codebook subsequent to the current level is not less than the current codebook level threshold, but otherwise repeating steps (j) through (l); n) storing an indication of only a portion of the address of the codevector selected at the current level that, in combination with previously stored data, is required to uniquely identify the codevector selected at the current level; and o) transmitting the stored data while periodically adjusting the distortion threshold and codebook level threshold values based upon the amount of stored data. - View Dependent Claims (16, 17, 18, 19, 20, 21)
-
-
22. Method comprising the steps of:
-
a) providing, at an earth station, a tree search variable rate vector quantization data compression system of the type that organizes an image frame into blocks of input data and that converts each 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, the codevectors at each successive level representing possible input vectors with greater accuracy than codevectors at a preceding level, each codevector having an associated address, the addresses increasing in length with each subsequent level of the codebook; b) defining, in the compression system, a plurality of pairs of first and second threshold values wherein each first threshold value is indicative of a tolerable distortion between a representation of the input vector and a codebook vector and each second threshold value is indicative of a level of the codebook from which a codevector should be selected if the distortion is greater than the first threshold value; c) providing, in the compression system, a plurality of buffers, there being a buffer corresponding to each pair of threshold values; d) in the compression system; (i) for each input vector, automatically selecting, based upon the threshold values, a plurality of codevectors, each codevector being selected from a different level of the codebook, each buffer being assigned to one of the selected codevectors; (ii) for a first codevectors selected for each input vector, storing data indicative of the address associated therewith in the buffer assigned to the first selected codevector; (iii) for each subsequent codevector selected for each input vector, storing, in its assigned buffer, data indicative of at least a portion of the address associated therewith that, in combination with address data stored in other buffers, uniquely identifies the subsequent codevector; e) transmitting from the earth station, via satellite, to a receiving location, the address data from the buffers while periodically adjusting each pair of threshold values based upon a measure of unused capacity of its corresponding buffer; f) at the receiving location; i) providing another tree search vector quantization codebook that is substantially identical to that in the compression system; (ii) receiving the data transmitted for each input vector and obtaining therefrom the address for the first selected codevector and the address portions for the subsequently selected codevectors; (iii) combining the address of the first selected codevector and at least one of the address portions to uniquely identify one of the subsequently selected codevectors; (iv) retrieving from the codebook at the receiving location the codevector uniquely identified in step (F)(iii); and (v) employing the retrieved codevector to provide at the receiving location a substantial representation of the block of input data. - View Dependent Claims (23, 24, 25, 26)
-
-
27. Data compression apparatus comprising:
-
first means for receiving a multi-dimensional input vector representative of a block of data to be compressed; a tree search vector quantization codebook having plural levels of codevectors, each codevector being representative of a possible input vector and the codevectors at each successive level representing possible input vectors in greater detail than codevectors at a preceding level, each codevector having a unique address associated therewith; a controller coupled to the first means and to the tree search codebook for maintaining a plurality of threshold values and for repeatedly and automatically comparing the input vector to the codevectors at successive levels of the codebook and for repeatedly and automatically selecting a plurality of codevectors for the input vector, each codevector being selected from a different level based on a comparison of one of the threshold values with a measure of difference between the codevector and the input vector; and
,a plurality of transmitters each coupled to the controller, a first one of the transmitters for transmitting an indication of the address associated with a firs tone of the selected codevectors, the indication of the address associated with the first one of the selected codevectors being representative of a basic signal, each other transmitter for transmitting an indication of at least a portion of the address associated with a one of the remaining selected codevectors, each indication of at least a portion of the address associated with a one of the remaining selected codevectors being representative of an enhancement signal. - View Dependent Claims (28, 29, 30, 31, 32, 33, 34, 35, 36)
-
-
37. A decoder for use by subscribers of a pay television system employing, at a head end thereof, 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, and having a 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 head end transmitting a basic signal comprising data indicative of the address of a first selected codevector found to most closely resemble the input vector and successively transmitting a plurality of enhancement signals each indicative of a portion of an address of a subsequently selected codevector, each portion of an address being such that, in combination with previously transmitted data, the portion uniquely identifies the selected codevector, the decoder comprising:
-
a second codebook being substantially identical in content to the first codebook; first means for receiving the basic signal and each successive enhancement signal, and for combining the basic signal and a selected number of the enhancement signals to obtain an address for addressing the second codebook and retrieving a codevector therefrom residing at the obtained address, the retrieved codevector being a function of the number of enhancement signals combined with the basic signal; second means for converting the retrieved codevectors to NTSC image data and for providing the NTSC image data at an output thereof for substantially reproducing images input to the head end.
-
Specification