﻿ 结合SIFT和Delaunay三角网的遥感图像配准算法
 计算机系统应用  2018, Vol. 27 Issue (10): 161-169 PDF

Remote Sensing Images Registration Algorithm Combining with SIFT and Delaunay Triangulation
QI Xi, CHEN Zhi-Yun
School of Computer Science and Software Engineering, East China Normal University, Shanghai 200062, China
Abstract: Aiming at the problems such as false matching points and large volume remote sensing image registration, a high-resolution remote sensing images registration algorithm based on coarse and fine registration is proposed. Firstly, the high scale space feature points were extracted after down sampling the images to execute the coarse registration. Secondly, the initial set of feature points was extracted using the Scale Invariant Feature Transform (SIFT) algorithm for each block after using image blocking strategy. Furthermore, feature points were used to obtain the Delaunay triangulation, and then calculated the similarity between blocks of both images to select pairs of triangles which the similarity greater than threshold. Finally, the fine registration was achieved by precise feature points. The proposed algorithm can reduce the number of feature points, and it can eliminate more false matching points to increase the correct feature point matching rate. The experimental results indicate that the proposed method is effective.
Key words: Scale Invariant Feature Transform (SIFT)     image registration     image blocking strategy     Delaunay triangulation

1 相关术语 1.1 SIFT配准原理

SITF算法是由David G. Lowe于1999年提出, 并在2004年加以完善. Lowe将尺度的概念引入到SIFT算法中, 利用SIFT方法检测图像特征点的实质就是在不同尺度空间上查找特征点, 这些特征点对应的就是不同尺寸的地物[17]. 而在高分辨影像中, 往往就是较小尺寸的地物会容易发生变化, 如房屋、汽车等等, 因此为了减少这些小尺寸地物对特征点提取的影响, 那么就要分尺寸的对图像中的地物进行分析. SIFT配准方法主要分为四步: 尺度空间的建立, 尺度空间中提取关键点, 生成特征点描述子, 特征点匹配.

(1) 尺度空间的构建: SIFT算法用函数 $L(x,y,\sigma )$ 来表示图像的尺度空间, 用函数 $I(x,y)$ 表示遥感图像, 则尺度空间就是由图像 $I(x,y)$ 和高斯函数 $G(x,y,\sigma )$ 卷积生成的, 公式为:

 $\;L(x,y,\sigma ) = I(x,y)*G(x,y,\sigma )$ (1)
 $G(x,y,\sigma ) = \frac{1}{{2\pi {\sigma ^2}}}{{\rm{e}}^{ - ({x^2} + {y^2})/\left( {2{\sigma ^2}} \right)}}$ (2)

 $\begin{gathered} D(x,y,\sigma ) = (G(x,y,k\sigma ) - G(x,y,\sigma ))*I(x,y) \\ = L(x,y,k\sigma ) - L(x,y,\sigma ) \\ \end{gathered}$ (3)

(2) 尺度空间中提取特征点: 尺度空间中的所有检测点都与其同尺度相邻的8个点和上下尺度各相邻的9个点进行比较, 只保留局部极值点. 之后去除其中不好的关键点, 通过子像元插值和剔除对比度低的点以及不稳定的边缘响应点来对精化检测到的关键点.

(3) 生成特征点描述子: 在以关键点为中心的邻域窗口内采样, 计算邻域内各像元的梯度幅值和梯度方向, 并用梯度方向直方图来统计邻域内像元的梯度方向, 则关键点的主方向就是直方图的峰值. 之后将坐标轴旋转为特征点的方向, 以确保旋转不变性, 然后对特征点周围区域进行分块, 分为 $\;4 \times 4$ 个子区域, 对每个块内的梯度方向进行统计, 得到8个方向的梯度方向直方图, 最终形成128维的SIFT特征向量.

(4) 特征点匹配: 使用欧氏距离来判断两幅图像特征点的相似性. 在匹配过程中, SIFT算法使用的是Kd-tree算法, 即找出待配准图像中与参考图像特征点A距离最近的点B和距离次近的点C, 将最近邻和次近邻距离相比, 若比值小于给定的阈值, 则认为匹配正确, 特征点AB是一对匹配点.

1.2 图像分块策略

(1) 第一种方式是预先设定图像块的边长, 然后对整幅图像分块. 适用于块数未知的情况.

