Dimensional vector and variable resolution quantization

• US 7,680,670 B2
• Filed: 01/30/2004
• Issued: 03/16/2010
• Est. Priority Date: 01/30/2004
• Status: Expired due to Fees

• Current Assignee: Orange S.A.
• Original Assignee: Orange S.A.
• Inventors: Lamblin, Claude, Massaloux, Dominique, Virette, David, Kovesi, Balazs
• Primary Examiner(s): Smits; Talivaldis Ivars
• Assistant Examiner(s): BORSETTI, GREG
• Application Number:
  US10/587,907
• Publication Number:
  US 20070162236A1
• Time in Patent Office: 2,237 Days
• Field of Search: 704/500, 704/501, 704/E19.017, 704/E19.014, 704/222, 704/E19.033, 375/240, 375/241
• US Class Current: 704/500
• CPC Class Codes: G10L 19/097 using prototype waveform decomposition or prototype waveform interpolative [PWI] coders
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

The invention relates to compression coding and/or decoding of digital signals, in particular by vector variable-rate quantisation defining a variable resolution. For this purpose an impulsion dictionary comprises: for a given dimension, increasing resolution dictionaries imbricated into each other and, for a given dimension, a union of: a totality (D′i<N>) of code-vectors produced, by inserting elements taken in a final set (A) into smaller dimension code-vectors according to a final set of predetermined insertion rules (F1) and a second totality of code-vectors (Y′) which are not obtainable by insertion into the smaller dimension code vectors according to said set of the insertion rules.

Claims

1. A computer system for coding and decoding digital signals by vector quantization at variable rate defining a variable resolution, comprising:

a computer readable medium storing a dictionary comprising;

codevectors of variable dimension; and

inter-embedded sub-dictionaries of increasing resolution of a given dimension, wherein each sub-dictionary comprises a union of a) a first set consisting of codevectors constructed by inserting, into codevectors of dictionaries of lower dimension, elements taken from a finite set of real numbers according to a finite collection of predetermined insertion rules, and of b) a second set consisting of codevectors that may not be obtained by insertion into codevectors of lower dimension of the elements of said finite set according to said collection of insertion rules.

2. The computer readable medium as claimed in claim 1, wherein said collection of insertion rules is formulated on the basis of elementary rules consisting of inserting a single element of the finite set of real numbers in the guise of a component at a given position of a vector.

3. The computer readable medium as claimed in claim 2, wherein each elementary rule is defined by a pair of two positive integers representative of a rank of the element in said finite set, and of a position of insertion.

4. A method for operating a coding-decoding device having a processor by vector quantization at variable rate defining a variable resolution, comprising:

forming, using the processor, a dictionary comprising codevectors of variable dimension in which, for a given dimension, the method comprises;

a) forming a first set consisting of codevectors by performing an operation selected from the group consisting of inserting into and deleting from codevectors of dictionaries of dimension elements comprising at least one of lower and higher dimension elements taken from a finite set of real numbers according to a finite collection of predetermined operation rules selected from the group consisting of insertion rules and deletion rules,

b) constructing a first, intermediate, dictionary comprising at least said first set, for said given dimension, and

c) adapting said dictionary for use with at least one given resolution, wherein a second, definitive, dictionary is constructed, on the basis of the intermediate dictionary, by performing at least one of embedding and simplification of dictionaries of at least one of increasing and decreasing resolutions, the dictionaries of increasing resolutions being inter-embedded from the dictionary of smallest resolution up to the dictionary of greatest resolution.

5. The method as claimed in claim 4, in which, for a given dimension N, the method further comprising:

a0) obtaining an initial dictionary of initial dimension n, lower than said given dimension N,

a1) forming a first set consisting of codevectors of dimension n+i, where i is a non negative integer, by inserting into codevectors of the initial dictionary elements taken from a finite set of real numbers according to a finite collection of predetermined insertion rules,

a2) providing a second set consisting of codevectors of dimension n+i that may not be obtained by insertion into the codevectors of the initial dictionary of the elements of said finite set with said collection of insertion rules,

a3) constructing an intermediate dictionary, of dimension n+i comprising a union of said first set and of said second set, and

a4) repeating steps a1) to a3) at most N−

n−

1 times, with said intermediate dictionary in the guise of initial dictionary, up to said given dimension N.

6. The method as claimed in claim 5, in which N successive dictionaries of respective dimensions 1 to N are obtained on the basis of an initial dictionary of dimension p, through the repeated implementation of steps a1) to a3) for the dimensions p+1 to N, and through a repeated implementation of steps a′

1) to a′

3) that follow for the dimensions p−

1 to 1;

