Image analysis – Image compression or coding – Quantization
Reexamination Certificate
1999-01-19
2004-04-27
Johnson, Timothy M. (Department: 2625)
Image analysis
Image compression or coding
Quantization
C375S240220
Reexamination Certificate
active
06728413
ABSTRACT:
FIELD OF THE INVENTION
The present invention concerns a digital signal coding device and method, and the corresponding decoding device and method.
The signal to be coded may be of any type. The signal is in general terms a set of data representing physical quantities. The following text will be concerned with a digital image, by way of example.
RELATED ART
A conventional digital image is a matrix of for example 512×512 pixels coded in eight bits. Transmitting such an image over a low-speed channel requires several tens of minutes. Image compression techniques have been developed to reduce the transmission time.
Vector quantization is frequently used for image coding. Such a quantization uses a code vector dictionary, which can be a lattice, for example of the D
n
type, each element of which is represented for example by its Cartesian coordinates, or by a polar representation.
In order to comply with the statistics of the data, it is preferable to represent a code vector of the lattice by its polar coordinates, namely its norm and an index representing its position on an isonorm. The norm of a vector is calculated in a conventional fashion, using a predetermined norm.
In a first aspect, in order to determine the index of a code vector, it is known that it is possible to use a table of correspondence between all the code vectors, represented in Cartesian coordinates, and their respective indices. This table of correspondence is very large, and consequently requires a large amount of memory space. In addition, the size of the table of correspondence is in general related to the maximum transmission rate of the coded data.
The present invention aims to remedy these drawbacks by providing a rapid method for determining the index of a code vector in a lattice of the D
n
type.
In a second aspect, the coding of the index of a code vector is the coding of one event amongst a known group of events.
For this purpose, it is known how to code each event in a number of bits corresponding to the power of two greater than the number of events. Each event is thus coded in a unique fashion. However, this technique use a large number of bits.
Another known technique is entropic coding, for example of the Huffman type. This technique requires a large amount of calculation time and generates tables which occupy a large amount of memory space, notably when there are a large number of events to be coded.
BRIEF SUMMARY OF THE INVENTION
The present invention aims to remedy these drawbacks by providing a method of coding an event included in a known group of events, which provides a more compact code.
To this end, the invention first of all proposes a method of determining an index of a code vector belonging to a predetermined lattice, characterised in that it includes the steps of:
determining a leader vector for the code vector,
seeking a permutation number between the code vector and the leader vector,
determining the index for the code vector according to the permutation number.
Correlatively, the invention proposes a device for determining an index of a code vector belonging to a predetermined lattice, characterised in that it has:
means of determining a leader vector for the code vector,
means of seeking a permutation number between the code vector and the leader vector,
means of determining the index for the code vector as a function of the permutation number.
The coding according to the invention can be implemented rapidly. It requires only a limited number of calculations, since seeking the index of a code vector is a search over a limited number of vectors.
The invention has the advantage of not requiring the use of a table of correspondence between code vectors and their respective indices, which saves on memory space and imposes no constraint on the transmission rate of the coded data.
The invention also concerns a method of coding a code vector included in a known group of vectors belonging to a predetermined lattice, the said vectors having the same norm, in the sense of a predetermined norm, characterised in that it includes the steps of:
determining a leader vector for the code vector,
seeking a permutation number between the code vector and the leader vector,
determining an index for the code vector as a function of the permutation number.
The invention applies to the coding of a set of data representing physical quantities, characterised in that it includes the steps of:
dividing the set of data into vectors, then, for each of the vectors resulting from the division,
vector quantization of the vector so as to determine a code vector belonging to a predetermined lattice,
determining a leader vector for the code vector,
seeking a permutation number between the code vector and the leader vector,
determining an index for the code vector as a function of the permutation number.
The invention then has advantages similar to those described previously.
According to a preferred characteristic, the coding method includes the steps of:
determining an area of the lattice according to the norm of the code vector,
seeking a set of leader vectors in the area,
seeking a sub-set of leader vectors having the same norm as the code vector,
calculating the sum of a respective number of permutations of the leader vectors of the sub-set which are different from the leader vector relating to the code vector, and of the permutation number between the code vector and its leader vector.
Thus the seeking of the leader vector and of the permutation number between the vector to be coded and the leader vector is effected on a reduced number of vectors.
According to a preferred characteristic, the permutation number is determined by applying the Schalkwijk method to the code vector and to the leader vector. This method can be implemented rapidly.
The coding device includes means of using the above characteristics which have advantages similar to those disclosed above.
The invention also concerns a method of decoding a code vector belonging to a predetermined lattice, whose coded form includes a norm and an index, characterised in that it includes the steps of:
determining a leader vector for the code vector,
determining a permutation number between the code vector and the leader vector, according to the index,
determining the code vector according to the permutation number.
Correlatively, the invention proposes a device for decoding a code vector belonging to a predetermined lattice, whose coded form includes a norm and an index, characterised in that it has:
means of determining a leader vector for the code vector,
means of determining a permutation number between the code vector and the leader vector, according to the index,
means of determining the code vector according to the permutation number.
According to a preferred characteristic, the decoding method includes the step of determining an area of the lattice as a function of the norm of the code vector, and the leader vector is sought in this area.
According to another preferred characteristic, the code vector is determined by applying the inverse Schalkwijk method to the permutation number and to the leader vector.
The decoding can be implemented rapidly, since there also searches are carried out on a limited number of vectors.
The decoding method and device make it possible to find the code vectors, for example in a receiving apparatus corresponding to a sending apparatus in which the signal was coded according to the invention.
In the second aspect, the invention proposes a method of coding an event included in a known group of events, characterised in that it includes the steps of:
determining a first number and a second number of bits which can be used to code an event, as a function of the number of events in the group,
coding the event by using the first number of bits or the second number of bits according to a selection criterion.
Correlatively, the invention proposes a device for coding an event included in a known group of events, characterised in that it has:
means of determining a first number and a second number of bits which can be used
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
Johnson Timothy M.
LandOfFree
Lattice vector quantization in image compression and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Lattice vector quantization in image compression and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lattice vector quantization in image compression and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3224364