解释这一算法（比较SURF算法分）

我需要知道，如果这个算法是一个已知的一个：解释这一算法（比较SURF算法分）

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; 
};

这SURF算法的结果进行比较。

这是最近邻居算法吗？看起来func正在搜索每个点的最近点。
我可以使用Quadtree或kd-tree来做同样的事吗？
有一个更好的算法来比较图像点，并知道它们是否相同或相似？
优先我想将它们存储到mysql中，并构建一个kd-tree来比较所有图像中的1张图像，这可能吗？
RANSAC对于此任务中的任何内容都很有用？
有什么方法可以捕获误报？

来源

2011-08-05 Wiliam

我投票给您最后的评论，没有必要和时间回答。 – Wiliam

http://stackoverflow.com/questions/5962131/c-application-collapsing-after-some-hours需要你跟进。 –

你问了很多问题，我不认为我可以回答所有问题，但这里有尽可能多的问题的答案。

这肯定是一个最近邻算法，其目的是要找到两个最接近的点在第一向量中的每个点，然后检查他们的距离之比是否小于一定的临界值。
您可以与四叉树或KD树这样做，而是因为你的观点都是一维的值，你可以做的更好的利用平衡二叉搜索树。给定这样一棵树，如果你通过节点对一个链表进行线程化，你可以在二叉搜索树中查找最接近的元素p，然后在每个步骤中遍历（k + 1）个步骤，找到某个测试点p的k个最近邻居方向，并采取你找到的k个最接近的点。这在时间O（lg n + k）中运行，其中n是点数并且k如上所述。这比现在更有效，每次查找需要O（n）个时间。

如果您的特征向量的维数大于1但小于20，那么使用kd-trees将是非常有效的度量。

对于更高的维度，您可能希望在应用kd树之前使用PCA减少维数，或者使用更具可扩展性的ANN结构（如局部敏感散列）。
SURF最适合场景和物体检测。如果您需要查明两幅图像是否相同，则使用全局描述符算法（如GIST）会更好。使用全局描述符的优点是，您可以获得整个图像的单个矢量，并使用简单的Eucledian距离执行图像比较。
你绝对可以使用MySQL来做这件事，因为你不需要kd-tree。一个简单的平衡二叉树应该就足够了。
RANSAC是一种估计对异常值有效的模型参数的方法。使用SURF功能将多张照片组合成3D场景非常有用。
检查误报肯定是一个机器学习练习，我在这方面没有很好的训练。你可能可以使用监督学习算法（如SVM，增强型决策树或神经网络）来做到这一点，但我不知道这方面的建议。

希望这有助于！

来源

2011-08-05 01:28:55 templatetypedef

对不起，我忘了告诉你点的课程，我认为我需要64/128尺寸，所以也许对于100万张图片，我需要一个随机kd-tree。我一直在阅读关于GIST的内容，现在我正在使用SURF，并且我拥有本地特性，全局特性的概念对我来说是新的，我会寻找更多信息。如果我使用kd-tree，关于MySQL我必须先构建树。谢谢。 – Wiliam

@Wiliam：当维数低于20时，kd-tree的性能最好。对于你的问题，你可能想要先使用类似PCA的东西来降低维度，或者使用更具可伸缩性的ANN结构，比如局部敏感散列。 –

@templatetypedef，uf，我不知道这是否是更好的解决方案。我在一些论文中使用过他们使用随机kd-tree来存储这些特征，但是我不知道更多的细节...... – Wiliam

我只会回答5，因为templatetypedef解决了其余问题。 RANSAC是一种参数估计方法（有点像找到最适合一组数据点的线）。所以它在最近的邻居搜索中并不直接有用。

来源

2011-08-05 02:40:21

谢谢，我已经在互联网中用于加入图像。 – Wiliam

解释这一算法（比较SURF算法分）

回答

相关问题