局部形狀特征概率混合的半自動三維點云分類

李紅軍，劉欣瑩，張曉鵬，嚴冬明

(1.北京林業(yè)大學 理學院， 北京 100083； 2.中國科學院自動化研究所 模式識別國家重點實驗室， 北京 100190)

局部形狀特征概率混合的半自動三維點云分類

李紅軍1，劉欣瑩2，張曉鵬2，嚴冬明2

(1.北京林業(yè)大學 理學院， 北京 100083； 2.中國科學院自動化研究所 模式識別國家重點實驗室， 北京 100190)

三維激光掃描獲取的點云數(shù)據可用于數(shù)字城市建設、三維模型獲取、場景分析與物體測量等領域.但因遮擋和噪聲的影響，加之掃描場景復雜，采樣精度受限，使得不能直接運用經典的曲面和三維空間理論對點云數(shù)據進行有效分析和處理.分類是點云數(shù)據預處理的重要方式之一.提取近鄰四面體體積、近鄰法向量差異度、主方向差異度和主曲率值4個局部形狀特征，采用概率混合策略構建了一種點云數(shù)據的半自動分類方法，可實現(xiàn)平面點集、柱面點集和其他點集的有效區(qū)分.其中，概率混合策略是依據近鄰點平均距離和單指標類別一致程度估計每個特征推斷形狀的概率，通過混合加權，依據概率賦權函數(shù)最大值準則進行局部形狀推斷.可實現(xiàn)用戶交互，以便處理不同掃描尺度和精度的點云數(shù)據.采用本文方法對模擬生成的點云、單棵樹木點云、街道場景點云、曠野自然場景掃描點云以及航空機載掃描點云等多組數(shù)據進行了實驗，結果表明，基于局部形狀特征的概率混合方法對各種點云數(shù)據均具有良好的分類效果.

點云分類；局部形狀推斷；概率混合；法向量差異；主曲率；大規(guī)模場景分析

A semi-automatic 3D point cloud classification method based on the probability mixture of local shape features. Journal of Zhejiang University(Science Edition), 2017,44(1):001-009

三維激光掃描儀和雷達等硬件設備及其操控軟件的快速發(fā)展，使得三維點云數(shù)據的獲取變得方便而快捷.只需幾分鐘便可完成一個場景的稠密采樣,而稀疏采樣可通過車載或者機載設備從移動設備上快速獲取.數(shù)據獲取的成本不斷降低,目前小型三維掃描儀的報價僅為幾萬元.設備日趨智能,經過簡單培訓即可學會數(shù)據采集與預處理.三維點云數(shù)據的快速積累及其蘊含的準確三維采樣信息,使得相關理論和應用研究日益廣泛和深入.在林業(yè)研究中,可用于無損測量和森林調研;在計算機圖形學[1]中,可用于三維場景模型的重建;在數(shù)字娛樂中,可用于虛擬場景構建;在建筑領域,則可用于數(shù)字文物保護和建筑測量等.此外,在數(shù)字城市建設和地理信息系統(tǒng)中也有應用.

點云數(shù)據有2個基本特點.一是準確的三維位置信息,主要包括采樣點的x,y,z三維空間相對坐標,有些數(shù)據還包括點的顏色信息和反射強度,但是沒有關聯(lián)關系信息;二是數(shù)據量大,一個場景包含幾千萬的離散采樣點，而多站點組合的掃描數(shù)據則構成大數(shù)據的規(guī)模.研究的挑戰(zhàn)來自于點集數(shù)據量的龐大、沒有拓撲結構和形狀信息以及由于遮擋造成數(shù)據的殘缺,此外還有噪聲的干擾.這些問題對采樣點集的形狀結構分析和進一步的場景理解造成了困難.

點云數(shù)據分類是語義標注和場景分析處理的基礎.從分類目的看,大致分為以語義標注為目的[2-4]和以形狀結構分析為目的2類.前者是場景理解的主要目標,后者依據點云形狀進行分類,側重于線和線段、平面、柱面、球面、錐面等形狀基元的識別,是實現(xiàn)前者的一個重要途徑,亦是本文的側重點.

