保留邊界特征的點云簡化算法

趙偉玲， 謝雪冬， 程俊廷

(黑龍江科技學院 現(xiàn)代制造工程中心，哈爾濱 150027)

0 引言

為精確快速地獲取工件表面的尺寸信息，非接觸的三維光學掃描設備已被廣泛應用在生產(chǎn)線上。由測量所得到的通常包含大量數(shù)據(jù)點的數(shù)據(jù)能很好地描述物體表面信息，但是大規(guī)模的點云給準確快速的三維重建或其他的后續(xù)處理帶來了很大的困難。為更有效地表達和繪制三維點云模型，需要對點云進行合理的簡化。近年來，國內(nèi)外學者提出了針對不同類型點云的簡化算法。對于掃描線點云數(shù)據(jù)，可以采用均勻采樣法、角度偏差法、弦高差和角度弦高法等[1]。針對網(wǎng)格點云數(shù)據(jù)，Chen等[2]提出了一種減少三角網(wǎng)格數(shù)目，刪除部分數(shù)據(jù)點的方法。針對目前最常見的散亂點云數(shù)據(jù)類型，Sun等[3]提出包圍盒法簡化數(shù)據(jù)。洪軍[4]改進了包圍盒算法，利用包圍盒法構(gòu)造分割面，由分割面將數(shù)據(jù)點云處理成按掃描線存儲的“結(jié)構(gòu)化”測量數(shù)據(jù)，再利用角度—弦高聯(lián)合準則法逐線精簡。殷金祥[5]利用數(shù)據(jù)點周圍以R為半徑的球進行測量，得到測量球內(nèi)的臨近點數(shù)量作為該數(shù)據(jù)點面密度，以面密度確定曲面凹凸彎曲程度，進而確定點的簡化距離閾值和精簡數(shù)據(jù)點集。張麗艷[6]提出基于三種原則的簡化算法，即按簡化后的個數(shù)、點云密度以及刪除一點后引起的法向偏差進行簡化。Lee等[7]以數(shù)據(jù)點的法矢為判據(jù)，對點云進行空間柵格細分，在每個柵格上選擇1個特征點。近幾年，有文獻[8－10]提出了基于聚類和相似性的點模型簡化方法。

筆者研究了一種在保留邊界特征基礎上簡化點云的有效方法。該算法，首先利用三維柵格劃分法計算出每個數(shù)據(jù)點的近鄰，通過球擬合法計算出點的法向量和曲率，接著通過投影點個數(shù)比值法找到并保留點云邊界，然后根據(jù)具體情況設定所需閾值，對非邊界點進行分類，通過對點的曲率與平均曲率比較、近鄰保留點與近鄰點個數(shù)比例，進行點云簡化。

1 點云預處理

1.1 點云的空間劃分與鄰域搜索

測量得到的散亂數(shù)據(jù)只包含數(shù)據(jù)點的三維坐標值，點與點之間沒有明顯的幾何分布信息，因此，必須建立數(shù)據(jù)點云之間的拓撲關系以及搜索每個點對應的k個最近鄰域。文中采用空間柵格劃分法搜索點的k個鄰域，此方法在求某點的k鄰近時，不需要在整個點云中搜索，而只需在相應的小立方體柵格中搜索即可。

1.1.1 空間柵格劃分

數(shù)據(jù)點p的最近k個點稱為p的k－鄰域，記為Nbhd(p)。首先，讀入點云數(shù)據(jù)，計算測量點云數(shù)據(jù)的x、y、z坐標的最小值和最大值，得到所有數(shù)據(jù)的最小長方體空間[xmin，xmax]，[ymin，ymax]，[zmin，zmax]，通過柵格邊長L的設定，將長方體包圍盒按三個坐標方向劃分成m×n×l個小立方體柵格，其中m=(xmax－ xmin)/L，n=(ymax－ ymin)/L，l=(zmaxzmin)/L。然后，把每個數(shù)據(jù)點分配到相應的小立方體柵格(mp，np，lp)中，其中mp=(xp－xmin)/L，np=(yp－ymin)/L，lp=(zp－ zmin)/L。

