没有合适的资源?快使用搜索试试~ 我知道了~
自适应变换图匹配方法的理论和应用分析
自适应变换图匹配王福东1、薛楠1、张一鹏2、白翔3、夏桂松11国家重点实验室。LIESMARS,武汉大学,中国{fudong-wang,xuenan,guisong.xia}@ whu.edu.cn2武汉大学计算机科学学院zyp91@whu.edu.cn3中国华中科技大学EISxbai@hust.edu.cn抽象。最近,许多图匹配方法,结合成对约束,并可以制定为一个二次分配问题(QAP)已被提出。虽然这些方法展示了有前途的结果的图匹配问题,他们在空间或时间上有很高的复杂性。在本文中,我们介绍了一种自适应变换图匹配(ATGM)方法从功能表示的角度。更确切地说,在变换公式下,我们的目标是通过最小化原始图和变换后的图之间的差异来匹配两个图。通过变换的线性表示映射,图的成对边属性被显式地表示为一元节点属性,这使得我们能够显著地降低空间和时间复杂度。由于有效的基于Frank-Wolfe同时,由于变换映射可以保持图的结构,提出了一种基于域自适应的策略来去除离群点。实验结果表明,我们提出的方法优于国家的最先进的图匹配算法。关键词:图匹配·变换表示·Frank-Wolfe方法1介绍图匹配广泛用于各种计算机视觉和模式识别任务[1,9,36,31,12,29,33]中,以找到两个图结构特征集之间的对应关系。图匹配解决方案背后的一般思想是最小化由一元、成对[22,5,19]或高阶[21,35,19,37]势组成的目标函数,以保持两个图之间的结构对齐。在成对约束下,图匹配可以被公式化为二次分配问题(QAP)[27],这是NP完全的[11],并且只能在多项式时间内找到近似解。尽管过去十年在图匹配方面取得了显著进展[34,23,5,6,40],但在计算复杂性和匹配性能方面仍存在一些挑战。例如,通常需要计算或因式分解昂贵的亲和矩阵[23,22,40],这导致高空间通讯作者2F. Wang等人i=1j=1一般图匹配X1GXX2X3Y4GYY1Y3Y2(a)图X和Y(b)亲和矩阵WX1ATGMY4Y4FX1XXYY1G1XYY1X2X3X3(c)将图X变换为YX2 Y3Y2YX̅32Y2X3(d)X(e)X(f)XY图1:ATGM与一般图匹配。 两个之间的一般图匹配节点X={Xi}3的图GX且Y={Yj}4如(a)所示,通常涉及计算大小为12×12的成对亲和矩阵W,如(b)所示。相比之下,我们提出的ATGM通过最小化两个对象iv eFXY和GX<$ Y,将每个节点X i转换为映射上的最佳转换 格 式 i , 将 G X 匹 配 到 G Y,如(c)所示。 TGM通过最小化两个边属性矩阵wX和wX′之间的差异来呈现成对结构比对,具有较小的3 × 3大小,如(d)和(e)所示。ATGM还可以去除异常值,即,Y1,自然地根据G X ′和G Y之间的距离矩阵DX′ Y,如(f)所示。复杂性-特别是对于大规模的完全图。由于QAP的组合性质,难以求解目标函数以获得二进制解[23,35,20]。尽管通过松弛,离散约束可以通过更容易求解的连续约束来近似,但这种方法需要额外的努力来实现全局最优或满足二元约束[38,40,25,15]。此外,匹配大小不等的图经常会遇到离群值[6,38]。因此,降低计算复杂度并对异常值尽可能鲁棒是非常感兴趣的。本文从函数表示的角度介绍了一种图匹配的方法。主要的想法是说明了一个玩具的例子在图。1.一、在这个角度下,一个图被转换到由第二个图所跨越的空间中,然后,期望的对应关系可以被重新表述为图之间的最优转换映射。为了追求这样的映射,我们构造了两个泛函来度量图之间的差异,并使用Frank-Wolfe方法将其最小化[18]。利用变换映射,图的成对边属性可以用节点属性显式表示,从而大大降低了空间和时间复杂度。我们还提出了一个基于域自适应的策略,利用转换图可以保留图形结构的事实,以消除离群值。我们的工作在以下几个方面是突出的:- 我们提出了一个新的视角,明确表示成对的边缘属性的图匹配,使用一元节点属性的图。因此,空间复杂度从O(m2n2)降到O(mn),并且目标函数可以以O(Tn3)的时间复杂度有效地优化. 受益于这种简化,我们可以匹配大规模的图,甚至完全图。- 我们提出了一种基于域自适应的方法,使用变换映射去除离群点该技术可以用作预处理步骤以改进图匹配算法。自适应变换图匹配32相关工作在过去的几十年里,精确和不精确(容错)图匹配都得到了广泛的研究,以测量(差异)相似性[9,28,30,2]或找到图之间的对应性[13,23,5,35,40]我们专注于不精确的图匹配,以找到对应的精确图匹配和测量相似性的工作(例如。图编辑距离)超出了本文的范围。成对图匹配的许多现有工作已经解决了降低QAP公式化的高计算复杂度。在文献[38]提出的路径跟踪方法中,作者将图匹配问题改写为置换矩阵集合上的近似最小二乘问题提出了一种基于因式分解的方法[40在[39]中提出了一种有效的采样启发式算法,以避免亲和矩阵的高空间复杂性然而,[38,40]中的方法在实践中遭受巨大的时间消耗,并且降低作品[40,39]的空间复杂度的能力作为比较,我们的功能表示为基础的方法可以减少空间复杂度的两个数量级,具有较低的时间复杂度,并在实践中运行速度更快。考虑到寻找图匹配的具有二元性质的全局最优解,[38,40,25,26]中的方法构造了由连续参数控制的凸松弛和凹松弛然而,这些方法在达到理想的解决方案时通常是耗时的。此外,为了确保二元解,已经提出了求解一阶泰勒近似序列的整数投影不动点算法[23],并且[35]的作者直接在离散域中采用自适应和动态松弛机制进行优化。在我们的方法中,我们分别构造非凸和凸松弛,并获得(近)二进制解决方案,以更快的方式与高匹配精度。此外,基于亲和矩阵的秩1近似,引入了几种光谱匹配方法[22,7分级分配方法[13]迭代地解决了目标的一系列凸近似。文献[32]和[19]中基于分解的工作分别对原始复图进行分解,并对匹配约束进行分解。基于概率的[39,10]和基于学习的[3,24]方法给出了图匹配问题的进一步解释通过模拟具有重新加权跳跃的随机游动,引入了问题的随机游动视图[5]。在[6]中还提出了一种基于最大池的策略,以解决离群值的存在。这两个作品[5,6]由于它们在迭代期间的重新加权过程而对离群值都是鲁棒的。相比之下,我们提出的离群值去除策略通过显式依赖于全局结构来去除离群值。图的真实性,并且它可以作为预处理步骤应用于其他方法。3一般图匹配设无向图GX={X,EX}有m个结点Xi∈X,i=1,. . .,m,我们将每条边表示为Xii ,(Xi,Xi)∈ EX,其中EX是由1 2 1 2的M个边。匹配两个具有m,n个节点和M,N条边的图GX和GY,4F. Wang等人Pm×nT分别产生二元对应P∈ {0,1}m×n,使得当节点Xi和Yj匹配时Pij=1,否则Pij=0图匹配问题通常通过最大化一个目标函数来解决其测量GX和GY之间的节点和边亲和力。在成对约束下,目标函数通常由一元势wv(Xi,Yj)和成对势we(Xi1i2,Yj1j2)组成,其分别测量节点Xi和Yj 与边 Xi1i2 和Yj1j2 之间 的相 似性 这两 类相 似性 通常由 一个 仿射 矩阵W∈Rmn×mn来综合,其中对角元素Wij,ij对应于一元势wv(Xi,Yj),非对角元素Wi1j1,i2j2对应于成对势we(Xi1i2,Yj1j2).因此,用于图匹配的目标函数可以写为PT WPv= Σ wv(Xi,Xi)+Σ we(Xii,Yjj),(1)vPij=1Pi1j1=1Pi2j2=11 2 1 2其中Pv是P的列向量化副本。对于一对(至多)一约束下的图匹配,可行域P由所有(部分)置换矩阵(其中m ≤ n)组成,即、、、P,P ∈ {0,1}m×n;PIn=Im,PTIm ≤In、(二)其中Im是m×1单位向量。然后,图匹配问题可以通过最大化找到最优分配矩阵P*来解决。最大PTWPv.(三)P∈Pv当量(3)是所谓的(QAP),这是已知的NP-完全。通常,可以通过将离散可行域P松弛为连续可行域P来找到它的近似解:.Σ,P∈[0,1];PIn=Im,PIm≤In,(4)这被称为双随机松弛。不幸的是,(1)亲和度ma-martinW导致高的空间复杂性,特别是与完整的图,和(2)实现全球最佳或二元解决方案的(3)通常非常耗时。4自适应变换图匹配本节介绍了我们的ATGM算法,首先定义了从一个图到另一个图所跨越的空间的变换的线性表示映射。基本上,转换映射对图之间的对应关系进行建模。在此基础上,我们首先测量两个图之间的边缘差异,以获得次优的转换地图。然后,我们将转换节点的移位向量最后,我们提出了一种基于域自适应的离群点去除策略,以解决图匹配中的大小不等的情况。自适应变换图匹配51 24.1变换的线性表示给定两个无向图GX={X,EX}和GY={Y,EY},我们将图匹配作为从节点集X={Xi}m到Y={X i } m所跨越的空间的变换。{Y}ni=1jj=1。由于X,Y是离散集,我们首先定义了张成的连续空间以Y为C=Σnα Y。从X到C的变换T被定义为Yi=1J JYT:X→ CY,Xi→ T(Xi).(五)根据线性代数,T(X)可以表示为T(X),ΣnPY.iij=1国际新闻报则P∈Rm×n是一个线性表示(即,转化图)。通过约束Eq.(4)P∈P,每个节点T(Xi)都位于Y的凸x壳中。因此,我们重新定义CY作为图匹配问题的凸包Y。当P到达可行域P的极值点时,它是一个二元分配矩阵,并且因此,Xi被变换为(i. e. 其中Pij′=1,Pi,j′=j′=0。通过这种表示公式,变换后的图X¯,T(X)=PY是由指定的P和Y确定。P越是二元y,X¯就越与Y相似。因此,当我们试图最小化分歧时,我们可以用GX¯代替GY在GX和GY之间通过强迫P是二进制y。 记法X¯ii ,(X¯i,X¯i),we1 2 1 2构造函数w。r. t. P用于测量GX和GX¯之间的不一致,如F(P)= Σ fv( Xi,Yj) Pi j+Σ fe(Xii,X¯ii),(6)(i,j)(i1,i2)1 2 1 2其中,一元势fv(Xi,Yj)表示节点Xi和Yj之间的不一致Yj,成对势fe(Xii,X¯ii)表示边与边之间的离散y。1 2 1 2Xi1i2 和它的变换边X¯ii。使用这个公式,昂贵的有限矩阵将一般图匹配中的W∈Rmn×mn用th代替。e节点不同意mΣent矩阵{fv(Xi,Yj)}∈Rm×n和边离散矩阵fe(Xii,X¯ii)∈1 2 1 2Rm×m,从而将空间复杂度从O(m2n2)降低到O(mn)。为了得到给定图GX和GY的期望分配矩阵P*,我们可以:构造一个指定的泛函F(P)并最小化它,以基于优化的方式保持GX和GX¯之间的结构对齐P*∈ arg min F(P).(七)P∈P在本节的其余部分,我们引入两个泛函w.r.t. P作为我们的目标函数来建模成对图匹配问题。4.2边缘差异在图嵌入欧几里德空间Rd中的情况下,上述函数fe可以以一些简单但有效的形式6F. Wang等人定义,以包含边长(或方向),1)2)3)4)5)6)6)7)7)8)||Xi1i2||−||X¯i1i2||)2,(8)自适应变换图匹配71 2XX910910910[X,Y]:[12 8]指数:0.06422[R,G,B]:[0.1922 0.2627910[X,Y]:[12 8]指数:0.9536[R,G,B]:[0.9569 0.921612121111885544375312131415375366121314156767171716161717242524161924252416192523252318183030222220222829262721202322282920222120232226272627282926273030282911(一)(b)第(1)款(c)第(1)款(d)其他事项图2:(a)在20-vs-30中通过最小化FXY(P)进行变换后,节点移位案子 T.蓝色的liΣ是平移向量,绿色的点是平移的节点X¯iMi=1. (b)变换图(顶部)和它们的后离散化(底部)对应于(a)。(c)通过最小化GX¯Y(P)而变换的节点,几乎没有转移(d)变换图(顶部)和它们的后离散化(底部)对应于响应于(c)。在(b)和(d)中,红点标记地面实况。哪里||Xi1 i2||是Xi1 i2的l2范数。因此,我们的第一目标函数的成对势被定义为:Σ(1)xx(||Xii||−||X¯ii||)2、(9)1 2 1 2 1 2(i1,i 2)Σ2016 - 05 - 22 00:00:00(||X¯ii||2−2||Xii||||X¯ii||)+c1 2 1 2(i1i 2)1 2 1 2其中c是常数,并且Si是 10.计算(||Xii||−||X¯ii||)2如果我们1 2有前科 记S,{Sii} ∈ Rm×m。1 2 1 2FXY(P)w.r.t.P可以使用链式法则来计算FXY(P)= 2(LX+L*)(PY)YT,(10)其中,LX=diag(SIm)−S是GX的拉普拉斯算子,并且L*=diag(S*Im)−S*,其中S*,Sii||Xii||||X¯ii||-1。为了避免文献[4]中的数值不稳定性,一个小的我1我 21 2 1 2 1 2>0被添加到||X¯i1i2||−1,i. e. ,(||X¯i1i2|Σ|+)−1。当然,我们可以重建FXY(P)通过添加一元势如ijfv(Xi,Yj)Pij+λFXY(P)。由于FXY(P)的非一致性,它的极小元P*∈P,这是已知的作为从GX到GX¯的最佳变换映射,通常会达到局部最小值,并且不是二进制的;参见图2(b)以供说明。因此,变换后的节点X¯i通常不完全等于aYj′∈Y,并且X¯i和its正确匹配Yσi之间经常存在移位。图图2(a)显示了这种移位现象,其中每个X¯i从在某种程度上正确匹配Yσi4.3节点移位8F. Wang等人受益于FXY(P)的性质,该性质保持GX和GX′,相邻节点的移位向量具有相似的方向和范数,自适应变换图匹配9如图所示。第2段(a)分段。因此,为了减少从X¯i到其正确匹配Yσi的节点移位,表示为-−→X¯iYσi=Yσi−X¯i,我们最小化相邻移位向量之间的差的和,即,、ΣGX¯Y(P)=S¯i,i||(X¯i −X¯i)−(X¯i −X¯i)||2(i1i 2).1 2 1 1 2 2 2¯T¯Σ=Tr (PY−X)LX¯(PY−X)、(11)其中LX<$=diag(S<$Im)−S<$。We表示X<$=PY作为X<$的变换节点。在我们的方法中,权重矩阵S¯被设置为正对称的,因此,LX¯是正定的,GX¯Y(P)是连续的x。稀疏正则化由于GX¯Y(P)是连续的x,所以它的最小值通常是可行域P的内点而不是极值点。为了接近二进制为了解决这个问题,我们首先添加稀疏正则化项,即。e. ,P到GX¯Y(P)的l1范数. We表示Dij,d(X¯i,Yj)为X¯i和Yj之间的距离。受益于-−→FXY(P)的解,移位向量X¯iYσi的范数 相对较小,且项Di,σi比Di,jσi小得多,如图2所示1(f). 因此,我们还添加一个一元项DX¯Y={Dij}∈Rm×n,以提高极小化r的稀疏性.最后,GX¯Y(P)可以总结为G(P)=∠P,D+ λ ||P||1.−X¯)TL(PY−¯ΣX¯YX¯YΣ11+λ2树(PYX<$X),式中,P,DX<$Y=ijPijDij。则GX¯Y(P)的梯度为GX<$ Y(P)=DX<$ Y+λ1+2λ2LX<$(PY−X<$)YT。(十二)通过这种稀疏正则化,函数GX¯Y(P)可以用(几乎)二进制解来求解,这显著提高了匹配精度。见图2(c)和(d)例如。4.4通过域自适应去除离群不同大小的图GX和GY与mn的匹配比较复杂。在这种情况下,图GY中出现的离群点通常会影响匹配结果。谢谢对于由极小化FXY(P)得到的变换映射P *,GX′的结构与GX的 结 构 相 似 .在某种意义上,操作X¯=P*Y可以被视为从源域X到目标域Y的域适应[8]。我们提出了一种方法通过使用从FXY(P)和GXY(P)交替最小化的变换映射自适应地去除离群值,其中GXY(P)通过在GXY(P)的成对势中用X替换XY来定义:ΣGXY(P)=SII||(X¯i −Xi)−(X¯i-Xi)||2(十三)1 2 1 1(i1,i2)Σ10F. Wang等人2 22=Sii||(Xi−Xi)−(X¯i-X¯i)||第二条,(十四)1 2 2 1(i1,i2)2 12自适应变换图匹配11XYXY具有46个节点的图X46个内点和40个离群点迭代= 1迭代= 2迭代= 3迭代= 4图3:利用通过交替地最小化FXY(P)和GXY(P)获得的变换映射P_n来去除异常值。在每次迭代中,红色点是内点,绿色加号是移除后剩余的节点。它描述了原始图G X和变换后的图GX¯之间的边向量差。边缘的取向也已经在许多图匹配方法[19,32,40]中使用,以将亲和矩阵的非对角元素构造为:Wi1 j1,i2j2=exp∫12-2(||Xi1i2||−||yj1j2||)、2-(θii−θjj)21 21 2,(15)其中θi1i2是边Xi1i2与水平线之间的角度在最小化FXY(P)或GXY(P)之后,我们得到变换后的节点X¯=P*Y。因此,GX¯具有类似于原始图GX的结构,并且位于与GY相同的坐标系中,具有相对较小的位移。然后,我们可以移除异常值使用比率检验技术来适应。给定两个点集X¯和Y,我们计算所有对(X¯i,Yj)之间的欧氏距离dij。F或每个节点X¯i,我们找到最近的节点Yj*,并在dij>k·dij*时删除所有节点Yjk>0。 如果剩余节点的数量l小于m,则从更接近X¯的剩余节点中选择m − l个节点并添加。实验结果表明,在交替地最小化FXY(P)和GXY(P)的几次迭代之后,大多数异常值被去除(见图13)。(3)第三章。我们的带有离群点去除的ATGM算法总结在算法1中。算法1P←ATGM(X,Y,k0)输入:X、Y、k0和S、S′(如果可用)。产出:P*当k≤k0时通过等式P←argminG(16)和Eq.(17);Y←用P*去除Y的离群值;P*←argmin Fvia Eq(16)和Eq.(17);Y←用P*去除Y的离群值;K←k+ 1;end whileP*←argminF经由等式(16)和Eq.(17);X¯←P*Y;P*← argmin G¯以P*作为初始化。XYP<$←P<$的后离散化用洪阿里安的方法1XY12F. Wang等人5数值实现与分析如上所述,我们构造了两个目标函数,即非凸的FXY(P)和凸的xGX<$ Y(P)。 现有的方法,e. G. ,[38,40,25],分别将凸形式和凹形式的目标函数Jv和Jc联系起来,并求解了一系列由参数λ从0增加到1控制的组合函数Jλ=λJc+(1−λ)Jv. 相比之下,我们通过Frank-Wolfe(FW)方法[ 38,40 ]分别求解目标函数FXY(P)和GX¯Y(P),该方法简单但有效。如果g是连续x且可微函数,并且如果P是连续x集合,FW方法迭代以下步骤直到其收敛:P~ (k+1)∈argming(P(k)),P,(16)P∈PP(k+1)=P(k)+α(k)(P~ (k+1)-P(k)),(17)其中,α(k)是通过线搜索过程[14]获得的迭代k的步长,并且使用等式来计算g(10)和Eq.(十二)、由方程式(16),极小化子P~ (k+1)∈P理论上是P的极值点(因此是二进制的)。 这意味着P~ (k+1)∈P。因此,Eq。(16)是线性分配问题(LAP),其可以通过诸如匈牙利[17]、LAPJV[16]算法的方法有效地求解。更进一步地,由于P~ (k+1)在每次迭代中是二进制的,因此最终的解P在最小化GX<$ Y(P)之后是(几乎)二进制的。收敛FW方法确保至少次线性收敛速度[18],这可能导致求解非凸函数FXY(P)的大迭代。然而,在200次迭代内最小化FXY(P)是足够的,因为它的解将被应用作为最小化GX¯Y(P)的初始化,这是强收敛性x并且可以实现更强的收敛性。在我们的实验中,GX<$ Y(P)在k≤100次迭代中以10−7的容差收敛与路径跟踪方法相比解决了[38,40,25]中组合在一起的两个松弛目标函数,我们的优化策略更快,匹配精度更高。局部最优与全局最优FW方法可以保证仅获得非凸目标FXY(P)的局部最优。然而,如上所述,F XY(P)的局部最优值被应用为用于求解凸对象iveGXY(P)的初始化,这都使我们达到全局最优值。计算复杂度对于我们的方法,空间复杂度为O(mn),这是相当小的大小O(m2n2)的大多数其他方法与完全图。时间复杂度为O(Tn3),其中T是FW方法中的迭代次数 该复杂度可以计算为O(T(τf+ τl)+ τs),其中τs= O(m2)是GX的边属性矩阵的成本。 在FW方法的每次迭代中,τf= O(m2n)是计算P(k)处的梯度、函数值和步长的成本,并且τl= O(n3)是最小化等式(1)的成本。(16)使用匈牙利算法。6实验分析在本节中,我们在合成数据和真实世界数据集上评估我们的方法ATGM。我们将我们的方法与包括GA [13]的最新方法进行自适应变换图匹配130的情况。15在[22],[23],[24],[25],[26],[28],[29],作为建议在[23]中,我们使用SM的解决方案作为IPFP的初始化。此外,对于FGM,我们使用可变形图匹配方法称为FGM-D。在所有实验中,为了能够应用统一参数λ=1,λ1=103和λ2=1,我们将节点坐标归一化为[0,1]用于我们的方法。对于非凸目标函数FXY,我们通过使用Shape Context [1]来计算其一元项为了比较,报告了每个算法的平均准确度我们的目标函数与所比较的方法所使用的目标函数不同,因此,比较目标分数或目标比率没有意义6.1合成数据的结果我们在合成随机点集上对ATGM进行了比较评估,如下[40,15,5]。GX和GY的合成点构造如下:对于图GX,n个内点在R2上随机生成,且服从高斯分布N(0,1).通过对每个Xi∈X添加高斯噪声N(0,σ2)生成带噪声的图GY,以评估该方法对变形噪声的鲁棒性通过在具有高斯分布N(0,1)的R2上添加n个额外的点来生成具有离群点的图G-Y,以评估对离群点的鲁棒性对于比较的方法,如在[40]中,我们设置边缘亲和度矩阵Wi1j1,i2j2=ex p(− (||Xi1i2||−||yj1j2||)2)。设S∈Rm×m为我1我2为||X我1我2||−1for FXY (P)一个GXY(P),其中G X是全连通的。对于GX¯Y(P),我们的方法在X上执行Delaunay三角剖分以获得其边集E¯X,然后,E¯X被分成两部分,使用k-通过考虑边缘长度来表示(具有较长长度的边缘被丢弃)。内存效率如第二节中所分析。5、该方法的空间复杂度低于对比方法。在这个实验中,我们试图验证ATGM可以匹配图形与低内存消耗,同时实现更好的准确性。由于比较的方法可以实现更好的准确性与完整的图,公平起见,我们首先应用所有的方法,以完成一个相对较小的大小n=20的图。然后,我们将大小扩大到nin=100,以测试ATGM在内存效率方面的优势。由于其他方法的高空间复杂度,我们不得不将它们应用于Delaunay三角剖分的图然而,我们的方法是能够使用完全图,由于其较低的空间复杂度O(n2)。如图4(a)和(b),在完全图设置下,我们的方法实现了在具有变形噪声的情况下获得最高的平均精度,并且在具有异常值的情况下获得有对于大尺寸的图,我们的方法优于所有其他方法(如图所示)。(见第4段(c)和(d)分段)。相比之下,使用具有大量节点的完全图与其他方法在实践中是不可行的。除了PM [39],所有比较的方法都需要使用n2(nin+nout)2个内存单元,对于n_in=100,n_out≥100,这将是极大的。这一要求影响它们在实际中对图匹配的应用。运行时间为了比较所有方法的时间消耗,我们在大小相等和大小不等的情况下测试了它们,即(1)nin=10,20,...,100,n_out=0,σ= 0。2和(2)n_in= 100,n_out= 10,20,… 100,σ= 0。05. 考虑到边的数目对时间消耗的影响14F. Wang等人GAPMSMSMACIPFP-SRRWMFGM-DMPMATGM1 1 1 10.80.80.80.80.60.60.60.60.40.2n输入= 20n输出 = 0000.10.20.30.40.5形变噪声(一)0.40.2nin= 20噪声= 00048121620离群值数量(b)第(1)款0.40.2n输入= 100n输出 = 0000.040.080.120.160.2形变噪声(c)第(1)款0.40.2nin= 100噪声= 00020406080100离群值数量(d)其他事项图4:对噪声和异常值的鲁棒性的比较。对于完全图,关于噪声和异常值的数量的准确度分别在(a)和(b)中由Delaunay三角剖分连接的图的结果在(c)和(d)中示出。完全图和Delaunay三角连通图。在不等长的情况下,我们将我们的方法应用到完全图和其他Delaunay三角连接图,使ATGM比其他人采取更多的边缘。如图5(a)和(b),其中图是完整的或通过Delaunay三角剖分连接,我们的方法需要中等的运行时间,并达到最高的平均精度。如图如图5(c)所示,即使ATGM比其他方法处理与运行速度较快的GA、SM、PM、SMAC和IPFP-S相比,ATGM可以获得更高的平均精度。对于完全图的匹配,RRWM、FGM、MPM等方法然而,他们的时间消耗迅速增加,变得比我们更大。表1:在具有变化的内点ηin、变形噪声σ和异常点ηout的合成数据上的ATGM的平均准确度和运行时间。#内部噪声(σ)0.020.040.060.080.10100时间0.220.510.740.781.01acc.(%)99.1094.1589.7584.273.9300时间3.345.436.727.738.02acc.(%)96.8788.3374.3760.1351.33500时间23.3332.4733.1233.8135.24acc.(%)94.2079.9662.3248.5438.721000时间147.15 150.92 156.71 156.99 159.26#Inlier #Outlier0.20.40.60.81.0100时间1.903.113.814.625.51acc.(%)99.9099.8099.9099.8099.60300时间17.0222.7042.9247.7055.13acc.(%)100.00 99.8099.6799.7099.53500时间107.24 123.42 146.99 187.84 185.54acc.(%)99.8699.8899.6498.2481.301000时间563.83 645.11 758.73 882.18 1070.26大规模图匹配。为了测试我们的方法在应用于大规模图时的效率,我们通过将内点的数量设置为nin=100,300,500,1000以及变形噪声和离群点来进行更具挑战性的实验异常值的数量设置为20%、40%、…… 100%的内围值。如表1所示1、ATGM对异常值具有很强的鲁棒性,但对强噪声的鲁棒性较差精度精度精度精度自适应变换图匹配15在更大的图表。由于比较的方法需要存储的亲和矩阵的大小约为n2(n在+n出)2,将这些方法应用到大规模的图与数百或数千个节点是不可行的。16F. Wang等人时间(log10)时间(log10)GAPMSMSMACIPFP-SRRWMFGM-DMPMATGM10.8n个 = 0噪声= 0.210.8n个 = 0噪声= 0.210.8n=100 噪声= 0.050.60.60.60.40.40.40.20.20.2010 20 40 60 80100#Inlier010 20 40 60 80100#Inlier010 20 40 60 80 100离群值数量5n个3= 0 噪声= 0.25n个3= 0 噪声= 0.24n=100 噪声= 0.05321 1 10 00- 一个-1-310 20 40 60 80100#Inlier(一)-310 20 40 60 80100#Inlier(b)第(1)款-210 20 40 60 80 100离群值数量(c)第(1)款图5:运行时间和平均精度的比较(a)中的图是完全图,(b)中的图是Delaunay三角连通图。在(c)中,只有ATGM使用完全图,而其他的使用Delaunay三角连通图。6.2真实数据集的结果我们还对真实世界的数据集进行了比较评估,包括CMU House序列4和PASCAL汽车和摩托车对[24],它们通常用于评估图匹配算法。4748 49 78 79 8091042 435608517175767769 70747384 858635 36282734299 104420 2219242355 56 5758 596012481133428211835 411517169113635 36282734 293245333230463153761213513 14 2733454630313937616281828338401914152022 1924 236 71728 216364 6566 6711371815394019101211414211612131624242313 14 2761582173026512342538141423 438252 535417137234328252518 1921202322282926202272425 263710293830453931464032473372416 32523444514 1523911 84226274476171819202122262712 25266514 152021221628291073041617 18192126(a)20 vs 30(ATGM:20/20)(b)28对48(ATGM:28/28)(c)46对86(ATGM:44/46)图6:在真实世界数据集上使用ATGM匹配大小不等的图的示例红点是GX中的内点,黄色加号是GY中的内点和外点。绿色的线是正确的匹配,而红色的线是不正确的。CMU房屋序列由合成房屋的111个帧组成每个图像包含30个特征点,这些特征点用已知的对应关系手动标记。在该实验中,我们匹配了由10、20、…90帧。不相等大小的情况被设置为20-vs-30和25-vs-30。对于比较的方法,我们设置对W的边亲和i1j 1,i 2j2精度时间(log10)精度精度自适应变换图匹配172500(||Xii|| −||Yjj||)2个=exp (−1 21 2)与[40]相同。4http://vasc.ri.cmu.edu//idb/html/motion/house/index.html18F. Wang等人Σ(Pij≥r)GAPMSMSMACIPFP-SRRWMFGM-DMPMATGM10.80.60.40.2010 30 50 7090#分离(a) 庄家:30比3010.80.60.40.2010 30 50 7090#分离(b) 庄家:25比3010.80.60.40.2010 30 50 70 90#分离(c) 庄家:20比30图7:在大小相等和大小不等的情况下,House序列的平均准确度的比较。GA下午SMSMACIPFP-SRRWMFGM-DMPMATGM10.80.60.40.200 5 10 15 20离群值数量10.80.60.40.200 5 10 15 20离群值数量图图8:汽车(左)和摩托车(右)图像对与离群值的比较用于图匹配的PASCAL数据集由30对汽车图像和20对摩托车图像组成。每一对包含具有地面实况标签的内点(大约30-60个特征点)和随机标记的离群点。在不等长匹配的情况下,我们在G-Y上分别添加了5、10、15、20个异常值.对于比较的方法,我们将边缘亲和度矩阵设置为Eq. [15][16][17][18][19][19][19][19]平均精度对于CMU House序列,如图所示。7,我们的方法在等尺寸和不等尺寸的情况下都达到了更高的精度。同时,我们的方法优于所有比较的方法在PASCAL数据集上,因为我们的方法可以自动删除离群值。结果示于图8.目标函数的影响正如我们在第二节中所讨论的那样。4、对象iv e函数GX<$ Y对稀疏性和匹配精度都有影响首先,评估的稀疏性我P∈[0,1]m×n,我们定义一个指数S(P)=i,其中I是指示函数。Rm第我们在r = 0的House序列上计算Sr(P). 9 .第九条。如Tab.所示。2,GX¯Y的最优表示映射P* 在所有情况下都是(几乎)二进制的。然后,我们评估了两种情况下的平均精度:(1)仅最小化FXY和(2)应用-ingGX¯YafterFXYisminimized. 如Ta b所示。2.由于G X <$Y的存在,平均精度得到了很大提高,特别是在尺寸不等的情况下。结果表明,GX<$ Y能提高分配矩阵的稀疏性,减少节点移动.最后,我们提出的离群点去除策略并不局限于我们的方法。它可以应用于任何其他方法。评价精度精度精度精度精度自适应变换图匹配19表2:目标函数FXY和GX Y对分配矩阵P*的稀疏性和房屋序列数据集的平均匹配精度的影响。大小#分离10 20 30 40 50 60 70 80 90m=20n=30稀疏性98.18 97.98 97.59 96.11 95.15 89.63 90.79 79.58 80.90acc. (F)acc. (FG)59.60 58.89 57.78 56.18 55.38 54.05 53.52 51.9098.2597.8696.8493.9792.1188.3785.6679.37 77.67m=25n=30稀疏性99.72 99.42 98.35 98.42 96.63 92.43acc. (F)acc. (FG)81.25 80.24 78.15 76.56 75.80 74.93 73.25 71.05 68.9299.9299.7199.4298.6697.7096.0594.6391.63 89.08m=30n=30稀疏性100.00 100.00 100.00 100.00 100.00acc. (F)acc. (FG)100.00 100.00 100.00 100.00 100.00 99.68100.00 100.00 100.00 100.00 100.00表3:离群值去除策略的有效性。该策略使几乎所有方法的平均匹配精度提高了10%数据 Out.Re. 中文(简体)[39]第三十九话SM [22] SMAC [7] IPFP-S [23] RRWM [5] FGM-D [40] MPM [6] ATGM汽车W/Ow/34.5061.9337.0460.7138.0463.5538.5349.5426.7465.5553.8470.3749.0570.6258.0263.44-71.83电机W/Ow/45.9766.5343.5661.9147.1367.4343.8452.0634.9075.8065.6472.6167.3176.7665.7369.46-74.75我们的离群值去除策略的一般性,我们将其应用为预处理步骤,然后使用预处理的输入执行其他方法。如Tab.所示。3、所有方法的平均准确率都有很大的提高,几乎所有方法的性能都提高了10%以上。7结论本文从函数表示的角度出发,通过将分配矩阵重新定义为线性表示映射,提出了一种新的图匹配方法。我们的方法大大降低了空间和时间复杂度。因此,我们的方法是适合于匹配完全图与数百和数千个节点。除了变
下载后可阅读完整内容,剩余1页未读,立即下载
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)