形狀提取的2種經典方法:霍夫變換(Hough transform)[5]和隨機抽樣一致算法(RANdom SAmple Consensus,RANSAC)[6],在點云數(shù)據形狀提取方面已有廣泛應用.文獻[7]應用RANSAC算法從深度數(shù)據中提取了圓柱；CHAPERON等[8]則用RANSAC算法從三維點云數(shù)據中提取圓柱.德國波恩大學SCHNABEL等[9]認為,早期的這2種算法及其變式在基本形狀識別上有所欠缺,并開展了一系列工作,比如通過改進RANSAC算法，有效解決三維點云數(shù)據中的平面、球面、柱面和錐面的分類.但由于許多點云數(shù)據的法向量很難準確估計,僅依賴于點云法向量進行形狀推斷的方法有其局限性.當然,若能準確提取基元,則基于基元空間關系形成的圖結構,就能進行有語義信息的形狀推斷[10-11].

除了這2種經典算法外,其他算法需提取特定幾何形狀基元,本質上都屬于二類分類問題.較為常用的是對局部近鄰點集進行平面擬合[12-13],然后根據擬合度判斷形狀,此類方法較適合平面片的提取.采用模板匹配技術,也有助于快速獲得近似的重建結果[14].采用離散微分幾何量進行點云分類,主要是利用近鄰法向量方向差異度進行平面提取[15-16],此法適用于地面或者墻面的識別.利用近鄰點的主方向差異度進行圓柱面提取,可應用于樹干識別和樹木掃描點云枝葉分類[17].

除平面、柱面、球面、錐面外,線或者線段也是常用基元.根據激光掃描原理,通過分析掃描線提取線段并逐步形成多邊形,有利于建筑等對象的快速分割[18].提取的線段再結合其他信息對于點云分析和處理也有顯著作用,比如2015年普林斯頓大學關于點云對齊的工作[19]、法國DEMANTKE等[20]的關于點云維度分析的工作，他們依據局部幾何特征,主要是近鄰點之間的空間位置關系,采用主成分分析法將點云分為3類:線(1D)、平面(2D)和體(3D).

從上述已經公開的方法可知,近幾年利用法向量、主方向、平面擬合等方法提取特定形狀基元,實現(xiàn)2種分類的比較多,且都取得了一定效果.可見這些幾何量在局部形狀推斷上是起作用的.

受以上研究的啟發(fā),筆者認為這些幾何量對形狀推斷是一個綜合的效果,因此利用法向量和主方向的差異度,并結合局部點云主曲率的基本性質,提出了多個局部形狀特征概率混合的半自動點云分類方法,實現(xiàn)平面、柱面和其他點的3種分類.另外,注意到在同一設備同一次掃描中,可能由于遮擋,有些地方的點比較稀疏,受空中粒子的阻擋,引起水面或者玻璃等的采樣誤差,因此,筆者認為同一場景中,點云的疏密蘊含著形狀推斷的可靠性大小.將這種疏密用概率進行描述,再用加性混合策略實現(xiàn)基于多特征的3種分類.實踐中,大規(guī)模的點云數(shù)據有可能超過計算機的內存限制,因此本文從局部特征分析入手,通過對局部的研究進行全局推斷,為大數(shù)據的并行算法設計和核外算法設計提供參考.

1 局部形狀特征及其概率混合方法

1.1 局部形狀特征計算

不同于機器學習方法，局部形狀特征計算基于三維空間位置、回波強度、顏色等特征[21]進行點云分類,首先研究有利于區(qū)分平面(plane)、柱面(cylinder)、球面(sphere)和空間體(volumetric)等形狀的4個特征:近鄰四面體體積、法向量差異度、主方向差異度和主曲率閾值.

1.1.1 近鄰四面體體積

(1)

式(1)具有較明顯的幾何形狀度量含義.從直觀理解,若四面體的4個頂點來自同一平面點集,則v=0;若來自于柱面、球面,則v值略大于0;若來自于立方體內,則v值比較大.

1.1.2 k-近鄰點的法向量差異度

