曹 爽，趙顯富，馬 文

(南京信息工程大學(xué)遙感與測(cè)繪工程學(xué)院,江蘇 南京 210044)

為實(shí)現(xiàn)基于點(diǎn)云數(shù)據(jù)的工業(yè)構(gòu)件加工質(zhì)量檢測(cè)，需利用三維激光掃描儀掃描工業(yè)構(gòu)件，得到的點(diǎn)云數(shù)據(jù)有著很高的精度，但也包含大量的冗余點(diǎn)。這些冗余點(diǎn)會(huì)給計(jì)算機(jī)建模、傳輸，以及構(gòu)件的快速檢測(cè)帶來(lái)阻礙。工業(yè)構(gòu)件的幾何特征是對(duì)其進(jìn)行檢測(cè)的基礎(chǔ)，在保證被測(cè)構(gòu)件幾何特征的前提下，對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行精簡(jiǎn)，可以減少存儲(chǔ)空間，提高計(jì)算速度，突出建模特征，對(duì)曲面重構(gòu)的速度和效率可以產(chǎn)生重要的影響[1,2]。

國(guó)內(nèi)外學(xué)者在點(diǎn)云數(shù)據(jù)精簡(jiǎn)方面作了很多研究，比較有代表性的有3類(lèi)：第一類(lèi)，最初由Martin[3]提出的基于均勻格網(wǎng)劃分的散亂點(diǎn)云數(shù)據(jù)精簡(jiǎn)方法，但該方法不適用于非均勻分布的點(diǎn)云；第二類(lèi)，基于空間包圍盒[4-5]的散亂點(diǎn)云數(shù)據(jù)精簡(jiǎn)方法，空間包圍盒法與均勻格網(wǎng)劃分思路基本一致，只是在選點(diǎn)上進(jìn)行了改進(jìn)，這種方法不適用于曲率變化較大且形狀復(fù)雜的數(shù)據(jù)點(diǎn)云,可能導(dǎo)致某些過(guò)渡區(qū)域的重要數(shù)據(jù)點(diǎn)的丟失；第三類(lèi)，基于曲率采樣的散亂點(diǎn)云數(shù)據(jù)精簡(jiǎn)方法[6-8]，利用不同的擬合法求解局部曲率，再根據(jù)曲率偏差對(duì)點(diǎn)云進(jìn)行精簡(jiǎn)，曲率能夠很好地反映點(diǎn)云的特征，但曲率的計(jì)算復(fù)雜，影響精簡(jiǎn)速度。

本文針對(duì)工業(yè)構(gòu)件提出一種基于曲面變化的點(diǎn)云精簡(jiǎn)算法。在建立點(diǎn)云空間鄰域關(guān)系后，通過(guò)計(jì)算點(diǎn)的曲面變化將點(diǎn)云分成特征不同的3個(gè)區(qū)域，對(duì)不同點(diǎn)區(qū)域設(shè)定權(quán)值，利用點(diǎn)的曲面變化定義近似特征點(diǎn)閾值，將曲面變化大于該值的點(diǎn)保留，小于該值的點(diǎn)進(jìn)一步按照屬于不同的特征區(qū)域計(jì)算其精簡(jiǎn)比率，由精簡(jiǎn)比率定義距離閾值，完成精簡(jiǎn)。

1 基于曲面變化的工業(yè)構(gòu)件點(diǎn)云數(shù)據(jù)精簡(jiǎn)

1.1 散亂點(diǎn)云空間拓?fù)潢P(guān)系確定

手持掃描儀獲取的點(diǎn)云為散亂點(diǎn)云，每個(gè)數(shù)據(jù)點(diǎn)只具有三維坐標(biāo)值的信息，沒(méi)有明確的空間鄰域信息，不利于鄰域數(shù)據(jù)點(diǎn)的搜索，而鄰域數(shù)據(jù)點(diǎn)的搜索速度正是影響散亂數(shù)據(jù)處理和曲面重構(gòu)效率的主要因素之一，因此必須建立數(shù)據(jù)點(diǎn)間的空間拓?fù)潢P(guān)系以搜索每個(gè)點(diǎn)的K鄰近。常用的空間柵格法的思路是，通過(guò)三維散亂點(diǎn)云的空間劃分確定散亂點(diǎn)云的空間位置，將點(diǎn)云數(shù)據(jù)按X、Y、Z劃分成M、N、T個(gè)部分。散亂點(diǎn)云空間柵格化后，不但可以求出每個(gè)點(diǎn)所在的柵格位置，而且可以確定每個(gè)柵格中點(diǎn)云的個(gè)數(shù)。

1.2 點(diǎn)的曲面變化

