Lattice vector quantization in image compression and decompression

• US 6,728,413 B2
• Filed: 01/19/1999
• Issued: 04/27/2004
• Est. Priority Date: 01/19/1998
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Onno, Patrice
• Primary Examiner(s): Johnson, Timothy M.
• Application Number:
  US09/232,213
• Publication Number:
  US 20030072494A1
• Time in Patent Office: 1,925 Days
• Field of Search: 341/51, 341/52, 341/63, 341/106, 348/404.1, 348/405.1, 348/414.1, 348/417.1, 348/422.1, 358/261.2, 358/430, 375/240.02, 375/240.03, 375/240.22, 375/240.25, 382/232, 382/233, 382/238, 382/239, 382/251, 382/253
• US Class Current: 382/253
• 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: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

The invention proposes a method of determining an index of a code vector (VC_k) belonging to a predetermined lattice, characterised in that it includes the steps of:

determining (E47) a leader vector (Y, VL_k) for the code vector (VC_k),

seeking (E50, E51) a permutation number (NP) between the code vector and the leader vector,

determining (E51) the index (I_k) for the code vector according to the permutation number.

The invention makes it possible to code a code vector, for example in the context of the lattice vector quantization of a digital signal.

Claims

1. A method of coding an index representing a position of a code vector of a code vector dictionary on an isonorm, the index being included in a known group of indices, comprising the steps of:

determining a first number and a second number of bits which can be used to code an index, as a function of the number of indices in the group,

determining an even delimiter,

comparing the index with the delimiter,

coding the index decreased by half the delimiter, using the first number of bits, if the index is greater than or equal to the delimiter, and

coding the index using the second number of bits, if the index is less than the delimiter.

2. The method according to claim 1, wherein the determination of the first number of bits includes a calculation of the largest integer which is not larger than the logarithm to the base 2 of the number of indices in the group.

3. The method according to claim 1, wherein the determination of the second number of bits includes the calculation of the largest integer which is not larger than the logarithm to the base 2 of a number of indices in the group increased by one unit.

4. A method of coding an index representing a position of a code vector of a code vector dictionary on an isonorm, the index being included in a known group of indices, comprising the steps of:

determining a first number and a second number of bits which can be used to code an index, as a function of a number of indices in the group,

determining a delimiter,

comparing the index with the delimiter, in order to select the first number of bits or the second number of bits according to the result of the comparison, and

coding the index by using the first number of bits or the second number of bits according to the result of the selection.

5. The method according to claim 4, further comprising the steps of:

determining an even delimiter,

comparing the index with the delimiter,

coding the index decreased by half the delimiter, using the first number of bits, if the index is greater than or equal to the delimiter, and

coding the index using the second number of bits, if the index is less than the delimiter.

6. The method according to claim 4, wherein the delimiter depends on the number of indices contained in the group.

7. The method according to claim 4, wherein the determination of the first number of bits includes a calculation of the largest integer which is not larger than the logarithm to the base 2 of the number of indices in the group.

8. The method according to claim 4, wherein the determination of the second number of bits includes a calculation of the largest integer which is not larger than the logarithm to the base 2 of a number of indices in the group increased by one unit.

9. A device for coding an index representing a position of a code vector of a code vector dictionary on an isonorm, the index being included in a known group of indices, comprising:

means of determining a first number and a second number of bits which can be used for coding an index, as a function of a number of indices in the group,

means of determining an even delimiter,

means of comparing the index with the delimiter,

mean of coding the index decreased by half the delimiter, using the first number of bits, if the index is greater than or equal to the delimiter, and

means of coding the index using the second number of bits, if the index is less than the delimiter.

10. The device according to claim 9, adapted to determine the first number of bits by calculating the largest integer which is not larger than the logarithm to the base 2 of the number of indices in the group.

11. The device according to claim 9, adapted to determine the second number of bits by calculating the largest integer which is not larger than the logarithm to the base 2 of the number of indices in the group increased by one unit.

12. A device for coding an index representing a position of a code vector of a code vector dictionary on an isonorm, the index being included in a known group of indices, comprising:

means of determining a first number and a second number of bits which can be used for coding an index, as a function of a number of indices in the group,

means of determining a delimiter,

means of comparing the index with the delimiter, in order to select the first number of bits or the second number of bits according to a result of the comparison, and

means of coding the index by using the first number of bits or the second number of bits according to the result of the selection.

13. The device according to claim 12, adapted to determine the first number of bits by calculating the largest integer which is not larger than the logarithm to the base 2 of the number of indices in the group.

14. The device according to claim 12, adapted to determine the second number of bits by calculating the largest integer which is not larger than the logarithm to the base 2 of the number of indices in the group increased by one unit.

15. A device for coding a code vector included in a known group of code vectors, comprising:

means of determining a first number and a second number of bits which can be used to code a code vector, as a function of a number of code vectors in the group, and

means of allocating an integer index to the code vector,

means of determining an even delimiter,

means of comparing the integer index with the delimiter,

mean of coding the index decreased by half the delimiter, using the first number of bits, if the index is greater than or equal to the delimiter, and

means of coding the index using the second number of bits, if the index is less than the delimiter.

16. The device according to claim 15, further comprising means of determining the code vector, said means of determining the code vector comprising:

means of dividing a set of data into vectors;

means of vector quantization of a vector, using a known set of code vectors; and

means of determining a group of code vectors to which the code vector used for quantizing the vector belongs.

17. The device according to claim 15, adapted to determine a group of code vectors which includes the code vectors with a same norm.

18. The device according to claim 15, adapted to determine the first number of bits by calculating the largest integer which is not larger than the logarithm to the base 2 of the number of code vectors contained in the group.

19. The device according to claim 15, adapted to determine the second number of bits by calculating the largest integer which is not larger than the logarithm to the base 2 of the number of code vectors contained in the group increased by one unit.

20. A device for coding a code vector included in a known group of code vectors, comprising:

means of determining a first number and a second number of bits which can be used to code the code vector, as a function of a number of code vectors in the group, and

means of allocating an integer index to the code vector,

means of determining a delimiter,

means of comparing the index with the delimiter, in order to select the first number of bits or the second number of bits according to the result of the comparison, and

means of coding the vector by using the first number of bits or the second number of bits according to the result of the selection.

21. The device according to claim 20, further comprising means of determining the code vector, said means of determining the code vector comprising:

means of dividing a set of data into vectors;

means of vector quantization of a vector, using a known set of code vectors; and

means of determining a group of code vectors to which the code vector used for quantizing the vector belongs.

22. The device according to claim 20, adapted to determine a group of code vectors which includes the code vectors with a same norm.

23. The device according to claim 20, adapted to determine the first number of bits by calculating the largest integer which is not larger than the logarithm to the base 2 of the number of code vectors contained in the group.

24. The device according to claim 20, adapted to determine the second number of bits by calculating the largest integer which is not larger than the logarithm to the base 2 of the number of code vectors contained in the group increased by one unit.