李學(xué)兵，胡天亮+，劉忠強(qiáng)，馬嵩華

(1.山東大學(xué) 機(jī)械工程學(xué)院，山東 濟(jì)南 250061；2.高效潔凈機(jī)械制造教育部重點(diǎn)實(shí)驗(yàn)室(山東大學(xué))，山東 濟(jì)南 250061；3.機(jī)械工程國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心(山東大學(xué))，山東 濟(jì)南 250061；4.山東大學(xué) 深圳研究院,廣東 深圳 518000)

1 問(wèn)題的提出

隨著三維掃描設(shè)備的發(fā)展，點(diǎn)云獲取技術(shù)越發(fā)成熟，成本越來(lái)越低，三維點(diǎn)云在逆向工程及工業(yè)測(cè)量等領(lǐng)域的應(yīng)用越來(lái)越廣泛[1-2]。逆向工程可應(yīng)用于工件的產(chǎn)品改型設(shè)計(jì)、質(zhì)量分析檢測(cè)等領(lǐng)域以提高生產(chǎn)效率[3]，然而常用的三維點(diǎn)云是散亂三維點(diǎn)的集合，不存在任何拓?fù)潢P(guān)系，不能很好地表達(dá)工件的形狀尺寸等信息。為更好表達(dá)工件外形特征和尺寸，點(diǎn)云數(shù)據(jù)需要進(jìn)行曲面生成來(lái)構(gòu)造出易于逆向和測(cè)量的網(wǎng)格模型。

在從點(diǎn)云到生成曲面模型的過(guò)程中，法向量估計(jì)和基于法向量的曲面重建是最基本的兩個(gè)環(huán)節(jié)，國(guó)內(nèi)外對(duì)此進(jìn)行了一系列研究，具體如下：

(1)法向量估計(jì) 曲面重建算法依賴(lài)法向量估計(jì)與調(diào)整得到的法向信息，其結(jié)果直接關(guān)系曲面重建的成敗。目前，根據(jù)法向量估計(jì)方法原理的不同主要分為基于局部表面擬合的方法和基于Delaunay/Voronoi的方法[4]?；贒elaunay/Voronoi的法向量估計(jì)方法計(jì)算效率低、耗費(fèi)內(nèi)存大，且容易受離群噪聲點(diǎn)影響導(dǎo)致計(jì)算精度差，不適合處理諸如CAD模型等含有尖銳特征區(qū)域的點(diǎn)云數(shù)據(jù)。QUENTIN等[5]提出VCM (Voronoi covariance measure)算法，該算法較為復(fù)雜且計(jì)算效率較低。在基于局部表面擬合的法向量估計(jì)方法方面，HOPPE等[6]通過(guò)求取給定點(diǎn)的K鄰域來(lái)擬合切平面，將該切平面的法向量作為點(diǎn)云表面該點(diǎn)的法向量，該方法雖然在尖銳特征處的估計(jì)精度偏低，但是算法效率高、性能穩(wěn)定，對(duì)后續(xù)的貪婪投影三角化曲面重建算法影響不大，能夠滿(mǎn)足需要；CAZALS等[7]提出對(duì)K鄰域進(jìn)行Jet擬合的方法，Jet指截?cái)嗟奶├照归_(kāi)式，包含法向量、曲率等局部幾何特征，相對(duì)于主成分分析(Principal Components Analysis, PCA)方法，該方法在高曲率處的計(jì)算精度有所提升，但是計(jì)算比較復(fù)雜。另外，法向量的指向往往不一致，導(dǎo)致法向量估計(jì)得到的結(jié)果存在二義性，需要進(jìn)行調(diào)整。最小生成樹(shù)法[8]是目前使用比較廣泛的法向量調(diào)整算法，該算法調(diào)整一個(gè)點(diǎn)時(shí)需要遍歷所有點(diǎn)，因此計(jì)算效率較低。針對(duì)特征簡(jiǎn)單的工件，本文提出效率較高的法向量調(diào)整算法。

(2)曲面重建 隨著點(diǎn)云處理技術(shù)的成熟，曲面重建技術(shù)得到快速發(fā)展[9-10]。曲面重建的早期研究主要集中于顯式重建，顯式重建將整體點(diǎn)云數(shù)據(jù)的子集作為頂點(diǎn)，對(duì)頂點(diǎn)進(jìn)行插值生成三角形，然后對(duì)點(diǎn)云進(jìn)行三角剖分得到重建的曲面[11-13]；隱式重建也是三維點(diǎn)云曲面重建的重要內(nèi)容，泊松重建就是經(jīng)典的隱式重建算法，KAZHDAN等[14-15]和HOPPE等[16]提出泊松重建算法并不斷進(jìn)行改進(jìn)，該算法通過(guò)對(duì)點(diǎn)云進(jìn)行插值處理得到近似曲面。顯式和隱式曲面重建的對(duì)比如表1所示。

