三維激光掃描系統(tǒng)中曲面空洞的識(shí)別與修復(fù)

呂源治，孫　強(qiáng)，畢國(guó)玲

(中國(guó)科學(xué)院 長(zhǎng)春光學(xué)精密機(jī)械與物理研究所，吉林 長(zhǎng)春 130033)

?

三維激光掃描系統(tǒng)中曲面空洞的識(shí)別與修復(fù)

呂源治*，孫強(qiáng)，畢國(guó)玲

(中國(guó)科學(xué)院 長(zhǎng)春光學(xué)精密機(jī)械與物理研究所，吉林 長(zhǎng)春 130033)

摘要：為了解決三維激光掃描系統(tǒng)中重構(gòu)曲面存在的空洞問題，提出了基于Floyd最短路徑選擇算法的空洞識(shí)別與修復(fù)方法。該方法對(duì)三維曲面中所有可能構(gòu)成空洞的邊界點(diǎn)進(jìn)行逐個(gè)處理，采用樹搜索算法獲得與處理點(diǎn)直接或間接相連的邊界點(diǎn)；將搜索到的邊界點(diǎn)作為路徑選擇的節(jié)點(diǎn)，將連接節(jié)點(diǎn)的邊界邊作為路徑選擇的邊并根據(jù)節(jié)點(diǎn)的搜索級(jí)別設(shè)置邊的長(zhǎng)度。當(dāng)新搜索到的邊界點(diǎn)與已搜索點(diǎn)發(fā)生重復(fù)時(shí)，首先，利用Floyd算法處理距離矩陣和路由矩陣找到空洞端點(diǎn)；然后，根據(jù)重復(fù)點(diǎn)與空洞端點(diǎn)生成空洞邊集，最后，采用波前法對(duì)空洞邊集進(jìn)行處理。實(shí)驗(yàn)結(jié)果表明：本文所提方法能夠準(zhǔn)確識(shí)別連接有孤立邊的空洞以及兩個(gè)相鄰空洞的特殊空洞結(jié)構(gòu)，與傳統(tǒng)方法相比，該方法具有更強(qiáng)的通用性和魯棒性，空洞修復(fù)數(shù)量與兩個(gè)傳統(tǒng)方法相比分別提高了54.1%和21.3%。

關(guān)鍵詞:三維重構(gòu)；空洞識(shí)別；曲面修復(fù)

Recognition and repairing of surface hole in

1引言

隨著逆向工程和三維建模技術(shù)的不斷發(fā)展，三角網(wǎng)格模型被廣泛應(yīng)用于快速成型、虛擬現(xiàn)實(shí)以及工業(yè)設(shè)計(jì)中，并且貫穿于模型的整個(gè)生命周期。在三維激光掃描系統(tǒng)中[1-3]，由于待測(cè)模型自身缺陷或采樣點(diǎn)數(shù)據(jù)不足等因素的影響，測(cè)量結(jié)果中存在數(shù)據(jù)丟失現(xiàn)象，這使得重建網(wǎng)格模型[4-5]中可能存在空洞缺陷。這些空洞不僅影響重建模型的視覺效果，而且影響模型快速重建、有限元分析等后續(xù)處理的有效性?？斩醋R(shí)別是指通過某種途徑將網(wǎng)格模型中的空洞缺陷識(shí)別出來，以便進(jìn)行空洞修復(fù)。因此，空洞識(shí)別技術(shù)是否完善直接關(guān)系到網(wǎng)格模型空洞修復(fù)的整體效果，在網(wǎng)格模型的建立過程中起到舉足輕重的作用。

