Method and apparatus for vector quantization by hashing

• US 4,979,039 A
• Filed: 01/30/1989
• Issued: 12/18/1990
• Est. Priority Date: 01/30/1989
• Status: Expired due to Fees

• Current Assignee: Peter Derrick Brown
• Original Assignee: Medi-Tech
• Inventors: Parker, James F., Kisor, Gregory H., King, Edward J.
• Primary Examiner(s): Kostak, Victor R.
• Application Number:
  US07/303,795
• Time in Patent Office: 687 Days
• Field of Search: 358/133, 358/135, 358/136, 358/11, 358/12, 358/432, 358/261-263, 341/106, 325/27, 325/122
• US Class Current: 375/240.22
• 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/94 Vector quantisation

Abstract

A method of and apparatus for vector quantization operates on binary signal vectors. Each signal vector contains a plurality of sample elements of a signal to be compressed. Each of the signal vectors is hashed to generate a value identifying one of at least three different subsets of code words collectively constituting a set of binary code words. Each code word is equal in length to the length of each of the signal vectors and has associated with it a unique binary code of a lesser length. The vector quantizer performs a distortion comparison search through the code words of the selected subset to identify the one code word and its uniquely associated code which has the least distortion of all of the code words of the one subset with respect to the hashed signal vector. That one code is outputted to represent the hashed signal vector. The subsets may be mutually exclusive and include a plurality of code words.

Claims

1. A vector quantizer for data compression of a signal represented by a plurality of binary signal vectors, each signal vector being of a predetermined length and including a plurality of individual sample elements of the signal to be compressed, comprising:

hashing means for hashing each signal vector to generate a value identifying one of at least three different predetermined subsets of predetermined code words, each code word having a length equal to the predetermined length of the signal vectors and each code word having a unique associated binary code, each of the codes having a length less than the predetermined length of the signal vectors and code words; and

output means for outputting from the vector quantizer a code associated with one code word of the one subset to represent the hashed signal vector, the one code word having the least distortion with respect to the hashed signal vector of all of the code words of the one subset.

2. The vector quantizer of claim 1 further comprising:

code book means for storing the at least three different subsets; and

comparison means for comparing the hashed signal vector with each code word of the one subset to determine a distortion between the hashed signal vector and each code word of the one subset and for comparing the distortions to identify the one code word of the one subset having the least distortion with respect to the hashed signal vector.

3. The vector quantizer of claim 1 wherein the hashing means selects sample elements from each signal vector, combines the selected sample elements and scales the combination of the selected sample elements to generate the value identifying the one subset of code words.

4. The vector quantizer of claim 3 wherein the sample elements of each signal vector are pixels of a video signal to be compressed, the pixels of each signal vector adjoining one another in a matrix portion of a two-dimensional array of the pixels, the array corresponding to an image frame of the video signal.

5. The vector quantizer of claim 4 further comprising means for averaging pixels adjoining one another in portions of an original, two-dimensional array of the pixels corresponding to the image frame of the video signal to generate a two-dimensional array of averaged pixels and wherein the hashing means operates on the averaged pixels.

6. The vector quantizer of claim 5 wherein the averaged pixels are generated from at least one of an I and a Q color difference components of a composite color video signal to be compressed.

7. The vector quantizer of claim 1 wherein the subsets are mutually exclusive.

8. The vector quantizer of claim 1 wherein each subset includes a plurality of code words.

9. A method for compressing data of a signal by vector quantization, the signal being represented by a plurality of binary signal vectors, each signal vector having a predetermined length and including a plurality of individual sample elements of the signal to be compressed, comprising the steps of:

hashing each signal vector to generate a value identifying one of at least three different predetermined subsets of predetermined code words, each code word having a length equal to the predetermined length of the signal vectors and each code word having a unique associated binary code, each of the codes having a length less than the predetermined length of the signal vectors and code words; and

outputting a code associated with one of the code words of the one subset to represent the hashed signal vector, the one code word having the least distortion with respect to the hashed signal vector of all of the code words of the one subset.

10. The method of claim 9 further comprising the step of transmitting a plurality of the binary codes as a compressed representation of the signal, each code representing one of the plurality of binary signal vectors.

11. The compressed signal transmitted by the method of claim 10.

12. The method of claim 9 wherein the subsets are mutually exclusive.

13. The method of claim 12 wherein each subset includes a plurality of code words.

14. The method of claim 9 wherein the one subset includes a plurality of code words and further comprising the steps of:

storing the at least three different subsets of code words;

comparing the hashed signal vector with each code word of the one subset to determine a distortion between the hashed signal vector and each code word of the one subset; and

comparing the distortions to identify the one code word of the one subset having the least distortion with respect to the hashed signal vector.

15. The method of claim 14 wherein said hashing step comprises the steps of:

selecting sample elements from the signal vector being hashed;

combining the selected sample elements; and

scaling the combination of selected sample elements to generate the value identifying the one subset of code words.

16. The method of claim 15 wherein the sample elements of each hashed signal vector are pixels of a video signal to be compressed, the pixels of each signal vector adjoining one another in a matrix portion of a two-dimensional array of the pixels, the array corresponding to an image frame of the video signal.

17. The method of claim 16 further comprising the step of transmitting a plurality of the binary codes as a compressed representation of the signal, each code representing one of the plurality of binary signal vectors.

18. The compressed signal transmitted by the method of claim 17.

19. The method of claim 16 further comprising the preliminary step of averaging adjoining subsets of the pixels of the two-dimensional array to generate a two-dimensional array of averaged pixels and wherein the hashing step comprises selecting averaged pixels from the signal vectors.