Paulyt[9]等提出了曲面變化(surface variation)概念來(lái)衡量曲面的彎曲程度，記為δk，它可以直接從散亂點(diǎn)云數(shù)據(jù)中計(jì)算出來(lái)。曲面變化能夠近似表示該點(diǎn)附近的曲面變化程度和特征明顯度，處于特征明顯地段的點(diǎn)的曲面變化率大，相反處于特征不明顯、不尖銳的地方的點(diǎn)的曲面變化率小。在表達(dá)曲面幾何特征方面曲面變化非常接近于曲率，且不需要進(jìn)行復(fù)雜的曲率計(jì)算。

設(shè)P點(diǎn)為散亂點(diǎn)云中一點(diǎn),M3×3為P及其K鄰近點(diǎn)所構(gòu)成的協(xié)方差矩陣，P點(diǎn)的曲面變化δk可以由式(3)求出。

(1)

(2)

(3)

式中，P1、P2、…、Pk為P的K鄰近點(diǎn)；λ0、λ1、λ2為協(xié)方差矩陣M3×3的特征值，且λ0為最小特征值。實(shí)際上，特征值λ0、λ1、λ2分別表示了點(diǎn)云數(shù)據(jù)在3個(gè)主方向的變化程度。由于M3×3是對(duì)稱矩陣，因此λ0、λ1、λ2都為正值，那么δk(P)的取值范圍就是[0,1/3]。當(dāng)P及P的K鄰近點(diǎn)各向均勻分布時(shí),δk(P)=0。因此，δk(P)的取值反映了曲面在P點(diǎn)沿其法向量方向離開(kāi)切平面的程度。

1.3 點(diǎn)集劃分

將所有點(diǎn)按照各自的曲面變化值δk分成3個(gè)集合Qi(i=1,2,3)，分別為平面鄰域類(lèi)型、次特征鄰域類(lèi)型和特征鄰域類(lèi)型，并使每個(gè)區(qū)間的點(diǎn)的數(shù)目相等。對(duì)于曲面變化最小的平面鄰域類(lèi)型點(diǎn)集Q1，其特征最弱，點(diǎn)對(duì)模型的影響程度也最低；曲面變化次大的次特征鄰域類(lèi)型點(diǎn)集Q2，區(qū)域特征稍強(qiáng)，點(diǎn)的影響程度也稍強(qiáng)；曲面變化最大的特征鄰域類(lèi)型點(diǎn)集Q3，區(qū)域特征最明顯，相對(duì)屬于特征部分，點(diǎn)的影響程度也最強(qiáng)。

1.4 點(diǎn)云精簡(jiǎn)策略

所有點(diǎn)云精簡(jiǎn)的基本法則在于特征明顯處的點(diǎn)盡量保留，精簡(jiǎn)率小，而在特征不明顯處相對(duì)可以進(jìn)行多精簡(jiǎn)。定義近似特征點(diǎn)閾值如下

(4)

式中，δ(Pi)為點(diǎn)Pi的曲面變化；N為點(diǎn)云中的點(diǎn)數(shù)；α為調(diào)節(jié)因子，根據(jù)點(diǎn)云表面曲面變化情況依經(jīng)驗(yàn)設(shè)置。如果點(diǎn)云中的點(diǎn)的曲面變化大于ρ，認(rèn)為該點(diǎn)為近似特征點(diǎn)，則該點(diǎn)不被刪除保留下來(lái)。

對(duì)于曲面變化小于特征點(diǎn)閾值ρ的點(diǎn)，暫時(shí)標(biāo)記為不保留，按照其δ(Pi)進(jìn)行降序排列，從大到小逐點(diǎn)在其K鄰域內(nèi)判斷如何精簡(jiǎn)。按上文所述，將所有的點(diǎn)按照曲面變化的值劃分為3個(gè)集合，3個(gè)集合按照其中的點(diǎn)對(duì)于點(diǎn)云整體形狀的影響程度從小到大排列，分別為Q1、Q2、Q3。定義精簡(jiǎn)比率如下

(5)

式中，NQ1、NQ2、NQ3分別代表該點(diǎn)K鄰域中分別屬于Q1、Q2、Q3集合的點(diǎn)的數(shù)目；μ1、μ2、μ3分別為3類(lèi)點(diǎn)集的權(quán)重系數(shù)，權(quán)重系數(shù)可根據(jù)精簡(jiǎn)情況自行調(diào)整，按照點(diǎn)集中點(diǎn)的影響力程度設(shè)置，在此分別設(shè)為0.9、0.6、0.3。計(jì)算得出的點(diǎn)的R值的大小能夠更好地反映單個(gè)點(diǎn)鄰域特征明顯的點(diǎn)所占權(quán)值的高低情況。如果周?chē)卣髅黠@，那么該點(diǎn)附近的精簡(jiǎn)率就要低一些。再根據(jù)該點(diǎn)的精簡(jiǎn)比率R計(jì)算出該點(diǎn)的精簡(jiǎn)距離閾值