目前，主要的空洞識(shí)別與修復(fù)技術(shù)包括基于點(diǎn)云模型的修復(fù)技術(shù)[6-7]和基于網(wǎng)格模型的修復(fù)技術(shù)[8-13]。在基于點(diǎn)云模型的修復(fù)技術(shù)中，Min等人[6-7]采用層次空間剖分技術(shù)進(jìn)行空洞識(shí)別，利用張量理論提取發(fā)生劇烈變化的點(diǎn)云區(qū)域并消除噪聲的影響。但是，該方法在提取空洞周圍點(diǎn)云數(shù)據(jù)的拓?fù)湫畔r(shí)存在較高的計(jì)算復(fù)雜度。相對(duì)而言，基于網(wǎng)格模型的修復(fù)技術(shù)更容易實(shí)現(xiàn)，其中，王乾等人[8-9]對(duì)點(diǎn)云模型中的空洞進(jìn)行分類，并分別給出了對(duì)應(yīng)的識(shí)別與修復(fù)算法。該類方法雖然能夠進(jìn)行有針對(duì)性的空洞修復(fù)，但是，分類過程帶來了額外的運(yùn)算量且所分類別很難涵蓋所有情況下的空洞。Wang等人[10-11]分別提出了將曲面空洞周圍的灰度信息以及拐點(diǎn)等特征信息作為輔助的空洞修復(fù)方法，該類方法受空洞的個(gè)體差異影響較為明顯。高旋輝等人[12-13]提出了基于鄰接三角形中邊界邊性質(zhì)的空洞識(shí)別方法，該類方法具有較強(qiáng)的通用性，但是在進(jìn)行特殊空洞的識(shí)別過程中魯棒性較低且容易破壞網(wǎng)格模型的原始數(shù)據(jù)結(jié)構(gòu)。

針對(duì)上述問題，本文在系統(tǒng)分析普通空洞與特殊空洞結(jié)構(gòu)特性的基礎(chǔ)上，提出了一種無需對(duì)各種情況進(jìn)行分別判斷即可有效識(shí)別出曲面空洞的具有強(qiáng)魯棒性的空洞識(shí)別與修復(fù)方法。通過為邊界邊重新分配長(zhǎng)度的方法對(duì)網(wǎng)格中的空洞進(jìn)行數(shù)學(xué)建模，將圖論中的Floyd最短路徑選擇算法[14]與空洞識(shí)別過程有效結(jié)合，采用經(jīng)典的波前法處理空洞邊集生成修復(fù)后的三維曲面。

2Floyd最短路徑選擇算法的基本思想

設(shè)有節(jié)點(diǎn)集V={v1,v2,…,vn}，當(dāng)存在關(guān)系R將V中的某些節(jié)點(diǎn)相互連接生成邊集E={e1,e2,…,em}時(shí)，稱節(jié)點(diǎn)集V和邊集E組成圖G，記為G=(V,E)，關(guān)系R稱為圖G的路由矩陣。Floyd算法是一種用于計(jì)算圖G中多源節(jié)點(diǎn)之間最短路徑的算法，該算法使用大小均為n×n的距離矩陣和路由矩陣，距離矩陣記為W=[wij]n×n，其中wij表示圖G中vi和vj兩點(diǎn)之間的路徑長(zhǎng)度。路由矩陣記為R=[rij]n×n，其中rij表示vi至vj經(jīng)過的轉(zhuǎn)接點(diǎn)(中間節(jié)點(diǎn))。Floyd算法的基本思想是首先寫出初始的W矩陣和R矩陣，然后，按順序依次將節(jié)點(diǎn)集中的各個(gè)節(jié)點(diǎn)作為中間節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)集中任意兩個(gè)其它節(jié)點(diǎn)的徑長(zhǎng)，如果計(jì)算結(jié)果小于W矩陣中記錄的徑長(zhǎng)，則更新W矩陣和R矩陣，如果計(jì)算結(jié)果大于或等于W矩陣中記錄的徑長(zhǎng)則不變，以此不斷更新W矩陣和R矩陣，直至W中的數(shù)值收斂，從最后得到的W和R中便可以找到任何節(jié)點(diǎn)間最短路徑的徑長(zhǎng)和路由。

3基于Floyd算法的空洞識(shí)別與修復(fù)

本文將三角網(wǎng)格中只參與構(gòu)成一個(gè)三角形和未參與構(gòu)成三角形的邊定義為邊界邊，將三角網(wǎng)格中至少連接有一條邊界邊的頂點(diǎn)定義為邊界點(diǎn)，多條邊界邊首尾相連構(gòu)成了三維曲面的空洞?；贔loyd算法的空洞識(shí)別與修復(fù)過程如圖1所示。

圖1　基于Floyd算法的空洞識(shí)別流程圖Fig.1　Flow chart of Floyd-based hole-recognition algorithm

3.1　樹搜索算法

