王 果，崔希民，袁德寶，張 強(qiáng)，王立鴻

(1.中國(guó)礦業(yè)大學(xué)(北京)地球科學(xué)與測(cè)繪工程學(xué)院，北京100083;2.北京東方道邇信息技術(shù)有限責(zé)任公司，北京100080)

車載激光點(diǎn)云領(lǐng)域比較的道路邊線提取方法

王 果1，崔希民1，袁德寶1，張 強(qiáng)1，王立鴻2

(1.中國(guó)礦業(yè)大學(xué)(北京)地球科學(xué)與測(cè)繪工程學(xué)院，北京100083;2.北京東方道邇信息技術(shù)有限責(zé)任公司，北京100080)

對(duì)車載激光掃描獲取的高速公路信息進(jìn)行研究，提出直接利用三維激光點(diǎn)云數(shù)據(jù)的平面和高程信息，通過(guò)點(diǎn)云與其鄰域比較進(jìn)行道路邊線提取的方法。該方法提取不需要其他輔助數(shù)據(jù)，能直接從點(diǎn)云中自動(dòng)提取出道路邊線信息，對(duì)點(diǎn)云數(shù)據(jù)自動(dòng)提取具有一定借鑒意義。

激光掃描;點(diǎn)云;道路邊線;提取;VC++

一、引 言

三維空間信息的快速獲取及其自動(dòng)處理技術(shù)是地球空間信息科學(xué)和空間信息產(chǎn)業(yè)快速發(fā)展的前提。激光LiDAR技術(shù)作為一種新的空間數(shù)據(jù)采集手段，具有全天候、作業(yè)周期短、精度高等優(yōu)點(diǎn)，能快速獲取海量的高精度三維坐標(biāo)數(shù)據(jù)。最近10多年來(lái)，激光掃描測(cè)量系統(tǒng)作為快速、精確獲取地面三維數(shù)據(jù)的測(cè)繪工具已經(jīng)得到廣泛認(rèn)同。從1998年開始，激光測(cè)繪系統(tǒng)使用量以每年25%的速度增長(zhǎng)。加拿大Optech公司的ALTM、瑞士徠卡公司的ALSSO、德國(guó)IGI公司的LiteMapper、瑞典Topo-EyeAB公司的TopEye以及法國(guó)TopoSys公司的Falcon II等系統(tǒng)是當(dāng)前比較成熟的商業(yè)應(yīng)用系統(tǒng)。

按照激光掃描設(shè)備搭載的平臺(tái)，通常將激光掃描測(cè)量系統(tǒng)分為機(jī)載激光掃描測(cè)量系統(tǒng)(air-borne laser scanning system，ALSS;或airborne laser terrain mapper，ALTM)、地面掃描測(cè)量系統(tǒng)(ground-based laser scanning system，GLSS)和車載激光掃描測(cè)量系統(tǒng)(vehicle-borne laser scanning system，VLSS)。

經(jīng)過(guò)十幾年的發(fā)展，機(jī)載激光LiDAR技術(shù)已相對(duì)成熟，車載激光LiDAR系統(tǒng)硬件的開發(fā)和研究也有了較大的進(jìn)展，而對(duì)于激光掃描數(shù)據(jù)的處理卻相對(duì)滯后，到目前為止，尚沒(méi)有距離點(diǎn)云分割成熟可行的方法［1］?，F(xiàn)有文獻(xiàn)中，文獻(xiàn)［1］提出基于投影點(diǎn)密度的車載激光掃描數(shù)據(jù)處理方法;文獻(xiàn)［2］提出一種格網(wǎng)化的車載激光點(diǎn)云提取方法;文獻(xiàn)［3］將所有數(shù)據(jù)點(diǎn)投影到格網(wǎng)上，根據(jù)每個(gè)格網(wǎng)單元投影前后高度最大值對(duì)格網(wǎng)數(shù)據(jù)進(jìn)行分類，提取出建筑物特征;文獻(xiàn)［4］介紹了一種基于建筑物幾何特征，對(duì)建筑物的平面輪廓信息進(jìn)行提取，并對(duì)其三維建模和可視化的方法;文獻(xiàn)［5］研究了基于車載激光測(cè)距的建筑物立面信息提取;文獻(xiàn)［6］借鑒了投影點(diǎn)密度的思想，提出了一套從車載激光掃描數(shù)據(jù)中提取和重建窗戶的方案;文獻(xiàn)［7］利用掃描線上的公路三維信息進(jìn)行提取，取得了一定效果。上述文獻(xiàn)，大都是針對(duì)建筑物的相關(guān)信息進(jìn)行提取，很少有關(guān)于道路方面提取的文獻(xiàn)。文獻(xiàn)［8］中指出，如果按照機(jī)載激光的方法利用點(diǎn)云數(shù)據(jù)生成DSM，然后從DSM進(jìn)行相關(guān)信息提取，就會(huì)丟失一些信息，從而導(dǎo)致提取精度降低。本文主要通過(guò)研究利用高速公路自身的形態(tài)特征，并利用點(diǎn)云與其鄰域比較的思想，從車載激光點(diǎn)云數(shù)據(jù)中提取道路邊線信息的方法。

