c++ - How to find euclidean distance between keypoints of a single image in opencv

Question

I want to get a distance vector d for each key point in the image. The distance vector should consist of distances from that keypoint to all other keypoints in that image. Note: Keypoints are found using SIFT.

Im pretty new to opencv. Is there a library function in C++ that can make my task easy?

Answer 1

If you aren't interested int the position-distance but the descriptor-distance you can use this:

cv::Mat SelfDescriptorDistances(cv::Mat descr)
{
    cv::Mat selfDistances = cv::Mat::zeros(descr.rows,descr.rows, CV_64FC1);
    for(int keyptNr = 0; keyptNr < descr.rows; ++keyptNr)
    {
        for(int keyptNr2 = 0; keyptNr2 < descr.rows; ++keyptNr2)
        {
            double euclideanDistance = 0;
            for(int descrDim = 0; descrDim < descr.cols; ++descrDim)
            {
                double tmp = descr.at<float>(keyptNr,descrDim) - descr.at<float>(keyptNr2, descrDim);
                euclideanDistance += tmp*tmp;
            }

            euclideanDistance = sqrt(euclideanDistance);
            selfDistances.at<double>(keyptNr, keyptNr2) = euclideanDistance;
        }

    }
    return selfDistances;
}

which will give you a N x N matrix (N = number of keypoints) where Mat_i,j = euclidean distance between keypoint i and j.

with this input:

I get these outputs:

1. image where keypoints are marked which have a distance of less than 0.05

2. image that corresponds to the matrix. white pixels are dist < 0.05.

REMARK: you can optimize many things in the computation of the matrix, since distances are symmetric!

UPDATE:

Here is another way to do it:

From your chat I know that you would need 13GB memory to hold those distance information for 41381 keypoints (which you tried). If you want instead only the N best matches, try this code:

// choose double here if you are worried about precision!
#define intermediatePrecision float
//#define intermediatePrecision double
// 
void NBestMatches(cv::Mat descriptors1, cv::Mat descriptors2, unsigned int n, std::vector<std::vector<float> > & distances, std::vector<std::vector<int> > & indices)
{
    // TODO: check whether descriptor dimensions and types are the same for both!

    // clear vector
    // get enough space to create n best matches
    distances.clear();
    distances.resize(descriptors1.rows);
    indices.clear();
    indices.resize(descriptors1.rows);

    for(int i=0; i<descriptors1.rows; ++i)
    {
        // references to current elements:
        std::vector<float> & cDistances = distances.at(i);
        std::vector<int>  & cIndices = indices.at(i);
        // initialize:
        cDistances.resize(n,FLT_MAX);
        cIndices.resize(n,-1);  // for -1 = "no match found"

        // now find the 3 best matches for descriptor i:
        for(int j=0; j<descriptors2.rows; ++j)
        {
            intermediatePrecision euclideanDistance = 0;
            for( int dim = 0; dim < descriptors1.cols; ++dim)
            {
                intermediatePrecision tmp = descriptors1.at<float>(i,dim) - descriptors2.at<float>(j, dim);
                euclideanDistance += tmp*tmp;
            }
            euclideanDistance = sqrt(euclideanDistance);

            float tmpCurrentDist = euclideanDistance;
            int tmpCurrentIndex = j;

            // update current best n matches:
            for(unsigned int k=0; k<n; ++k)
            {
                if(tmpCurrentDist < cDistances.at(k))
                {
                    int tmpI2 = cIndices.at(k);
                    float tmpD2 = cDistances.at(k);

                    // update current k-th best match
                    cDistances.at(k) = tmpCurrentDist;
                    cIndices.at(k) = tmpCurrentIndex;

                    // previous k-th best should be better than k+1-th best //TODO: a simple memcpy would be faster I guess.
                    tmpCurrentDist = tmpD2;
                    tmpCurrentIndex =tmpI2;
                }
            }


        }
    }

}

It computes the N best matches for each keypoint of the first descriptors to the second descriptors. So if you want to do that for the same keypoints you'll set to be descriptors1 = descriptors2 ion your call as shown below. Remember: the function doesnt know that both descriptor sets are identical, so the first best match (or at least one) will be the keypoint itself with distance 0 always! Keep that in mind if using the results!

Here's sample code to generate an image similar to the one above:

int main()
{
    cv::Mat input = cv::imread("../inputData/MultiLena.png");

    cv::Mat gray;
    cv::cvtColor(input, gray, CV_BGR2GRAY);

    cv::SiftFeatureDetector detector( 7500 );
    cv::SiftDescriptorExtractor describer;

    std::vector<cv::KeyPoint> keypoints;

    detector.detect( gray, keypoints );

    // draw keypoints
    cv::drawKeypoints(input,keypoints,input);



    cv::Mat descriptors;
    describer.compute(gray, keypoints, descriptors);

    int n = 4;
    std::vector<std::vector<float> > dists;
    std::vector<std::vector<int> > indices;

    // compute the N best matches between the descriptors and themselves.
    // REMIND: ONE best match will always be the keypoint itself in this setting!
    NBestMatches(descriptors, descriptors, n, dists, indices);

    for(unsigned int i=0; i<dists.size(); ++i)
    {
        for(unsigned int j=0; j<dists.at(i).size(); ++j)
        {
            if(dists.at(i).at(j) < 0.05)
                cv::line(input, keypoints[i].pt, keypoints[indices.at(i).at(j)].pt, cv::Scalar(255,255,255) );
        }
    }

    cv::imshow("input", input);
    cv::waitKey(0);

    return 0;
}