由于邊界點(diǎn)和邊界邊是空洞存在的必要非充分條件，因此，本文的空洞識(shí)別算法將邊界點(diǎn)和邊界邊作為分析數(shù)據(jù)。如圖2(a)所示，點(diǎn)A01為對(duì)三角網(wǎng)格進(jìn)行遍歷搜索過程中發(fā)現(xiàn)的一個(gè)未經(jīng)處理的邊界點(diǎn)，在樹搜索算法中，首先，將點(diǎn)A01作為樹搜索的第0級(jí)節(jié)點(diǎn)并初始化距離矩陣W、路由矩陣R以及搜索點(diǎn)集P，圖3中的左側(cè)為初始化數(shù)據(jù)，搜索點(diǎn)集P記錄了搜索點(diǎn)在構(gòu)成整個(gè)三維曲面的散點(diǎn)集中的編號(hào)(P的第一行數(shù)據(jù))以及搜索點(diǎn)在樹搜索過程中的搜索級(jí)別(P的第二行數(shù)據(jù))；然后，采用迭代的方法獲取與當(dāng)前最高搜索級(jí)別中的所有節(jié)點(diǎn)直接相連的全部邊界點(diǎn)作為下一搜索級(jí)節(jié)點(diǎn)。當(dāng)下一搜索級(jí)中的節(jié)點(diǎn)數(shù)量為零或者當(dāng)前搜索的空洞尺寸超過了空洞的最大修復(fù)尺寸或者下一搜索級(jí)節(jié)點(diǎn)中出現(xiàn)了與搜索點(diǎn)集P中重復(fù)的節(jié)點(diǎn)時(shí)，迭代結(jié)束。圖2中各邊界點(diǎn)下角標(biāo)的第一個(gè)數(shù)字表示該點(diǎn)的搜索級(jí)別，第二個(gè)數(shù)字表示該點(diǎn)在本搜索級(jí)別中的編號(hào)，點(diǎn)A11和點(diǎn)A12為與點(diǎn)A01直接相連的邊界點(diǎn)，該兩個(gè)點(diǎn)即為第1搜索級(jí)中的節(jié)點(diǎn)。

圖2　空洞識(shí)別示意圖Fig.2　Sketch map of hole-recognition

圖3　距離矩陣W、路由矩陣R以及搜索點(diǎn)集P更新過程Fig.3　Renewal process of distance matrix W, routing matrix R and search points set P

3.2　數(shù)據(jù)更新

對(duì)于樹搜索算法搜索到的邊界點(diǎn)，如果該點(diǎn)不與搜索點(diǎn)集P中的點(diǎn)重復(fù)，則將W中該點(diǎn)到其它非直接相連點(diǎn)的距離設(shè)置為∞(無窮遠(yuǎn))，該點(diǎn)到前一搜索級(jí)中直接相連節(jié)點(diǎn)的距離設(shè)置為該點(diǎn)的搜索級(jí)別；將該點(diǎn)與搜索點(diǎn)集P中每個(gè)點(diǎn)的路由關(guān)系存儲(chǔ)到路由矩陣R中；將該點(diǎn)在三維曲面散點(diǎn)集中的編號(hào)以及搜索級(jí)別存儲(chǔ)到搜索點(diǎn)集P中。圖2(a)中第1級(jí)搜索結(jié)束后對(duì)W、R和P的更新結(jié)果如圖3右側(cè)數(shù)據(jù)所示。路由矩陣R中的非零數(shù)字表示其所在列的對(duì)應(yīng)節(jié)點(diǎn)在P中的編號(hào)，例如，R(1,2)表示點(diǎn)A11是P中保存的第2個(gè)點(diǎn)。

如果樹搜索算法搜索到的邊界點(diǎn)與搜索點(diǎn)集P中的某個(gè)點(diǎn)發(fā)生重復(fù)，表明此處可能存在空洞，則在更新距離矩陣W時(shí)存在圖2(a)和圖2(b)兩種情況。在圖2(a)中，按照樹搜索算法的搜索順序，點(diǎn)A31首先通過點(diǎn)A21搜索得到并將相關(guān)數(shù)據(jù)更新到W、R和P中，然后，在搜索與點(diǎn)A22相連的邊界點(diǎn)時(shí)再次得到了點(diǎn)A31，此時(shí)，重復(fù)點(diǎn)A31與點(diǎn)A22不屬于同一搜索級(jí)別，對(duì)于這種情況，在進(jìn)行數(shù)據(jù)更新時(shí)，將距離矩陣W中重復(fù)點(diǎn)A31到點(diǎn)A22間的距離設(shè)定為點(diǎn)A31的搜索級(jí)別3(此前為∞)；而在圖2(b)中，在搜索與點(diǎn)B21相連的邊界點(diǎn)時(shí)得到點(diǎn)B22，此時(shí)，重復(fù)點(diǎn)B22與點(diǎn)B21屬于同一搜索級(jí)別，與圖2(a)中的情況不同，在進(jìn)行數(shù)據(jù)更新時(shí)，將距離矩陣W中重復(fù)點(diǎn)B22到點(diǎn)B21間的距離設(shè)定為0。兩種情況均將重復(fù)點(diǎn)與當(dāng)前搜索點(diǎn)的路由關(guān)系更新到路由矩陣R中而不對(duì)搜索點(diǎn)集P進(jìn)行更新。圖2(a)的數(shù)據(jù)更新結(jié)果為

