均值漂移与卡尔曼滤波相结合的遥感影像道路中心线追踪算法

曹帆之,朱述龙，朱宝山，李润生，孟伟灿

信息工程大学地理空间信息学院，河南 郑州 450000



均值漂移与卡尔曼滤波相结合的遥感影像道路中心线追踪算法

曹帆之,朱述龙，朱宝山，李润生，孟伟灿

信息工程大学地理空间信息学院，河南 郑州 450000

Foundation support： The National Natural Science Foundation of China (No. 41401462)

摘要：基于模板匹配的道路追踪方法是道路提取中较实用的一类方法，但传统模板匹配方法主要以相关系数作为相似性测度，对车辆、树荫等遮挡敏感，不适用于高分辨率遥感影像道路提取。针对这一问题，本文采用一种稳健的相似性测度，设计了一种基于均值漂移的道路中心点匹配算法，克服了传统模板匹配对遮挡敏感的缺点；然后运用卡尔曼滤波，实现高分辨率遥感影像道路中心线追踪。试验表明，该方法能够准确提取高分辨率遥感影像道路中心线，对车辆、树荫等遮挡具有稳健性。

关键词：高分辨率遥感影像；道路提取；道路中心线追踪；模板匹配；均值漂移；卡尔曼滤波

从遥感影像上自动提取道路是地理信息系统(GIS)快速获取和更新道路数据的一种有效途径。随着高分辨率遥感技术的快速发展，在高分辨率遥感影像上提取道路成为近年的研究热点[1-6]。在高分辨遥感影像上，道路两侧的树木阴影、路面上行驶的汽车等都会对道路提取产生不利影响，如何滤除这些不利影响是高分辨率影像道路提取的关键。

目前遥感影像道路提取方法按自动化程度可分为全自动提取和半自动提取[7]。全自动提取虽然经过多年的研究，但仍未取得突破性的进展[8]。现有的全自动算法稳健性差，提取结果需要大量人工后处理，效果不理想，因此采用人机交互方式的半自动提取是当前更好的选择[9]。在各种半自动提取方法中，基于模板匹配的方法被认为是更实用的一类方法[10]。但传统的模板匹配方法主要采用相关系数作为相似性测度[11]，因此对遮挡敏感，稳健性差，当路面上出现树荫、车辆时会产生较大的匹配误差，不适用于高分辨率遥感影像道路提取。针对这一问题，国内外的学者提出了各种方法。这些方法主要通过引入几何约束条件[12]、运用贝叶斯滤波[13-14]或神经网络[15]等方式来优化匹配结果，提高道路追踪的稳健性，取得了一定的效果，但这些方法并没有从本质上解决模板匹配对遮挡敏感的问题。

通过分析传统模板匹配对遮挡敏感的原因，本文设计了一种基于均值漂移的道路中心点匹配算法。

1基于均值漂移的道路中心点匹配

本文设计了一种基于均值漂移的道路中心点匹配算法，该算法采用一种稳健的概率相似性测度，能够在目标区域内根据道路中心点模板寻找相似度最大点，作为道路中心点，对遮挡不敏感。

1.1核密度估计

核密度估计[16]是在概率论中用来估计未知的概率密度函数，是一种非参数估计方法。假定n个数据点xi,i=1,2，…,n在d维空间Rd，核密度估计采用如下形式

(1)

(2)

1.2概率相似性测度

相关系数是匹配算法中常用的相似性测度，但对粗差敏感，这导致很多道路追踪算法对车辆、树荫敏感，稳健性差。本文采用概率相似性测度[17]，这种相似性测度对粗差具有稳健性，具体计算方式如下：

(3)

式中，K(x)为高斯核函数。相似性测度公式(3)的实质是利用式(1)计算对象y的每一个样本点在对象x中的概率密度估值，再将它们的平均值作为对象y与对象x的相似度，可以直观地理解为计算对象y是对象x的概率。相似性测度公式(3)由于使用了核函数，因而能够有效地限制粗差的影响。

1.3均值漂移算法

