Hierarchical adaptive multistage vector quantization

• US 5,799,110 A
• Filed: 11/09/1995
• Issued: 08/25/1998
• Est. Priority Date: 11/09/1995
• Status: Expired due to Term

• Current Assignee: Utah Valley University
• Original Assignee: Utah Valley University
• Inventors: Huang, Chien-Min, Israelsen, Paul D.
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/555,434
• Time in Patent Office: 1,020 Days
• Field of Search: 382/253, 382/251, 382/270, 382/240, 348/405, 348/414, 348/417, 348/418, 348/422
• US Class Current: 382/253
• 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/107 between spatial and temporal predictive coding, e.g. picture refresh
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/19 using optimisation based on Lagrange multipliers
• CPC Class Codes: H04N 19/39 involving multiple description coding [MDC], i.e. with separate layers being structured as independently decodable descriptions of input picture data
• CPC Class Codes: H04N 19/40 using video transcoding, i.e. partial or full decoding of a coded input stream followed by re-encoding of the decoded output stream
• CPC Class Codes: H04N 19/587 involving temporal sub-sampling or interpolation, e.g. decimation or subsequent interpolation of pictures in a video sequence
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

An N-stage vector quantizer in which increasingly smaller portions of a vector are compared to a threshold until the quantization error is less than the threshold. The threshold may be adaptive to insure a constant bit rate. The first stage performs VQ and inverse VQ on an input vector. The difference between the inverse VQ and the input vector is determined to create a first stage residual error. If the first stage residual error is less than a threshold, no further stages of the multistage vector quantizer are used and the input vector or first stage residual is passed on to the output stage. However, if the first stage residual error is not less than the threshold, the residual error is passed to stage two of the multistage vector quantizer where VQ and inverse VQ are performed on the first stage residual error. The process is continued until the residual is less than the threshold. If the Nth stage is reached without the residual being less than the threshold, the process is repeated on a smaller portion of the original input vector. For example, if the original input vector were a 16×16 vector, the smaller section could be a 16×8 vector.

Claims

1. An hierarchical adaptive multistage vector quantizer to supply compressed video signals to a transmission line, said hierarchical adaptive multistage vector quantizer comprising:

means for receiving a vector I having a particular magnitude reflective of a portion of a video signal;

mean removal means for performing mean removal on vector I to provide a mean removed vector I_M ;

an vector quantizer having "N" stages in which N equals 3 or more, the first stage performing vector quantization (VQ) and inverse vector quantization (YQ^-1) of the vector I_M to obtain a residual vector E_1-, the (N-1)th second stage performing VQ and inverse vector quantization (VQ^-1) of the residual vector E₁ to obtain a residual vector E_N-1 and the Nth stage performing vector quantization (VQ) and inverse vector quantization (VQ^-1) of the residual vector EN_N-1 to obtain residual vector E_N ;

comparison means for comparing each vector(I_M, E₁, E_N-1, . . . E_N) to a threshold when each such vector is generated; and

vector reduction means connected to be operative when residual vector E_N is greater than said threshold for selecting a subsection of vector I for processing by the vector quantizer and for processing the comparison means until a residual vector (r_s), is equal to or less than said threshold; and

means to generate and transmit to a transmission line an address representing said residual vector r_s when said residual vector (r_s) is equal to or less than said threshold.

2. The quantizer of claim 1 wherein said threshold is adaptive to maintain a constant bit rate.

3. The quantizer of claim 2 wherein said threshold is adaptive as the vector I magnitude decreases and as the stages advance toward stage N.

4. The quantizer of claim 1 wherein said vector quantizer includes a motion compensator and a first codebook for use in vector quantization VQ on a current block and a second codebook is used for vector quantization VQ on residual vector which has been motion compensated by the motion compensator.

5. The quantizer of claim 1 in which the vector I is compared with the threshold.

6. An hierarchical adaptive multistage vector quantizer to supply compressed video signals to a transmission line, said hierarchical adaptive multistage vector quantizer comprising:

means for receiving a vector I having a particular magnitude reflective of a portion of a video signal;

mean removal means for performing mean removal on vector I to provide a mean removed vector I_M ;

an vector quantizer having "N" stages in which N equals 3 or more with each of said N stages having its own vector codebook, the first stage performing vector quantization (VQ) and inverse vector quantization (VQ^-1) of the vector I_M to obtain a residual vector E_1-, the (N-1)th stage performing VQ and inverse vector quantization (VQ^-1) of the residual vector E_1- to obtain a residual vector E_N-1 and the Nth stage performing vector quantization (VQ) and inverse vector quantization (VQ^-1) of the residual vector E_N-1 to obtain residual vector E_N ;

comparison means for comparing each vector(I_M, E_I, E_N-1, . . . E_N) to a threshold when each such vector is generated; and

vector reduction means connected to be operative when residual vector E_N is greater than said threshold for selecting a subsection of vector I for processing by the vector quantizer and for processing the comparison means until a residual vector (r_s) is equal to or less than said threshold; and

selection means for selecting the first residual vector that is equal to or less than the threshold and for passing an address reflective of said residual vector to a transmission line.