楊 威，萬(wàn)幼川，何培培

（1.武漢大學(xué) 遙感信息工程學(xué)院，湖北 武漢 430079）

基于機(jī)載LiDAR數(shù)據(jù)的城區(qū)道路中心線提取

楊 威1，萬(wàn)幼川1，何培培1

（1.武漢大學(xué) 遙感信息工程學(xué)院，湖北 武漢 430079）

提出一種基于離散點(diǎn)的道路中心線提取方法。在利用高程、強(qiáng)度和幾何形狀等多特征逐步約束提取出條帶道路點(diǎn)的基礎(chǔ)上，采用迭代Meanshift算法將條帶道路聚集成線狀點(diǎn)集，并通過(guò)分段Hough變換檢測(cè)出矢量道路中線。實(shí)驗(yàn)表明，該方法克服了傳統(tǒng)中心線提取方法中的精度損失，提高了準(zhǔn)確度。

機(jī)載LiDAR；道路中心線；迭代Meanshift；分段Hough變換

從機(jī)載LiDAR點(diǎn)云數(shù)據(jù)中提取道路可以分為2個(gè)過(guò)程：分類和矢量化[1]。分類即從原始點(diǎn)中分割出道路點(diǎn)；矢量化即從條帶狀的道路點(diǎn)中提取出矢量的道路信息，包括道路中心線、道路寬度等。其中，道路中心線的提取是矢量化過(guò)程中最為重要的一環(huán)，國(guó)內(nèi)外眾多學(xué)者對(duì)此進(jìn)行了研究。Clode等[1]首先將道路點(diǎn)轉(zhuǎn)化為二值影像，然后采用PCD（phase coded disk）方法提取中心線；彭檢貴等[2]引入a-shapes算法從道路條帶中提取出輪廓線，然后將輪廓線包圍的區(qū)域柵格化，采用數(shù)學(xué)形態(tài)學(xué)細(xì)化方法提取出道路中線；徐景中等[3]將道路點(diǎn)生成不同尺度的影像并分別細(xì)化，采用多尺度追蹤方式提取中心線；Hu等[4]和Couloigner等[5]分別采用Hough和Radon變換從生成的影像中提取道路中心線。上述方法雖然取得了相應(yīng)效果，但還存在以下問題：①將離散道路點(diǎn)轉(zhuǎn)化為柵格影像，丟失了原始信息，降低了數(shù)據(jù)精度；②道路中心線的位置受到道路兩側(cè)邊緣的干擾，產(chǎn)生偏移；③提取出的道路矢量無(wú)法滿足道路的光滑性要求（如PCD、細(xì)化等），且部分方法所能檢測(cè)出的道路線型有限（如Hough、Radon變換等）。鑒于此，本文提出一種基于離散點(diǎn)云的道路中心線提取方法。

1 基于離散點(diǎn)的道路中線提取

1.1 基于Meanshift的中心線聚集

Meanshift算法[6]的基本思想是：對(duì)于空間中的樣本點(diǎn)，任選一點(diǎn)X作為當(dāng)前點(diǎn)，計(jì)算該點(diǎn)的鄰域均值Mx并將其移動(dòng)至均值處，以此作為新的起點(diǎn)，重新計(jì)算均值，直至不再移動(dòng)。漂移均值計(jì)算公式如下：

式中，N（x）表示落入當(dāng)前點(diǎn)x一定鄰域內(nèi)的樣本點(diǎn)集；k為該鄰域中樣本點(diǎn)總數(shù)。

本文首先采用多特征逐步約束方法從原始點(diǎn)中提取出初始的道路條帶，主要步驟為高程約束、強(qiáng)度約束和幾何形狀約束等，具體過(guò)程見文獻(xiàn)[2]。在已提取出的初始條帶道路中，邊緣點(diǎn)具有較小的點(diǎn)密度，越靠近中心，點(diǎn)密度越大。根據(jù)這一性質(zhì)，可利用Meanshift算法從條帶道路中探測(cè)出道路中心。如圖1所示，道路邊緣點(diǎn)經(jīng)過(guò)Meanshift后，向著道路中心聚集，從而使原本為條帶分布的道路點(diǎn)“細(xì)化”成線狀，形成初始道路中心線。

