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

（1.河海大學(xué) 地球工程與工程學(xué)院，江蘇 南京 210098；2.長江下游水文水資源勘測局,江蘇 南京 210010）

基于聚類與重構(gòu)的河流區(qū)域濾波方法

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

（1.河海大學(xué) 地球工程與工程學(xué)院，江蘇 南京 210098；2.長江下游水文水資源勘測局,江蘇 南京 210010）

研究河流區(qū)域水體點云的分布特征與相互關(guān)系，提出基于特征聚類的點云分割與基于LLE算法的鄰近點點云重構(gòu)濾波方法。通過統(tǒng)計網(wǎng)格內(nèi)點云的特征參數(shù)，進行點云分割并濾除水面點，再利用LLE算法的鄰近點構(gòu)建約束條件進行點云重構(gòu)，分離近岸船只點云與岸堤點云的邊緣，最后利用船只點云的獨立性進行二值連通域標記與濾除，從而實現(xiàn)河流區(qū)域的點云濾波。實驗表明，該方法能夠濾除90%以上的水面點云與大部分船只點云。

水體點云；特征參數(shù)；聚類分析；點云重構(gòu)

機載激光雷達（LiDAR）技術(shù)是目前應(yīng)用最廣泛的高分辨率測量技術(shù)之一。LiDAR系統(tǒng)獲取到地面的三維點云信息，并記錄多次反射的強度信息。由于陸地測量的機載LiDAR工作波長一般為1 040～1 060 nm[1]，位于水體的強吸收帶，所以理想條件下不反射激光脈沖。但在實際中，河流區(qū)域的船只等物體會產(chǎn)生反射信號形成船只點云，且受到無人機飛行路線與水面反射的影響，在特殊情況下水面也會產(chǎn)生反射信號，形成水面點云。水面點云與船只點云都為非地面點，且相互嵌套，分布較為復(fù)雜。河流區(qū)域點云濾波的目的就是將河流區(qū)域非地面點濾除[2-4]。

河流區(qū)域非地面點濾除在水體邊緣提取中較為常見[5,6]。本文通過對河流區(qū)域的點云分布特性進行研究，利用水面點云均勻分布與船只點云獨立性明顯的特點，參考楊曉云[7]等所提出描述數(shù)據(jù)分布形態(tài)的統(tǒng)計量偏度與峰值概念，提出了基于特征聚類的點云分割和基于LLE算法的鄰近點點云重構(gòu)的濾波方法。該方法能從河流區(qū)域點云數(shù)據(jù)中有效剔除非地面點云。

1 基于特征聚類的點云分割與LLE算法

1.1 基于特征聚類的點云分割

點云分割是利用目標區(qū)域點云的空間、幾何和紋理等特征進行劃分，使得處于同一區(qū)域內(nèi)的點云具有相似的分布特征。本文利用點云高程分布的偏度、峰度與均值進行特征聚類，實現(xiàn)點云分割。

偏度是統(tǒng)計數(shù)據(jù)分布偏斜方向和程度的度量。偏度為0時，表示其數(shù)據(jù)點云分布與正態(tài)分布的偏離程度相同，偏度的計算公式如下：

式中，N為格網(wǎng)內(nèi)的點數(shù)；si為格網(wǎng)內(nèi)點的高程；i∈（1,2,3…N）；σ為格網(wǎng)內(nèi)點的標準差，u為高程均值。標準差和算術(shù)平均值的計算公式如下：

峰度是描述數(shù)據(jù)點云高程分布形態(tài)陡緩程度的量度，峰度為0表示總體數(shù)據(jù)分布與正態(tài)分布的陡緩程度相同。峰度的計算如式如下：

由于水面點高程變化不大，而非水面點大多變化明顯，因此利用偏度、峰度與高程均值對格網(wǎng)內(nèi)的點云進行特征聚類，可有效分割出水面點。

1.2 LLE算法

局部線性嵌入（locally linear embedding，LLE）算法是Roweis和Saul于2000年提出的一種非線性降維方法，基于高維空間中相鄰或相關(guān)的點映射到低維空間中也同樣地相鄰或相關(guān)的幾何思想[8]。LLE算法流程可以歸結(jié)為以下幾步：

1）計算出每個樣本點的k個鄰近點，把相對于所求樣本點歐氏距離最近的k個樣本點規(guī)定為所求樣本點的k個鄰近點。k是預(yù)先設(shè)定的值。

2）計算樣本點的局部重建權(quán)值矩陣。這里定義一個成本函數(shù)，其函數(shù)形式如下所示：

式中，xij(j=1,2…,k)為xi的k個鄰近點；為xi與xij之間的權(quán)值，并滿足如下公式：

3）將所有的樣本點映射到低維空間中。

1.3 點云重構(gòu)效率優(yōu)化與權(quán)值選擇