(2)其中,nP表示點P處的單位法向量,nQi表示P的近鄰點Qi處的單位法向量.顯然,對于平面上的點集,各點處的法向量垂直于平面,且都共線,|nP·nQi|=1,即ηP=0.而柱面的法向量則共面.

1.1.3 k-近鄰點的主方向差異度

(3)

其中,mP表示點P處的單位最小主曲率方向,mQi表示P的近鄰點Qi處的單位最小主曲率方向.顯然,理想情況下，柱面上點集各點處的最小主曲率方向都共線,離散數(shù)據測試表明,mP值最接近0.而來自于立方體內各點的主曲率方向比較雜亂,其差異度也比較大.需要注意的是，由于球面點集和平面點集中任意一點各方向的法向曲率值相等,因此其最大主曲率和最小主曲率值相等,導致最大和最小主曲率方向不能唯一確定,若隨機指定一個方向,則會造成第二主曲率方向的差異度較大.由于主方向的不確定性,利用主方向進行球面或者平面的推斷變得很不方便.

1.1.4 主曲率閾值

加入主曲率值特征是本算法框架區(qū)別于其他算法的特征之一.經典微分幾何表明,曲面上點的主曲率(設為κ1與κ2)組合有如下性質[22]:

?柱面上每個點都是拋物點(parabolic point),其最小主曲率為0，另一個主曲率值與柱面橫截面大小相關;

?平面上每個點都是平面臍點(umbilic point),其κ1和κ2都為0;

?球面上的點,κ1與κ2同號,是橢圓點(elliptical point);又因κ1=κ2,所以又是臍點;

根據上述主曲率性質,可以設計基于2個主曲率閾值的點云局部形狀判定算法：

算法X 基于主曲率閾值的離散點形狀類型推斷算法.

輸入：點P的主曲率κ1與κ2，且|κ2|≤|κ1|， ε.

輸出：P點所處的局部形狀類型.

該算法基于局部主曲率組合規(guī)則,將采樣點全部進行了分類,具有類型完備性.但是,由于受近似計算或者噪聲影響,接近閾值時或許容易誤判,因此,算法中若增加一類無法判定的類型也有其工程應用價值．算法中沒有直接采用解析曲面類型中的雙曲點,而是把此類型的點歸結到空間體內,以便于識別樹冠層內的點云．

1.2 概率混合分類算法設計

考慮到主曲率閾值法能把點云分為4類,加上接近閾值的情況對類別不作判斷,因此,所設計的算法把點云暫時分為平面、柱面、球面、空間體和類型不確定5類.將用單獨一種特征對點云分類的結果稱為初始分類,因此,4種特征對應4種初始分類.

1.2.1 澆灌液制備 準確稱取A物質0.005 g溶于100 mL蒸餾水中作為母液，將母液平均分為4份，第1份不加蒸餾水，標為濃度0.050 g/L的澆灌液，第2份加蒸餾水25 mL，標為濃度0.025 g/L的澆灌液，第3份加蒸餾水50 mL，為濃度0.010 g/L的澆灌液，第4份加蒸餾水125 mL，為濃度0.005 g/L的澆灌液。用同樣的方法制備B、C、D不同濃度的澆灌液。

接下來的重點是將這4個特征綜合到一個指標中,這種綜合方法稱為概率混合法.概率的引入基于以下假設:受遮擋和噪聲的影響,局部近鄰關系估計的體積、法向量、主方向和主曲率都可能存在誤差.這些誤差與采樣密度相關.另一方面,在k個近鄰點中,類別標號越一致,其類別的可信度就越高.反之，類別標號越雜亂,則類別的可信度就越低.于是,定義任意一點P屬于類別j的概率為

(4)

其中,pα,j,j=1,2,…,5表示用α特征分類時,點分別屬于平面、柱面、球面、空間體和不確定類的概率.其中，α∈{ν,η,m,κ}.示性函數(shù)

(5)

其中,l(Qi)表示點Qi的初始類別標號.縮放因子Ω為掃描點云最近鄰4個點平均距離的2k倍.該縮放因子的設定使得概率計算免受場景大小和掃描分辨率對參數(shù)設定的影響.

由式(4)可以計算每一個點對應于分類方法的概率向量,記為

