基于动态规划的城市道路提取改进算法

刘晓平 ， 朱晓强， 余 烨， 李 琳

（1. 特种显示技术教育部重点实验室（合肥工业大学），安徽 合肥 230009；2. 合肥工业大学计算机与信息学院VCC研究室，安徽 合肥 230009）

从航空或卫星影像中提取道路一直都是一个很具有挑战性的问题。根据道路特征提取的自动化程度，道路特征提取分为自动特征提取和半自动特征提取。自动提取方法包括基于平行线对[1]、基于二值化和知识[2]、基于窗口模型特征[3]等；半自动提取的常用算法有模板匹配[4]、动态规划[6]、可变模型或Snakes方法[7]等。到目前为止，从航空或卫星影像中全自动识别道路仍然处于不成熟的状态[8]，而且在未来的短期时间内也很难开发一套完全脱离人工干预而自动识别道路的系统。在各种半自动道路提取方法中，由于动态规划是一个解决优化问题的稳定算法，能够确保结果的最优性，成为近年来道路半自动提取的首选方法之一。动态规划法首先应用在低分辨率影像提取道路中（Sakoda等，1993；Gruen和Li，1997；Merlet和 Zerubia，1996）。Dal Poz等[6]修改了“代价”函数，使之适用于从中高分辨率影像中提取道路。

另一方面，从机载LiDAR（Light Detection and Ranging）数据中提取道路在近年来也有了一定的研究，Hatger和 Brenner在文献[10]中结合LiDAR数据和已经存在的数据库信息提取道路的几何属性；在Rieger等人的论文[11]中研究了林区范围内由 LiDAR点云提取道路方法；为充分利用LiDAR数据信息，文献[12]和文献[13]引入了强度信息辅助道路的提取。

由于从航拍图像中提取道路时一些经验条件难以满足，如要求道路的灰度比背景亮，道路的灰度变换不大等，而从 LiDAR数据中提取道路对点的要求比较高，如点集密度高、需要强度信息等，因此，本文融合 LiDAR点云和配准的航空图像两种数据源来提取道路，降低了对单一数据源的依赖性。文章首先介绍了现有的基于动态规划的道路提取方法和代价函数的意义；然后对 LiDAR点云数据进行重新采样，并根据提取的道路特征对原有代价函数进行扩展；为精确配准航拍图像和 LiDAR数据，本文利用局部控制点对当前位置进行插值；最后通过试验对本文算法进行验证。

1 基于动态规划的道路提取及其改进

1.1 现有基于动态规划道路提取方法

1.1.1 在低分辨率航拍图像中的应用

利用动态规划从航拍图像中提取道路首先从较低分辨率的图像中[14]，将道路建立成线状的模型。道路模型中同时考虑道路的几何属性和物理属性（如道路为线状、灰度和宽度变化慢、方向变化平缓等）。由于道路可以用多边形来表达{ p1, p2,… ,pn}，其中 pi=( xi,yi)是多边形在图像上的第i个定点。则道路模型可以用下面的代价函数和约束不等式表示

其中 Ep1(pi,pi+1), Ep2(pi,pi+1)，和 Ep3(pi,pi+1)描述道路的各种几何和物理属性，每个表达式只依赖于连续邻接的两个点pi和pi+1；αi表示由点pi-1和pi构成的向量方向；β和γ为正常数；|ΔSi|为pi-1和pi之间的距离；T为用户定义的由控制点构成的临近两个向量的方向改变量的上限。

分析式(1)可以知道，代价函数为一系列Ei的加权和，每一个Ei依赖于多边形P的 3个连续的控制点(pi-1, pi,pi+1)，即每个点pi只和它的前一个pi-1、后一个点pi+1直接相关。这使得可以利用动态规划来该问题，通过一系列的决策过程来达到优化的目的。根据精度要求的不同，迭代的过程可以在原有的控制点之间添加一些额外的辅助控制点。

1.1.2 在中、高分辨率航拍图像中的应用

为使式(1)也能适合从高分辨率航空影像中提取道路，文献[6]研究了中等和较高分辨率航空影像中道路中心线的提取方法，将道路的边缘信息和宽度信息融入到式(1)得到了新的代价函数如下

1.2 代价函数的改进

在式(3)中虽然融入了航空图像中道路的各种属性，但是很多条件是基于经验，当条件改变的时候，该方法很难保证道路提取的正确性，如Ep中假定路面的灰度高于两侧的灰度值[14]，路