將數(shù)據(jù)點的序號追加到該立方體柵格對應的鏈表中。由于每個子空間內(nèi)含有數(shù)據(jù)點的個數(shù)是未知的，為了節(jié)省存儲空間采用鏈表的結(jié)構(gòu)來存儲。先給每個子空間分配一個固定長度的存儲空間，如果存儲空間不夠可以動態(tài)地再次分配。

1.1.2 k最近鄰域搜索方法

首先，計算該點所在立方體柵格的索引號，然后，在其所在的立方體柵格及其頂點相鄰的上下、左右、前后共27個小立方體柵格中查找k個最鄰近的點，并按相鄰點到xp的距離dist由小到大的順序進行排序。如果在這27個柵格中相鄰點不夠k個，這樣就必須繼續(xù)搜索外層柵格，即與27個柵格外側(cè)表面相鄰的柵格，達到k個點便可以結(jié)束。

1.2 不需調(diào)整方向的點法向量與曲率計算

在數(shù)據(jù)簡化中，點云法向量和曲率的計算是關鍵預備工作之一。測量數(shù)據(jù)很密集，在小范圍內(nèi)理想意義上所在的曲面應該是很光滑的，所以任何點的局部鄰域都可以用平面或者曲面進行很好地擬合。但是擬合平面得到的法向量方向是兩個方向，這樣就需要對法向量方向進行適當?shù)恼{(diào)整。曲率計算常見的方法是基于法向量的局部坐標系，利用最小二乘法擬合簡化拋物面，計算得到擬合拋物面的兩個主曲率，其中兩個主曲率的平均值稱為平均曲率。由于平均曲率更能反應曲面的彎曲特性，所以，一般取平均曲率作為曲面曲率的衡量標準。這樣點p的曲率定義為點k近鄰擬合拋物面的平均曲率。

上述介紹求取點云的法向量需要進行方向調(diào)整，常見計算曲率的方法也比較復雜。在曲率大的地方可用半徑小的球面擬合，在曲率小的位置可用半徑大的球面擬合，所以在近鄰小范圍內(nèi)可選用球擬合。球面的法向量方向是唯一的，免去了法向量調(diào)整這一過程，也可以很簡便得到對應點的曲率，為此，用球面擬合得到點的法向量和曲率。

點 p 的距離最近 k 個點 pi(xi，yi，zi)(i=1，2，…，k)稱為p的k－鄰域，記為Nbhd(p)。假設這k個點以及點p分布在一個球面上，理想的球面方程為

式中:x0、y0、z0——球面參數(shù);

Op(x0，y0，z0)——球心坐標;

R——球半徑。

將球面方程展開可得其一般形式:

F(x，y，x)=x2+y2+z2+ax+by+cz+d=0，可得:

通過點p及其k個近鄰點，利用最小二乘法擬合可以得到球心坐標和球半徑。

推導過程:首先，計算

通過判定可知，M為實對稱的半正定矩陣，可以求取矩陣的廣義逆矩陣M－1。

然后，求出 F=M－1·N，假設求出的 F=[f(0)f(1)f(2)f(3)]T，則

將點p及其k個近鄰點，代入式(1)的球心坐標值和半徑表達式，可求出參數(shù) x0、y0、z0、R。接著求出k個近鄰點以及點 p(xp，yp，zp)和的平均坐標pave(xave，yave，zave)，其中，

則法向量為 pave－Op，相應的坐標為(xave－x0，yavey0，zave－z0)，則曲率為 1/R。

重復以上步驟，求出點云中每個數(shù)據(jù)點的法向量和曲率，并把法向量和曲率保存到相應的位置。

2 散亂點云簡化算法

2.1 邊界提取

由于點云的邊界數(shù)據(jù)反映了樣件的邊界特征，而邊界特征對于曲面重構(gòu)是十分重要的，因而在點云數(shù)據(jù)簡化過程中對邊界數(shù)據(jù)點進行保護。常見的邊界提取方法是，把點近鄰投影到擬合的最小二乘平面上，分析投影點之間分布的均勻性，提取邊界。均勻性的判斷標準是角度標準差，但是計算量很大，會耗費大量時間。故，文中基于這種思想，采用直接比較坐標值，這樣可以節(jié)省大量計算時間。

按照點云預處理的空間柵格劃分方法把三維點云數(shù)據(jù)分配到相應的柵格內(nèi)，柵格內(nèi)有點云數(shù)據(jù)則設置為1，沒有點云數(shù)據(jù)則設置為0，這樣就把三維點云可以看成是三維圖像。利用三維圖像提取邊界技術(shù)，提取出三維圖像邊界，圖像邊界對應的三維數(shù)據(jù)則是點云的粗邊界。在粗邊界的基礎上進行三維數(shù)據(jù)邊界提取，如圖1所示，通過點p的坐標及對應的法向量，構(gòu)造其對應的平面，并將點p的近鄰投影到該平面上，然后過點p分別做平行于 xOy、xOz、yOz的三個平面 xpy、xpz、ypz，并計算出位于這三個平面兩側(cè)的點數(shù)，只要其中一個平面的兩側(cè)點數(shù)差與k的比值大于設定閾值，則該點記為邊界點。

圖1 點p邊界點及投影Fig.1 Boundary points and projection of point p

2.2 點云簡化算法

數(shù)據(jù)簡化最佳效果是使簡化后的點云具有較少的數(shù)據(jù)量，同時又能保證不丟失物體表面的細節(jié)特征，且運算速度越快越好。數(shù)據(jù)點在簡化后的疏密應該隨著曲面曲率的變化而變化，即曲率變化越大，數(shù)據(jù)點應越多，反之曲率變化越小，數(shù)據(jù)點就應該越少。因此在簡化過程中，必須在保證被測物體幾何特征的前提下，根據(jù)物體曲面的曲率變化對數(shù)據(jù)進行非均勻簡化，文中提出保留邊界的點云簡化方法。

2.2.1 簡化算法

該算法首先構(gòu)造散亂點云的局部拓撲信息，通過空間柵格法快速找到點的k近鄰;通過球面擬合得到該點相應的法向量和曲率，接著找到點云的邊界點并保留;對非邊界點，根據(jù)文中提出的曲率簡化原則進行數(shù)據(jù)簡化，直至遍歷完點云數(shù)據(jù)的所有點。該算法不僅可以完整保存實物模型整體輪廓，而且能夠最大限度地保證模型區(qū)域特征。

2.2.2 曲率簡化原則

曲率反映了曲面的基本特性，曲率可作為點云數(shù)據(jù)簡化的閾值準則。對曲率按照大小進行排序，根據(jù)實際情況和結(jié)果要求設定閾值，對曲率分為幾種不同等級，文中采用對曲率分為大中小三類曲率，從大到小區(qū)域標記為1、2、3，進而便對點云數(shù)據(jù)進行對應的分類和分片處理。其中曲率小的區(qū)域3是近似平面等一些變化平滑的區(qū)域，這部分可以刪除較多的點;而曲率最大的區(qū)域1則是變化比較尖銳的區(qū)域，說明有較多的特征區(qū)域，需要保留較多的點，所以在分區(qū)的每部分，設定的閾值是不同的。

在每一分區(qū)中，按照曲率從大到小進行點云處理，并求取每一個點的k近鄰曲率平均值。如果點的k近鄰點保留邊界點和非邊界點的個數(shù)之和已經(jīng)超過近鄰點總數(shù)的設定比例1內(nèi)，則刪除此點。如果點的k近鄰點保留邊界點和非邊界點的個數(shù)之和低于近鄰點總數(shù)的設定比例2內(nèi)，則保留此點。如果點的曲率大于曲率平均值的系數(shù)，則保留此點，其中區(qū)域1的曲率需要保留較多的點，因此，系數(shù)1較小;區(qū)域3的變化比較平滑，系數(shù)3較大，根據(jù)具體需要保留點的個數(shù)對系數(shù)1、系數(shù)3進行自適應的調(diào)節(jié)。這樣就在曲率較高的區(qū)域，保留了較多的點，相反則在曲率較小的區(qū)域保留了較少的采樣點。

3 實例與結(jié)果分析

使用自主研發(fā)的設備對雕塑及某加工零件進行非接觸式三維測量，對三維點云進行去噪、拼合等處理后，得到的三維點云作為文中應用實例。利用球面擬合算法得到有方向的法向量和曲率，以及利用文中提出的簡化方法對點云數(shù)據(jù)進行了簡化。圖2是黑龍江科技學院自主研發(fā)的三維測量儀器照片，為了驗證問題，對雕塑點云進行詳細的分析。為了說明算法應用的普遍性，對某加工零件進行分析。

圖2 自主研發(fā)的三維測量設備Fig.2 Independent development 3D measuring equipment

3.1 雕塑模型分析

3.1.1 法向量的比較

計算三維點云的法向量和曲率，分別利用平面擬合以及球面擬合算法得到其結(jié)果。為了更加清晰的說明法向量方向性，選擇一小部分點云的法向量進行比較說明。文中選擇的是雕塑的帽子一部位，圖3是法向量的顯示效果圖，其中圖3a是通過平面擬合得到法向量，但是沒有調(diào)整方向的顯示效果圖，圖3b是通過球面擬合得到的法向量顯示效果圖。為了更加清晰看到該方法的效果，特別選取一部分點云的兩種法向量進行效果顯示。圖4是把兩個方法得到的法向量進行方向性比較，其是帶有點云序號的兩種計算方法得到的法向量顯示，圖4a的法向量方向基本一致，處于基本重合的狀態(tài)。圖4b法向量方向基本相反，兩向量基本處于180°。通過比較分析可見，該算法得到的法向量和平面擬合調(diào)整后的法向量大小基本一致，誤差在允許范圍之內(nèi)，達到了預想的效果，還可以節(jié)省所有點云數(shù)據(jù)法向量方向調(diào)整的時間，為數(shù)據(jù)處理節(jié)省了時間。

圖3 法向量顯示效果Fig.3 Effect drawing of normal vector

圖4 兩種法向量方向性比較Fig.4 Two normal vector directional comparison

3.1.2 曲率的比較

在簡化過程中，點云曲率的計算是很重要的一個環(huán)節(jié)。通過平面擬合得到法向量曲面擬合方法得到的平均曲率作為點云的曲率，是一種常見計算點云曲率的方法，稱為方法一。但是其過程復雜，還影響數(shù)據(jù)處理的速度，故選取文中的方法計算曲率。表1是把常見方法的計算的曲率和文中計算得到的曲率進行大小值的比較，可以看出曲率的誤差在允許范圍之內(nèi)。

表1 部分點云的曲率值比較及誤差分析Table 1 Value comparison and error analysis of curvature about several points cloud

3.1.3 簡化效果分析

圖5是某雕塑的點云數(shù)據(jù)通過調(diào)節(jié)設定閾值的大小得到不同簡化程度的點云。圖5a是原始點云含有279 610個點的效果圖，圖5b～d是簡化后分別含有144 541、89 903、47 108個點的效果圖，由圖5可見，設定閾值的大小決定了簡化后點云數(shù)量的多少。從圖5b和圖5c簡化的效果得到在鼻子、帽子、手等表面變化陡峭的部位保留了較多的點，而在面部等表面變化平緩的部位保留的點相對稀疏，但是圖5b比圖5c保留了較多的數(shù)據(jù)點;由圖5d的效果圖可見其丟失了一部分特征，這是因為閾值設定的不合適，刪除掉了很多的點。具體采用多大閾值，需要根據(jù)預想效果去設定。對圖5b～d的點云個數(shù)和原始點云的個數(shù)進行比例計算，分別為51.7%、32.1%、16.8%。

3.2 加工零件分析

圖6是某加工零件的點云數(shù)據(jù)通過調(diào)節(jié)設定閾值的大小得到不同簡化程度的點云。圖6a是原始點云含有391 715個點的效果圖。圖6b～d是簡化后分別含有253 601、137 858、73 826個點的效果圖，由圖可見，使用文中的簡化方法設定閾值很關鍵。從圖6b和圖6c簡化效果看到圓孔、棱邊界處等曲率變化大的地方保留了較多點，而在平坦處等曲率小的部位保留了較少點;圖6b在比較平滑部位也保留了比較多的點。由圖6d的效果圖可見，因為閾值設定的不合適還是丟失了一部分特征。將圖6b～d的點云個數(shù)和原始點云的個數(shù)進行比例計算，分別為64.7%、35.2%、18.9%。

圖5 不同閾值某雕塑簡化效果Fig.5 Effect of sculpture simplified in different threshold

圖6 不同閾值加工零件簡化效果Fig.6 Effect of machining parts simplified in different threshold

實驗結(jié)果表明:該算法適用于多種三維點云的簡化，在點云簡化過程中，通過閾值設定的不同，得到不同的簡化效果圖以及不同的簡化比例。通過簡化效果的比較，可以得出，使用文中的簡化方法設定閾值很關鍵，根據(jù)實際需求設定閾值并達到所需的簡化要求。多組點云數(shù)據(jù)的簡化實驗可以看出，簡化比例為25%～40%。通過對閾值進行合適的設定達到了在保留邊界特征的基礎上，在曲率較大的地方保留相對多的點，在曲率較小的地方保留相對少的點。該簡化效果能夠滿足后期數(shù)據(jù)要求。

4 結(jié)束語

利用三維柵格法可構(gòu)造散亂點云的拓撲關系，通過球擬合計算點的法向量、曲率以及投影點個數(shù)比值，得到點云邊界并保留邊界點，然后對其余點進行分類。根據(jù)具體情況進行閾值設定，通過點的曲率與平均曲率、近鄰保留點個數(shù)與近鄰點個數(shù)的比較，實現(xiàn)了數(shù)據(jù)簡化，并對具有不同表面特征的點云數(shù)據(jù)進行了驗證。多組點云數(shù)據(jù)的實驗簡化比例為25% ～40%，在保留邊界特征的基礎上，曲率較大的地方保留相對多的點，曲率較小的地方保留相對少的點。結(jié)果表明:該算法易于實現(xiàn)，運行速度快，數(shù)據(jù)簡化原則靈活，調(diào)節(jié)設定閾值可得不同簡化程度的點云，能準確識別散亂點云的邊界特征點，在保留幾何特征基礎上對點云數(shù)據(jù)具有很好的簡化效果，在實際工程應用中具有一定的應用價值。

[1]張舜德，朱東波，盧秉恒.反求工程中三維幾何形狀測量及數(shù)據(jù)預處理[J].機電工程技術(shù)，2001(1):7－10.

[2]CHEN Y H，NEG C T，WANG Y Z.Data reduction in integrated reverse engineering and rapid prototyping[J].International Journal of Computer Integrated Manufacture，1999，12(2):97－103.

[3]SUN W，BRADLEY C，ZHANG Y F.Cloud data modeling employing a unified non-redundant triangle mesh[J].Computer Aided Design，2001，33(2):183－193.

[4]洪 軍，丁玉成，曹 亮，等.逆向工程中的測量數(shù)據(jù)精簡技術(shù)研究[J].西安交通大學學報，2004(7):661－664.

[5]殷金祥，陳關龍.一種基于面密度概念的數(shù)據(jù)簡化方法[J].現(xiàn)代制造工程，2003，23(8):39－40.

[6]張麗艷，周儒榮，蔡煒斌，等.海量測量數(shù)據(jù)簡化技術(shù)研究[J].計算機輔助設計與圖形學學報，2001，13(11):1119－1023.

[7]LEE K H，WOO H，SUK T.Point data reduction using 3D grids[J].Advanced Manufacturing Technology，2001(18):201 －210.

[8]SONG H，F(xiàn)ENG H Y.A global clustering approach to point cloud simplification with a specified data reduction ratio[J].Computer Aided Design，2008(40):281－292.

[9]王仁芳，張三元，葉修梓.基于相似性的點模型簡化算法[J].浙江大學學報:工學版，2009(3):448－454.

[10]倪小軍，姜曉峰，葛亮.特征保留的點云數(shù)據(jù)自適應精簡算法[J].計算機應用與軟件，2011(8):38－39.

[11]黃文明，肖朝霞，溫佩芝，等.保留邊界的點云簡化方法[J].計算機應用，2010(2):348－350.