在利用k最鄰近點實現(xiàn)局部點云重構(gòu)、分離點云邊緣時，本文采用3×3窗口搜索鄰近點。如圖1所示，點云邊緣窗口密度必然小于內(nèi)部窗口密度，且點云重構(gòu)的目的是分離邊緣，只需處理點云塊邊緣上的點，因此只對點數(shù)量處于一定閾值內(nèi)的窗口進行處理可以極大地提高效率。重構(gòu)時根據(jù)點號儲存兩套坐標：原始坐標和重構(gòu)后坐標。濾波后輸出原始坐標，因此在構(gòu)建重構(gòu)權(quán)值公式時無需考慮點云拓撲結(jié)構(gòu)的變化，但若選權(quán)不正確，會導(dǎo)致誤分類。如圖1所示，中心黑色點為重構(gòu)點，紅色和紫色點為鄰近點。由于艦船靠岸較近，下方岸堤上的紫色點也被歸為鄰近點。若按照將距離向量作為權(quán)的原則，岸堤上的點對重構(gòu)點影響遠大于船只上的點。

圖1 點云邊緣密度、內(nèi)部密度和k鄰近點

針對構(gòu)建權(quán)值公式這個問題，考慮到一般情況下鄰近點群內(nèi)同類型點占大多數(shù)，所以，不應(yīng)以距離大小作為權(quán)，而是將方向作為權(quán)，并與鄰近k個點的方向的權(quán)等價再進行重構(gòu)。先將重構(gòu)點與鄰近點的方向向量單位化，并分別用與坐標軸平行的向量表示，單位化公式如下：

表示每個鄰近點對重構(gòu)點造成影響的方向； (xi、yi)(i=1,2…,N)表示重構(gòu)點原始坐標；(xij、yij)(j=1,2…,k)表示重構(gòu)點的k個鄰近點坐標，重構(gòu)點的位移距離為中心點與這k個點的平均距離：

重構(gòu)點重構(gòu)方向向量為：

重構(gòu)點重構(gòu)后坐標（xi'，yi'）為：

2 基于特征聚類與點云重構(gòu)的濾波方法

2.1 算法原理

河流區(qū)域點云數(shù)據(jù)中，非地面點主要包括水面與船只等非地面點云，其特性為非連續(xù)性塊狀孤立存在或相互嵌套，主要有4種分布情況:①圖2左上方區(qū)域水面點云獨立存在；②圖2右下方區(qū)域船只點云獨立存在；③圖2中心區(qū)域水面與船只點云相互嵌套；④圖2左下方近岸船只點云。而傳統(tǒng)濾波算法大多針對的是連續(xù)表面區(qū)域，帶有一定的局限性[9]。

圖2 水面點云與船只點云嵌套存在

本文通過分析水體區(qū)域非地面點云分布特征，利用水面點云均勻分布、高差變化較小和船只點云獨立性明顯的特點，利用基于偏度與峰度的特征聚類，將大部分水面點云濾除。剩下的非地面點大部分為孤立船只點云與近岸船只點云，利用其獨立性可通過二值連通域標記的方法將獨立性明顯的船只點云進行濾除,但近岸船只離岸較近難以標記。本文算法通過先利用點云k最鄰近點間歐氏距離構(gòu)建約束條件進行點云重構(gòu)，對獨立點云塊邊緣的激光點重新賦予三維坐標，使其向點云塊內(nèi)部聚攏，近岸船只與岸堤點云邊緣相互遠離，從而增強點云塊的獨立性。若一次重構(gòu)獨立性還不明顯，可進行多次重構(gòu)，最后利用二值連通域的方法對孤立船只與近岸船只點云進行標記與濾除。

2.2 算法具體過程

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

1）首先對點云進行分塊。為保證格網(wǎng)內(nèi)有足夠多的點進行參數(shù)統(tǒng)計與足夠多的鄰近點，且格網(wǎng)應(yīng)當盡量小以提高精度，通過統(tǒng)計陸地與水體雜質(zhì)點云密度得出格網(wǎng)大小。

2）利用偏度與峰度和高程均值進行特征聚類，設(shè)定閾值，并選取一塊典型水體雜質(zhì)區(qū)域統(tǒng)計其特征參數(shù)作為標準，實現(xiàn)點云分割，從而濾除水面點。

3）利用k最鄰近點實現(xiàn)局部點云重構(gòu)提高近岸船只點云獨立性，分離船只點云與地面點云邊緣。

4）最后對重構(gòu)后的點云數(shù)據(jù)提取其離群點集，將點云數(shù)據(jù)按照格網(wǎng)塊轉(zhuǎn)化為二值圖像，再利用王靜等二值圖像連通域的分段標記算法[10]對二值圖像進行連通域標記，濾除格網(wǎng)數(shù)量處于一定閾值內(nèi)的點云塊，將濾除后的點云塊數(shù)據(jù)進行顯示。觀察濾除效果是否明顯，若不明顯，重復(fù)第3～5步。對重構(gòu)后的點云圖像進行迭代，多次重構(gòu)分離邊緣，直至達到理想濾除效果。算法主要流程如圖3所示。

