廖中平 劉科 向雨 蔡晨光

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

關(guān)鍵詞：

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

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

0引言

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

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

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

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

1.1近鄰點的檢索

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

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

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

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

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

1.2點集的幾何特性分析

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

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

1.3判斷過程

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

2實驗及分析

2.1實驗說明

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

2.2實驗結(jié)果

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

2.3實驗結(jié)果分析

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

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

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

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

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

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

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

2.3.2結(jié)果分析

圖9中的19種提取結(jié)果進一步驗證了2.3節(jié)中閾值設(shè)置原則的可行性，對于該點云外輪廓的提取，由于外輪廓邊界點所構(gòu)成的形狀為凸多邊形，因此在k不斷變化時，只要α0值不是很接近或大于180°，則外輪廓邊界點就會較好地保留；而如果大于180°，則會將位于一條直線上的邊界點給忽略掉，而只保留凸角處的邊界點。圖9中的（d）、（i）、（n），拐角處邊界點保留較好，位于直線上的邊界點則遺漏較多。對于內(nèi)邊界點的提取，則角度閾值α0接近或等于45°時提取效果比較好。α0為120°、150°和180°的內(nèi)部邊界點遺漏嚴重，甚至沒有達到提取效果。如需兩者兼顧，同時提取外輪廓與內(nèi)邊界點，則需將k值增大，α0接近凹角最小角范圍，圖9（g）與圖9（l）提取效果的差別在于前者k值小于后者。同時在提取實驗過程中發(fā)現(xiàn)，α0越接近凹角最小值，則k值需相應(yīng)增加，才能提取出理想的邊界效果。由圖4的本文算法計算流程可知，k值的大小直接決定著程序的運算量，因此在提取過程中，在保證邊界信息準確的前提下，避免設(shè)置α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結(jié)語

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

參考文獻：

[1]

程效軍，方芳.基于形態(tài)學的散亂點云輪廓特征線提取[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]

徐工，程效軍.基于小波技術(shù)的散亂點云自適應(yīng)壓縮算法[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].計算機輔助設(shè)計與圖形學學報，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]

邱澤陽，宋曉宇，張樹生，等.一種新的散亂數(shù)據(jù)邊界點提取方法[J].機械科學與技術(shù)，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]

齊維毅，丁言鎂，吳麗娟.四邊形網(wǎng)格劃分過程中的邊界其提取與優(yōu)化算法實現(xiàn)[J].小型微型計算機系統(tǒng)，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]

孫殿柱，范志先，李延瑞.散亂數(shù)據(jù)點云邊界特征自動提取算法[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].計算機應(yīng)用，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].計算機應(yīng)用，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]

陳義仁，王一賓，彭張節(jié)，等.一種改進的散亂點云邊界特征點提取算法[J].計算機工程與應(yīng)用，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].計算機應(yīng)用與軟件，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].計算機應(yīng)用與軟件，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程序設(shè)計教程[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.）