Nearest Neighbor Search For Large-scale Visual Object Recognition

Nearest neighbor classifier is the oldest method for classification in machinelearning. As a non-parametric classification method, nearest neighbor classifier becomesa hot research topic in machine learning and pattern recognition, because of suchadvantages as it doesn’t require training step, can naturally handle multi-class situations,avoids parameters overfitting, etc. Especially in large-scale visual recognition problem,nearest neighbor classifier can play a better role. The main academic contributions ofthis thesis are as follows.First of all, this thesis based on the Na ve Bayes Nearest Neighbor (NBNN)approach, proposed a Pyramid Nearest Neighbor Search (PNNS) algorithm by addingspatial information in the Nearest Neighbor Search kernel. The main idea in theapproach was adding the global geometric correspondence into the NBNN. First, PNNSdivided images into increasingly fine sub-windows as the Spatial Pyramid Matching(SPM) approach. Second, PNNS was introduced for measuring local descriptors and thesimilarity of feature sets over classes in each pyramid sub-window. Different from thefixed weights in SPM, the author learned pyramid weights in a class-dependent mannerto obtain class-specific geometric correspondence. At last, a framework of the optimalnearest neighbor classifier was exploited to combine different pyramid kernel functions.This approach was evaluated on four public datasets, the experimental results show thatPNNS outperformed existing techniques.Secondly, this thesis based on PNNS, proposed a Kernel Pyramid NearestNeighbor (KPNN) approach. Aim to the unbalanced class problem, the Pyramid NearestNeighbor feature representation transformed the measure of local features into globalfeatures by using a kernel mapping function, and provided to the Support VectorMachine (SVM) classifier for classification. Moreover, for better calibrating the outputsof classifiers in each pyramid window, the author fit the Sigmoid function and weightedthe outputs in each pyramid window. The Sigmoid parameters and weights could belearned in a class-dependent and window-dependent manner. Compared on two publicdatasets, the experimental results show the significant performance of KPNN.Finally, for the purpose of large-scale visual recognition, this thesis proposed aProduct Quantization Pyramid Nearest Neighbor Search (PQPNNS) approach. This approach increased the computational efficiency and reduced the memory cost bycoding features. The experimental results indicated that, in the condition of large-scaledata, this approach could enhance the computational efficiency300times and reducethe memory space several times than traditional PNNS approach.