Dimensional vector and variable resolution quantization
First Claim
1. A dictionary comprising codevectors of variable dimension and intended to be used in a device for compression coding and/or decoding of digital signals, by vector quantization at variable rate defining a variable resolution, wherein on the one hand, for a given dimension, inter-embedded dictionaries of increasing resolution, and, on the other hand, for a given dimension, a union:
- of 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 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.
1 Assignment
0 Petitions
Accused Products
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.
72 Citations
31 Claims
-
1. A dictionary comprising codevectors of variable dimension and intended to be used in a device for compression coding and/or decoding of digital signals, by vector quantization at variable rate defining a variable resolution,
wherein on the one hand, for a given dimension, inter-embedded dictionaries of increasing resolution, and, on the other hand, for a given dimension, a union: -
of 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 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. - View Dependent Claims (2, 3)
-
-
4. A method for forming a dictionary comprising codevectors of variable dimension and intended to be used in a device for compression coding and/or decoding of digital signals, by vector quantization at variable rate defining a variable resolution,
in which, for a given dimension: -
a) a first set consisting of codevectors formed by inserting/deleting into/from codevectors of dictionaries of lower/higher dimension elements taken from a finite set of real numbers according to a finite collection of predetermined insertion/deletion rules, b) a first, intermediate, dictionary comprising at least said first set is constructed, for said given dimension, c) and, to adapt said dictionary to a use with at least one given resolution, a second, definitive, dictionary is constructed, on the basis of the intermediate dictionary, by embedding/simplification of dictionaries of increasing/decreasing resolutions, the dictionaries of increasing resolutions being inter-embedded from the dictionary of smallest resolution up to the dictionary of greatest resolution. - View Dependent Claims (5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
25. A method of using a dictionary in the compression coding/decoding of digital signals, by vector quantization at variable rate defining a variable resolution, said dictionary, of a given dimension, giving codevectors reconstituted 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 insertion/deletion rules and indices identifying elements of a set of codevectors that may not be obtained by application of the insertion/deletion to codevectors of lower/higher dimension than the given dimension according to said collection of insertion/deletion rules,
in which a search is made for the codevector (xj) which is the nearest neighbour of an input vector y=(y0, . . . , yk, . . . , yj− - 1) in a dictionary (Dij) of given dimension (j),
and comprising the following steps;
CO1) for a current index (mj) of said codevector (xj) sought, reconstitution at least partial of a codevector of index (m′
) corresponding to said current index (mj), at least through the prior reading of the indices (j′
, m′
, lr) appearing in the correspondence tables making it possible to formulate said dictionary,CO2) at least on coding, calculation of a distance between the input vector and the codevector reconstituted in step CO1), CO3) at least on coding, repetition of steps CO1) and CO2), for all the current indices in said dictionary, CO4) at least on coding, identification of the index (mmin) of the codevector at least partially reconstituted whose distance (dmin), calculated in the course of one of the iterations of step CO2), with the input vector is the smallest, and CO5) at least on decoding, determination of the nearest neighbour of the input vector (y) in the guise of codevector (xj) whose index (mmin) has been identified in step CO4). - View Dependent Claims (26, 27, 28, 29)
CO11) the reading, in the correspondence tables, of indices representative of links to said second set and to the insertion/deletion 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 insertion/deletion rule for the construction of the codevector of the dictionary of given dimension, CO12) the reading, in the subset identified by its current dimension, of said element identified by its current index, in step CO2), said distance is calculated as a function of a distortion criterion estimated as a function of;
the index of the insertion/deletion 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.
- 1) in a dictionary (Dij) of given dimension (j),
-
28. The method as claimed in claim 25, 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=(y0, . . . , yk, . . . , yj−
1) defined by its absolute vector |y|=(|y0|, . . . ,|yk|, . . . ,|yj−
1|) and by a sign vector ε
=(ε
0, . . . ,ε
k, . . . ,ε
j−
1) 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 xj′
of the leader vector |{tilde over (y)}| is determined from among the leaders of the dictionary Dji of dimension j,CP4) an index of the rank of said nearest neighbour xj′
in the dictionary Dji is determined,CP5) and an effective value of coding/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).
-
-
29. The method as claimed in claim 25, in which at least said correspondence tables are stored in a memory of a coding/decoding device.
-
30. 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 a method for forming a dictionary comprising codevectors of variable dimension and intended to be used in a device for compression coding and/or decoding of digital signals, by vector quantization at variable rate defining a variable resolution,
in which, for a given dimension: -
a) a first set consisting of codevectors formed by inserting/deleting into/from codevectors of dictionaries of lower/higher dimension elements taken from a finite set of real numbers according to a finite collection of predetermined insertion/deletion rules, b) a first, intermediate, dictionary comprising at least said first set is constructed, for said given dimension, c) and, to adapt said dictionary to a use with at least one given resolution, a second, definitive, dictionary is constructed, on the basis of the intermediate dictionary, by embedding/simplification of dictionaries of increasing/decreasing resolutions, the dictionaries of increasing resolutions being inter-embedded from the dictionary of smallest resolution up to the dictionary of greatest resolution.
-
-
31. 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 a coding/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 a use of a dictionary in the compression coding/decoding of digital signals, by vector quantization at variable rate defining a variable resolution, said dictionary, of a given dimension, giving codevectors reconstituted 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 insertion/deletion rules and indices identifying elements of a set of codevectors that may not be obtained by application of the insertion/deletion to codevectors of lower/higher dimension than the given dimension according to said collection of insertion/deletion rules, in which a search is made for the codevector (xj) which is the nearest neighbour of an input vector y=(y0, . . . , yk, . . . , yj− - 1) in a dictionary (Dij) of given dimension (j),
and comprising the following steps;
CO1) for a current index (mj) of said codevector (xj) sought, reconstitution at least partial of a codevector of index (m′
) corresponding to said current index (mj), at least through the prior reading of the indices (j′
, m′
, lr) appearing in the correspondence tables making it possible to formulate said dictionary.CO2) at least on coding, calculation of a distance between the input vector and the codevector reconstituted in step CO1). CO3) at least on coding, repetition of steps CO1) and CO2), for all the current indices in said dictionary, CO4) at least on coding, identification of the index (mmin) of the codevector at least partially reconstituted whose distance (dmin), calculated in the course of one of the iterations of step CO2) with the input vector is the smallest, and CO5) at least on decoding, determination of the nearest neighbour of the input vector (y) in the guise of codevector (xj) whose index (mmin) has been identified in step CO4).
- 1) in a dictionary (Dij) of given dimension (j),
Specification