易 航，李 浩，楊 彪，韋立新，蔣建平

（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)云。

1 基于特征聚類(lèi)的點(diǎn)云分割與LLE算法

1.1 基于特征聚類(lèi)的點(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)。

1.2 LLE算法

局部線(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)映射到低維空間中。

1.3 點(diǎn)云重構(gòu)效率優(yōu)化與權(quá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'）為：

2 基于特征聚類(lèi)與點(diǎn)云重構(gòu)的濾波方法

2.1 算法原理

河流區(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)記與濾除。

2.2 算法具體過(guò)程

本文算法的基本描述思路如下：

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)的算法流程

3 實(shí)驗(yàn)分析

3.1 本文算法整體濾波效果

為了判斷本文算法的有效性，采用長(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 總體濾波效果圖

3.2 基于偏度與峰度的特征聚類(lèi)效果

圖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)云圖

3.3 點(diǎn)云重構(gòu)分離邊緣效果

圖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ì)/%

4 結(jié) 語(yǔ)

通過(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è)量與遙感。