search - 将特征与数据库匹配的快速(er)方式

Question

我正在做一个项目，我在图像中有一个特征，描述为一组 X 和 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

此搜索有效，但显然在大型数据库上会变得非常缓慢。有谁知道进行此类搜索的更快方法，或者至少是否有一种方法可以快速排除显然与描述符不匹配的特征？

Answer 1

从每个特征创建一个位集(一个 1 和 0 的数组)。

为您的搜索条件创建这样一个位掩码，然后只使用按位和将搜索掩码与您的功能进行比较。

使用这种方法，您可以将大部分工作转移到负责保存内容的例程中。此外，创建位掩码不应该是计算密集型的。

如果您只想排除绝对不匹配的特征，那么您的掩码创建算法应该处理这一点并创建有点模糊的位掩码。

创建此类掩码的最简单方法可能是创建一个与特征矩阵一样大的矩阵，并在为该特征设置的每个坐标中放置一个 1，在每个未设置的坐标中放置一个 0。然后将该矩阵变成一维行。然后将特征行与搜索掩码按位进行比较。

这类似于位图索引在大型数据库(例如 oracle)上工作的方式，但目的不同，并且没有内存中所有数据库行的完整位图图像。

其强大之处在于按位比较。

在 32 位机器上，每条指令可以执行 32 次比较，而在点比较中只能对整数进行一次比较。它为浮点运算产生更高的 yield ，具体取决于架构。