多閾值提取平面點云邊界點的方法

廖中平 劉科 向雨 蔡晨光

摘要：針對基于切片技術的點云數據重建算法需要提取切片內點云邊界點，及現有算法效率低、提取效果不好等問題，提出一種多閾值提取平面點云邊界點的算法。通過選取判斷點的k個近鄰點，計算相鄰兩點與判斷點連線間夾角，由于邊界點必存在最大夾角，通過判斷最大夾角是否超過設定閾值，從而快速提取邊界點。通過對閾值設值分析，不同點云數據的邊界提取實驗及幾種方法間比較，該方法不受點云形狀影響，均能較好提取邊界點，且優于其他3種算法。結果表明該方法在保證原始點云特征信息的前提下，可較好提取邊界點，提高后續點云重建速度與效率。

關鍵詞：

點云；邊界點；閾值；效率；點云形狀

中圖分類號： P232； TP391.41 文獻標志碼：A

0引言

三維激光掃描技術能快速獲取掃描對象表面的大量點云數據，基于點云數據對物體進行三維重建，已成為當前逆向工程三維重構領域中的研究熱點[1-2]。采用切片技術的點云重建方法可將原始無序的三維點云數據轉化為具有層次結構、有序組織形式的數據，使得對物體的重建更加有效。切片技術就是用一組平行平面沿著某一給定方向、給定間隔對三維點云進行劃分，再將平面兩側的點云投影到平面上，從而將三維點云轉換為二維點集，在此基礎上再進行物體表面重建[3-4]，因此，如何提取投影在平面上點云的邊界點，成為后續物體表面三維重構的重要一步。

文獻[5]中，在提取平面邊界點時提出以判斷點為中心，將其鄰域采用不同的分割方法分成若干區域，再根據某一區域內是否有散亂點作為判斷準則來提取邊界點。由于每進行一次判斷，需要將其他散亂點遍歷一次，導致運算速度慢，效率低。文獻[6]中，將判斷點的鄰域從4個均勻區域增至8個均勻的區域，提取效果有所改善，仍不能較好提取凹陷區域邊界點。文獻[7]在提取三維邊界散亂點云時，采用R*tree對點云數據進行動態聚類劃分，依據k近鄰點以最小二乘法擬合該點集的切平面，將k個點投影在切平面上，再以點云中最大夾角與設定的閾值為依據來提取邊界點；但文中未對閾值大小的設置進行分析，也未考慮平面上點云形狀對提取效果的影響。文獻[8]中，通過計算判斷點周邊點之間的夾角，采用角度標準差作為邊界點判斷依據來提取三維點云邊界點；但該方法對離散、分布不均勻的點云提取效果不理想。文獻[9]中，在提取保留三維邊界點時，將近鄰點投影到某一平面上，然后選取若干參考面，統計位于參考面兩側的點數，以兩側點數之差作為判斷的標準；但該方法不適合平面點云邊界點的提取。文獻[10]中，采用矢量合成的思想，將判斷點周圍點構成矢量并單位化后進行疊加，依據疊加后的矢量的模與矢量數量的比值作為判斷準則；但該算法對非均勻分布的點云及凹陷處的邊界點提取效果不理想。

以上一些算法在提取三維邊界點時，效果較好；但經實驗將其計算思想應用在提取二維平面散亂點的邊界點時，則提取效果不理想，尤其是有凹陷的點云形狀邊界的提取。同時計算過程復雜、繁瑣，如文獻[5]需要進行區域劃分。本文在文獻[7]基礎上進行改進，提出一種基于多閾值的提取平面點云邊界點算法，不需對近鄰點進行區域劃分。同時對本方法中閾值的設定進行了分析，實驗結果表明，依據本文的閾值設置原則，使用本文方法能夠較好地提取邊界點。

1多閾值提取平面點云邊界點的方法

1.1近鄰點的檢索

二維平面散亂點云沒有明顯的幾何分布特征，點與點之間也沒有拓撲關系，因此當點云數量巨大，尋找k近鄰點時，有必要建立點云間的拓撲關系，提高搜索速度。常用方法有柵格法、八叉樹法、空間單元格法和KDtree法等[11]。由于切片面上點云數據量較小，且為二維點云數據，因此采用簡單的柵格法建立點間的拓撲關系，提高k近鄰點搜索速度。柵格大小的設置與點云密度有關，如果設置不當，會影響計算效率[11]。

點云密度ρ的估算方法如下所示。

