Frame-to-frame compression of vector quantized signals and other post-processing

• US 5,124,791 A
• Filed: 05/31/1989
• Issued: 06/23/1992
• Est. Priority Date: 05/31/1989
• Status: Expired due to Term

• Current Assignee: Utah State University Foundation UMC
• Original Assignee: Utah Valley University
• Inventors: Israelsen, Paul D., Harris, Richard W.
• Primary Examiner(s): Kostak, Victor R.
• Application Number:
  US07/359,496
• Time in Patent Office: 1,119 Days
• Field of Search: 358/135, 358/136, 358/133, 358/105, 358/261.1, 358/261.3, 358/426, 358/432, 341/106, 341/65, 364/570, 375/122, 375/27, 375/30, 382/56, 370/118, 381/30, 381/31
• US Class Current: 375/240.12
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 7/10 Adaptations for transmission by electrical cable H04N7/12 takes precedence
• CPC Class Codes: H04N 7/20 Adaptations for transmission via a GHz frequency band, e.g. via satellite

Abstract

Post-quantization processing is disclosed in which frames of data are organized into frames of input vectors. For each input vector, the quantizer identifiers a closely matching codebook vector. The quantizer generates a compressed signal by replacing each input vector in a frame with an ID code of a closely matching codebook vector. On subsequent frames, the quantizer further processes ID codes to achieve additional compression. In one embodiment, the ID codes from one frame are compared to the corresponding ID codes in the previous frames. If the ID code from the subsequent frame (new ID code) is the same as the corresponding ID code from the previous frame (old ID code), the new ID code is eliminated from the frame and a tag bit is set to indicate that the ID Code was eliminated. Similarly, if the new ID code represents a vector which is only slightly different from the vector represented by the old ID code, the new ID code is replaced with a tag bit. In this way, transmission of the subsequent frames requires only the transmission of vectors which differ by a significant amount from the prior frame. In other embodiments, other post processing methods are used. For example, lossless coding techniques, such as the socalled Lempel-Ziv and Huffman codes are discussed.

Claims

1. A method for compressing data for use with a codebook of vectors, the method comprising the steps of:

(a) arranging the data into a plurality of discrete frames;

(b) vector quantizing each of said data frames; and

(c) performing post-quantization compression on the vector quantized data, said post-quantization compression comprising representation of differences between adjacent frames.

2. A method in accordance with claim 1 wherein the step of interframe compression comprises the steps of:

(a) organizing the data into an ordered series of input vectors and organizing the vectors into at least two frames such that a vector from any frame has a logical correspondence to a vector from each preceeding frame,

(b) generating identification codes of codebook vectors which closely match the input vectors,

(c) modifying a vector ID code if its distortion relative to the corresponding vector in a prior frame is less than a threshold amount.

3. A method in accordance with claim 2 further comprising the step of:

setting a code in a frame, said code indicating the position in the frame where an identification code has been modified.

4. A method in accordance with claim 2 wherein the step of modifying a vector comprises the steps of:

(a) performing a table look-up of distances from a table based in identification code,

(b) comparing the distance to a threshold, and

(c) eliminating the identification code from the frame if the distance is less than a threshold.

5. A method in accordance with claim 2 wherein the step of generating identification codes comprises the steps of:

(a) indentifying a reference codebook vector, A_j, which satisfies a first criterion,

(b) identifying a subset, S, of codebook vectors for which the distance between the reference codebook vector, A_j, and each codebook vector of the subset S satisfies a second criterion,

(c) selecting a codebook vector from the subset S which closely matches the input vector.

6. A method in accordance with claim 2 wherein the step of generating identification codes comprises the steps of:

(a) simultaneously computing distance values between an input vector and a plurality of codebook vectors, and

(b) identifying the smallest distance value.

7. An apparatus for use with a codebook of vectors for compressing data comprising:

(a) interface means responsive to the data for organizing the data into an ordered series of vectors and for organizing the vectors into at least two frames such that a vector from a succeeding frame has a logical correspondence to a vector from a preceeding frame,

(b) vector quantizer means responsive to the series of input vectors for generating identification codes of codebook vectors which closely match the input vectors, and

