c++ - 解释这个算法(比较SURF算法中的要点)

Question

我需要知道这个算法是否是已知的:

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算法的结果。

1. 这是最近邻算法？看起来函数正在搜索每个点的最近点。
2. 我可以使用 Quadtree 或 kd-tree 做同样的事情吗？
3. 是否有更好的算法来比较图像点并知道它们是否相同或相似？
4. 最好我想将它们存储到 mysql 中并构建一个 kd 树来比较所有图像中的 1 个图像，这可能吗？
5. RANSAC 对这项任务有用吗？
6. 有什么方法可以捕捉误报？

Answer 1

您问了很多问题，我想我无法回答所有问题，但这里已尽可能多地回答您的问题。

1. 这无疑是一种最近邻算法，其目标是找到与第一个 vector 中的每个点最近的两个点，然后检查它们的距离之比是否小于某个截止值。

2. 您可以使用四叉树或 kd 树执行此操作，但是因为您的点都是一维值，所以使用平衡二叉搜索树可以做得更好。给定这样一棵树，如果你通过节点​​串接一个链表，你可以通过在二叉搜索树中查找最近的元素 p 找到某个测试点 p 的 k 个最近邻居，然后在每个元素中遍历 (k + 1) 步方向并取你发现的 k 个最近点。这在时间 O(lg n + k) 中运行，其中 n 是点数，k 同上。这比您现在的效率要高得多，后者每次查找需要 O(n) 的时间。

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

   对于更高的维度，您可能希望在应用 kd 树之前使用 PCA 减少维数，或者使用更具可扩展性的 ANN 结构，例如局部敏感哈希。

3. SURF 最适合场景和物体检测。如果你需要找出两个图像是否相同，你最好使用全局描述符算法，例如 GIST。使用全局描述符的优点是您可以获得整个图像的单个 vector ，并且使用简单的欧几里得距离执行图像比较。

4. 您绝对可以使用 MySQL 来完成此操作，因为您不需要 kd-tree。一个简单的平衡二叉树就足够了。

5. RANSAC 是一种估计模型参数的方法，该方法对异常值具有鲁棒性。它对于使用 SURF 功能将多张照片组合成 3D 场景非常有用。

6. 检查误报绝对是一项机器学习练习，我在这方面没有受过良好训练。您或许可以使用监督学习算法(例如支持 vector 机、提升决策树或神经网络)来执行此操作，但我的知识还不足以就此向您提供建议。

希望这对您有所帮助!