快速（呃）匹配功能到数据库的方法

我正在开展一个项目，我在图像中有一个特征，描述为一组X＆amp; Y坐标（每个特征5-10个点），对于此功能是唯一的。我还有一个包含数千个功能的数据库，每个功能都有相同类型的描述符。结果如下：

myFeature: (x1,y1), (x2,y2), (x3,y3)...

myDatabase: Feature1: (x1,y1), (x2,y2), (x3,y3)...
            Feature2: (x1,y1), (x2,y2), (x3,y3)...
            Feature3: (x1,y1), (x2,y2), (x3,y3)...
            ...

我想在myDatabase的功能中找到myFeature的最佳匹配。匹配这些功能的最快方法是什么？目前我正在踩着数据库中的每个功能并比较每个单独的点：

bestScore = 0
for each feature in myDatabase:
    score = 0
    for each point descriptor in MyFeature:
        find minimum distance from the current point to the...
          points describing the current feature in the database
        if the distance < threshold:
            there is a match to the current point in the target feature
            score += 1

    if score > bestScore:
        save feature as new best match

这种搜索有效，但很明显它在大型数据库上变得非常缓慢。有没有人知道更快的方法来进行这种类型的搜索，或者至少是否有办法快速排除明显与描述符不匹配的功能？

已邀请:

2 个回复

视蕉梁拌客

从每个功能创建一个bitset（1和0的数组）。为您的搜索条件创建这样的位掩码，然后只使用按位并将搜索掩码与您的功能进行比较。通过这种方法，您可以将大多数工作转移到负责保存内容的例程。此外，创建位掩码不应该是计算密集型的。如果你只是想排除绝对无法匹配的功能，那么你的掩码创建算法应该处理它并创建有点模糊的位掩码。创建此类蒙版的最简单方法可能是创建一个与要素矩阵一样大的矩阵，并在为要素设置的每个坐标中放置一个，而在每个坐标中放置一个非零。然后将该矩阵转换为一维行。然后按比特将特征行与搜索掩码进行比较。这类似于位图索引在大型数据库（例如oracle）上工作的方式，但具有不同的意图并且没有内存中所有数据库行的完整位图图像。这种力量在于逐点比较。在32位机器上，你可以在每个指令执行32次比较，只需在点比较中使用整数进行比较。它可以为浮点运算提供更高的效果，具体取决于架构。

锯康

这通常看起来像空间索引问题。这不是我的领域，但您可能需要构建一种树索引，例如四叉树，您可以使用它来轻松搜索要素。您可以在此维基百科文章中找到一些链接：http：//en.wikipedia.org/wiki/Spatial_index 您可以在现有空间数据库中轻松实现这个问题。它的描述与GIS非常相似。你可以做的一件事就是为每个特征计算一个重力点，并用它来缩小搜索空间（一维搜索更容易构建一个索引），但这有一个缺点就是只是一个启发式（取决于你的特征的形状，重力点可能最终在奇怪的地方）。

要回复问题请先登录或注册

快速（呃）匹配功能到数据库的方法

2 个回复

发起人

template_matching

问题状态

快速（呃）匹配功能到数据库的方法

与内容相关的链接

2 个回复

发起人

template_matching

问题状态