Adaptive hierarchical subband vector quantization encoder

• US 5,272,529 A
• Filed: 03/20/1992
• Issued: 12/21/1993
• Est. Priority Date: 03/20/1992
• Status: Expired due to Fees

• Current Assignee: MEWS Incorporated
• Original Assignee: Northwest Starcan Limited Partnership
• Inventors: Frederiksen, Jeffrey E.
• Primary Examiner(s): Britton, Howard W.
• Application Number:
  US07/854,203
• Time in Patent Office: 641 Days
• Field of Search: 358/13, 358/133, 358/135, 358/136
• US Class Current: 375/240.22
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/527 Global motion vector estimation
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 21/2365 Multiplexing of several video streams
• CPC Class Codes: H04N 21/4347 Demultiplexing of several video streams

Abstract

A method system for data reduction of digital video signals based on vector quantization of vectors formed from coefficients of a discrete cosine transform of pixel blocks. The coefficients are grouped into subbands and both scalar and vector quantization are used. Vector quantization is implemented either directly on the vectors or on vectors formed from inter-frame differences between the transformed vectors. The vector quantization searching routine is in accordance with the Voronoi regions resulting from an off-line codeword clustering method using a minimum distance criterion.

Claims

1. A method for data compression of a digital image signal whereby said image signal is subdivided into pixel blocks, each pixel represented by a predetermined number of bits, comprising the steps of:

(a) generating the discrete cosine transform for said block, resulting in a corresponding block of transform coefficients;

(b) scalar quantizing DC and one or more AC coefficients of said discrete cosine transform;

(c) dividing remaining said AC coefficients which are not scalar quantized into a plurality of subband vectors according to their frequency components;

(d) vector quantizing said subband vectors composed of subband coefficients resulting in a code for each said subband vector; and

(e) repeating the above steps for each said block of said image signal.

2. The method according to claim 1, wherein a subset of said plurality of subbands is omitted from subsequent said vector quantization.

3. The method according to claim 1 wherein said vector quantizing comprises a plurality of codetables for each subband, including:

(a) a differential codetable comprising codewords derived from inter-frame differences of transformed training image sequences; and

(b) a spatial codetable comprising codewords derived from individual training image frames.

4. The method according to claim 1, wherein said vector quantizing of each subband vector includes separate codetable for each subband.

5. The method according to claim 4 wherein said codetable for each subband is prepared according to the steps of:

(a) forming training vectors from coefficients derived from performing a discrete cosine transform on training images partitioned into pixel blocks, said coefficients grouped into training vectors according to said subband frequencies;

(b) clustering training vectors into a set of representative codewords according to a minimum distance criterion which ensures spanning the vector space formed by said training vectors; and

(c) forming said codetable by ordering said codewords in binary tree structure according to Voronoi regions.

6. A system for data compression of a digital image signal whereby said image signal is subdivided into pixel blocks, each pixel represented by a predetermined number of bits, comprising:

(a) a video preprocessor stage for receiving a plurality of individually selectable video input data, said preprocessor comprising individually selectable stages for formatting said input video data into separate digital luminance and chrominance data, said chrominance data reduced by averaging, said digital luminance and chrominance data assembled into pixel blocks which are transformed by a discrete cosine transformation processor which additionally forms subband vectors from transform coefficients of a particular frequency band and scalar quantizes coefficients corresponding DC and AC components;

(b) a vector quantization processor stage connected to output of said preprocessor stage for outputting a code corresponding to the result of a search for a minimum mean square error codeword with respect to a particular said subband vector; and

(c) a data flow management stage connected to the output of said vector quantization processor further receiving said scalar quantized coefficients, comprising;

a data flow control unit which monitors output data buffer and regulates data received from said vector quantization processor according to said output data buffer status;

a Huffman encoder which receives said regulated data from said data flow control unit;

a format control unit which formats received Huffman coded data; and

said output buffer which receives formatted data and outputs said data at a predetermined rate.

7. The system according to claim 6, wherein said format control unit merges audio data with said data.

8. The system according to claim 6, further comprising means for signaling the availability of space in said data stream for interjecting opportunistic data.

9. The system according to claim 6, further comprising means for interjecting deterministic data into said data stream at a predetermined rate.

10. The system according to claim 6, further comprising circuitry associated with said vector quantization processor for skipping repeated input vectors or repeated vector codes.

11. The system according to claim 6, further comprising circuitry associated with said vector quantization processor for vector binning, said binning comprising tabulating the number of codes and code length within each of a plurality of frequency ranges within said subbands.

12. The system according to claim 6, wherein said vector quantization processor includes a plurality of vector quantizers for each subband.

13. The system according to claim 12, wherein said plurality of vector quantizers includes a differential codebook and a spatial codebook.

14. A system for data compression of a digital image signal whereby said image signal is subdivided into pixel blocks, each pixel represented by a predetermined number of bits, comprising:

(a) an input terminal for accepting a plurality of individually selectable video signals;

(b) a selectively operable digitizing stage connected to said input terminal for conversion of input analog video signals;

(c) a selectively operable pulldown stage connected to said digitizing stage for reducing the frame rate of said video signals by eliminating redundant fields or combining correlated fields;

(d) a frame formation stage connected to said pulldown stage comprising circuitry for removing video blanking data, separating color data, and generating a frame format video signal from a field oriented video signal;

(e) a frame motion estimation stage connected to output of said frame formation stage for generating an output signal corresponding to a relative motion between adjacent image frames;

(f) a scene change stage connected to said frame motion estimation stage for determining a change of scene event and generating a signal corresponding to occurrence of said event;

(g) a frame motion compensation stage connected to output of frame estimation stage for reframing luminance and chrominance data;

(h) a block forming circuit connected to said compensation stage for forming data blocks for luminance and chrominance data;

(i) a color averaging circuit connected to luminance block data output from block forming stage for reducing said chrominance data and outputting reduced chrominance data in block format;

(j) a transformation stage connected to output of said block forming circuit and color averaging circuit for generating discrete cosine transformation data for each received said block and grouping resulting transform coefficients into a plurality of subbands;

(k) a vector quantization stage connected to said transformation stage having an output code corresponding to a codeword which best matches input vector;

(l) a data flow control stage connected to output of said vector quantization stage and to output of said transformation stage, also monitoring an output data buffer, said data flow control stage regulating data flow into said output data buffer;

(m) a Huffman coding stage connected to output of said data flow control stage for data reduction prior to transfer to said output data buffer;

(n) a format control stage connected to output of said Huffman coding stage for organizing said data according to a predetermined format; and

(o) said output data buffer connected to output of said format control stage for storing said data and outputting said data at a predetermined rate.

15. The system according to claim 14, wherein said format control stage merges audio data with said data.

16. The system according to claim 14, further comprising means for signaling the availability of space in said data stream for interjecting opportunistic data.

17. The system according to claim 14, further comprising means for interjecting deterministic data into said data stream at a predetermined rate.

18. The system according to claim 14, further comprising circuitry associated with said vector quantization stage for skipping repeated input vectors or repeated vector codes.

19. The system according to claim 14, further comprising circuitry associated with said vector quantization stage for vector binning, said binning comprising tabulating the number of codes and code length within each of plurality of frequency ranges within said subbands.

20. The system according to claim 14, wherein said vector quantization stage includes a plurality of vector quantizers for each subband.

21. The system according to claim 20, wherein said plurality of vector quantizers includes a differential codebook and a spatial codebook.