Data compression using orthogonal transform and vector quantization

In an image communication system, an input image sequence is converted into a block-formatted sequence. A data compression signal indicative of the amount of moving blocks in the block-formatted sequence is generated to individually control a plurality of vector quantizers each having a particular frequency band and a memory containing output vectors. The output vectors of each of the vector quantizers is representative of inverse orthogonal transform of a code table of optimum quantized vectors in the particular frequency band, the optimum quantized vectors being orthogonal transform of interframe differential training image sequences. The output vectors is retrievable from the memory as a function of an interframe differential image sequence, or prediction error. Each vector quantizer selects one of the vectors retrieved from the memory which is nearest to the value of the interframe differential image sequence and generates an index signal representative of the selected vector, which index signal is encoded and transmitted to a destination. The outputs of the vector quantizers are processed by inverse vector quantizers to generate a predictive image sequence. The prediction error is detected as a difference between the predictive image sequence and the block-formatted sequence.

BACKGROUND OF THE INVENTION 
The present invention relates generally to image communication systems, and 
more specifically to a data compression technique for image signals using 
orthogonal transform and vector quantization. 
Vector quantization is an efficient data compression technique for 
full-motion image signals. According to the vector quantization coding 
technique, the amount of coded image information bits increases with the 
rate of movement of the image. Under extreme cases, the rate of the coded 
information bits exceeds the data rate of a transmission channel. When 
this occurs, the transmission is interrupted, causing discontinuities in 
the reproduction of the original. Vector quantizers proposed in a paper 
entitled "Discrete cosine transform coding system using gain/shape vector 
quantizers and its application to color image coding" (Saito, H., Takeo, 
H., Aizawa, K., Harashima, H., and Miyakawa, H., Picture Coding Symposium 
'86, April, Tokyo) is intended to solve this problem by reducing the image 
resolution as a function of the amount of rapidly moving objects since the 
human eyes exhibit poor perception to rapid movements. The proposed system 
comprises a discrete cosine transform encoder which performs discrete 
cosine transform on a predictive, interframe differential image sequence 
of the block format so that the orthogonally transformed block signals are 
mapped on different bands of a frequency domain. A plurality of vector 
quantizers are connected to the output of the encoder to effect vector 
quantization on the respective frequency bands. However, a substantial 
amount of hardware is required for implementing orthogonal transformation 
at the transmitter and for implementing inverse orthogonal transformation 
at the receiver. 
SUMMARY OF THE INVENTION 
It is therefore an object of the present invention to provide a 
communication system in which image data is compressed using orthogonal 
transform and vector quantization. 
This object is obtained by forming code tables according to different 
frequency bands. Each of the code tables contains output vectors which are 
produced by the following steps: 
(a) performing orthogonal transform on interframe differential training 
image sequences, so that the orthogonally transformed interframe 
differential training image sequences are mapped onto a frequency domain; 
(b) partitioning the mapped training image sequences into different 
frequency bands; 
(c) deriving a plurality of code tables of optimum quantized vectors 
respectively from the partitioned training image sequences; and 
(d) performing inverse orthogonal transform on the quantized vectors of 
each of the code tables, so that the inversely orthogonally transformed 
optimum quantized vectors of each of the code tables are mapped onto a 
spatial domain. 
Each of the code tables is implemented by a memory and incorporated into a 
vector quantizer. The output vectors are stored and retrieved from the 
memory as a function of a signal representative of the interframe 
differential signal, or prediction error. One of the vectors which is 
nearest to the input value is selected and the index of the selected 
vector is encoded for transmission. 
Specifically, the present invention provides a vector quantization encoder 
which comprises a scan converter for converting an input image sequence 
into a block-formatted sequence. A data compression signal indicative of 
the amount of moving blocks in the block-formatted sequence is generated 
to individually control a plurality of vector quantizers. Each of the 
vector quantizers has a particular frequency band and a memory containing 
output vectors, the output vectors of each of the vector quantizers being 
representative of inverse orthogonal transform of a code table of optimum 
quantized vectors in the particular frequency band, the optimum quantized 
vectors being orthogonal transform of an interframe differential training 
image sequence, the output vectors being readable from the memory as a 
function of an interframe differential image sequence, or prediction 
error. Each vector quantizer selects one of the vectors read out of the 
memory which is nearest to the value of the interframe differential image 
sequence and generates an index signal representative of the selected 
vector. The outputs of the vector quantizers are processed by inverse 
vector quantizers to generate a predictive image sequence. A subtractor is 
provided for detecting a difference between the block-formatted sequence 
and the predictive image sequence and applying the detected difference to 
the vector quantizers as said prediction error. An encoder is connected to 
the vector quantizers for encoding the index signals for transmission over 
a transmission channel. 
According to a further aspect of the invention, there is provided a 
communication system which comprises the vector quantization encoder 
constructed in a manner as mentioned above and a vector quantization 
decoder which includes means for decoding the transmitted coded index 
signals and a plurality of inverse vector quantizers, the outputs of the 
inverse vector quantizers being summed and delayed for a frame interval, 
and summed again with a subsequent value of the sum of the outputs of the 
inverse vector quantizers. 
Preferably, a moving vector detector is provided for detecting motion 
vectors from the output of the scan converter. A variable delay circuit 
introduces a variable delay time in accordance with the output of the 
moving vector detector to the predictive image sequence before it is 
applied to the subtractor. The timing of the encoder is also controlled in 
response to the detected motion vector.