式中，WA、RA和PA分別為圖2(a)的距離矩陣、路由矩陣和搜索點(diǎn)集，圖2(b)的數(shù)據(jù)更新結(jié)果為

式中，WB、RB和PB分別為圖2(b)的距離矩陣、路由矩陣和搜索點(diǎn)集，WA和WB中由虛線圈出的數(shù)值，即為圖2(a)和圖2(b)兩種情況對(duì)距離矩陣的影響。

采用對(duì)邊界邊重新分配長(zhǎng)度的方法構(gòu)建了以處理點(diǎn)(圖2中的點(diǎn)A01和點(diǎn)B01)為中心的邊界點(diǎn)拓?fù)浣Y(jié)構(gòu)，重新分配的邊界邊長(zhǎng)度表征了邊界點(diǎn)與處理點(diǎn)間的相關(guān)性強(qiáng)度，即，到處理點(diǎn)所經(jīng)由的邊界邊數(shù)量越少的邊界點(diǎn)與處理點(diǎn)的相關(guān)性越強(qiáng)，到處理點(diǎn)的距離也越近。

3.3　獲取空洞邊集

本文定義構(gòu)成空洞的邊界點(diǎn)中搜索級(jí)別最低的點(diǎn)為空洞端點(diǎn)。圖2(a)和圖2(b)的空洞端點(diǎn)分別為點(diǎn)A01和點(diǎn)B01，從圖2中可以看出，重復(fù)點(diǎn)與空洞端點(diǎn)之間有兩條長(zhǎng)度相等的最短路徑，且這兩條最短路徑包含的邊界邊即為構(gòu)成空洞的邊集。因此，只需找到重復(fù)點(diǎn)對(duì)應(yīng)的空洞端點(diǎn)，即可實(shí)現(xiàn)曲面空洞的有效識(shí)別。

在獲取空洞邊集的過程中，首先，利用本文改進(jìn)的Floyd算法處理距離矩陣W和路由矩陣R，在依次將節(jié)點(diǎn)集中的各個(gè)節(jié)點(diǎn)作為中間節(jié)點(diǎn)。計(jì)算節(jié)點(diǎn)集中任意兩個(gè)其它節(jié)點(diǎn)的徑長(zhǎng)時(shí)，如果計(jì)算結(jié)果等于W矩陣中記錄的徑長(zhǎng)，表明出現(xiàn)了兩條長(zhǎng)度相等的最短路徑，傳統(tǒng)的Floyd算法直接將后出現(xiàn)的路徑舍掉，而改進(jìn)的Floyd算法將這兩條最短路徑同時(shí)保存下來。用改進(jìn)的Floyd算法對(duì)圖2(a)的距離矩陣和路由矩陣進(jìn)行處理的結(jié)果為

式中，WFA和RFA分別為WA和RA的處理結(jié)果，改進(jìn)的Floyd算法將路由矩陣的行數(shù)擴(kuò)展為原來的2倍，路由矩陣中的每?jī)尚袛?shù)據(jù)分配給一個(gè)邊界點(diǎn)，其中第二行數(shù)據(jù)保存可能出現(xiàn)的第二條最短路徑的情況，從RFA中可以看出，點(diǎn)A01到點(diǎn)A31有兩條最短路徑，同時(shí)，點(diǎn)A21到點(diǎn)A22也有兩條最短路徑。然后，利用計(jì)算得到的距離矩陣和路由矩陣確定空洞端點(diǎn)，空洞端點(diǎn)需滿足以下條件：

