基于快速搜索的码书快速生成算法

在k维欧氏空间R^k中,给定一个有限子集W及一个向量x,如何快速搜索W中与x距离最近的向量,具有重要的实际应用价值,尤其在图像的矢量量化编码、自组织特征映射SOFM(Self-Organizing Feature Maps)算法的码书迭代生成等问题中,快速搜索算法起决定性的作用.针对SOFM算法的具体特点,在分析已有快速搜索算法的基础上,给出了一种新的快速迭代码书生成算法,该算法兼顾了快速与节省内存问题.实验结果表明:提出的新算法的执行时间仅为已有算法执行时间的约42％.另外,新算法在模式识别领域和计算机图形学领域均具有实际应用价值.

Algorithm for Rapid Codebook Generating Based on Fast Search

Given a finite subset W and a vector x both in k dimension space R k ,the method to fast locate the vector in W closest to x is of great value in various applications,and would speed up the encoding for vector quantization and the iterative process of generating codebook based on SOFM algorithm. This paper analyzes the properties of SOFM algorithm and the existed fast encoding algorithms,and presents a new method to speed up the codebook generating. The advantages of the new method are in high searching efficiency and less memory requirement. The experiment shows that the running time of the new algorithm is only about 42% of the existing one's. The new algorithm proposed in this paper is of applied value in many fields such as pattern recognition and computer graphics.