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

计算机视觉

量子计算

153 浏览量更新于2025-01-16 收藏 1.17MB PDF 举报

417

我

|−

我

稳健拟合的量子-经典混合算法

Anh-Dzung Doan

Michele Sasdelli

David Suter

Tat-Jun

Chin

南澳大利亚阿德莱德大学计算机科学学院

西澳大利亚

Edith Cowan

大学理学院

AI ML

中心

摘要

将几何模型拟合到异常值污染的数据上可证明是棘

手的。许多计算机视觉系统依赖于随机采样启发式算

法来解决鲁棒拟合，其不提供最优性保证和误差界。

因此，至关重要的是开发新的方法，可以弥合昂贵的

精确解决方案和无法提供质量保证的快速制造之间的

差距。本文提出了一种稳健拟合的量子

经典混合算

法。我们的核心贡献是一个新的鲁棒拟合公式，解决

了一系列的整数规划和终止的全局解或误差界。组合

子问题可以用量子退火器处理，这有助于有效地收紧

边界。虽然我们使用量子计算并没有克服鲁棒拟合的

基本困难，但通过提供误差界限，我们的算法是对随

机化算法的实际改进。此外，我们的工作代表了量子

计算在计算机视觉中的具体应用。我们提出了使用实

际量子计算机（

D-Wave Advantage

）和通过模拟

获得

的结果。

介绍

计算机视觉中传感和处理的不完善不可避免地会产

生包含离群值的数据。因此，视觉管道必须对离群值

具有鲁棒性，以减轻其有害影响。

在3D视觉中，主要目标是恢复场景结构和相机运

动，基本任务是将几何模型拟合到有噪声和离群值倾

向的测量上。这通常通过共识最大化来

框架

[18]

：给定

个

数据点D

}

和

其中

（x）

是点

相对于

. r.t.

，

并且

是给定的内

点阈值。

（x）

的形式取决于具体的几何模型（更

多细节见第

节）。（

）第三章。一个可达解（

，

x）由一个共识集和它的

“

见证

”

（估计）

组成问题

（

）寻求最大共识集

，

其见证人

是

模型

的稳健估计。许多计算机视觉系

统采用随机采样，

应用化学，即，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]也

目标几何模型参数化

排除了具有误差界的有效近似解

x∈R，设P

为

索引集{1

，

. -

是的

是的，

}。我们的目标是解决

部分受到深度学习在计算机视觉中的主导地位的鼓

舞，基于学习的鲁棒几何

Max

I∈

，

∈

我

（一）

已开发[10，60，70]。这种技术利用大型数据集中的

统计数据来从

S.T. r

（x）≤

∈

，

这也取决于使用正确的

工具

。大量的作品，

源代码：https://github.com/dadung/HQC-robust-fitting

应用共识最大化建议通常不需要考虑

设置阈值

。

我

418

|−

我

≤

≥

C ≤

C c

输入实例到所需的解决方案。尽管在基准数据集上显

示出有希望的结果，但学习方法并不提供最优性保证

和误差界。学习模型是否可以推广也是一个问题。总

而言之，现有的鲁棒拟合算法，特别是那些以共识最

大化为目标的算法，还没有令人满意地解决这个问

题。因此值得

研究基于新见解的新方法

我们提出了一种新的方法，

利用量子计算实现共识

最

大化。

我们的核心贡献是一个共识最大化算法，迭

代地解决了一系列整数规划

，并终止于

或一个次优

解

，

具有已知的误差

界

。整数程序是服从量子退火

[64

，章

.8]

，这是用来收紧绑定有效。由于我们的

方

法采用凸子程序和随机采样，因此

它是一种

混合量子

经典

算法

[11

，

56]

。

我们将使用实际的量子计算机D-Wave Advantage

[23]以及模拟来展示结果。虽然我们的技术还没有超

过最先进的算法，部分原因是由于当前量子技术的限

制，但我们的工作代表了量子计算在计算机视觉中的