表1 隱式與顯式曲面重建對(duì)比

針對(duì)法向量估計(jì)與調(diào)整計(jì)算效率較低的問(wèn)題，本文采用PCA方法求取點(diǎn)云的法向量，并提出一種基于廣度優(yōu)先搜索的法向量調(diào)整算法，以得到正確的法向信息，為后續(xù)的曲面重建算法提供保證。在曲面重建方面，顯式曲面重建算法適用于重建尖銳特征，在平緩特征處表現(xiàn)不佳；隱式曲面重建算法適用于重建光滑曲面，但是會(huì)使工件的尖銳特征變得光滑。針對(duì)這一問(wèn)題，本文基于工件特征并充分結(jié)合顯式和隱式曲面重建的優(yōu)缺點(diǎn)開(kāi)展研究，以得到更優(yōu)的曲面重建方法。

2 曲面生成整體思路

綜合分析隱式和顯式曲面重建的優(yōu)缺點(diǎn)可知，現(xiàn)有曲面重建方法各有所長(zhǎng)，沒(méi)有一種普適性的通用算法。工業(yè)應(yīng)用中的工件形態(tài)千差萬(wàn)別，但是其表面特征卻只分為曲面變分較小的平緩特征和曲面變分較大的尖銳特征兩種。針對(duì)不同的特征，用同一種曲面重建算法必然效果不佳，因此本文結(jié)合工件特征提出一種曲面重建優(yōu)化方法，以提高點(diǎn)云重建的精度。

本文用結(jié)構(gòu)簡(jiǎn)單的常見(jiàn)工件為研究對(duì)象，對(duì)所提方法進(jìn)行論述，其設(shè)計(jì)圖紙如圖1a所示。算法流程是首先使用三維掃描設(shè)備獲取工件的點(diǎn)云數(shù)據(jù)，然后對(duì)點(diǎn)云進(jìn)行一系列處理，最終得到工件的曲面模型，如圖1b所示。

首先通過(guò)對(duì)點(diǎn)云進(jìn)行降采樣來(lái)減少點(diǎn)云數(shù)據(jù)；然后求取工件表面每個(gè)點(diǎn)的法向量，調(diào)整法向量的方向指向工件一側(cè)，并根據(jù)曲面變分從點(diǎn)云中區(qū)分出尖銳部分；接著對(duì)尖銳部分的點(diǎn)云進(jìn)行貪婪投影三角形重建，對(duì)整體點(diǎn)云進(jìn)行泊松重建，并根據(jù)整體和尖銳點(diǎn)云剔除冗余和尖銳部分的三角面片；最后將兩部分三角面片合并，得到最終的曲面模型。

3 點(diǎn)云數(shù)據(jù)獲取及其預(yù)處理

3.1 點(diǎn)云數(shù)據(jù)獲取

點(diǎn)云獲取方法主要分為接觸式和非接觸式兩種。接觸式采集主要用三坐標(biāo)機(jī)在工件表面采點(diǎn)，其測(cè)量精度較高，但是測(cè)量時(shí)間長(zhǎng)、成本高，獲得的數(shù)據(jù)點(diǎn)少，不能滿(mǎn)足高精度三維重建的需要；非接觸式采集主要包括三維結(jié)構(gòu)光測(cè)量、激光測(cè)量等，其因測(cè)量速度快、成本低且能獲得大量數(shù)據(jù)點(diǎn)而廣泛應(yīng)用于工業(yè)界。

本文點(diǎn)云均通過(guò)如圖2所示的基于雙目結(jié)構(gòu)光的三維掃描設(shè)備獲得，雙目相機(jī)為大恒DH-HV1351UM，鏡頭為16 mm焦距，投影儀分辨率為1 920×1 280。

通過(guò)三維掃描設(shè)備采集的點(diǎn)云數(shù)據(jù)如圖3所示，因?yàn)楣ぜ撞颗c工作臺(tái)表面接觸，無(wú)法被掃描到，所以得到的是一個(gè)非封閉點(diǎn)云數(shù)據(jù)，本文以該數(shù)據(jù)為研究對(duì)象對(duì)所提方法進(jìn)行論述。

