Fitting geometric models onto outlier contaminated data is provably
intractable. Many computer vision systems rely on random sampling heuristics to
solve robust fitting, which do not provide optimality guarantees and error
bounds. It is therefore critical to develop novel approaches that can bridge
the gap between exact solutions that are costly, and fast heuristics that offer
no quality assurances. In this paper, we propose a hybrid quantum-classical
algorithm for robust fitting. Our core contribution is a novel robust fitting
formulation that solves a sequence of integer programs and terminates with a
global solution or an error bound. The combinatorial subproblems are amenable
to a quantum annealer, which helps to tighten the bound efficiently. While our
usage of quantum computing does not surmount the fundamental intractability of
robust fitting, by providing error bounds our algorithm is a practical
improvement over randomised heuristics. Moreover, our work represents a
concrete application of quantum computing in computer vision. We present
results obtained using an actual quantum computer (D-Wave Advantage) and via
simulation. Source code: this https URL

该论文提出了一种使用混合量子经典算法的鲁棒拟合方法，采用一系列整型规划求解并实现全局解或误差界限，该方法可为计算机视觉中的随机启发式算法提供较实用的改进。

一个用于健壮拟合的混合量子 - 经典算法

A Hybrid Quantum-Classical Algorithm for Robust Fitting

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 * 树搜索，使其在过去几乎无法实现的一些输入上具有合理的效率。

共识最大化树搜索的再探讨

Consensus Maximization Tree Search Revisited

Consensus maximization is one of the most widely used robust fitting
paradigms in computer vision, and the development of algorithms for consensus
maximization is an active research topic. In this paper, we propose an
efficient deterministic optimization algorithm for consensus maximization.
Given an initial solution, our method conducts a deterministic search that
forcibly increases the consensus of the initial solution. We show how each
iteration of the update can be formulated as an instance of biconvex
programming, which we solve efficiently using a novel biconvex optimization
algorithm. In contrast to our algorithm, previous consensus improvement
techniques rely on random sampling or relaxations of the objective function,
which reduce their ability to significantly improve the initial consensus. In
fact, on challenging instances, the previous techniques may even return a worse
off solution. Comprehensive experiments show that our algorithm can
consistently and greatly improve the quality of the initial solution, without
substantial cost.

本文提出了一种高效的确定性优化算法，以增加一组解的最大一致性，该算法将每个迭代的更新公式化为双凸编程实例，并使用新颖的双凸优化算法高效求解。