具体应用。我们希望在社区中推动未来在这一主题上

的努力。

相关工作

节中1，我们提供了鲁棒拟合的概述

然后在D-Wave Advantage上进行了验证

与我们最接近的工作是[19]，他提出了一个稳健拟

合的量子解决方案。然而，存在重要的差异：首先，

[19]估计

每点影响

（离群度的度量）[66，67]用于离群

值去除而不是共识最大化。其次，他们的算法基于门

计算模型，这与我们工作中采用的量子退火方法有第

三，[19]中的结果仅基于模拟;我们将在第二节中在此

基础上与[19六、

重新定义共识最大化

在这一节中，我们描述了我们的新的共识最大化和

相关的理论结果的重新制定，be-forth使用的量子退火

在SEC。4和SEC中的整体算法。五、

3.1.

预赛

在[19]之后，我们考虑准凸的残差

（

），其封装

了计算机视觉中的许多几何兴趣模型[38]。形式上，

如果集合

{

∈

（x）

≤

}

（

）

是凸的，则

（x）是拟凸的.请注意，假设拟凸残差不

会降低共识最大化的计算难度[16]。

对于

C ∈

，定义极大极小问题

和最新的算法进展因此，我们将调查重点放在计算机

视觉中的量子计算上。

（）=最

小值

∈R

max

（x）

（

三）

∈C

许多量子方法已经被提出用于图像处理[15，27，

71，74]，图像识别[26，50，51]和物体检测[45]。此

外，有几种方法探索了分类和训练深度神经网络的任

务[39，52，63]。最近，Golyanik和Theobalt [34]提出

了一种实用的量子算法，用于旋转估计以对齐两个点

集。他们的基本想法是

对于拟凸

（x），（3）是一个拟凸规划[3，30]，它

是多项式时间可解的.

请

注意，g（）

意味着这是一个共识集，因为所有的点

都在误差

范围内，

达到（3）的极值。

定义

如果

（

）

≤

;

旋转矩阵将问题公式化为二次无约束二元优化

（QUBO），可以是

（

）

（

四

）

否则

。

量子退火器解决的问题Benkner等人。[7]提出通过将二

次分配问题（QAP）公式化到QUBO us来解决图匹配

问题。

任何这样的

（）

0意味着这是一个共识

集。因此，问题（

）可以重新表述为：

惩罚的方式。他们进行了实验并对量子计算机D-Wave

进行了分析

Max

I∈P

，

s.t.|

, s.t.

（

）

，

（

）

2000Q。然而，量子计算机的局限性使它们无法解决

大问题。为了解决这个问题，Q-Match [65]不是对QAP

实施惩罚，而是提出迭代选择和解决QAP的子问题，

这使得D-Wave退火机能够有效地处理大型问题。另一

个有趣的工作是泉-

420

一

、

我

（

）

|B O|≥ B

定义

（真内值和真离群值）

。

设

为最大共识

集，

，

. -

是的

是的，

}

。我们

称

为

“

真内点

”

，

为

“

真离群点

”

。

性质1（单调性）。

对于

（3）

的拟凸剩余

，给定子

集

，

∈

，

且

P <$Q <$R

，有

（P）≤

（

）

≤

（

）

通过推广，我们也有

（

）

≤

（Q）≤

（R）

。更多细节见

，

30]

直观地说，向可行子集添加点只能潜在地使其不可

行;相反的情况不可能成立。

权利要求2.

子集是一致集当

且仅当

它是超图

的独立集。

证据

参见第B补充材料。

权利要求2证明了寻找最大共识集

这

等价于找到H的最大独立集。由于一个独立集的补

集是一个顶点覆盖，所以它证明了最小化顶点覆盖是

min

这就引出了以下关键概念。

定义

（依据）

。

基

B ∈ {1

，

. -

是的

是的，

}

是

子集

{

，

}

S.T.

z≥ 1

，

. -

是

的

是的，

，

（VC

）

使得对于每个

′，

（B