(1)空洞端點(diǎn)到重復(fù)點(diǎn)有兩條最短路徑，重復(fù)點(diǎn)到空洞端點(diǎn)也有兩條最短路徑；

(2)在所有滿足條件(a)的邊界點(diǎn)中，空洞端點(diǎn)到重復(fù)點(diǎn)的距離最短；

(3)如果同時(shí)滿足條件(a)和條件(b)的邊界點(diǎn)不止一個(gè)，則任取其中之一即可。

在圖2(a)中，由WFA和RFA可以確定空洞端點(diǎn)為點(diǎn)A01。最后，利用路由矩陣，將構(gòu)成重復(fù)點(diǎn)到空洞端點(diǎn)的兩條最短路徑的邊界邊提取出來生成空洞邊集。

如果空洞邊集中邊界邊的數(shù)量為3，表明搜索到的并不是空洞而是一個(gè)孤立的三角形，對(duì)于這種情況，本文繼續(xù)進(jìn)行樹搜索算法獲取邊界點(diǎn)；反之，則修復(fù)搜索到的空洞并重新搜索邊界點(diǎn)。

本文定義空洞尺寸為構(gòu)成空洞的邊界邊數(shù)量，由于三維激光掃描系統(tǒng)獲取的點(diǎn)云密度相對(duì)均勻，因此，構(gòu)成空洞的邊界邊數(shù)量越多，空洞的空間面積越大。本文通過設(shè)定空洞的最大修復(fù)尺寸來提高所提算法的靈活性并避免將三維曲面的輪廓判斷為空洞，操作人員根據(jù)掃描對(duì)象的精度要求設(shè)定最大修復(fù)尺寸。

3.4　空洞修復(fù)

本文采用波前法[15]對(duì)空洞進(jìn)行修復(fù)，該方法將搜索到的空洞邊集作為迭代計(jì)算的初始數(shù)據(jù)，在迭代過程中，首先，依次計(jì)算當(dāng)前空洞邊集中每?jī)蓷l相鄰邊界邊的夾角并記錄構(gòu)成最小夾角的邊界邊；然后，連接構(gòu)成最小夾角的兩條邊界邊的非公共端點(diǎn)生成新的三角形以縮小空洞的尺寸；接下來，在空洞邊集中，用新生成的邊界邊替換與其一起構(gòu)成三角形的兩條邊界邊，如果更新后的空洞邊集中包含的邊界邊數(shù)量大于3，則重復(fù)上述過程繼續(xù)進(jìn)行迭代，反之，則將空洞邊集中包含的這三條邊界邊構(gòu)成三角形并結(jié)束迭代；最后，對(duì)構(gòu)成空洞的所有邊界點(diǎn)采用二面角最大化的三角網(wǎng)格優(yōu)化準(zhǔn)則[16-17]使修復(fù)后的空洞更加平滑。圖4為空洞修復(fù)示意圖，圖中點(diǎn)C、D、E、F和G構(gòu)成了一個(gè)由五條邊界邊組成的空洞，在第一次迭代中，搜索到∠EFG為空洞的最小內(nèi)角，連接點(diǎn)E和點(diǎn)G生成△EFG并用邊EG替換空洞邊集中的EF和FG，由于此時(shí)空洞邊集中包含4條邊界邊，因此繼續(xù)進(jìn)行迭代；第二次迭代中，由于連接點(diǎn)C和點(diǎn)E后空洞邊集中只剩下3條邊界邊，因此，迭代結(jié)束并生成△CDE和△CEG。

圖4　波前法空洞修復(fù)示意圖Fig.4　Sketch map of hole-repairing with wave-front method

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

圖5　連接有孤立邊的空洞處理結(jié)果Fig.5　Processing results of the hole with an isolated boundary

