全局最优几何匹配问题的简单有效分支定界算法的比较

188理论计算机科学电子笔记46（2001）网址：http://www.elsevier.nl/locate/entcs/volume46.html15页一种实用的全局最优不确定性Thomas M. Breuel1施乐帕洛阿尔托研究中心3333Coyote Hill RoadPalo Alto，CA94304摘要不确定条件下的几何匹配是计算机视觉中一个长期存在的问题。本文提出了一种简单而有效的分支定界算法，用于在各种允许的变换（平移、等距、等形变换等）和各种允许的特征类型（点特征、有向点特征、线特征、线段特征等）下寻找几何匹配问题的全局最优解。该算法只需要实现正向变换（模型到图像）和提供误差模型。文中给出了该算法与对齐方法和Hough变换方法的比较结果.1介绍计算机和机器视觉中的许多问题涉及几何模型与几何不确定性下的图像数据的匹配这些问题可以描述如下。假设模型由几何图元（点、线段等）的集合组成，通常称为假设图像通过模型特征的几何变换T（例如，模型的平移和旋转）、某些特征的删除（遮挡）、将已知分布的噪声添加到图像中的特征位置、以及添加不是从模型导出的随机背景特征（杂波）现在让我们假设噪声是由某个误差界限定的。在简单的附加假设下，可以通过最大化在给定误差范围下可以与模型特征相对应的图像特征的数量来找到图像1电子邮件地址：tbreuel@parc.xerox.com2001年由ElsevierScienceB出版。 诉 在CCBY-NC-ND许可下开放访问。布·鲁尔189并且在某种模型到图像的变换T.因此，对象识别问题通常被形式化为在给定的可能变换空间中识别变换T的几何匹配问题，该变换T在给定的误差界限下使最大数量的模型特征与图像特征相对应。各种各样的算法已经被开发用于解决这些类型的几何匹配问题。本文不能希望对这些技术进行全面的调查，但以下描述了该领域中与本文所述算法相关的一些主要思想通过对齐进行识别[15]的工作原理是重复选择一小部分模型特征，并将它们与一系列图像特征相对应这些集合的大小由为了唯一地确定变换所需的特征对应的最小数量确定。然而，由于根据模型和图像特征之间的对应关系计算的变换是基于已经被位置误差破坏的数据来计算的，因此以这种方式确定的变换将不一定是使特征对应关系的总数最大化的变换。因此，通过比对的识别仅仅是最佳几何匹配的近似或启发。对应搜索[12]是一种与对齐识别密切相关的方法。然而，不是使用最小数量的对应关系，而是在搜索树中探索图像与模型特征之间的可能对应关系，并且对于给定的对应关系集合，例如使用最小二乘法来确定总体“良好”变换。如果运行完成，这样的搜索算法将找到图像和模型之间的最佳匹配然而，这样的搜索方法受到组合爆炸。在文献中已经描述了几种可证明的多项式时间几何匹配算法（例如，Cass[9]）。有许多方法可以查看和实现这些算法，但就复杂性而言，它们似乎等同于扫描或探索由模型特征和图像特征之间的直接应用，这些方法似乎并不实用。然而，他们所基于的见解形成了本文所提出的算法的基础姿势聚类技术[20]基于检查图像和模型特征之间的许多不同假设对应关系所隐含的变换（“姿势”）。在给定误差范围内使许多图像和模型点对应的变换将倾向于在变换空间中聚类。然而，因为图像中的误差边界不能直接转换为变换空间中容易定义的误差边界，因此这种方法只是启发式的。霍夫变换（在[16]中回顾）是另一种与姿势聚类密切相关的几何匹配方法（并且早于它多年）。布·鲁尔190Fig. 1.几何匹配问题的一个简单例子。右边的图像包含左边图像的10个点的子集，这些点经过平移、旋转，每个点的位移小于5个像素。霍夫变换可以被视为在变换空间中使用各种简单的分箱方法来执行姿势聚类。Hough变换易于实现且速度相当快;通过仔细调整，它们可以给出合理可靠的答案。然而，像其他姿势聚类技术一样，霍夫变换方法不能完全准确地对位置误差进行然而，与大多数其他几何匹配技术不同，霍夫变换也不强制约束，即单个模型特征仅产生单个图像特征。因此，霍夫变换可能非常容易受到误报和漏报的影响。粗略地说，这些方法分为两类：保证正确的解决方案，但具有高复杂性，可能难以实现的方法，以及快速但启发式的方法，从某种意义上说，它们不能保证找到最佳解决方案。RAST（变换空间自适应细分识别）系列算法[3]将可用性能与保证找到几何定义良好的解决方案相结合。RAST算法已被描述用于有界误差下的线查找[6]、用于同构变换下的几何匹配[2]以及用于平移和旋转下的点特征的几何匹配其他作者已经使用类似RAST的算法在高斯误差下进行匹配[17]。分支定界式算法最近在计算机视觉中受到了更多的关注（例如，[13 18.我们将在结论中对这些方法进行比较布·鲁尔191不||−||2输入该算法有两种输入。首先，存在数据无关部分：计算从模型到图像特征的参数化几何变换的函数，以及评估单个变换的模型特征和图像特征之间的匹配质量的函数第二，数据依赖部分：模型和图像特征的实际为了简单起见，并且不失一般性，让我们假设可能的变换T的集合由单位超立方体[0， 1]D的元素参数化。 我们将使用T来表示转换本身及其参数化。例如，对于等距（平移和旋转）下的匹配，T的参数空间将是[0，1]3。对于图像和模型点的集合，其与原点的距离均以512个像素为界，我们可以选择变换T的参数化为如下所示：（一）xjyJy（二）=cos2π T3− sin2πT3 x+ 1024T1sin 2πT3cos 2πT3y1024T2我们对这个参数化不做任何特殊的假设，除了它的导数对于任何变换和任何固定的界限都应该是有界的。在模型特征的坐标上：对于T∈[0， 1]D和x，y常数，（三）xJ∂Ti （T，x，y）const<和阿吉吉∂Ti（T，x，y）常数<该算法的另一个与数据无关的成分是一个在我们的错误模型下计算匹配的函数。为了讨论的具体性，让我们假设一个有界误差模型，尽管其他误差模型（如高斯模型）可以很容易地合并进来，而且变化很小。特征匹配函数b将变换后的模型特征TM、图像特征I和误差界ρ作为输入，并计算匹配分数。我们要求特征匹配函数是单调的：(4)b（TM，I，ρ）≤b（TM，I，ρJ）如果ρ ρJ这种单调性条件对于所有常用的匹配标准都是满足的（并且很容易验证），包括有界误差下的匹配，任何度量下的匹配以及高斯误差下的匹配在点特征的情况下，b（TM，I，ρ）可以简单地定义为谓词TM I ρ的指示函数，即，- 函数，如果变换的模型特征TM和图像特征I之间的距离小于ρ，则该函数取值1，否则取在线段特征的情况下，计算机视觉中使用的另一个常见特征b（TM，I，ρ）可以定义为线段的总长度布·鲁尔192{}我{}图二.一个例子的安排所产生的约束集在匹配问题下的翻译。- 图像线段I的落在变换后的模型线段TM的距离ρ内的子线段。注意，这样的测度仍然满足单调性条件。与特征匹配函数一起，我们还假设（对于有界误差匹配）误差界的选择。观察到b（TM，I，ρ）将被计算为与所选误差界不同的ρ值。该算法的数据相关输入是一组模型特征M={M1，...，RDM 以及一组图像特征=I1，...， 我在研发I。在平面的等距变换下的匹配点的情况图像点和模型点都是R2中的点。给定特征匹配函数b以及图像和模型fea的集合因此，变换T的匹配Q的总体质量由下式给出（五）ΣQ（T）=Σb（T Mi，Ij，）i =1. mj =1. n本文定义的几何匹配算法的任务是在所有可能的变换中优化这种匹配质量：（六）3该算法Tmax= arg maxT∈[0，1]D Q（T）我们将首先描述匹配算法，并在后面的章节中简要讨论几何和复杂性该算法是一个最好的第一次搜索通过递归细分的参数空间的转换。为了说明的简单性，让我们假设一个三维参数空间。作为递归细分，为了具体起见，让我们选择一个数据-布·鲁尔1932R112D112D图三. 在算法的实际运行期间探索的变换空间的细分。在这个例子中，变换空间是三维的，两个平移分量和一个旋转分量，但是空间已经沿着旋转维度向下投影到二维。 位置解决方案的可识别性是朝向空间左上部分的密集探索区域。变换空间独立kD-树型二叉剖分在树的底部是完全参数空间R1= [0，1]D。对于递归步骤，如果我们在搜索空间中查看表示区域Rr=[l1，h1]×.. . ×[1D，hD]. 设m=argmaxihi−lie是Rr的最大维数。 我们沿着那个维度分割区域两个子节点则是：（七）R= [l，h] ×. ×[l，（hm+ lm）] ×...×[l，h]（8）R= [l，h] ×. × [（hm+ lm），h]×... ×[l，h]图3显示了从实际运行中细分的变换空间（向下投影到二维对于我们扩展的变换空间中的每个区域Rr，我们计算任何变换T∈Rr可以生成。我们计算这个界限如下。对于每个模型特征Mi，我们可以计算距离上界δmin = max T，TJ∈Rr||TMi− T JMi||. 注意，δ可以是下式的函数：MD2r+1MD布·鲁尔194→∈∞Rr以及所讨论的模型特征Mi，δ=δ（Rr，Mi）还注意到，由于我们上面要求的有界导数性质，当diam（Ri）→0时δmin→0，并且我们要求上界δ（Ri，Mi）→0，当diam（Ri）0时，选择也接近0。我们可以从变换PJ=Tp的解析形式手工导出δ（Rr，Mi），也可以通过符号微分、数值微分或随机微分自动计算δ（Rr，M i）DOM采样(Such自动推导可以通过进一步将δ（Rr，Mi）从上面的δ（Rr，M）限制为δ（R r，M）来简化和加速，||const.）||

下载后可阅读完整内容，剩余1页未读，立即下载