易 航,李 浩,楊 彪,韋立新,蔣建平
(1.河海大學(xué) 地球工程與工程學(xué)院,江蘇 南京 210098;2.長(zhǎng)江下游水文水資源勘測(cè)局,江蘇 南京 210010)
基于聚類(lèi)與重構(gòu)的河流區(qū)域?yàn)V波方法
易 航1,李 浩1,楊 彪1,韋立新2,蔣建平2
(1.河海大學(xué) 地球工程與工程學(xué)院,江蘇 南京 210098;2.長(zhǎng)江下游水文水資源勘測(cè)局,江蘇 南京 210010)
研究河流區(qū)域水體點(diǎn)云的分布特征與相互關(guān)系,提出基于特征聚類(lèi)的點(diǎn)云分割與基于LLE算法的鄰近點(diǎn)點(diǎn)云重構(gòu)濾波方法。通過(guò)統(tǒng)計(jì)網(wǎng)格內(nèi)點(diǎn)云的特征參數(shù),進(jìn)行點(diǎn)云分割并濾除水面點(diǎn),再利用LLE算法的鄰近點(diǎn)構(gòu)建約束條件進(jìn)行點(diǎn)云重構(gòu),分離近岸船只點(diǎn)云與岸堤點(diǎn)云的邊緣,最后利用船只點(diǎn)云的獨(dú)立性進(jìn)行二值連通域標(biāo)記與濾除,從而實(shí)現(xiàn)河流區(qū)域的點(diǎn)云濾波。實(shí)驗(yàn)表明,該方法能夠?yàn)V除90%以上的水面點(diǎn)云與大部分船只點(diǎn)云。
水體點(diǎn)云;特征參數(shù);聚類(lèi)分析;點(diǎn)云重構(gòu)
機(jī)載激光雷達(dá)(LiDAR)技術(shù)是目前應(yīng)用最廣泛的高分辨率測(cè)量技術(shù)之一。LiDAR系統(tǒng)獲取到地面的三維點(diǎn)云信息,并記錄多次反射的強(qiáng)度信息。由于陸地測(cè)量的機(jī)載LiDAR工作波長(zhǎng)一般為1 040~1 060 nm[1],位于水體的強(qiáng)吸收帶,所以理想條件下不反射激光脈沖。但在實(shí)際中,河流區(qū)域的船只等物體會(huì)產(chǎn)生反射信號(hào)形成船只點(diǎn)云,且受到無(wú)人機(jī)飛行路線(xiàn)與水面反射的影響,在特殊情況下水面也會(huì)產(chǎn)生反射信號(hào),形成水面點(diǎn)云。水面點(diǎn)云與船只點(diǎn)云都為非地面點(diǎn),且相互嵌套,分布較為復(fù)雜。河流區(qū)域點(diǎn)云濾波的目的就是將河流區(qū)域非地面點(diǎn)濾除[2-4]。
河流區(qū)域非地面點(diǎn)濾除在水體邊緣提取中較為常見(jiàn)[5,6]。本文通過(guò)對(duì)河流區(qū)域的點(diǎn)云分布特性進(jìn)行研究,利用水面點(diǎn)云均勻分布與船只點(diǎn)云獨(dú)立性明顯的特點(diǎn),參考楊曉云[7]等所提出描述數(shù)據(jù)分布形態(tài)的統(tǒng)計(jì)量偏度與峰值概念,提出了基于特征聚類(lèi)的點(diǎn)云分割和基于LLE算法的鄰近點(diǎn)點(diǎn)云重構(gòu)的濾波方法。該方法能從河流區(qū)域點(diǎn)云數(shù)據(jù)中有效剔除非地面點(diǎn)云。
點(diǎn)云分割是利用目標(biāo)區(qū)域點(diǎn)云的空間、幾何和紋理等特征進(jìn)行劃分,使得處于同一區(qū)域內(nèi)的點(diǎn)云具有相似的分布特征。本文利用點(diǎn)云高程分布的偏度、峰度與均值進(jìn)行特征聚類(lèi),實(shí)現(xiàn)點(diǎn)云分割。
偏度是統(tǒng)計(jì)數(shù)據(jù)分布偏斜方向和程度的度量。偏度為0時(shí),表示其數(shù)據(jù)點(diǎn)云分布與正態(tài)分布的偏離程度相同,偏度的計(jì)算公式如下:
式中,N為格網(wǎng)內(nèi)的點(diǎn)數(shù);si為格網(wǎng)內(nèi)點(diǎn)的高程;i∈(1,2,3…N);σ為格網(wǎng)內(nèi)點(diǎn)的標(biāo)準(zhǔn)差,u為高程均值。標(biāo)準(zhǔn)差和算術(shù)平均值的計(jì)算公式如下:
峰度是描述數(shù)據(jù)點(diǎn)云高程分布形態(tài)陡緩程度的量度,峰度為0表示總體數(shù)據(jù)分布與正態(tài)分布的陡緩程度相同。峰度的計(jì)算如式如下:
由于水面點(diǎn)高程變化不大,而非水面點(diǎn)大多變化明顯,因此利用偏度、峰度與高程均值對(duì)格網(wǎng)內(nèi)的點(diǎn)云進(jìn)行特征聚類(lèi),可有效分割出水面點(diǎn)。
局部線(xiàn)性嵌入(locally linear embedding,LLE)算法是Roweis和Saul于2000年提出的一種非線(xiàn)性降維方法,基于高維空間中相鄰或相關(guān)的點(diǎn)映射到低維空間中也同樣地相鄰或相關(guān)的幾何思想[8]。LLE算法流程可以歸結(jié)為以下幾步:
1)計(jì)算出每個(gè)樣本點(diǎn)的k個(gè)鄰近點(diǎn),把相對(duì)于所求樣本點(diǎn)歐氏距離最近的k個(gè)樣本點(diǎn)規(guī)定為所求樣本點(diǎn)的k個(gè)鄰近點(diǎn)。k是預(yù)先設(shè)定的值。
2)計(jì)算樣本點(diǎn)的局部重建權(quán)值矩陣。這里定義一個(gè)成本函數(shù),其函數(shù)形式如下所示:
式中,xij(j=1,2…,k)為xi的k個(gè)鄰近點(diǎn);為xi與xij之間的權(quán)值,并滿(mǎn)足如下公式:
3)將所有的樣本點(diǎn)映射到低維空間中。
在利用k最鄰近點(diǎn)實(shí)現(xiàn)局部點(diǎn)云重構(gòu)、分離點(diǎn)云邊緣時(shí),本文采用3×3窗口搜索鄰近點(diǎn)。如圖1所示,點(diǎn)云邊緣窗口密度必然小于內(nèi)部窗口密度,且點(diǎn)云重構(gòu)的目的是分離邊緣,只需處理點(diǎn)云塊邊緣上的點(diǎn),因此只對(duì)點(diǎn)數(shù)量處于一定閾值內(nèi)的窗口進(jìn)行處理可以極大地提高效率。重構(gòu)時(shí)根據(jù)點(diǎn)號(hào)儲(chǔ)存兩套坐標(biāo):原始坐標(biāo)和重構(gòu)后坐標(biāo)。濾波后輸出原始坐標(biāo),因此在構(gòu)建重構(gòu)權(quán)值公式時(shí)無(wú)需考慮點(diǎn)云拓?fù)浣Y(jié)構(gòu)的變化,但若選權(quán)不正確,會(huì)導(dǎo)致誤分類(lèi)。如圖1所示,中心黑色點(diǎn)為重構(gòu)點(diǎn),紅色和紫色點(diǎn)為鄰近點(diǎn)。由于艦船靠岸較近,下方岸堤上的紫色點(diǎn)也被歸為鄰近點(diǎn)。若按照將距離向量作為權(quán)的原則,岸堤上的點(diǎn)對(duì)重構(gòu)點(diǎn)影響遠(yuǎn)大于船只上的點(diǎn)。
圖1 點(diǎn)云邊緣密度、內(nèi)部密度和k鄰近點(diǎn)
針對(duì)構(gòu)建權(quán)值公式這個(gè)問(wèn)題,考慮到一般情況下鄰近點(diǎn)群內(nèi)同類(lèi)型點(diǎn)占大多數(shù),所以,不應(yīng)以距離大小作為權(quán),而是將方向作為權(quán),并與鄰近k個(gè)點(diǎn)的方向的權(quán)等價(jià)再進(jìn)行重構(gòu)。先將重構(gòu)點(diǎn)與鄰近點(diǎn)的方向向量單位化,并分別用與坐標(biāo)軸平行的向量表示,單位化公式如下:
表示每個(gè)鄰近點(diǎn)對(duì)重構(gòu)點(diǎn)造成影響的方向; (xi、yi)(i=1,2…,N)表示重構(gòu)點(diǎn)原始坐標(biāo);(xij、yij)(j=1,2…,k)表示重構(gòu)點(diǎn)的k個(gè)鄰近點(diǎn)坐標(biāo),重構(gòu)點(diǎn)的位移距離為中心點(diǎn)與這k個(gè)點(diǎn)的平均距離:
重構(gòu)點(diǎn)重構(gòu)方向向量為:
重構(gòu)點(diǎn)重構(gòu)后坐標(biāo)(xi',yi')為:
河流區(qū)域點(diǎn)云數(shù)據(jù)中,非地面點(diǎn)主要包括水面與船只等非地面點(diǎn)云,其特性為非連續(xù)性塊狀孤立存在或相互嵌套,主要有4種分布情況:①圖2左上方區(qū)域水面點(diǎn)云獨(dú)立存在;②圖2右下方區(qū)域船只點(diǎn)云獨(dú)立存在;③圖2中心區(qū)域水面與船只點(diǎn)云相互嵌套;④圖2左下方近岸船只點(diǎn)云。而傳統(tǒng)濾波算法大多針對(duì)的是連續(xù)表面區(qū)域,帶有一定的局限性[9]。
圖2 水面點(diǎn)云與船只點(diǎn)云嵌套存在
本文通過(guò)分析水體區(qū)域非地面點(diǎn)云分布特征,利用水面點(diǎn)云均勻分布、高差變化較小和船只點(diǎn)云獨(dú)立性明顯的特點(diǎn),利用基于偏度與峰度的特征聚類(lèi),將大部分水面點(diǎn)云濾除。剩下的非地面點(diǎn)大部分為孤立船只點(diǎn)云與近岸船只點(diǎn)云,利用其獨(dú)立性可通過(guò)二值連通域標(biāo)記的方法將獨(dú)立性明顯的船只點(diǎn)云進(jìn)行濾除,但近岸船只離岸較近難以標(biāo)記。本文算法通過(guò)先利用點(diǎn)云k最鄰近點(diǎn)間歐氏距離構(gòu)建約束條件進(jìn)行點(diǎn)云重構(gòu),對(duì)獨(dú)立點(diǎn)云塊邊緣的激光點(diǎn)重新賦予三維坐標(biāo),使其向點(diǎn)云塊內(nèi)部聚攏,近岸船只與岸堤點(diǎn)云邊緣相互遠(yuǎn)離,從而增強(qiáng)點(diǎn)云塊的獨(dú)立性。若一次重構(gòu)獨(dú)立性還不明顯,可進(jìn)行多次重構(gòu),最后利用二值連通域的方法對(duì)孤立船只與近岸船只點(diǎn)云進(jìn)行標(biāo)記與濾除。
本文算法的基本描述思路如下:
1)首先對(duì)點(diǎn)云進(jìn)行分塊。為保證格網(wǎng)內(nèi)有足夠多的點(diǎn)進(jìn)行參數(shù)統(tǒng)計(jì)與足夠多的鄰近點(diǎn),且格網(wǎng)應(yīng)當(dāng)盡量小以提高精度,通過(guò)統(tǒng)計(jì)陸地與水體雜質(zhì)點(diǎn)云密度得出格網(wǎng)大小。
2)利用偏度與峰度和高程均值進(jìn)行特征聚類(lèi),設(shè)定閾值,并選取一塊典型水體雜質(zhì)區(qū)域統(tǒng)計(jì)其特征參數(shù)作為標(biāo)準(zhǔn),實(shí)現(xiàn)點(diǎn)云分割,從而濾除水面點(diǎn)。
3)利用k最鄰近點(diǎn)實(shí)現(xiàn)局部點(diǎn)云重構(gòu)提高近岸船只點(diǎn)云獨(dú)立性,分離船只點(diǎn)云與地面點(diǎn)云邊緣。
4)最后對(duì)重構(gòu)后的點(diǎn)云數(shù)據(jù)提取其離群點(diǎn)集,將點(diǎn)云數(shù)據(jù)按照格網(wǎng)塊轉(zhuǎn)化為二值圖像,再利用王靜等二值圖像連通域的分段標(biāo)記算法[10]對(duì)二值圖像進(jìn)行連通域標(biāo)記,濾除格網(wǎng)數(shù)量處于一定閾值內(nèi)的點(diǎn)云塊,將濾除后的點(diǎn)云塊數(shù)據(jù)進(jìn)行顯示。觀(guān)察濾除效果是否明顯,若不明顯,重復(fù)第3~5步。對(duì)重構(gòu)后的點(diǎn)云圖像進(jìn)行迭代,多次重構(gòu)分離邊緣,直至達(dá)到理想濾除效果。算法主要流程如圖3所示。
圖3 基于特征聚類(lèi)與鄰近點(diǎn)重構(gòu)的算法流程
為了判斷本文算法的有效性,采用長(zhǎng)江河道九江至湖口張家洲河段點(diǎn)云數(shù)據(jù),累計(jì)掃描面積約15×4 km2,共采集 6 586 465個(gè)激光點(diǎn),平均點(diǎn)距1.4 m,點(diǎn)云密度0.51 個(gè)/m2。圖4為總體濾波效果圖,圖中獨(dú)立塊狀點(diǎn)云一般為船只,且存在較多近岸船只點(diǎn)云,帶狀點(diǎn)云一般為水面點(diǎn),其中鑲嵌大量船只等非水面點(diǎn)云。實(shí)驗(yàn)區(qū)域總體上點(diǎn)云分布情況較為復(fù)雜,濾波后共濾除134 917個(gè)點(diǎn)(圖中紅色點(diǎn)),可觀(guān)察到非地面點(diǎn)已基本被濾除。
圖4 總體濾波效果圖
圖5為對(duì)圖2中相互嵌套的船只與水面點(diǎn)云進(jìn)行特征聚類(lèi)前后的對(duì)比圖,可明顯觀(guān)察到水體區(qū)域內(nèi)水面點(diǎn)已基本濾除,且特征聚類(lèi)后的水體區(qū)域僅存在孤立船只點(diǎn)云和少量與孤立船只點(diǎn)云較近的水面點(diǎn),但在之后的二值連通域標(biāo)記中被一同濾除。
圖5 特征聚類(lèi)后點(diǎn)云圖
圖6為使用基于參數(shù)統(tǒng)計(jì)的點(diǎn)云分割算法對(duì)水面點(diǎn)進(jìn)行濾除之后的數(shù)據(jù)進(jìn)行基于k最鄰近點(diǎn)點(diǎn)云重構(gòu)前后的局部效果對(duì)比圖,可觀(guān)察到近岸船只點(diǎn)云與岸堤點(diǎn)云邊緣被分離開(kāi)來(lái),近岸艦船點(diǎn)云與岸邊最近距離從4 m擴(kuò)大到10 m,邊緣明顯分離。
圖6 點(diǎn)云重構(gòu)效果對(duì)比圖
觀(guān)察特征聚類(lèi)分割后的圖6可知,非近岸點(diǎn)云的濾波效果較好,整體濾波的主要誤差來(lái)自于近岸船只點(diǎn)云的誤分類(lèi)。為驗(yàn)證本算法的有效性,從實(shí)驗(yàn)區(qū)域中選取一塊含有近岸船只點(diǎn)云的典型區(qū)域進(jìn)行驗(yàn)證。圖7為所選取的典型區(qū)域,有大量船只??吭诎哆?,大部分船只點(diǎn)云與岸邊有一明顯的窄縫,部分船只點(diǎn)云與岸堤相連。圖中共有10個(gè)近岸點(diǎn)云塊。將重構(gòu)前和重構(gòu)后的點(diǎn)云分別進(jìn)行二值連通域標(biāo)記與提取,共濾除602個(gè)點(diǎn)(圖中紅色點(diǎn)),9個(gè)近岸船只點(diǎn)云塊;不進(jìn)行重構(gòu)而直接提取二值連通域的方法共濾除211個(gè)點(diǎn)(圖中藍(lán)色矩形區(qū)域內(nèi)的紅色點(diǎn)),3個(gè)近岸船只點(diǎn)云塊。
圖7 濾波后點(diǎn)云圖像
通過(guò)人工對(duì)比實(shí)時(shí)光學(xué)影像資料與點(diǎn)云數(shù)據(jù),可準(zhǔn)確區(qū)分河流點(diǎn)云數(shù)據(jù)地面點(diǎn)與非地面點(diǎn),并進(jìn)行統(tǒng)計(jì)。共濾出非地面點(diǎn)654個(gè),一共10個(gè)船只點(diǎn)云塊。由于地面點(diǎn)大多相連,所以不會(huì)導(dǎo)致地面點(diǎn)誤分類(lèi)為非地面點(diǎn)。將人工濾除結(jié)果作為標(biāo)準(zhǔn)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)價(jià)。本文的重構(gòu)方法顯著提高了非地面點(diǎn)云的濾除效果。
表1 重構(gòu)前后近岸船只點(diǎn)云濾波指標(biāo)統(tǒng)計(jì)/%
通過(guò)分析河流區(qū)域非地面點(diǎn)云的類(lèi)型,主要包括水面點(diǎn)云與船只點(diǎn)云,且船只點(diǎn)云分為孤立船只點(diǎn)云與近岸船只點(diǎn)云,利用水面點(diǎn)的均勻分布和高差變化小以及船只點(diǎn)云獨(dú)立性明顯的特點(diǎn),通過(guò)特征聚類(lèi)標(biāo)記水面點(diǎn)云并利用k最鄰近點(diǎn)點(diǎn)云重構(gòu)分離點(diǎn)云塊邊緣,提高近岸船只點(diǎn)云獨(dú)立性,最后使用二值連通域標(biāo)記,最終實(shí)現(xiàn)河流區(qū)域非地面點(diǎn)的濾除。由于地面點(diǎn)大多相連,所以不會(huì)導(dǎo)致地面點(diǎn)誤分類(lèi)為非地面點(diǎn),能夠有效保留地面點(diǎn)信息。該算法能將90%以上的水面點(diǎn)云、孤立船只點(diǎn)云和鑲嵌在水面點(diǎn)云中的船只點(diǎn)云濾除,從總體上實(shí)現(xiàn)河流區(qū)域非地面點(diǎn)云的有效濾除。
[1] 舒寧 . 激光成像 [M]. 武漢 :武漢大學(xué)出版社 ,2005
[2] Kraus K, Pfeifer N. Determination of Terrain Models in Wooded Areas with Airborne Laser Scanner Data[J]. ISPRS Journal of Photogrammetry & Remote Sensing, 1998, 53(4):193-203
[3] Axelsson P. DEM Generation from Laser Scanner Data Using Adaptive TIN Models[J].International Archives of Photogrammetry & Remote Sensing,2000,33
[4] Vosselman G. Slope Based Filtering of Laser Altimetry Data[J].International Archives of Photogrammetry & Remote Sensing,2000, 33(B3):935-942
[5] 王宗躍, 馬洪超, 徐宏根,等. 基于LiDAR點(diǎn)云數(shù)據(jù)的水體輪廓線(xiàn)提取方法研究[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2010(4):432-435
[6] 張永軍,吳磊,林立文,等. 基于LiDAR數(shù)據(jù)和航空影像的水體自動(dòng)提取[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2010(8):936-940
[7] 楊曉云,岑敏儀,賈洪果. 基于參數(shù)統(tǒng)計(jì)的LiDAR數(shù)據(jù)分割算法[J].測(cè)繪通報(bào), 2013(10):20-22
[8] Kanade T, Tian Y, Cohn J F. Comprehensive Database for Facial Expression Analysis[C].IEEE International Conference on Automatic Face and Gesture Recognition, 2000
[9] 李卉, 李德仁, 黃先鋒,等. 一種漸進(jìn)加密三角網(wǎng)LIDAR點(diǎn)云濾波的改進(jìn)算法[J].測(cè)繪科學(xué),2009, 34(3):39-40
[10] 王靜. 二值圖像連通域的分段標(biāo)記算法及實(shí)現(xiàn)[J].紅外與激光工程, 2010, 39(4):761-765
P237
B
1672-4623(2017)10-0032-04
10.3969/j.issn.1672-4623.2017.10.010
2016-09-12。
項(xiàng)目來(lái)源:國(guó)家自然科學(xué)基金資助項(xiàng)目(41471276);水利部黃土高原水土流失過(guò)程與控制重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金課題(2015001)。
易航,碩士研究生,研究方向?yàn)閿z影測(cè)量與遙感。