為了證明所提方法與其它方法相比具有更高的魯棒性以及對(duì)復(fù)雜空洞具有更準(zhǔn)確的識(shí)別能力，實(shí)驗(yàn)中對(duì)特殊形狀的空洞進(jìn)行了處理分析，圖5(a)為一個(gè)與孤立邊相連的空洞，圖5(b)為文獻(xiàn)[12]的處理結(jié)果，由于文獻(xiàn)[12]將只屬于一個(gè)三角形的邊識(shí)別為空洞的邊界邊，而圖5(b)中虛線圈出的兩條邊不屬于任何三角形，因此，文獻(xiàn)[12]無法對(duì)空洞進(jìn)行有效識(shí)別，圖5(c)為文獻(xiàn)[13]的處理結(jié)果，文獻(xiàn)[13]首先將孤立邊刪除，然后對(duì)空洞進(jìn)行修復(fù)，該方法雖然能夠成功檢測(cè)到空洞，但是刪除了原始數(shù)據(jù)的一條邊，破壞了數(shù)據(jù)的完整性。圖5(d)為本文所提方法的處理結(jié)果，從圖中可以看出，本文所提方法不僅能夠有效識(shí)別到空洞，而且不需要?jiǎng)h除孤立邊，保證了原始數(shù)據(jù)的完整性。

圖6　兩個(gè)相鄰空洞處理結(jié)果Fig.6　Processing results of two adjacent holes

圖6(a)為兩個(gè)相鄰空洞的情況，由于文獻(xiàn)[13]通過對(duì)邊界邊進(jìn)行依次搜索的方法來判斷空洞的存在。該方法在識(shí)別相鄰空洞時(shí)存在圖6(b)和圖6(c)兩種情況的不唯一性，其中，圖6(b)能夠成功的將兩個(gè)空洞識(shí)別出來，而圖6(c)卻將圍成兩個(gè)相鄰空洞的邊界邊識(shí)別為一個(gè)大的空洞，圖6(c)中識(shí)別到的空洞的修復(fù)結(jié)果如圖6(d)所示，從圖6(d)中可以看出，兩個(gè)相鄰空洞的公共邊(虛線內(nèi)的邊界邊)并沒有參與空洞修復(fù)而是成為了一條孤立邊懸浮于曲面之外，顯然，圖6(c)的空洞識(shí)別結(jié)果是不正確的，文獻(xiàn)[13]無法對(duì)兩個(gè)相鄰空洞的情況進(jìn)行有效識(shí)別和修復(fù)。由于文獻(xiàn)[12]將只屬于一個(gè)三角形的邊識(shí)別為空洞的邊界邊，因此，文獻(xiàn)[12]也只識(shí)別到了一個(gè)大的空洞(修復(fù)結(jié)果如圖6(e)所示)。在本文所提方法中，由于采用樹搜索算法對(duì)所有空洞進(jìn)行并行搜索，可以有效識(shí)別出相鄰的兩個(gè)空洞，本文所提方法的空洞修復(fù)結(jié)果如圖6(f)所示。

圖7　空洞修復(fù)效果對(duì)比Fig.7　Comparison of the hole-repairing results

圖7(a)為由三維激光掃描儀生成的包含多個(gè)空洞的三維曲面，圖7(b)、圖7(c)和圖7(d)分別為文獻(xiàn)[12]、文獻(xiàn)[13]以及本文所提方法的修復(fù)結(jié)果。從圖中可以看出，本文所提方法的修復(fù)效果明顯優(yōu)于文獻(xiàn)[12]和文獻(xiàn)[13]。構(gòu)成圖7中4個(gè)曲面的邊數(shù)量、三角形數(shù)量以及3種方法修復(fù)的空洞數(shù)量如表1所示，與文獻(xiàn)[12]和文獻(xiàn)[13]相比，本文所提方法的空洞修復(fù)數(shù)量分別提高了54.1%和21.3%，同時(shí)，從表1中可以看出，文獻(xiàn)[13]的修復(fù)曲面與本文所提方相比只少了4個(gè)三角形，但是構(gòu)成曲面的邊卻減少了40條，進(jìn)一步證明了文獻(xiàn)[13]由于刪除曲面中的孤立邊導(dǎo)致原始數(shù)據(jù)的完整性遭到破壞的問題。

圖7(d)中空洞的最大修復(fù)尺寸為60，曲面的最大修復(fù)尺寸不僅能夠有效界定三維曲面的外輪廓與空洞，而且，在實(shí)際應(yīng)用中，操作人員可以通過改變最大修復(fù)尺寸來獲取不同尺寸空洞在曲面中的統(tǒng)計(jì)分布，同時(shí)，并非所有空洞都是需要進(jìn)行修復(fù)的，對(duì)于一些大尺寸的空洞，修復(fù)算法會(huì)帶來較大誤差，操作人員可以通過設(shè)定最大修復(fù)尺寸來屏蔽掉這些較大尺寸的空洞，而通過再次掃描的方式用真實(shí)數(shù)據(jù)來填充剩余空洞。