二、鄰域比較原理

1.基于k-d樹的點(diǎn)云鄰域

1975年由J.L.Bentley提出的k-d樹，是k(k≥2)維二叉檢索樹(BST)，它主要用于所有索引多屬性的數(shù)據(jù)或多維數(shù)據(jù)點(diǎn)。與二叉檢索樹有所不同，k維空間的點(diǎn)是通過(guò)k-d樹的結(jié)點(diǎn)表示，并且樹的每一層都會(huì)根據(jù)該層的分辨器(discriminator)做出相應(yīng)的分枝決策。k-d樹的第i層分辨器定義如下：i對(duì)k取余，即imodk，其中樹的根結(jié)點(diǎn)所在層為0，根結(jié)點(diǎn)的孩子所在層為1;其他同理，依次遞增［9］。

點(diǎn)云數(shù)據(jù)為散亂數(shù)據(jù)點(diǎn)，即對(duì)于每個(gè)數(shù)據(jù)點(diǎn)只包含點(diǎn)的三維坐標(biāo)值，而其對(duì)應(yīng)的幾何拓?fù)湫畔⒉](méi)有給出。因此，需要根據(jù)空間點(diǎn)的鄰域關(guān)系估算點(diǎn)對(duì)應(yīng)的拓?fù)潢P(guān)系，從而估算點(diǎn)對(duì)應(yīng)的幾何信息(如數(shù)據(jù)點(diǎn)單位法向量、微切平面、曲率大小和鄰接關(guān)系)。二維或三維散亂點(diǎn)云數(shù)據(jù)中，某點(diǎn)Q的k個(gè)最臨近鄰域是指在數(shù)據(jù)集S={Pi(i=1，2，3，…，n)}中找到k個(gè)與該點(diǎn)歐式距離最近的點(diǎn)的集合。若Λ是一排列，Λ滿足

則某點(diǎn)Q的k鄰域?yàn)?/p>

k-d樹是二叉檢索樹的擴(kuò)展，k表示空間維數(shù)，故又稱k維搜索樹，其示意圖如圖1所示。在每個(gè)內(nèi)部節(jié)點(diǎn)中，用一個(gè)k-1維與坐標(biāo)軸平行的超平面(如二維空間中的線)將節(jié)點(diǎn)所表示的k維空間分成兩個(gè)部分，存儲(chǔ)在子樹中的點(diǎn)大約一半落入一側(cè)，而另一半落入另一側(cè)。當(dāng)一個(gè)節(jié)點(diǎn)中的點(diǎn)數(shù)少于給定的最大點(diǎn)數(shù)時(shí)，劃分結(jié)束。這些超平面在k個(gè)可能的方向上交替出現(xiàn)，每個(gè)超平面中至少包括一個(gè)數(shù)據(jù)點(diǎn)，這就保證了k-d樹不存在“無(wú)點(diǎn)空間”的浪費(fèi)。當(dāng)有n個(gè)點(diǎn)時(shí)，構(gòu)造k-d樹的時(shí)間復(fù)雜度為0［9］。

圖1 點(diǎn)云的k-近域搜索