在點云中隨機抽取n個點，對每個點gi（i=1，2，…，n）在點云中搜索距其距離最近的m個點，并計算每點到其距離Di，求其平均值即為點云密度估計值：

ρ=（∑ni=1∑mj=1Dji）/（n×m）（1）

依此密度值設置柵格尺寸，在獲取得到近鄰點后，可依據距離對近鄰點排序，獲得最近的k個近鄰點[12]。

1.2點集的幾何特性分析

判斷點P的近鄰點分布，若近鄰點偏向一側，則認為P點為邊界點；反之若近鄰點均勻分布在其四周，該點則為內部點。P點為內部點和外部點的點集分布如圖1所示。

邊界點具有不確定性，即邊界點是否處在邊界線上，是不確定的，如圖2所示，因此，不能提取出完全與邊界一致的點，而只能提取出其近似邊界點，但要在最大限度上保留其邊界特征[5]。

1.3判斷過程

依據預測點云密度ρ設置柵格尺寸，獲取k個近鄰點。以當前判斷點P為中心，分別連接各個近鄰點，以選定的某一方向為起始方向，順時針旋轉到近鄰點所在的線上，得到k個與之對應的旋轉角，如圖3所示。

2實驗及分析

2.1實驗說明

本文使用Leica C10三維激光掃描儀采集數據，選取5類點云數據，分布情況如圖5所示。其中：圖5（a）對應具有一定弧度、近似圓形的點云數據；圖5（b）中則將矩形與圓形進行組合；圖5（c）為任意多邊形點云數據；圖5（d）為線狀點與面狀點組合；圖5（e）中則是更加復雜的組合。其中各點云的點數及密度情況如表1所示。同時增加了文獻[6]、[8]、[10]對應方法與本文方法的比較。由于各算法效率與獲得鄰近點方法及鄰近點數量有關，因此采用兩套標準比較：第1套標準中，各方法獲取鄰近點方法與數量相同的前提下比較，不考慮最終提取效果；第2套是在最大限度提取邊界點前提下比較，統計各種算法耗時。

2.2實驗結果

算法是在PC機配置為AMD E350 Processor 1.60GHz，內存為3.0GB，Windows 7 32位系統上運行，使用Matlab 7.0進行編程，冒泡法進行排序，使用本文方法分別對圖5中的點云數據進行邊界點的提取，均采用k=15、α0=120°的閾值，其提取的邊界點效果如圖6所示。表2為4種算法在第1兩套標準下耗時統計結果，圖7中的（a）～（d）則為4種算法在第2套標準下的提取結果。其中：圖7（a）為文獻[6]算法提取結果，圖7（b）為文獻[8]算法提取結果，圖7（c）為文獻[10]算法提取結果，圖7（d）為本文的提取結果。

2.3實驗結果分析

由表2中的4種算法耗時可知，由于第1套標準未考慮提取效果，因此4種算法在第1種標準下耗時均少于在第2套標準下的耗時。由圖7（a）～（d）可知，本文算法與文獻[6]對應的算法提取效果最好；但本文算法在提取內部邊界點上要優于文獻[6]算法。

在第1套標準下，4種算法均需計算獲取鄰近點。但文獻[10]矢量合成算法，只需計算矢量并求和，計算過程相比其余3種算法計算相鄰點間夾角要簡單；同時也少了計算鄰點與指定方向的夾角這一步驟，因此在不考慮提取效果的前提下效率最高；同時計算過程所占存儲空間最小。而文獻[8]角度方差法由于計算角度方差相對于夾角計算要復雜，因此效率最低。而文獻[6]區域劃分法由于增加對點距離限制條件，因此效率次于本文算法，運行內存也高于本文算法。而在第2套標準下，由于各算法中參數大小的改變，導致最后提取耗時相差較大；但本文算法效率依舊高于其余3種。

由圖6可知，在使用相同的閾值k、α0進行邊界點提取，均能提取點云邊界點。其中圖6（a）～（d）提取效果相對于圖6（e）較好，圖6（e）中內部邊界點遺漏較多。結果表明在點云密度ρ、閾值k、α0大致相同的情況下，提取效果與點云形狀有關。