均值漂移算法是一种步长自适应的梯度上升算法[18-20]，能够快速地收敛于d维空间内一系列离散点对应的概率密度函数的局部极值。均值漂移向量的标准形式为

(4)

式中，m(x)为x处的均值漂移向量；K(x)为核函数；W(x)为权函数；S为样本点集，s为样本点。

1.4道路中心点匹配的计算过程

道路中心点匹配的基本过程为：首先，给定一个道路中心点模板和一个匹配初始点；然后，算法以匹配初始点为中心建立目标区域；最后，利用均值漂移算法寻找目标区域内相似度最大的点，作为道路中心点。计算过程如下所示。

(5)

式中，K(x)和W(x)都为高斯核函数。

令初始点与道路中心点的相似度函数为

l(y0)=lnJ(y0)

(6)

l(y0)=J(y0)/J(y0)

而

x0-y0

(7)

y0j+1=y0j+L(y0j)

(8)

图1　道路中心点匹配试验Fig 1　Experiment of road center matching

在图1(a)所示的匹配过程中，匹配初始点y0移动的步长与次数的关系如图1(c)所示。从图1(c)可以看出，初始点距离道路中心点较远时(移动次数小于16)，移动步长较大，随着初始点越来越接近道路中心点(移动次数超过16次)，移动步长迅速递减并趋于零，初始点y0最终收敛于道路中心点。

2结合卡尔曼滤波的道路中心线追踪

基于均值漂移的道路中心点匹配算法充分利用道路中心点模板信息和目标区域内的样本信息来寻找道路中心点，对车辆和树荫等遮挡具有稳健性，但没有考虑道路中心点的先验信息。因此，为了进一步提高道路中心线追踪的稳健性，本文在道路中心点匹配算法的基础上结合卡尔曼滤波， 利用卡尔曼滤波的预测过程给道路中心点匹配算法提供匹配初始点，而匹配得到的道路中心点作为卡尔曼滤波的观测值，进而迭代追踪道路中心线。具体流程如图2所示。

(9)

由式(9)可知，状态预测过程不属于线性过程，需要使用扩展卡尔曼滤波[21]。预测状态向量的协方差矩阵为

(10)

式中，Φt+dt表示状态方程线性化后的系数矩阵；Qt+dt表示系统噪声的协方差矩阵。在预测过程之后，则利用道路中心点匹配算法获取观测值，即

(11)

式中，φt+dt表示t+dt处的道路方向观测值，可由道路中心点坐标观测值和上一状态的中心点坐标估值计算得到。则观测方程为

(12)

式中，zt+dt表示t+dt处的状态向量。那么t+dt处的状态向量估值为

(13)

式中，Kt+dt为卡尔曼滤波增益，计算公式为

(14)

式中，Rt+dt为观测值的协方差矩阵。

图2　道路中心线追踪流程图Fig.2　Flow chart of road centerline tracking

由式(14)可知，系统误差的协方差Q和观测值的协方差R在卡尔曼滤波中发挥着非常重要的作用。在本文中，系统误差主要由实际道路的曲率决定，因而系统误差的协方差Q应根据实际道路曲率而定。对于观测值协方差R的确定，采用如下自适应策略：在每匹配一个道路中心点之后，算法将利用式(5)计算匹配点与道路中心点的相似度，根据相似性实时确定R，同时还结合道路中心线应为光滑曲线这一特征，即如果观测值中的方向与上一个道路方向估值的差值超过阈值，则增大R。

最后，利用式(9)—式(14)迭代追踪高分辨率遥感影像上的道路中心线。

3试验与分析

本文设计了4组试验：第1组试验验证概率相似性测度的稳健性；第2组试验测试本文的道路中心点匹配算法的性能；第3组试验验证卡尔曼滤波的优化作用；第4组试验为高分辨率遥感影像道路中心线追踪试验。试验数据采用QuickBird影像。

3.1相似性测度的稳健性测试

试验将本文所使用的相似性测度与相关系数对比，验证本文的相似性测度的稳健性，具体如下。