pα=(pα,1,pα,2,pα,3,pα,4,pα,5).

(6)

設混合策略以權向量w表示為

w=(wν,wη,wm,wκ)，

(7)

其中每個分量分別為4種特征分類權系數(shù).則由概率向量式(6)和策略權向量式(7)通過加性組合形成概率混合函數(shù),使得這個函數(shù)取得最大值的類別標號就是該點的最終類別.則本文的概率混合決策式為

(8)

由式(8)進行決策,確定該點最可能的類別.需要說明的是,混合權向量體現(xiàn)用戶對選取的分類特征的偏好.若混合權向量的某分量為0,則該分類結果不進入混合計算;若各個分類結果相同,則混合后的分類結果也不變;若各個分類結果不同,則由概率較大且權系數(shù)較大的混合結果決定最終的分類標號.本文算法的半自動方法主要指權向量的設定.

作為一個完整的點云分類算法,本文的概率混合點云分類算法流程如圖1所示.算法中的kd樹構建和近鄰查詢參見文獻[23],法向量、主曲率和主方向的計算參考文獻[24].由于kd樹的構建是O(n)級,近鄰點查詢?yōu)镺(log(n))級,而法向量、主曲率計算都是O(nlog(n))級,概率融合為O(n)級,所以算法為線性對數(shù)級,即O(nlog(n)).算法中主要是近鄰點的個數(shù)k、共面性和零閾值參數(shù)ε的選取.其中參數(shù)k的精細選取可以參考文獻[25],由于空間體的確定，k至少大于6,通常在9～25間選1個數(shù),比如k=20.而ε的選取與數(shù)據有關,需通過實驗調試確定.

圖1 算法流程圖Fig.1 The algorithm flowchart

2 點云分類實驗

為了驗證本文提出的4個局部形狀特征概率混合進行點云分類算法的可行性,用模擬數(shù)據和多個公開數(shù)據進行實驗,并與相關工作比較.除了主曲率方法能區(qū)分球面和空間體點云外,其他3個特征對這些形狀的區(qū)分效果不明顯,因此,實驗中重點進行平面、柱面和其他點云等的3種分類.

2.1 模擬數(shù)據分類實驗

首先，用一個解析曲面隨機采樣的離散點集進行實驗.該點集從平面、柱面、球面和正方體中簡單隨機采樣(見圖2(a)).每種形狀采樣3 000個點,共12 000個點.

圖2 4種基本形狀合成點云分類Fig.2 Point cloud synthesized with 4 kinds of shapes

采用本文算法,得到的分類情況如圖2(b)所示.圖中黃色為平面點,藍色為柱面點,綠色為其他點.從分類結果可以看出,在疊合區(qū)域,對點的形狀判斷較為困難.但通過準確的點的類型信息,并與分類結果相比較,可以得到混淆矩陣及其對應的百分率,結果見表1.三類的平均準確率為90.96%.

表1 分類點數(shù)以及對應百分比的混淆矩陣

事實上,4種形狀特征可以組合成15種分類方式,各種混合方式的準確率如圖3所示,其中v,n,d,k分別表示基于體積、法向量、主方向和主曲率的分類.從圖3可以看出,依據法向量一致性分類的準確率約為70%,這與文獻[9]的結論一致;而主曲率參與的分類效果最好,最好的是4種特征(kndv)的概率混合結果.

圖3 不同混合算法分類結果的準確率Fig.3 Accurate rates of different mix methods

2.2 單棵樹木點云分類

對于實際掃描點云,首先以樹干檢測為例,測試本文算法與主方向一致性判斷方法[17]在柱面識別上的效果.

圖4 松樹點云枝葉分類比較Fig.4 A pine point cloud classified into leaves and branches points using two different methods

一般而言,對于單棵樹木點云,其枝干點云局部呈圓柱形[26];而樹冠點云則呈立方體或者球形;少有平面點集.實驗數(shù)據(見圖4(a))采集于北京大學校園,包含116 940個采樣點,樹高約8.24 m,點云的枝葉以及地面的分類效果如圖4(b)所示.對比樹干提取結果(圖4(d),16 452個點)與基于主方向投票技術的樹木枝葉分割結果(圖4(c),14 076個點)[17],本文算法提取枝干點多出2 376個,其結果更有利于樹干的準確測量和重建.

