Caetano Tibério S, Caelli Terry, Schuurmans Dale, Barone Dante A C
National ICT Australia, Locked Bag 8001, Canberra ACT 2601, Australia.
IEEE Trans Pattern Anal Mach Intell. 2006 Oct;28(10):1646-63. doi: 10.1109/TPAMI.2006.207.
This paper describes a novel solution to the rigid point pattern matching problem in Euclidean spaces of any dimension. Although we assume rigid motion, jitter is allowed. We present a noniterative, polynomial time algorithm that is guaranteed to find an optimal solution for the noiseless case. First, we model point pattern matching as a weighted graph matching problem, where weights correspond to Euclidean distances between nodes. We then formulate graph matching as a problem of finding a maximum probability configuration in a graphical model. By using graph rigidity arguments, we prove that a sparse graphical model yields equivalent results to the fully connected model in the noiseless case. This allows us to obtain an algorithm that runs in polynomial time and is provably optimal for exact matching between noiseless point sets. For inexact matching, we can still apply the same algorithm to find approximately optimal solutions. Experimental results obtained by our approach show improvements in accuracy over current methods, particularly when matching patterns of different sizes.
本文描述了一种针对任意维度欧几里得空间中刚性点模式匹配问题的新颖解决方案。尽管我们假设存在刚性运动，但允许有抖动。我们提出了一种非迭代的多项式时间算法，该算法保证能在无噪声情况下找到最优解。首先，我们将点模式匹配建模为加权图匹配问题，其中权重对应于节点之间的欧几里得距离。然后，我们将图匹配表述为在图形模型中寻找最大概率配置的问题。通过使用图刚性论证，我们证明了在无噪声情况下，稀疏图形模型产生的结果与完全连接模型等效。这使我们能够获得一种在多项式时间内运行的算法，并且对于无噪声点集之间的精确匹配可证明是最优的。对于不精确匹配，我们仍然可以应用相同的算法来找到近似最优解。我们的方法所获得的实验结果表明，与当前方法相比，在准确性方面有改进，特别是在匹配不同大小的模式时。
