ArticleComputer Vision

Is it possible to quickly and efficiently retrieve similar images from a dataset of 1M (or more) images?

by Federico Magliani, PhD student at the University of Parma (PubhD Dublin, January 2019)

The problem is trivial for humans thanks to experience and semantic perception, but not for computers. This is known as semantic gap, which refers to the difference between low-level image pixels and high-level semantic concepts.

Another relevant problem lies in the images themselves, which may present noisy patches (e.g. trees, person, cars, …), different lightning conditions, viewpoints and resolution. For this reason, it is crucial to develop algorithms and methods with the objective of reducing the focus on unnecessary details in the images and that work well with a vast quantity of data.

However, the final objective of this task is the accuracy of the entire system, that means if the retrieved images are really similar to the query or not.

The implementation of the diffusion process allows for boosting of the final performance of the retrieval systems. This method, through the use of a kNN graph, can better exploit the similarities between the images than using only a Euclidean metric. This is possible simply executing many times a random walk on the graph from the query point. All the nodes crossed, during the walk, will be potential neighbours of the query. In order to calculate the ranking of the neighbours found, the edge weight of the connected nodes is important information. The weight of an edge is set after the calculation of a similarity measure between the nodes.

Unfortunately, the creation of the initial graph requires a lot of computational time and resources because it calculates the connections between all the possible pairs of images in the dataset (brute-force approach). So, my work is focused on reducing this bottleneck of the diffusion approach and then allows to apply this process also on very large datasets. The proposed method is subdivided into two steps: divide and conquer.

In the first one, all the elements are subdivided into several sets based on the similarity using an unsupervised hashing function. This step reduces the number of times in which a similarity measure between two nodes is calculated because some connections are useless for the final diffusion application.
Instead, in the second step, the creation of the subgraphs of the different subsets is executed using the brute-force approach. Finally, all the subgraphs are merged in the final approximate kNN graph.

All the details of the research project, the news and the publications are available on the website of my ​research lab​.

Leave a Reply

Your e-mail address will not be published. Required fields are marked *