(6)

式中，d為初始設(shè)定距離，對(duì)于不同的點(diǎn)云模型，為求得更好的效果，一般先根據(jù)點(diǎn)云的密度估算一個(gè)d，然后再進(jìn)行調(diào)整。遍歷點(diǎn)P的K鄰域，計(jì)算每點(diǎn)與P點(diǎn)的距離dPi(i=1,2,…,K)，當(dāng)dPi

2 精簡(jiǎn)邊界保護(hù)

邊界對(duì)于工業(yè)構(gòu)件點(diǎn)云數(shù)據(jù)的后續(xù)處理特別是曲面的重構(gòu)十分重要，利用曲率變化作為準(zhǔn)則精簡(jiǎn)時(shí)，盡管可以在保證幾何特征的前提下精簡(jiǎn)，但被測(cè)物體的邊界還是會(huì)受到影響。

周煜[10]等提出的一種基于立方體的邊界保護(hù)方法，結(jié)合曲面變化進(jìn)行改進(jìn)。在空間柵格劃分后，對(duì)立方體空間進(jìn)行二值化處理，用函數(shù)g(x,y,z)表示立方體空間是否包含數(shù)據(jù)點(diǎn)，若g(x,y,z)=0，則表示立方體空間內(nèi)不包含有數(shù)據(jù)點(diǎn)，定義為空體；若g(x,y,z)=1，則表示立方體空間內(nèi)包含有數(shù)據(jù)點(diǎn)，定義為實(shí)體。

(7)

在空間柵格化后的空間中，每個(gè)立方體G存在26個(gè)相鄰立方體。用(x,y,z)表示G，(i,j,k)表示G拓?fù)浞较颍瑒tG的26個(gè)鄰接立方體可由(x+i,y+j,z+j)表示，其中i∈[-1,1],j∈[-1,1],k∈[-1,1]，且(i,j,k)不同時(shí)為0。構(gòu)造函數(shù)QΔ(x,y,z)表示G的26個(gè)鄰接立方體中實(shí)體的數(shù)目，即

g(x+i,y+j,z+k)]

(8)

如果QΔ(x,y,z)=0，說(shuō)明G沒(méi)有實(shí)體與其相鄰，稱G為孤立立方體?；谇孀兓牟钪禈?gòu)建G與26個(gè)鄰接立方體的曲面變化差函數(shù)UΔ

(9)

由式(9)可以看出，G的26個(gè)鄰接立方體：實(shí)體數(shù)目越少，則QΔ越少，此時(shí)UΔ值顯著增大；G與相鄰立方體的曲面變化差越大，式(9)中的分子越大，則UΔ值增大。因此，可根據(jù)曲面變化差UΔ值判別G是否為邊界立方體。設(shè)定邊界特征參數(shù)σ，比較曲面變化差與邊界特征參數(shù)，若UΔ>σ，則認(rèn)為G為邊界立方體，精簡(jiǎn)時(shí)對(duì)其數(shù)據(jù)點(diǎn)予以保護(hù)。

3 試驗(yàn)與分析

利用本文提出的基于曲面變化的點(diǎn)云精簡(jiǎn)方法進(jìn)行點(diǎn)試驗(yàn)。試驗(yàn)1數(shù)據(jù)為斯坦福大學(xué)三維掃描庫(kù)中著名的bunny點(diǎn)云數(shù)據(jù)，試驗(yàn)2數(shù)據(jù)為利用手持三維激光掃描儀掃描的盒子點(diǎn)云數(shù)據(jù)，試驗(yàn)3數(shù)據(jù)為手持三維激光掃描儀掃描的工業(yè)零件點(diǎn)云數(shù)據(jù)。對(duì)上述數(shù)據(jù)采用基于曲率的精簡(jiǎn)方法處理，再與本文的精簡(jiǎn)算法從精簡(jiǎn)的簡(jiǎn)度、速度及精度3方面進(jìn)行比較[11]。

為保證本文算法和基于曲率精簡(jiǎn)的精簡(jiǎn)率大致在相同的前提下進(jìn)行3組試驗(yàn)數(shù)據(jù)分析，精簡(jiǎn)前后數(shù)據(jù)的點(diǎn)的個(gè)數(shù)及精簡(jiǎn)率統(tǒng)計(jì)見(jiàn)表1，精簡(jiǎn)結(jié)果如圖1—圖11所示，其中圖7和圖11是進(jìn)行了邊界保護(hù)的精簡(jiǎn)結(jié)果。

表1 點(diǎn)云精簡(jiǎn)前后簡(jiǎn)度對(duì)照

