快速(呃)匹配功能到数据库的方式

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，在每个不是特征的坐标中放置一个零。然后将该矩阵转换为一维行。然后将特征行与搜索掩码按位进行比较。

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

其威力在于按位比较。

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