圖3 基于特征聚類與鄰近點重構(gòu)的算法流程

3 實驗分析

3.1 本文算法整體濾波效果

為了判斷本文算法的有效性，采用長江河道九江至湖口張家洲河段點云數(shù)據(jù)，累計掃描面積約15×4 km2，共采集 6 586 465個激光點，平均點距1．4 m，點云密度0．51 個/m2。圖4為總體濾波效果圖，圖中獨立塊狀點云一般為船只，且存在較多近岸船只點云，帶狀點云一般為水面點，其中鑲嵌大量船只等非水面點云。實驗區(qū)域總體上點云分布情況較為復(fù)雜，濾波后共濾除134 917個點（圖中紅色點），可觀察到非地面點已基本被濾除。

圖4 總體濾波效果圖

3.2 基于偏度與峰度的特征聚類效果

圖5為對圖2中相互嵌套的船只與水面點云進行特征聚類前后的對比圖，可明顯觀察到水體區(qū)域內(nèi)水面點已基本濾除，且特征聚類后的水體區(qū)域僅存在孤立船只點云和少量與孤立船只點云較近的水面點，但在之后的二值連通域標記中被一同濾除。

圖5 特征聚類后點云圖

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

圖6為使用基于參數(shù)統(tǒng)計的點云分割算法對水面點進行濾除之后的數(shù)據(jù)進行基于k最鄰近點點云重構(gòu)前后的局部效果對比圖，可觀察到近岸船只點云與岸堤點云邊緣被分離開來，近岸艦船點云與岸邊最近距離從4 m擴大到10 m，邊緣明顯分離。

圖6 點云重構(gòu)效果對比圖

觀察特征聚類分割后的圖6可知，非近岸點云的濾波效果較好，整體濾波的主要誤差來自于近岸船只點云的誤分類。為驗證本算法的有效性，從實驗區(qū)域中選取一塊含有近岸船只點云的典型區(qū)域進行驗證。圖7為所選取的典型區(qū)域，有大量船只?？吭诎哆叄蟛糠执稽c云與岸邊有一明顯的窄縫，部分船只點云與岸堤相連。圖中共有10個近岸點云塊。將重構(gòu)前和重構(gòu)后的點云分別進行二值連通域標記與提取，共濾除602個點（圖中紅色點），9個近岸船只點云塊；不進行重構(gòu)而直接提取二值連通域的方法共濾除211個點（圖中藍色矩形區(qū)域內(nèi)的紅色點），3個近岸船只點云塊。

圖7 濾波后點云圖像

通過人工對比實時光學(xué)影像資料與點云數(shù)據(jù)，可準確區(qū)分河流點云數(shù)據(jù)地面點與非地面點，并進行統(tǒng)計。共濾出非地面點654個，一共10個船只點云塊。由于地面點大多相連，所以不會導(dǎo)致地面點誤分類為非地面點。將人工濾除結(jié)果作為標準對實驗結(jié)果進行評價。本文的重構(gòu)方法顯著提高了非地面點云的濾除效果。

表1 重構(gòu)前后近岸船只點云濾波指標統(tǒng)計/%

4 結(jié) 語

通過分析河流區(qū)域非地面點云的類型，主要包括水面點云與船只點云，且船只點云分為孤立船只點云與近岸船只點云，利用水面點的均勻分布和高差變化小以及船只點云獨立性明顯的特點，通過特征聚類標記水面點云并利用k最鄰近點點云重構(gòu)分離點云塊邊緣，提高近岸船只點云獨立性，最后使用二值連通域標記，最終實現(xiàn)河流區(qū)域非地面點的濾除。由于地面點大多相連，所以不會導(dǎo)致地面點誤分類為非地面點，能夠有效保留地面點信息。該算法能將90%以上的水面點云、孤立船只點云和鑲嵌在水面點云中的船只點云濾除，從總體上實現(xiàn)河流區(qū)域非地面點云的有效濾除。

[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點云數(shù)據(jù)的水體輪廓線提取方法研究[J]．武漢大學(xué)學(xué)報(信息科學(xué)版),2010(4):432-435

[6] 張永軍,吳磊,林立文,等． 基于LiDAR數(shù)據(jù)和航空影像的水體自動提取[J]．武漢大學(xué)學(xué)報(信息科學(xué)版), 2010(8):936-940

[7] 楊曉云,岑敏儀,賈洪果． 基于參數(shù)統(tǒng)計的LiDAR數(shù)據(jù)分割算法[J]．測繪通報, 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] 李卉, 李德仁, 黃先鋒,等． 一種漸進加密三角網(wǎng)LIDAR點云濾波的改進算法[J]．測繪科學(xué),2009, 34(3):39-40

[10] 王靜． 二值圖像連通域的分段標記算法及實現(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。

項目來源：國家自然科學(xué)基金資助項目（41471276）；水利部黃土高原水土流失過程與控制重點實驗室開放基金課題（2015001）。

易航，碩士研究生，研究方向為攝影測量與遙感。