高维特征下快速近邻法的定位点选择及在手写汉字识别中的应用  

A Fast Nearest-Neighbor Search Algorithm Based on High-dimension Features and its Application to Handwritten Chinese Character Recogni tion

作　　者：朱宁波[1] 曾生根[1] 娄震[1] 杨静宇[1] 

机构地区：[1]南京理工大学计算机系,南京210094

出　　处：《计算机工程与应用》2004年第32期71-72,88,共3页Computer Engineering and Applications

摘　　要：在采用最近邻法进行模式识别时,减小搜索的计算量是一个重要的问题,对于在线识别尤为重要,解决的途径之一是采用快速搜索近邻法。快速近邻法在将样本集分级后,若采用样本均值作为子集圆心,则求取所得的样本子集半径将大于其实际半径。该文介绍了一种高维特征情况下的样本子集圆心的求取方法,根据该方法求得的样本子集圆心与样本均值存在一定的距离,且求得的样本子集半径较小。将这两个圆心以及子集中特征累加值最大和最小的样本作为定位点,应用于基于三角不等式的搜索算法的样本排除规则,大大减少了搜索的计算量。在手写汉字识别实验中,基于该方法的快速近邻法识别速度更快。It is an important problem to reduce the computational complexity of nearest-neighbor search algorithm,espe-cially in the case of on-line classification.One of settling approaches is adopting the fast nearest-neighbor search algo-rithm.Traditional method for calculating radius of sample set is taking the average value as the center of the sample set,and the radius value is larger than its actual radius.A new method for calculating the center of sample set with the high-dimension features is presented.The center is away from the center based on the average value,and the radius of the sample set is less.Using the two centers and the samples with maximum or minimum feature accumulating values as the anchor points,the efficiency of the triangle-inequality elimination greatly increases.Experimental of handwritten Chi-nese character recognition results show the effectiveness of the algorithm.

关 键 词：高维特征 快速近邻法 三角不等式 样本子集 汉字识别 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]