5

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

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

4

2 回答 2

2

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

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

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

如果您只是想排除绝对无法匹配的功能，那么您的掩码创建算法应该处理好这个问题并创建有点模糊的位掩码。

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

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

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

在 32 位机器上，每条指令可以执行 32 次比较，而在点比较中只能使用整数进行一次比较。根据架构，它为浮点运算产生更高的boni。

于 2010-11-05T12:55:44.257 回答
1

这通常看起来像一个空间索引问题。这不是我的领域，但您可能需要构建一种树索引，例如四叉树，您可以使用它来轻松搜索特征。您可以从这篇维基百科文章中找到一些链接：http ://en.wikipedia.org/wiki/Spatial_index

这可能是一个您可以在现有空间数据库中轻松实现的问题。它的描述非常类似于 GIS。

您可以做的一件事是为每个特征计算一个重心点，并使用它来稍微缩小搜索空间（一维搜索更容易为其建立索引），但这有一个缺点是只是一个启发式（取决于你的特征的形状，重心可能会出现在奇怪的地方）。

于 2010-11-05T14:00:04.230 回答