Method and apparatus for fast nearest neighbor search for vector quantizers
View Patent ↗A method comprises identifying a component k of a codevector from a codebook C having one or more codevectors, the component k introducing highest variance for an input vector; allowing ordering of codevectors in the codebook C; and searching for a best match vector for the input vector using ordered codevectors.
1. A method, comprising:
searching for a best match vector for an input vector using ordered codevectors in a codebook C, wherein the codevectors are ordered based on a component k of the codevector, wherein the searching comprises:
performing a binary search only considering component k of the input vector; and
performing a modified partial distortion search considering full codevectors.
2. The method of claim 1 , wherein the codevectors are ordered in ascending order and wherein performing the binary search finds a vector with smallest index j satisfying the condition:
X k <C j,k ,
where X is the input vector and C is the ordered codevectors.
3. The method of claim 2 , wherein performing the modified partial distortion search comprises:
performing a downward search starting at index j−1; and
performing an upward search starting at index j.
4. The method of claim 3 , wherein the downward search is terminated upon finding a codevector resulting in a larger distortion for component k than the then-current codevector providing the best match.
5. The method of claim 3 , wherein the upward search is terminated upon finding a codevector resulting in a larger distortion for component k than the then-current codevector providing the best match.
6. The method of claim 3 , further comprising:
selecting a codevector as the output of the searching for a best match upon termination of both the upward search and the downward search.
7. An apparatus, comprising:
a processor; and
a memory unit communicatively connected to the processor and including:
computer code for searching for a best match vector for an input vector using ordered codevectors in a codebook C, wherein the codevectors are ordered based on a component k of the codevector, wherein the computer code for searching comprises
computer code for performing a binary search only considering component k of the input vector; and
computer code for performing a modified partial distortion search considering full codevectors.
8. The apparatus of claim 7 , wherein codevectors are ordered in ascending order and wherein the computer code for performing the binary search is configured to find a vector with smallest index j satisfying the condition:
X k <C j,k ,
where X is the input vector and C is the ordered codevectors.
9. The apparatus of claim 8 , wherein computer code for performing the modified partial distortion search comprises:
computer code for performing a downward search starting at index j−1; and
computer code for performing an upward search starting at index j.
10. The apparatus of claim 9 , wherein the computer code for performing a downward search is configured to terminate the downward search upon finding a codevector resulting in a larger distortion for component k than the then-current codevector providing the best match.
11. The apparatus of claim 9 , wherein the computer code for performing an upward search is configured to terminate the upward search upon finding a codevector resulting in a larger distortion for component k than the then-current codevector providing the best match.
12. The apparatus of claim 9 , further comprising:
computer code for selecting a codevector as the output of the searching for a best match upon termination of both the upward search and the downward search.
13. A computer program product, embodied on a computer-readable medium, comprising:
computer code for searching for a best match vector for an input vector using ordered codevectors in a codebook C, wherein the codevectors are ordered based on a component k of the codevector, wherein the computer code for searching comprises
computer code for performing a binary search only considering component k of the input vector; and
computer code for performing a modified partial distortion search considering full codevectors.
14. The computer program product of claim 13 , wherein codevectors are ordered in ascending order and wherein the computer code for performing the binary search is configured to find a vector with smallest index j satisfying the condition:
X k <C j,k ,
where X is the input vector and C is the ordered codevectors.
15. The computer program product of claim 14 , wherein computer code for performing the modified partial distortion search comprises:
computer code for performing a downward search starting at index j−1; and
computer code for performing an upward search starting at index j.
16. The computer program product of claim 15 , wherein the computer code for performing a downward search is configured to terminate the downward search upon finding a codevector resulting in a larger distortion for component k than the then-current codevector providing the best match.
17. The computer program product of claim 15 , wherein the computer code for performing an upward search is configured to terminate the upward search upon finding a codevector resulting in a larger distortion for component k than the then-current codevector providing the best match.
18. The computer program product of claim 15 , further comprising:
computer code for selecting a codevector as the output of the searching for a best match upon termination of both the upward search and the downward search.