由圖可知，試驗(yàn)1 bunny點(diǎn)云因?yàn)楸砻媲首兓鄬?duì)復(fù)雜，基于曲率的精簡(jiǎn)方法處理的結(jié)果并沒(méi)有突出特征，而本文方法在特征處保留的點(diǎn)比較多；試驗(yàn)2精簡(jiǎn)后在盒子平面處的點(diǎn)云，本文方法處理的點(diǎn)均勻且達(dá)到了精簡(jiǎn)的目的；試驗(yàn)3零件精簡(jiǎn)后的結(jié)果相近，但本文方法相對(duì)基于曲率的精簡(jiǎn)方法處理的結(jié)果在特征處保證了更多的點(diǎn)，可保證后續(xù)建模的需要。綜上可知，在精簡(jiǎn)率相同的前提下，本文方法可以達(dá)到與基于曲率的精簡(jiǎn)方法相似的處理效果，并且更好地保護(hù)了特征。

圖1 bunny點(diǎn)云

圖2 基于曲率精簡(jiǎn)后bunny點(diǎn)云

圖3 本文方法精簡(jiǎn)后bunny點(diǎn)云

圖4 盒子點(diǎn)云

圖5 基于曲率精簡(jiǎn)后盒子點(diǎn)云

圖6 本方方法精簡(jiǎn)后盒子點(diǎn)云(邊界未保護(hù))

圖7 本方方法精簡(jiǎn)后盒子點(diǎn)云(邊界保護(hù))

圖8 工業(yè)零件點(diǎn)云

圖9 基于曲率精簡(jiǎn)后零件點(diǎn)云工業(yè)零件點(diǎn)云

統(tǒng)計(jì)本文精簡(jiǎn)方法和基于曲率的精簡(jiǎn)方法處理3個(gè)點(diǎn)云數(shù)據(jù)的時(shí)間見(jiàn)表2。由表2可知,本文的方法相對(duì)于基于曲率的精簡(jiǎn)方法精簡(jiǎn)速度有很大提高。

圖10 本文算法精簡(jiǎn)后工業(yè)零件點(diǎn)云(未加邊界保護(hù))

圖11 本文算法精簡(jiǎn)后工業(yè)零件點(diǎn)云(加邊界保護(hù))

點(diǎn)云數(shù)據(jù)本文方法基于曲率精簡(jiǎn)方法bunny1065520753盒子610214158零件68640118462

精簡(jiǎn)的最終目的是在保證精度的前提下提高簡(jiǎn)度與速度。筆者利用體積法[12]對(duì)本文方法的精簡(jiǎn)精度進(jìn)行分析評(píng)價(jià)。選取工業(yè)零件點(diǎn)云數(shù)據(jù)和本文基于曲面變化精簡(jiǎn)并加入邊界保護(hù)處理后的點(diǎn)云數(shù)據(jù),以及基于曲率精簡(jiǎn)后的零件點(diǎn)云數(shù)據(jù)進(jìn)行評(píng)價(jià)，統(tǒng)計(jì)數(shù)據(jù)見(jiàn)表3。從表中可知，在精簡(jiǎn)率達(dá)到30%的情況下，本文方法與基于曲率的方法處理后的點(diǎn)云與原點(diǎn)云體積變化率只有0.06%，說(shuō)明精簡(jiǎn)后體積損失很小，且達(dá)到了精簡(jiǎn)效果。

表3 工業(yè)零件精簡(jiǎn)前后體積數(shù)據(jù)表

4 結(jié) 語(yǔ)

本文針對(duì)工業(yè)構(gòu)件提出了基于曲面變化的點(diǎn)云精簡(jiǎn)算法，通過(guò)計(jì)算點(diǎn)的曲面變化將點(diǎn)云分成特征不同的3個(gè)區(qū)域，對(duì)不同點(diǎn)區(qū)域設(shè)定權(quán)值，利用點(diǎn)的曲面變化定義近似特征點(diǎn)閾值，將小于閾值的點(diǎn)按照屬于不同的特征區(qū)域計(jì)算其精簡(jiǎn)比率，由精簡(jiǎn)比率定義距離閾值完成精簡(jiǎn)。試驗(yàn)結(jié)果表明，在近似的精簡(jiǎn)比率前提下，本文的點(diǎn)云精簡(jiǎn)方法在精簡(jiǎn)精度上可以達(dá)到與基于曲率精簡(jiǎn)方法相同的效果，且計(jì)算速度更快，更好地保持了幾何特征；加入邊界保護(hù)處理后，精簡(jiǎn)對(duì)邊界影響也比較小，可以滿足后續(xù)建模要求。在表達(dá)曲面幾何特征方面曲面變化非常接近于曲率，因此該方法能夠盡可能地保留區(qū)域特征明顯的點(diǎn)，且不需要進(jìn)行復(fù)雜的曲率計(jì)算，精簡(jiǎn)效率比較高。