a′

1) constructing a first set, of dimension n−

i, where i is a non negative integer, by selecting and extracting of possible codevectors of dimension n−

i from the dictionary of dimension n, according to a finite collection of predetermined deletion rules,

a′

2) providing a second set consisting of codevectors of dimension n−

i, that may not be obtained by deletion, from the codevectors of the initial dictionary, of the elements of said finite set with said collection of deletion rules, and

a′

3) constructing an intermediate dictionary, of dimension n−

i comprising a union of said first set and of said second set.

7. The method as claimed in claim 4, in which said collection of operation rules is formulated on the basis of elementary rules consisting of performing the operation on a single element of the finite set of real numbers in the guise of component at a given position of a vector.

8. The method as claimed in claim 7, in which each elementary rule is defined by a pair of two positive integers representative of a rank of the element in said finite set, and of a position of the operation.

9. The method as claimed in claim 4, in which said finite set and said collection of operation rules are defined a priori, before constructing the dictionary by analysis of a source to be quantized.

10. The method as claimed in claim 9, in which said source is modeled by a learning sequence and the definition of said finite set and of said collection of operation rules is effected by statistical analysis of said source.

11. The method as claimed in claim 9, in which said finite set is chosen by estimation of a mono-dimensional probability density of said source.

12. The method as claimed in claim 9, in which:

a first set and a first collection of operation rules are chosen a priori by analysis of a learning sequence, so as to form one or more intermediate dictionaries,

at least one part of at least one of said first set and of said first collection of operation rules is updated by a posteriori analysis of said one or more intermediate dictionaries,

and, as appropriate, at least one part of the set of codevectors forming said one or more intermediate dictionaries is also updated.

13. The method as claimed in claim 4, in which said finite set and said collection of operation rules are defined a posteriori after construction of dictionaries by performing at least one of embedding and simplification of dictionaries of successive resolutions, followed by a statistical analysis of these dictionaries thus constructed.

14. The method as claimed in claim 13, further comprising:

choosing, a priori, a first set and a first collection of operation rules by analysis of a learning sequence, so as to form one or more intermediate dictionaries,

updating at least one part of said first set and/or of said first collection of operation rules by a posteriori analysis of said one or more intermediate dictionaries,

and, as appropriate, also updating at least one part of the set of codevectors forming said one or more intermediate dictionaries.

15. The method as claimed in claim 4, in which step c) comprises:

c′

0) obtaining an initial dictionary of initial resolution r_n, higher than said given resolution r_N,

c′

1) constructing, on the basis of the initial dictionary, an intermediate dictionary of resolution r<sub>n−

1</sub> lower than the initial resolution r_n, by partitioning of the initial dictionary into several subsets ordered according to a predetermined criterion, and

c′

2) repeating step c′

1) until the given resolution r_N is attained.

16. The method as claimed in claim 15, in which said predetermined criterion is chosen from among the cardinal of the subsets, an invoking of the subsets in a learning sequence, a contribution of the subsets to a total distortion or preferably to a decrease of this distortion.

17. The method as claimed in claim 15, in which said partition uses part at least of said operation rules.

19. The method as claimed in claim 4, further comprising storing in a memory said collection of operation rules, each identified by an index (l_r), and, for a given dimension:

said second set consisting of codevectors that may not be obtained by application of the operation to codevectors of at least one of lower and higher dimension than the given dimension according to said collection of operation rules,

as well as at least one correspondence table making it possible to reconstitute any codevector of the dictionary of given dimension, using the indices of the operation rules and indices identifying elements of said second set,

thereby making it possible to avoid the complete storage of the dictionary for said given dimension, by simply storing the elements of said second set and links in the correspondence table for access to these elements and to the associated operation rules.

20. The method as claimed in claim 19, in which the correspondence tables are formulated previously, for each index (m^j) of a codevector (x^j) of the dictionary (D^j_Nj) of given dimension (j) that may be reconstructed on the basis of elements of current indices (m′

) in the second set of current dimension (j′

), through a tabulation of three integer scalar values representing;

a current dimension (j′

) of said second set,

a current index (m′

) of an element of the second set, and

an operation rule index (l_r), this operation rule at least contributing to reconstitute said codevector (x_j) of the dictionary (D^j_Nj) of given dimension (j), by applying the insertion/deletion to the element of said current index (m′

) and of said current dimension (j′

).

31. A computer readable memory storing a computer program product intended to be stored in a memory of a processing unit, in particular of a computer or of a mobile terminal, or on a removable memory medium and intended to cooperate with a reader of the processing unit, wherein it comprises instructions for implementing the method according to claim 4.

