# Matching the feature points

I have 2 vector of keypoints like this: vector<keypoint> points; vector<keypoint> keypoints; fea.detect(t,keypoints); goodFeaturesToTrack(t,points,100,0.001,8,CV_8UC1,5,false,0.04);

I need to store those keypoints which are at the same pixel location in both vectors. How can i do it? (eg., if there is a feature point at(3,4) in both vectors i should take it.. else i should not)

edit retag close merge delete

Sort by ยป oldest newest most voted

Edit:

I wanted to test if using a map could be more "efficient" than a double loops.

The key in the map is the hash code computed from the 2D coordinate of the keypoint. The approach is inspired by similar methods in Java or other languages, but I don't know if there is a better way to store a cv::Point2f in a map.

The following code try to bench between 3 methods for 1000 iterations:

• use a map to store the list of keypoints, the key is the 2D coordinate so we can check for same location
• sort the vectors and find keypoints located in same coordinates using two loops
• use two loops to find keypoints located in same coordinates

The results are:

vectorOfKeypoints1=4254 ; vectorOfKeypoints2=3042
Times passed in seconds for 1000 iterations (map): 1.49184
Times passed in seconds for 1000 iterations (sort + loops): 54.9015
Times passed in seconds for 1000 iterations (loops): 25.4545


So, the map could be a good option and sorting is useless here.

The code:

bool compareKeypointDistance(const cv::KeyPoint &kpt1, const cv::KeyPoint &kpt2) {
double dist1 = cv::norm(kpt1.pt);
double dist2 = cv::norm(kpt2.pt);
return (dist1 < dist2);
}

bool isSamePoint(const cv::Point2f &pt1, const cv::Point2f &pt2, float eps) {
if( fabs(pt1.x - pt2.x) < eps && fabs(pt1.y - pt2.y) < eps ) {
return true;
}

return false;
}

int pointToHashCode(const cv::Point2f &point)
{
int hash = 23;
int odd_prime_number = 31;

int hash_x = (int) (point.x * 10.0f); //keep one decimal
hash = odd_prime_number * hash + hash_x;

int hash_y = (int) (point.y * 10.0f); //keep one decimal
return odd_prime_number * hash + hash_y;
}

void method_with_map(const std::vector<cv::KeyPoint> &vectorOfKeypoints1_, const std::vector<cv::KeyPoint> &vectorOfKeypoints2_,
std::vector<cv::KeyPoint> &vectorOfBothKeypoints1, std::vector<cv::KeyPoint> &vectorOfBothKeypoints2) {
//Copy vectors to be consistent with the other methods
std::vector<cv::KeyPoint> vectorOfKeypoints1 = vectorOfKeypoints1_;
std::vector<cv::KeyPoint> vectorOfKeypoints2 = vectorOfKeypoints2_;

//Map of keypoints located in the same 2D coordinate
std::map<int, std::vector<cv::KeyPoint> > mapOfKeypoints;
//Fill the map
for(std::vector<cv::KeyPoint>::const_iterator it1 = vectorOfKeypoints1.begin(); it1 != vectorOfKeypoints1.end(); ++it1) {
int hash = pointToHashCode(it1->pt);
mapOfKeypoints[hash].push_back(*it1);
}

for(std::vector<cv::KeyPoint>::const_iterator it2 = vectorOfKeypoints2.begin(); it2 != vectorOfKeypoints2.end(); ++it2) {
int hash = pointToHashCode(it2->pt);
//Check if the map contains the current hash for the current point
std::map<int, std::vector<cv::KeyPoint> >::const_iterator it1_find = mapOfKeypoints.find(hash);
if(it1_find != mapOfKeypoints.end()) {
bool equal = false;
for(std::vector<cv::KeyPoint>::const_iterator it1 = it1_find->second.begin(); it1 != it1_find->second.end(); ++it1) {
//Check for possible collisions
if( isSamePoint(it1->pt, it2->pt, std::numeric_limits<float>::epsilon()) ) {
equal = true;
vectorOfBothKeypoints1.push_back(*it1);
}
}

if(equal) {
vectorOfBothKeypoints2.push_back(*it2);
}
}
}
}

void method_with_sort_and_loops(const std::vector<cv::KeyPoint> &vectorOfKeypoints1_, const std::vector<cv::KeyPoint> &vectorOfKeypoints2_,
std::vector<cv::KeyPoint> &vectorOfBothKeypoints1, std::vector<cv::KeyPoint> &vectorOfBothKeypoints2) {
//Copy vectors to be consistent with the other methods
//Needed here to avoid to sort an already sorted vector
std::vector<cv::KeyPoint> vectorOfKeypoints1 = vectorOfKeypoints1_;
std::vector<cv::KeyPoint> vectorOfKeypoints2 = vectorOfKeypoints2_;

//Sort ...
more

Thanks a lot .. but this would require lot of time to complete for a single frame.. any other idea?

( 2016-02-05 10:10:58 -0500 )edit

Other ideas ?

Use a kd tree to efficiently get the closest neighbor in the other set.

Use a map and compute the hash of the coordinate of the point as a key.

( 2016-02-05 11:31:17 -0500 )edit

Official site

GitHub

Wiki

Documentation