Multidimensional close neighbor search

Abstract

A method for a multidimensional search for a close neighbor of an input vector, amongst a first set of reference vectors, comprises the prior determination of a first set of hyperplanes in the space containing the reference vectors, then selection of a first hyperplane from the first set, formation of a second set of reference vectors, by eliminating reference vectors which are on the other side of the first hyperplane selected, compared with the input vector, formation of a second set of hyperplanes, by eliminating the said first hyperplane, reiteration, a predetermined number of times, of the selection and formation operations, taking, as the first set of reference vectors and as the first set of hyperplanes, respectively, the second sets formed previously, and searching for the closest neighbor of the input vector in the second set of reference vectors.

What is claimed is: 
     
       1. A method for a multidimensional search for a close neighbor of an input vector representing physical data, amongst a first set of reference vectors stored in memory means, said method comprising the steps of: determining, according to first rules, a first set of hyperplanes in a space containing the reference vectors;   selecting, according to second rules, a first hyperplane from the first set of hyperplanes;   forming a second set of reference vectors from the first set of reference vectors, by eliminating the reference vectors which are on the other side of the first hyperplane selected, compared with the input vector;   forming a second set of hyperplanes, by eliminating the first hyperplane from the first set of hyperplanes;   reiterating, a predetermined number of times, the selection step and the two formation steps, taking in each iteration, as the first set of reference vectors and the first set of hyperplanes, respectively, the second set of reference vectors and the second set of hyperplanes formed in the last proceeding iteration;   searching, according to third rules, for the closest neighbor of the input vector, in the second set of reference vectors.   
     
     
       2. A method for coding a digital signal by vectorial quantification with a dictionary of reference vectors forming a first set of reference vectors stored in memory means, comprising division of the digital signal into input vectors, said method comprising the steps of: determining, according to first rules, a first set of hyperplanes in a space containing the reference vectors; and   then, for each input vector: selecting, according to second rules, a first hyperplane from the first set of hyperplanes,   forming a second set of reference vectors from the first set of reference vectors, by eliminating reference vectors which are on the other side of the first hyperplane selected, compared with the input vector,   forming a second set of hyperplanes, by eliminating the first hyperplane from the first set of hyperplanes,   reiterating, a predetermined number of times, the selection step and the two formation steps, taking in each iteration, as the first set of reference vectors and the first set of hyperplanes, respectively, the second set of reference vectors and the second set of hyperplanes formed in the last proceeding iteration, and   searching, according to third rules, for the closest neighbor of the input vector in the second set of reference vectors.     
     
     
       3. A method for producing a dictionary of reference vectors from an initial dictionary of reference vectors forming a first set of reference vectors stored in memory means, and predetermined digital signals stored in memory means, the digital signals being divided into input vectors, said method comprising the steps of: determining, according to first rules, a first set of hyperplanes in the space containing the reference vectors;   for each input vector of the predetermined digital signals: selecting, according to second rules, a first hyperplane from the first set of hyperplanes,   forming a second set of reference vectors from the first set of reference vectors, by eliminating the reference vectors which are on the other side of the first hyperplane selected, compared with the input vector,   searching, according to third rules, for the closest neighbor of the input vector in the second set of reference vectors; and     then, for each reference vector in the initial dictionary: calculating a barycenter of the input vectors for which the reference vector under consideration is a close neighbor, and   substituting the barycenter for the reference vector under consideration in the initial dictionary, so as to form a modified dictionary,     wherein the determination, selection, formation, reiteration, search, calculation and substitution steps being reiterated a number of times, taking, at each iteration of the set of these steps, the modified dictionary at the preceding iteration as the initial dictionary and as the first set of reference vectors.   
     
     
       4. A method for coding a digital signal by local vectorial quantification from an initial dictionary of reference vectors forming a first set of reference vectors stored in memory means, including division of the digital signal into input vectors, said method comprising the steps of: determining, according to first rules, a first set of hyperplanes in the space containing the reference vectors;   then, for each input vector of the digital signal: selecting, according to second rules, a first hyperplane from the first set of hyperplanes,   forming a second set of reference vectors from the first set of reference vectors, by eliminating reference vectors which are on the other side of the first hyperplane selected, compared with the input vector,   forming a second set of hyperplanes, by eliminating the first hyperplane from the first set of hyperplanes,   reiterating, a predetermined number of times, the selection step and the two formation steps, taking in each iteration, as the first set of reference vectors and the first set of hyperplanes, respectively, the second set of reference vectors and the second set of hyperplanes formed in the last proceeding iteration, and   searching, according to third rules, for the closest neighbor of the input vector in the second set of reference vectors; and     then, for each reference vector in the initial dictionary: calculating a barycenter of the input vectors for which the reference vector under consideration is a close neighbor, and   substituting the barycenter for the reference vector under consideration in the initial dictionary, so as to form a modified dictionary,     wherein the determination, selection formation, reiteration, search, calculation and substitution steps being reiterated a number of times, taking, at each iteration of the set of these steps, the modified dictionary at the preceding iteration as the initial dictionary and as the first set of reference vectors.   
     
     
       5. A method according to any one of claims 1 to 4, further comprising the steps of determining a barycenter of the reference vectors and calculating coordinates of the reference vectors the input vector in a reference frame centered on the barycenter. 
     
     
       6. A method according to claim 5, wherein the first rules for determining the first set of hyperplanes comprise a choice of hyperplanes passing through the barycenter of the reference vectors. 
     
     
       7. A method according to any one of claims 1 to 4, wherein the first rules for determining the first set of hyperplanes comprise a choice of hyperplanes orthogonal to the base vectors of the space containing the reference vectors. 
     
     
       8. A method according to any one of claims 1 to 4, wherein the second rules for selecting the first hyperplane selected comprise selection of the hyperplane for which the distance to the input vector is the greatest. 
     
     
       9. A method according to any one of claims 1 to 4, wherein the third search rules comprise calculation of the distance from the input vector to all the reference in the second set of reference vectors and selection of the reference vector for which the distance is the smallest. 
     
     
       10. A method for producing a dictionary of reference vectors according to claim 3 or 4, wherein the determination, selection, formation, reiteration, search, calculation and substitution steps are reiterated until the successive modified dictionaries converge to a convergence dictionary. 
     
     
       11. An apparatus for coding a vector by vectorial quantification having memory means for storing a first set of reference vectors, and means for entering the vector to be coded, comprising: means, adapted to implement first rules, for determining a first set of hyperplanes in the space containing the reference vectors;   means, adapted to implement second rules, for selecting a first hyperplane from the first set of hyperplanes;   means for forming a second set of reference vectors, by eliminating reference vectors which are on the other side of the first hyperplane selected, compared with the input vector;   means for forming a second set of hyperplanes, by eliminating the first hyperplane from the first set of hyperplanes,   wherein said means for forming the second set of reference vectors and the second set of hyperplanes being adapted to reiterate the formation operations a predetermined number of times, taking, at each reiteration, as the first set of reference vectors and the first set of hyperplanes, respectively, the second set of reference vectors and the second set of hyperplanes formed previously; and   means, adapted to implement third rules, for searching for the closest neighbor of the input vector in the second set of reference vectors.   
     
     
       12. An apparatus according to claim 11, further comprising means adapted to determine barycenter of the reference vectors and to calculate coordinates of the reference vectors and the input vector in a reference frame centered on the barycenter. 
     
     
       13. An apparatus according to claim 12, further comprising means adapted to determine the first set of hyperplanes so that it comprises hyperplanes passing through the barycenter of the reference vectors. 
     
     
       14. An apparatus according to any one of claims 11 to 13, wherein said determination means is adapted to implement first rules according to which the first set of hyperplanes comprises hyperplanes orthogonal to base vectors of the space containing the reference vectors. 
     
     
       15. An apparatus according to any one of claims 11 to 13, wherein said selection means is adapted to implement second rules according to which the first hyperplane is the hyperplane for which the distance to the input vector is the greatest. 
     
     
       16. An apparatus according to any one of claims 11 to 13, wherein said search means is adapted to implement third rules consisting of calculating the distance from the input vector to all the reference vectors in the second set of reference vectors and selecting the reference vector for which the distance is the smallest. 
     
     
       17. An apparatus according to any one of claims 11 to 13, wherein said determination, selection, formation and search means are incorporated in: a microprocessor,   a read-only memory having a program for coding a digital signal by vectorial quantification, and   a random access memory having registers adapted to record variables modified during execution of the program.   
     
     
       18. A digital data processing device having a coding apparatus according to any one of claims 11 to 13.