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

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

?

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

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

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

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

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

Recognition and repairing of surface hole in

1引言

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

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

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

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

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

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

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

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

3.1　樹搜索算法

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

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

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

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

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

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

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

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

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

3.3　獲取空洞邊集

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

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

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

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

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

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

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

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

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

3.4　空洞修復(fù)

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

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

4實驗結(jié)果與分析

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

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

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

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

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

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

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

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

5結(jié)論

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

參考文獻(xiàn)：

[1]王飛,湯偉,王挺峰,等.8×8APD陣列激光三維成像接收機(jī)研制[J].中國光學(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]徐正平,沈宏海,許永森.直接測距型激光主動成像系統(tǒng)發(fā)展現(xiàn)狀[J].中國光學(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].中國光學(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ī)律的點云孔洞修補(bǔ)[J].大地測量與地球動力學(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]岳杰,陸聲鏈,孫智慧,等.三維點云孔洞修補(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]劉詠梅,李鳳霞,雷正朝,等.基于邊界特征增長的孔洞修補(bǔ)算法[J].系統(tǒng)仿真學(xué)報,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ī)應(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

作者簡介：

中圖分類號：TP391

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

doi:10.3788/CO.20160901.0114

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

基金項目：國家高技術(shù)研究發(fā)展計劃(863計劃)資助項目(No.2013AA03A116)；國家重大科學(xué)儀器設(shè)備開發(fā)資助專項 (No.2013YQ14051702)；長春市科技局重大科技攻關(guān)計劃資助項目(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)