圖1 Meanshift道路中點(diǎn)聚集原理示意圖

基于Meanshift的道路中心線聚集的關(guān)鍵在于平面窗口尺寸（即鄰域）的確定。窗口過(guò)小，聚集的中心線仍為條帶狀；窗口過(guò)大，由于道路點(diǎn)云分布不均勻，會(huì)使漂移陷入局部最優(yōu)，即部分道路中心點(diǎn)向著附近其他具有更大點(diǎn)密度的中心點(diǎn)漂移，使得聚集的道路中心線發(fā)生斷裂。為此，本文首先利用點(diǎn)密度探測(cè)粗略窗口大小[7]，進(jìn)行初次Meanshift，然后采用統(tǒng)一平面窗口進(jìn)行二次Meanshift。具體步驟如下：

1）設(shè)置區(qū)域道路最大寬度Wthmax、最小寬度Wthmin和寬度增量Δ Wth；

2）以最小寬度作為初始窗口計(jì)算當(dāng)前點(diǎn)的點(diǎn)密度，如果點(diǎn)密度大于給定的密度閾值Tden，將窗口尺寸增加一個(gè)寬度增量，重新計(jì)算點(diǎn)密度，直到點(diǎn)密度小于閾值或者窗口尺寸大于道路最大寬度；

3）將第2）步中確定的窗口尺寸作為當(dāng)前點(diǎn)的平面窗口進(jìn)行Meanshift迭代漂移；

4）對(duì)道路條帶所有點(diǎn)，重復(fù)2）～3）；

5）以道路最小寬度作為統(tǒng)一的平面窗口對(duì)所有點(diǎn)進(jìn)行二次Meanshift，得到最終的道路中心點(diǎn)集。

圖2 不同寬度道路迭代Meanshift結(jié)果

1.2 分段Hough變換檢測(cè)中心線

通常，如果道路點(diǎn)分布均勻且平面窗口選擇合適，道路邊緣點(diǎn)僅會(huì)產(chǎn)生垂直于道路走向的“縱向漂移”。但是，由于道路寬度多變、道路點(diǎn)分布并不均勻，導(dǎo)致道路點(diǎn)產(chǎn)生沿著道路走向的“橫向漂移”，使得聚集的中心線發(fā)生斷裂，這在道路交叉口處尤為明顯（如圖3），而這也為分段Hough變換提供了基礎(chǔ)。

圖3 道路交叉口斷裂示意圖

選擇圓弧作為檢測(cè)的形狀基元，對(duì)道路中心點(diǎn)集分段進(jìn)行Hough變換。該過(guò)程通過(guò)以下2個(gè)步驟完成：

1）分段。輸入任意一點(diǎn)，以該點(diǎn)為種子點(diǎn)進(jìn)行區(qū)域增長(zhǎng)，將總點(diǎn)數(shù)大于閾值Tnum的連接體作為待檢測(cè)道路點(diǎn)集。搜索該點(diǎn)集中距離最遠(yuǎn)的兩點(diǎn)，將其作為端點(diǎn)連接成直線，計(jì)算其他點(diǎn)到該直線的最遠(yuǎn)距離Dmax，若Dmax〉 Tdis，則將該連接體在距離最遠(yuǎn)處打斷；重復(fù)該過(guò)程，直到不再有新的連接體產(chǎn)生。從圖4中看出，一些具有復(fù)雜線型的道路經(jīng)過(guò)此過(guò)程，被分割成曲率單一的弧線。

圖4 連接體分段過(guò)程

2）Hough變換。圓的參數(shù)方程為：

其中，（a，b）為圓的圓心；r為圓的半徑。通常，待檢測(cè)圓弧具有3個(gè)未知參數(shù)，Hough變換的參數(shù)空間可以表示為（a，b，r）。假設(shè)已知圓弧上兩點(diǎn)，則待檢測(cè)圓弧的圓心位于兩已知點(diǎn)連線的中垂線上，故只需確定一個(gè)參數(shù)（即圓弧的半徑），即可確定圓的參數(shù)方程。因此，為減小Hough變換的參數(shù)空間，提高算法效率，對(duì)于分段后的連接體，將其2個(gè)端點(diǎn)作為圓弧上的已知點(diǎn)進(jìn)行Hough變換，變換的參數(shù)空間為半徑r。