與格網(wǎng)數(shù)據(jù)有所不同，空間散亂的三維激光點(diǎn)云數(shù)據(jù)無(wú)附加的拓?fù)湫畔?。為了獲取激光腳點(diǎn)的拓?fù)湫畔⑿枰x散亂腳點(diǎn)的局部鄰域，常用的鄰域方式有ε-鄰域和k-鄰域。所謂ε-鄰域，就是以當(dāng)前查詢的激光腳點(diǎn)為中心，半徑為ε的球體內(nèi)所有激光腳點(diǎn)定義為該采樣腳點(diǎn)的鄰域腳點(diǎn)，該方式比較適合于比較規(guī)則的采樣表面;而對(duì)于k-鄰域來(lái)說(shuō)，是指離散的空間點(diǎn)云中與查詢點(diǎn)歐氏距離最近的k個(gè)點(diǎn)所組成的點(diǎn)的集合，這種方式比較適合于非規(guī)則采樣的點(diǎn)云數(shù)據(jù)。根據(jù)激光掃描數(shù)據(jù)的特點(diǎn)，選取k-鄰域進(jìn)行相應(yīng)的道路邊線提取。

2.鄰域比較方法

從車載激光掃描的距離圖像(如圖2所示)可看出，反射自高速公路地面的數(shù)據(jù)點(diǎn)信息基本排列在水平面上，反射自樹和桿狀地物的數(shù)據(jù)點(diǎn)成離散分布狀態(tài)。同時(shí)，反射自地面上地物的數(shù)據(jù)點(diǎn)在高程方面比反射自地面上的大，而且，高速公路路面具有比較平坦的特點(diǎn)。如果按照4%的坡度計(jì)算，車載激光點(diǎn)云點(diǎn)間隔按2 cm計(jì)算，相鄰點(diǎn)間的高差為0.02×4%=0.000 8 m，即0.8 mm，所以路面點(diǎn)之間的高程差別很小。基于高速公路激光點(diǎn)云數(shù)據(jù)的以上特性，可利用激光腳點(diǎn)與周圍鄰域點(diǎn)的高程進(jìn)行比較，從而提取所關(guān)注的信息。

圖2 車載激光掃描高速公路距離圖像

三、試驗(yàn)過(guò)程及結(jié)果

1.試驗(yàn)過(guò)程

選取某高速公路的車載激光點(diǎn)云數(shù)據(jù)作為試驗(yàn)數(shù)據(jù)，該數(shù)據(jù)為一段長(zhǎng)5 km的高速公路數(shù)據(jù)，通過(guò)分塊處理，將5 km數(shù)據(jù)25塊，每塊數(shù)據(jù)長(zhǎng)度為200 m，分別對(duì)25塊數(shù)據(jù)進(jìn)行處理。對(duì)于路面數(shù)據(jù)，如果k-鄰域中有k/2個(gè)點(diǎn)高程值與當(dāng)前查詢點(diǎn)Q的高程值之差小于2 cm，則把該查詢點(diǎn)的分類信息寫入las文件;對(duì)于路沿石和其他非地面數(shù)據(jù)，若Q為當(dāng)前查詢點(diǎn)，A為Q的其中一個(gè)最臨近鄰域，B為Q正上方或者正下方和A有相同高程值的點(diǎn)，對(duì)于Q周圍的k鄰近，記錄向量QA和向量QB的夾角在某個(gè)閾值范圍內(nèi)的鄰近點(diǎn)個(gè)數(shù)m，如果m大于一定的條件，則將非地面信息的分類，寫入las文件。試驗(yàn)發(fā)現(xiàn)，對(duì)于非地面點(diǎn)如果將k設(shè)為大于20，可明顯將路沿石分離出來(lái)。

通過(guò)las文件，將default類的點(diǎn)讀入，對(duì)于default類的某點(diǎn)Q，如果Q的k-鄰域中既有路面點(diǎn)又有非路面點(diǎn)，而且這k-鄰域中的路面點(diǎn)和查詢點(diǎn)的距離小于0.02 m，則將該查詢點(diǎn)的類信息寫入las文件。遍歷default類的所有點(diǎn)即可將路面和路沿石之間的點(diǎn)成功分離。

遍歷las文件中的路面和路沿石之間點(diǎn)，如果某點(diǎn)k-鄰域中既有路面和路沿石之間點(diǎn)又有路面點(diǎn)，而且這k-領(lǐng)域中的路面點(diǎn)和查詢點(diǎn)的距離小于0.01 m，則將該查詢點(diǎn)的類信息寫入las文件。通過(guò)這種方法，可將道路邊線點(diǎn)成功分類。

上述分類方法通過(guò)VC++環(huán)境下編寫代碼予以實(shí)現(xiàn)，整個(gè)道路邊線試驗(yàn)提取流程如圖3所示。

圖3 試驗(yàn)流程

2.試驗(yàn)結(jié)果

