Two fast nearest neighbor searching algorithms for vector quantization
In this paper, two efficient codebook searching algorithms for vector quantization (VQ) are presented. The first fast search algorithm utilizes the compactness property of signal energy of orthogonal transformation. On the transformed domain, the algorithm uses geometrical relations between the input vector and codeword to discard many unlikely codewords. The second algorithm, which transforms principal components only, is proposed to alleviate some calculation overhead and the amount of storage. The relation between the principal components and the input vector is utilized in the second algorithm. Since both of the proposed algorithms reject those codewords that are impossible to be the nearest codeword, they produce the same output as conventional full search algorithm. Simulation results confirm the effectiveness of the proposed algorithms.
nearest neighbor search vq fast encoding