Nearest Neighbors (NN) is a fundamental operation in many areas of scientific computing, including computer vision, machine learning, robotics, and data mining. It is the backbone of applications people use every day, such as Google Images. Images tend to be high-dimensional, and as the dimensionality of the data increases, the NN task becomes computationally more difficult. This is called the “curse of dimensionality” and it affects efforts to analyze and organize high-dimensional spaces.
Graduate student and MSI researcher Anoop Cherian, who works with MSI PI Professor Nikolaos Papanikolopoulos (Computer Science and Engineering), is developing a novel NN algorithm for image data. The goal is to develop an NN algorithm that is computationally tractable at high dimensions. Other needs for this algorithm include:
- state-of-the-art performance in accuracy
- good search speed
- robustness to data distortions
- storage efficiency
- scalabilty
The algorithm is called Multi-Regularization Sparse Coding (MRSC) and is based on sparse coding and dictionary learning. The algorithm is showing great promise in accuracy, speed of retrieval, scalability, and robustness. Because of the huge computational demands that working with millions of data points requires, MSI resources are necessary for this work. The image above shows the results of a search using the MRSC algorithm on a database of images of Notre Dame (containing 1,500 images). The first column shows the query images and the other three columns are the first three nearest neighbors.
Mr. Cherian’s poster about this research was the Grand Prize winner at MSI’s Research Exhibition in April 2012 and has been submitted for publication.