Why do exact images not have exact descriptors?

Question

I'm developing an image recognition application and something is bugging me.

I am working with bitonal images (documents). If I make a copy of the same image file and compare both (actually comparing a sub-region of both [the same sub region]), i don't get 100% matches using SURF. Here's part of my code:

public double FindPercentMatch(Bitmap obj, Bitmap scene)
{

    // get scene key points
    VectorOfKeyPoint scenePoints = GetKeyPoints((Bitmap)scene.Clone());

    // if no scene points found, no need to go any further
    if (scenePoints == null || scenePoints.Size == 0) { return 0; }

    // get object key points
    VectorOfKeyPoint objectPoints = GetKeyPoints((Bitmap)obj.Clone());            

    // if not enough object key points found vs scene key points, then match can't be close enough (since
    // you can't have more matches than scene points anyway, so don't even try to match
    if (objectPoints == null || objectPoints.Size == 0 || (scenePoints.Size / objectPoints.Size < .15)) { return 0; }

    // we have enough key points, so compute descriptors for scene and object
    Matrix<float> objectDescriptors = GetDescriptors(objectPoints,(Bitmap)obj.Clone());
    Matrix<float> sceneDescriptors = GetDescriptors(scenePoints, (Bitmap)scene.Clone());
    int objectDescriptorCount = objectDescriptors == null ? 0 : objectDescriptors.Size.Height;
    int sceneDescriptorCount = sceneDescriptors == null ? 0 : sceneDescriptors.Size.Height;

    // find matches
    int sim = FindMatches(objectDescriptors, sceneDescriptors);

    // for testing so we know how many were found so we can monitor it
    log.Debug("descriptors1 = " + objectDescriptorCount + ", 2 = " + sceneDescriptorCount + ", matches=" + sim);

    double percent = 0;
    if (sim != 0)
    {
        percent = objectDescriptorCount != 0 ? (double)sim / (double)objectDescriptorCount : 0;
        log.Debug(percent * 100 + "%");
    }
    return percent;

}

public int FindMatches(Matrix<float> dbDescriptors, Matrix<float> queryDescriptors)
{

    double uniquenessThreshold = 0.6;

    if (dbDescriptors == null || queryDescriptors == null)
    {
        return 0;
    }
    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 eatch match over a certain threshold, add +1 to the number of 'good' matches
    int sim = 0;
    for (int i = 0; i < indices.Rows; i++)
    {
        // filter out all inadequate pairs based on distance between pairs
        if (dists.Data[i, 0] < (uniquenessThreshold * dists.Data[i, 1]))
        {
            sim++;
        }
    }
    return sim;
}

The expected outcome when using FindPercentMatch on the same sub-region of an image would be 100%, but depending on the image, it may be 70%, 99%, and I've even seen 101%.

Answer 1

I think I have fixed my problem by using the brute force matcher instead of flann index. Also, instead of using 2nn and comparing them, I only found the first nearest neighbor and counted any that were under a certain threshold as a 'good match'. Then I divide the good matches by the total number of keypoints for the OBJECT (not the scene) so I now end up with 0-100% matches.

        int numberOfNearestNeighbors = 1;

        double maxDistance = .30;

        BruteForceMatcher<float> matcher = new BruteForceMatcher<float>(DistanceType.L2);

        matcher.Add(dbDescriptors);

        var indices = new Matrix<int>(queryDescriptors.Rows, numberOfNearestNeighbors);
        using (Matrix<float> dist = new Matrix<float>(queryDescriptors.Rows, numberOfNearestNeighbors))
        {
            // null = no mask, use whole image
            matcher.KnnMatch(queryDescriptors, indices, dist, numberOfNearestNeighbors, null);

            int matchesUnderMaxDistance = 0;
            float distance = 0;

            // filter matches that are too different
            for (int i = 0; i < indices.Rows; i++)
            {
                distance = dist.Data[i, 0];

                if (distance < maxDistance)
                {
                    matchesUnderMaxDistance++;
                }
            }

            return matchesUnderMaxDistance;
        }