发布时间: 2019-11-16 摘要点击次数: 全文下载次数: DOI: 10.11834/jig.190079 2019 | Volume 24 | Number 11 图像理解和计算机视觉

 收稿日期: 2019-03-19; 修回日期: 2019-05-30; 预印本日期: 2019-06-06 基金项目: 国家自然科学基金项目（61601213）；中国博士后基金面上项目（2017M611252）；辽宁省教育厅项目（LJYL017，LR2016045） 第一作者简介: 贾迪, 1982年生, 男, 副教授, 主要研究方向为立体匹配与3维重建、视觉空间定位。E-mail:lntu_jiadi@163.com;赵明远, 男, 硕士研究生, 主要研究方向为像对立体稠密匹配。E-mail:zju_zmy@163.com;杨宁华, 男, 硕士研究生, 主要研究方向为图像匹配。E-mail:lgdyangninghua@163.com. 中图法分类号: TP391 文献标识码: A 文章编号: 1006-8961(2019)11-1962-10

# 关键词

Image dense matching based on smooth constraint and triangulation proportion
Jia Di, Wu Si, Zhao Mingyuan, Yang Ninghua
School of Electronic and Information Engineering, Liaoning Technical University, Huludao 125105, China
Supported by: National Natural Science Foundation of China (61601213); Postdoctoral Science Foundation Funded Project of China (2017M611252)

# Abstract

Objective The dense matching of image pairs is the basis of advanced image-processing technologies, such as vision localization, image fusion, and super-resolution reconstruction. Efficient dense matching results are difficult to obtain because image pairs may be affected by various photographic conditions. Therefore, this study proposes a dense matching method combining density-clustering, smoothing constraint and triangulation. Method First, ORB (oriented FAST and rotated BRIEF) algorithm is used to obtain the sparse matching point set and corresponding point set rapidly. The number of feature points directly arrived at by density in the neighborhood centered on the feature point is screened out by using integral graph. Connection distance, position information, and Euclidean distance are used to perform density estimation clustering, and the feature point pairs in the cluster are expanded by smoothing constraints. The inner point set is thus rapidly obtained. Second, the equal proportion property of triangulation under affine transformation, which plays a key role in the subsequent matching process, is proven. The triangulation is constructed on the basis of the interior point set. The positions of equal proportion points corresponding to the interior of the triangulation in two images to be matched are calculated by using this property, and the similarity of the two triangular regions is checked by the color information of these equal proportion points to purify the interior point set. Finally, the positions of dense matching points are calculated by using the refined interior point set as the final dense matching result. Result Three pairs of images with large photographic baseline in Mikoalyciz data set were selected for feature point-matching process and fast dense matching algorithm experiments. These groups of images were pairs of images with scaling, repeated texture, and rotation. All experiments were conducted in CPU and 8 GB memory with the main frequency of 3.3 GHz. In the environment of Windows compiler, MATLAB was selected as the development tool. Experimental results showed that the proposed method had the ability to resist rotation, scale change, and repeated texture by analyzing the matching accuracy and efficiency and could estimate local consistency and achieve dense matching of image pairs. The proposed method could also avoid the inaccurate estimation of affine transformation matrix caused by several local outliers and then affect the accuracy of global plane dense matching. The experimental parameters of grid-based motion statistics (GMS) and DeepMatching algorithm were the default values. The empirical values of the density-clustering-smoothing constraint purification interior point algorithm were obtained through considerable experimental experience. The GMS used the mesh-smoothing motion constraint method, although it could complete the local invariant point feature matching while eliminating the outliers, to ensure matching accuracy and improve processing speed. However, this method was restricted by the grid parameters and boundary conditions, which reduced the number of sparse matching points obtained by this method and affected the subsequent dense matching work. The number of sparse matching points was obviously more than that of the GMS matching points. The advantage of DeepMatching algorithm was that it did not depend strongly on continuity constraints and monotonicity. Nevertheless, its time complexity was high and operation time was long because the dense results obtained by each layer were checked step by step by using pyramid architecture. The density of the experimental results was higher than that of DeepMatching matching results, and the interior point purity was higher after smoothing constraints and equal proportional triangulation constraints. Obvious outliers existed in the DeepMatching matching results. The dense matching range of the proposed method was not as wide as that of DeepMatching. Methods with high sparse matching performance (e.g., affine scale-invariant feature transform) can effectively solve this problem owing to the distribution of sparse matching points. The memory and time requirements of the proposed algorithm increased linearly with an increase in image size. The matching time of this method increased slowly. The difference between the processing times of this algorithm and of DeepMatching was increasingly obvious. The accuracy gap between the proposed algorithm and DeepMatching algorithm was also obvious and stable. With the increase in image size to 512, the accuracy of the proposed algorithm reached 0.9 (error 10 pixels). This algorithm was superior to DeepMatching in time efficiency and accuracy. Particularly when dealing with large-scale images, it could guarantee high accuracy and greatly shorten the processing time of dense matching. Therefore, the proposed method not only improved the number of sparse matching points but also enhanced the execution speed, accuracy, and efficiency in processing large-scale images. Conclusion The experimental results verified the efficiency and practicability of the proposed method. In the future, this method will be integrated into advanced image processing, such as 3D reconstruction and super-resolution reconstruction.

