System and method for data compression using multiple codewords and transmitted indices
BACKGROUND OF THE INVENTION 
     This invention relates to an improved method and apparatus for compressing data for storage, transmission or other processing, and more particularly to a method and apparatus for improving the accuracy of a multistage data compression arrangement while also reducing memory and computation requirements. 
     Data compression has been defined as the process of reducing the number of bits necessary to transmit or store information (see Makhoul, John, et al., &#34;Vector Quantization in Speech Coding&#34;, Proc. of the IEEE, Vol. 73, No. 11, November 1985, pp. 1551-1568) or the conversion of a stream of very high rate sampled analog (continuous amplitude, discrete time) data into a stream of relatively low rate digital (discrete amplitude, discrete time) data for communication over a digital communication link or storage in a digital memory (Gray, Robert M., &#34;Vector Quantization&#34;, IEEE ASSP Magazine, April, 1984, pp. 4-29). In other words, data compression involves the process reducing the amount of data needed to represent (for storage, transmission, etc.) information signals. 
     The need for new and more powerful methods of data compression continues to grow with the increase in the amount of information which users wish to transmit over or store in existing information transmission and storage facilities. Of course, in addition to seeking to reduce the amount of data necessary to transmit or store a given amount of information, users also desire to maintain the efficiency, security and reliability of the transmission and storage operation. 
     One approach to implementing data compression is known as vector quantization. Typically, in vector quantization an analog signal source is sampled to form a sequence of digital values representative of the analog signal. Portions or groups of the digital values are then represented as vectors, known as source vectors. The source vectors are compared to a set (codebook) of allowable vector patterns (code vectors) which have been previously determined to be statistically representative and stored. The code vectors all have assigned indices identifying them, and the index of the closest code vector to each source vector (the code vector that minimizes the distortion between it and the source vector) is either stored or transmitted to a receiver which also has a copy of the codebook. Such comparisons thus yield a small array of indices which identify a larger array of source vectors. This process of representing the array of source vectors with a smaller array of indices is vector quantization which, as is evident, achieves data compression. 
     The indices derived in quantization may be stored, transmitted to another location or otherwise operated upon, after which they are used to retrieve from memory the associated code vectors which represent approximations of the original source vectors. In effect, the retrieved code vectors carry the information (with some distortion) which was to be stored, transmitted or otherwise operated upon. 
     In one approach to determining the closest code vector, each source vector is compared with every code vector in the codebook. This approach, known as exhaustive search vector quantization (ESVQ), results in the computational and memory burden growing exponentially while the data rate remains constant and the vector length increases (the theory of data compression guarantees better performance with the use of longer vectors at a fixed compression ratio). 
     A modification of ESVQ, termed residual vector quantization or multistage vector quantization, has been proposed for reducing the memory and computation requirements of the vector quantization process. With multistage vector quantization, a series of quantization stages and codebooks are utilized to produce the array of indices for storage or transmission. Each stage of a multistage quantization system operates on an error or residual vector produced in the previous stage. Although this approach does reduce memory and computation costs, a decline in performance and accuracy of the quantization has also typically resulted. See for example the aforecited Makhoul, et al. reference, page 1576. 
     SUMMARY OF THE INVENTION 
     It is an object of the invention to provide a data compression method and apparatus which reduces the memory, computation, and hardware requirements without correspondingly reducing the performance and accuracy of the operations being carried out on the data. 
     It is a further object of the invention to provide such a method and apparatus which utilizes multistage vector quantization to achieve more reliable and accurate data compression and data reconstruction. 
     It is an additional object of the invention to provide a method and apparatus for constructing and searching codebooks used in a multistage vector quantization system. 
     It is also an object of the invention to provide such methods and apparatus which may be utilized with a wide range of source vector sizes and codebook sizes, and with varying numbers of stages. 
     The above and other objects of the invention are realized in a specific illustrative embodiment of a system and method for operating upon input data sequences. Included in this embodiment is an encoder for receiving each input sequence, with the encoder comprising two or more quantizer stages, each having a memory for storing an established set of codewords preselected such that the sum of different combinations of codewords, one from each stage, is representative of likely to occur input data sequences, each codeword of each stage having a respective index associated therewith. The encoder operates to select a codeword from at least two of the stages such that the sum of the selected codewords is a closer match to each input sequence than any other sum of codewords formed from the selected stages, and to retrieve the selected codewords&#39; indices. These indices may then be transmitted to another location, stored in memory or otherwise processed. 
     The illustrative embodiment also includes a decoder coupled to the transmission channel, memory, or other mechanism which operates upon the indices. This decoder, in turn, includes a decoder memory for storing the established set of codewords with respective indices, a retrieval device for retrieving from the decoder memory the codewords whose respective indices were transmitted, stored or otherwise processed, and a summing mechanism for adding the retrieved codewords to produce a reproduction data sequence representing an approximation of a corresponding input data sequence. 
     The established sets of codewords are determined by 
     1. Storing a training set of data sequences statistically representative of likely to occur input data sequences; 
     2. Storing current sets of codewords, one set for each stage of the encoder; 
     3. Forming equivalent codewords by adding together different combinations of one codeword from each current set, each equivalent codeword thus being comprised of the sum of a unique combination of constituent codewords; 
     4. Forming subsets of the training set of data sequences, one for each equivalent codeword, including in each subset those training set data sequences which match the associated equivalent codeword more closely than they do any other equivalent codeword; 
     5. Computing and storing a first distortion measure between the training set data sequences and their closest equivalent codewords; 
     6. Establishing the current sets of codewords as the established sets of codewords if the distortion measure is less than a predetermined threshold, and the number of stages and number of current codewords equal predetermined values, otherwise continuing to the next step; 
     7. Augmenting the current sets of codewords by storing new current codewords in existing sets of codewords in existing stages and in new sets of codewords in new stages, if the distortion measure is less than the predetermined threshold but the number of stages and number of codewords are less than the predetermined values, and returning to step 3, otherwise continuing to the next step; 
     8. For each stage, replacing the current set of codewords with a computed set of codewords, each computed set being formed for each current codeword of the corresponding stage by 
     (a) selecting all equivalent codewords of which each current codeword is a constituent, each current codeword thus associating with a corresponding group of equivalent codewords and their associated subsets of training sequences, 
     (b) subtracting from each training sequence of the associated subsets of each current codeword the difference of the associated subset&#39;s corresponding equivalent codeword and each current codeword to thereby form a set of residual training sequences, 
     (c) averaging the set of residual training sequences to form a computed codeword, 
     (d) replacing the current codeword by the computed codeword; 
     9. Forming new equivalent codewords from the computed codewords, and computing and storing a second distortion measure between the new equivalent codewords and the existing training sequences of the corresponding associated subsets; and 
     10. Returning to step 4 if the second distortion measure is less than a second predetermined threshold, otherwise repeating step 8. 
     With the sets of codewords thus obtained, an efficient and accurate data compression system, using multistage vector quantization, is obtained. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The above and other objects, features and advantages of the invention will become apparent from a consideration of the following detailed description presented in connection with the accompanying drawings in which: 
     FIG. 1 shows an exemplary multistage vector quantization system made in accordance with the principles of the present invention; 
     FIGS. 2A and 2B are flow diagrams illustrating the method of deriving codebooks for use with the present invention; and 
     FIG. 3 is a glossary defining the terms and designations used in the FIGS. 2A and 2B flow charts. 
    
    
     DETAILED DESCRIPTION 
     Referring to FIG. 1, there is shown a multistage vector quantization system utilizing codebooks and code vectors or codewords constructed in accordance with the principles of the present invention. A source 4 produces a series of digital input data sequences or source vectors representing, for example, radar return signals, coded image signals, coded speech signals, and the like. The input data sequences are supplied to an encoder 8 which includes a microprocessor 12 (labeled VQ), and multiple vector quantization stages with code book memories 20, 24, etc. The microprocessor 12 forms equivalent codewords or code vectors from constituent codewords or code vectors retrieved from each of the memories 20, 24, etc., and stores the equivalent codewords in a memory 16. The equivalent codewords are formed by adding together the different combinations of one codeword from each of the codebook memories. The microprocessor 12 compares each source vector with each of the equivalent codewords and retrieves from the codebook memories indices identifying the constituent codewords of the equivalent codeword which most closely matches the said each source codeword. 
     All of the codewords stored in the memories 20, 24, etc. have corresponding identifying indices associated therewith, which indices are much shorter in length (fewer bits) than the codewords they identify. 
     The codeword indices retrieved by the microprocessor 12 are supplied to a channel 32 and transmitted to a decoder 48 which includes multiple stages 52a, 52b, etc. In particular, each index transmitted over the channel 32 is supplied to a corresponding codebook read only memory (ROM) such as ROM 56, ROM 60, etc. Stored in each ROM are the codewords stored in a corresponding codebook memory of the encoder 8. For example, the same codewords stored in codebook memory 24 are also stored in ROM 56, and the same codewords stored in codebook memory 44 are also stored in ROM 60, etc. Upon receipt of an index, a ROM supplies to a summing circuit 64 the codeword identified by the index. Thus, a number of codewords corresponding to the number of stages are supplied to the summing circuit 64 which simply adds the codewords together to produce a reproduction data sequence representing an approximation of a corresponding input data sequence. The reproduction data sequence is supplied to a sink 68 representing some type of utilization device. 
     The data compression, of course, occurs through the process of vector quantization and transmission of indices representing much longer codewords. That is, the input data sequences are &#34;compressed&#34; to the size of a composite of the indices transmitted for that data sequences. 
     FIGS. 2A and 2B show a flow diagram of a process for determining the codewords or code vectors for the codebooks of a P-stage residual vector quantization system (such as in FIG. 1), where the ultimate desired number of code vectors for the pth stage is N p , where N p  &gt;1 for 0≦p≦P-1, all in accordance with the present invention. FIG. 3 is a glossary of terms and symbols used in the flow diagram of FIGS. 2A and 2B. The criteria for whether the desired codebook code vectors have been constructed will be based upon E, a predetermined distortion threshold level for use in optimizing both the encoder and decoder, and Ed, a predetermined distortion threshold level for use in optimizing the decoder only. (&#34;Distortion&#34; is the variation between one signal and another; various distortion measures may be used in signal processing, probably the most commonly used being the mean-squared error distortion measure.) The number of desired stages may be dictated by the memory available for performing the vector quantization. For example, if less memory is available, then more stages with smaller codebooks may be used. The number of code vectors per stage (codebook size) is determined by the compression ratio desired--the smaller the codebook size, the greater will be the compression ratio and vice versa. 
     The first step in the codebook construction process is to select and store a source training set of data sequences {x l   o  ; 1≦l≦L}. (See box 104 of FIG. 2A.) The training set sequences or vectors are the most statistically likely to occur sequences of those produced by the source 4 (FIG. 1). 
     The next step is to initialize certain parameters of the system (box 108) by setting m=-1, where m is the iteration count for the process of joint optimization of the encoder and decoder, setting D m  =-1=oo, and N c   p  =1, where N c   p  represents the number of code vectors currently existing for the pth stage. 
     In a decision step 112 (FIG. 2A), a determination is made as to whether N c   p  =N p . If it does, the process halts, if it does not (which would be the case in the first iteration), then the process moves to box 116. There, m is incremented and for one or more stages, one or more nonzero &#34;seed&#34; code vectors are added to the selected stages, i.e., stored in memory in sections corresponding to the stages. The code vectors added to the stages could be randomly selected or could be chosen from among the training set of vectors. With the present process, the desired code vectors for filling the codebooks will be determined regardless of the initial code vectors selected. With the &#34;seed&#34; vectors added to the stages, the number of code vectors N c   p  that now exist for each stage is calculated. This number, of course, must not total more than the desired number of code vectors N p . Next, the number of current equivalent code vectors N c   e  is calculated as ##EQU1## 
     Equivalent code vectors are formed by adding together all combinations of one code vector from each stage (each codebook)--this yields A m   e  ={y je   3  ; 0≦je≦N e  }, (the equivalent codebook which exists at the mth iteration of the process), where y je   e  is the (je)th equivalent code vector of the equivalent codebook (box 120 of FIG. 2A). 
     Then, subsets of the source training set of vectors previously selected and stored (box 104) are formed for each equivalent code vector, with each subset of an equivalent code vector containing those training set vectors which are closer to the subset&#39;s equivalent code vector than to any other equivalent code vector. This is shown in box 124 as &#34;determine P v   e  (A m   e )&#34; which equals {S j   e  e; 0≦je≦N e  }, the so-called Voronoi partition with respect to the equivalent codebook A m   e , where S j   e  e is the (j e ) th  partition cell or subset of the subdivided source training set of vectors. 
     During the partitioning of the training set of vectors, the distortion between the source training set of vectors of each subset and their closest equivalent code vector is calculated as the residual set {x l   P  : x l   P  =x l   o  -y j   e  e for 1≦l≦L}. The average distortion is then calculated as ##EQU2## (see box 124). 
     A decision is next made (box 128) as to whether the rate of change of the average distortion is less than or equal to E, i.e., whether ##EQU3## If it is, the process returns to box 112, where it is determined whether the desired number of code vectors have been developed. If so, the process halts, otherwise it continues to box 116. If, in box 128, the decision is &#34;no&#34;, then the process moves to box 132 for decoder optimization. This begins in box 136 of FIG. 2B, where the following are initialized: set n=o, D n   d  =Dm, and p=-1, where n is the iteration count for the process of decoder only optimization (FIG. 2B), D n   d  is the average distortion after the n th  iteration of the FIG. 2B process and Dm is the average distortion after the m th  iteration of the FIG. 2A process. 
     Next increment p (iterate through each stage) and set j p  =-1 (box 140). Then increment j p  (box 144) (iterate through the code vectors of each stage). Now determine the so-called conditional graft residual subset of {U l   p  } of y j   p  p, defined as {U l   p  :U l   p  =x l   o  -(y j   e  e-y j   p  p)=x l   p  +y j   p  p if x l   o  in s j   e  e for any l in {1, 2, . . . , L} and y j   e  e contains y j   p  p as a constituent for any j e  in {1, 2, . . . , N e ), with definitions of the various symbols given in FIG. 3. This step, performed in box 148, comprises selecting all equivalent code vectors of which each current code vector is a constituent (used to calculate the equivalent code vectors)--thus each current code vector is associated with a group of equivalent code vectors of which the code vector is a constituent, and each equivalent code vector, in turn, is associated with a subset of training set vectors which most closely match the equivalent code vector. The difference between an equivalent code vector and said each constituent current code vector is then subtracted from each training set vector of the subset associated with each current code vector, to thereby form a corresponding &#34;graft&#34; residual set. 
     The centroid y j   C  p of the graft residual subset {U l   p  with l in Ljp} is then calculated (box 152), where Ljp is the set of training set vector indicies used to form the graft residual set of Y j   p  p. This centroid is the average of the graft residual set for each current code vector, and such current code vector is replaced with the corresponding centroid (box 156). The new code vector y j   p  p=y j   C  p (the centroid of the graft residuals of the (j p ) th  code vector) is then subtracted from its corresponding graft residual vectors {U l   p  } to form a new set of total residual vectors {x l   P  :x l   p  =U l   p  -y j   C  p for all l in Ljp}. 
     If j p  is less than N p  (box 164), meaning that the last code vector of the stage has not yet been replaced, the process returns to box 144, otherwise the process moves to the next step (box 168). If p is less than P-1 (box 168), meaning that the last stage of current code vectors has not been replaced, then the process returns to box 140, otherwise the process moves to the next step. Here (box 172), n is incremented and the decoder distortion D d  is calculated again. At this point, the process moves to box 176 of FIG. 2A. 
     At box 176, a determination is made as to whether (D.sub.(n-1) d  -D n   d )/D n  is less than or equal to E d . If not, p is set equal to -1 and the process returns to box 140 of FIG. 2B, otherwise the process moves to box 180. 
     Of course, the above-described process is repeated until optimum codebooks, according to the present invention, are obtained and the process is halted at box 114 of FIG. 2A. The process described above may be carried out on a Hewlett-Packard 350 Work Station. 
     The codebooks constructed using the present invention may be used with any multistage vector quantization system. Such codebooks enable improvement of performance and accuracy in carrying out data compression, and with a reduction in memory size. 
     It is to be understood that the above-described arrangements are only illustrative of the application of the principles of the present invention. Numerous modifications and alternative arrangements may be devised by those skilled in the art without departing from the spirit and scope of the present invention and the appended claims are intended to cover such modifications and arrangements.