平面多邊形可分為凸多邊形和凹多邊形，對于帶有弧段的多邊形，可以認為其是無窮多邊形。對于凸多邊形，其定義為：設pi=（xi，yi）（（xi，yi）∈R2（i=1，2，…，n，且pn+1=p1））是構成多邊形的n個頂點，若線段pi-1pi與pipi+1所形成的內角（即該多邊形圍成的有界區域內所形成的角）不大于180°，則稱點pi為凸點，否則稱為凹點；若n個頂點都是凸點，則稱該多邊形為凸多邊形（n≥4），用O表示[14]。其具有所有內角均是劣角、外角均是優角的性質，因此對于凸多邊形的點云提取邊界點時，由于內部點四周較均勻分布著離散點，因此設置夾角閾值α0要接近但要小于180°，則可較好保留邊界點。如果大于或非常接近180°，則會將位于直線上的邊界點忽略掉，只能提取出拐點處的邊界點，效果不好。

對于凹多邊形，由于不具有凸多邊形的外角均為優角的性質，因此在設置閾值時，需要依據點云形狀來具體設置。凹、凸多邊形的點云形狀如圖8所示，黑色部分為散亂點云分布情況。在凹多邊形中，有兩個外角β1、 β2，均是劣角。如果仍是選擇角度閾值接近180°，當取一定數量近鄰點時，相鄰點間夾角就會均會小于180°，則會將β1、 β2頂點處的邊界點給忽略掉，因此需重新設置角度閾值。針對此種情況，本文處理方法是統計多邊形中凹角中劣角的個數，然后估計劣角的角度大小范圍，在此基礎上設置角度閾值，使其接近外角中最小的角度，該圖中β1較小，則設置的閾值應接近β1。

2.3.1凹、凸多邊形點云提取實驗

本次實驗選取的數據是表1中（e）中所對應的數據，此點云形狀中，外輪廓邊界點云對應凸多邊形，內部輪廓對應凹多邊形。根據點云所構成的形狀來看，內部輪廓中凹角中最小角度大致為45°，因此本次選取角度閾值α0=45°、60°、120°、150°、180°。同時為了研究k大小對角度設置的影響，選取了k=5，15，25進行組合實驗。其中在α0=45°時，在原有的k值基礎上，增加了k=30，35，40，50四組實驗。其閾值與序號對應關系如表3所示，表3與圖9存在重復表達的現象，故刪除表3。提取效果如圖9所示。

2.3.2結果分析

圖9中的19種提取結果進一步驗證了2.3節中閾值設置原則的可行性，對于該點云外輪廓的提取，由于外輪廓邊界點所構成的形狀為凸多邊形，因此在k不斷變化時，只要α0值不是很接近或大于180°，則外輪廓邊界點就會較好地保留；而如果大于180°，則會將位于一條直線上的邊界點給忽略掉，而只保留凸角處的邊界點。圖9中的（d）、（i）、（n），拐角處邊界點保留較好，位于直線上的邊界點則遺漏較多。對于內邊界點的提取，則角度閾值α0接近或等于45°時提取效果比較好。α0為120°、150°和180°的內部邊界點遺漏嚴重，甚至沒有達到提取效果。如需兩者兼顧，同時提取外輪廓與內邊界點，則需將k值增大，α0接近凹角最小角范圍，圖9（g）與圖9（l）提取效果的差別在于前者k值小于后者。同時在提取實驗過程中發現，α0越接近凹角最小值，則k值需相應增加，才能提取出理想的邊界效果。由圖4的本文算法計算流程可知，k值的大小直接決定著程序的運算量，因此在提取過程中，在保證邊界信息準確的前提下，避免設置α0過小，k值過大組合的情況。如圖9（k）、（p）要達到圖9（q）的提取效果，k值由25，30增加到35，無形中增加計算量。圖9（i）相對圖9（q），較好地保留了邊界點；但計算量相對于圖9（k）沒有增加。同時并非k值越大，提取的效果會越好；相反有時會降低效率。圖9（r）、（s）相對圖9（q）雖k值增加，提取效果并沒提高；但計算量卻增加不少。

3結語

本文提出的基于多閾值提取二維平面點云邊界點的算法，依據最近鄰點閾值k與相鄰點夾角閾值α0對平面點云進行邊界點提取，并對兩個閾值的設置進行分析，也給出了凹凸多邊形的閾值設置原則。這可應用于以后對不同情況提取邊界點和后續基于切片技術的點云數據重建。由于本文未對不同點云密度的情況進行研究，而點云密度可能影響到本文算法閾值的設置，因此在接下來的工作中會研究點云密度對閾值的影響，使該算法適用性更廣。

參考文獻：

[1]

程效軍，方芳.基于形態學的散亂點云輪廓特征線提取[J].同濟大學學報（自然科學版），2014，42（11）：1738-1743.（CHENG X J， FANG F. Morphologybased scatter point cloud contour extraction [J]. Journal of Tongji University （Natural Science）， 2014， 42（11）： 1738-1743.）