2.3 城市街道場景點云分類

在數(shù)字城市建設過程中,城市街道的掃描是一項主要工作.街道場景中的對象一般包括道路、建筑、行道樹、車、人和廣場等.由于道路和廣場都近似為平面形狀,而建筑往往由平面近似組合而成,以往的文獻側重于提取這類建筑面.本文方法則還能進一步獲得柱面形狀對象.

一個來源于美國卡內基梅隆大學(Carnegie Mellon University, CMU)的三維點云數(shù)據庫[27]的城市街道場景數(shù)據(見圖5(a))包含196 811個點.用本文方法,點云數(shù)據分為3類:平面，包括地面和部分建筑面(黃色)；柱面，主要是建筑柱子、棱角和樹干(藍色)；其他點，即城市植被等(綠色),如圖5(c)所示.2015年德國Karlsruhe Institute of Technology(KIT)提出通過優(yōu)化最近鄰數(shù)實現(xiàn)點云最優(yōu)聚類方法[27],其分類效果如圖5(b)所示.

表2 街道場景點云分類的混淆矩陣

對比2個結果可以看出,本文方法能區(qū)分建筑物的平面墻和柱面墻(見圖5(d));更多地保留了一些細節(jié),比如左側建筑前面的小汽車和摩托車，可看到右側建筑物門口更多的臺階等.表2為本文的概率混合方法的混淆矩陣與文獻[27]的對比,本文方法的平均準確率為82.13%.

數(shù)據來源：http://www.cs.cmu.edu/～vmr/datasets/oakland-3d/cvpr09/doc/

圖5 城市街道場景點云分類Fig.5 Street point cloud classification

2.4 曠野自然場景點云分類

對復雜自然場景進行點云分類有助于環(huán)境監(jiān)測和地理信息分析.以法國Brodu N主頁的自然場景及數(shù)據(圖6(a))為例.該場景包含1 908 271個點,局部空白處是由遮擋造成的點云缺失.圖6(b)是本文方法的分類結果,沙地和植被大致可區(qū)分.圖6(c)是圖6(b)左下區(qū)域的局部放大圖,對比Canupo軟件的計算結果[28](見圖6(d))可以看出，本文4個特征概率混合方法能將沙漠地形較好地分離,且地上的綠植明顯比Canupo軟件多.考慮是遠距離大場景的掃描,故對點的位置敏感性要求有所降低,僅測試了用法向量差異度進行的分割,即其余的特征權重皆為零,所得結果如圖6(d)所示,則點云分類效果與該軟件分類結果相當,分類結果的混淆矩陣如表3所示,準確率為94.86%.

據文獻[3],本文算法具有階層式分類的特征.可滿足用戶的多階層分類需求.

表3 Canupo數(shù)據分類的混淆矩陣

數(shù)據來源：http://nicolas.brodu.net/en/recherche/canupo/

圖6 曠野自然場景點云分類Fig.6 A nature scene point cloud classification

2.5 機載掃描點云數(shù)據分類

上面幾組數(shù)據都由地面掃描儀采集.本節(jié)將測試由空中機載掃描儀獲得的數(shù)據,并進行分類準確率的量化分析.數(shù)據來源于莫斯科國立羅蒙諾索夫大學的圖形與媒體實驗室(Graphics and Media Lab, GML),他們曾用樸素貝葉斯方法[29]和非聯(lián)合馬爾科夫網方法[30]進行了點云分類.數(shù)據包含1 002 668個點,并附有一個點云分類準確結果,如圖7(a)所示.原始數(shù)據分7類,本文將地面單獨作為一類(黃色),建筑和汽車等歸為第2類(藍色),其余為第3類(綠色).這3類點的數(shù)量分別為439 989,22 880和539 799.這樣便于與本文分類結果相比較,也便于計算混淆矩陣,見表4.

數(shù)據來源：http://graphics.cs.msu.ru/en/node/922

