Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

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

Eduardo gravatar image

One possible solution would be:

  • sort the two vectors by distance to (0 ; 0)
  • for each keypoint in vector1, iterate in vector2 to find keypoints that are located at the same pixel coordinate

It is certainly not optimal but the idea should be there.

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 main() {
  //Sort vectorOfKeypoints1
  std::sort(vectorOfKeypoints1.begin(), vectorOfKeypoints1.end(), compareKeypointDistance);

  //Sort vectorOfKeypoints2
  std::sort(vectorOfKeypoints2.begin(), vectorOfKeypoints2.end(), compareKeypointDistance);

  //Vector to store keypoints that are present in both vectors
  std::vector<cv::KeyPoint> vectorOfBothKeypoints1, vectorOfBothKeypoints2;

  //Iterate through vectorOfKeypoints1
  for(std::vector<cv::KeyPoint>::const_iterator it1 = vectorOfKeypoints1.begin();
      it1 != vectorOfKeypoints1.end(); ++it1) {
    bool alreayAdded = false;
    //Iterate through vectorOfKeypoints2
    for(std::vector<cv::KeyPoint>::const_iterator it2 = vectorOfKeypoints2.begin();
        it2 != vectorOfKeypoints2.end(); ++it2) {
      double dist1 = cv::norm(it1->pt);
      double dist2 = cv::norm(it2->pt);

      if(dist2 > dist1) {
        //No need to continue to iterate
        break;
      }

      //Test if the two points are located in the same coordinate
      if(isSamePoint(it1->pt, it2->pt, std::numeric_limits<float>::epsilon())) {
        if(!alreayAdded) {
          //Do not add it1 if already added
          alreayAdded = true;
          vectorOfBothKeypoints1.push_back(*it1);
        }
        vectorOfBothKeypoints2.push_back(*it2);
      }
    }
  }

  //Print vectorOfBothKeypoints1
  for(std::vector<cv::KeyPoint>::const_iterator it = vectorOfBothKeypoints1.begin();
      it != vectorOfBothKeypoints1.end(); ++it) {
    std::cout << "vectorOfBothKeypoints1=" << it->pt << std::endl;
  }

  //Print vectorOfBothKeypoints2
  for(std::vector<cv::KeyPoint>::const_iterator it = vectorOfBothKeypoints2.begin();
      it != vectorOfBothKeypoints2.end(); ++it) {
    std::cout << "vectorOfBothKeypoints2=" << it->pt << std::endl;
  }

  return 0;
}

One possible solution would be:

  • sort the two vectors by distance to (0 ; 0)
  • for each keypoint in vector1, iterate in vector2 to find keypoints that are located at the same pixel coordinate

It is certainly not optimal but the idea should be there.