3.2 點(diǎn)云數(shù)據(jù)降采樣

通常點(diǎn)云數(shù)據(jù)中包含的數(shù)據(jù)點(diǎn)數(shù)高達(dá)幾十萬(wàn)個(gè)，這將會(huì)在后續(xù)操作中大大降低點(diǎn)云的處理速度，因此需要對(duì)原始點(diǎn)云進(jìn)行降采樣以減少數(shù)據(jù)量，目前比較常用的是基于體素網(wǎng)格的降采樣方法[17]。首先將點(diǎn)云數(shù)據(jù)劃分為三維體素網(wǎng)格，然后計(jì)算網(wǎng)格內(nèi)所有點(diǎn)的重心，用于代替網(wǎng)格內(nèi)的所有點(diǎn)。假設(shè)某網(wǎng)格內(nèi)的所有數(shù)據(jù)點(diǎn)組成的集合為{Pi},i∈{1,2,…,n}，n為該網(wǎng)格內(nèi)數(shù)據(jù)點(diǎn)的個(gè)數(shù)，則該網(wǎng)格的重心

(1)

該方法充分考慮了點(diǎn)云的空間特征，可以在保證點(diǎn)云所含信息基本不變的情況下，大大減少點(diǎn)云的數(shù)據(jù)量，提高后續(xù)算法操作的效率。

3.3 點(diǎn)云法向量估計(jì)與調(diào)整

法向量估計(jì)是點(diǎn)云處理過(guò)程中重要的一步，目前有多種點(diǎn)云法向量估計(jì)算法[8,18]，其中PCA適用于處理掃描工件得到的稠密點(diǎn)云。法向量估計(jì)與調(diào)整方法如圖4所示。

整體思路為求取給定點(diǎn)的K鄰域，用K鄰域擬合一個(gè)平面，將平面的法向量作為該點(diǎn)的法向量[6]。首先從所有數(shù)據(jù)點(diǎn)中求出距離給定點(diǎn)最近的k個(gè)點(diǎn)作為該點(diǎn)的K鄰域，k的大小可根據(jù)實(shí)際數(shù)據(jù)及不同應(yīng)用場(chǎng)景進(jìn)行調(diào)整；然后根據(jù)這k個(gè)點(diǎn)構(gòu)建協(xié)方差矩陣，并求解該矩陣的特征值和特征向量；最后用廣度優(yōu)先的策略遍歷所有點(diǎn)，并在遍歷過(guò)程中調(diào)整法向量方向，使其指向一致。

3.3.1K近鄰求解

3.3.2 協(xié)方差矩陣的構(gòu)建求解

三維點(diǎn)云共有3個(gè)坐標(biāo)，即有3個(gè)隨機(jī)變量x,y,z，3個(gè)隨機(jī)變量自由組合可得協(xié)方差矩陣

Cov(x,y,z)=

(2)

求得特征根λi和特征向量υi，對(duì)特征根進(jìn)行排序，有λ0<λ1<λ2,λ0對(duì)應(yīng)的法向量υ0為切平面的法向，即該點(diǎn)的法向量。

該點(diǎn)處的曲面變分[19]

(3)

式中λ0,λ1,λ2為給定點(diǎn)沿對(duì)應(yīng)特征法向的偏移量，類(lèi)似于用曲率描述曲面的微分性質(zhì)，可用其衡量點(diǎn)云的局部微分性質(zhì)，即衡量點(diǎn)云的平緩程度。

3.3.3 法向量調(diào)整

法向量估計(jì)之后，一部分法向量指向工件外側(cè)，一部分指向工件內(nèi)側(cè)，法向量指向不一致將導(dǎo)致泊松重建失敗，因此必須對(duì)所有法向量進(jìn)行調(diào)整，使其指向工件一側(cè)。

本文提出一種基于隊(duì)列的廣度優(yōu)先算法，能夠在搜索過(guò)程中不斷調(diào)整法向量，有較高的計(jì)算效率，算法流程圖如圖5所示。算法通過(guò)判斷向量相乘是否為正來(lái)調(diào)整法向量，假設(shè)給定點(diǎn)的法向量為ni,待調(diào)整的點(diǎn)的法向量為nj，若ni·nj>0，則兩個(gè)法向量共向，不做調(diào)整；若ni·nj<0,則兩個(gè)法向量異向，反轉(zhuǎn)nj。遍歷方法則是選取一點(diǎn)作為法向量調(diào)整的起始點(diǎn)，從起始點(diǎn)開(kāi)始采用廣度優(yōu)先策略向整個(gè)點(diǎn)云擴(kuò)展，在擴(kuò)展過(guò)程中完成對(duì)法向量的調(diào)整。從最終的法向量估計(jì)結(jié)果來(lái)看，該方法能夠正確高效地求解點(diǎn)云法向，為后續(xù)的曲面重建提供保障。