表1　原始曲面與修復(fù)后曲面參數(shù)

5結(jié)論

本文提出了一種三維曲面空洞的識(shí)別與修復(fù)方法，該方法將樹搜索算法中的搜索級(jí)別作為邊界邊的長(zhǎng)度，利用Floyd最短路徑算法對(duì)存在的空洞進(jìn)行識(shí)別，采用波前法修復(fù)發(fā)現(xiàn)的空洞。本文所提方法不僅能夠識(shí)別出由只屬于一個(gè)三角形的邊界邊圍成的普通空洞，而且能夠在保證原始數(shù)據(jù)完整性的前提下對(duì)連接有孤立邊的空洞進(jìn)行識(shí)別。對(duì)于兩個(gè)空洞相鄰的情況，傳統(tǒng)方法會(huì)將其識(shí)別為一個(gè)大的空洞，而本文所提方法能夠?qū)ζ溥M(jìn)行準(zhǔn)確判斷，與傳統(tǒng)方法相比，空洞修復(fù)數(shù)量提高了21.3%以上。

參考文獻(xiàn)：

[1]王飛,湯偉,王挺峰,等.8×8APD陣列激光三維成像接收機(jī)研制[J].中國(guó)光學(xué),2015,8(6):422-427.

WANG F,TANG W,WANG T F,etal.. Design of 3D laser imaging receiver based on 8×8 APD detector array[J].ChineseOptics,2015,8(6):422-427.(in Chinese)

[2]徐正平,沈宏海,許永森.直接測(cè)距型激光主動(dòng)成像系統(tǒng)發(fā)展現(xiàn)狀[J].中國(guó)光學(xué),2015,8(1):28-38.

XU ZH P,SHEN H H,XU Y S. Review of the development of laser active imaging system with direct ranging[J].ChineseOptics,2015,8(1):28-38.(in Chinese)

[3]WANG Z,ZHANG L Q,FANG T,etal.. A multiscale and hierarchical feature extraction method for terrestrial laser scanning point cloud Classification[J].IEEETransactionsonGeoscienceandRemoteSensing,2015,53(5):2409-2425.

[4]WANG H Y,WANG C,LUO H,etal.. 3-D point cloud object detection based on supervoxel neighborhood with hough forest framework[J].IEEEJ.SelectedTopicsinAppliedEarthObservationsandRemoteSensing,2015,8(4):1570-1581.

[5]曾蔚,王匯源,劉瑩奇,等.基于IR-SFS算法空間目標(biāo)紅外影像3D重建[J].中國(guó)光學(xué),2014,7(3):376-388.

ZENG W,WANG H Y,LIU Y Q,etal.. 3Dreconstruction of space target IR image based on IR-SFS algorithm[J].ChineseOptics,2014,7(3):376-388.(in Chinese)

[6]羅德安,張騰波,廖麗瓊.基于建筑結(jié)構(gòu)分布規(guī)律的點(diǎn)云孔洞修補(bǔ)[J].大地測(cè)量與地球動(dòng)力學(xué),2014,34(1):59-62.

LUO D A,ZHANG T B,LIAO L Q. Repairing holes of point cloud based on distribution regularity of building fa?ade components[J].J.GeodesyandGeodynamics,2014,34 (1):59-62.(in Chinese)

[7]MIN K P,LEE S J,LEE K H. Multi-scale tensor voting for feature extraction from unstructured point clouds[J].GraphicalModels,2012,74(4):197-208.

[8]王乾.三角網(wǎng)格模型過渡與孔洞修補(bǔ)算法的研究及應(yīng)用[D].南京:南京航空航天大學(xué),2007.

WANG Q. Research and application of triangle mesh models transition & hole repairing algorithm[D]. Nanjing:Nanjing University of Aeronautics and Astronautics,2007.(in Chinese)

[9]岳杰,陸聲鏈,孫智慧,等.三維點(diǎn)云孔洞修補(bǔ)算法及在植物形態(tài)建中的應(yīng)用[J].農(nóng)機(jī)化研究,2013,5:190-195.

YUE J,LU SH L,SUN ZH H,etal.. The repair algorithm of 3D point cloud holes and the application of the reconstruction in plant forms[J].J.AgriculturalMechanizationResearch,2013,5:190-195.(in Chinese)