# Key words

local consistency estimation; dense matching; equal proportion triangulation; affine transformation; smooth constraint

# 1.1 密度聚类平滑约束提纯内点

 $f\left( {{N_i}, {N_j}} \right) = \left\{ {\begin{array}{*{20}{l}} 1&{{f_{\rm{d}}}\left( {{N_i}, {N_j}} \right)\varepsilon , (i \ne j)}\\ 0&{{\rm{其他}}} \end{array}} \right.$ (1)

 $C_{N_{i}}=\iint_{D(x, y)+A(x, y)-B(x, y)-C(x, y)} f(x, y) \mathrm{d} x \mathrm{d} y$ (2)

 $\begin{array}{l} \left\| {\frac{1}{m}\sum\limits_{j = 1}^m {{{\left( {{E_{ij}} - \mu } \right)}^2}} - \varepsilon } \right\|\\ \alpha \left( {\mu = \frac{2}{{n(n - 1)}}\sum\limits_{i = 1}^n {\sum\limits_{j = i + 1}^n {{E_{ij}}} } } \right) \end{array}$ (5)

 $\mathit{\boldsymbol{A}} = \bigcup\limits_i {\left\{ {\left( {{N_i}, {M_i}} \right) \cup {\mathit{\boldsymbol{P}}_i}} \right\}} , \left( {{N_i}, {M_i}} \right) \in \mathit{\boldsymbol{C}}$ (6)

# 1.2 三角网等比例剖分稠密匹配

$τ$($\mathit{\boldsymbol{OA}}$)=τ($λ$·$\mathit{\boldsymbol{OP}}$)=λ($τ$($\mathit{\boldsymbol{OP}}$))=$λ$·$\mathit{\boldsymbol{O′P′}}$=$\mathit{\boldsymbol{O′A′}}$

$\tau(\boldsymbol{O} \boldsymbol{A})=\boldsymbol{O}^{\prime} \boldsymbol{A}^{\prime}$

$\mathit{\boldsymbol{AD = \lambda AC, A'D' = \lambda A'C'}}$

2) 建立[$m$, $n$]大小的零矩阵$\mathit{\boldsymbol{F}}_{sl}$，通过$\mathit{\boldsymbol{FP}}_a$确定每一个特征点的对应坐标($x$, $y$)，在$\mathit{\boldsymbol{F}}_{sl}$中将该坐标标记为1。

3) 计算$\mathit{\boldsymbol{F}}_{sl}$的积分矩阵$\mathit{\boldsymbol{F}}_{ig}$

4) 遍历$\mathit{\boldsymbol{FP}}_a$每一个特征点，通过积分矩阵$\mathit{\boldsymbol{F}}_{ig}$计算特征点周围10×10的矩阵区域特征点总数，通过计算邻域特征点总数判断是否剔除该特征点，得到筛选后的特征点集$\mathit{\boldsymbol{FP}}_a′$，数量为$N_a$

5) 以$\mathit{\boldsymbol{FP}}_a′$为基准，利用汉明距离实现特征点的初匹配，匹配对$\psi$的数量与特征点$\mathit{\boldsymbol{FP}}_a′$的数量相等，大小为$N_a$