4 基于工件特征的曲面重建優(yōu)化

本文重點(diǎn)研究顯式重建中的貪婪投影三角形重建算法和隱式重建中的泊松重建算法，分別對(duì)工件的平緩和尖銳特征進(jìn)行重建，最終得到精度較高的曲面模型。

4.1 貪婪投影三角形和泊松重建

貪婪投影三角形算法是一種基于貪婪算法的網(wǎng)格曲面重建算法；泊松重建算法是一種經(jīng)典的隱式曲面重建算法，其通過(guò)將曲面重建轉(zhuǎn)化為泊松方程來(lái)求解問(wèn)題，該算法要求點(diǎn)云的法向量一致且朝向統(tǒng)一指向工件外側(cè)或內(nèi)側(cè)，如果法向量缺失或指向不統(tǒng)一，則重建效果不好，甚至導(dǎo)致失敗。

4.2 算法優(yōu)化方案

圖6所示為采用兩種算法重建的結(jié)果，其中泊松重建得到曲面模型，重建后的尖銳特征變得比較光滑；通過(guò)貪婪投影三角形重建算法得到曲面模型，雖然保留了棱角處的尖銳特征，但是平緩特征沒(méi)有泊松重建得到的曲面精確光滑。

貪婪投影三角形算法對(duì)尖銳和平緩特征的重建效果沒(méi)有明顯區(qū)別，而泊松算法在平緩處的重建效果很好，在尖銳處卻很差，因此本文對(duì)二者各取所長(zhǎng)。整體點(diǎn)云采用泊松重建剔除尖銳特征和冗余的三角面片，僅保留平緩處的曲面模型，尖銳特征處的點(diǎn)云采用貪婪投影三角形重建，最后將二者重建的結(jié)果合并，得到工件最終的曲面模型。

4.3 尖銳特征處理

工件平緩特征的曲面變分較小，尖銳特征的曲面變分較大，根據(jù)第3章法向量估計(jì)時(shí)得到的曲面變分，可以很容易地區(qū)分尖銳特征和平緩特征。

實(shí)踐發(fā)現(xiàn)，用式(4)定義分割閾值能夠更精確地定義平緩和尖銳特征。

(4)

式中：m為比例因子，默認(rèn)為1便可有效區(qū)分平緩和尖銳特征，而且通過(guò)調(diào)整m值可以區(qū)分得更精確;n為數(shù)據(jù)點(diǎn)的個(gè)數(shù)。

數(shù)據(jù)點(diǎn)的曲面變分大于T則為尖銳特征，小于T則為平緩特征，最終提取出的尖銳特征如圖7所示。

5 實(shí)驗(yàn)結(jié)果分析

5.1 kd樹(shù)算法效率分析

由于用點(diǎn)云數(shù)據(jù)構(gòu)造kd樹(shù)可以提高近鄰求取等后續(xù)算法的效率，現(xiàn)以階梯軸的點(diǎn)云數(shù)據(jù)(k=18)為例分別基于數(shù)組和kd樹(shù)測(cè)試求取近鄰及后續(xù)操作所需的時(shí)間，結(jié)果如表2所示?？梢?jiàn)，對(duì)于大規(guī)模點(diǎn)云，基于數(shù)組的算法效率過(guò)低，甚至無(wú)法滿(mǎn)足實(shí)際需要，kd樹(shù)則大大提高了點(diǎn)云處理的效率。

表2 kd樹(shù)與數(shù)組算法效率比較 s

5.2 法向量估計(jì)與調(diào)整結(jié)果分析

不同的法向量估計(jì)算法有不同的算法效率和性能，現(xiàn)針對(duì)常用工件對(duì)引言中提到的的法向量估計(jì)算法進(jìn)行測(cè)試，所耗時(shí)間如表3所示，估計(jì)效果如圖10～圖12所示。

表3 法向量估計(jì)效率比較 s

根據(jù)實(shí)驗(yàn)結(jié)果可知，VCM算法耗費(fèi)的時(shí)間最長(zhǎng)，而且由于易受噪聲影響導(dǎo)致圖12中的階梯臺(tái)數(shù)據(jù)法向估計(jì)出現(xiàn)錯(cuò)誤。PCA算法和Jet算法均為基于局部擬合的算法，由于工件尖銳處存在倒角，從結(jié)果來(lái)看二者估計(jì)的精度相當(dāng)，但是PCA算法的效率比Jet算法更高。