(2) 第二种方式是预先设定好划分的块数, 根据块数来对整幅图像进行分块. 通常可划分 $\;2 \times 2$ $\;4 \times 4$ $\;8 \times 8$ 等.

1.3 Delaunay三角形相似函数

 ${I_a} = {\cos ^3}(\frac{\pi }{2}(1 - d(a')))$ (4)
 $d(a') = {e^{ - \frac{1}{{2{\sigma ^2}}}{{(a' - a)}^2}}}$ (5)

 $I = \frac{{({I_a} + {I_b} + {I_c})}}{3}$ (6)

2 高分辨率遥感图像配准改进算法 2.1 算法思路

(1) 对图像降采样后利用SIFT算法对图像进行粗配准. 因为单幅高分辨率图像的数据量很大, 所以从图像上提取的特征点数目很多, 如果直接利用这些特征点进行配准的话, 会增加计算量, 影响配准速度, 还容易造成误匹配, 从而降低配准精度. 因此, 在进行配准之前, 先对图像进行降采样处理, 然后利用SIFT算法提取两幅降采样图像的特征点. 通过对SIFT算法进行分析发现, 该算法中低尺度层的特征点往往对应的是高分辨率图像中较小尺寸地物, 比如城市区域中的建筑物等, 由于尺寸较小的地物在高分辨率图像中容易发生变化, 所以这类特征点的提取一般容易出现错误; 而算法中的高尺度层的特征点则对应的是一些尺寸比较大的地方, 比如说大面积的草坪、广场等等, 这类特征点一般比较稳定, 不会轻易的就发生变化[17]. 所以本文在进行粗配准时, 选用的就是这些比较稳定的特征点. 首先在进行SIFT尺度空间构建时, 把第三组及其以上尺度空间的特征点作为该尺度空间的高尺度特征点, 其它尺度空间的特征点作为该尺度空间的低尺度特征点. 选择高尺度空间的特征点进行特征匹配工作, 寻找待配准图像中与参考图像中特征点的距离最近与次近的特征点, 求得最近距离与次近距离的比值, 并将该值与给定阈值进行比较来得到匹配点对. 最后使用这些匹配点求得仿射变换模型, 对图像进行几何校正, 完成图像粗配准.

(2) 在图像分块的基础上提取特征点, 并完成初始匹配. 在上一步之后, 得到了待精配准图像和基准图像, 之后对这两幅图像进行精配准工作. 首先对两幅图像进行分块, 因为之前已对图像进行了粗配准, 所以此处对应位置的子块图像构成一组图像子块对, 之后分别对各组图像子块对进行特征点提取和匹配工作. 在这里使用的是SIFT算法对子块图像提取特征点, 完成初始匹配工作, 得到初始匹配点对.

(3) 构建Delaunay三角网, 利用三角形相似函数获得精确匹配点对. 首先使用逐点插入算法进行Delaunay三角形剖分, 得到三角形网. 之后针对三角形网使用三角形相似函数来度量三角网中所有三角形对之间的相似度, 构建相似度矩阵, 从中选取相似度大于等于判断标准s的三角形对作为候选三角形对, 该三角形对所对应的顶点对就是精确匹配点对. 本文对这一步的改进之处在于求解三角形对之间相似性时, 不需要计算整幅图像三角形之间的相似度, 而是利用第二步的图像分块, 分别在子图像上构建三角网, 然后计算一组图像子块对之间的三角形相似度矩阵这样可以大大减少计算量, 提高匹配效率. 最后得到了每组子图像对之间的精确匹配点对, 然后把这些子图像匹配点对的坐标转化为分块之前图像中点的坐标, 以便之后进行整幅图像的精配准.

(4) 在获得精确匹配点对之后, 进行仿射模型变换, 求解空间变换模型, 对图像进行几何校正, 完成最终的图像配准.

 图 1 改进算法流程图

2.2 评价标准

 $CMR = \frac{n}{N}$ (7)
 $RMSE = \sqrt {\frac{{\sum\nolimits_{i = 1}^n {[{{({x_{1i}}' - {x_{1i}})}^2} + {{({y_{1i}}' - {y_{1i}})}^2}]} }}{n}}$ (8)

 ${x_{1i}}' = {t_{11}}{x_{2i}} + {t_{12}}{y_{2i}} + {t_x}$ (9)
 ${y_{1i}}' = {t_{21}}{x_{2i}} + {t_{22}}{y_{2i}} + {t_y}$ (10)