[10]WANG L C,HUNG Y C. Hole filling of triangular mesh segments using systematic grey prediction[J].Computer-AidedDesign,2012,44(12):1182-1189.

[11]WANG X C,LIU X P,LU L F,etal.. Automatic hole-filling of CAD models with feature-preserving[J].Computers&Graphics,2012,36(2):101-110.

[12]劉詠梅,李鳳霞,雷正朝,等.基于邊界特征增長(zhǎng)的孔洞修補(bǔ)算法[J].系統(tǒng)仿真學(xué)報(bào),2014,26(9):1916-1921.

LIU Y M,LI F X,LEI ZH CH,etal.. New hole filling algorithm based on boundary-feature growing[J].J.SystemandSimulation,2014,26(9):1916-1921.(in Chinese)

[13]高旋輝,鮑蘇蘇,范應(yīng)方,等.一種基于三角網(wǎng)格模型的空洞填補(bǔ)方法[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(6):188-191.

GAO X H,BAO S S,FAN Y F,etal.. A method for holes filling in triangular mesh model[J].ComputerApplicationandSoftware,2014,31(6):188-191.(in Chinese)

[14]FLOYD R W. Algorithm 97:shortest path[J].CommunicationsoftheAssociationforComputingMachinery,1962,5(6):345.

[15]ZHAO W,GAO S M,LIN H W. A robust hole-filling algorithm for triangular mesh[J].TheVisualComputer,2007,23(12):987-997.

[16]TSAI Y C，HUANG Y，LIN K Y．Development of automatic surface reconstruction technique in reverse engineering[J].TheInternationalJ.AdvancedManufacturingTechnology，2009,42:152-167.

[17]ZHOU M,WANG M Y. Engineered model simplification for simulation based structural design[J].Computer-AidedDesignandApplications,2012,9(1):87-94.

呂源治(1986—)，男，黑龍江齊齊哈爾人，博士，助理研究員，2014年于吉林大學(xué)獲得博士學(xué)位，主要從事立體圖像采集、處理、編碼與顯示等方面的研究。E-mail:lyuyuanzhi@163.com

three dimensional laser scanning system

LYU Yuan-zhi*, SUN Qiang, BI Guo-ling

(ChangchunInstituteofOptics,FineMechanicsandPhysics,

ChineseAcademyofSciences,Changchun130033,China)

*Correspondingauthor,E-mail:lyuyuanzhi@163.com

Abstract:To solve the hole-problem of the reconstructed surface in three dimensional laser scanning system, the hole-recognition and repair method based on the Floyd shortest path selection algorithm is proposed. We process one by one all the boundary points of the three dimensional surface which might constitute a hole, and adopt the tree search algorithm to obtain the boundary points, which are directly or indirectly connected to the processed point, and use them as the routing nodes, then the boundary sides which are connected with the nodes are used as the routing sides, and we set the length of the boundary sides according to the search level of the nodes. When the newly searched boundary point overlap with the already searched points, we firstly process the distance matrix and the routing matrix to find the hole endpoint by the Floyd algorithm, and then make use of the repeated point and the hole endpoint to generate the hole boundary sides set. Finally, we deal with the hole boundary sides set using the wave front method. The experimental results show that the proposed method can accurately identify the special hole-structures, such as a hole connected with an isolated boundary side and two adjacent holes, and has better versatility and robustness compared with the traditional method. Compared with two traditional methods, the number of the repaired holes has been increased by 54.1% and 21.3%, respectively.

Key words:three dimensional reconstruction;hole-recognition;surface repair

作者簡(jiǎn)介：

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)識(shí)碼:A

doi:10.3788/CO.20160901.0114

文章編號(hào)2095-1531(2016)01-0114-08

基金項(xiàng)目：國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863計(jì)劃)資助項(xiàng)目(No.2013AA03A116)；國(guó)家重大科學(xué)儀器設(shè)備開發(fā)資助專項(xiàng) (No.2013YQ14051702)；長(zhǎng)春市科技局重大科技攻關(guān)計(jì)劃資助項(xiàng)目(No.14KG011)

收稿日期:2015-09-24；

修訂日期:2015-10-19

Supported by National High-tech R&D Program of China(No.2013AA03A116), National Science Equipment Major Special Project of China(No.2013YQ14051702), Changchun S&T Bureau Major Scientific Research Project of China(No.14KG011)