Sample-adaptive product quantization

• US 6,826,524 B1
• Filed: 07/07/2000
• Issued: 11/30/2004
• Est. Priority Date: 01/08/1998
• Status: Expired due to Fees

• Current Assignee: Purdue Research Foundation (Purdue University)
• Original Assignee: Purdue Research Foundation (Purdue University)
• Inventors: Kim, Dong Sik, Shroff, Ness B.
• Primary Examiner(s): Knepper, David D.
• Application Number:
  US09/612,579
• Time in Patent Office: 1,607 Days
• Field of Search: 704/220-223, 375/240.14, 382/253
• US Class Current: 704/200
• CPC Class Codes: G06T 9/008 Vector quantisation

Abstract

A technique to encode a group of vectors by quantizing the group with each of a number of different codes (44) and selecting the quantization results which are most favorable. This technique may include providing several vectors to an encoder (40) of a communication system (20) and quantizing each of the vectors with a number of different codebooks (44) to generate a corresponding number of codeword sets with the encoder (40). The codeword sets are each representative of the vectors. Each of the codeword sets is evaluated by determining a corresponding distortion value. The codeword set with the lowest distortion is selected to encode the vectors based on this evaluation. The codebook (44) or sequence of codebooks (44) used to generate the selected codeword set may differ from one vector sample to the next to provide a sample adaptive coding scheme. Transmission of the encoded data to a decoder (50) of communication system (20) may also be performed where the original vectors are reconstructed.

Claims

1. A method of encoding an audio or image signal, comprising:

operating a communication system including an audio or image input device and an encoder;

providing several ordered vectors for encoding by the encoder;

quantizing said vectors with a first ordered group of codebooks to generate a first ordered set of codewords representative of said vectors;

quantizing said vectors with a second ordered group of codebooks to generate a second ordered set of codewords representative of said vectors;

evaluating said first and second ordered codeword sets by determining a corresponding performance characteristic for each set; and

selecting one of the ordered codeword sets to encode the vectors based on said evaluating.

2. The method of claim 1 wherein said evaluating includes calculating the performance characteristic for each of the codeword sets as a function of a number of codewords in a corresponding one of the codeword sets.

3. The method of claim 1 wherein the performance characteristic corresponds to a measure of distortion.

4. The method of claim 1 wherein the communication system includes a decoder and defines a communication channel between the encoder and the decoder, and further comprising:

transmitting data corresponding to the one of the codeword sets with the encoder over a channel to a decoder; and

decoding the data with the decoder to provide at least one signal representative of the vectors.

5. The method of claim 1 wherein the data includes a value representing one of the codebooks used to generate the one of the codeword sets corresponding to the data.

6. The method of claim 1 wherein said quantizing includes applying the different codebooks in a number of different sequences relative to a predetermined order of the vectors.

7. The method of claim 1 wherein the performance characteristic for each of the codeword sets corresponds to the equation:

