|
|
|
发布时间: 2016-06-25 |
图像理解和计算机视觉 |
|
|
|
宋伟东1, 朱红1, 王竞雪1, 刘玉轩2 |
收稿日期: 2015-11-07; 修回日期: 2016-01-20
基金项目: 国家自然科学基金项目(41101452);辽宁省科技厅博士启动基金项目(20141142);辽宁省教育厅科学技术研究一般项目(L2014134)
第一作者简介: 宋伟东(1965-),男,教授, 2005年于辽宁工程技术大学获大地测量学与测量工程博士学位,主要研究方向为遥感图像处理、影像匹配、3维建模等。E-mail: lntu_swd@163.com
中图法分类号: TP391
文献标识码: A
文章编号: 1006-8961(2016)06-764-07
|
摘要
目的 针对影像匹配时提取特征线断裂而影响匹配结果及可靠性的问题,提出多重约束条件下的近景影像线特征匹配方法。 方法 首先,采用SIFT算法获取同名点,并使用RANSAC算法进行优化,通过同名点计算仿射变换矩阵;建立格网点,利用仿射变换、Harris兴趣值及最小二乘法提高密集匹配结果的精度;其次,采取Freeman链码优先级算法提取直线,根据搜索区域内密集匹配点与直线位置关系完成特征线的初始匹配;最后通过线段重合度对初始匹配结果进行优化,并利用核线约束确定同名直线端点。 结果 选取存在旋转、尺度、遮挡的近景影像进行线特征匹配实验,结果表明,与其他直线匹配方法相比,本文方法不仅在直线匹配成功数目上约为经典算法的1.07~4.1倍,而且直线匹配正确率也提升0.6%~53.3%,具有较好的准确性和鲁棒性。 结论 通过多重约束有效地减小了立体影像中线特征匹配时的搜索范围,提高了直线匹配速率,且该方法适用于不同类型几何变化下的近景影像数据,并能较好地改善直线断裂及遮挡问题。
关键词
近景影像, 直线匹配, Freeman链码, 多重约束, 密集匹配
Song Weidong1, Zhu Hong1, Wang Jingxue1, Liu Yuxuan2 Abstract
Objective Given that the fracture situation affects the results and reliability of straight line matching, a new line matching method for close-range images under multi-conditions is proposed. Method First, the initial corresponding points are obtained using the scale-invariant feature transform algorithm and are optimized by random sample consensus. The affine transform matrix is computed based on the final corresponding points. The dense matching accuracy is improved through affine transform, Harris interest value, and least square method based on the constructed points. Second, the lines are extracted using the Freeman chain code priority algorithm, and the initial matching results are obtained based on the position relationship between the dense matching points and the lines in the searching area. Third, the initial corresponding lines are optimized by the line coincidence degree, and the endpoints of the extracted lines are determined under epipolar constraint. Results A set of close-range images that contain rotation, scale change, and occlusion are used in line extraction experiments. The experiment results show that, compared with other line matching methods, the proposed method successfully matches 1.07 to 4.1 times more lines and improves the accuracy of straight line matching by 0.6% to 53.3%. The proposed method also outperforms the existing methods in terms of accuracy and robustness. Conclusion By setting multi-conditions, the searching area of line features is effectively decreased in stereo image matching, thereby significantly improving the matching efficiency. Experiments are performed on close-range images under different geometric transformations. The proposed method can be used to solve line break and occlusion problems.
Key words
close-range image, line matching, Freeman chain code, multiple constraints, dense matching
0 引 言
直线匹配是计算机视觉、特征识别、图像配准等领域的关键技术和经典问题，也是3维重建亟待解决的问题[1]。虽然特征点匹配已取得较大进展，但是直线匹配由于噪声、光照、遮挡等因素影响，却进展相对较慢。其难点主要体现在以下3个方面[2-4]：1)直线段端点不确定性，极线虽然能较好约束点匹配，但在直线匹配中却不能提供准确位置约束；2)直线提取中出现断裂情况导致匹配结果中易出现“一配多”、“多配一”情况；3)没有预知全局的几何约束条件，由于直线长短决定直线支撑域大小，因此对区域描述子来说，缺少一个归一化策略的全局约束条件。
现有大量直线匹配算法大致可分为3类：1)基于直线本身几何属性[5-7](长度、方向、重叠度等)，该类算法缺乏有效几何约束，算法复杂度大，匹配成功率偏低；2)基于直线邻域灰度信息[8-9]，在立体像对上比较一定尺寸窗口内匹配基元灰度相似度信息，该类算法对存在亮度变化的影像效果不够理想；3)基于几何约束直线匹配[10-12]，多借助单应矩阵、三焦张量等几何约束，但是不适用于视差变化较大的近景影像。通过对现有直线匹配方法总结与分析，针对近景影像直线特征匹配缺乏强有效的约束问题，提出多重约束条件下的近景影像线特征匹配方法。
1 原 理
通过SIFT (scale invariant feature transform)算子[13-15]匹配近景影像中同名点，利用RANSAC (random sample consensus)算法[16]优化匹配结果，依据最佳匹配结果，计算立体像对间仿射变换矩阵[17]。为了获取合适数量且分布均匀的密集特征点，将参考影像划分成等间距格网，以格网点为待匹配基元，通过格网大小控制特征点的密集覆盖程度。利用仿射变换计算出搜索影像中相应的格网点位置，由于格网点大致坐标已确定，所以特征点匹配过程中无需设置较大的搜索窗口，可以通过计算窗口内Harris兴趣值，将兴趣值最大的点作为匹配点，最终采用最小二乘法[18]对密集匹配结果进一步提纯。采用Freeman链码优先级直线提取算法[19-20]分别提取参考影像和搜索影像中直线，根据密集匹配点与直线位置关系筛选同名直线，不仅简化了搜索同名直线的复杂程度，而且有效地减小立体影像线特征在匹配过程中的搜索范围，提高直线匹配速率；通过重合度约束对匹配结果进一步优化，剔除“一配多”、“多配一”等情况，提升直线匹配结果精度且原理简单，同时利用核线约束确定同名直线端点，得到了尽可能长的同名直线段，改善了特征线提取过程中所出现的断裂情况。
1.1 密集匹配点约束
因为近景影像中存在较多的建筑物，而使得提取的直线结果中存在较多垂直线，所以将直线方程两点式转换为一般式，避免对斜率是否存在进行讨论，提高运行速度。依据密集匹配点与待匹配直线位置关系，确定初始匹配结果。密集匹配点与待匹配直线应满足：1)如果密集匹配点到直线距离d≤1(像素)，视为特征点位于直线上；2)构建自适应搜索窗口，以线段长l定义搜索窗口的长，以二分之一线段长定义搜索窗口宽，若密集匹配点位于窗口内，视为特征点存在于直线周围，此时同名点与候选直线的位置关系也应保持顺序一致。
由于提取特征线过程中会出现直线断裂的情况，从而导致匹配结果中可能会存在“一配多”、“多配一”现象，因此根据线段有向距离，判断线段是否共线，若共线且间距较小，则连接两线段首尾端点。同时计算更新后直线与原直线间的夹角，若夹角过大，则不予以更新，避免因异面直线存在而导致更新结果中出现“假共线”的现象。
1.2 重合度约束
为提高直线匹配精度，通过仿射变换将参考影像中初始匹配结果映射到搜索影像上，仿射变换后两匹配线段应基本平行。但为突出两线段重合区域间的距离变化，以初始匹配直线的交点为原点，以两直线所交锐角的角平分线为x轴，如图 1所示，x1,x2分别为待匹配直线段重合区域对应的起点和终点。图 1中下图为一种极端情况，此时两线段与x轴夹角为45°，线段l所在的直线函数斜率为1，由此可以推出，基于密集匹配约束的待匹配直线段所在的直线函数斜率不可能大于1。
理论上待匹配直线应完全重合，然而实际匹配过程中，大多数待匹配直线并不在同一条直线上，而是存在一定的距离和角度，假设s代表待匹配直线重合区域内任意位置处的距离，x代表待匹配直线重合区域x方向坐标，即
| $s = {y_1} + \frac{{\left( {x - {x_1}} \right)\left( {{y_1} - {y_2}} \right)}}{{\left( {{x_1} - {x_2}} \right)}}$ | (1) |
重合度函数为
| $f\left( s \right) = \left\{ {\begin{array}{*{20}{c}} 0&{s > 0}\\ 1&{s = 0} \end{array}} \right.$ | (2) |
因此，待匹配直线段重合长度为
| $O\left( {l,l'} \right) = \int_{{x_1}}^{{x_2}} {f\left( {s\left( x \right)} \right){\rm{d}}x} $ | (3) |
即在定义域内对重合度函数式(2)求定积分的结果就是待匹配直线段重合区域的长度。然而实际匹配时，大多数待匹配直线并不在同一条直线上，而是存在一定的距离和角度，公式中的s即为较小的一个的数值，为避免s值较小而导致式(3)失效，因此将模糊数学中隶属度概念引入，定义直线重合度函数为
| $f\left( s \right) = \max \left( {1 - \frac{s}{{dis}},0} \right)$ | (4) |
最终线段重合长度为
| $O\left( {l,l'} \right) = \int_{{x_1}}^{{x_2}} {f\left( s \right){\rm{d}}x} $ | (5) |
将式(1)代入式(4)，再将式(4)代入式(5)得到重合度判别公式为
| $O\left( {l,l'} \right) = \int_{{x_1}}^{{x_2}} {\max \left( {1 - \frac{{{y_1} + \frac{{\left( {x - {x_1}} \right)\left( {{y_1} - {y_2}} \right)}}{{\left( {{x_1} - {x_2}} \right)}}}}{{dis}},0} \right)} {\rm{d}}x$ | (6) |
式中，dis表示待匹配直线段重合区域起点所对应距离的阈值，设置该阈值为待匹配直线段重合区域起点距离的1.5倍。利用重合度判别式(6)，计算每对初匹配直线重合度O(l,l′)，直线重合度阈值th为待匹配直线段重合长度的下限，当重合长度O(l,l′)≥th时，则记录直线匹配结果。参数th设定为待匹配线段最小重合长度的二分之一。重合度随着参数dis的增大而线性减小，匹配精度随着参数th的减小而逐渐降低。
1.3 核线约束直线同名端点
因为通过直线提取算法分别对参考影像和搜索影像进行特征线提取，所以上述直线匹配的结果同名直线段长度基本不同，利用核线约束确定同名直线端点，其原理如图 2所示。
假设线段L1、R1为同名直线段，参考影像中L1端点分别为A、B，搜索影像中R1端点分别为C、D。HA、HB为点A、B在搜索影像中相对应的核线，与线段R1交于A′和B′，比较A′、B′、C、D每两点间距离，将距离最大的两点作为线段端点坐标，搜索影像亦同理。因为受拍摄角度不同影像中可能会有遮挡情况存在，由于遮挡未被完整提取的直线段也得到延长，通过判断延长线段端点窗口灰度相似性来避免类似错误的情况出现。在保证同名直线尽可能长的同时，需考虑延长后线段端点是否超越影像范围，若因遮挡导致同名端点不在影像范围内，此时以直线与影像边界交点更新端点坐标，以保证同名线段端点存在的真实性。
2 实验结果及分析
为验证所提出直线匹配方法的有效性和可靠性，选用中国科学院自动化研究所机器视觉课题组公开的3组不同类型近景影像数据，分别为存在旋转变换(640×460像素)、尺度变换(800×600像素)以及存在遮挡(640×460像素)的立体像对完成直线匹配实验。
利用密集匹配特征点约束直线匹配，减小直线匹配过程中的搜索范围。通过格网间距(sub)控制匹配特征点数量，格网间距参数sub越小，匹配点数目越多，同时匹配直线对数也就越多，但当sub减小到一定程度时，虽然密集匹配特征点数目还在增加，但匹配直线的对数将保持不变，即通过密集匹配结果约束直线匹配已到达最优化状态，同时表明该格网间距对直线匹配结果具有较好的鲁棒性，如图 3所示。因此实验过程中设置格网间距大小为sub=5，在该格网间距下密集匹配点数目能够提高到原SIFT匹配结果的1017倍，此外，在重合度约束直线匹配的过程中参数设置为dis=2,th=380。
1)旋转变换。用本文方法处理存在旋转变换的立体像对，最终成功匹配直线170对，由于直线提取算法导致匹配结果直线段长度不一致，如图 4(a)右图像中12号直线(红圈内)，局部放大图如图 4(b)，通过核线约束最终获取长度较长的直线匹配结果见图 4(c)，局部放大图如图 4(d)。从图 4中可以看出，本文核线约束同名直线端点不同于传统核线约束只获取同名直线重叠部分，而是获取尽可能长的同名直线。
2)尺度变换。利用本文方法处理存在尺度变换的立体像对，影像数据存在大约为1.5倍的缩放尺度，实验结果表明，即使直线段端点不同，利用多重约束成功匹配直线58对，说明本文方法对于端点位置不确定的线段仍然可以实现成功匹配。再利用核线约束同名直线端点，结果如图 5所示。
3)遮挡。受拍摄角度影响，搜索影像中房屋边缘被部分遮挡，遮挡影像势必存在影像不连续性问题，造成直线特征提取不完整，以至于对应直线段端点不对应。如何解决影像中存在遮挡的问题，目前在直线匹配领域具有一定的挑战。通过实验结果可以看出，成功匹配直线55对，类似于图 6(a)中53号直线(黄框内)所存在的遮挡情况，本文方法仍然可以成功匹配，因为本文方法不依赖于直线端点。但图 6(a)中44号直线(红框内)，图 6(b)中为对应位置的局部放大显示，图 6(b)中44号直线(右图红圈内)匹配出现错误，原因是近景影像中存在夹角较小且比较靠近两直线，两条直线相似且近似平行，在这种情况下影响了直线匹配精度，后续将对此类情况进行更深入的研究。从成功匹配直线对数来看，本文方法对于直线端点不确定性问题具有一定的鲁棒性，可以成功解决部分遮挡问题。
对数据库中经典算法的直线匹配结果进行比较与分析。表 1列出了3种不同类型近景影像数据的直线匹配总对数、正确匹配直线对数以及匹配的正确率。文献[7]单纯利用直线描述算子完成直线匹配，由于缺乏严格的几何约束，导致匹配结果不够稳定，这种不稳定性对于尺度变换的影像显得尤为明显。文献[9]在文献[7]的基础上，通过局部仿射不变性及核线约束来匹配直线，虽然采取核线约束提高了直线匹配对数，但由于需要首先利用直线特征与邻域内以同名点为端点的虚拟直线段的相交仿射不变性进行同名直线的筛选，相对于本文采用密集匹配约束筛选同名直线就显得过于复杂和繁琐。
表 1
两种方法匹配结果对比分析
Table 1
Comparative analysis of matching results by two methods
从表 1可以看出，本文方法实验结果不仅在成功匹配直线对数上有所增加，而且直线匹配正确率也明显提升。通过对实验结果对比分析，本文方法在大大缩减直线匹配过程中搜索范围的同时，采取核线约束获取尽可能长的同名直线，从而改善特征线在提取过程中所出现的断裂情况。多种类型近景影像数据实验表明，匹配结果均具有较高正确率和良好稳定性，说明本文方法具有鲁棒性和普适性。
3 结 论
直线匹配目前是3维重建中热点和难点问题，通过对现有方法分析和总结，提出多重约束下的近景影像线特征匹配方法。利用密集匹配特征点约束直线匹配，同时对格网间距变化进行鲁棒性检测，选取最佳格网间距完成线特征初始匹配。密集匹配点约束有效地缩减了近景影像在直线匹配过程中线特征的搜索范围，进而提升了直线匹配速率。并利用重合度约束对初始匹配结果进行一致性检核，使得直线匹配精度得到提升。再通过核线约束同名直线端点，不同于传统的核线约束单纯地保留同名直线间的重叠部分，而是获得尽可能更长的同名直线段，有效地改善了特征线提取过程中所出现的断裂情况。而且对于存在遮挡的影像也取得较好的匹配结果，成功解决了部分遮挡问题。实验结果表明，通过本文所提出的直线匹配方法，对于不同类型的近景影均表现出较好的鲁棒性和普适性，但本文初步对候选直线的筛选依赖于特征点密集匹配的结果，后续将进一研究组直线匹配，提高直线匹配的独立性。
参考文献
-
[1] Tang F, Lim S H, Chang N L, et al. A novel feature descriptor invariant to complex brightness changes[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Miami, FL: IEEE, 2009: 2631-2638. [DOI: 10.1109/CVPR.2009.5206550]
-
[2] Hu H X, Li G. Line matching based on binary relations of geometric attributes[J]. Journal of Image and Graphics, 2014 ,19 (9) : 1338 –1348. [ 胡海霞, 李钢. 几何特性二元关系的直线匹配[J]. 中国图象图形学报, 2014 ,19 (9) : 1338 –1348.] [DOI:10.11834/jig.20140911]
-
[3] Zhao Q Q. Line matching method based on a new geometric invariant: CHR-IMP method[D]. Dalian: Dalian University of Technology, 2013. [赵倩倩. 基于一种新的几何不变量的直线匹配方法: CHR-IMP法[D]. 大连: 大连理工大学, 2013.]
-
[4] Wang J X, Song W D, Han D, et al. Feature line matching algorithm for aerial image based on continuity constraint of edge parallax[J]. Journal of Signal Processing, 2015 ,31 (3) : 364 –371. [ 王竞雪, 宋伟东, 韩丹, 等. 边缘视差连续性约束的航空影像特征线匹配算法[J]. 信号处理, 2015 ,31 (3) : 364 –371.] [DOI:10.3969/j.issn.1003-0530.2015.03.015]
-
[5] Fu D, Wang C, Xu Y D, et al. A new algorism of matching line segments[J]. Journal of National University of Defense Technology, 2008 ,30 (1) : 115 –119. [ 傅丹, 王超, 徐一丹, 等. 一种直线段匹配的新方法[J]. 国防科技大学学报, 2008 ,30 (1) : 115 –119.] [DOI:10.3969/j.issn.1001-2486.2008.01.024]
-
[6] Shao Z F, Chen M. Line-based matching for high-resolution images with robustness for scale, rotation andillumination[J]. Optics and Precision Engineering, 2013 ,21 (3) : 790 –798. [ 邵振峰, 陈敏. 尺度、旋转以及亮度稳健的高分辨率影像直线特征匹配[J]. 光学精密工程, 2013 ,21 (3) : 790 –798.] [DOI:10.3788/ope.20132103.0790]
-
[7] Wang Z H, Wu F C, Hu Z Y. MSLD: A robust descriptor for line matching[J]. Pattern Recognition, 2009 ,42 (5) : 941 –953. [DOI:10.1016/j.patcog.2008.08.035]
-
[8] Wang Z H, Wu F C. Mean-standard deviation descriptor and line matching[J]. Pattern Recognition and Artificial Intelligence, 2009 ,22 (1) : 32 –39. [ 王志衡, 吴福朝. 均值-标准差描述子与直线匹配[J]. 模式识别与人工智能, 2009 ,22 (1) : 32 –39.] [DOI:10.3969/j.issn.1003-6059.2009.01.006]
-
[9] Liang Y, Sheng Y H, Zhang K, et al. Linear feature matching method based on local affine invariant andepipolar constraint for close-range images[J]. Geomatics and Information Science of Wuhan University, 2014 ,39 (2) : 229 –233. [ 梁艳, 盛业华, 张卡, 等. 利用局部仿射不变及核线约束的近景影像直线特征匹配[J]. 武汉大学学报: 信息科学版, 2014 ,39 (2) : 229 –233.] [DOI:10.13203/j.whugis20120611]
-
[10] Zhang Y S, Zhu Q, Wu B, et al. A hierarchical stereo line matching method based on a triangle constraint[J]. Geomatics and Information Science of Wuhan University, 2013 ,38 (5) : 522 –527. [ 张云生, 朱庆, 吴波, 等. 一种基于三角网约束的立体影像线特征多级匹配方法[J]. 武汉大学学报: 信息科学版, 2013 ,38 (5) : 522 –527.]
-
[11] Schmid C, Zisserman A. The geometry and matching of lines and curves over multiple views[J]. International Journal of Computer Vision, 2000 ,40 (3) : 199 –233. [DOI:10.1023/A:1008135310502]
-
[12] Li F F, Jia Y H, Xiao B L, et al. A multi-sensor image registration algorithm based on line features and SIFT points[J]. Geomatics and Information Science of Wuhan University, 2010 ,35 (2) : 233 –236. [ 李芳芳, 贾永红, 肖本林, 等. 利用线特征和SIFT点特征进行多源遥感影像配准[J]. 武汉大学学报: 信息科学版, 2010 ,35 (2) : 233 –236.]
-
[13] Jia F M, Kang Z Z, Yu P. A SIFT and Bayes sampling consensus method for image matching[J]. Acta Geodaetica et Cartographica Sinica, 2013 ,42 (6) : 877 –883. [ 贾丰蔓, 康志忠, 于鹏. 影像同名点匹配的SIFT算法与贝叶斯抽样一致性检验[J]. 测绘学报, 2013 ,42 (6) : 877 –883.]
-
[14] Luo J, Gwun O. A Comparison of SIFT, PCA-SIFT and SURF[J]. Journal of Business Education, 2009 ,3 (4) : 143 –152.
-
[15] Lowe D G. Distinctive image features from scale-invariantkeypoints[J]. International Journal of Computer Vision, 2004 ,60 (2) : 91 –110. [DOI:10.1023/B:VISI.0000029664.99615.94]
-
[16] Kim T, Im Y J. Automatic satellite image registration by combination of matching and random sample consensus[J]. IEEE Transactions on Geoscience and Remote Sensing, 2003 ,41 (5) : 1111 –1117. [DOI:10.1109/TGRS.2003.811994]
-
[17] Dong P,Galatsanos N P. Affine transformation resistant watermarking based on image normalization[C]//Proceedings of 2002 International Conference on Image Processing. Rochester, NY, USA: IEEE, 2002, 3: 489-492. [DOI: 10.1109/ICIP.2002.1039014]
-
[18] Yang H C, Zhang S B, Zhang Q Z. Least squares matching methods for wide base-line stereo images based on SIFT features[J]. Acta Geodaetica et Cartographica Sinica, 2010 ,39 (2) : 187 –194. [ 杨化超, 张书毕, 张秋昭. 基于SIFT的宽基线立体影像最小二乘匹配方法[J]. 测绘学报, 2010 ,39 (2) : 187 –194.]
-
[19] Zhao L K, Song W D, Wang J X. Straight line extraction algorithm of freeman chain codepriority[J]. Geomatics and Information Science of Wuhan University, 2104 ,39 (1) : 42 –46, 122. [ 赵丽科, 宋伟东, 王竞雪. Freeman链码优先级直线提取算法研究[J]. 武汉大学学报: 信息科学版, 2104 ,39 (1) : 42 –46, 122.] [DOI:10.13203/j.whugis20120690]
-
[20] Wang J X, Song W D, Zhao L K, et al. Application of improved freeman chain code in edge tracking and straight line extraction[J]. Journal of Signal Processing, 2014 ,30 (4) : 422 –430. [ 王竞雪, 宋伟东, 赵丽科, 等. 改进的Freeman链码在边缘跟踪及直线提取中的应用研究[J]. 信号处理, 2014 ,30 (4) : 422 –430.] [DOI:10.3969/j.issn.1003-0530.2014.04.008]
