Caetano Tibério S, McAuley Julian J
Statistical Machine Learning Program, NICTA, and the Research School of Information Sciences and Engineering, ANU, Canberra, Australia.
Spat Vis. 2009;22(5):443-53. doi: 10.1163/156856809789476083.
It has been shown that isometric matching problems can be solved exactly in polynomial time, by means of a Junction Tree with small maximal clique size. Recently, an iterative algorithm was presented which converges to the same solution an order of magnitude faster. Here, we build on both of these ideas to produce an algorithm with the same asymptotic running time as the iterative solution, but which requires only a single iteration of belief propagation. Thus our algorithm is much faster in practice, while maintaining similar error rates.
已经表明，通过具有小的最大团大小的联合树，可以在多项式时间内精确地解决等距匹配问题。最近，提出了一种迭代算法，其收敛到相同解的速度快一个数量级。在此，我们基于这两种思想来产生一种算法，该算法具有与迭代解相同的渐近运行时间，但只需要一次信念传播迭代。因此，我们的算法在实际应用中要快得多，同时保持相似的错误率。
