基于双阈值SSDA模板匹配的遥感图像道路边缘检测研究

阙昊懿， 黄辉先， 徐建闽

(1.湘潭大学信息工程学院，湘潭 411105； 2.华南理工大学土木与交通学院，广州 510200)

0 引言

随着遥感图像处理技术的发展和图像分辨率的不断提高[1]，基于高分辨率遥感图像[2]的道路专题信息提取技术已广泛应用于城市交通研究领域。而由纵横交错的城市道路网构成的庞大交通网络，也自然而然成为了遥感图像在城市交通领域的研究热点之一。目前，从遥感图像上提取道路边缘信息的算法主要有边缘检测[3-4]、Hough直线提取[5-7]以及模板匹配[6-11]等等。其中，边缘检测就是通过对图像灰度跃变的分析寻找图像区域边缘的技术。对于数字图像，通常使用卷积或是类似卷积的方法来实现对灰度的分析。常用的边缘检测算法有梯度法[2]、Roberts梯度法[3]和Sobel算法等[4]。 Hough变换常常被用来对图像中的直线和圆进行识别[7]，但是Hough变换对于间断点以及不规则图形的检测效果并不理想[8]。

模板匹配技术一般是基于已知的模板，利用影像的灰度、形态等特征算法对待识别的图像进行匹配计算，判断图像中是否含有该模板的信息和坐标。但模板匹配算法计算量过大，匹配速度较低[11]。为此，本文提出了一种基于减小增长误差的序列模板匹配检测算法，旨在提高算法检测精度的同时，减小模板匹配的计算量，提高检测速度，抑制增长误差。

1 检测算法

1.1 模板匹配算法

在图像识别过程中，模板匹配是将待匹配的图像与被搜索图像的全部或部分在空间上对准，根据已知模式的图像在一幅陌生图像中寻找对应该模式子图像的过程。将模板T(M×N)叠放在被搜索图像S(W×H)上并平移(M和N分别表示模板纵向和横向的像素个数)。令模板覆盖下的图像区域为子图像Sij(i和j是子图像左上角像素点在图像上的坐标)。模板匹配就是通过比较模板T与子图像Sij的相似性来完成模板匹配的过程。定义模板T与子图像Sij的差的平方为D(i,j)，则

(1)

将式(1)展开，得到

(2)

式中： 等号右面第1项为子图像Sij的能量； 第3项为模板T的能量； 第2项表示模板T和子图像Sij的相关程度，用相关系数Rij表示。将R(i,j)归一化得

(3)

当模板T和子图像Sij完全一致时，相关系数R(i,j)=1。R(i,j)越大，表明T与Sij的相似度越高。

使用典型的模板匹配算法对道路边缘进行检测时，由于每次都必须遍历原图进行搜索并对比，因此存在计算量大、速度较慢等缺点。

1.2 SSDA算法

模板匹配算法效率低下的原因是无法将更多的计算时间用在更接近目标的区域范围内，且算法中相关阈值的选取较为困难。模板过大容易导致错测，过小则漏检，严重影响检测的准确性； 但如果将模板数目固定，则在更大的环境中，模板匹配算法不具备智能性[12]。

为了加快匹配速度，Barnea[13]于1972年提出了序贯相似性检测算法(sequential similarity detection algorithm,SSDA)。该算法通过人为设定一个固定阈值，使不匹配位置上的计算及早终止，以减小计算量，达到提高运算速度的目的。定义模板T与子图像Sij差的绝对值为D(n)，则

(4)

式中Tp和Sp分别为模板T与子图像Sij的第p个像素值。定义阈值△k，在模板T与搜索子图Sij的相似度测试D(n)的搜索过程中，如果到达其中某一像素点时，对应的D(n)超过了预设阈值△k，则表示此处配准不成功，记录当前的匹配次数n，结束该搜索子图并开始下一次配准。当满足结束判断条件的值较小时，说明系统能够迅速判别出此次配准失败，因而可以节约大量的计算时间。这种算法的性能在很大程度上取决于阈值△k的设定。当△k较小时，D(n)可能很快超过此阈值而终止当前匹配，虽然降低了计算量，但是会增加过早结束搜索的可能性，导致配准图像未能检测到，降低了配准精确性； 而阈值△k较大时，虽然精确性得到了保证，但处理速度大大降低。

1.3 双阈值SSDA算法

