Consensus maximization is widely used for robust fitting in computer vision.
However, solving it exactly, i.e., finding the globally optimal solution, is
intractable. A* tree search, which has been shown to be fixed-parameter
tractable, is one of the most efficient exact methods, though it is still
limited to small inputs. We make two key contributions towards improving A*
tree search. First, we show that the consensus maximization tree structure used
previously actually contains paths that connect nodes at both adjacent and
non-adjacent levels. Crucially, paths connecting non-adjacent levels are
redundant for tree search, but they were not avoided previously. We propose a
new acceleration strategy that avoids such redundant paths. In the second
contribution, we show that the existing branch pruning technique also
deteriorates quickly with the problem dimension. We then propose a new branch
pruning technique that is less dimension-sensitive to address this issue.
Experiments show that both new techniques can significantly accelerate A* tree
search, making it reasonably efficient on inputs that were previously out of
reach.

本文针对在计算机视觉中的鲁棒拟合策略 —— 全局最大值求解的问题，提出了两种新的加速策略：避免冗余路径的加速策略和对新的枝剪枝策略。实验证明，这两种新技术可以极大地加速 A * 树搜索，使其在过去几乎无法实现的一些输入上具有合理的效率。