圖7 空中掃描場景點云分類Fig.7 An airborne LIDAR scan point cloud classification

形狀平面柱面其他平面/%柱面/%其他/%地面2822444545911228664．20．325．5建筑117614670644951．420．428．2其他506505614885889．40．190．5

表4中,由于原數(shù)據標簽是地面和建筑,而本文的分類是平面與柱面,比較圖7(c)與(d)可知,屋頂平面點不在建筑類而大量地被分到平面點集中.通過增大與地面的距離或許能識別屋頂,但這不是本文的當前目標,而是基于物體提取的目標.即便如此,參考GML的類型標示，本文方法的平均準確率也達到了77.34%.

從上述實驗可以看出,本文算法能夠達到現(xiàn)有優(yōu)化方法的點云分類效果.在保證效果的前提下,本文算法的優(yōu)勢主要有:(1)對點云類別結果給出了類別判定的概率;(2)方法直觀、邏輯明確、容易實現(xiàn);(3)用戶半自動設定特征融合方式,便于適應不同點云采樣分辨率和滿足用戶的階層式分類需求.上述數(shù)據的實驗耗時如表5所示,主要耗時通過主曲率計算.

表5 實驗時間

3 結論與討論

針對以形狀結構分析為目的的點云分類,提出了一種將近鄰四面體體積、近鄰法向量方向差異度、主方向差異度和主曲率閾值4種局部形狀特征概率進行混合的半自動分類方法.該方法將點云數(shù)據分為平面點、柱面點和其他點3個基本類，為賦權加性混合方式，其概率基于點的分散程度和近鄰點類型的一致程度定義.工程應用中,用戶可根據經驗和實驗情況調整混合方式和權重.實驗數(shù)據包含模擬以及4個不同來源的掃描數(shù)據,即自己采集的松樹掃描點云和來自美國、法國、俄羅斯的數(shù)據.實驗結果表明,本文方法能較好地進行點云分類,準確率達77%以上.

一般而言,語義層面的點云分類主要有2條途徑:計算統(tǒng)計特征或采用機器學習方法判斷語義層面的點云分類；先從點云中獲取基本形狀,再根據基本形狀的位置關系進行語義層面的點云分類.本文采用的是后一種分類方法,其分類結果可作為面向語義形狀標注的預處理工作之一.

點云分類的準確性尚有很大的提升空間,涉及的工作包括噪聲識別與處理、缺失數(shù)據補全、分類準確性評估和有標注的點云對象庫的構建等.基于本文工作,還可就以下問題展開研究：提取更加豐富的形狀基元,研究各個基元之間的空間結構關系;參考網格曲面的形狀分析[31],研究一般二次曲面級別的點云分類問題;結合有效的地面識別方法[32],完成建筑側立面和屋頂面的提取;將這些結果應用于基于點云的形狀查詢、三維重建以及室內外點云場景理解等.

[1] 伍龍華,黃惠.點云驅動的計算機圖形學綜述[J].計算機輔助設計與圖形學學報,2015,27(8):1341-1353. WU L H, HUANG H. Survey on points-driven computer graphics[J]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(8): 1341-1353.

[2] 李慧盈,李文輝,陳圣波.一種機載雷達點云數(shù)據的快速分類方法[J].吉林大學學報:地球科學版，2010(5):1205-1210. LI H Y, LI W H, CHEN S B. A method for classify point clouds of airborne laser scanning[J]. Journal of Jilin University: Earth Science Edition, 2010(5): 1205-1210.

[3] 李文寧,張愛武,王書民,等.地面激光點云階層式分類方法[J].計算機輔助設計與圖形學學報,2015,27(8):1555-1561. LI W N, ZHANG A W, WANG S M, et al. Hierarchical classification method for terrestrial laser point clouds[J]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(8): 1555-1561.

[4] 吳永華,胡以華,顧有林,等.激光點云分類算法的探討與展望[J].紅外與激光工程,2010,39(增刊):147-151.WU Y H, HU Y H, GU Y L, et al. Discussion and prospect for classification algorithm of laser point cloud[J]. Infrared and Laser Engineering,2010,39(supp):147-151.