$\frac{1}{m}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{i=1}{\overset{m}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{<br><br>X_i^{\mathrm{\omega <br><br>}}-Q_{C_n^i}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(X_i^{\mathrm{\omega <br><br>}}\right)<br><br>}^r.$

where;

X^ω

_i represents the vectors, m represents the number of vectors, Q_Cn represents the quantization function using code C_n belonging to the class of n-level codes having a real value in a vector space of the vectors, r is the rth power of the ² norm function, and i is a summation index.

8. The method of claim 1 wherein the encoder is provided by a single integrated circuit chip.

9. A method of encoding an audio or image signal, comprising:

operating a communication system including an audio or image input device and an encoder;

providing an ordered group of vectors to the encoder for quantizing sequentially;

generating a number of ordered codeword sets each representative of the same group of vectors, the codeword sets each corresponding to a vector quantization using a different sequential arrangement of codebooks relative to the order of the vectors in the group;

evaluating each of the ordered codeword sets by determining a corresponding performance characteristic for each set; and

selecting one of the ordered codeword sets to encode the group based on said evaluating.

10. The method of claim 9 wherein the performance characteristic corresponds to a measure of distortion.

11. The method of claim 9 wherein the communication system includes a decoder coupled to the encoder by a communication channel, and further comprising:

transmitting data corresponding to the one of the codeword sets with the encoder over the channel to the decoder of the communication system; and

decoding the data to provide at least one signal representative of the vectors.

12. The method of claim 9 wherein the data includes a value representing one of the codebooks used to generate the one of the codeword sets corresponding to the data.

13. The method of claim 9 wherein the different codebooks number at least four.

14. The method of claim 9 wherein the encoder is provided by a single integrated circuit chip.

15. A method of encoding an audio or image signal, comprising:

providing a communication system including an audio or image input device and an encoder with a number of different codebooks;

establishing an ordered group of vectors based on an audio or image input;

quantizing each of the vectors of the ordered group using respective codebooks from first and second ordered groups of codebooks to provide first and second ordered codeword sets each representative of the group of vectors;

evaluating distortion of each of the first and second ordered codeword sets; and

selecting the ordered codeword set having less distortion than any other of the codeword sets to encode the group of vectors with the encoder.

16. The method of claim 15 wherein said evaluating includes determining a performance characteristic for each of the codeword sets.

17. The method of claim 15 wherein said evaluating includes calculating the performance characteristic for each of the codeword sets as a function of a number of codewords in a corresponding one of the codeword sets.

18. The method of claim 15 further comprising:

transmitting data corresponding to the one of the codeword sets with the encoder over a channel to a decoder of the communication system; and

decoding the data with the decoder to provide at least one signal representative of the vectors.

19. The method of claim 15 wherein the data includes a value representing one of the codebooks used to generate the one of the codeword sets corresponding to the data.

20. The method of claim 15 further comprising empirically determining a property of the vectors corresponding to a distribution function.

21. The method of claim 15 wherein said quantizing includes applying the different codebooks in a number of different sequences relative to a predetermined order of the vectors.

22. The method of claim 15 wherein the encoder is provided by a single integrated circuit chip.

23. A communication system, comprising:

an audio or image input device;

an encoder coupled to said input device;

a decoder coupled to said encoder by a communication channel; and

an audio or image output device coupled to said decoder,

wherein said encoder includes;

a number of different ordered groups of codebooks;

a number of quantizers each configured to receive a common set of vectors for quantization with a different one of said ordered groups of codebooks to provide a corresponding ordered codeword set representative of said set of vectors, said quantizers each providing a perfomance signal characterizing distortion of said corresponding codeword set;

a comparator responsive to said performance signals to generate a selection signal corresponding to a selected one of said quantizers providing said corresponding codeword set with lowest distortion; and

a multiplexor responsive to said selection signal to transmit data to said decoder along said communication channel representative of said corresponding codeword set for said selected one of said quantizers.

24. The apparatus of claim 23 wherein said performance signals each correspond to a measure of distortion of said corresponding codeword set.

25. The apparatus of claim 23 wherein each of said quantizers provides a different sequential arrangement of said codebooks relative to a predetermined order of said vectors.

26. A sample-adaptive product quantizer, comprising:

an audio or image input device adapted to convert an input signal to vector data; and

an encoder having an input configured to receive vector data from said input device and an output for transmitting codeword indices and a codebook group index corresponding to said vector data, said encoder including a number of different codebooks and defining first and second ordered groups thereof, said encoder being responsive to said vector data to define a group of vectors from said vector data and quantize each of said vectors of said group using respective codebooks from said first and second ordered groups to provide first and second ordered codeword sets each representative of said group of vectors, said encoder being configured to calculate distortion of each of said ordered codeword sets and provide codeword indices to said output corresponding to the codewords in the codeword set having less distortion than any other codeword set, said encoder being further configured to provide an index for the ordered group of codebooks corresponding to the codeword set having less distortion than any other codeword set.

27. The system of claim 26 further comprising:

a communication channel coupled to said output of said encoder to receive said encoded data; and

a decoder coupled to said communication channel responsive to said encoded data to decode said encoded data and output at least one signal representative of said vectors.

28. The system of claim 27 wherein said decoder includes said different codebooks.

29. The system of claim 26 wherein said encoder is configured to empirically determine a property of said vectors of said group corresponding to a distribution function.

30. The system of claim 26 wherein said codeword sets each correspond to a different sequential arrangement of said codebooks relative to a predetermined order of said vectors of said group.

31. The system of claim 26 wherein said encoder is provided by a single integrated circuit.

32. The system of claim 26 wherein said codebooks number at least as many as said vectors.