對(duì)于每一塊數(shù)據(jù)，按照設(shè)計(jì)的分類算法，首先分離出地面點(diǎn)和路沿石點(diǎn)，將其類信息分別寫為20和21，對(duì)于未分類點(diǎn)，即類信息為1的點(diǎn)，建立k-d樹，通過(guò)設(shè)計(jì)的算法分離出路面和路沿石之間的點(diǎn)，將其類信息寫為30;其次遍歷類為30的點(diǎn)，建立k-d樹，分類出道路邊線點(diǎn)，將其類信息寫為31;然后將類為31的所有點(diǎn)的坐標(biāo)信息，寫入文本文件;最后將TXT文本導(dǎo)入MicroStation實(shí)現(xiàn)離散點(diǎn)自動(dòng)連線，結(jié)果如圖4所示。

圖4 道路邊線提取效果

四、結(jié)束語(yǔ)

根據(jù)高速公路道路邊線自身的特點(diǎn)及公路在車載激光掃描據(jù)表達(dá)中的特點(diǎn)，運(yùn)用鄰域比較的方法，對(duì)原始未分類的點(diǎn)云不斷進(jìn)行鄰域比較，并按照設(shè)計(jì)的算法利用VC++9.0編寫代碼，不斷分類出高速公路道路邊線點(diǎn)，然后在MicroStation下將濾出的離散點(diǎn)自動(dòng)連線，實(shí)現(xiàn)基于車載激光點(diǎn)云道路邊線的提取。該方法不僅可以減少內(nèi)業(yè)大量的人力勞動(dòng)，而且基于點(diǎn)云直接進(jìn)行分類，不會(huì)出現(xiàn)人工提取過(guò)程中“飛點(diǎn)”的情況，自動(dòng)化程度高，可減少人工提取時(shí)出錯(cuò)的幾率。試驗(yàn)結(jié)果表明，其能相對(duì)快速地從車載激光點(diǎn)云中提取出高速公路道路邊線以及所關(guān)心的信息。

［1］ 史文中，李必軍，李清泉.基于投影點(diǎn)密度的車載激光掃描距離圖像分割方法［J］.測(cè)繪學(xué)報(bào)，2005，34(2)：95-100.

［2］ 盧秀山，黃磊.基于激光掃描數(shù)據(jù)的建筑物信息格網(wǎng)化提取方法［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2007，32(10)：852-855.

［3］ 吳芬芳，李清泉，熊卿.基于車載激光掃描數(shù)據(jù)的目標(biāo)分類方法［J］.測(cè)繪科學(xué)，2007，32(4)：75-77.

［4］ 李必軍，方志祥，任娟.從激光掃描數(shù)據(jù)中進(jìn)行建筑物特征提取研究［J］武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2003，28(1)：65-70.

［5］ 王健，靳奉祥，呂海彥，等.基于車載激光測(cè)距的建筑物立面信息提取［J］.山東科技大學(xué)：自然科學(xué)版，2003，23(4)：8-11.

［6］ 楊洋，馬一薇，楊靖宇.基于車載激光掃描技術(shù)的窗戶提取與重建技術(shù)［J］.海洋測(cè)繪，2010，30(3)：48-51.

［7］ 李永強(qiáng)，盛業(yè)華，劉會(huì)云，等.基于車載激光掃描的公路三維信息提取［J］.測(cè)繪科學(xué)，2008，33(4)：23-25.

［8］ ASELSSON P.Processing of Laser Scanner Data：Algorithm and Applications［J］.ISRPS Journal of Photogrametry and Remote Sensing，1999，54：138-147.

［9］ 郭薇，郭菁，胡志勇.空間數(shù)據(jù)庫(kù)索引技術(shù)［M］.上海：上海交通大學(xué)出版社，2006.

［10］ SITHOLE G，VOSSELMAN G.Experimental Comparison ofFilterAlgorithmsforBare-Earth Extraction from Airborne Laser Scanning Point Clouds［J］.ISPRS Journal ofPhotogrammetry and Remote Sensing，2004，59：85-101.

Method of Extraction of Highway Sideline from Point Cloud of Mobile Scanning System

WANG Guo，CUI Ximin，YUAN Debao，ZHANG Qiang，WANG Lihong

0494-0911(2012)09-0055-03

P234.5

B

2011-09-14

王 果(1986—)，男，河南南陽(yáng)人，博士生，主要研究方向?yàn)闇y(cè)繪新技術(shù)及數(shù)據(jù)處理。