Fast norm-ordered nearest-neighbor codeword search algorithms for image vector quantization

Recently, a fast VQ encoding algorithm using an efficient kick-out condition has been presented. In that algorithm, codewords are sorted in ascending order of their norms and a kick-out condition based on a new distortion measure is used to reject unlikely codewords. However, it cannot be combined with partial distance search (PDS) technology. In this paper, two fast norm-ordered codeword search algorithms are presented. One is spatial-domain based, the other is Hadamard transform-domain based. Both of them can be combined with PDS technology without increasing any additional memory requirement and any degradation in quality. Experimental results demonstrate the effectiveness of the proposed algorithms.