[2]

徐工，程效軍.基于小波技術的散亂點云自適應壓縮算法[J].同濟大學學報（自然科學版），2013，41（11）：1738-1743.（XU G， CHENG X J. Adaptive reduction algorithm of scattered point clouds based on wavelet technology [J]. Journal of Tongji University （Natural Science）， 2013， 41（11）： 1738-1743.）

[3]

柯映林，王青.反求工程中的點云切片算法研究[J].計算機輔助設計與圖形學學報，2005，17（8）：1798-1802.（KE Y L， WANG Q. Research on point cloud slicing technology in reverse engineering [J]. Journal of Computer Aided Design & Computer Graphics， 2005， 17（8）： 1798-1802.）

[4]

WU Y F， WONG Y S， LOH H T， et al. Modeling cloud data using an adaptive slicing approach [J]. ComputerAided Design， 2004， 36（3）： 231-240.

[5]

邱澤陽，宋曉宇，張樹生，等.一種新的散亂數據邊界點提取方法[J].機械科學與技術，2004，23（9）：1037-1039.（QIU Z Y， SONG X Y， ZHANG S S， et al. A new method for the extraction of boundary points from scatter data points [J]. Mechanical Science and Technology， 2004， 23（9）： 1037-1039.）

[6]

齊維毅，丁言鎂，吳麗娟.四邊形網格劃分過程中的邊界其提取與優化算法實現[J].小型微型計算機系統，2007，28（10）：1861-1864.（QI W Y， DING Y M， WU L J. Realization of the edge points searching and edges optimization in quadrangular mesh generation process [J]. Journal of Chinese Computer Systems， 2007， 28（10）： 1861-1864.）

[7]

孫殿柱，范志先，李延瑞.散亂數據點云邊界特征自動提取算法[J].華中科技大學學報（自然科學版），2008，36（8）：82-84.（SUN D Z， FAN Z X， LI Y R. Automatic extraction of boundary characteristic from scatter data [J]. Journal of Huazhong University of Science and Technology （Nature Science）， 2008， 36（8）： 82-84.）

[8]

劉章明，董慧穎，王金濤.一種非封閉自由曲面的點云邊界提取算法[J].計算機應用，2009，29（Z2）：247-249.（LIU Z M， DONG H Y， WANG J T. Boundary extraction algorithm of point clouds on nonclosed freeform surface [J]. Journal of Computer Applications， 2009， 29（Z2）： 247-249.）

[9]

黃文明，肖朝霞，溫佩芝，等.保留邊界的點云簡化方法[J].計算機應用，2010，30（2）：348-350.（HUANG W M， XIAO Z X， WEN P Z， et al. Point cloud simplification with boundary points reservation [J]. Journal of Computer Applications， 2010， 30（2）： 348-350.）

[10]

陳義仁，王一賓，彭張節，等.一種改進的散亂點云邊界特征點提取算法[J].計算機工程與應用，2012，48（23）：177-181.（CHEN Y R， WANG Y B， PENG Z J， et al. Improved algorithm for extraction of boundary characteristic point from scattered point cloud [J]. Computer Engineering and Applications， 2012， 48（23）： 177-181.）

[11]

吳祿慎，晏海平，陳華偉，等.一種基于散亂點云的邊界提取算法[J].計算機應用與軟件，2014，31（11）：264-268.（WU L S， YAN H P， CHEN H W， et al. A boundary extraction algorithm based on scattered point cloud [J]. Computer Applications and Software， 2014， 31（11）： 264-268.）

[12]

楊振清，雍永磊.基于點云切片的邊界提取[J].計算機應用與軟件，2014，31（1）：221-224.（YANG Z Q， YONG Y L. Boundary extraction based on point cloud slices [J]. Computer Applications and Software， 2014， 31（1）： 221-224.）

[13]

龔沛曾，楊志強，陸慰民.Visual Basic程序設計教程[M].3版.北京：高等教育出版社，2007：106-107.（GONG P Z， YANG Z Q， LU W M. An Introduction to Visual Basic Programming [M]. 3rd ed.Beijing： Higher Education Press， 2007： 106-107.）

[14]

戴光明，王茂才，彭雷.凸多邊形最小面積四邊形包圍盒算法[J].華中科技大學學報（自然科學版），2006，34（6）：71-73.（DAI G M， WANG M C， PENG L. Algorithm for smallest quadrangle encasing box of convex polygon [J]. Journal of Huazhong University of Science and Technology （Nature Science）， 2006， 34（6）： 71-73.）