Two fast nearest neighbor searching algorithms for vector quantization

In this paper, two efficient codebook searching algorithms for vector quant ization (VQ) are presented. The first fast search algorithm utilizes the co mpactness property of signal energy of orthogonal transformation. On the tr ansformed domain, the algorithm uses geometrical relations between the inpu t vector and codeword to discard many unlikely codewords. The second algori thm, which transforms principal components only, is proposed to alleviate s ome calculation overhead and the amount of storage. The relation between th e principal components and the input vector is utilized in the second algor ithm. Since both of the proposed algorithms reject those codewords that are impossible to be the nearest codeword, they produce the same output as con ventional full search algorithm. Simulation results confirm the effectivene ss of the proposed algorithms.