′

）

（B）≠ B

。

直觉上，从基中移除任何点都会导致子集的极大极

小值缩小。

性质2（组合维数）。

极大

极小问题

（

）的组合维数

是基的大小的上界

，

30]

。对于拟凸

（

）

，

权利要求

如果基础是不可行的，即，

（）

，则

，即，不可行基包含至少一个真离群

值。

证据

参见第补充材料中的A

3.2.

超图顶点覆盖

定义二进制N向量

[

，

. -

是的

是的，

] ∈

{

，

}

，

（

）

其中对应于非零z

的索引集合

∈

，

. -

是的

是的，

}

= 1}

。

（

八）

离群值最小化问题（6）可以重新表示为

这是一个0-1整数线性规划（ILP）。设置

1意味着移

除第i个顶点，并且约束确保所有超边都被每个超边中

的至少一个顶点权利要求1）。

超图的形式主义已被应用于几何拟合[2，46，47，

58]。然而，目标问题-

[2，46，47，58]中的LEM是高阶聚类（例如，通过超

图切割），这与我们的目标非常不同。

由于两个原因，配方（VC

•

超图的顶点覆盖是一个棘手的问题;

•

H中的超边数是指数的。然而，形式（VC）是服从

量子退火，因为我们将显示在节。4.第一章去处理那

些-

peredges，我们提出了一种混合量子经典算法，

节中5，增量生成超边。

量子解

我们首先提供一个基本的介绍量子退火，然后描述

我们的量子处理（VC）。

4.1.

量子退火

一量子退火炉解决优化问题

min

∈{

，

}

阿

利什

卡

号

体育

场

（

{

，

. -

是的

是的，

}

| C

（

）

，

（

）

通过物理系统的能量最小化。

哈密顿

量

定义了量子系统的能量分布

其中

1意味着第

个点作为离群值被移除

令b

（

）

是

对应于问题的所有不可行基的

个

二进制

向量

，即，对于每个

，

（

）

，

（

）

≤

，

（

）

其中后者诉诸于组合维度（性质

）。此外，不可

行基的数量

（

）。定义具有顶点集

的超图

，

剩余15页未读，继续阅读

cpongm

粉丝: 6

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

最新资源

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

MATLAB下的微电网两阶段鲁棒优化经济调度：基于CCG算法与混合整数线性规划求解,MATLAB下的微电网两阶段鲁棒优化经济调度策略：基于CCG算法与混合整数线性规划求解,MATLAB代码：微电网两阶

基于阿基米德优化算法的智能路径规划系统：鲁棒性强、简单易实现且适应性广泛,基于阿基米德优化算法的路径规划算（可自定义路径）-具有以下优点： 1.鲁棒性强：阿基米德优化算法不依赖于初始解的质量，具有

基于人工蜂群算法的智能路径规划系统：全局搜索、鲁棒性强、灵活多用的路径规划解决方案,路径规划算法：基于人工蜂群算法的路径规划算法:支持地图任意创建保存，起始地点任意更改 基于人工蜂群算法的路径规划算

高斯牛顿算法结合什么算法来提高算法的鲁棒性和收敛速度

基于量子力学的水印算法有哪些

在构建网络入侵检测系统时，FAST-ABQGSA-SVM算法是如何整合特征选择和参数优化来提高SVM的学习精度和鲁棒性的？

分布鲁棒模型中，约束含有混合整数规划如何处理

在Origin 7.5中进行非线性拟合时，如何根据数据特点和拟合目标选择使用Levenberg-Marquardt算法或Simplex算法？请结合两种算法的原理和应用实例进行说明。

matlab 遗传算法做公式拟合

TD3-PSO 混合算法

最新资源

基于人工蜂群算法的智能路径规划系统：全局搜索、鲁棒性强、灵活多用的路径规划解决方案,路径规划算法：基于人工蜂群算法的路径规划算法:支持地图任意创建保存，起始地点任意更改基于人工蜂群算法的路径规划算