Explain this algorithm (compare points in the SURF algorithm)

Question

I need to know if this algorithm is known:

void getMatches(IpVec &ipts1, IpVec &ipts2, IpPairVec &matches, float ratio) { float dist, d1, d2; Ipoint *match; matches.clear(); for (unsigned int i = 0; i < ipts1.size(); i++) { d1 = d2 = FLT_MAX; for (unsigned int j = 0; j < ipts2.size(); j++) { dist = ipts1[i] - ipts2[j]; if (dist < d1) // if this feature matches better than current best { d2 = d1; d1 = dist; match = &ipts2[j]; } else if (dist < d2) // this feature matches better than second best { d2 = dist; } } // If match has a d1:d2 ratio < 0.65 ipoints are a match if (d1 / d2 < ratio) { // Store the change in position ipts1[i].dx = match->x - ipts1[i].x; ipts1[i].dy = match->y - ipts1[i].y; matches.push_back(std::make_pair(ipts1[i], *match)); } } } 

---

 class Ipoint { public: //! Destructor ~Ipoint() { }; //! Constructor Ipoint() : orientation(0) { }; //! Gets the distance in descriptor space between Ipoints float operator-(const Ipoint &rhs) { float sum = 0.f; for (int i = 0; i < 64; ++i) { //std::cout << i << "\n"; try { sum += (this->descriptor[i] - rhs.descriptor[i])*(this->descriptor[i] - rhs.descriptor[i]); } catch (char *str) { std::cout << "Caught some other exception: " << str << "\n"; } } return sqrt(sum); }; //! Coordinates of the detected interest point float x, y; //! Detected scale float scale; //! Orientation measured anti-clockwise from +ve x-axis float orientation; //! Sign of laplacian for fast matching purposes int laplacian; //! Vector of descriptor components float descriptor[64]; //! Placeholds for point motion (can be used for frame to frame motion analysis) float dx, dy; //! Used to store cluster index int clusterIndex; }; 

This compares the results of the SURF algorithm.

• Is this the nearest neighbor algorithm? It is like func looking for the closest point of each point.
• Can I do the same using Quadtree or kd-tree?
• Is there a better algorithm for comparing points of the image and know if they are the same or similar?
• Preferably I want to save them in mysql and build a kd tree to compare 1 image across all images, what is possible?
• Is RANSAC useful for anything in this task?
• Is there a way to catch false positives?

Answer 1

You asked a lot of questions, and I don’t think I can answer all of them, but here are the answers to the largest possible question than I can.

• This is most likely the nearest neighbor algorithm, the purpose of which is to find the two nearest points for each point in the first vector, and then check whether the ratio of their distances from a certain cutoff value is less.

• You can do this with quadtree or kd-tree, but since your points are all one-dimensional values, you could do much better using a balanced binary search tree. Given such a tree, if you put a linked list through nodes, you can find k nearest neighbors at some test point p by looking at the closest element p in the binary search tree and then going through (k + 1) steps in each and take the k nearest points of that what you find. This is done in time O (log n + k), where n is the number of points and k is as indicated above. This is significantly more efficient than what you have now, which takes O (n) time to search.

  If the dimension of your vector function is more than 1, but less than 20, then the use of kd-trees will be a very effective measure.

  For higher measurements, you can either reduce the number of measurements with a PCA before applying the kd tree, or use a more scalable ANN structure, such as location sensitivity.

• SURF is best suited for scene and object detection. If you need to find out if the two images match, you would be better off with global descriptor algorithms such as GIST. The advantage of using a global descriptor is that you get one vector for the whole image, and image comparison is performed with a simple Euclidean distance.

• You could do it using MySQL because you don't need a kd tree. A simple balanced binary tree should be sufficient.

• RANSAC is a model estimation method that is emission resistant. This is useful for using the SURF functions to combine multiple photos into a 3D scene.

• Verification of false positives is, of course, a mechanical training exercise, and I am not well prepared in this area. You could probably do this using a supervised learning algorithm (like SVM, a reinforced decision tree or a neural network), but I don’t know enough to let you know.

Hope this helps!

Answer 2

I will just answer 5, since templatetypedef addresses the rest. RANSAC is a method for evaluating parameters (such as finding the line most suitable for a set of data points). Thus, it cannot be useful in finding the nearest neighbors.