没有合适的资源?快使用搜索试试~ 我知道了~
1我基于四元数的带野值Wahba问题的可证最优解杨恒和卢卡·卡隆麻省理工学院信息决策系统{hankyang,lcarlone}@mit.edu摘要Wahba问题,也称为旋转搜索,寻求找到最佳旋转以在给定假定对应的情况下对齐两组向量观测,并且是许多计算机视觉和机器人应用中的基本例程。这项工作提出了第一个多项式时间证明最优的方法来解决Wahba问题时,大量的向量观测值是outliers。我们的第 一 个 贡 献 是 制 定 Wahba 问 题 使 用 截 断 最 小 二 乘( TLS ) 的 成 本 是 不 敏 感 的 一 个 大 部 分 的 虚 假correspondences。第二个贡献是使用单位四元数重写问题,并表明TLS成本可以被框定为二次约束二次规划(QCQP)。由于所得到的优化仍然是高度非凸的,很难解决全局,我们的第三个con-tensor是开发一个凸半定规划(SDP)松弛。我们发现,虽然天真的放松图1.我们提出了QUASAR(基于四元数的半定关系鲁棒对齐),一个可证明的最佳解决方案的Wahba问题与离群值。(a)具有四个向量观测值的Wahba问题(三个内点和一个离群点)。(b)与标准最小二乘公式相反,QUASAR使用截断最小二乘成本,将恒定成本分配给具有较大残差的测量值,因此对离群值不敏感。重建[10,19,35],和卫星姿态确定-[52,18,15],仅举几例。给定两组向量ai,bi∈R3,i = 1,. . . ,N,Wahba问题被公式化为最小二乘问题通常表现不佳,即使在存在大噪声和离群值的情况下,我们的松弛也很紧。我们验证了所提出的算法,命名为QUASAR(QUAternion-basedminR∈SO(3)ΣNi=1 w2bi-Rai2(1)鲁棒对准的半定关系),在两个同步中,它计算对齐矢量ai的最佳旋转R理论和实际数据集显示,该算法优于-和bi,其中{w2}N是(已知)相关i i=1.3×3形式RANSAC,鲁棒局部优化技术,全局离群值去除程序,和分支定界方法。QUASAR能够计算可证明的最优解(即,松弛是精确的),即使在95%的对应是异常值的情况1. 介绍Wahba问题[52,18],也称为旋转搜索[42,27,6],是计算机视觉,机器人和航空航天工程中的一个基本问题,包括在给定两个坐标系中的矢量观测值的情况下找到两个坐标系之间的旋转。该问题在点云配准[8,54]、图像拼接[6]、运动估计和3D每对测量值。 这里SO(3)={R ∈ R:RTR =RRT=I3,det(R)= 1}是含有适当三维旋转矩阵的三维特殊正交群,Id表示大小为d的单位矩阵。已知问题(1)是未知旋转的最大似然估计,当地面真实对应关系(ai,bi)已知且观测值被零均值各向同性高斯噪声破坏时[48] 。 换句 话 说 , ( 1 ) 当 观 测 值 可 以 写 为bi=Rai+Rai(i=1,. . . .,N),其中,R1是各向同性高斯噪声。此外,问题(1)可以用封闭形式解决[37,28,36,3,47,29]。不幸的是,在实际应用中,许多向量观测值可能是异常值,这通常是由于不正确的向量到向量对应关系,参见图1。图1(a).在com-1665(一)(b)第(1)款截断最小二乘最小二乘成本内点b我我异常值−c<$σ残余 c'σ1666在计算机视觉中,通过2D(例如,,SIFT [33],ORB[44])或3D(例如,,FPFH[45])功能匹配技术,这是容易产生许多离群对应。例如,当使用FPFH进行点云配准时,观察到95%的离群值并非罕见[13]。在存在离群值的情况下,标准Wahba问题(1)不再是最大似然估计量,并且所得估计量受到大误差的影响[13]。一个常见的方法来获得对离群值的鲁棒性是纳入问题(1)的求解器。 在RANSAC方案中[22]。然而,RANSAC本文的目的是设计一种方法,(i)可以全局解决Wahba问题(无需初始猜测),(ii)可以容忍大噪声(例如,噪声的幅度是测量矢量幅度的10%)和极端数 量的 异 常值 ( 例 如, 超 过95%的 观测 值 是异 常值),(iii)在多项式时间内运行,以及(iv)提供可证明的最优解。在第2节中回顾的相关文献未能同时满足这些目标,并且仅包括对中等数量的离群值具有鲁棒性或对极端数量的离群值具有鲁棒性的算法(例如,,90%),但仅提供次优解决方案(例如,,GORE [42]),或者是全局最优的,但在最坏的情况下以指数时间运行,例如分支定界(BnB)方法(例如,,[27,7])。贡献我们的第一个贡献,在第3节中介绍,是使用截 断 最 小 二 乘 ( TLS ) 成 本 重 新 制 定 Wahba 问 题(1),该成本对大部分离群值具有鲁棒性。我们将由此产生的优化问题的(离群)鲁棒Wahba问题。第二个贡献(第4节)是脱离旋转矩阵表示,并使用单位四元数重写Robust Wahba问题。此外,我们还展示了如何通过使用附加的二进制变量来重写TLS成本函数,这些变量决定了测量值是内点还是离群点。最后,我们证明了混合整数规划(包括一个四元数和N个二元变量)可以重写为涉及N+1个单位四元数的优化。这个序列的重新参数化,我们称之为二进制克隆,导致一个非凸二次约束二次规划(QCQP)。第三个贡献(第5节)是为QCQP提供一个多项式时间可证明的最优求解器。由于QCQP是高度非凸的,很难解决全球范围内,我们提出了一个半定规划(SDP)放松,是经验紧。我们表明,虽然朴素SDP松弛不紧,性能差 在实践中,所提出的方法即使在观察到95%的异常值时也保持严密。我们的方法是可证明的最佳[4],因为它提供了一种检查最佳结果的解决方案,并计算实际问题的最佳据我们所知,这是第一个多项式时间的方法,解决了强大的Wahba问题与可证明的最优性保证。我们验证了所提出的算法,名为QUASAR(基于四元数的半定关系鲁棒对齐),在合成和真实数据集的点云配准和图像拼接,表明该算法优于RANSAC,鲁棒的局部优化技术,离群去除程序,和BNB方法。2. 相关工作2.1. 无离群值的Wahba问题Wahba问题最早由Grace Wahba于1965年提出,目的是估计给定矢量观测的卫星姿态[52]。在航空航天中,矢量观测通常是由卫星上的传感器观测到的可见星 的 方 向 。 Wahba 问 题 ( 1 ) 与 众 所 周 知 的 正 交Procrustes问题[24]相关,其中搜索正交矩阵(而不是旋转)并且所有权重wi被设置为等于1。Schonemann[47]使用奇异值分解为正交Procrustes问题随后跨多个社区的研究工作导致了使用四元数[28,37]和旋转矩阵[29,36,3,23,46,31]表示的Wahba问题(1计算机视觉社区已经在点云配准[8,54]、图像拼接[6]、运动估计和3D重建[10,19]的背景下研究了Wahba问题。特别是,Horn [28]和Arun等人的封闭形式解。 [3]现在常用于点云配准技术[8]。 虽然公式(1)隐含假设零均值各向同性高斯噪声,但几位作者研究了Wahba问题(1)的广义版本,其中噪声遵循各向异性高斯[12,15,30]。Cheng和Cras-sidis [15]开发了一种局部迭代优化算法。Briales和Gonzalez-Jimenez[12]提出了一种凸松弛来计算各向异性情况的全局解。Ahmed等人。 [1]针对有界噪声和无离群值的情况开发了SDP松弛。已知所有这些方法在存在离群值的情况下表现不佳。2.2. 带离群值的Wahba问题在计算机视觉应用中,通常通过描述符匹配来建立向量到向量的对应关系,这可能会导致虚假的对应关系和离群值[42,13]。这一发现引发了对Wahba问题的异常鲁棒变体的研究。本 地 方 法 。 处 理 异 常 值 最 广 泛 使 用 的 方 法 是RANSAC,它在1667我σσ2我σ2我σσ我2i i2i低噪声和低异常值制度[22,38]。然而,RANSAC是非确定性的(不同的运行给出不同的解决方案),次优的(该解决方案可能无法捕获所有的内点测量),并且其性能在大噪声和高离群值状态下迅速恶化。其他方法诉诸M-估计,取代最小二乘成本方程。(1)具有稳健的成本函数,是一个内点,那么它必须是ai加上噪声的旋转版本,而如果bi是一个离群点,那么bi是任意的。 在所有的bi都阿吉什N(03,σ2I3),则R采用EQ的形式。(1),权重选择为测量方差的倒数,w2=1/σ2。在这我我对异常值不太敏感[9,34]。Zhou等人 [56]提出了快速全局配准(FGR),该配准采用Geman- McClure鲁棒成本函数,并使用连续方法迭代求解所得优化。由于问题在每次迭代中变得越来越非凸,因此FGR一般不保证全局最优性。事实上,正如我们在第6节中所展示的,FGR在以下情况下往往会失败:在这篇论文中,我们感兴趣的是测量值包括离群值的情况。3.1. 鲁棒Wahba问题我们引入了一种新的(离群值)鲁棒Wahba问题的公式,该公式使用了截断最小二乘(TLS)成本函数:离群值比率高于观察值的70%。全局方法。鲁棒旋转搜索的最流行的一类全局方法是基于一致性的,minR∈SO(3)ΣNi=1. 1min2我Σbi−Rai(三)sus最大化[17]和分支定界(BnB)[14]。Hartley和Kahl[27]首先提出使用BnB进行旋转搜索,Bazin等人。 [7]采用共识最大化来扩展他们的BnB算法,并具有鲁棒公式。BnB保证返回全局最优解,但在最坏情况下,它以指数时间运行。另一类全局一致最大枚举所有可能的测量值子集,其中内部的TLS成本最近已被证明对姿态图优化中的高离群值率[32]。问题(3)计算具有小残差的测量值的最小二乘解,即当1bi−我Rai2≤c<$2(或r,等式y,bi−Rai2≤σ2c<$2),同时丢弃具有较大残差的测量值(当不大于问题维度(3用于旋转搜索)1美元bi我-Rai2>c<$2第i项变为常数c<$2解析计算候选解,然后使用计算几何[41,21]验证全局最优性。这些方法仍然需要穷举。离群点去除方法.最近,Para和Chin [42]提出了一种保证离群值去除(GORE)算法,该算法在确保保留所有内点的同时去除总离群值。使用GORE作为预处理BnB的步骤被示出为提高BnB的速度,而单独使用GORE仍然提供了合理的次优解决方案。除了旋转搜索,GORE还被广泛应用于其他几何视觉问题,如三角测量[16]和配准[42,13]。然而,现有的文献仍然缺少一个多项式时间算法,可以同时容忍极端数量的离群值和返回全局最优解。并且对优化没有影响)。问题(3)实现了图1所示的TLS成本函数。第1段(b)分段。参数σi和c′2在实践中很容易设定,如下面的说明所讨论的。注1(σi和c<$2的概率选择)。假设内点遵循生成模型(2),其中σi∈ N(03,σ2I3);我们不会对离群点的生成模型做出假设,这在实践中是未知Tice。由于内点上的噪声是高斯的,因此它成立:1b−Ra2=1b2x2(3)(4)我我其中χ2(3)是具有三个自由度因此,以期望的概率p,内点的加权误差122我我3. 问题表述:鲁伯瓦赫巴. ǁǫǁ2Σ≤c<$2=p,(5)设A={a}N和B={b}N是两组三维σ2ii=1我ii=1向量(ai,bi∈R3),使得给定A,B由以下生成模型描述:.其中r ec′2是χ2分布的分位数,具有三个自由度,下尾概率等于p。因此,可以简单地将问题(3)中的σ i设置为:bi=Rai+Rai,如果bi是内点,或者bi=oi,如果bi是离群值(二)是内层噪声的标准差,并根 据 设 计 的 概 率 p 的 χ2(3)分布计算c ′ 2(例如,,p=0。第99段)。常数c′2单调递增其中R∈SO(3)是一个(未知的,待估计的)旋转矩阵,i∈R3模拟内点测量噪声,oi∈R3是一个任意向量。换句话说,如果bp = 1,则p= 1,则p = 1,则p = 1。公式(3)更倾向于接受具有大残差的测量,而小的p使得(3)更具选择性。σP1668σ2我σi=1我备注2(设置σi和c<$2的隶属度选择)。让我们假设内点遵循生成模型(2),其中问题1(基于四元数的鲁棒Wahba)。鲁棒Wahba问题(3)可以等价地写为:其中β i是给定的噪声界;这是集合成员估计[40]中假设的典型设置。在这种情况下,很容易看出内点满足:minq∈S3ΣNi=1.min1美元b我-qaiΣq−1、 (11)i.其中,我们定义ai=[aT0]T和bi=[bT0]T,并且因此,我们可以简单地选择σ2c<$2=β2,直观地,我我表示四元数乘积。我我常数σ2c′2是最小的(平方的)剩余量,或者我们愿意在第i次测量时容忍。3.2. 四元数公式我们现在采用四元数公式表示(3)。四元数是3D旋转的另一种表示[49,11],它们的使用将简化我们在第5节中的凸松弛的推导。我们首先回顾关于四元数的基本事实,然后在下面的问题1中陈述基于四元数的Ro-bust Wahba公式。单位四元数上的符号我们将单位四元数表示为单位范数列向量q=[vTs]T,其中v∈R3是四元数的向量部分,最后一个元素s是标量部分。我们还使用q=[q1q2q3q4]T来表示四元数的四个元素。每个四元数表示一个3D旋转,两 个 旋 转 qa 和 qb 的 位 置 可 以 使 用 四 元 数 乘 积qc=qa<$qb来计算:qc=qa<$qb=<$1 ( qa ) qb=<$2 ( qb ) qa ,(7)其中<$1(q)和<$2(q)定义如下:(11)和(3)之间的等价性可以很容易地从方程中理解。(十)、使用的主要优点(11)我们用一个更简单的集合,单位范数向量集合S3代替了集合SO(3)。4. 二进制克隆和QCQP本节的目标是将公式11重写为二次约束二次规划( QCQP ) 。 我们分 三 个 步 骤 : ( i ) 我 们 证 明 了(11)可以用二进制变量来写,(ii)我们证明了二进制变量可以使用N+1四元数写入,和(iii)我们操纵由此产生的问题,暴露其二次性质。QCQP的推导将为我们的凸松弛铺平道路(第5节)。从截断最小二乘到混合规划问题(11)由于成本函数和约束的非凸性(S3是非凸集)而难以全局求解。作为第一次重新参数化,我们通过以下方式暴露成本的非凸性:使用二进制变量重写TLS成本。为了实现这个目标,我们使用以下内容重写(11)中的内部年q4−q3Q2年q1年q4年q3−q2q1性质,对任何一对标量x和y都成立:1(q)=,2(q)=。(八)第3章年q4−q1q2− q 2年q1年q4第三季度−q 1−q 2−q3q4Q-q3年q4年q1q2第二次世界大战−q1年q4第三季度−q 1−q 2−q3q41+θ1−θ四元数q=[vTs]T的逆定义为:min(x,y)= minx+θ∈{+1,−1} 2y.(十二)2Σq−1=−vSΣ、(9)当量可以通过检查来验证公式(12)为真:如果xy,则右侧返回x(最小化器θ=+1),并且<其中简单地反转矢量部分的符号。向量a∈R3的旋转可以用四元数积表示.形式上,如果R是对应于单位四元数q的(唯一)旋转矩阵,则:y(极小化器θ=−1),如果x>y。 这使我们能够将问题(11)重写为混合整数程序,包括四元数q和二进制变量θ i,i = 1,. . . ,N:联系我们1+θb-qaq−11−θ罗敏iii+ic<$2。(十三)=q<$a<$$>q−1,(10)0其中a=[aT0]T是a的均匀化,通过增加一个等于零的额外条目来获得。单位四元数的集合,记为S3={q∈R4:<$q<$=1},是三维球面流形。S3是双盖q∈S322θi={±1}i=1该重构与鲁棒估计和线性过程之间的Black-Rangarajan对偶有关[9]:TLS成本是导致二进制线性过程的鲁棒函数的极端情况。直观地说,二元变量由于q和−q表示相同的旋转(intu-1),{θi}N在问题(13)中,确定给定度量-我1669Eq.(10)如果我们替换,q与−q,因为(8)中的矩阵在q中是线性的)。基于四元数的鲁棒Wahba问题 配备有了上述关系,现在很容易项i是内点(θi=+1)或离群点(θi=-1)。从混合矩阵到四元数。现在,我们将混合整数规划(13)转换为N+1四元数。直觉是,如果我们定义额外的使用单位四元数重写(3四元.qi=θiq ,我们可以将(13)重写为以下函数:1670I2Q我我NQIq和qi(i = 1,. . . ,N)。 这是获得二次成本的关键一步(命题4)。重新参数化在以下命题中形式化。二进制克隆(Binary Cloning)混合整数程序(13)等价于(在它们承认相同的最优解q的意义上)以下优化(二次等式约束是非凸的)。本文对问题(15)建立了一个凸半定规划(SDP)松弛.松弛的关键在于将问题(15)重写为以下矩阵的函数:TTqq qq1 ···qqN吴恩达−1Tˆ−12⋆q1qT···q1qTminbi−q+qqibi−qai<$qi ǁ2Z=xxT= 0。. 1.一、.N 。(十六)q∈S3i=14σi。.. ..qi={±q}1 −qTq+c'。(十四)* ···qN不.Σ2为此,我们注意到,如果我们定义Q=Ni=1 问:其涉及N +1个四元数(q和qi,i = 1,. . . ,N)。虽然在补充材料中给出了形式证明,但很容易看出,如果qi={±q},或等价于ΣNi=1xTQix=xTQx= tr . QxxT = tr(QZ)(17)alently,qi =θ iq,其中θi ∈ {±1},则qTq=θi,而xqiT=[Z]QiQi,其中[Z] QiQi表示4 ×4且q<$a<$i<$q−1=θi(q<$a<$i <$q−1),其中Z的对角块,行和列索引对应-不(13)和(14)之间的关系。我们称之为重新参数化(14)二进制克隆,因为现在我们创建了响应Qi。 由于任何形式为Z = xx的 矩 阵 都是半正定秩1矩阵,我们得到:每个测量的“克隆”q i,这样对于内点q i = q(回想一下q i = θ i q),对于离群点从Quaternions到QCQP 我们通过证明(14)实际上可以写成QCQP来结束本节。这个观察是不平凡的,因为(14)有四次成本命题5(二元克隆的矩阵公式)。问题(15)等价于(在一个问题的最优解可以映射到另一个问题的最优解的意义上)以下非凸规划:并且qi={±q}不是二次约束的形式作为QCQP的重新制定如下所示minZ≥0tr(QZ)命题4(二进制克隆作为QCQP)。 定义单个条件是tr([Z]qq)=1列向量x =[qTqT. . . qT]T堆叠所有变量[Z]qq=[Z]qq,n i= 1,. . . ,N1Ni i问题(14)然后,问题(14)等价于(在它们承认相同的最优解q的意义上)以下二次约束二次规划:rank(Z)=1(18)此时,通过丢弃rank-1约束来开发(标准)SDP松弛是直接的,minx∈R4(N+1)ΣNi=1 xTQix(十五)这是(18)中唯一的非凸性来源6号提案(Naive SDP Relaxation) 以下SDP以xTxq为条件 =1是问题(18)的凸松弛:qT T其中Qxqixqi=xqxq,i=1,. . . ,N∈R4(N+1)×4(N+1)(i=1,. . . ,N)已知minZ≥0中文(简体)我依赖于3D向量ai和bi的对称矩阵(在补充材料中给出了显式表达式),以及符号xq(分别为xqi)表示对应于q(resp.qi)。命题4的完整证明在补充材料中给出直观地说,(i)我们在代价函数(14)中推导出平方,(ii)我们利用单位四元数的性质(第3节)将表达式简化为二次代价,(iii)我们采用向量x提供的更紧凑的符号来获得(15)。5. 半定松弛问题(15)将鲁棒Wahba问题写为QCQP。问题(15)仍然是一个非凸问题X1671条件是tr([Z]qq)=1[Z] qiqi=[Z] qq,qi=1,. . . ,N下面的定理证明了朴素SDP松弛(6)在没有噪声和异常值的情况下是紧的。定 理 7 ( 无 噪 声 和 无 异 常 值 的 Wahba 中 的 紧性)。 当测量中没有噪声和异常值,并且至少有两个矢量测量(ai)彼此不平行时,SDP松弛(19)总是紧的,即:1. (19)的最优成本匹配QCQP(15)的最优成本,2. (19)的最优解Z=1,1672i=1i=1qqi联系我们。51503. Z可以写成Z=(x)(x)其中x=[(q)T(q)T. . . (q∈T)]是4个的1N原始非凸问题(15)。一个正式的证明,拉格朗日对偶理论的基础上,给出了补充材料。虽然定理7确保了朴素SDP松弛计算无噪声和无离群值问题的最优解,但我们的原始32100 0.2 0.40.60.81005000 0.2 0.4 0.6 0.8动机是解决有许多离群值的问题。人们仍然可以通过求解SDP来经验性地评估紧度,异常值比率(a) 解秩异常值比率(b) 旋转误差验证是否获得秩-1解不幸的是,朴素松弛产生的解决方案与秩大于1的离群值的存在下,参见。 图第2段(a)分段。即使当秩大于1时,也可以通过计算Z的秩-1近似来舍入解;然而,我们根据经验观察到,每当秩大于1时,舍入估计值都会出现较大的误差,如图所示。第2段(b)分段。为了解决这些问题,我们建议添加冗余约束以收紧(改善)SDP松弛,受[12,51]的启发。建议的放宽措施如下:图2.原始松弛(19)和建议松弛(20)之间增加离群值百分比的比较。(a)解的秩(秩为1时松弛是紧的);(b)旋转误差(实线:平均值;阴影区域:1-西格玛标准差)。6.1. 合成数据集的评价与朴素SDP松弛的比较。我们首先在零噪声和增加离群值率的情况下测试朴素SDP松弛(19)和QUASAR(20)的性能在每个测试中,我们对N=40个单位范数向量进行采样,紧(经验上满足定理7的三个要求)变量A={ai}N均匀随机分布。 然后我们应用即使存在噪声和95%的异常值。根据(2)的随机旋转R到A,没有附加的8号提案(SDP松弛与冗余约束)。以下SDP是(18)的凸松弛:噪声,得到B={bi}N。为了生成离群值,我们用随机单位范数向量替换一小部分bi结果是40次Monte Carlo运行的平均值图2(a)minZ≥0中文(简体)显示了朴素SDP生成的解的秩条件是tr([Z]qq)=1[Z]qiqi=[Z]qq,qi=1,. . . ,N松弛(19)和类星体(20);回想一下,当秩为1时,松弛是紧的。当没有异常值时,两个松弛都是紧的,这验证了定理7。然而,在这方面,[Z]qqi[Z]qiqj=[Z]T不qiqj,i=1,. . . ,N,n 1≤i
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 京瓷TASKalfa系列维修手册:安全与操作指南
- 小波变换在视频压缩中的应用
- Microsoft OfficeXP详解:WordXP、ExcelXP和PowerPointXP
- 雀巢在线媒介投放策划:门户网站与广告效果分析
- 用友NC-V56供应链功能升级详解(84页)
- 计算机病毒与防御策略探索
- 企业网NAT技术实践:2022年部署互联网出口策略
- 软件测试面试必备:概念、原则与常见问题解析
- 2022年Windows IIS服务器内外网配置详解与Serv-U FTP服务器安装
- 中国联通:企业级ICT转型与创新实践
- C#图形图像编程深入解析:GDI+与多媒体应用
- Xilinx AXI Interconnect v2.1用户指南
- DIY编程电缆全攻略:接口类型与自制指南
- 电脑维护与硬盘数据恢复指南
- 计算机网络技术专业剖析:人才培养与改革
- 量化多因子指数增强策略:微观视角的实证分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功