You can also skip the sorting part and just iterate in vector1 and iterate in vector2 to find keypoints located at the same position. I thought that sorting vectors is possibly more optimal but I may be wrong.

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 main() {
  //Sort vectorOfKeypoints1
  std::sort(vectorOfKeypoints1.begin(), vectorOfKeypoints1.end(), compareKeypointDistance);

  //Sort vectorOfKeypoints2
  std::sort(vectorOfKeypoints2.begin(), vectorOfKeypoints2.end(), compareKeypointDistance);

  //Vector to store keypoints that are present in both vectors
  std::vector<cv::KeyPoint> vectorOfBothKeypoints1, vectorOfBothKeypoints2;

  //Iterate through vectorOfKeypoints1
  for(std::vector<cv::KeyPoint>::const_iterator it1 = vectorOfKeypoints1.begin();
      it1 != vectorOfKeypoints1.end(); ++it1) {
    bool alreayAdded = false;
    //Iterate through vectorOfKeypoints2
    for(std::vector<cv::KeyPoint>::const_iterator it2 = vectorOfKeypoints2.begin();
        it2 != vectorOfKeypoints2.end(); ++it2) {
      double dist1 = cv::norm(it1->pt);
      double dist2 = cv::norm(it2->pt);

      if(dist2 > dist1) {
        //No need to continue to iterate
        break;
      }

      //Test if the two points are located in the same coordinate
      if(isSamePoint(it1->pt, it2->pt, std::numeric_limits<float>::epsilon())) {
        if(!alreayAdded) {
          //Do not add it1 if already added
          alreayAdded = true;
          vectorOfBothKeypoints1.push_back(*it1);
        }
        vectorOfBothKeypoints2.push_back(*it2);
      }
    }
  }

  //Print vectorOfBothKeypoints1
  for(std::vector<cv::KeyPoint>::const_iterator it = vectorOfBothKeypoints1.begin();
      it != vectorOfBothKeypoints1.end(); ++it) {
    std::cout << "vectorOfBothKeypoints1=" << it->pt << std::endl;
  }

  //Print vectorOfBothKeypoints2
  for(std::vector<cv::KeyPoint>::const_iterator it = vectorOfBothKeypoints2.begin();
      it != vectorOfBothKeypoints2.end(); ++it) {
    std::cout << "vectorOfBothKeypoints2=" << it->pt << std::endl;
  }

  return 0;
}

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 vectorOfKeypoints1
  std::sort(vectorOfKeypoints1.begin(), vectorOfKeypoints1.end(), compareKeypointDistance);

  //Sort vectorOfKeypoints2
  std::sort(vectorOfKeypoints2.begin(), vectorOfKeypoints2.end(), compareKeypointDistance);

  //Iterate through vectorOfKeypoints1
  for(std::vector<cv::KeyPoint>::const_iterator it1 = vectorOfKeypoints1.begin();
    it1 != vectorOfKeypoints1.end(); ++it1) {
      bool alreayAdded = false;
      //Iterate through vectorOfKeypoints2
      for(std::vector<cv::KeyPoint>::const_iterator it2 = vectorOfKeypoints2.begin();
        it2 != vectorOfKeypoints2.end(); ++it2) {
          double dist1 = cv::norm(it1->pt);
          double dist2 = cv::norm(it2->pt);

          if(dist2 > dist1) {
            //No need to continue to iterate
            break;
          }

          //Test if the two points are located in the same coordinate
          if(isSamePoint(it1->pt, it2->pt, std::numeric_limits<float>::epsilon())) {
            if(!alreayAdded) {
              //Do not add it1 if already added
              alreayAdded = true;
              vectorOfBothKeypoints1.push_back(*it1);
            }
            vectorOfBothKeypoints2.push_back(*it2);
          }
      }
  }
}

void method_with_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
  std::vector<cv::KeyPoint> vectorOfKeypoints1 = vectorOfKeypoints1_;
  std::vector<cv::KeyPoint> vectorOfKeypoints2 = vectorOfKeypoints2_;

  //Iterate through vectorOfKeypoints1
  for(std::vector<cv::KeyPoint>::const_iterator it1 = vectorOfKeypoints1.begin();
    it1 != vectorOfKeypoints1.end(); ++it1) {
      bool alreayAdded = false;
      //Iterate through vectorOfKeypoints2
      for(std::vector<cv::KeyPoint>::const_iterator it2 = vectorOfKeypoints2.begin();
        it2 != vectorOfKeypoints2.end(); ++it2) {
          double dist1 = cv::norm(it1->pt);
          double dist2 = cv::norm(it2->pt);

          //Test if the two points are located in the same coordinate
          if(isSamePoint(it1->pt, it2->pt, std::numeric_limits<float>::epsilon())) {
            if(!alreayAdded) {
              //Do not add it1 if already added
              alreayAdded = true;
              vectorOfBothKeypoints1.push_back(*it1);
            }
            vectorOfBothKeypoints2.push_back(*it2);
          }
      }
  }
}