6) 每个匹配对$\psi_{i}$所对应的一对特征点坐标分别为($x_{i}^{a}$, $y_{i}^{a}$)和($x_{i}^{b}$, $y_{i}^{b}$)，以($x_{i}^{a}$)为基准，计算每一对特征点的欧氏距离$D_i$和角度$θ_i$，形成集合[$D$, $θ$, $x_a$, $y_a$]。

7) 对邻域内的匹配点进行平滑约束，采用[$θ$, $D$, $x_a$, $y_a$]进行密度聚类(DBSCAN)处理剔除外点，从而得到内点集$\mathit{\boldsymbol{FP}}$1$\mathit{\boldsymbol{I}}$1$\mathit{\boldsymbol{FP}}$2$\mathit{\boldsymbol{I}}$2

1) 构建$\mathit{\boldsymbol{I}}$1的Delaunay三角网：

$Tri_{1}=D\left(\boldsymbol{F} \boldsymbol{P}_{1}\right)$

2) 根据$\mathit{\boldsymbol{I}}$1的三角网索引，构建$\mathit{\boldsymbol{I}}$2的Delaunay三角网：$Tr{i_2} = D\left({{\mathop{\rm ReIndex}\nolimits} \left({Tr{i_1}, \mathit{\boldsymbol{F}}{\mathit{\boldsymbol{P}}_2}} \right)} \right)$

3) 计算三角网$T r i_{1}$$T r i_{2}中三角形重心的坐标： Tr i C_{1}=F\left(Tr i_{1}\right); Tr i C_{2}=F\left(Tr i_{2}\right) 4) 计算三角网T r i_{1}$$T r i_{2}$中等比例点的坐标：

$Tri D_{1}=F^{\prime}\left(Tri_{1}, Tri C_{1}, m\right)$;

$Tri D_{2}=F^{\prime}\left(Tri_{2}, Tri C_{2}, m\right)$;

$n=size\left(TriD_{1}\right)$

5) 三角网中包含了$n$个三角形，向每个三角形中插入$m$个等比例点，通过这些等比例点衡量三角形的相似性，进一步优化构成相似三角形的内点集：

$j$ = 0;

for $i$ = 1:$n$

if ($disp$($TriD$1($i$), $TriD$2($i$)) / $m$ < $r$))

$TriD_a$($j$) = $Tri$1($i$);

$TriD_b$($j$)=$Tri$2($i$);

$j$ + +;

end

end

6) 根据内点集重新构造$\mathit{\boldsymbol{I}}$1$\mathit{\boldsymbol{I}}$2的三角网：

$T r i_{1}=D\left(T r i D_{a}\right)$;

$Tri_{2}=D\left(\operatorname{ReIndex}\left(Tri_{1}, Tri D_{b}\right)\right)$

7) 重新插入等比例点(同步骤4))，并输出

$V_{\mathrm{ver}}=\left[TriD_{1} \quad TriD_{2}\right]$

# 2.1 实验结果

GMS和DeepMatching实验参数的选取分别与文献[10]和文献[12]方法相同，设经验值$α$= 0.6，阈值$r$= 20，比例点数$m$= 100。

# 参考文献

