Fast k-nearest neighbor search algorithm based on pyramid structure of wavelet transform and its application to texture classification

作者：Qiao, Yu Long^*; Lu, Zhe Ming; Pan, Jeng Shyang; Sun, Sheng He

来源：Digital Signal Processing, 2010, 20(3): 837-845.

DOI：10.1016/j.dsp.2009.10.011

• k-nearest neighbor search
• Wavelet transform
• Vector quantization encoding
• Texture classification
• Pattern recognition

Traditional fast k-nearest neighbor search algorithms based on pyramid structures need either many extra memories or long search time. This paper proposes a fast k-nearest neighbor search algorithm based on the wavelet transform, which exploits the important information hiding in the transform coefficients to reduce the computational complexity. The study indicates that the Haar wavelet transform brings two kinds of important pyramids. Two elimination criteria derived from the transform coefficients are used to reject those impossible candidates. Experimental results on texture classification verify the effectiveness of the proposed algorithm.

• 出版日期2010-5
• 单位哈尔滨工业大学; 哈尔滨工程大学; 浙江大学