没有合适的资源?快使用搜索试试~ 我知道了~
图匹配中的离群点问题及其解决方法
1具有离群点王福东1,薛楠1,余金刚2,夏桂松11中国武汉大学{fudong-wang,xuenan,guisong.xia}@ whu.edu.cn2华南理工大学,中国jingangyu@scut.edu.cn摘要图匹配是计算机视觉和模式识别中的一个长期问题,在实际应用中仍然存在大量杂乱的离群点。为了解决这个问题,我们提出了零分配约束(ZAC)接近图匹配问题中存在的离群值。其基本思想是通过将零值向量分配给所获得的最佳对应矩阵中的潜在离群点来抑制离群点的匹配本文对这一问题进行了详尽的理论分析,即:带ZAC的GM模型,并指出有野值的GM问题与无野值的GM问题有本质的区别,从而为构造有效合理的目标函数提供了一个充分条件。因此,我们设计了一个有效的离群鲁棒算法,以显着减少由大量离群值引起的不正确或冗余匹配。大量的实验表明,我们的方法可以实现国家的最先进的性能方面的准确性和效率,特别是在存在大量的离群值。1. 介绍在计算机视觉和模式识别的许多实际应用中,表示为图形的感兴趣的特征集通常与许多离群值[3,42,38,30]混杂在一起,这通常会降低GM的准确性。虽然最近的GM [7,11,21,22,34,44]的工作可以达到满意的结果,简单的图,只包括内点或少数离群点,他们仍然缺乏能力,容忍大量的离群点出现在复杂的图。根据经验,一个图中的内点是在另一个图中具有高度相似的对应节点的节点,而离群点则不是。基于经验准则,上述方法希望正确匹配内点和内点,并迫使离群点只匹配离群点。然而,由于com-*通讯作者10.80.60.40.20(a) 左:异常值导致的不正确/冗余匹配(红色线条)。右:生成(黄色)与理想(红色)对应矩阵。10.80.60.40.20(b) 左:我们的图匹配结果。右:我们的对应矩阵与零分配约束的离群值。图1:在存在异常值的情况下用于图匹配的ZAC。为了抑制(a)中离群点的不期望匹配,我们在(b)中的最优对应矩阵中为潜在的离群点分配零值向量,在此基础上,我们既可以为离群点图匹配建立理论基础,又可以提出一种离群点识别方法,在实际应用中可以显著减少离群点导致的不正确或冗余匹配。内点和外点之间复杂的相互关系,它们通常导致内点之间的不正确匹配或外点之间的冗余匹配(例如,图1(a))。在本文中,我们通过引入离群值的零分配约束来应对这一挑战:与以往的方法希望只匹配离群值不同,它更合理地抑制了离群值的匹配。同样,我们尝试为每个潜在的离群值分配一个零值向量(即,异常值的零分配约束)在我们的目标函数的解中(例如,图中的对应矩阵。(b)款。为了使我们的想法更加合理和实用,我们从两个方面进行了努力。首先,基于零分配约束,建立了内点和野点的定义及其定量可拓性等理论基础,并在此基础上,提出了一种基于零分配约束的内点和野点的定量可拓性方法。30333034一一充分条件,使得所提出的目标函数只能在理想匹配处达到其最小值。此外,它还有助于证明GM与不含大量异常值的GM之间的内在差异。其次,我们提出了一个有效的GM算法,包括快速优化和显式离群点识别。该优化算法是在Frank-Wolfe方法[18]的基础上结合k-基数线性分配问题[10]改进的,具有较低的空间和时间复杂度。然后,利用目标函数最优解中的零分配向量,以联合概率对两个图中的节点进行分配,该联合概率衡量节点是内点还是离群点,有助于在实际应用中识别和剔除潜在的离群点。我们的主要贡献总结如下:- 基于零分配约束建立了带野值GM问题的理论基础,并对野值和内值进行了定量分析,在此基础上从理论上提出了构造有效合理目标函数的充分条件。- 通过避免使用代价高昂的仿射矩阵和设计快速优化算法,提出了一种空间复杂度和时间复杂度都较结合我们的离群值识别方法,我们可以实现最先进的性能复杂,改进亲和矩阵K(在等式(1)中)。(1)基于从真实数据学习的先验。提出了一个函数表示框架[34],为一般和欧几里得GM提供几何见解开创性的工作[39,35]为GM提供了一个端到端的深度学习框架。本文的工作旨在为带野值的GM模型建立数学基础,增强其理论合理性。计算效率。一些现有的工作旨在减少昂贵的空间复杂性所造成的K方程。(一). 一个典型的工作是因式分解图匹配-ing [44],将K分解为几个较小矩阵的Kronecker积。然而,由于优化过程中的冗长迭代,它在实践中非常一些方法如分级分配法[13]和整数投影定点算法[24]提出了特定的快速近似,但最终得到了不满意的匹配结果。作为比较,我们的方法具有较低的空间和时间复杂度,并实现了更好的时间消耗和匹配精度之间的权衡。3. 离群点图匹配本节回顾了GM模型的一般公式,并给出了带异常值GM模型的理论基础。3.1. 图匹配的一般公式给定两个属性图G={V,E},G′={V′,E′},其中V={V}m和V′={V′}n表示节点有许多异常值的封闭图。ii=1a a=12. 相关工作已知GM问题是NP完全的[12,16,20],只能用近似解在多项式时间内求解在过去的几十年里,无数的文献被广泛研究(调查见[9,37]),我们讨论了最相关的作品在以下几个方面。对离群值的稳健性。对偶分解方法[31]在目标函数中为不匹配的特征构造了一个惩罚势。基于最大池的方法[8]是为了避免离群点误匹配的不利影响而提出的[34]中提出的基于域自适应的离群值去除策略旨在去除离群值作为预处理步骤。但是,它们直接依赖于孤立点的经验准则,不能处理复杂的情况。集合(假设m≤n),E V × V和E ′ V ′× V ′表示边集。通常,对于每个图,例如,G的边用一个(加权)邻接矩阵E∈Rm×m 表 示 ,其中如果有边(Vi,Vj),则Eij> 0,否则Eij= 0. 在实际应用中,图G通常与节点Vi的节点属性Vi∈ Rdv和边E ij的边属性Aij∈ Rde相关联,图G ′也是如此.求解GM问题是寻找一个最优二元对应P∈ {0,1}m×n,其中当节点Vi∈ V和V′∈ V′匹配Pia=1,否则Pia=0. 为了找到这样的最佳对应,GM方法通常最小化或最大化测量图之间的相互(不)相似性的目标函数。作 为 一 个 典 型 的 二 次 分 配 问 题( QuadraticAssignmentProblem , QAP ) , Lawler 的QAP [ 20,23,24,7,44 ]所描述的GMcated情况. 在我们的工作中,我们都解释了理论上的ΣmaxPTKP =P KΣ+P KP、(1)分析异常值,并提出一个有效的异常值识别,化的方法,通过它我们可以更好地实现P∈Pvv我这个ia亚,亚ia(i,j),(a,b)免疫抑制剂 JB在复杂应用中的匹配精度。图形匹配的可解释性。基于概率的工作[41,11]从最大似然估计的角度制定GM.随机游走观点[7]是通过对GM模型中的跳重加权来模拟随机游走而引入的.一些基于机器学习的作品[6,25]进一步调整图的属性,其中 Pv 是P 的列向量化副本。 亲和度矩阵K ∈Rmn×mn具有对角元素Kia; ia和非对角元素K i a ; j b,对角元素Kia ;ia测量用节点属性(vi,v′)计算的节点亲和度,非对角元素Kia;jb测量用边属性(Aij,Bab)计算的边亲和度。另一个著名的公式是Koopmans-Beckmann3035一P ∈{0,1}m×nTT一测量节点和边相似性的函数maxtr(UTP)+λ tr(EPE′PT),P∈P(二)给定τ,G与G′之间的匹配(或对应)可以等价地表示为与τ相容的部分置换矩阵P∈ {0,1}m×n其中{Uia}∈Rm×n度量Vi和V ′之间的节点相似性,λ ≥0是一个权值.一般来说,GM方法采用一对(最多)一约束,即,可行域P可以定义为:定义3.3. 对于P ∈ {0,1}m×n与τ相容,-内点的一对一约束 :Pi,a=τ(i)=1,Pi,a=/ τ(i)=0,a∈BI.(十)、、、P,P ∈ {0,1}m×n;P1=1,PT1≤1、(3)- 离群值的零分配约束其中1是列方向单位向量。事实上,Eq。(3)意味着内点和外点都被同等对待以找到它们的对应。一些方法如[6,31]将P1=1替换为P1≤1,以放松一对(至多)一的约束。然而,他们仍然缺乏内在的理论分析,在这两个图表中出现的众多离群值。3.2. 离群值的零分配约束如前所述,在SEC。1,我们的目标是只匹配内点到内点,并抑制离群点的匹配。为了实现我们的目标,我们在本节中提出了离群值的零分配将G′和G中的内点个数记为k(0k≤m≤n),为了更好地理解,下面我们先介绍一些基本的定义<定义3.1. 表示A={1,2,...,m}作为图G中节点的指数集。G的内点和离群点的指标集分别定义为,AI,{i ∈ {1,2,.,m}; Vi是G}的内围点,(4)P1,:α0T,α1∈A0和P1,α0,α1∈B0. (十一)其中,Pi:(或Pi,a)是P的行(或列)向量,并且0是一个列零向量。通过这种方式,可行域Pk可以重新定义为:.ΣP1≤1,P1≤1,1 P1=k . (十二)显式方程约束1TP1=k将用于证明我们在第二节中提出的目标函数的合理性。3.4节中设计了一个有效的优化算法。4.1.3.3. 一致性和可互换性在经验上,GM方法假设内点i∈AI和边(i,j)∈AI×AI的一元属性和成对属性与理想匹配a∈BI和(a,b)∈BI×BI的一元属性和成对属性一致,而离群点的一元属性和成对属性则相反。A O,{o ∈ {1,2,..., m}; Vo是G的一个离群值。(五)基于这一经验标准,我们进一步阐述了内点和可检验性的定量一致性索引集合B ={1,2,..., n},BI和BO对图G ′也有类似的定义. 很明显,我们有|A我|为|B我|= k。内点集和外点集是互补的,不相交的。内点和外点之间的关系,在此基础上可以保证我们的目标函数的合理性。将{Dia}ia表示为节点Vi∈ V和V′∈ V′之间的相异性,{Aij}ij和{Bab}ab是边属性的边(Vi,Vj)∈E和(V′,V′)∈E′. 与此同时,德-1.提案保加利亚ab注意{τ,P∈Pk}是G与AIAO=A,AIAO=,(6)BIBO= B,BIBO= B。(七)其中表示空集。接下来,我们推导出异常值的零分配约束。从数学上讲,G和G′con之间的匹配-G ′。因此,在经验准则之外,我们可以通过{τ,P<$∈Pk}来推导出内点的一致性和内点与外点之间的一致性。第二个提案。 内点之间的一致性- 一元一致性:i∈AI,内点和外点的存在可以由部分置换τ和部分置换矩阵P定义如下。迪亚 =min{Dia,a∈B}惠a′=τ* ㈠、(13)3036定义3.2.G和G之间的部分置换τG′定义为τ:A →B,Di′a=min{Dia,i∈A}惠i′=τ−1(a).(十四)- 成对一致性:i,j∈A,我我i<$→ a = τ(i)∈ BI,如果i ∈ AI; a = τ(i),如果i ∈ AO.(八)||Aij−Ba′b′||=min {||Aij−Bab||,a,b ∈ B}τ的倒数也可以定义为τ−1:B→A,惠a′=τ(i),b′=τ(j),(15)a<$→i=τ−1(a)∈AI,如果a∈BI;i=<$,如果a∈BO。(九)||=min {||Bab − Aij||,i,j ∈ A}||, i, j ∈ A}惠i′=τ−1(a),j′=τ−1(b)。(十六)3037AB123号提案内点和外点之间的可区分性。第四个提案。目标函数的充分条件。假设加权邻接矩阵E,E ′和- 一元可积性:<$(i,a)∈AO×B或A×边属性A、B满足BO,Ei∈A,j∈A≥ Ei∈A,j∈A,Ei∈A,j∈A,(24)I IO ODia≥max{Di′τε(i′),i′∈ AI}.(十七)- 成对可积性:<$(i,a),(j,b)∈AO×B或A ×BO,||Aij− Bab||≥ max {||Ai′j′ − Bτ(i′)τ(j′)||,i′,j′∈AI},(18)||Bab− Aij||≥ max {||Ba′b′ − Aτ−1(a′)τ −1(b′)||,a′,b′∈BI}.(十九)哪里||·||是欧几里得范数。通过这种方法,我们给出了一个定量的数学判据,该判据比经验判据更简洁明了更重要的是,上述命题启发我们如何构造合理的目标函数,并找到证明其合理性的充分条件3.4. 具有充分条件的一个合理的目标函数F(P)应满足两个主要性质:(1)保持两个图的匹配点(或边)之间的一元和成对一致性;(2)仅在理想匹配点P处达到最优。总的来说,我们的目标函数定义为minF(P)=λ1Fu(P)+λ2Fp(P),(20)P∈Pk||≥||Ai ∈ A,j ∈ AO||、||A i ∈ A O,j ∈A||、(二十五)||,(25)E′和B也是如此。那就<$P∈Pk,F(P)≥F(P<$),(26)当且仅当P=P≠ P时,方程成立。证据由于整个证明的篇幅过长,我们在补充材料中给出了详细的证明,这些补充材料也证明了简单图和复杂图上的GM之间的本质区别。注意,Eq。 (24)和(25)告诉我们如何计算正确的{Eij},{Aij}(或{E ′},{Bab}):我们应该计算Eij和Aij来度量边(i,j)中两个端点之间的相似性,使得由两个内点连接的边比由内点-外点或外点-外点连接的边具有更高的相似性。将在实验章节第2.2节中对其进行跟踪和五、4. 离群鲁棒图匹配算法在本节中,我们提出了一个有效的算法来解决方程。(20)然后设计了一种离群点识别方法。4.1. 优化算法我们的优化算法是基于Frank-Wolfe方法[18,19],该方法广泛用于凸或非凸优化,并实现至少次线性连续性。其中Fu(P)和Fp(P)是一元和两两次幂元,聚散率由于它是一个连续的线搜索为基础的方法,我们应该放松离散的Pk到连续的,tials。精确地说,我们设Fu(P)=DiaPia,ia通过将Pia∈{0,1}化为Pia∈[0,1],Giv enFp(P),Fp(P)+Fp(P)(21)F(P)是可微的,P_k是连续的,方法迭代以下步骤,直到它收敛:Σ、Eij||Aij−IJΣ甲乙丙PiaBabPjb||2P∈ (t+1)∈ar gmin,P∈F(P(t)),P∈(273038E′2EE)P∈PkΣ+ABAB||Bab− Σi、jPiaAijPjb||2(22)P(t+1)=P(t)+α(t)(P<$ (t+1)−P(t)),(28)、||A − PBPT||2个以上||B −PTAP||2′。(二十三)性质(1)是保证的,因为最小化其中<$F(P(t))是F(P)在P(t)处的梯度,α(t)是通过精确或不精确线搜索获得的步长[14]。梯度计算。梯度ΔF(P)可以是F(P)的最小值趋于找到P匹配通过如下矩阵运算有效地计算G(或G′)中的节点和边到最相容节点的G′(或G)中的边。接下来,我们应该确保它也满足性质(2)。然而,由于在两个图中出现的杂乱离群值,它可能不适用于任意给定的加权邻接矩阵E、E′或边属性A、B。并给出了一个充分条件来支持它。W1,4||PBPT− A||符号(PBPT-A)W2,4||PTAP − B||符号(PTAP − B)λF(P)=λ1D+λ2[W1PBT+APWT],(31)其中,n是逐点乘法,sign(·)是符号函数。3039PF-measure= 2。一i=1a=1一k-基数当量(27)起着优化的关键作用。这是一个线性规划(LP)问题,可以通过LP算法(如内点法[29])解决。然而,这样的方法具有昂贵的时间复杂度O(m3n3/ln(mn))[2]。幸运的是,我们可以证明P(t+1)是Pk的一个 极值点[4],因此,P(t+1)∈Pk.因此,Eq。(27)归结为k-基数线性分配问题(k)[10]。我们可以采用10.80.60.40.2010.80.60.40.200 0.2 0.4 0.6 0.81行数和[33]这是一种将知识转化为知识的方法这是一个可以用Hungarian [17]或LAPJV [15]算法有效解决的标准问题,其时间复杂度为O(n3)。正规化。有人可能会怀疑可行域中的显式方程约束1TP1=k是否太强。我们可以用隐式正则化来项(1TP1-k)2,并获得新的目标函数为minFr(P,k)= F(P)+ λ0(1TP1 − k)2.(三十二)本文设λ0=1。要求解方程 (32)、我们可以采用交替优化策略:或者找到方程的最小值P。 (32)用Frank-Wolfe方法,固定k,然后更新k=1TP1。注意,在这种情况下,Eq.用LP算法(内点法)求解方程(27在本文中),而不是k-ε求解器,因为约束1TP1=k在求解方程时不成立。(27页)。计算复杂性。因为我们不使用亲和矩阵K,所以空间复杂度仅为O(n2)。在优化问题中,每次迭代 的 时 间 复 杂 度 为 O ( n3 ) 求 解 k- 多 项 式 或 O(m3n3/ln(mn))求解线性规划,计算目标函数的值和梯度的时间复杂度为O(m2n + mn2). 我们建议采用基于kLAP的方法的基础上的实验分析,在第二节。五、4.2. Outlier identification and removal在最小化F(P)或F(P,k)之后,我们得到一个最优解。图2:异常值识别和重新识别的示例莫瓦勒图1(b). 左:最后一行和列显示了最佳对应矩阵P的列向量和行向量之和。右:内值(绿点)和离群值(红色标志)可以显著分离,并将其与分成两个班。请注意,每个图中有一个离群点聚类为内点,因为它与其他内点的相似性很高(参见图1中的匹配结果)。(b)款。节点留下较高的分量值,并将它们放回内点。若m′> k或n′> k,则分量值小于0的节点。5也将被选为离群值。我们迭代地执行这个离群点去除过程,然后细化两个图的内点,直到内点的枚举保持不变。最后求解出最优解w.r.t是我们最终的匹配结果。5. 实验分析在本节中,我们评估和比较我们的方法(表示为ZAC w.r.t.当量(20)和ZACR w.r.t当量(32))与最先进的图匹配方法,包括GA [13],RRWM [7],MPM [8],FGMD [44],BPFG [36]和FRGM [34]在匹配精度和时间消耗方面对广泛使用的复杂数据集进行了比较。比较方法的代码都 是 从 作 者 的 网 站 上 下 载 的 . 我 们 的 代 码 可 在https://github.com/wangfudong/ZAC_GM上获得。为更好地评价图匹配的存在外,一种新的异常对应矩阵P具有两个有利于异常点识别的优点:(1)P最优地保持了V我们计算了常用的指标,称为RE。电话=#{正确匹配} ,precision=#{correct matching}两个匹配图之间的结构对齐。#{groundtruth matching}#{总匹配数}(2)近零值向量Pi,:100T或P :,a200美元召回·精确召回+精确表明节点Vi∈G或V′∈ G′可以被识别为离群值,如图2所示的示例第2段(a)分段。基于此离群点识别准则,提出了一种离群点剔除方法。Giv enP,我们首先计算5.1. PASCAL数据集上的结果我们首先在PASCAL数据集[25]中的图形上进行实验,该数据集由30和20对汽车和当P1={Pi,:1}m时,且1TP={1TP:,a}n、摩托车图像(例如,图(1),分别。每一对都是其具有较小值的组件更有可能异常值然后,P1和1TP形成联合概率空间中耦合节点{(Vi,V ′)}i,a的二维坐标,其中内点和外点可以被显著地分离和聚类(例如, 通过k均值)分为两类,见图中的示例。第2段(b)分段。假设两个图的m′,n′个节点通过聚类步骤被聚类为内点,如果m′
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功