Vector quantizer

• US 4,670,851 A
• Filed: 10/22/1984
• Issued: 06/02/1987
• Est. Priority Date: 01/09/1984
• Status: Expired due to Term

• Current Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Inventors: Itoh, Atsushi, Asai, Kohtaro, Murakami, Tokumichi
• Primary Examiner(s): Chin, Gary
• Assistant Examiner(s): Teska, Kevin J.
• Application Number:
  US06/663,436
• Time in Patent Office: 953 Days
• Field of Search: 364/518, 364/745, 364/807, 358/21 R, 358/12, 358/133, 358/136, 340/732, 340/733, 340/347 AD, 340/347 M
• US Class Current: 378/121
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/238 using non-full search, e.g. three-step search
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/50 using predictive coding H04N19/61 takes precedence
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation

Abstract

A vector quantizer for quantizing the vector of image and audio information, the vector quantizer being capable of efficiently encoding a compensation predictive error signal at a reduced bit rate by performing adaptive vector quantization after judging the significance of the compensation predictive error signal in blocks, and capable of movement compensation inter-frame vector encoding in which variable-length encoding of movement vector is facilitated and information production control is achieved easily.

Claims

1. A vector quantizer comprising:

a vector quantization encoder including a subvector register which stores picture signal sequences to be coded, samples every N (N=a plural number) picture signal sequences in blocks to store the input picture signal sequences as input subvectors and a coding code table memory for sampling output vectors obtained previously by clustering using picture input signal sequences to form blocks of the output vectors and for reading the blocks as output subvectors, said encoder including a distortion computation circuit and a minimum distortion detector for selecting an output subvector having a minimum distortion from the input subvectors from a set of output subvectors stored in the code table memory, said encoder coding the address of the selected output subvector and giving the corresponding index of the output subvector; and

a decoder which reads the corresponding output vector by using the index given by the encoder as the address of the output vector from a decoding code table memory storing a set of output vectors obtained by clustering or the like using picture input signal sequences, and then decodes the output vector.

2. The vector quantizer as set forth in claim 1, wherein the distortion computation circuit for calculating the distortion between the input and the output vectors is of the pipeline system constituted by the cascaded connection of a parallel subtractor, a parallel magnitude operator, a register and a parallel adder, to enhance the speed of operation of the calculation of the distortion between the input and the output vectors.

3. A vector quantizer comprising:

a movement vector quantizer including;

an input vector register which stores picture input signal sequences to be coded and stores input vectors formed by blocking every K (K=a plural number) input picture signal sequences;

a variable-delay frame memory which stores the picture signal sequences of a one-frame cycle or more preceding frame; and

a rewritable dynamic output vector code table memory for properly extracting a plurality of adjacent blocks lying around a block located at the same position as that of the picture input signal sequences in the frame memory from the frame memory and reading the same sequentially as movement output vectors; and

said movement vector quantizer selecting a movement output vector having a minimum distortion from the input vector from a set of movement output vectors stored in the dynamic output vector code table memory, and sending an address corresponding to the movement output vector as a movement vector index to a multiplexer;

a coder comprising;

a subtractor which obtains the difference between the input vector and the selected movement output vector and gives a differential signal;

a differential input vector register which blocks every L (L=a plural number) output signal sequences of the subtractor and stores the same as differential input vectors;

a differential input vector code table memory which stores a differential output vector set produced previously by clustering using the differential input signal sequences;

a differential vector quantizer which selects a differential output vector having a minimum distortion from among a set of the differential output vectors, sends the selected differential output vector to an adder, and provides an address corresponding to the differential output vector as a differential vector index to said multiplexer;

said adder adding the movement output vector and the differential output vector, and sending a regenerated output signal to the frame memory; and

said multiplexer multiplying the code sequence of the movement vector index by the code sequence of the differential vector index to produce coded output signal sequences;

a demultiplexer which partitions the signal sequence transmitted by the encoder to obtain a code sequence of decoded movement vector index and a code sequence of the decoded differential vector index;

a variable-delay decoding frame memory for storing the picture output signal sequences of a frame preceding at least one-frame cycle;

a rewritable decoded dynamic output code table memory for reading a movement vector corresponding to the movement vector index transmitted thereto by the decoding frame memory;

a decoded differential output vector code table memory storing the same contents as those of the differential output vector code table of the coder; and

a decoder which reads a differential output vector corresponding to the differential vector index transmitted thereto from the decoded differential output vector code table memory, and adds the same to the decoded movement output vector to decode and regenerate the picture output signal sequences;

whereby animated picture coding efficiency is enhanced.

4. A vector quantizer comprising:

a coder comprising;

a first frame memory for storing the picture signals of a frame preceding at least by one-frame cycle;

a dynamic vector quantizer which uses a dynamic output vector set consisting of input vectors formed by blocking every K (K=a plural number) picture signal sequences of a present frame and a plurality of blocks of picture signal sequences formed by displacing the input vectors by a predetermined picture element in the first frame memory and a fixed memory and a fixed mean value output vector set as a dynamic output vector set, and codes a dynamic output vector or a mean value output vector having a minimum distortion from the input vector in K-dimensional signal space into a first index;

a subtractor which subtracts the dynamic output vector or the mean value output vector having the minimum distortion from the input vector to obtain a differential input vector;

a differential vector quantizer which codes the differential input vector into a second index of a differential output vector having the minimum distortion among a differential output vector set obtained previously;

a first adder which adds the dynamic output vector or the mean value vector which has the minimum distortion and the differential output vector to regenerate the block of the picture signal sequence and transmits a signal to the first frame memory;

a variable-length encoder which processes the first index and the second index through variable-length encoding;