20. The method of claim 16 wherein the averaged pixels are generated from a two-dimensional array of pixels from at least one of an I and a Q color difference components of a composite color video signal to be compressed.

21. A method of compressing data of a signal by vector quantization comprising the steps of:

generating a plurality of binary sample vectors from a sample signal similar to the signal to be compressed, each sample vector having a predetermined length and including a plurality of individual sample elements of the sample signal;

generating a set of binary code words from the plurality of sample vectors, each of the code words having a length equal to the predetermined length of the sample vectors to represent vectors of the predetermined length to be generated from the signal to be compressed;

generating a hashing function from the set of code words, the hashing function dividing the set of code words into at least three different subsets of code words; and

storing the code words and the hashing function for future compression of the signal.

22. A method of compressing data of a signal by vector quantization comprising the steps of:

generating a plurality of binary sample vectors from a sample signal similar to the signal to be compressed, each sample vector having a predetermined length and including a plurality of individual sample elements of the sample signal;

generating a hashing function from the plurality of sample vectors, the hashing function dividing the plurality of sample vectors into at least three different subsets of code words;

generating at least one binary code word from each of the subsets, each of the code words having a length equal to the predetermined length of the sample vectors to represent binary vectors of the predetermined length to be generated from the signal to be compressed; and

storing the code words and the hashing function for future compression of the signal.

23. A method of compressing data of a signal by vector quantization comprising the steps of:

generating a plurality of binary sample vectors from a sample signal similar to the signal to be compressed, each sample vector having a predetermined length and including a plurality of individual sample elements of the sample signal;

simultaneously hashing the sample vectors to divide the sample vectors into at least three different subsets and identifying from each of the subsets the most commonly occurring sample vectors as the code words of the subset;

storing the code words and the hashing function for future compression of the signal.

24. A vector quantizer for data compression of a signal represented by a plurality of binary signal vectors, each signal vector being of a predetermined length and including a plurality of individual sample elements of the signal to be compressed, comprising:

hashing means for hashing each signal vector to generate a value identifying one of at least three different predetermined subsets of predetermined code words, each code word having a length equal to the predetermined length of the signal vectors and each code word having a unique associated binary code, each of the codes having a length less than the predetermined length of the signal vectors and code words; and

means for storing a plurality of the binary codes as a compressed representation of the signal, one binary code being stored for each hashed signal vector.

25. The vector quantizer of claim 24 further comprising:

code book means for storing the at least three different subsets; and

comparison means for comparing the hashed signal vector with each code word of the one subset to determine a distortion between the hashed signal vector and each code word of the one subset and for comparing the distortions to identify the one code word of the one subset having the least distortion with respect to the hashed signal vector.

26. The vector quantizer of claim 24 wherein the hashing means selects sample elements from each signal vector, combines the selected sample elements and scales the combination of the selected sample elements to generate the value identifying the one subset of code words.

27. The vector quantizer of claim 26 wherein the sample elements of each signal vector are pixels of a video signal to be compressed, the pixels of each signal vector adjoining one another in a matrix portion of a two-dimensional array of the pixels, the array corresponding to an image frame of the video signal.

28. The vector quantizer of claim 27 further comprising means for averaging pixels adjoining one another in portions of an original, two-dimensional array of the pixels corresponding to the image frame of the video signal to generate a two-dimensional array of averaged pixels and wherein the hashing means operates on the averaged pixels.

29. The vector quantizer of claim 24 wherein the subsets are mutually exclusive.

30. The vector quantizer of claim 29 wherein each subset includes a plurality of code words.

40. The method of claim 30 wherein the storing step comprises storing the plurality of binary codes in a single data storage element.

41. The data storage element of claim 40 storing the plurality of binary codes.

31. A method for compressing data of a signal by vector quantization, the signal being represented by a plurality of binary signal vectors, each signal vector having a predetermined length and including a plurality of individual sample elements of the signal to be compressed, comprising the steps of:

hashing each signal vector to generate a value identifying one of at least three different predetermined subsets of predetermined code words, each code word having a length equal to the predetermined length of the signal vectors and each code word having a unique associated binary code, each of the codes having a length less than the predetermined length of the signal vectors and code words; and

storing a plurality of the binary codes as a compressed representation of the signal, one binary code associated with one code word of the one subset of code words identified for each signal vector by the hashing step being stored for each hashed signal vector.

32. The method of claim 31 wherein the one subset includes a plurality of code words and further comprising the steps of:

comparing the hashed signal vector with each code word of the one subset to determine a distortion between the hashed signal vector and each code word of the one subset; and

comparing the distortions to identify the one code word of the one subset having the least distortion with respect to the hashed input vector.

33. The method of claim 31 wherein said hashing step comprises the steps of:

selecting sample elements from the signal vector being hashed,

combining the selected sample elements; and

scaling the combination of selected sample elements to generate the value identifying the one subset of code words.

34. The method of claim 31 wherein the sample elements of each hashed signal vector are pixels of a video signal to be compressed, the pixels of each signal vector adjoining one another in a matrix portion of a two-dimensional array of the pixels, the array corresponding to an image frame of the video signal.

35. The method of claim 34 further comprising the preliminary step of averaging adjoining subsets of the pixels of the two-dimensional array to generate a two-dimensional array of averaged pixels and wherein the hashing step comprises selecting averaged pixels from the signal vectors.

36. The method of claim 31 wherein the subsets are mutually exclusive.

37. The method of claim 36 wherein each subset includes a plurality of code words.

38. The method of claim 31 wherein the storing step comprises storing the plurality of binary codes in a single data storage element.

39. The data storage element of claim 38 storing the plurality of binary codes.