(1) 试验1。对目标旋转的稳健性测试。图3(a)为目标模板，图3(b)、(c)为待匹配图像。由图3(b)、图3(c)可知，待匹配图像相对目标模板发生了25°的旋转。试验运用两种相似性测度逐像素的计算待匹配图像内每一个位置与目标模板的相似度，然后选取相似度最大的点作为最佳匹配点。结果如图3所示。

图3　稳健性测试1Fig.3　Robustness test 1

(2) 试验2。对遮挡的稳健性测试。图4(a)为目标模板，图4(b)、4(c)为待匹配图像，其中待匹配图像中的白色区域为遮挡，灰度值为255。过程与试验1相同，结果如图4所示。

图4　稳健性试验2Fig.4　Robustness test 2

由图3、4可知，当目标旋转或被遮挡时，相关系数无法准确度量出目标的真实位置，而本文所

使用的相似度不受目标旋转、遮挡的影响，准确度量出目标的位置。因此，由本组试验可知，本文所使用的相似性测度比相关系数更稳健。

3.2道路中心点匹配试验

(1) 试验3。测试基于均值漂移的道路中心点匹配算法对车辆、树荫等遮挡的稳健性。试验3在各种存在遮挡的道路场景中进行单个道路中心点匹配试验。试验中，先由人工给定道路中心点模板和一个匹配初始点，然后算法在以初始点为中心的目标区域内匹配道路中心点，结果如图5所示。

从图5(a)—图5(e)可以看出，基于均值漂移的道路中心点匹配算法对车辆遮挡具有很强的稳健性。而当道路存在小面积树荫遮挡时，本文的道路中心点匹配算法能准确匹配出道路中心点，如图5(f)-图5(h)所示。但当道路存在大面积树荫遮挡时，道路中心点匹配算法出现误匹配，产生较大的匹配误差，如图5(l)、图5(m)所示。针对这些误匹配点，本文将在后续部分使用卡尔曼滤波对其进行修正。

图5　单个道路中心点匹配结果Fig.5　Results of matching single road center

(2) 试验4。将基于均值漂移的道路中心点匹配算法与经典的相关系数模板匹配进行对比。试验中，使用同一模板，分别利用两种匹配算法对一幅存在汽车遮挡的道路影像进行中心线追踪，具体过程为:首先，以道路中心线上一点为中心定义模板窗口，并将这一点作为道路中心线追踪的起始点；然后，根据起始点和道路方向预测下个道路中心点的初始位置；接着，在道路中心点初始位置运用匹配算法匹配道路中心点，并利用匹配得到的道路中心点继续预测下个道路中心点的初始位置；最后，重复前述过程，提取道路中心线。框架为道路中心点模板，试验结果如图6所示。

图6　基于均值漂移的道路中心点匹配与相关系数匹配的对比试验Fig.6　Comparison between the mean shift based road center matching algorithm and correlation coefficient matching

由图6(b)可知，利用本文的道路中心点匹配算法能够准确提取道路中心线，对车辆遮挡具有稳健性。对比图6(a)可知，两种匹配算法在没有车辆遮挡的路段上都能准确匹配出道路中心点，但当路面出现车辆时，相关系数匹配受车辆的影响会产生较大的匹配误差。而基于均值漂移的道路中心点匹配算法能够排除车辆的影响，准确匹配道路中心点。

3.3卡尔曼滤波优化试验

试验5，目的是为了验证卡尔曼滤波对道路中心点匹配算法的优化作用。试验过程为：①单独利用基于均值漂移的道路中心点匹配算法对两幅存在树荫遮挡的道路影像进行中心线追踪；②将基于均值漂移的道路中心点匹配算法与卡尔曼滤波结合对同样两幅影像进行道路中心线追踪。本文使用中心线提取的位置偏差作为精度衡量指标[3]，道路中心线提取和精度统计结果分别如图7和表1所示。