(c) interframe compressor means responsive to the frames of identification codes for modifying a vector ID code if its distortion relative to the corresponding vector in a prior frame is less than a threshold amount.

8. An apparatus in accordance with claim 7 wherein the interframe compressor means additionally inserts a code into a frame, said code indicating the position in the frame where an identification code has been modified.

9. An apparatus in accordance with claim 7 further comprising:

storage means responsive to the interframe compressor means for storing a table of vector distances between codebook vectors and for indicating to the interframe compressor the distances between codebook vectors.

10. A system for use with a codebook of vectors and input vectors for compressing and restoring data comprising:

(a) vector quantizer means responsive to the input vectors for generating identification codes of codebook vectors which closely match the input vectors,

(b) interframe compression means responsive to the frames of identification codes for modifying a vector ID code if the vector'"'"'s distortion relative to the corresponding vector in a prior frame is less than a threshold amount,

(c) interframe expansion means responsive to the interframe compression means for restoring identification codes which had been modified by the interframe compression means,

(d) decoder means responsive to the regenerated frames of identification codes for regenerating frames of data.

11. A system in accordance with claim 10 wherein the interframe compressor means comprises means for setting a code in a frame, said code providing an indication as to the position in the frame where an identification code has been modified.

12. A system in accordance with claim 10 further comprising:

storage means responsive to the interframe compressor means for storing a table of vector distances between codebook vectors and for indicating to the interframe compressor the distances between codebook vectors.

13. A system in accordance with claim 10 further comprising:

storage means responsive to the interframe compression means for receiving frames of identification codes from the interframe compression mean at one time and for regenerating frames of identification codes at another time.

14. A system in accordance with claim 10 further comprising:

communication means responsive to the interframe compression means for communicating frames of identification codes from the interframe compression means to the interframe expansion means.

15. A method for use with a codebook of vectors for compressing data comprising the steps of:

(a) expressing the data as a series of identification codes of closely matching codebook vectors, each identification code comprising a string of one or more symbols,

(b) for a first sequence of symbols in the series of symbols, identifying a second sequence of symbols which is identical to the first sequence and which precedes the first sequence in the series,

(c) representing the first sequence with a code which indicates the position of the second sequence in the series of symbols.

16. A method in accordance with claim 15 wherein the step of expressing the data as a series of identification codes includes the steps of:

(a) indentifying a reference codebook vector, A_j, which satisfies a first criterion,

(b) identifying a subset, S, of codebook vectors for which the distance between the reference codebook vector, A_j, and each codebook vector of the subset S satisfies a second criterion,

(c) selecting a codebook vector from the subset S which closely matches the input vector.

17. A method in accordance with claim 15 wherein the step of expressing the data as a series of identification codes includes the steps of:

(a) simultaneously computing distance values between an input vector and a plurality of codebook vectors, and

(b) identifying the smallest distance value.

18. A method for compressing data for use with a codebook of vectors, the method comprising the steps of:

(a) arranging the data into at least two frames;

(b) expressing the data as a series of input vectors;

(c) identifying codebook vectors which closely match the input vectors; and

(d) representing each frame as a series of identification codes of closely matching codebook vectors, said identification codes being selected such that the identification code of a more frequently identified codebook vector is shorter than the identification code of a less frequently identified codebook vector, wherein said codebook vector identification step comprises the steps of;

(i) identifying a reference codebook vector, A_j, which satisfies a first criterion;

(ii) identifying a subset, S, of codebook vectors for which the distance between the reference codebook vector, A_j, and each codebook vector of the subset S satisfies a second criterion; and

(iii) selecting a codebook vector from the subset S which closely matches the input vector.

19. A method for compressing data for use with a codebook of vectors, the method comprising the steps of:

(a) arranging the data into at least two frames;

(b) expressing the data as a series of input vectors;

(c) identifying codebook vectors which closely match the input vectors; and

(d) representing each frame as a series of identification codes of closely matching codebook vectors, said identification codes being selected such that the identification code of a more frequently identified codebook vector is shorter than the identification code of a less frequently identified codebook vector, wherein said codebook vector identification step comprises the steps of;

(i) simultaneously computing distance values between an input vector and a plurality of codebook vectors; and

(ii) identifying the smallest distance value.