18. A method for operating a coding-decoding device having a processor, comprising:

forming, using the processor, a dictionary comprising codevectors of variable dimension in which, for a given dimension N of codevectors, the method comprises;

constructing a first, intermediate, dictionary still of dimension N′

but of at least one of higher and lower resolution r_N on the basis of an initial dictionary of resolution r_n and of dimension N′

by performing at least one of embedding and simplification of dictionaries of at least one of increasing and decreasing resolutions, so as to substantially attain the resolution r_N of said first dictionary,

forming, to attain the given dimension N, a first set consisting of codevectors by performing an operation selected from the group consisting of inserting into and deleting from codevectors of the first dictionary of dimension N′

at least one of lower and higher than said given dimension N elements taken from a finite set of real numbers according to a finite collection of predetermined operation rules is constructed,

and subsequent to a possible step of definitive adaptation to the resolution r_N, constructing a second, definitive, dictionary comprising at least said first set for said given dimension N.

21. A method for operating a coding-decoding device having a processor by vector quantization at variable rate defining a variable resolution, comprising:

forming, using the processor, a dictionary comprising codevectors of variable dimension and, in which, for a given dimension;

a) forming a first set consisting of codevectors by performing an operation selected from the group consisting of inserting into and deleting from codevectors of dictionaries of dimension elements comprising at least one of lower and higher dimension elements taken from a finite set of real numbers according to a finite collection of predetermined operation rules,

b) constructing a first, intermediate, dictionary comprising at least said first set said given dimension,

c) adapting said dictionary for a use with at least one given resolution, wherein a second, definitive, dictionary is constructed, on the basis of the intermediate dictionary, by performing at least one of embedding and simplification of dictionaries of at least one of increasing and decreasing resolutions, the dictionaries of increasing resolutions being inter-embedded from the dictionary of smallest resolution up to the dictionary of greatest resolution;

in which, for a given dimension N;

a′

0) obtaining an initial dictionary of initial dimension n, higher than said given dimension N,

a′

1) constructing a first set, of dimension n−

i, where i is a non negative integer, by selecting and extracting of possible codevectors of dimension n−

i from the dictionary of dimension n, according to a finite collection of predetermined deletion rules,

a′

2) providing a second set consisting of codevectors of dimension n−

i, that may not be obtained by deletion, from the codevectors of the initial dictionary, of the elements of said finite set with said collection of deletion rules,

a′

3) constructing an intermediate dictionary, of dimension n−

i comprising a union of said first set and of said second set, and

a′

4) repeating steps a′

1) to a′

3) at most n−

N−

1 times, with said intermediate dictionary in the guise of initial dictionary, down to said given dimension N.

22. A method for operating a coding-decoding device having a processor by vector quantization at variable rate defining a variable resolution, comprising:

forming, using the processor, a dictionary comprising codevectors of variable dimension in which, for a given dimension, the method comprising;

a) forming a first set consisting of codevectors by performing an operation selected from the group consisting of inserting into and deleting from codevectors of dictionaries of dimension elements comprising at least one of lower and higher dimension elements taken from a finite set of real numbers according to a finite collection of predetermined operation rules,

b) constructing a first, intermediate, dictionary comprising at least said first set, for said given dimension, and

c) adapting said dictionary to a use with at least one given resolution, wherein a second, definitive, dictionary is constructed, on the basis of the intermediate dictionary, by performing at least one of embedding and simplification of dictionaries of at least one of increasing and decreasing resolutions, the dictionaries of increasing resolutions being inter-embedded from the dictionary of smallest resolution up to the dictionary of greatest resolution;

wherein

step c) further comprises;

c0) obtaining an initial dictionary of initial resolution r_n, lower than said given resolution r_N,

c1) constructing on the basis of the initial dictionary, an intermediate dictionary of resolution r_n+1 higher than the initial resolution r_n, and

c2) repeating step c1) until the given resolution r_N is attained.

23. The method as claimed in claim 22, in which, for each iteration of operation c1), there is provided a construction of classes and of centroids, in which the centroids belonging at least to the dictionaries of resolution higher than a current resolution r_i are recalculated and updated.

24. The method as claimed in claim 23, in which the centroids which belong to the dictionaries of resolution lower than a current resolution r_i are updated only if the total distortions of all the dictionaries of lower resolution are decreasing from one update to the next.

25. The method as claimed in claim 22, in which N successive dictionaries of respective resolutions r₁ to r_N are obtained on the basis of an initial dictionary of intermediate resolution r_n, by the repeated implementation of step c1) for the increasing resolutions r_n+1 to r_N, and through a repeated implementation of step c′

