稳健拟合的量子-经典混合算法：鲁棒拟合公式解决整数规划和终止的全局解或误差界，使用量子退火器有效收紧边界，实际改进随机化算法，量...

417我我我我D|−|我|I|稳健拟合的量子-经典混合算法Anh-Dzung Doan1Michele Sasdelli1David Suter2Tat-JunChin11南澳大利亚阿德莱德大学计算机科学学院2西澳大利亚Edith Cowan大学理学院AI ML中心摘要将几何模型拟合到异常值污染的数据上可证明是棘手的。许多计算机视觉系统依赖于随机采样启发式算法来解决鲁棒拟合，其不提供最优性保证和误差界。因此，至关重要的是开发新的方法，可以弥合昂贵的精确解决方案和无法提供质量保证的快速制造之间的差距。本文提出了一种稳健拟合的量子-经典混合算法。我们的核心贡献是一个新的鲁棒拟合公式，解决了一系列的整数规划和终止的全局解或误差界。组合子问题可以用量子退火器处理，这有助于有效地收紧边界。虽然我们使用量子计算并没有克服鲁棒拟合的基本困难，但通过提供误差界限，我们的算法是对随机化算法的实际改进。此外，我们的工作代表了量子计算在计算机视觉中的具体应用。我们提出了使用实际量子计算机（D-Wave Advantage）和通过模拟1获得的结果。1. 介绍计算机视觉中传感和处理的不完善不可避免地会产生包含离群值的数据。因此，视觉管道必须对离群值具有鲁棒性，以减轻其有害影响。在3D视觉中，主要目标是恢复场景结构和相机运动，基本任务是将几何模型拟合到有噪声和离群值倾向的测量上。这通常通过共识最大化来框架[18]：给定N个数据点D={pi}N和a其中ri（x）是点pi相对于. r.t.x，并且x是给定的内点阈值。ri（x）的形式取决于具体的几何模型（更多细节见第2节）。（3）第三章。一个可达解（，x）由一个共识集和它的“见证”（估计）x组成问题（1）寻求最大共识集，其见证人x是模型2的稳健估计。许多计算机视觉系统采用随机采样，应用化学，即，RANSAC [32]及其变体（例如，[5，6，20，57，68，69]），用于共识最大化。基本的想法是反复拟合模型随机sam-pled极小子集 ，并返回最大值为共识集这样的算法只能近似（1），并且通常不提供最优性保证或误差表征，例如，在差异上的严格界限好吧此外，x{\displaystylex{\displaystyle x}}服从随机性，经常执行处理或重新运行以检查结果。不幸的是，共识最大化是不可证明的[4，16]，因此找到可以精确解决它的有效算法的希望很小。虽然对全局最优算法[13，17，44，54，55]进行了积极的研究，但这些技术仅适用于小输入实例（小d，N和/或离群值[17]）。弥合昂贵的精确算法和不提供质量的随机算法之间的差距是具有实际后果的鲁棒拟合的重要研究方向。为了实现这一目标，确定性近似算法[14，41，42，59，73]避免了穷举搜索（例如，分支定界）和随机化，而是采用确定性子例程，例如凸优化、邻近分裂等。这些方法避免了随机抽样的变幻莫测，有些甚至可以保证收敛[41，42，59]。然而，它们都没有提供误差界限。事实上，复杂性结果[4，16]也目标几何模型参数化i=1D排除了具有误差界的有效近似解x∈R，设PN为索引集{1，. - 是的- 是的，N}。我们的目标是解决部分受到深度学习在计算机视觉中的主导地位的鼓舞，基于学习的鲁棒几何MaxI∈PN，x∈RD|我|（一）已开发[10，60，70]。这种技术利用大型数据集中的统计数据来从S.T.ri（x）≤i∈I，2这也取决于使用正确的工具。大量的作品，1源代码：https://github.com/dadung/HQC-robust-fitting应用共识最大化建议通常不需要考虑设置阈值。我418|−|我|≤|≤≥CCCC ≤C cCD输入实例到所需的解决方案。尽管在基准数据集上显示出有希望的结果，但学习方法并不提供最优性保证和误差界。学习模型是否可以推广也是一个问题。总而言之，现有的鲁棒拟合算法，特别是那些以共识最大化为目标的算法，还没有令人满意地解决这个问题。因此值得研究基于新见解的新方法我们提出了一种新的方法，利用量子计算实现共识最大化。我们的核心贡献是一个共识最大化算法，迭代地解决了一系列整数规划，并终止于x或一个次优解x，具有已知的误差界ρ。整数程序是服从量子退火[64，章.8]，这是用来收紧绑定有效。 由于我们的方法采用凸子程序和随机采样，因此它是一种混合量子经典算法[11，36，40，56]。我们将使用实际的量子计算机D-Wave Advantage[23]以及模拟来展示结果。虽然我们的技术还没有超过最先进的算法，部分原因是由于当前量子技术的限制，但我们的工作代表了量子计算在计算机视觉中的具体应用。我们希望在社区中推动未来在这一主题上的努力。2. 相关工作节中1，我们提供了鲁棒拟合的概述然后在D-Wave Advantage上进行了验证与我们最接近的工作是[19]，他提出了一个稳健拟合的量子解决方案。然而，存在重要的差异：首先，[19]估计每点影响（离群度的度量）[66，67]用于离群值去除而不是共识最大化。其次，他们的算法基于门计算模型，这与我们工作中采用的量子退火方法有第三，[19]中的结果仅基于模拟;我们将在第二节中在此基础上与[19六、3. 重新定义共识最大化在这一节中，我们描述了我们的新的共识最大化和相关的理论结果的重新制定，be-forth使用的量子退火在SEC。4和SEC中的整体算法。五、3.1. 预赛在[19]之后，我们考虑准凸的残差ri（x），其封装了计算机视觉中的许多几何兴趣模型[38]。形式上，如果集合{x∈R|ri（x）≤ α}（2）是凸的，则ri（x）是拟凸的.请注意，假设拟凸残差不会降低共识最大化的计算难度[16]。对于C ∈PN，定义极大极小问题和最新的算法进展因此，我们将调查重点放在计算机视觉中的量子计算上。g（）=最小值x∈Rdmaxr i（x）.（三）i∈C许多量子方法已经被提出用于图像处理[15，27，71，74]，图像识别[26，50，51]和物体检测[45]。此外，有几种方法探索了分类和训练深度神经网络的任务[39，52，63]。最近，Golyanik和Theobalt [34]提出了一种实用的量子算法，用于旋转估计以对齐两个点集。他们的基本想法是对于拟凸ri（x），（3）是一个拟凸规划[3，30]，它是多项式时间可解的.请注意，g（）意味着这是一个共识集，因为所有的点都在误差范围内，达到（3）的极值。定义.0 如果g（C）≤n;旋转矩阵将问题公式化为二次无约束二元优化（QUBO），可以是f（C）=（四）1否则。量子退火器解决的问题Benkner等人。[7]提出通过将二次分配问题（QAP）公式化到QUBO us来解决图匹配问题。任何 这样的f（）= 0意味着这是一个共识集。因此，问题（1）可以重新表述为：惩罚的方式。他们进行了实验并对量子计算机D-Wave进行了分析MaxI∈PN|，s.t.|,s.t.f（I）=0，（5）2000Q。然而，量子计算机的局限性使它们无法解决大问题。为了解决这个问题，Q-Match [65]不是对QAP实施惩罚，而是提出迭代选择和解决QAP的子问题，这使得D-Wave退火机能够有效地处理大型问题。另一个有趣的工作是泉-419O{}\I我我我对于任何通过计算g（）来评估f（）可获得的可行性，证明x。给定一个具有见证人x的共识集，补码=1，. . . ，N是x的离群值。因此，问题（5）的tumSync [8]，它解决了多图像匹配背景下的同步问题这份工作照顾-minO∈PN|，s.t.|,s.t.f（{1，. - 是的- 是的 ，N}| 0）= 0，（6）充分阐述了QUBO的同步问题，即，找到具有最少离群值的模型。420一、我（k）BBB|B O|≥Bk=1--定义1（真内值和真离群值）。 设I为最大共识集，O={1，. - 是的- 是的 ，N}\n。我 们 称I为“真内点”，O为“真离群点”。性质1（单调性）。 对于（3）的拟凸剩余，给定子集P，Q，R ∈ PN，且P <$Q <$R，有g（P）≤g（Q）≤g（R）.通过推广，我们也有f（P）≤ f（Q）≤ f（R）。更多细节见[3，30]直观地说，向可行子集添加点只能潜在地使其不可行;相反的情况不可能成立。权利要求2. 子集是一致集当且仅当它是超图H的独立集。证据 参见第B补充材料。权利要求2证明了寻找最大共识集这等价于找到H的最大独立集。由于一个独立集的补集是一个顶点覆盖，所以它证明了最小化顶点覆盖是zminNz1这就引出了以下关键概念。定义2（依据）。 基B ∈ {1，. - 是的- 是的，N}是子集{0，1}S.T.BTz≥ 1，n = 1，. - 是的- 是的，K，（VC）使得对于每个B′，g（B′）g（B）≠ B。直觉上，从基中移除任何点都会导致子集的极大极小值缩小。性质2（组合维数）。极大极小问题（3）的组合维数δ是基的大小的上界[3，30]。 对于拟凸ri（x），δ =2d +1.权利要求1. 如果基础是不可行的，即，f（）=1，则1，即，不可行基包含至少一个真离群值。证据 参见第补充材料中的A3.2. 超图顶点覆盖定义二进制N向量z=[z1，. - 是的- 是的 ，z N] ∈ {0，1}N，（7）其中对应于非零zi的索引集合Cz={i ∈ {1，. - 是的- 是的，N} |zi= 1}。（八）离群值最小化问题（6）可以重新表示为这是一个0-1整数线性规划（ILP）。设置zi=1意味着移除第i个顶点，并且约束确保所有超边都被每个超边中的至少一个顶点权利要求1）。超图的形式主义已被应用于几何拟合[2，46，47，58]。然而，目标问题-[2，46，47，58]中的LEM是高阶聚类（例如，通过超图切割），这与我们的目标非常不同。由于两个原因，配方（VC• 超图的顶点覆盖是一个棘手的问题;• H中的超边数是指数的。然而，形式（VC）是服从量子退火，因为我们将显示在节。4.第一章去处理那些-peredges，我们提出了一种混合量子经典算法，节中5，增量生成超边。4. 量子解我们首先提供一个基本的介绍量子退火，然后描述我们的量子处理（VC）。4.1. 量子退火一 量子 退火炉 解决 优化问题minz∈{0，1}N阿利什卡1号体育场f（{1，. - 是的- 是的 ，N}| C（z）=0，（9）通过物理系统的能量最小化。哈密顿量定义了量子系统的能量分布其中zi=1意味着第i个点作为离群值被移除令b（k）K是对应于问题的所有不可行基的K个二进制N-向量，即， 对于每个k，f（Cb（k））=1，φb（k）φ1≤δ，（10）其中后者诉诸于组合维度（性质2）。 此外，不可行基的数量K=O（Nδ）。 定义具有顶点集V的超图H，421K联系 我们ΣΣTEM，它由许多相互作用的量子比特组成。该系统在退火结束时，可以从以下模型Q nn q n+Q nm q n q m= qTQq。（十二）n n m超边集E分别为H={V，E}，V={1，.- 是的- 是的，N}，E={Cb（k）}k=1. （十一）测量将N-量子比特量子态坍缩为q=[q1，q2，. . .，qN]，其中q n0，1，Q RN×N。Q的元素定义了量子比特之间的耦合，回想一下，超图是图的推广，其中一个超边可以与两个以上的顶点关联偏误;见[64，章。8]的双曲余切值。量子退火器解决了以下形式tices [2].在我们的超图（11）中，每个超边连接形成不可行基的顶点;见图11。1.一、minq∈{0，1}NqTQq，（13）422341289101156721i=1′δΣ×不m=1⊆≤（m）--联系我们10.80.60.40.2000. 51 1. 52.(a) 索引集为{1，. - 是的- 是的 ，12}。 无穷基={1，5，6}，={2，7，8}，={3，9，10}，={4，11，12}，={1，2，3}，={2，3，4}。 离群值集合O={1，2，3，4}。反感觉集合I ={5，6，7，8，9，10，11，12}。123456789101112(b) 顶点集V ={1，. - 是的- 是的 ，12}。 Hyperedges={1，5，6}，={2，7，8}，={3，9，10}， ={4，11，12}，={1，2，3}，={2，3，4}。顶点覆盖={1，2，3，4}。独立集={5，6，7，8，9，10，11，12}图1. （a）假设我们在平面上N=12点{（ai，bi）}N上拟合一条直线x ∈ R 2，残差ri（x）=。的2最大共识大小为8。还绘制了六个不可行的基础（颜色编码，注意总共有281个不可行的基础）。(b)基于我们的构造（Sec.3.2）。不可行基是超边。权利要求2意味着最大一致集等于最大独立集，最小离群集等于最小顶点覆盖。二次无约束二元优化{0，1}M×（N+δ′M+1），S=IMM×M恒等式（QUBO）. QUBO在经典机器上是难以处理的，但是量子退火机，凭借上面描述的物理过程，可以有效地解决这个问题。它允许N个量子比特通过叠加和纠缠态进化（量子隧穿），并且Q从最终MEA获得矩阵IM和Kronecker乘积I M。 此外，目标可以用二次形式T1T1 T1T2T1T2T2，（18）保证;见第二节。4.3实际限制。4.2. 超图顶点覆盖为QUBO其中J=IN0N×（δ′M+1）0（δ′M+1）×N0（δ′M+1）×（δ′M+1），其中0为了简化第二节中的主要算法的描述，5、我们先概括（VC）。设A是超图H的超边E的子集：是一个零矩阵，其大小在其下标中指定，IN是NN单位矩阵。在惩罚参数λ >0的情况下，我们将约束（17）提升到目标中以产生QUBOM KQ（A）= 最小值vT1<$（J + λHTH）A={Ca（m）}m=1<$E ={Cb（k）}k=1。（十四）定义0-1 ILPλv∈{0，1}N+δ′MAA（十九）I（ A）=minz∈{0，1}N阿利什卡1号体育场A z≥ 1M，（15）在精确匹配（13）之前，需要进一步的代数操作来从（19）中移除常数1;参见其中A0，1N×M是通过水平堆叠二进制N- 向量a（m）M获得的对应于A中的超边，1M是M个1的向量。通过设置A = E，我们可以从（15）式中得到（VC）。此外，由于A E，很明显I（A）I（E）.为了将公式（15）表示为QUBO，我们首先将不等式转换为等式。定义δ′=δ−1。对于（15）中的每个约束aTz≥1，我们引入δ′二元松弛秒C在supp材料的细节。在下文中，我们将讨论使用量子退火器来求解（194.3. 实际考虑和限制我们在SOTA量子退火器的背景下进行讨论-D波优势[23]。挑战问题（19）是二次罚函数法的一个应用[53，Chap.17]。当基础-变量t（m）=Σt m，1. - 是的-是的不m，δ'T进入约束当Q λ（A）等于I（A）时，存在一个总结果，它们 不变地 要求 λ 接 近一 个大 值 。 然而 ， D-WaveAdvantage的精度仅限于4-5位[22，28]，T Ta（m）z−t（m）1δ′=1;（16）回想一下，每个a（m）具有值为1的e个xmδ元素。所有的M等式约束都可以用矩阵形式表示423（一）（m）一（男）HvT1T=0，（17）其中v =πzTtT。-是的- 是的tT. -是的- 是的tT<$T∈{0，1}N+δ′M， HA =<$AT−S−1M<$∈这排除了使用大的惩罚参数。第二，尽管D-Wave优势中有>5000个量子比特允许Q矩阵不是稠密的[25，49]。给定任意Q，需要较小的嵌入步骤[9，12，62]来将QUBO映射到QPU拓扑上。嵌入消耗额外的物理量子位，减少了可用的物理量子位的数量。如SEC所述4.1、退火过程“逐渐”过渡（注意：按人类尺度，过渡是迅速的424V ← V←←∅¯←←I← V\C∥ ∥ ∥∥←V\CV ←C{I}V ← V \C⊆VV量子系统从初始哈密顿量到最终哈密顿量。目前的量子退火机无法算法1混合量子经典鲁棒拟合。注意：只有步骤8调用量子退火器。完全隔离外部噪音的过程，要求：数据D={pi}N，内点阈值，最大值影响解决方案的质量。迭代i=1¯ ¯为了得到一个有用的解，在退火过程中，系统必须有一个不可忽略的概率保持在最低能量状态。如果系统跳到更高的能量状态，它将无法最优地求解QUBO（19）M，惩罚λ与衰减参数λ，γ，M。一曰： 初始化超边集A，候选顶点′，最佳离群集zbest1N.2：对于m= 1至M，3：a（m）←Act iv esetofV′（见第二节） 5.2）。光谱间隙是最低光谱之间的最小间隙。和第二低（较高）的能量状态，这会影响4：A←A{Ca(m) {\fn方正粗倩简体\fs12\b1\bord1\shad1\3cH2F2F2F}停留在最低能量状态的概率;详见[24，31]。我们将在第二节中研究光谱间隙问题。补充材料D为什么量子退火？上述问题限制了问题的规模和利用当前量子退火机可获得的解决方案的质量。然而，量子技术正在稳步发展，愿景社区应该为潜在的突破做好准备，因为志同道合的同事也在倡导[7，8，19，34，63，65]。此外，我们的主要算法结合了量子和经典计算，以利用这两种范式的优势。5. 主要算法Alg. 1提出了我们的整体算法。在其核心，我们的算法旨在解决（VC），即，找到最小离群值集，但是通过递增地生成超边A E。该算法的其他主要特征是：• 在每次迭代时，使用量子退火来求解基于当前超边A的QUBO（19• （19）的惩罚λ按照由超参数λ<$、γ和M<$定义的时间表衰减（步骤6）。• 超边是从候选顶点集'中采样的，该候选顶点集'基于当前结果进行更新（第二节）。5.2）。该算法以最小离群点集的最佳估计zbest和采样超边A终止。在下文中，我们将展示Alg.1可以用来推导一致性最大化的误差界，以及我们的超边缘采样技术的基本原理5.1. 误差界考虑（15）不5：如果mmodM = 0，则6：λma x（λ/γ，λ<$）。7：如果结束8：v=[z t]使用量子退火求解（199： 如果f（ z）=0，则10：z（找到共识集）。11：如果z1zbest1，则<12：zbestz.13：如果结束14：'z随机子集（见第二节）5.2）。15：其他16：'z（参见第二节）5.2）。17：如果结束18：结束十九： 返回离群值集估计zbest和超边缘集A。利用这个事实|我*|= N − I（E），则有|−|我最好|≤ z best ≤ 1 − LP（A）。| ≤∥zbest∥1 −LP (A).（23）如果RHS为0，则Ibest是全局最优解。5.2. 超边采样的启发式算法回想一下，超边是不可行基。生成超边的一个简单方法是从中随机抽取δ-子集，直到我们找到一个不可行的子集，要有效率。为了提高效率，我们的采样技术保持候选顶点集V′= V，其中f（V′）=1，并取V′的活动集S[3，30]，其中g（S）=g（V′），（24）作为超边缘。直观地说，V′的活动集是一个基与V相等。 为了生成不同的超边，LP（A）=zminNz1，s.t.一z≥1M（20）采用两种策略来维持V′：[0，1]这是一个线性规划。我们一定要有那个LP（A）≤I（A）≤ I（E）。（二十一）425IV\C由于SEC的因素4.3，量子退火器在（19）上的解z可能是次优的。给定最佳解zbest，如果best=Z最佳 是一致集，根据权利要求2，zbest是（VC）的顶点覆盖。我们一定要有那个LP（A）≤I（E）≤ λzbestλ1。（二十二）• 如果它不是共识集，则取V′=V\Cz（步骤16）;• 如果找到新的共识集I=V\Cz（步骤10），则设置V′作为Cz与I的随机子集的并集（步骤14）。5.3. 超参数选择惩罚值和衰减时间表在算法中起着重要的作用。1快速找到一个共识集并收紧误差范围，请参见第2节。E在补充材料中详细说明。在我们的实验中使用和/或研究的参数的精确值将在第2.1节中提供。六、426数量的异常值i=1∈|−|≤≤≈∥ ∥∥ ∥∥ ∥∈6. 实验6.1. 合成数据我们首先通过合成数据检查D-Wave Advantage（版本1.1）[23]在我们的稳健拟合公式上的性能。我们生成2D点D={（a i，b i）}N3025201510500.10.20.30.50.80.915102050 100处罚对于一维线性回归（xR1），残差r i（x）=a i x b i，其中0a i，b i1。对于随机选择的地面真值x，一定比例的点被σ in= 0的高斯噪声破坏。1以形成内点，其余的由σ out= 1的高斯噪声产生。5模拟离群值。由于访问QPU的成本，我们在(a) 刑罚效力20151050λ（N=50 ，异常值比率=0。（二）这一小节不是从许多数据重复中得出的。然而，每个QPU输入实例都是通过10，000次退火调用的这是SEC。F在Sup。用于嵌入细节的材料（19）（例如，量子比特的数量，运行时间）到QPU上。CPU和QPU的比较我们首先在我们的QUBO（19）上比较CPU和QPU的性能（即，不依赖于Alg. 1），其中A包含所有超边E.所使用的CPU求解器是Guidelines[35]，它通过穷举搜索精确地求解（19），因此仅适用于小实例。图2绘制了由求解器优化的离群值z1（越低越好）的数量作为以下函数的曲线图：• 惩罚λ ∈ [0. 1，100]，其中N = 50，异常值比率=0。二、• 离群值比率∈ [0. 1，0。6]，其中N = 20，λ =1。0的情况。0.1 0.2 0.3 0.4 0.5 0.6异常值比率(b) 离群值比率的影响（N = 20，λ = 1。0个）40CPU30QPU2010010 20 30 40 50 60 70 80 90 100数据大小(c) 数据大小N（λ = 1. 0，离群值比率= 0。（二）图2. QUBO上CPU和QPU之间的比较（19）。50454035• N[10，100]，其中λ = 1。0，离群值比率= 0。二、3025如预期（参见第二节）。4.3），20之间的质量差距QPU解决方案和Guidelines提供的随着检查参数的增加，表明10QPU在（19）的“更简单”的实例上更可靠50N=20N=50N=100主要算法Fig. 3说明了运行Alg。 1在N = 20、50和100个点的合成1D线性回归实例上，每个点的离群值比率为0。二、使用λ = 1的QPU求解主算法中的QUBO子例程（19）。0（未进行λ衰减）。将值z1和LP（A）绘制为A的大小的函数，即，hyperedges的数量结果主要说明了量子退火方法解决鲁棒拟合问题的可行性在Alg的上下文中比较模拟退火。 1，我们比较了量子退火（QA）和模拟退火（SA）[37]（在CPU上进行10，000次退火）在求解QUBO子例程（Alg.1）。 一个合成的一维线性回归实例，N = 20，异常值比0。2已生成。 惩罚λ被设置为0。5（未进行λ衰减）。图 4显示了QA和SA在Alg迭代中的运行时。 1（对于QA，将（19）嵌入QPU的成本不包括在内;再次参见第F在Sup。用于细节的材料），以及在每次迭代中通过该方法找到的z之间的汉明距离。0 20 40 60 80 100超边数图3.通过QPU和下限LP（A）优化的离群值z 1的数量，在Alg的迭代中绘制。1.一、结果表明，SA的运行时间（在CPU上）随着采样超边数A的增加而稳定增长，而QA的运行时间在整个迭代过程中基本保持恒定，这表明QA的底层物理过程不受问题大小的显著影响（只要问题另外，Fig.4显示QA和SA获得的解决方案基本相同;这支持使用SA代替QA来检查Alg的有效性。1、大数据的真实性。6.2. 真实数据我 们 测 试 了 我 们 的 方 法 对 实 际 数 据 的 基 本 ma-kingness估计和多视图三角剖分。我们使用SA（在CPU上）代替QA来允许Alg。1、处理更大的问题。Alg的两个变种1人被处决：CPUQPUCPUQPU数量的异常值数量的异常值数量的异常值427∈∈1210864200 5 10 15 20 25 30 35 40 45 50超边数3模 拟 退火与量子退火解之间的Hamming距离预计，最快的方法是随机抽样方法。我们的方法比其他方法慢得多，主要是由于使用了SA。然而，我们的实验在SEC。6.1表明，QA可以提高SA的速度高达10倍，而不影响解决方案的质量（见图6）。4）.因此，我们期待Alg。随着量子退火能力的提高，1将更具竞争力图6定性地示出了Alg的结果。1-E。2100 5 10 15 20 25 30 35 40 45 50超边数图4.比较量子退火（在D-Wave Advantage上）和模拟退火（在经典计算机上）。• Alg. 1-E，其中一旦发现共有集，算法就终止（第10行）。• Alg. 1-F，其中运行算法直到最大迭代M（对于基本矩阵为300，对于三角测量为200我们将我们的方法与i）随机采样方法：RANSAC（RS）[32]，LO-RANSAC（LRS）[20]和固定LO-RANSAC（FLRS）[43]，ii）确定性算法：精确惩罚（EP）[41]和迭代双凸优化（IBCO）[14]以及iii）量子鲁棒拟合（QRF）[19]进行了比较。每种方法运行100次，并报告平均结果。所有实验均在2.6 GHz处理器和16 GB RAM。6.2.1基本矩阵估计我们评估了我们的方法线性化的基本的mathematics拟合[61，第4章]，其中xR8。我们使用了内点阈值θ= 0。03的代数残差（在x中是凸的，因此也是拟凸的），并且惩罚参数λ = 1。0，γ=0。5，M<$=5 0，λ<$=0。01.我们使用了来自VGG [72]（Castle，Val-bonne和Zoom）和来自KITTI里程计[33]3序列00的三个图像对（帧索引104-108、198-201和738-742）。在每一对中，使用VLFeat [1]对SIFT特征[48]进行扩展和匹配;Lowe图5示出了Alg的中间输出。1-F的Castle，KITTI198-201和KITTI 738-742，特别是解决方案的下限。参见第G在用于其他图像对的绘图的辅助材料中。表1将我们的方法与其他方法进行了比较。总的来说，我们的方法的质量与其他方法相当，Alg。1-F提供比Alg更高的质量和更紧密的结合。1-E。请注意，只有我们的方法返回错误边界（Sec. 5.1），这允许推断Alg. 1-F找到了接近最优的共识集作为3CC BY-NC-SA 3.0许可证[21].(a) 变焦(b) KITTI 104-108图6.Alg的定性结果1-E基本矩阵估计。绿线和红线表示发现的内值和离群值。6.2.2多视三角剖分使 用 了 Nikolai 的134 534 点 、 Linkop- ing 的 114 点 和Tower的3132点[29在该任务中，使用离群值下的重投影误差（拟凸[38]）估计这些3D点（xR3重新定义了内点阈值和惩罚，λ=1像素，λ=5。衰变参数为γ=0。5，M<$=5 0，λ<$=0。03.图7显示了Alg的中间输出1-F打开Nikolai点134，Linkoping点1和Tower点132，特别是解的下界。参见第在补充材料中对G点进行绘图。有趣的是，结果表明，在这里找到一个紧的下界更困难（特别是尼古拉点134和林雪平点1）。这可能是由于在求解准凸残差的极大极小问题（3）时的数值不准确性[3，30]，这影响了超边缘采样的有效性。表2显示了定量结果;可以得出与表1特别是，注意，只有我们的方法能够提供误差界;在塔点132的情况下，全局解是通过算法可证明找到的（间隙为零）。7. 弱点和结论有两个主要的缺点：第一，Alg。1在实际的量子计算机上仅针对小规模合成数据进行了验证（原因见第2节）。4.3）。为了充分发挥该算法的潜力，需要在量子计算机上使用真实数据进行测试。其次，我们的研究结果表明，超边缘采样过程也是至关重要的算法。1.一、开发一种更有效的超边采样方法是一个有趣的研究方向。模拟退火量子退火运行时时间（s）汉明距离42835城堡3025201510500 50 100 150 200 250 300超边数35KITTI 198-2013025201510500 50 100 150 200 250 300超边数35KITTI 738-7423025201510500 50 100 150 200 250 300超边数图5.基本矩阵估计，其中离群值的数量为1，下限为LP（A），在Alg的迭代中绘制1-F。方法RS [32]LRS [20]FLRS [43]欧洲议会[41]IBCO [14]QRF [19]Alg. 1-EAlg. 1-F城堡N=84|（误差界限）|(Error bound)时间（s）74（−）0.2074（−）0.1174（−）0.2070（−）0.2576（−）0.3473（−）199.4872（8.17）18.0776（1.41）1998.87ValbonneN=45|（误差界限）|(Error bound)时间（s）34（−）0.2136（−）0.2036（−）0.3133（−）0.3438（−）0.4429（−）110.3036（6.00）6.71三十六（四点）1915.82变焦N=108|（误差界限）|(Error bound)时间（s）90（−）0.3191（−）0.2991（−）0.1492（−）0.2195（−）0.3589（−）257.03九十三（9.91）92.3594（3.64）2109.13KITTI 104-108N=337|（误差界限）|(Error bound)时间（s）309（−）0.04313（−）0.04312（−）0.07318（−）0.28321（−）0.39256（−）799.33320（9.91）137.26324（2.30）2408.04KITTI 198-201N=322|（误差界限）|(Error bound)时间（s）306（−）0.05308（−）0.13307（−）0.07308（−）0.23312（−）0.42309（−）774.06308（10.00）36.15312（1.89）2350.39KITTI 738-742N=501|（误差界限）|(Error bound)时间（s）481（−）0.05483（−）0.18483（−）0.23491（−）0.53492（−）0.61447（−）1160.12492（5.88）22.46493（1.39）2506.04表1.基本矩阵估计结果。Alg. 1采用模拟退火（量子退火可以快10倍）。只有Alg。在这里比较的所有方法中，有1个返回了错误界限。20尼古拉点1341510500 50 100 150 200超边数30Linkoping点125201510500 50 100 150 200超边数30塔点13225201510500 50 100 150 200超边数图7.多视图三角剖分，其中离群值的数量为1，下限LP（A）在Alg的迭代中绘制。1-F。方法RS [32]LRS [20]FLRS [43]欧洲议会[41]IBCO [14]QRF [19]Alg. 1-EAlg. 1-F尼古拉点134N=24|（误差界限）|(Error bound)时间（s）21（−）0.2421（−）0.3221（−）0.3021（−）0.3421（−）0.3621（−）158.3921（1.00）6.1221（0.00）159.28尼古拉点534N=20|（误差界限）|(Error bound)时间（s）16（−）0.2716（−）0.3516（−）0.2515（−）0.2917（−）0.3217（−）154.6316（2.00）8.7116（1.00）147.14Linkoping点1N=25|（误差界限）|(Error bound)时间（s）15（−）0.2515（−）0.3015（−）0.3414（−）0.3816（−）0.4714（−）175.83十三（5.75）20.05十三（5.75）153.79Linkoping点14N=52|（误差界限）|(Error bound)时间（s）36（−）0.2736（−）0.4436（−）0.3835（−）0.5337（−）0.6432（−）360.37三十七（4.67）130.10三十七（四点二十七）194.46塔点3N=79|（误差界限）|(Error bound)时间（s）73（−）0.2873（−）0.6473（−）0.3273（−）0.3673（−）0.4373（−）555.2772（3.00）27.2672（1.00）177.43塔点132N=85|（误差界限）|(Error bound)时间（s）79（−）0.3079（−）0.6279（−）0.4279（−）0.5181（−）0.5181（−）563.4379（2.75）26.3381（0.00）163.32表2.多视图三角剖分结果。Alg. 1采用模拟退火（量子退火可以快10倍）。只有Alg。在这里比较的所有方法中，有1个返回了错数量的异常值数量的异常值429误界限。结论我们的工作说明了量子退火在稳健拟合中的潜力。它在鲁棒拟合方面优于（在模拟中）唯一的其他量子方法[19]，并提供了一个误差范围，以减轻当前QPU的弱点。我们希望我们的工作有助于推动量子计算机在鲁棒性方面的进一步发展拟合和计算机视觉应用。确认这 项 工 作 得 到 了 澳 大 利 亚 研 究 中 心 ARC DP200101675和D.苏特承认澳大利亚研究理事会拨款DP200103448下的资金。430引用[1] VLFeat. 网址：http：//www.vlfeat.org/访问时间：2021-11-02。[2] Sameer Agarwal ， Jongwoo Lim ， Lihi Zelnik-Manor ，Pietro Perona，David Kriegman，and Serge Belongie.比成对聚类更好。IEEE计算机协会计算机视觉和模式识别会议，2005年。[3] 尼娜·阿门塔，马歇尔·伯恩，大卫·埃普斯坦。网格平滑的最佳点放置算法杂志，1999年。[4] Pasquale Antonante，Vasileios Tzoumas，Heng Yang，and Luca Carlone. Outlier-Robust Estimation：Hardness，Minimally-Tuned Algorithms ， and Applications. IEEETrans- actions on Robotics，2021。[5] Daniel Barath和Jiˇr´ı Matas。图形切割ransac。在IEEE计算机视觉和模式识别会议上，2018年。[6] Daniel Barath、Jana Noskova、Maksym Ivashechkin和JiriMatas。Magsac++，快速、可靠、准确的稳健估计器。在IEEE/CVF计算机视觉和模式识别集，2020年。[7] Marcel Seelbach Benkner、Vladislav Golyanik、ChristianTheobalt和Michael Moeller。具有置换矩阵约束的绝热量子图匹配。在2020年国际3D视觉会议上[8] Tolga Birdal，Vladislav Golyanik，Christian Theobalt，and Leonidas J Guibas.量子置换同步。在IEEE/CVF计算机视觉和模式识别会议论文集，2021。[9] 托马斯·布斯比安德鲁·D·金艾丹·罗伊嵌合量子比特连通图中的快速量子信息处理，2016年。[10] Eric Brachmann、Alexander Krull、Sebastian Nowozin、Jamie Shotton、Frank Michel、Stefan Gumhold和CarstenR