int main()
{
  //[...]

  std::cout << "vectorOfKeypoints1=" << vectorOfKeypoints1.size() << " ; vectorOfKeypoints2=" << vectorOfKeypoints2.size() << std::endl;

  //Vector to store keypoints that are present in both vectors
  std::vector<cv::KeyPoint> vectorOfBothKeypoints1, vectorOfBothKeypoints2;

  int nbIterations = 1000;
  double t1 = (double) cv::getTickCount();
  for(int cpt = 0; cpt < nbIterations; cpt++) {
    vectorOfBothKeypoints1.clear();
    vectorOfBothKeypoints2.clear();
    method_with_map(vectorOfKeypoints1, vectorOfKeypoints2, vectorOfBothKeypoints1, vectorOfBothKeypoints2);
  }
  t1 = ((double) cv::getTickCount() - t1) / cv::getTickFrequency();
  std::cout << "Times passed in seconds for " << nbIterations << " iterations (map): " << t1 << std::endl;

  double t2 = (double) cv::getTickCount();
  for(int cpt = 0; cpt < nbIterations; cpt++) {
    vectorOfBothKeypoints1.clear();
    vectorOfBothKeypoints2.clear();
    method_with_sort_and_loops(vectorOfKeypoints1, vectorOfKeypoints2, vectorOfBothKeypoints1, vectorOfBothKeypoints2);
  }
  t2 = ((double) cv::getTickCount() - t2) / cv::getTickFrequency();
  std::cout << "Times passed in seconds for " << nbIterations << " iterations (sort + loops): " << t2 << std::endl;

  double t3 = (double) cv::getTickCount();
  for(int cpt = 0; cpt < nbIterations; cpt++) {
    vectorOfBothKeypoints1.clear();
    vectorOfBothKeypoints2.clear();
    method_with_loops(vectorOfKeypoints1, vectorOfKeypoints2, vectorOfBothKeypoints1, vectorOfBothKeypoints2);
  }
  t3 = ((double) cv::getTickCount() - t3) / cv::getTickFrequency();
  std::cout << "Times passed in seconds for " << nbIterations << " iterations (loops): " << t3 << std::endl;


  //Print vectorOfBothKeypoints1
  for(std::vector<cv::KeyPoint>::const_iterator it = vectorOfBothKeypoints1.begin();
    it != vectorOfBothKeypoints1.end(); ++it) {
      std::cout << "vectorOfBothKeypoints1=" << it->pt << " ; hash=" << pointToHashCode(it->pt) << std::endl;
  }

  //Print vectorOfBothKeypoints2
  for(std::vector<cv::KeyPoint>::const_iterator it = vectorOfBothKeypoints2.begin();
    it != vectorOfBothKeypoints2.end(); ++it) {
      std::cout << "vectorOfBothKeypoints2=" << it->pt << " ; hash=" << pointToHashCode(it->pt) << std::endl;
  }

  return 0;
}

One possible solution would be:

  • sort the two vectors by distance to (0 ; 0)
  • for each keypoint in vector1, iterate in vector2 to find keypoints that are located at the same pixel coordinate

It is certainly not optimal but the idea should be there.

You can also skip the sorting part and just iterate in vector1 and iterate in vector2 to find keypoints located at the same position. I thought that sorting vectors is possibly more optimal but I may be wrong.

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 main() {
  //Sort vectorOfKeypoints1
  std::sort(vectorOfKeypoints1.begin(), vectorOfKeypoints1.end(), compareKeypointDistance);

  //Sort vectorOfKeypoints2
  std::sort(vectorOfKeypoints2.begin(), vectorOfKeypoints2.end(), compareKeypointDistance);

  //Vector to store keypoints that are present in both vectors
  std::vector<cv::KeyPoint> vectorOfBothKeypoints1, vectorOfBothKeypoints2;

  //Iterate through vectorOfKeypoints1
  for(std::vector<cv::KeyPoint>::const_iterator it1 = vectorOfKeypoints1.begin();
      it1 != vectorOfKeypoints1.end(); ++it1) {
    bool alreayAdded = false;
    //Iterate through vectorOfKeypoints2
    for(std::vector<cv::KeyPoint>::const_iterator it2 = vectorOfKeypoints2.begin();
        it2 != vectorOfKeypoints2.end(); ++it2) {
      double dist1 = cv::norm(it1->pt);
      double dist2 = cv::norm(it2->pt);

      if(dist2 > dist1) {
        //No need to continue to iterate
        break;
      }

      //Test if the two points are located in the same coordinate
      if(isSamePoint(it1->pt, it2->pt, std::numeric_limits<float>::epsilon())) {
        if(!alreayAdded) {
          //Do not add it1 if already added
          alreayAdded = true;
          vectorOfBothKeypoints1.push_back(*it1);
        }
        vectorOfBothKeypoints2.push_back(*it2);
      }
    }
  }

  //Print vectorOfBothKeypoints1
  for(std::vector<cv::KeyPoint>::const_iterator it = vectorOfBothKeypoints1.begin();
      it != vectorOfBothKeypoints1.end(); ++it) {
    std::cout << "vectorOfBothKeypoints1=" << it->pt << std::endl;
  }

  //Print vectorOfBothKeypoints2
  for(std::vector<cv::KeyPoint>::const_iterator it = vectorOfBothKeypoints2.begin();
      it != vectorOfBothKeypoints2.end(); ++it) {
    std::cout << "vectorOfBothKeypoints2=" << it->pt << std::endl;
  }

  return 0;
}
Copyright OpenCV foundation, 2012-2018. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
about | faq | help | privacy policy | terms of service
Powered by Askbot version 0.10.2