1面的灰度值变化缓慢，这些条件在大多数情况下是成立的，但是不能绝对保证（如斑马线处灰度值变化剧烈等）。为提高算法的鲁棒性，本文中引入了另外一个数据源——LiDAR点云，从而可以为模型式(3)添加更多的路面几何信息，如路面的边缘、高度等。

1.2.1 LiDAR数据的重采样和特征提取

为使LiDAR数据能够与航空图像结合使用，并减少对数据密度的依赖性，本文对 LiDAR点云进行重新采样。重采样的方法就是，按LiDAR点云的X、Y范围进行等网格划分，每个网格对应像素的灰度值正比于网格内的点的平均高度。由于 LiDAR点云分布是杂乱无章、密度不均的（如图1所示），所以生成的高度图包含空洞[12]，空洞处像素用离最近的像素灰度值代替。至于网格的大小可以根据实际的点云密度来设定。该阶段生成的高度图由于灰度对应 LiDAR点集的高度信息，为后续处理和叙述的方便，记该高度图为Image1（如图2所示），并用边缘检测方法（如Canny方法）生成边缘图像Image2。因为路面是平滑的，检测出的边缘不会出现在路面上，而道路与两旁的建筑物以及立交桥与两旁的地面有明显的高度差，因此在道路边缘处会检测到边缘点的存在（如图3所示）。

图1 城市LiDAR点云数据

图2 高度图像

图3 边缘图像

图4 边缘距离图像

为确定道路中心线的精确位置，根据边缘检测图像Image2生成边缘距离图像Image3，其不仅在求取道路中心线中用到，在最后求取道路宽度时也要使用该图像中的信息。Image3生成方法为，对于 Image2中任一非边缘点P，求取其最近的边缘点E1，若E1有关于P对称的边缘点E2，则将P和E1的距离作为像素P点的灰度值，如图4所示。

1.2.2 LiDAR数据道路特征

根据图像Image1, Image2和Image3的生成过程和道路本身固有的属性，可以得到如下有关道路特征的描述：

（1）小段范围内道路高度变化小，从而对应Image1中像素的灰度值变化小，则有

其中 f(s)为道路曲线的表达式；s为道路曲线的弧长；Δsi为取定的一段道路；G可分别表示灰度图像Image1和航拍图像 Image4的灰度值；Gm( Δ si)为对应图像中在道路段Δsi上的平均灰度值，即

（2）路面是平滑的，在边缘图像 Image2中道路曲线一般不会横跨边缘点，也即 Image2中的边缘点对代价函数E的贡献应该最小，为

其中 G表示图像Image2对应图像灰度值。

（3）提取的道路应离道路的中心线很近，则边缘距离图像中 Image3中每点的灰度值对代价函数的影响为

其中 G表示图像Image3对应图像灰度值。

（4）道路呈现带状形态，在短距离内不会有太大的宽度变化，基于此得出道路宽度变化对代价函数的影响

其中 G表示图像Image3对应图像灰度值。

1.2.3 代价函数的扩充

综合航空图像和 LiDAR数据的信息，可以从式(3)～式(7)中得出最终的道路模型的代价函数

其中 Ep5(pi,pi+1)=µ1E1+µ2E2-µ3E3+µ4E4，

式(2)、式(8)共同组成了本文道路识别的动态规划半自动提取模型。

2 航拍图像与LiDAR数据配准

由于距离较远和影像获取环境的不稳定等因素会使获取的图像有一定的畸变和倾斜，影响道路的提取效果和精度。因此，在结合航空图像和 LiDAR点云提取道路之前需要对两者进行配准。配准过程需要选定一些控制点作为配准依据，所提供的控制点个数和分布情况影响配准结果。配准的每一步都使用全部的控制点不仅计算量很大，而且当控制点离当前像素点较远时反而会降低配准的精度。

本文利用基于局部插值的思想，首先对控制点进行构造Delaunay三角网，然后对每个三角形内的像素只使用该三角形的顶点进行配准[15]，既减少了计算量，也能保证配准的精确性。如图5和图6分别为配准前的航拍图像和由LiDAR数据生成的高度图，以及根据选取的控制点所构建的三角网，图7为与图6高度图配准的航拍图像。

图5 配准前的航拍图像

图6 LiDAR高度图

图7 配准后的航拍图像

3 试验结果与分析

