Matching image to a collection of images with Emgu CV

One way for finding matching image within a collection of images (let’s say using SURF algorithm) is to extract features from the query image and all the images in the collection, and then find matching features one by one. While this might work for small collections, it will have horrible performance for collections of considerable size.
For a better performing approach we can use Fast Approximate Nearest Neighbor (FLANN) search which was created for the purpose of doing fast nearest neighbor search in large data-sets.
So let’s get straight to it.

Implementation Concept

For each image in the collection compute descriptors with the algorithm best fitting your requirements. I am using SURF, however depending on the required license, performance or image nuances a different algorithm might be more appropriate.
Combine all the descriptors into one big matrix while keeping track which descriptor range within the matrix came from what image. Basically we concatenate rows from all matrices and save the row number where the newly appended descriptors start and end.
Build a FLANN index from the concatenated matrix.
Compute descriptors for the query image.
Run KNN search over the FLANN index. A K-Nearest-Neighbours search computes the distance between a query descriptor and all of the image collection descriptors, and returns the K pairs with lowest distance. KNN search will produce two matrices – Indeces matrix and Distances matrix containing indices of descriptors within the concatenated matrix which had the lowest distance and the distances themselves, respectively.
Filter out all the inadequate matches computed in the previous step.
Now we can find images matching the query image. Since we know which descriptors within the concatenated matrix belong to what image, the best matching image will be one that has the higher number of descriptors, or more precisely descriptor indexes in the Indices matrix.

Implementation

/// <summary>
/// Main method.
/// </summary>
public IList<IndecesMapping> Match()
{
    string[] dbImages = {"1.jpg", "2.jpg", "3.jpg"};
    string queryImage = "query.jpg";

    IList<IndecesMapping> imap;

    // compute descriptors for each image
    var dbDescsList = ComputeMultipleDescriptors(dbImages, out imap);

    // concatenate all DB images descriptors into single Matrix
    Matrix<float> dbDescs = ConcatDescriptors(dbDescsList);

    // compute descriptors for the query image
    Matrix<float> queryDescriptors = ComputeSingleDescriptors(queryImage);

    FindMatches(dbDescs, queryDescriptors, ref imap);

    return imap;
}

/// <summary>
/// Computes image descriptors.
/// </summary>
/// <param name="fileName">Image filename.</param>
/// <returns>The descriptors for the given image.</returns>
public Matrix<float> ComputeSingleDescriptors(string fileName)
{
    Matrix<float> descs;

    using (Image<Gray, Byte> img = new Image<Gray, byte>(fileName))
    {
        VectorOfKeyPoint keyPoints = detector.DetectKeyPointsRaw(img, null);
        descs = detector.ComputeDescriptorsRaw(img, null, keyPoints);
    }

    return descs;
}

/// <summary>
/// Convenience method for computing descriptors for multiple images.
/// On return imap is filled with structures specifying which descriptor ranges in the concatenated matrix belong to what image. 
/// </summary>
/// <param name="fileNames">Filenames of images to process.</param>
/// <param name="imap">List of IndecesMapping to hold descriptor ranges for each image.</param>
/// <returns>List of descriptors for the given images.</returns>
public IList<Matrix<float>> ComputeMultipleDescriptors(string[] fileNames, out IList<IndecesMapping> imap)
{
    imap = new List<IndecesMapping>();

    IList<Matrix<float>> descs = new List<Matrix<float>>();

    int r = 0;

    for (int i = 0; i < fileNames.Length; i++)
    {
        var desc = ComputeSingleDescriptors(fileNames[i]);
        descs.Add(desc);

        imap.Add(new IndecesMapping()
        {
            fileName = fileNames[i],
            IndexStart = r,
            IndexEnd = r + desc.Rows - 1
        });

        r += desc.Rows;
    }

    return descs;
}

/// <summary>
/// Computes 'similarity' value (IndecesMapping.Similarity) for each image in the collection against our query image.
/// </summary>
/// <param name="dbDescriptors">Query image descriptor.</param>
/// <param name="queryDescriptors">Consolidated db images descriptors.</param>
/// <param name="images">List of IndecesMapping to hold the 'similarity' value for each image in the collection.</param>
public void FindMatches(Matrix<float> dbDescriptors, Matrix<float> queryDescriptors, ref IList<IndecesMapping> imap)
{
    var indices = new Matrix<int>(queryDescriptors.Rows, 2); // matrix that will contain indices of the 2-nearest neighbors found
    var dists = new Matrix<float>(queryDescriptors.Rows, 2); // matrix that will contain distances to the 2-nearest neighbors found

    // create FLANN index with 4 kd-trees and perform KNN search over it look for 2 nearest neighbours
    var flannIndex = new Index(dbDescriptors, 4);
    flannIndex.KnnSearch(queryDescriptors, indices, dists, 2, 24);

    for (int i = 0; i < indices.Rows; i++)
    {
        // filter out all inadequate pairs based on distance between pairs
        if (dists.Data[i, 0] < (0.6 * dists.Data[i, 1]))
        {
            // find image from the db to which current descriptor range belongs and increment similarity value.
            // in the actual implementation this should be done differently as it's not very efficient for large image collections.
            foreach (var img in imap)
            {
                if (img.IndexStart <= i && img.IndexEnd >= i)
                {
                    img.Similarity++;
                    break;
                }
            }
        }
    }
}

/// <summary>
/// Concatenates descriptors from different sources (images) into single matrix.
/// </summary>
/// <param name="descriptors">Descriptors to concatenate.</param>
/// <returns>Concatenated matrix.</returns>
public Matrix<float> ConcatDescriptors(IList<Matrix<float>> descriptors)
{
    int cols = descriptors[0].Cols;
    int rows = descriptors.Sum(a => a.Rows);

    float[,] concatedDescs = new float[rows, cols];

    int offset = 0;

    foreach (var descriptor in descriptors)
    {
        // append new descriptors
        Buffer.BlockCopy(descriptor.ManagedArray, 0, concatedDescs, offset, sizeof(float) * descriptor.ManagedArray.Length);
        offset += sizeof(float) * descriptor.ManagedArray.Length;
    }

    return new Matrix<float>(concatedDescs);
}

public class IndecesMapping
{
  public int IndexStart { get; set; }
  public int IndexEnd { get; set; }
  public int Similarity { get; set; }
  public string fileName { get; set; }
}

private const double surfHessianThresh = 300;
private const bool surfExtendedFlag = true;
private SURFDetector detector = new SURFDetector(surfHessianThresh, surfExtendedFlag);

Sneaky Electrons

Miscellaneous Technical Stuff.

Matching Image to a Collection of Images With Emgu CV

Comments