Matching the feature points

edit

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 ...