4

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

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

2 回答 2

4

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

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

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

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

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

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

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

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

  6. 检查误报绝对是一种机器学习练习，我在这方面没有受过良好的训练。您可能可以使用监督学习算法（例如 SVM、增强决策树或神经网络）来做到这一点，但我对此知之甚少，无法为您提供建议。

希望这可以帮助！

于 2011-08-05T01:28:55.550 回答
1

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

于 2011-08-05T02:40:21.533 回答