1) that follows for the decreasing resolutions r<sub>n−

1</sub> to r₁;

c′

1) constructing, on the basis of the initial dictionary, an intermediate dictionary of resolution r<sub>n−

1</sub> lower than the initial resolution r_n, by partitioning of the initial dictionary into several subsets ordered according to a predetermined criterion.

26. A method for operating a compression coding-decoding device having a processor, comprising:

searching for a codevector (x^j) which is the nearest neighbour of an input vector y=(y₀, . . . , y_k, . . . , y<sub>j−

1</sub>) in a dictionary (Dⁱ_j) of given dimension (j),

reconstituting, using the processor, said codevectors by using at least one correspondence table making it possible to reconstitute any codevector of the dictionary of said given dimension, using indices of a collection of operation rules selected from the group consisting of insertion rules and deletion rules and indices identifying elements of a set of codevectors that may not be obtained by application of the operation to codevectors of at least one of lower and higher dimension than the given dimension according to said collection of operation rules,

CO1) reconstituting, for a current index (m^j) of said codevector (x^j) sought, at least partial of a codevector of index (m′

) corresponding to said current index (m^j), at least through the prior reading of the indices (j′

, m′

, l_r) appearing in the correspondence tables making it possible to formulate said dictionary,

CO2) calculating at least on coding, a distance between the input vector and the codevector reconstituted in step CO1),

CO3) repeating steps CO1) and CO2), at least on coding, for all the current indices in said dictionary,

CO4) identifying, at least on coding, of the index (m_min) of the codevector at least partially reconstituted whose distance (d_min), calculated in the course of one of the iterations of step CO2), with the input vector is the smallest, and

CO5) determining at least on decoding, of the nearest neighbour of the input vector (y) in the guise of codevector (x^j) whose index (m_min) has been identified in step CO4).

27. The method as claimed in claim 26, in which step CO1), at least on decoding, comprises:

CO11) reading, in the correspondence tables, indices representative of links to said second set and the operation rules and including;

the index of a current dimension of a subset of said second set,

the current index of an element of said subset,

and the index of the appropriate operation rule for the construction of the codevector of the dictionary of given dimension, on the basis of said element,

CO12) reading, from the subset identified by its current dimension, of said element identified by its current index,

CO13) reconstructing the codevector to said given dimension by applying to said element read in step CO12) the appropriate operation rule identified by its index read in step CO11).

28. The method as claimed in claim 26, in which, on coding, step CO1) comprises:

CO11) reading, from the correspondence tables, indices representative of links to said second set and to the operation rules and including;

the index of a current dimension of a subset of said second set,

the current index of an element of said subset,

and the index of the appropriate operation rule for the construction of the codevector of the dictionary of given dimension,

CO12) reading, from the subset identified by its current dimension, of said element identified by its current index, wherein, in step CO2), said distance is calculated as a function of a distortion criterion estimated as a function of;

the index of the operation rule,

and of the element of the subset identified by its current index,

thereby making it possible to only partially construct the codevector with said given dimension in step CO1), by reserving the complete reconstruction simply for decoding.

29. The method as claimed in claim 26, in which there is provided furthermore a supplementary structuring property according to a union of permutation codes and utilizing an index of said union of permutation codes, and in which:

CP1) on the basis of an input signal, an input vector y=(y₀, . . . , y_k, . . . , y<sub>j−

1</sub>) defined by its absolute vector |y|=(|y₀|, . . . , |y_k|, . . . , |y<sub>j−

1</sub>|) and by a sign vector ε

γ

(ε

₀, . . . , ε

_k, . . . , ε

<sub>j−

1</sub>) with ε

_k=±

1 is formed,

CP2) the components of the vector |y| are ranked by decreasing values, by permutation, to obtain a leader vector |{tilde over (y)}|,

CP3) a nearest neighbour x^j′

of the leader vector |{tilde over (y)}| is determined from among the leaders of the dictionary D^j_i of dimension j,

CP4) an index of the rank of said nearest neighbour x^j′

in the dictionary D^j_i is determined,

CP5) and an effective value of at least one of coding and decoding is applied to the input vector, which is dependent on said index determined in step CP4), on said permutation determined in step CP2) and on said sign vector determined in step CP1).

30. The method as claimed in claim 26, in which at least said correspondence tables are stored in a memory of at least one of coding and decoding devices.

32. A computer readable memory storing a computer program product intended to be stored in a memory of a processing unit, in particular of a computer or of a mobile terminal integrating at least one of coding and decoding device, or on a removable memory medium and intended to cooperate with a reader of the processing unit,

wherein it comprises instructions for implementing the method according to claim 26.