A Sketch Retrieval System Based On Two-demensional Embedding Nearest Neighbor Search

With the thriving development of information technology and the general utilization of multimedia digital equipment, we have embraced unprecedented image information resources. However, due to the high dimensionlity of image data, the issue of efficient index and retrieval of image information demands prompt solution. Traditional retrieval method relies on the text label of image, where the cost of human labeling is unbearable and the strong subjectivity of labeling results in bad performance. Therefore, Content-based image retrieval becomes the hot spot in recent studies, where features of image are extracted for indexing and corresponding image is retrieved through Nearest Neighbor Search(NNS).The basic NNS algorithm is linear scan, however, due to the high dimensionlity of features, computing the similarity of all images costs too much. The traditional strategies for quick retrieval often fail when encountering high dimensional data, and behave even worse than linear scan as dimension increasing to some degree. This article refers to some research precedents and proposes a fast two-dimensional based nearest neighbor search algorithm, which is able to efficiently retrieve accurate nearest neighbor, especially for high dimensional data.We advance a Vantage Point Tree-based strategy for data filtering first, where non-nearest neighbor is rapidly filtered in low dimensional space through data embedding. To enhance the effect of filtering we bring in Sampling algorithm, which leads to more accurate estimations of filtering threshold value at a relatively small price. With this "Sampling-Filtering-Verifying" integrated three-step strategy, our algorithm is competent for efficient nearest neighbor search in high dimension. Experimental results indicate the effectiveness of our method. Lastly we apply our method to sketch retrieval and implement a sketch-based image retrieval system.