为提高模板匹配算法对目标区域的检测效率，以及解决阈值选取困难的问题，本文提出了双阈值判断算法。该算法将明显不在匹配范围的数据丢弃，避免重复检测，提高了算法效率； 将匹配度较高的数据直接保存为匹配目标； 在匹配度高与低的中间范围，进行减小增长误差的全样本序贯时序性模板匹配判断，进一步提高了算法的检测精度。

首先，定义一个子图与模板的绝对误差，即

(5)

式中：k为模板序号，0△k1，抛弃当前εk(i,j)； ②当εk(i,j)≤△k2时，作为匹配目标进行保存，并记录为新样本； ③当△k2<εk(i,j)≤△k1，记录当前εk(i,j)的坐标值(i,j)及εk(i,j)值，并建立一个数组a(i,j,q)进行保存。

针对上述3种不同的结果，可以对应采用3种方式进行处理。配准值高于△k2的，则记录为匹配目标保存； 配准值较低，则不处理； 配准值处于△k1和△k2之间，则记录当前模板，并进行二次判断。这种处理方式大大提高了处理效率，将匹配范围减小到更接近于目标的检测范围内，在提高了检测精度的同时，减少了不必要的非目标范围的检测计算，从而提高了算法的检测效率。

对于结果③出现的在2个阈值间的子图，其图像介于相似度高和相似度低之间。为了提高该区域的检测精度，本文将采用基于减小增长误差的双阈值序列模板匹配算法对这一范围内的子图进行检测。

在SSDA算法带来运算速度提升的过程中，由于样本数目的不断增加，相应检测的误差也会不断增长，因此，本文根据统计增长误差的方法，提出了一个抑制增长误差的算子，保证了检测的准确性。

首先，定义总误差为每个样本误差之和，即

(6)

定义算子

(7)

由式(7)可以看出，f(p)是一个单调递增函数。当p=1时，f(p)=0； 当样本数不断增加时，f(p)将随着p的增加而不断增长。

将该算子加入误差计算，并记录累加次数q，得到最终的误差计算公式，即

(8)

式中εresult是总误差与匹配算子f(p)的差值。由于总误差是由每个样本误差之和累加的，当样本数增加时，总误差也在不断增加。匹配算子f(p)的提出，可以减小因样本数增加而带来的误差总量的增加，从而提高了算法的检测率。

将每次误差值不断累加，当εresult≥△k3时，计算中止，并记录当前累加次数q1～qp。记录q1～qp分布概率函数，并结合图形取得一个接近结果的分布值t，当qi>t时，记录为匹配目标，当qi≤t时，将结果抛弃。算法流程如图1所示。

图1 算法流程

2 方法实验

该算法适用于在较多相似目标中寻找匹配度较高的目标。因此，本实验选择的图像结构较为简单。2幅图像均通过Google Earth得到。

首先，对图像进行灰度化，得到灰度图； 然后采用中值滤波消除图像中的干扰点，用均质灰度检测方法获取边缘的大致分布。均质灰度检测的方法是在图像上取一个5像素×5像素的区域，计算其均值、标准差及均值差分绝对值，若均值差分绝对值较小，且标准差也较小，则视该像素区为同一类别对象，并将像素区矩阵元素的灰度取均值。若均值差分绝对值较大，则视为边缘区域。通过在图像上进行循环计算，就能检测出图像相同介质分布，并去除一些较小的噪点，得出大致的边缘分布情况。

获取均质灰度分布图像后，利用阈值分割方法得到二值化图像。对图像进行分析，利用轮廓检测方法将图像中路面车辆信息以及部分干扰去除，即可得到预处理后的图像。

采集图像规则道路边缘子图像为正模板，形变较大的且不规则部分边缘子图像为负模板，正、负样本初始数目各为15。使用本文匹配算法仿真得出道路边缘，并与其他算法得出的道路边缘结果进行对比(图2，3)。

(a) 原图像(b) 预处理后结果(c) Sobel算子检测结果

(d) Hough概率检测结果(e) 梯度算子检测结果(f) 本文方法检测结果

(a) 原图像(b) 预处理后结果(c) 梯度算子检测结果

(d) Sobel算子检测结果(e) Hough概率检测结果(f) 本文方法检测结果

由图2可知，Sobel算子的边缘检测方法虽然能得出道路边缘，但是边缘不连续，且没有消除杂点信息(图2(c))； Hough概率检测方法(红线部分为监测结果)虽然能准确地提取出大部分边缘信息，但对干扰信息较多或边缘形变较大部分的提取，效果依然不理想(图2(d))； 梯度算子检测结果遗漏了过多的边缘信息(图2(e))。本文采用双阈值模板匹配方法提取出了较为完整的边缘信息，且对于干扰及细节部分的滤除效果令人满意(图2(f))。