由图7(a)可知，仅使用道路中心点匹配算法提取的道路中心线在树荫遮挡路段明显偏离了实际道路中心线，存在较大匹配误差；而在图7(b)中，在原有的道路中心点匹配算法基础上结合卡尔曼滤波后，修正了在树荫遮挡路段的误匹配。在图7(c)中，仅使用道路中心点匹配算法提取的道路中心线受大面积树荫的影响出现一定的波动；而在图7(d)中，在结合卡尔曼滤波后算法有效地排除了树荫的影响。由表1可知，在结合卡尔曼滤波后道路中心线的提取精度得到显著提高。

图7　卡尔曼滤波优化试验Fig.7　Tests for optimization of Kalman filtering

像素

由本试验可知，卡尔曼滤波能够有效地修正由道路中心点匹配算法产生的误匹配，提高道路中心线追踪的稳健性和精度。

3.4道路中心线追踪试验

试验6，选取存在车辆、树荫遮挡的道路影像对算法进行测试。试验道路分为高速公路和乡村道路，其中高速公路上存在大量的车辆和树荫遮挡，在乡村道路上存在树枝遮挡。试验中，需由人工选定道路中心点模板和指定道路初始方向，试验结果如图8所示。

从图8可知，无论是高速公路还是乡村道路，本文的道路中心线追踪方法都能够排除车辆、树荫等遮挡的影响，提取道路中心线。因此，本文所提出的道路中心线追踪方法是一种稳健的道路追踪算法。

图8　道路中心线追踪试验1Fig 8　 Road centerline tracking experiment 1

图9　道路中心线追踪试验2Fig.9　Road centerline tracking experiment 2

为了进一步测试算法的性能，试验7选取尺寸为2428×2504像素的影像进行试验。影像中有两条相交的道路，总长约为3 km，路面上存在较多车辆、树荫遮挡。试验采用人机交互的方式，由人工输入一系列种子点，算法以第一个种子点为起始点，根据当前种子点和下一个种子点计算道路初始方向，追踪至下一个种子点时更换道路中心点模板，如图9所示。图9(c)中的黑色框架为道路中心点模板。试验7中，人工总共输入6个种子点，算法共提取1283个道路中心点，提取的道路中心点的最大位置偏差为4像素，平均位置偏差为1.0像素，位置偏差的中误差为0.8像素，如图9所示。由图9(b)可知，本文提出的道路追踪算法能够排除车辆、树荫的干扰，准确提取道路中心线。当道路一侧出现分岔口时，算法能够不受分岔口影响，继续按原先道路方向追踪，而当道路A追踪完毕后，再由人工重新输入种子点，更换模板，追踪道路B，如图9(c)所示。本文算法运用卡尔曼滤波，结合道路先验信息，因此能够适应道路宽度发生短暂变化的情况，如图9(d)所示。

4结论

本文提出了一种基于均值漂移和卡尔曼滤波的高分辨率遥感影像道路中心线追踪方法。该方法是一种对车辆、树荫等遮挡稳健的模板匹配方法，首先利用概率相似性测度和均值漂移算法设计了一种稳健的道路中心点匹配算法，取代了传统追踪算法中常用的相关系数匹配；然后结合卡尔曼滤波实现道路中心线的追踪。试验表明，该方法能够排除车辆、树荫遮挡的影响并能适应道路一侧存在分岔口的情况，对高分辨率道路影像取得较好的效果。但该方法只适用于道路存在明显边缘的道路影像，对道路形态的一致性有一定的要求，同时目前仍需人工提供道路中心点模板，且每次只能提取模板所在的道路。因此为了提高方法的自动化程度，下一步将研究模板的自动选取和更新。

参考文献：

[1]史文中, 朱长青, 王昱. 从遥感影像提取道路特征的方法综述与展望[J]. 测绘学报, 2001, 30(3): 257-262.

SHI Wenzhong, ZHU Changqing, WANG Yu. Road Feature Extraction from Remotely Sensed Image: Review and Prospects[J]. Acta Geodaetica et Cartographica Sinica, 2001, 30(3): 257-262.