DETAILED DESCRIPTION 
Referring now to FIG. 1, there is shown a vector quantization encoder 
according to a first embodiment of the invention. The encoder comprises a 
scan converter 1 which converts the scan format of a full-motion input 
image sequence so that the output of the scan converter is representative 
of a series of blocks each comprising a matrix array of picture elements, 
or pixels. The output of scan converter 1 is applied to a motion detector 
2. Motion detector 2 detects the absolute value of the interframe 
difference between the pixels of a given frame and the pixel of the next 
frame of that frame and totals the interframe differences derived from a 
given block and compares the total value with an appropriate threshold 
value. When the total value exceeds the threshold value, motion detector 2 
generates an output indicating that the given block is in motion. The 
motion-indicating signal is applied to an integrator 3 where the rate of 
occurrence of blockwise motions is determined. The integrator output is 
supplied to a comparator unit 4 where it is compared with a plurality of 
reference values representative of different frequencies. Comparator unit 
5 generates outputs indicating the frequencies of blockwise motions of the 
original picture, the comparator outputs being fed to vector quantizer 
unit 5 as band-elimination signals. The output of scan converter 1 is also 
applied to a delay circuit 6 which introduces a delay time corresponding 
to the time interval taken to perform motion detection and 
band-elimination determination. The output of delay circuit 6 is applied 
to a subtractor 7 to which the output of a frame memory 10 is also 
applied. Subtractor 7 generates a signal representative of a prediction 
error, or interframe differential image signal. 
As will be described later, vector quantizer unit 5 receives the output of 
subtractor 7 and quantizes an error term formed as the difference between 
the new sample and a prediction of the new sample based on past coded 
outputs. Vector quantization is effected on different frequency bands 
depending on the outputs of comparator unit 4 and supplies index signals 
to an inverse vector quantizer unit 8 and to a variable length encoder 11. 
The output of inverse vector quantizer unit 8 is applied to an adder 9 
which combines the output of frame memory 10 and applies its output to the 
frame memory 10. Frame memory 10 introduces a one-frame delay to the input 
signal and supplies its output to the subtractor 7 as a prediction of the 
new sample. 
As shown in FIG. 2, comparator unit 4 includes high and medium frequency 
comparators 41 and 42 for making comparison between the output of 
integrator with high and medium reference values, respectively. Typically, 
the higher reference value corresponds to moving blocks that occupy more 
than 20% of the total and the medium reference value those that occupy 10% 
to 20% of the total. When the total of the moving blocks is below the 
medium reference value, band-elimination signals are not generated. When 
it exceeds the medium value, the comparator 42 generates an output that 
inhibits vector quantization on the highest frequency band and when it 
further exceeds the higher reference value, the comparator 41 generates an 
inhibit signal for inhibiting quantization on the medium frequency band in 
addition to the output of comparator 42. 
Vector quantizer unit 5 comprises a low-frequency range vector quantizer 
51, a midrange vector quantizer 52 and a high-frequency range vector 
quantizer 53. The output of high frequency comparator 41 is applied to the 
inhibit input of midrange vector quantizer 52 and the output of medium 
frequency comparator 42 is applied to the inhibit input of the 
high-frequency range vector quantizer 53. It is seen that when the total 
number of moving blocks exceeds the medium reference value, but not 
exceeding the high reference value, high-frequency range vector quantizer 
53 is disabled, allowing vector quantization to be effected on frequencies 
below midrange. When the total of moving blocks falls within the high 
frequency range, comparators 41 and 42 produce their outputs, disabling 
midrange and high-frequency range vector quantizers 52 and 53 so that 
vector quantization is effected only upon the low-frequency range. 
In FIG. 3, a vector quantization decoder is shown as comprising a buffer 
20, a variable length decoder 21, and inverse vector quantizers 22, 23 and 
24. Buffer 20 is to absorb the difference between the data transmission 
speed and the speed at which the variable length code is decoded. The 
outputs of decoder 21 are coupled respectively to the inverse vector 
quantizers 22, 23 and 24 to perform inverse vector quantization in a 
manner inverse to the vector quantizers 51, 52 and 53, respectively. The 
outputs of inverse vector quantizers 22, 23 and 24 to produce 
spatial-domain, frequency-divided signals. These signals are summed in an 
adder 25 to recover the prediction error. An adder 26 is connected to the 
output of adder 25 to sum the prediction error with the output of a frame 
memory 27 which introduces a frame interval delay to the prediction error 
signal to recover the original image sequence at the output line 27. 
Returning to FIG. 2, each vector quantizer has a "code table" (or code 
book) which is an infinite set of output vectors. The code table of each 
vector quantizer is prepared according to the following steps: 
(a) performing orthogonal transform on each of a plurality of interframe 
differential training image sequences, so that the orthogonally 
transformed interframe differential training image sequences are mapped 
onto a frequency domain; 
(b) partitioning the mapped training image sequences into different 
frequency bands; 
(c) deriving a plurality of code tables of optimum quantized vectors 
respectively from the partitioned training image sequences, using the LBG 
(Linde, Buzo and Gray) algorithm (see Linde, Y., Buzo, A., and Gray, R. 
M., "An algorithm for vector quantizer design," IEEE Transactions on 
Communications COM-28 pp. 84-95 (January 1980)); and 
(d) performing inverse orthogonal transform on the quantized vectors of 
each of the code tables, so that the inversely orthogonally transformed 
optimum quantized vectors of each of the code tables are mapped onto a 
spatial domain. 
The output vectors are stored in locations of a read-only memory which are 
addressable as a function of the prediction error from the subtractor 7. 
The index of the addressed vector is generated for transmission. According 
to the data compression technique as taught by the present invention, the 
index of the addressed vector can be advantageously represented by as much 
as 10 bits. 
Quantitative analysis of the vector quantization of the present invention 
will be given with reference to FIG. 4. Let K.sub.0, K.sub.1 and K.sub.2 
represent the quantized indices of vector quantizers 51, 52 and 53, 
respectively. The outputs of inverse vector quantizers 22, 23 and 24 of 
the receiver are represented by spatial domain vectors F.sub.0, F.sub.1 
and F.sub.2 corresponding to the indices K.sub.0 K.sub.1 and K.sub.2, 
respectively, and F.sub.0 +F.sub.1 +F.sub.2 =F, where F is the vector 
composed by the pixels of the original block. The following relations 
hold: 
##EQU1## 
where Q.sup.-1 is the operator of inverse vector quantization, J is the 
vector in the frequency domain (or conversion space of each code table), 
T, the operator of orthogonal transform, and T.sup.t is the operator of 
the transposition of orthogonal transform. Since vector J is decomposed 
into component vectors J.sub.0, J.sub.1 and J.sub.2 in respective 
frequency bands, the following relations hold: 
##EQU2## 
An optimum index which minimizes the electrical power of prediction error P 
in a frequency band "O", for example, can be obtained as follows: 
##EQU3## 
where K.sub.0 ' is a representative vector of the low frequency band. 
Since there is no correlation between different components of the 
orthogonal transform, there is no correlation between different frequency 
bands. Since Q.sup.-1 (K.sub.0 ')=F.sub.0 ', and T.sup.t =T.sup.-1 
according to Hermit matrix, the following relation holds: 
##EQU4## 
Therefore, 
##EQU5## 
Equation 4 can be written as: 
##EQU6## 
It is therefore not necessary to partition the input image sequence into 
different frequency bands prior to vector quantization, thus eliminating 
the need to provide a hardware for implementing such partitioning. 
Using the code tables mentioned above, vector quantizers 51, 52 and 53 can 
readily perform orthogonal transformation and vector quantization on 
respective frequencies without the hardware for implementing orthogonal 
transformation and frequency partitioning. This is done by reading vectors 
from each memory, or code book as a function of the input prediction error 
and selects one which is nearest to the input value and which minimizes 
prediction error. The index of the selected vector is generated by each of 
the vector quantizers 51, 52 and 53 so that its quantum size is variable 
non-linearly as a function of the prediction error. The index signals from 
the quantizer 5 are converted to a variable length codeword by the encoder 
11 according to the Huffman coding algorithm. A buffer memory 12 is 
connected to the variable length encoder 11 to absorb differences in 
transmission speed between the encoder 11 and a transmission channel 13. 
The individual outputs of the vector quantizers 51, 52 and 53 are applied 
respectively to inverse vector quantizers 81, 82 and 83 of inverse vector 
quantizer unit 8. Inverse vector quantizers perform inverse vector 
quantization on the respective index signals and generate output signals 
which are frequency-divided in the spatial domain. The outputs of the 
inverse vector quantizers 81, 82 and 83 are summed by an adder 84 and fed 
to adder 9. 
A modified embodiment of the invention is shown in FIG. 5 which differs 
from the embodiment of FIG. 1 in that it includes a motion vector detector 
30 which replaces the motion detector 2 of FIG. 1. Motion vector detector 
30 receives inputs from the output of scan converter 1 and from the output 
of frame memory 10 and detects motion vectors using a technique known as 
"block matching". The output of motion vector detector 30 is applied to 
the integrator 3 and to a variable delay 31 to introduce a further delay 
to the output of frame memory 10 to compensate for vector motion. The 
output of variable delay 31 is applied to the subtractor 7 and to adder 9 
as a prediction error. The output of moving vector detector 30 is further 
applied to the variable length encoder 11 to effect the motion 
compensation. 
A vector quantization decoder shown in FIG. 6 is adapted to receive signals 
from the modified encoder of FIG. 5. This vector quantization decoder 
differs from the decoder of FIG. 3 in that it includes a variable delay 32 
which is responsive to a timing signal from the variable length decoder 
21. This output signal is representative of a vector motion detected by 
the motion vector detector 30. Variable delay 32 introduces a further 
delay to the output of frame memory 27 to compensate for the vector 
motion. 
The foregoing description shows only preferred embodiments of the present 
invention. Various modifications are apparent to those skilled in the art 
without departing from the scope of the present invention which is only 
limited by the appended claims. Therefore, the embodiments shown and 
described are only illustrative, not restrictive.