3 配准实验结果及分析 3.1 实验数据和实验环境

3.2 实验结果及分析 3.2.1 实验分析过程

 图 2 实验数据图

3.2.2 实验对比结果

 图 3 使用SIFT算法和本文算法分别对三组图像的基准图像提取特征点示意图

 图 4 使用传统SIFT算法得到的匹配点及其连线图

 图 5 使用RANSAC和Delaunay三角剖分分别进行匹配点配对的效果图

 图 6 配准结果图

4 结论与展望

 [1] 王瑞瑞, 马建文, 陈雪. 多源遥感影像自动配准技术的研究进展. 遥感信息, 2011(3): 121-127. DOI:10.3969/j.issn.1000-3177.2011.03.023 [2] Han Y, Choi J, Byun Y, et al. Parameter optimization for the extraction of matching points between high-resolution multisensor images in urban areas. IEEE Transactions on Geoscience and Remote Sensing, 2014, 52(9): 5612-5621. DOI:10.1109/TGRS.2013.2291001 [3] Zitová B, Flusser J. Image registration methods: A survey. Image and Vision Computing, 2003, 21(11): 977-1000. DOI:10.1016/S0262-8856(03)00137-9 [4] 吕步云. SIFT结合图像信息的多源遥感图像配准技术研究[硕士学位论文]. 杭州: 杭州电子科技大学, 2015. [5] 尹奎英, 张雄, 李成, 等. 基于SIFT-Delaunay编码的SAR图像自动配准算法. 现代雷达, 2015, 37(4): 20-23, 30. DOI:10.3969/j.issn.1004-7859.2015.04.005 [6] 孙亮, 王双庆, 邢建春. 一种基于自适应阈值的改进MIC算法. 微电子学与计算机, 2015, 32(5): 79-83. [7] 强赞霞, 彭嘉雄, 王洪群. 基于傅里叶变换的遥感图像配准算法. 红外与激光工程, 2004, 33(4): 385-387, 413. DOI:10.3969/j.issn.1007-2276.2004.04.013 [8] 冷成财, 张海鹏, 张聪炫, 等. 基于尺度、方向和距离约束的改进SIFT配准方法. 纳米技术与精密工程, 2017, 15(1): 36-43. [9] 潘建平, 郝建明, 赵继萍. 基于SURF的图像配准改进算法. 国土资源遥感, 2017, 29(1): 110-115. [10] Lowe DG. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 2004, 60(2): 91-110. DOI:10.1023/B:VISI.0000029664.99615.94 [11] Morevec HP. Towards automatic visual obstacle avoidance. Proceedings of the 5th International Joint Conference on Artificial intelligence. Cambridge, MA, USA. 1977. 584. [12] Harris C, Stephens M. A combined corner and edge detector. Proceedings of the 4th Alvey Vision Conference. Manchester, UK. 1998. 147–152. [13] Bay H, Tuytelaars T, van Gool L. SURF: Speeded up robust features. Proceedings of the 9th European Conference on Computer Vision. Graz. 2006. 404–417. [14] Smith SM, Brady JM. SUSAN—A new approach to low level image processing. International Journal of Computer Vision, 1997, 23(1): 45-78. DOI:10.1023/A:1007963824710 [15] 樊东昊, 朱建军, 郭南男, 等. 一种结合区域选择和SIFT算法的遥感图像配准方法. 工程勘察, 2015, 43(2): 69-74. [16] 李孚煜, 叶发茂. 基于SIFT的遥感图像配准技术综述. 国土资源遥感, 2016, 28(2): 14-20. [17] 吴伟, 丁香乾, 闫明. 基于异常区域感知的多时相高分辨率遥感图像配准. 计算机应用, 2016, 36(10): 2870-2874. DOI:10.11772/j.issn.1001-9081.2016.10.2870 [18] 马旭燕, 袁媛, 汪承义, 等. 高分辨率遥感图像配准控制点均匀化算法. 遥感信息, 2016, 31(3): 24-30. DOI:10.3969/j.issn.1000-3177.2016.03.004 [19] 程国华, 王阿川, 陈舒畅, 等. 多源遥感影像高精度自动配准方法研究. 液晶与显示, 2016, 31(6): 604-612. [20] 郑守住. 改进SURF和Delaunay三角网的图像配准算法研究[硕士学位论文]. 南昌: 东华理工大学, 2014.