下面對(duì)法向調(diào)整的最小生成樹(shù)算法和本文算法進(jìn)行對(duì)比分析，所耗時(shí)間如表4所示，估計(jì)效果如圖13和圖14所示。

表4 法向量調(diào)整效率比較

從實(shí)驗(yàn)結(jié)果可以看出，本文算法與最小生成樹(shù)算法均能正確調(diào)整法向。本文算法的效率明顯高于最小生成樹(shù)算法，但是因?yàn)楸疚乃惴▋H針對(duì)結(jié)構(gòu)簡(jiǎn)單的工件，未考慮形狀復(fù)雜的情況，為提高算法效率進(jìn)行了折中，所以沒(méi)有最小生成樹(shù)算法的應(yīng)用范圍廣泛。

5.3 曲面重建結(jié)果分析

在逆向工程中，曲面擬合精度體現(xiàn)在原始數(shù)據(jù)和重建得到的曲面模型之間的偏差，一般采用原始點(diǎn)云到模型表面的距離來(lái)衡量。假設(shè)Dj表示點(diǎn)Pj到其模型表面的最小距離，則最大值為點(diǎn)云距離曲面模型的最大距離，如式(5)所示；均值為點(diǎn)云距離曲面模型的平均距離，用于表征曲面模型的整體精度，如式(6)所示；標(biāo)準(zhǔn)差為點(diǎn)云距離曲面模型的標(biāo)準(zhǔn)差，用于表征曲面模型精度的穩(wěn)定性，如式(7)所示。

Dmax=max{Dj},j∈[1,n]；

(5)

(6)

(7)

式中n表示數(shù)據(jù)點(diǎn)的個(gè)數(shù)。采用上述標(biāo)準(zhǔn)對(duì)3種曲面重建算法得到的模型進(jìn)行評(píng)估，結(jié)果如表5所示。

表5 階梯軸曲面重建精度 mm

根據(jù)實(shí)驗(yàn)結(jié)果，本文算法的Dmax與另兩種算法結(jié)果相近，表示合并后的模型中某一數(shù)據(jù)點(diǎn)距離其最近面片的最大距離，是整體數(shù)據(jù)點(diǎn)的一個(gè)極大值，對(duì)整體精度影響不大；Dstd較另兩種算法有所下降，說(shuō)明本文算法得到的模型與點(diǎn)云距離的離散程度更小，整體模型的穩(wěn)定性更好；Dmean小于另兩種算法，可知本文算法得到的曲面模型的整體精度最好。本文方法的重建效果如圖15所示，相對(duì)于圖6所示的重建效果也有所提升，然而由于兩種曲面重建算法和合并算法本身的局限性，也可能會(huì)出現(xiàn)網(wǎng)格空洞和網(wǎng)格拼接錯(cuò)位等模型失真現(xiàn)象，業(yè)界針對(duì)這一問(wèn)題已有比較成熟的解決方法，即將結(jié)果放到Geomagic Studio中修復(fù)。綜上所述，本文算法結(jié)合工件特征吸取兩種重建算法的優(yōu)點(diǎn)，提高了曲面生成的整體精度。

6 結(jié)束語(yǔ)

本文基于工件特征提出法向量估計(jì)及調(diào)整算法，并對(duì)曲面重建算法進(jìn)行了優(yōu)化。該算法首先通過(guò)降采樣來(lái)降低點(diǎn)云數(shù)據(jù)的數(shù)據(jù)量，以提高后續(xù)操作的效率；然后采用PCA方法求取法向量，并根據(jù)廣度優(yōu)先策略調(diào)整方向，為曲面重建奠定了基礎(chǔ)；接著通過(guò)泊松算法處理工件的平緩特征，通過(guò)貪婪投影三角形算法處理工件的尖銳特征，最后將兩部分結(jié)果合并得到最終的曲面模型。實(shí)驗(yàn)表明，相比以上兩種算法，本文所提算法在精度上均有所提升，為曲面重建算法在工件的逆向及測(cè)量領(lǐng)域的優(yōu)化提供了借鑒。未來(lái)將重點(diǎn)研究網(wǎng)格空洞和網(wǎng)格拼接錯(cuò)位的修復(fù)問(wèn)題，以進(jìn)一步提高本文算法的魯棒性和穩(wěn)定性。