1.3 道路編組和連接

經(jīng)過(guò)以上步驟提取出的道路中心線為彼此斷開的圓弧段基元，需進(jìn)行編組并連接。分層感知編組方法[8]通過(guò)分析道路基元的連續(xù)性、鄰接性和相似性，計(jì)算道路基元之間的連接概率矩陣，將具有最大連接概率的道路基元連接，重新計(jì)算概率矩陣并連接最大概率基元，直到最大連接概率小于閾值。利用該方法，對(duì)提取的圓弧道路基元進(jìn)行編組連接，從而形成完整的道路中心線網(wǎng)絡(luò)。

2 實(shí)驗(yàn)與分析

采用ISPRS提供的用于城市地物分類和建筑物重建的試驗(yàn)數(shù)據(jù)對(duì)算法進(jìn)行驗(yàn)證。數(shù)據(jù)采集地為德國(guó)斯圖加特的Vaihingen小鎮(zhèn)，LiDAR點(diǎn)云由Leica ALS50系統(tǒng)獲取，平均點(diǎn)密度為4 pts/m2，對(duì)應(yīng)DMC影像分辨率為8 cm。如圖5所示，該區(qū)域地物復(fù)雜，建筑物和樹木密集，且道路寬度和形狀多變，具有代表性。

圖5 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)過(guò)程中的主要參數(shù)設(shè)置如下：

1） 迭代Meanshift過(guò)程中的最大寬度設(shè)置為30 m，最小寬度設(shè)置為4 m，控制窗口尺寸的點(diǎn)密閾值設(shè)置為0.8 pts/m2；

2） 分段Hough變換檢測(cè)圓弧過(guò)程中連接體包含的最小點(diǎn)數(shù)設(shè)置為10，分段的距離閾值為5 m，圓弧半徑r的取值范圍設(shè)置為（1 m，10 000 m），步長(zhǎng)為1 m。

實(shí)驗(yàn)結(jié)果如圖6所示。其中，圖6a為多特征逐步約束提取的初始道路條帶；圖6b、c為進(jìn)行迭代Meanshift算法后所聚集的道路中心點(diǎn)集；圖6d為分段Hough變換檢測(cè)出的道路圓弧段；圖6e為經(jīng)過(guò)編組連接后疊加到對(duì)應(yīng)影像上的道路網(wǎng)；圖6f為將道路條帶轉(zhuǎn)化為柵格影像后，采用數(shù)學(xué)形態(tài)學(xué)細(xì)化方法得到的道路中心線；圖6g～i為黃色矩形框內(nèi)的初始道路條帶和兩種方法提取結(jié)果的放大顯示。

圖6 實(shí)驗(yàn)結(jié)果

為定量評(píng)價(jià)算法效果，以手動(dòng)提取的道路中心線作為參考，對(duì)提取的道路中心線進(jìn)行精度評(píng)定。各項(xiàng)指標(biāo)定義如下[9]：

其中，TP為匹配的道路長(zhǎng)度；FN為未提取的道路長(zhǎng)度；FP為誤提取的道路長(zhǎng)度。經(jīng)統(tǒng)計(jì)，TP=4 555.64 m、FN=654.38 m、FP=607.79 m，評(píng)定結(jié)果如表1所示。

表1 道路提取精度評(píng)定表/%