[5] HOUGH P. Method and means for recognizing complex patterns: 3069654[P].1962-12-18.

[6] FISCHLER M A, BOLLES R C. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM,1981,24(6):381-395.

[7] BOLLES R C, FISCHLER M A.A ransack-based approach to model fitting and its application to finding cylinders in range data[C]// Proceedings of the 7th International Joint Conference on Artificial Intelligence, San Francisco: Morgan Kaufmann Publishers Inc,1981:637-643.

[8] CHAPERON T, GOULETTE F.Extracting cylinders in full 3-d data using a random sampling method and the gaussian image[C]// VMV01.Stuttgart: Aka Gmbh，2001:35-42.

[9] SCHNABEL R, WAHL R, KLEIN R. Shape detection in point clouds[J]. Computer Graphics Technical Reports,2006,CG-2006/2.

[10] SCHNABEL R, WESSEL R, WAHL R, et al. Shape recognition in 3d point-clouds[C]//The 16th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision. Plzen： UNION Agency-Science Press，2008, 8.

[11] NIEUWENHUISEN M, STüCKLER J, BERNER A, et al. Shape-primitive based object recognition and grasping[C]//Proceedings of 7th German Conference on Robotics. Munich：VDE, 2012: 1-5.

[12] LARI Z, HABIB A, KWAK E. An adaptive approach for segmentation of 3D laser point cloud[J]. ISPRS Workshop Laser Scanning, Remote Sensing and Spatial Information Sciences，2011,XXXVIII-5/W12:103-108.

[13] NING X, ZHANG X, WANG Y, et al. Segmentation of architecture shape information from 3D point cloud[C]// Proceedings of the 8th International Conference on Virtual Reality Continuum and Its Applications in Industry. New York: ACM, 2009: 127-132.

[14] NAN L, XIE K, SHARF A. A search-classify approach for cluttered indoor scene understanding[J]. ACM Transactions on Graphics (TOG), 2012, 31(6): 137.

[15] RABBANI T, VAN DEN HEUVEL F, VOSSELMANN G. Segmentation of point clouds using smoothness constraint[J]. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2006, 36(5): 248-253.

[16] LI H, ZHANG X, JAEGER M, et al. Segmentation of forest terrain laser scan data[C]// Proceedings of the 9th ACM SIGGRAPH Conference on Virtual-Reality Continuum and its Applications in Industry. New York: ACM, 2010: 47-54.

[17] DAI M, LI H, ZHANG X. Tree modeling through range image segmentation and 3d shape analysis [C]//Advances in Neural Network Research and Applications. Springer /Berlin/ Heidelberg: Springer, 2010: 413-422.

[18] HEBEL M, STILLA U. Pre-classification of points and segmentation of urban objects by scan line analysis of airborne LIDAR data[J]. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2008, 37(B3a): 105-110.

[19] YU F, XIAO J, FUNKHOUSER T. Semantic alignment of LIDAR data at city scale[C]//Computer Vision and Pattern Recognition (CVPR). Los Alamitos: IEEE Computer Society,2015:1722-1731.

[20] DEMANTKE J, MALLET C, DAVID N, et al. Dimensionality based scale selection in 3D lidar point clouds[J]. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2011, 38(Part 5): W12.

[21] 李海亭,肖建華,李艷紅,等.機器學習在車載激光點云分類中的應用研究[J].華中師范大學學報:自然科學版,2015,49(3):460-464. LI H T, XIAO J H, LI Y H, et al. Application of machine learning in the vehicle-borne laser point cloud extraction[J].Journal of Central China Normal University: Natural Sciences, 2015, 49(3): 460-464.

[22] TOPONOGOV V A. Differential Geometry of Curves and Surfaces: A Concise Guide[M]. Boston：Springer Science & Business Media,2006.

[23] MOUNT D M. ANN Programming Manual[EB/OL].[2009-12-14]. http link: http://www. cs. umd. edu/～ mount/ANN/Files/1.1,2006,1.

[24] CHENG Z L, ZHANG X P. Estimating differential quantities from point cloud based on a linear fitting of normal vectors[J]. Science in China(Ser F): Information Sciences,2009,52(3):431-444.

