Ask Your Question
0

Matching the feature points

asked 2016-02-05 06:38:00 -0500

vigneshr95 gravatar image

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 flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
0

answered 2016-02-05 07:20:49 -0500

Eduardo gravatar image

updated 2016-02-07 19:34:16 -0500

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)
edit flag offensive delete link more

Comments

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

vigneshr95 gravatar imagevigneshr95 ( 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.

Eduardo gravatar imageEduardo ( 2016-02-05 11:31:17 -0500 )edit
Login/Signup to Answer

Question Tools

1 follower

Stats

Asked: 2016-02-05 06:38:00 -0500

Seen: 172 times

Last updated: Feb 07 '16