從結(jié)果可以看出，整個(gè)數(shù)據(jù)區(qū)域中，主要道路被完整提出，提取的道路完整度和準(zhǔn)確度均在85%以上，結(jié)果質(zhì)量達(dá)78.31%。圖6e顯示，使用該方法從不同寬度、不同線型的道路條帶中提取的中心線均具有較好的效果。圖6f為采用細(xì)化方法提取出的道路中心線，與圖6e對(duì)比可發(fā)現(xiàn)，細(xì)化方法提取的中心線在形態(tài)上表現(xiàn)真實(shí)道路的能力較弱，提取的中心線更容易受到道路邊緣的干擾而產(chǎn)生偏離，降低了準(zhǔn)確度。如圖6g～i所示，在道路交叉口處，細(xì)化方法的部分提取結(jié)果發(fā)生了明顯的偏離，而采用迭代Meanshift和分段Hough相結(jié)合的方法則能克服這一問題。但是，該方法在完整度上稍有不足，這是由于在迭代Meanshift聚集過(guò)程中，道路端點(diǎn)會(huì)發(fā)生“縱向漂移”，從而導(dǎo)致道路長(zhǎng)度縮短。整體來(lái)說(shuō)，本文方法提高了道路中線提取的準(zhǔn)確度，使結(jié)果質(zhì)量得到改善。

3 結(jié) 語(yǔ)

本文在多特征逐步約束提取道路條帶的基礎(chǔ)上，提出一種基于迭代Meanshift和分段Hough變換的道路中線提取方法。該方法具有以下優(yōu)點(diǎn)：①過(guò)程完全基于離散的道路點(diǎn)集，避免了傳統(tǒng)方法中內(nèi)插生成影像造成的精度損失；②對(duì)于不同寬度、不同線型的道路均具有較好的提取效果；③在保證完整度和準(zhǔn)確度的同時(shí)，提取的光滑道路中心線更加接近真實(shí)道路形態(tài)。同時(shí)也有一些不足：①該中心線提取方法的精度首先受制于條帶道路的提取精度，基于多特征約束提取出的條帶道路是否準(zhǔn)確對(duì)中心線提取結(jié)果有重要的影響；②迭代Meanshift聚集過(guò)程中窗口尺寸的選擇尚未自動(dòng)化，有待進(jìn)一步研究。

[1] Clode S, Rottensteiner F, Kootsookos P, et al. Detection and Vectorization of Roads from LiDAR Data[J]. American Society for Photogrammetry and Remote Sensing, 2007, 73(5): 517-535

[2] 彭檢貴, 馬洪超, 高廣, 等.利用機(jī)載LiDAR點(diǎn)云數(shù)據(jù)提取城區(qū)道路[J].測(cè)繪通報(bào),2012(9)：16-19

[3] 徐景中, 萬(wàn)幼川, 賴祖龍. 機(jī)載激光雷達(dá)數(shù)據(jù)中道路中線的多尺度提取方法[J].紅外與激光工程,2009, 38(6): 1 099-1 103

[4] Hu X, Tao C V, Hu Y. Automatic Road Extraction from Dense Urban Area by Integrated Processing of High ResolutionImagery and LiDAR Data[C]. ISPRS, Beijing, 2009

[5] Couloigner I, Zhang Q. Iterative and Localized Radon Transform for Road Centerline from Classified Imagery[C]. ICIAR, Montreal, 2007

[6] Fukunaga K, Hostetler L. The Estimation of the Gradient of a Density Function, with Applications in Pattern Recognition [J].IEEE Trans Information Theory, 1975, 21(1): 32-40

[7] Hu X, Li Y, Shan J, et al. Road Centerline Extraction in Complex Urban Scenes From LiDAR Data Based on Multiple Features [J]. IEEE Trans Geoscience and Remote Sensing, 2014, 52(11): 7 448-7 456

[8] Hu X, Tao C V. Automatic Extraction of Main Road Centerlines from High Resolution Satellite Imagery Using Hierarchical Grouping [J]. Photogrammetric Engineering and Remote Sensing, 2007, 73(9): 1 049-1 056

[9] Heipke C, Mayer H, Wiedemann C. Evaluation of Automatic Road Extraction [J]. International Archives of Photogrammetry and Remote Sensing, 1997,32:47-56

P237.9

B

1672-4623（2015）04-0075-03

10.3969/j.issn.1672-4623.2015.04.027

楊威，碩士，主要研究方向?yàn)闄C(jī)載激光點(diǎn)云數(shù)據(jù)處理。

2014-12-11。

項(xiàng)目來(lái)源：國(guó)家高技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目（2013AA122104-3）；博士點(diǎn)基金資助項(xiàng)目（20130141130003）。