[2]周绍光, 陈超, 岳建平. 形状先验和图割的高分辨率遥感影像道路段提取[J]. 测绘学报, 2014, 43(1): 60-65.

ZHOU Shaoguang, CHEN Chao, YUE Jianping. Extracting Roads from High-resolution RS Images Based on Shape Priors and Graph Cuts[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(1): 60-65.

[3]傅罡, 赵红蕊, 李聪, 等. 曲折道路遥感影像圆投影匹配改进追踪法[J]. 测绘学报, 2014, 43(7): 724-730, 738.

FU Gang, ZHAO Hongrui, Li Cong, et al. A Method by Improved Circular Projection Matching of Tracking Twisty Road from Remote Sensing Imagery[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(7): 724-730, 738.

[4]李怡静, 胡翔云, 张剑清, 等. 影像与LiDAR数据信息融合复杂场景下的道路自动提取[J]. 测绘学报, 2012, 41(6): 870-876.

LI Yijing, HU Xiangyun, ZHANG Jiangqing, et al. Automatic Road Extraction in Complex Scenes Based on Information Fusion from LiDAR Data and Remote Sensing Imagery[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(6): 870-876.

[5]李晓峰, 张树清, 韩富伟, 等. 基于多重信息融合的高分辨率遥感影像道路信息提取[J]. 测绘学报, 2008, 37(2): 178-184.

LI Xiaofeng, ZHANG Shuqing, HAN Fuwei, et al. Road Extraction from High-resolution Remote Sensing Images Based on Multiple Information Fusion[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(2): 178-184.

[6]雷小奇, 王卫星, 赖均. 一种基于形状特征进行高分辨率遥感影像道路提取方法[J]. 测绘学报, 2009, 38(5): 457-465.

LEI Xiaoqi, WANG Weixing, LAI Jun. A Method of Road Extraction from High-resolution Remote Sensing Images Based on Shape Features[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(5): 457-465.

[7]MENA J B. State of the Art on Automatic Road Extraction for GIS Update: A Novel Classification[J]. Pattern Recognition Letters, 2003, 24(16): 3037-3058.

[8]DAS S, MIRNALINEE T T, VARGHESE K. Use of Salient Features for the Design of a Multistage Framework to Extract Roads from High-resolution Multispectral Satellite Images[J]. IEEE Transactions on Geoscience and Remote Sensing, 2011, 49(10): 3906-3931.

[9]MIAO Zelang, WANG Bin, SHI Wenzhi, et al. A Semi-automatic Method for Road Centerline Extraction from VHR Images[J]. IEEE Geoscience and Remote Sensing Letters, 2014, 11(11): 1856-1860.

[10]林祥国, 张继贤, 李海涛, 等. 基于T型模板匹配半自动提取高分辨率遥感影像带状道路[J]. 武汉大学学报(信息科学版), 2009, 34(3): 293-296.

LIN Xiangguo, ZHANG Jixian, LI Haitao, et al. Semi-automatic Extraction of Ribbon Road from High Resolution Remotely Sensed Imagery by a T-shaped Template Matching[J]. Geomatics and Information Science of Wuhan University, 2009, 34(3): 293-296.

[11]孟樊, 方圣辉. 利用模板匹配和BSnake算法准自动提取遥感影像面状道路[J]. 武汉大学学报(信息科学版), 2012, 37(1): 39-42.

MENG Fan, FANG Shenghui. Quasi-automatic Extraction of Zonal Roads from Remote Sensing Images Using Template Matching and BSnake Model[J]. Geomatics and Information Science of Wuhan University, 2012, 37(1): 39-42.

[12]HU Xiangyun, ZHANG Zuxun, TAO C V. A Robust Method for Semi-automatic Extraction of Road Centerlines Using a Piecewise Parabolic Model and Least Square Template Matching[J]. Photogrammetric Engineering & Remote Sensing, 2004, 70(12): 1393-1398.

[13]ZHOU Jun, BISCHOF W F, CAELLI T. Road Tracking in Aerial Images Based on Human-computer Interaction and Bayesian Filtering[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2006, 61(2): 108-124.

[14]VOSSELMAN G, DE KNECHT J. Road Tracing by Profile Matching and Kaiman Filtering[M]∥GRUEN A, Kuebler O, Agouris P. Automatic Extraction of Man-made Objects from Aerial and Space Images. Basel: Birkhäuser, 1995: 265-274.

[15]HU Xiangyun, ZHANG Zuxun, ZHANG Jiangqing. An Approach of Semiautomated Road Extraction from Aerial Image Based on Template Matching and Neural Network[J]. International Archives of Photogrammetry and Remote Sensing, 2000, 33(B3): 994-999.

[16]SILVERMAN B W. Density Estimation for Statistics and Data Analysis[M]. London: Chapman and Hall, 1986.

[17]YANG Changjiang, DURAISWAMI R, DAVIS L. Efficient Mean-Shift Tracking via a New Similarity Measure[C]∥Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Diego, CA: IEEE, 2005, 1: 176-183.

[18]CHENG Yizong. Mean Shift, Mode Seeking, and Clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17(8): 790-799.

[19]张剑清, 刘朋飞, 王华, 等. 利用Meanshift进行道路提取[J]. 武汉大学学报(信息科学版), 2010, 35(6): 719-722.

ZHANG Jianqing, LIU Pengfei, WANG Hua, et al. Semi-automatic Road Extraction with Meanshift Algorithm[J]. Geomatics and Information Science of Wuhan University, 2010, 35(6): 719-722.

[20]COMANICIU D, MEER P. Mean Shift: A Robust Approach toward Feature Space Analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(5): 603-619.

[21]DEAN G C. An Introduction to Kalman Filters[J]. Measurement and Control, 1986, 19(2): 69-73.

(责任编辑：张艳玲)

修回日期： 2015-10-19

Tracking Road Centerlines from Remotely Sensed Imagery Using Mean Shift and Kalman Filtering

CAO Fanzhi,ZHU Shulong,ZHU Baoshan,LI Runsheng,MENG Weican

Institute of Geosgatial Information,Information Engineering University, Zhengzhou 450000, China

Abstract：Road tracking based on template matching is one class of practical methods of road extraction. However, the conventional methods of template matching mainly utilize correlation coefficient as the similarity measure. As a result, these algorithms are sensitive to occlusions caused by vehicles and trees and are unsuitable for road extraction from high-resolution remotely sensed imagery. To address this problem, this paper designs a road center matching algorithm based on mean shift utilizing a robust similarity measure, which overcomes the sensitivity of correlation coefficient matching to occlusions; then Kalman filter is utilized to track road centerlines from high-resolution remotely sensed imagery. Experimental results demonstrate that the proposed method can extract road centerlines from high-resolution remotely sensed imagery accurately and is robust to occlusions caused by vehicles and trees.

Key words：high-resolution remotely sensed imagery; road extraction; road centerline tracking; template matching; mean shift; Kalman filter

基金项目：国家自然科学基金(41401462)

中图分类号：P237

文献标识码：A

文章编号：1001-1595(2016)02-0205-09

作者简介：第一 邹文博(1991—)，女，硕士生，研究方向为卫星导航及其应用。

收稿日期：2015-03-10

First author： ZOU Wenbo(1991—)，female，postgraduate，majors in GNSS and its applications.

E-mail： zwb@bupt.edu.cn

引文格式：曹帆之,朱述龙，朱宝山,等.均值漂移与卡尔曼滤波相结合的遥感影像道路中心线追踪算法[J].测绘学报，2016,45(2)：205-212. DOI:10.11947/j.AGCS.2016.20140610.

CAO Fanzhi,ZHU Shulong,ZHU Baoshan,et al.Tracking Road Centerlines from Remotely Sensed Imagery Using Mean Shift and Kalman Filtering[J]. Acta Geodaetica et Cartographica Sinica,2016,45(2):205-212. DOI:10.11947/j.AGCS.2016.20140610.