a decoder comprising;

a variable-length decoder which decodes the output of the variable-length encoder into the first index and the second index;

a dynamic output vector quantization decoder which receives the first index and transmits a regenerated dynamic output vector or a regenerated mean value corresponding directly to that of the coder among the dynamic output vector set or the mena value output vector set;

a differential vector quantization decoder which receives the second index and transmits a regenerated differential output vector corresponding directly to that of the coder among the differential output vector set;

a second adder which adds the regenerated dynamic output vector or the regenerated mean value vector and the differential output vector to obtain the block of regenerated picture signal sequences; and

a second frame memory which delays the regenerated picture signal sequences given by the second adder by one-frame cycle and gives a plurality of blocks of the regenerated picture signal sequences displaced by a predetermined picture element to the dynamic vector quantization decoder as a dynamic output vector.

5. A vector quantizer according to claim 4, wherein said dynamic vector quantizer uses a set of a plurality of movement vectors produced by dynamic vector-quantizing actual picture signals between frames repeating clustering processes so that the total sum of the distortions between output vectors and the dynamic output vectors is minimized, as a plurality of two-dimensional displacement vectors which define the set of dynamic output vectors.

6. A vector quantizer comprising:

a frame memory for storing past picture signals of at least one frame;

a subtractor which calculates the difference between a block of predictive signals formed by blocking the picture signal sequences of one-frame cycle preceding frame read from the frame memory and a block of picture signal sequences formed by blocking every K (K=a plural number) present picture signal sequences to provide a predictive error signal block;

a limiter which receives the predictive error signal block given by the subtractor as an input vector, regards the input vector as a zero vector when the distortion of the input vector from the zero vector is smaller than a predetermined threshold and gives a zero vector detection signal;

an output vector code table memory which stores the respective output points of 2ⁿ partitions of K-dimensional signal space including the input vector, formed in a binary tree structure of n steps (n=a positive integer) by repeating binary partitions, as a set of output vectors;

a parallel distortion calculating circuit which calculates the distortions between the input vector and two output vectors of each step of the binary tree structure;

a distortion comparator which compares distortions between the two output vectors and the input vector and selects the output vector which has smaller distortion from the input vector;

an index register which stores indices corresponding to addresses for reading the output vectors in steps according to the result of the comparison implemented by the distortion comparator and updates the index every time the distortion comparison result for each step is given;

a coding controller which receives the index for each step, controls the amount of data by controlling the number of steps, and processes the zero vector detection signal and the index through variable-length coding;

a second code table memory having the same contents as that of the output vector code table memory;

a decoder which receives the output of the coding controller processed through variable-length coding, decodes the zero vector detection signal and the index, reads an output vector from the second code table memory, and transmits the output vector or the zero vector as a regenerative predictive error signal block;

an adder which adds the regenerated predictive error signal block and the predictive signal block to calculate regenerated picture signals to be used as past picture signals after being delayed by one-frame cycle or more by the frame memory; and

a transmission buffer which controls the number of steps by feedback control.

7. A vector quantizer comprising:

a front stage vector quantizer comprising;

a variable-delay frame memory which stores the picture signal sequence of a frame preceding by one-frame cycle or more;

a dynamic output vector code table consisting of an input vector register which stores input vector blocks formed by blocking every K (K=a plural number) picture input signal sequences to be coded;

a rewritable first output vector code table which extracts properly a plurality of adjacent blocks lying around a block located at the same position in the frame memory as the position of the picture input signal sequences from the frame memory and reads the same sequentially as output vectors; and

a fixed second output vector code table for sequentially reading output vectors from a plurality of mean value vectors of different levels;

said front stage vector quantizer selecting a first output vector having the minimum distortion from the input vector from a set of output vectors stored in the rewritable first output vector code table;

selecting a second output vector having the minimum distortion from set of output vectors stored in the fixed second output vector code table when the distortion of the first output vector is greater than a predetermined upper threshold;

selecting an output vector consisting of the picture elements of a central block among a plurality of blocks extracted from the frame memory when the distortion of the first output vector is smaller than a predetermined threshold;

selecting the first output vector selected from the rewritable first output vector code table when the distortion of the first output vector is less than or equal to the upper threshold and greater than or equal to the lower threshold; and

transmitting the selected output vector and the corresponding address as an output vector index;

a fixed back stage vector quantizer comprising;

a subtractor which calculates the difference between the input vector and the output vector selected under the condition defined by the thresholds and transmitted by the dynamic front stage vector quantizer and transmits an inter-frame differential signal;

a differential input vector register which stores the output signal sequences transmitted by the subtractor as a differential input vector after blocking every L (L=a plural number) output signal sequences of the subtractor, separating the intrablock mean value from the blocks and normalizing the blocks after separating the intrablock mean value by an amplitude gain; and

a differential output vector code table storing differential output vectors produced previously using inter-frame differential signal sequences;

said fixed back stage vector quantizer selecting a differential output vector having the minimum distortion from the differential output vector code table to obtain the address of the selected differential output vector as a differential output vector index;

deciding whether or not the inter-frame differential signal block to be coded is significant by comparing the mean value and the amplitude gain with a significance decision threshold; and

transmitting the selected differential output vector, a significance identification label and, when significant, the mean value and the amplitude gain;

an adder which adds the output vector given by the dynamic front stage vector quantizer and the output vector given by the fixed back stage vector quantizer to give regenerated picture signals to the frame memory; and

a variable-length encoder which processes the output vector index given by the dynamic front stage vector quantizer, the significance identification label given by the fixed back stage vector quantizer, the mean value, the amplitude gain and the differential output vector index together through variable-length coding.