[25] WEINMANN M, JUTZI B, HINZ S, et al. Semantic point cloud interpretation based on optimal neighborhoods, relevant features and efficient classifiers[J]. ISPRS Journal of Photogrammetry and Remote Sensing,2015,105:286-304.

[26] YAN D M, WINTZ J, MOURRAIN B, et al. Efficient and robust reconstruction of botanical branching structure from laser scanned points[C]// CAD/Graphics, Los Alamitos: IEEE Computer Society,2009:572-575.

[27] MUNOZ D, BAGNELL J A, VANDAPEL N, et al. Contextual classification with functional max-margin markov networks[C]// Computer Vision and Pattern Recognition(CVPR2009).Los Alamitos: IEEE Computer Society,2009:975-982.

[28] AIJAZI A K, CHECCHIN P, TRASSOUDAINE L. Segmentation based classification of 3D urban point clouds: A super-voxel based approach with evaluation[J]. Remote Sensing,2013,5(4):1624-1650.

[29] BRODU N, LAGUE D. 3D terrestrial lidar data classification of complex natural scenes using a multi-scale dimensionality criterion: Applications in geomorphology[J]. ISPRS Journal of Photogrammetry and Remote Sensing,2012,68:121-134.

[30] SHAPOVALOV R, VELIZHEV A, BARINOVA O. Non-associative markov networks for point cloud classification[C]// Photogrammetric Computer Vision and Image Analysis. Paris:出版社，2010.

[31] SHAPOVALOV R, VELIZHEV A. Cutting-plane training of non-associative markov network for 3D point cloud segmentation[C]// 3D Imaging, Modeling, Processing, Visualization and Transmission (3DIMPVT). Paris: ISPRS,2011:1-8.

[32] YAN D M, LIU Y, WANG W. Quadric surface extraction by variational shape approximation[M]//Geometric Modeling and Processing-GMP 2006. Berlin: Springer,2006:73-86.

LI Hongjun1, LIU Xinying2, ZHANG Xiaopeng2, YAN Dongming2

(1.CollegeofScience,BeijingForestryUniversity,Beijing100083,China; 2.NLPR-LIAMA,InstituteofAutomation,CAS,Beijing100190,China)

Point clouds captured by three dimensional scanner have been used in many fields, including modeling of digital cities, acquisition of three dimensional shapes, scene analysis and object measuring. However, due to the limitation of the sampling process and the complexity of scanned scenes, most traditional methods of surface modeling and three dimensional space analysis cannot work effectively when dealing with the point cloud data. Classification is therefore an important way for point cloud preprocess. Four features, namely the volume of a tetrahedron constructed by 4 neighboring points, the deviation of normal directions of neighboring points, the deviation of principal directions of neighboring points, and the values of principal curvature, are mixed with probabilities for semi-automatic classification of the three dimensional point cloud data. With the new method, a point cloud is to be divided into three classes: plane points, cylinder points and other points. The initial classification result is labeled according to its single shape feature value. The probability mixture is completed by estimating the probability of inferring a shape from a local point set with respect to each feature, generating a mixture with weighted sum, and maximizing the mixture probability function, while the probability is estimated with the average distance between a point and its neighbor points together with the consistency ratio of initial labels of the point to its neighbors. User interactions are invoked to make the choice of classification thresholds and the setting of weights, which is helpful when dealing with point cloud with different space scale and scanning point resolution. Experiments show that the proposed method works well for various kinds of point cloud data sets, including point clouds generated by simulation, and those corresponding to a single pine tree, a street scene, a country scene, and an airborne big scene.

point cloud classification; local shape inference; probability mixture; normal difference; principal curvature; large scale scene analysis

2016-07-25.

國家自然科學基金資助項目(61372190,61372168,61572502,61571439);國家863計劃課題項目(2015AA016402).

李紅軍(1969-)，ORCID:http://orcid.org/0000-0003-1102-6225，男，博士，副教授，主要從事計算幾何、計算機圖形學研究，E-mail：lihongjun69@bjfu.edu.cn.

10.3785/j.issn.1008-9497.2017.01.001

TP 311

A

1008-9497(2017)01-001-09