对于带有大量干扰以及细节信息的图像(图3)，采用梯度算子和Sobel算子的检测结果仍然包含大量干扰信息，得不出完整的道路边缘(图3(c)(d))。Hough概率检测(红线部分)能提取出大部分道路边缘信息，但对阴影部分的道路边缘不能识别，且提取结果不完整(图3(e))，对干扰点较多部分，Hough概率也无法检测出准确的结果。本文方法不但能提取出正确的边缘信息，同时也消除了原图中道路边缘上因亮度不均导致的干扰信息，提取的边缘信息完整准确(图3(f))。

3 结论

本文从道路边缘的影像特征出发，提出了使用双阈值的序贯相似性检测算法(SSDA)的模板匹配方法提取道路边缘信息，同时，根据SSDA存在的总误差随着样本数增加而不断增大的问题，定义了一个减小增长误差的算子。从理论和实验的结果可以看出，该方法有以下3个优点： ①设计过程中考虑了阈值选取的复杂性，提出了采用双阈值多结果的处理方法，增加了模板匹配阈值选择的弹性空间； ②在对道路边缘信息提取过程中，能修复预处理时难以消除的干扰信息，完整显示道路的边缘； ③提取方法有一定的机器学习能力，带有一定的智能性。本算法适用于一般直线道路的边缘信息提取，对噪声不敏感，具备很好的检测效果。

参考文献(References)：

[1] 孙家柄.遥感原理与应用[M].武汉:武汉大学出版社,2003:79-111.

Sun J B.Principles and Applications of Remote Sensing[M].Wuhan:Wuhan University Press,2003:79-111.

[2] 李石华,王金亮,毕艳,等.遥感图像分类方法研究综述[J].国土资源遥感,2005,17(2):1-6.

Li S H,Wang J L,Bi Y,et al.A Review of methods for classification of remote sensing images[J].Remote Sensing for Land and Resources,2005,17(2):1-6.

[3] 朱长青,王耀革,马秋禾,等.基于形态分割的高分辨率遥感影像道路提取[J].测绘学报,2004,33(4):347-351.

Zhu C Q,Wang Y G,Ma Q H,et al.Road extraction from high-resolution remotely sensed image based on morphological segmentation[J].Acta Geodaetica et Cartographica Sinica,2004,33(4):347-351.

[4] Kaplan N H,Erer I,Kent S.Edge detection in remote sensing images via lattice filters based subband decomposition[C]//Proceedings of the 4th International Conference on Recent Advances in Space Technologies.IEEE,2009:437-440.

[5] Cai Y Q,Tong X H,Shu R.Multi-scale segmentation of remote sensing image based on watershed transformation[C]//IEEE Joint Urban Remote Sensing Event.Shanghai,2009:1-6.

[6] 梅珍,林伟.SAR图像道路检测及其仿真[J].计算机仿真,2010,27(5):201-203,251.

Mei Z,Lin W.SAR image road detection and simulation[J].Computer Simulation,2010,27(5):201-203,251.

[7] 邓小炼,王长耀,王汶,等.一种遥感影像地面控制点动态模板匹配算法[J].国土资源遥感,2005,17(2):7-11.

Deng X L,Wang C Y,Wang W,et al.An efficient remote sensing image ground control point matching algorithm based on dynamic template[J].Remote Sensing for Land and Resources,2005,17(2):7-11.

[8] Yu X Q,Chen X,Jiang M.Motion detection in moving background using a novel algorithm based on image features guiding self-adaptive Sequential Similarity Detection Algorithm[J].Optik-International Journal for Light and Electron Optics,2012,123(22):2031-2037.

[9] Du P J,Liu S C,Xia J S,et al.Information fusion techniques for change detection from multi-temporal remote sensing images[J].Information Fusion,2013,14(1):19-27.

[10]Lopez-Molina C,De Baets B,Bustince H,et al.Multiscale edge detection based on Gaussian smoothing and edge tracking[J].Knowledge-Based Systems,2013,44:101-111.

[11]Fazan A J,Poz A P D.Rectilinear building roof contour extraction based on snakes and dynamic programming[J].International Journal of Applied Earth Observation and Geoinformation,2013,25:1-10.

[12]Yang G W,Xu F C.Research and analysis of image edge detection algorithm based on the matlab[J].Procedia Engineering,2011,15:1313-1318.

[13]Barnea E I,Silverman H F A.A class of algorithms for fast digital image registration[J].IEEE Transactions on Computers,1972,C-21(2):179-186.