• [1] Li B, Ming D L, Yan W W, et al. Image matching based on two-column histogram hashing and improved ransac[J]. IEEE Geoscience and Remote Sensing Letters, 2014, 11(8): 1433–1437. [DOI:10.1109/LGRS.2013.2295115]
• [2] Barnes C, Shechtman E, Goldman D B, et al. The generalized patchmatch correspondence algorithm[C]//Proceedings of European Conference on Computer Vision. Berlin: Springer-Verlag, 2010: 29-43.[DOI: 10.1007/978-3-642-15558-1_3]
• [3] Bian J W, Lin W Y, Matsushita Y, et al. GMS: Grid-based motion statistics for fast, ultra-robust feature correspondence[C]//Proceedings of 2017 IEEE Conference on Computer Vision and Pattern Recognition. Honolulu, HI, USA: IEEE, 2017: 2828-2837.[DOI: 10.1109/CVPR.2017.302]
• [4] Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91–110. [DOI:10.1023/b:visi.0000029664.99615.94]
• [5] Bay H, Tuytelaars T, Van Gool L. SURF: Speeded up robust features[C]//Proceedings of European Conference on Computer Vision. Berlin: Springer, 2006: 404-417.[sDOI: 10.1007/11744023_32]
• [6] Ma J Y, Zhao J, Tian J W, et al. Robust point matching via vector field consensus[J]. IEEE Transactions on Image Processing, 2014, 23(4): 1706–1721. [DOI:10.1109/TIP.2014.2307478]
• [7] Yi K M, Trulls E, Lepetit V, et al. Lift: Learned invariant feature transform[C]//Proceedings of European Conference on Computer Vision. Cham: Springer, 2016: 1-16.[DOI: 10.1007/978-3-319-46466-4_28]
• [8] Mikolajczyk K, Schmid C. A performance evaluation of local descriptors[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(10): 1615–1630. [DOI:10.1109/TPAMI.2005.188]
• [9] Mikolajczyk K, Tuytelaars T, Schmid C, et al. A comparison of affine region detectors[J]. International Journal of Computer Vision, 2005, 65(1-2): 43–72. [DOI:10.1007/s11263-005-3848-x]
• [10] Zhao Q S, Wu X Q, Bu W. Contactless palmprint verification based on sift and iterative ransac[C]//Proceedings of 2013 IEEE International Conference on Image Processing. Melbourne, VIC, Australia: IEEE, 2013: 4186-4189.[DOI: 10.1109/ICIP.2013.6738862]
• [11] Rublee E, Rabaud V, Konolige K, et al. ORB: An efficient alternative to SIFT or SURF[C]//Proceedings of 2011 International Conference on Computer Vision. Barcelona, Spain: IEEE, 2011: 2564-2571.[DOI: 10.1109/ICCV.2011.6126544]
• [12] Revaud J, Weinzaepfel P, Harchaoui Z, et al. DeepMatching:hierarchical deformable dense matching[J]. International Journal of Computer Vision, 2016, 120(3): 300–323. [DOI:10.1007/s11263-016-0908-3]
• [13] Wang J X, Zhang J, Zhang X. A dense matching algorithm of close-range images constrained by iterative triangle network[J]. Journal of Signal Processing, 2018, 34(3): 347–356. [王竞雪, 张晶, 张雪. 迭代三角网约束的近景影像密集匹配[J]. 信号处理, 2018, 34(3): 347–356. ] [DOI:10.16798/j.issn.1003-0530.2018.03.012]
• [14] Wang X J, Xing F, Liu F. Stereo matching of objects with same features based on delaunay triangulation and affine constraint[J]. Acta Optica Sinica, 2016, 36(11): 1115044–1. [王向军, 邢峰, 刘峰. Delaunay三角剖分和仿射约束的特征相同多物体同名点立体匹配[J]. 光学学报, 2016, 36(11): 1115044–1. ] [DOI:10.3788/AOS201636.1115004]
• [15] Xu N, Xiao X Y, You H J, et al. A pansharpening method based on HCT and joint sparse model[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(4): 434–441. [许宁, 肖新耀, 尤红建, 等. HCT变换与联合稀疏模型相结合的遥感影像融合[J]. 测绘学报, 2016, 45(4): 434–441. ] [DOI:10.11947/j.AGCS.2016.20150372]
• [16] Zhu H, Song W D, Tan H, et al. Remote sensing images super resolution reconstruction based on multi-scale detail enhancement[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(9): 1081–1088. [朱红, 宋伟东, 谭海, 等. 多尺度细节增强的遥感影像超分辨率重建[J]. 测绘学报, 2016, 45(9): 1081–1088. ] [DOI:10.11947/j.AGCS.2016.20150451]
• [17] Zhu H, Song W D, Yang D, et al. Dense matching method of inserting point into the delaunay triangulation for close-range image[J]. Science of Surveying and Mapping, 2016, 41(4): 19–23. [朱红, 宋伟东, 杨冬, 等. 近景影像三角网内插点密集匹配方法[J]. 测绘科学, 2016, 41(4): 19–23. ] [DOI:10.16251/j.cnki.1009-2307.2016.04.005]