As a course project during my time at Freie Universität Berlin, my teammate Martí Griera Jorba and I experimented with various algorithms relating to shape matching and feature extraction in images. The project was coded in C++, making extensive use of the OpenCV library for computer vision. The image below illustrates some of the algorithms we used to extract features from input images, resulting in a representation of the image as a weighted point set.
Data from edge detection done using the Canny algorithm, corner detection using the MinEigenVal algorithm, and the intensity gradient computed using the Sobel operator were combined to generate the resultant point set. We used OpenCV implementations of all three algorithms.
To compare the weighted point sets, we used the Earth Mover’s Distance (EMD) algorithm, as implemented by Yossi Rubner.
Visualization of EMD computed on two images of simple shapes. Larger points indicated larger weights, and thicker lines indicate higher flow between points
With the feature extraction and comparison algorithms in place, we can query a database of images, and retrieve the closest matches.
Closest matches to the query image, as reported by our EMD comparison engine. Dataset: Brown Shape Indexing of Images Database (SIID)
The EMD image retrieval engine effectively returns matches for a database of simple images, such as the dataset of silhouettes shown above. For more complex datasets, the results are… mixed.
Image retrieval results of a larger, more complex dataset. Dataset: 500 image subset of the Caltec 101 Categories Dataset
It can be interesting to visualize an image database globally to examine the computed similarities of the images. We did this using a multidimensional scaling algorithm, which plots each image into 3D space. Images which are computed to be most similar to each other wind up closest to each other in the 3D space. We used the freely available MDSJ - Multidimensional Scaling for Java library, and created a 3D visualization using Processing.
The SIID image dataset visualized in 3D space. Each image class is given a different color. Images nearest to eachother in 3D space are most similar as computed by EMD.