三維激光掃描系統中曲面空洞的識別與修復

呂源治，孫　強，畢國玲

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

?

三維激光掃描系統中曲面空洞的識別與修復

呂源治*，孫強，畢國玲

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

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

關鍵詞:三維重構；空洞識別；曲面修復

Recognition and repairing of surface hole in

1引言

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

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

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

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

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

3基于Floyd算法的空洞識別與修復

本文將三角網格中只參與構成一個三角形和未參與構成三角形的邊定義為邊界邊，將三角網格中至少連接有一條邊界邊的頂點定義為邊界點，多條邊界邊首尾相連構成了三維曲面的空洞。基于Floyd算法的空洞識別與修復過程如圖1所示。

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

3.1　樹搜索算法

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

圖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　數據更新

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

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

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

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

采用對邊界邊重新分配長度的方法構建了以處理點(圖2中的點A01和點B01)為中心的邊界點拓撲結構，重新分配的邊界邊長度表征了邊界點與處理點間的相關性強度，即，到處理點所經由的邊界邊數量越少的邊界點與處理點的相關性越強，到處理點的距離也越近。

3.3　獲取空洞邊集

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

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

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

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

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

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

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

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

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

3.4　空洞修復

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

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

4實驗結果與分析

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

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

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

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

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

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

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

表1　原始曲面與修復后曲面參數

5結論

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

參考文獻：

[1]王飛,湯偉,王挺峰,等.8×8APD陣列激光三維成像接收機研制[J].中國光學,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]徐正平,沈宏海,許永森.直接測距型激光主動成像系統發展現狀[J].中國光學,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算法空間目標紅外影像3D重建[J].中國光學,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]羅德安,張騰波,廖麗瓊.基于建筑結構分布規律的點云孔洞修補[J].大地測量與地球動力學,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]王乾.三角網格模型過渡與孔洞修補算法的研究及應用[D].南京:南京航空航天大學,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]岳杰,陸聲鏈,孫智慧,等.三維點云孔洞修補算法及在植物形態建中的應用[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]劉詠梅,李鳳霞,雷正朝,等.基于邊界特征增長的孔洞修補算法[J].系統仿真學報,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]高旋輝,鮑蘇蘇,范應方,等.一種基于三角網格模型的空洞填補方法[J].計算機應用與軟件,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年于吉林大學獲得博士學位，主要從事立體圖像采集、處理、編碼與顯示等方面的研究。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

文獻標識碼:A

doi:10.3788/CO.20160901.0114

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

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