< br/>通
(1.西北大学信息科学与技术学院,陕西 西安 710127; 2.巢湖学院信息工程学院,安徽 巢湖 238000; 3.巢湖学院网络与分布式系统研究所,安徽 巢湖 238000)
(1.School of Information Science and Technology,Northwest University,Xi'an 710127,China; 2.School of Information Engineering,Chaohu University,Chaohu 238000,China; 3.Institute of Networks and Distributed Systems,Chaohu University,Chaohu 238000,China)
bounded distortion mapping; triangular mesh; plural; Jacobian matrix; image matching
DOI: 10.6043/j.issn.0438-0479.2018015
备注
< br/>通
针对受损文物图像这一特殊数据源,提出一种结合不变尺度特征变换(SIFT)和保扭曲映射的图像匹配(SBD)方法.该方法基于SIFT特征建立特征三角网格映射,对网格映射添加保扭曲约束,构建非凸的约束空间,并将属于L0范数问题的目标函数使用代理函数近似.实验结果表明SBD方法可以优化并减少错误匹配,对于解决破损文物图像匹配问题的研究具有较好效果.
An image matching method(SBD)combining scale invariant feature transform(SIFT)and bounded distortion mapping is proposed for the special data source of damaged cultural relic images.The feature triangular mesh mapping is established based on SIFT.In addition,the bounded distortion mapping constraint is added in the method,and the non-convex constraint space is constructed.Furthermore,a proxy function is used to approximate the target function,which belongs to the category of L0 norm.As a result,mismatch pairs can be optimized and reduced,as well as become effective for solving problem of damaged cultural relic images matching.
引言
图像匹配[1-2]是计算机视觉中的经典问题之一,它的目标是找到最佳的图像间的特征点对应关系.现有很多算法致力于解决这一问题,其中一类是以经典描述符为代表的方法,有不变尺度特征变换(SIFT)[3]、快速稳健特征(SURF)[4]及基于SIFT与SURF的方法.SIFT提供了图像间的多尺度匹配,使图像发生平移、缩放和旋转变化时特征保持不变,该方法对于局部的几何失真图像更具有鲁棒性.SURF为SIFT的改进方法,具有更快的匹配速度.基于以上两种经典描述符改进或融合而产生的新方法也在不断出现.陈洁等[5]在SURF描述符的基础上,使用极线约束删除误匹配,提高了匹配质量.基于SURF和快速近似最近邻搜索的图像匹配(SFANN)方法[6]融合SURF和最近邻搜索策略,采用顺序抽样一致性(PROSAC)算法对错误匹配进行滤除,解决了传统抽取匹配点偏差较大的问题,但是PROSAC模型的参数受内点数制约,缺乏稳定性.曹君宇等[7]提出SURF与随机抽样一致性的融合(SRSC)算法,由于使用随机抽样一致性算法,一定程度减少了传统近似最近邻算法呈现的误配结果.冯筠等[8]基于学习不变特征变换(LIFT)提出一种新的图像匹配方法并应用于兵马俑图像,取得了较好的图像匹配效果.此外,图像匹配方法还有基于几何拓扑[9]的方法,其依据特征点在图像上的位置信息,如基于交比[10]、特征数[11]等具有稳定几何特征的不变量及特征点形成的拓扑关系[12]进行图像匹配.贾棋等[13]利用特征点间的几何关系构造一种描述算子,通过直方图相似性度量实现图像匹配.鲍文霞等[14]利用椭圆形几何构造谱特征,最终使用贪心算法获得匹配.
不管是基于经典描述符还是基于几何拓扑关系的图像匹配方法,所检测出的特征点只是一种理想状态可识别的特征点,当受到光照、透视变化等条件影响时,易出现一幅图像中特征点不唯一匹配另一幅图像中的特征点的问题[15],导致匹配结果不是最优匹配,甚至错误匹配.如何根据图像特点,设计并进一步优化匹配模型,以适合具体应用需求仍然是图像匹配的重要研究方向.
三角网格作为图像分析的一个有力工具,近年来在数字几何设计和模型处理中发挥着重要的作用,并且在RGB图像、点云图像、CT图像等多模态图像数据处理中得到越来越广泛的应用.图像匹配的本质是获取源图像中特征点与目标图像中特征点的对应关系,由于特征点易实现三角网格化,得到图像对应的三角网格.因而,源图像网格中的每一个三角形与目标网格图像中的一个三角形实际也是存在映射关系的.
受损文物图像是对受损文物进行虚拟修复及数字化保护的重要数据源.受损文物的残缺往往由各种因素造成,使得这些文件局部或总体缺乏完整性,这种完整性的缺乏包含新的断裂面的形成纹理的缺失、对称性的破坏等,使得受损文物包含更丰富的形态信息和语义信息,这时特征的几何结构在这种情况下则成为了更加重要的信息.本研究将三角网格映射引入到受损图像匹配问题,提出一种基于SIFT和有界失真映射(SBD)的受损文物图像匹配方法,SBD方法首先使用SIFT算子获得候选匹配,形成由源图像与目标图像特征点组成的三角形之间的映射,建立几何近邻结构,然后在保扭曲映射的约束下,通过迭代对候选匹配集进一步筛选,去除那些可能错误匹配的特征点,尽可能提高匹配准确率.由于SBD方法是结合SIFT特征的一种新方法,所以本研究先将它与SIFT方法作对比,再与SFANN方法和SRSC方法对比以说明SBD方法的有效性.
1 SBD方法
由于SIFT算法提供了图像间的多尺度匹配,而且对于局部几何失真的图像具有鲁棒性,本研究首先利用SIFT方法获得候选匹配集,形成特征点三角网格之间的映射,在保扭曲映射的约束下,对候选匹配集进一步筛选,去除可能错误匹配的特征点,以提高匹配准确率.
设利用SIFT方法所获得的图像间对应的特征点为(vi,v -i),三角网格中每一个三角面片vi1vi2vi3通过映射fi被映射成v-i1v-i2v-i3(如图1),记为:
映射fi实际上是一种仿射变换,属于分片线性映射,即:
用Ji表示映射的雅可比矩阵,
对Ji进行奇异值分解(SVD),可得到两个奇异值
设σ1i≥σ2i,则σ1i与σ2i之比与三角形扭曲程度成正比,限定其取值范围可实现保扭曲约束,即
其中α为最大扭曲度.同时为了保持三角形不发生翻转,需确保映射Ji行列式值大于0,即|Ji|=aidi-bici>0.(7)
图像匹配问题就是在约束式(6)和(7)下,优化目标函数min∑ni=1ti,其中对于以筛选候选匹配集这一模型进行优化求解,需要解决两个问题,即非凸空间和目标函数为L0范数.下面分别对这两个问题进行分析并加以解决.针对约束形成的非凸空间问题,将Ji分解成1/2Ai+1/2Bi,其中,
引入一种复数表示约束式(6)和(7):
zi=(ai+di)+i(bi-ci),(11)
z'i=(ai-di)+i(bi+ci).(12)
此时,Ji的奇异值σ1i和σ2i可以用复数zi和z'i的模表示:
σ1i=|zi|+|z'i|,(13)
σ2i=||zi|-|z'i||.(14)
约束(6)和(7)可以写成:D(Ji)=(|zi|+|z'i|)/(||zi|-|z'i||)<α;(15)
|Ji|=|(zi)/2|2-|(z'i)/2|2>0.(16)
进一步,约束式(16)可以表示成:
|z'i|≤(α-1)/(α+1)|zi|.(17)
由于α>1,为了获取一个凸约束空间,按照文献[16]的方法,引用变量ci将式(18)表示为:
|z'i|≤(α-1)/(α+1)ci≤(α-1)/(α+1)|zi|.(18)
尽管|z'i|≤(α-1)/(α+1)ci是一个二次凸锥,但是约束0
i≤|zi|是非凸的,它是凸锥的补.为了寻找一个凸的子空间,Re(zi)代替ci≤|zi|,Re(zi)表示复数zi的实部,约束即 {|z'i|≤(α-1)/(α+1)ci,0
i≤Re(zi).(19) 此时,约束(20)对应的是一个凸空间.第二个需解决问题是L0范数问题,最小化L0范数问题属于非确定性多项式(NP)难问题[17],对此类问题一般采用凸松驰方法[18]或代理函数算法[19]解决.这里使用一种代理函数Eε,p(Ji)来近似表示能量,
Eε,p(Ji)=∑nj=1(‖fi(vi)-v-i‖2+τ)p/2.(20)最终将在保扭曲和无翻转约束下的非凸非连续优化问题转化成凸优化问题.对于能量函数(21),使用一种重加权迭代最小二乘(IRLS)方法[20],其中
表示迭代第k+1次能量:
其中ωi(k)表示迭代第k次后权重,且ωi(k)=(‖f(k)i(vi)-v-i‖2+τ)(p-2)/2.(22)
参数τ用来控制迭代速度,在约束空间中,通过式(21)迭代更新权值,重新计算能量式(22),获取新的变换矩阵以及特征点位置.本研究所提出SBD方法的步骤如下.输入:采集的待匹配图像对.输出:对应点映射.1)获取SIFT初始匹配; 2)获取雅可比矩阵; 3)表示约束空间; 4)当|E(k)-E(0)|<ε,令E(k)ε,p=E(0)ε,p,先用式(23)计算新的权值,再在约束(20)下优化(21),最后计算出新的特征点位置.
2 实 验
实验数据选择西北大学可视化实验室采集的相关文物图像,以兵马俑残片、残器物、破损兵马俑、陶俑残块图像为研究对象,实验平台计算机硬件CPU为Intel Xeon3.33G,内存为16 GB,实验编程软件主要使用MATLAB,优化软件工具包使用MOSEK[21].
2.1 实验结果对比为了说明SBD方法的有效性,本研究对比了SBD方法与SIFT、 SFANN、SRSC.匹配准确率的定义如下:匹配准确率=(正确匹配点对数)/(正确匹配点对数+错误匹配点对数).
为了选取合适的α值,首先分析了α与SBD方法的平均匹配准确率的关系(图2),可以看出,SBD方法扭曲度的取值对于结果的影响不大,α值为3时,SBD方法的平均匹配准确率最大,故本文中选取α值为3.
图2 SBD方法的平均匹配准确率(不同扭曲度α)
Fig.2 Average matching accuracy of SBD method(different distortion degree α)2.2 实验结果分析为进一步说明SBD方法可通过保扭曲约束筛选匹配对,提高匹配准确率.本研究给出了SBD方法与SIFT、SFANN、SRSC方法在兵马俑残片、残器物、破损兵马俑、陶俑残块的图像匹配对(如表1),并进行分析说明.
由表1和图4可知,在对兵马俑残片图像进行匹配时,虽然SIFT方法通过黑森矩阵获得比较稳定的局部极值,但它对于求取主方向要求较高,造成部分错误匹配发生在如发际线区域特征点与面颊区域特征点,或面颊区域特征点与下颚区域特征点,主方向的偏差使得匹配准确率降低.而SBD方法中通过对映射的雅可比矩阵奇异值分解得到的奇异值来对扭曲约束,这使匹配对不会出现太大偏差.
3 结 论
破损文物的特征提取及特征匹配是实现文物虚拟拼接和实现数字化保护的关键.本研究结合传统算法的优势,将三角网格映射引入图像匹配问题,提出了SBD方法.SBD方法利用三角网格确定特征点间的位置关系和结构关系,进一步减少了错误匹配,取得较高的图像匹配准确率效果.可将SBD方法应用于不同图像数据源和应用需求.当然,本方法也存在不足,由于其需要反复进行SVD运算,对硬件性能要求较高,需进一步利用GPU提高算法性能和适应性.
- [1] ORON S,DEKEL T,XUE T,et al.Best-buddies similarity:robust template matching using mutual nearest neighbors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2018,40(8):1799-1813.
- [2] HUANG Z,WEI Z,ZHANG G.RWBD:learning robust weighted binary descriptor for image matching[J].IEEE Transactions on Circuits and Systems for Video Technology,2018,28(7):1553-1564.
- [3] LOWE D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision,2004,60(2):91-110.
- [4] BAY H,ESS A,TUYTELAARS T,et al.Speeded-up robust features(SURF)[J].Computer Vision and Image Understanding,2008,110(3):346-359.
- [5] 陈洁,高志强,密保秀,等.引入极线约束的SURF特征匹配算法[J].中国图象图形学报,2016,21(8):1048-1056.
- [6] 赵璐璐,耿国华,李康,等.基于SURF和快速近似最近邻搜索的图像匹配算法[J].计算机应用研究,2013,30(3):921-923.
- [7] 曹君宇,周浩,高志山,等.基于SURF的图像拼接过程中配准算法的改进[J].云南大学学报(自然科学版),2016,38(6):845-852.
- [8] 冯筠,延瑜瑜,赵妍,等.基于学习不变特征变换的兵马俑图像分区匹配[J].光学精密工程,2018,26(7):1774-1783.
- [9] CARCASSONI M,HANCOCK E R.Spectral correspondence for point pattern matching[J].PatternRecognition,2003,36(1):193-204.
- [10] LI L,TAN C L.Recognizing planar symbols with severe perspective deformation[J].IEEE Transactions on Software Engineering,2010,32(4):755.
- [11] LUO Z X,ZHOU X C,GU D X F.From a projective invariant to some new properties of algebraic hypersurfaces[J].Science China Mathematics,2014,57(11):2273-2284.
- [12] 张勇,耿国华.基于拓扑关系和几何特征的图像匹配方法[J].北京师范大学学报(自然科学版),2018,54(2):198-202.
- [13] 贾棋,高新凯,罗钟铉,等.基于几何关系约束的特征点匹配算法[J].计算机辅助设计与图形学学报,2015,27(8):1388-1397.
- [14] 鲍文霞,余国芬,朱明,等.基于椭圆形度量谱特征的图像匹配算法[J].东南大学学报(自然科学版),2018,48(3):387-392.
- [15] ARNFRED J T,WINKLER S,SÜSSTRUNK S.Mirror match:reliable feature point matching without geometric constraints[C]∥2013 2nd IAPR Asian Conference on Pattern Recognition.Naha:IEEE,2013:256-260.
- [16] LIPMAN Y.Bounded distortion mapping spaces for triangular meshes[J].ACM Transactions on Graphics,2012,31(4):13-15.
- [17] EDOARDO A,VIGGO K.On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems[J].Theoretical Computer Science,1998,209(1/2):237-260.
- [18] HYDER M M,MAHATA K.An improved smoothed 0 approximation algorithm for sparse representation[J].IEEE Transactions on Signal Processing,2010,58(4):2194-2205.
- [19] PANT J K,LU W S,ANTONIOU A.New improved algorithms for compressive sensing based on p Norm[J].IEEE Transactions on Circuits and Systems Ⅱ:Express Briefs,2014,61(3):198-202.
- [20] CHARTRAND R,YIN W.Iteratively reweighted algorithms for compressive sensing[C]∥IEEE International Conference on Acoustics,Speech and Signal Processing.Las Vegas:IEEE,2008:3869-3872.
- [21] ANDERSEN E D,ANDERSEN K D.The mosek interior point optimizer for linear programming:an implementation of the homogeneous algorithm[M]∥High performance optimization.Boston:Springer,2000:197-232.