Study On The Nearest Neighbor Algorithm For Template Matching

Although template matching is one of the most classical methods in pattern recognition,it still has a place in the current era of big data.Therefore,it is worth studying to further improve and perfect this method according to the different characteristics of data.Two processings need be implemented in template matching.The suitable samples are selected as templates during the period of establishing the template standard library and the nearest neighbor principle based on distance or similarity is used to compare the test sample with each template.Some improvements have been implemented for the big data with a large number of samples.The main work is as follows:1.Two algorithms based on density or cluster learning are proposed to establish an optimal standard library.Firstly,isolated samples are removed to improve the correct recognition rate of the algorithm.Then,a template standard library which has better ergodicity and less templates is established based on density or cluster learning to speeded up the recognition.The density of each training sample is calculated and the redundant training samples can be eliminated arcoording to their densities.Therefore,the number of templates in the standard library can be reduced.In addation,a template standard can be built based on the K-means clustering.Training samples are clustered and the cluster centers are employed as the templates.It is possible to get the standard library with fewer templates as well as better ergodicity.Finally,to verify the proposed algorithms,some experiments have been done.The results of experiments show that the recognition speed is proportional to the reduction of the number of templates at the same time the correct recognition rate is slightly improved.2.An adaptive decision rule of nearest neighbor classification algorithm is presented.The category of the test sample is determined together by the templates which are selected adaptively.The number of templates that ultimately participate in the decision is usually different for different test sample.A method to automatically obtain the number of the templates is proposed.The experimental results show that this adaptive decision rule has better recognition rate than the original nearest neighbor and K-neighbor when the numbers of class templates are not balanced.3.The improved nearest neighbor classification algorithm in which class distance is proposed to be used as similarity is presented.Different class distances are defined.Firstly,two kinds weighted class distances are defined and the calculation method of weights is given.Then,the concept of weighted gaussian distance is proposed.Three definitions of similarity(weighted gaussian nearest neighbor(WGNN),adaptive weighted gaussian nearest neighbor(AWGNN),Gauss-based adaptive k-nearest neighbor mean(AG-KMEAN))by different weighted Gaussian class distance are given.The experimental results show that AWGNN has a better recognition effect.4.In order to verify the superiority of the improved algorithm,some recognition experiments by some other classification models,such as SVM,SRC,BP,RF,and Adaboost,and so on,have been carried out in the same experimental environment.Comparative analysis shows that AWGNN has higher correct recognition rate then others.