本文算法是半自动提取方法，首先由用户在道路附近选定一些控制点，之后的工作就由计算机来自动完成。它会自动算出道路代价函数的最大值，并根据列表保存的中间步骤信息，逆向求出使代价函数达到最大时的道路中心线位置。此外，通过道路中心线的位置和边缘距离图像Image3，算出道路中心线上任一位置的道路宽度；根据道路中心线的位置和高度图 Image1的生成过程计算道路的高度。

所使用的试验数据来源于在美国新奥尔良市区的LiDAR数据。图2～图4为LiDAR数据信息，图7为该区域的配准航拍图像，图8中为用户选取的控制点位置，图9显示所提取的道路位置和宽度信息，图10则为道路重建后的三维模型。从提取过程来看，用户提供的控制点甚至不需要在道路上，该算法仍然能够取得很好的效果。

图8 控制点位置

图9 提取的道路

图10 道路重建后

4 结束语

本文首先总结了动态规划方法在道路提取过程中的发展，其最先应用于较低分辨率的航拍图像中，将道路抽象为一条很细的线状，为了将该方法应用于中、高分辨率的航拍图像中，研究人员引入了道路的宽度信息，从而能够提取航拍图像中的道路中心线。

为了进一步提高算法的鲁棒性，本文融合航拍图像和LiDAR点云两种数据源，对LiDAR点云数据进行重新采样，分别生成对应的高度图、边缘检测图像和边缘距离图像；结合生成的三幅图像和对应的航拍图像提取道路的特征并用于改进后的动态规划算法；最后通过试验验证了本文方法的可行性。

[1]Ton J, Jain A K, Enslin W R, et al. Automatic road identification and labeling in Landsat 4 TM images [J].Photogrammetric Engineering & Remote Sensing,1989, 43(2): 257-276.

[2]Wang F, Newkirk R. A knowledge-based system for highway network extraction [J]. IEEE Transactions on Geoscience and Remote Sensing, 1988, 26(5):525-531.

[3]Barzohar M, Cooper D B. Automatic finding of main roads in aerial images by using geometric-stochastic models and estimation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996,18(7): 707-721.

[4]杨 云, 朱长青, 张 德. 高分辨率遥感影像上道路中心线的半自动提取[J]. 计算机辅助设计与图形学学报, 2007, 19(6): 781-785.

[5]German D, Jedynak B. An active testing model for tracking roads in satellite images [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, 18(1): 1-14.

[6]Pos A, Vale G. Dynamic programming approach for semi-automated road extraction from medium and high-resolution images [J]. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2003, 34(8): 87-91.

[7]Armin Gruen, Li Haihong. Semi-automatic linear feature extraction by dynamic programming and LSB-snakes [J]. Photogrammetric Engineering and Romote Sensing, 1997, 63(8): 985-995.

[8]Shackelford A K, Davis C H. Fully automated road network extraction from high-resolution satellite multispectral imagery [C]//Proceedings of the IEEE International Geoscience and Remote Sensing Symposium, 2003: 461-463.

[9]Zhu C, Shi W, Pesaresi M, et al. The recognition of road network from high-resolution satellite remotely sensed data using image morphological characteristics [J].International Journal of Remote Sensing, 2005, 26(24):5493-5508.

[10]Hatger C, Brenner C. Extraction of road geometry parameters from laser scanning and existing databases[C]//International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. XXXIV, Part 3/W13,2003.

[11]Rieger W, Kerschner M, Reiter T, et al. Roads and buildings from laser scanner data within a forest enterprise [C]//IAPRS, ISPRS Workshop, Vol. 32,La Jolla, California, 1999: 185-191.

[12]王 涛, 杨建思, 廖明生. 从机载激光扫描数据中提取道路[J]. 测绘信息与工程, 2006, 31(5): 10-11.

[13]Simon Clode, Peter Kootsookos, Franz Rottensteiner.The automatic extraction of roads from lidar data [C]//International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, XXXV-B3,2004: 231-236.

[14]Armin Gruen, Li Haihong. Road extraction from aerial and satellite images by dynamic programming [J].JSPRS Journal of Photogrammetry and Remote Sensing, 1995, 50(4): 11-20.

[15]罗月童, 朱晓强, 刘晓平. 基于三点的航拍图像倾斜校正方法及其应用[C]//中国仪器仪表学会第九届青年学术会议论文集, 2007: 590-593.