李群輝,張俊祖,耿國華,周明全

(1.長安大學理學院,710064,西安;2.西北大學信息科學與技術學院,710069,西安;3.北京師范大學信息科學與技術學院,100875,北京)

?

以輪廓曲線為特征的斷裂面匹配

李群輝1,張俊祖1,耿國華2,周明全3

(1.長安大學理學院,710064,西安;2.西北大學信息科學與技術學院,710069,西安;3.北京師范大學信息科學與技術學院,100875,北京)

現(xiàn)有斷裂面匹配算法主要適用于表面粗糙特征豐富的斷裂面,對于表面光滑特征稀少的斷裂面不能正確匹配。針對這一問題,提出一種以斷裂面輪廓曲線為特征的匹配算法。該算法首先將區(qū)域生長算法和邊界跟蹤算法相結合,在沿碎塊棱邊分割出斷裂面的同時又得到了封閉且序列化的輪廓頂點;輪廓曲線的匹配,先采用角點距離矩陣進行粗匹配,排除了大部分不匹配的曲線對,再根據(jù)輪廓曲線所有頂點的曲率和撓率,采用改進的Hausdorff距離進行細匹配;最后,根據(jù)匹配的輪廓曲線,采用四元數(shù)法計算三維變換將碎塊對齊,通過跨界切矢連續(xù)檢測且誤差最小的碎塊對為最優(yōu)匹配。在斷裂面粗糙和光滑且材質不同的多個碎塊上進行了實驗,結果表明該算法能較好實現(xiàn)特征稀少或豐富的斷裂面的匹配。

斷裂面匹配;斷裂面分割;輪廓曲線匹配;跨界切矢連續(xù)檢測

剛性物體破碎后形成若干任意形狀的子物體,利用計算機實現(xiàn)破碎剛體的虛擬復原在文物保護、工業(yè)設計和醫(yī)學等領域有著重要的應用價值,其中斷裂面匹配是剛體復原中的關鍵技術。

現(xiàn)有的斷裂面匹配算法主要是基于特征點或特征區(qū)域的,Papaioannou等采用Z-buffer算法獲得斷裂面的深度圖像進行匹配[1]。Chen等提出基于曲率形狀描述子的特征點匹配算法[2]。Huang等提出基于積分不變量和特征區(qū)域的匹配算法[3]。Winkelbach等直接根據(jù)斷裂面的所有頂點,采用隨機采樣算法和分級二叉樹進行碎塊的配對[4]。王堅等以自旋圖為特征進行斷裂面匹配[5]。Altantsetseg等采用基于傅立葉變換的方法提取斷裂面上的曲線作為特征進行匹配[6]。Pokrass等對斷裂面進行離散采樣得到若干采樣點進行匹配[7]。

這類算法均要求斷裂面粗糙具有豐富的特征,當斷裂面光滑特征稀少時,因缺少足夠的特征而無法進行正確匹配,如圖1、2所示。與基于特征的算法不同,Papaodysseus首先將兩個待匹配碎塊根據(jù)中心軸旋轉對齊,然后依次根據(jù)兩個拼接斷裂面間的間隙體積、重合面積、重合部分的曲率相似度及其邊界重合程度判斷兩碎塊是否匹配[8],該算法要求斷裂面整體接近平面。

圖1 斷裂面粗糙的碎塊

針對這一問題,本文提出以輪廓曲線為特征的斷裂面匹配算法,因為無論斷裂面的特征豐富與否,如果兩個斷裂面匹配,除了其中一個斷裂面是另一個的子曲面,即當其中一個碎塊表面全為斷裂面的情形時,這兩個斷裂面的輪廓有可能沒有重合部分,其余情況下兩斷裂面的輪廓曲線都會部分或全部匹配,如圖2所示。

圖2 斷裂面光滑的碎塊

1 輪廓曲線的提取

為了提取出斷裂面的輪廓曲線,首先將碎塊的外表面沿棱邊分割成多張曲面,然后區(qū)分出原始面和斷裂面,區(qū)分的主要依據(jù)是斷裂面比原始面粗糙,但對于光滑的斷裂面則不易區(qū)分,本文在曲面分割后,對于光滑的斷裂面人工標記,對于粗糙的斷裂面算法自動識別。

曲面分割主要有基于面的方法和基于邊的方法[9],不足之處是在邊界處容易形成鋸齒狀,邊界劃分不夠準確,且容易產(chǎn)生錯誤跟蹤,不一定能得到封閉的輪廓曲線。針對這一問題,本文給出一種將兩種方法相結合的算法,首先采用基于面的方法,即區(qū)域生長算法進行曲面分割,得到初始邊界點;然后對其進行擴展,再采用基于邊的方法,即邊界跟蹤算法提取邊界,這樣沿棱邊分割出了曲面,且得到了封閉的輪廓曲線。

1.1 提取棱邊頂點

為了沿棱邊進行曲面分割,首先區(qū)分出棱邊和非棱邊頂點,一般情況下棱邊較非棱邊凹凸程度顯著,曲率能很好地描述局部曲面的凹凸程度,但離散曲率的計算對噪聲敏感,所以采用多尺度的曲率信息基于邊的方法不足之處是因為在小尺度上局部噪聲對曲率影響較大,當增大尺度時對曲率影響就會逐漸減小。根據(jù)最大最小主曲率定義的曲度能較好地區(qū)分出棱邊和非棱邊頂點,如圖3所示。

圖3 根據(jù)曲度提取的棱邊點

定義頂點v在尺度rk下的曲度

(1)

式中:rk為頂點v的k階鄰域的頂點個數(shù),k=1,3,5;k1、k2為rk下的最大、最小主曲率,根據(jù)k階鄰域頂點進行曲面擬合求出[9]。對于每一個頂點v,如果在rk下的Cv(rk)均大于給定閾值T(rk),則頂點v為棱邊頂點。

對于粗糙的斷裂面,算法會將少量非邊界頂點提取出來,這些頂點曲面分割時會被當成邊界點,從而形成一些小面片,最后通過曲面融合算法將其合并到相鄰曲面中。

1.2 提取輪廓曲線

本文采用文獻[1]中的區(qū)域生長算法進行曲面分割,以頂點曲度進行生長。以法矢進行曲面分割,方法簡單速度快,對于有尖銳棱邊的碎塊能進行正確地分割,但當邊界過渡較緩慢時,邊界分割不準確且容易產(chǎn)生過分割的現(xiàn)象。因為曲度能很好地反映局部曲面的彎曲程度,碎塊邊界處過渡緩慢或尖銳時通常都有較高的曲度值。邊界處和曲面中間有一些獨立的小面片,采用曲面融合的方法[1]將其直接合并到相鄰較大曲面中,結果如圖4所示。

在每一個曲面的生長過程中,遇到的棱邊頂點為該曲面的邊界點,但邊界處有鋸齒現(xiàn)象,且邊界點沒有序列化,為此對邊界點進行了擴展,將每個邊界點一階鄰域內所有頂點作為候選邊界點,更準確的邊界點應該是其子集,然后采用邊界跟蹤算法[9]從候選邊界點中重新提取了邊界點,同時進行序列化,擴充后的邊界點不存在間斷的地方,故可得封閉的輪廓曲線,邊界頂點如圖4c所示。

(a)曲面分割 (b)曲面融合

(c)邊界頂點圖4 曲面分割及輪廓曲線提取結果

2 輪廓曲線匹配

因為一對碎塊的任意兩個斷裂面都要參加匹配檢測,但實際上最多只有一對為真匹配,為了提高匹配的速度和準確率,采用兩級匹配算法,即先用快速粗匹配排除大部分不匹配的曲線對,然后再細匹配。歸一化的角點距離矩陣能實現(xiàn)曲線的部分匹配,計算簡單速度快,具有平移旋轉和縮放不變性,能去除大部分不匹配的曲線對,減少下一步參加細匹配的曲線數(shù)量。

2.1 根據(jù)角點距離矩陣進行粗匹配

文獻[10]利用角點距離矩陣對二維輪廓曲線進行粗匹配,本文將其擴展用于空間曲線的匹配。采用角點檢測器[11]提取出輪廓曲線的角點,定義曲率的乘積

(2)

式中:k(σj)為尺度σj下的曲率。將|P|大于給定閾值的局部極大值點作為角點。

對于有n個角點的輪廓曲線,距離矩陣是一個n階方陣,第i行是第i個角點與其余角點間的歐氏距離。設輪廓曲線有p1,p2,…,pn共n個角點,坐標分別是(x1,y1,z1),(x2,y2,z2),…,(xn,yn,zn),角點距離矩陣為

(3)

(4)

理想情況下矩陣φ的各項值都為1,但實際會有一定的誤差,定義兩曲線的相似程度ω=(Σ(1-φi,j)2)1/2,ω越小,兩曲線相似度越高。

根據(jù)角點距離矩陣進行粗匹配,只利用了輪廓曲線的角點信息,沒有考慮角點間曲線段的信息,因此可能會存在一些誤匹配,如圖5所示,根據(jù)角點信息認為曲線段abcd和a′b′c′d′是匹配的,但實際上角點bc和b′c′之間的曲線段并不匹配,因此還需要對角點間的曲線段進一步細匹配。

(a)待匹配曲線 (b)匹配結果圖5 根據(jù)角點距離矩陣的粗匹配結果

2.2 根據(jù)Hausdorff距離和曲率撓率細匹配

空間曲線的曲率和撓率能唯一確定一條曲線的形狀,采用頂點的曲率、撓率組成的特征串描述兩角點間的曲線段。Hausdorff距離可從總體上衡量兩個點集之間的距離,不需要點的對應關系,當點集數(shù)量不大時,采用基于平均值并加入曲線段長度信息的Hausdorff距離衡量兩曲線段的相似度。

(5)

C1i和C2i間引入方差信息和曲線段長度信息的Hausdorff距離[13],即

‖p1i-p2i‖+

kS(C1i,C2i)+tΔN

(6)

kS(C2i,C1i)+tΔN

(7)

式中:NC1i、NC2i分別為C1i、C2i頂點的個數(shù);k為權重系數(shù),表示頂點分布在相似性比較中所占的比重;ΔN=|C1i-C2i|為C1i和C2i頂點個數(shù)的差,用來衡量C1i和C2i的長度差;t為加權系數(shù),表示曲線段長度差異在Hausdorff距離中所占的權重。

(8)

(9)

與傳統(tǒng)Hausdorff距離相比,改進的Hausdorff距離使用曲線段點集間的平均最小距離,并引入方差信息和曲線段長度信息,對噪聲和離群點的魯棒性更好,對曲線段的描述更精確。

一般情況下,H(C1i,C2i,k,t)和H(C2i,C1i,k,t)不相等,為了進一步減少離群點的影響,令

(10)

如果H(C1i,C2i,k,t)<ε2,說明曲線段C1i和C2i匹配,ε2為經(jīng)驗閾值。粗匹配得到的輪廓曲線C1和C2每一對對應曲線段C1i和C2i,如果均匹配,則輪廓曲線C1和C2匹配。

3 斷裂面匹配

兩輪廓曲線匹配后,還需要再根據(jù)跨界切矢是否連續(xù)進一步檢測其所在的斷裂面是否為真匹配。設C1、C2為斷裂面F1、F2的輪廓曲線,利用四元數(shù)法[14],計算C1、C2間的旋轉矩陣R和平移矩陣T,將斷裂面F1、F2對齊,如果F1、F2為真匹配,則C1、C2在對應點處應滿足G1連續(xù)(切矢同向),如圖6所示?？缃缜惺高B續(xù)檢測要求兩頂點序列一一對應,但由于斷裂面邊界的復雜性,匹配的輪廓曲線頂點序列并不是等間距的,重新采樣會帶來新的誤差和系統(tǒng)開銷,而匹配的輪廓曲線角點序列是對應的,因此根據(jù)對應角點來進行跨界切矢連續(xù)檢測。

圖6 跨界切矢連續(xù)圖示

4 實驗結果和分析

文中實驗數(shù)據(jù)包括6塊石頭碎塊brick和11塊灰泥碎塊cake,是Vienna University of Technology公開用于復原的部分碎塊模型[15],原始碎塊是點云模型,對其進行三角剖分并優(yōu)化可得三角網(wǎng)格模型。馬腿碎塊是在兵馬俑采集的,用Handy3dscan三維激光掃描儀直接得到三角網(wǎng)格數(shù)據(jù)。因為斷裂面的匹配是互補匹配,所以先將其中一個斷裂面的法矢反向。文中所有算法用Visual C++和OpenGL編程,在CPU為Pentium(R)/3.4 GHz、內存為8.0 GB的PC機上實現(xiàn)。

對于cake和brick碎塊,由于斷裂面比較粗糙,算法可根據(jù)其粗糙程度自動區(qū)分出斷裂面和原始面。實驗過程是手動選擇兩個碎塊,然后系統(tǒng)自動分割出其斷裂面和原始面,之后會在所有斷裂面間自動進行匹配。對于馬腿碎塊,因無法區(qū)分出斷裂面和原始面,采取人工交互的方式選擇兩個斷裂面進行匹配。

斷裂面光滑的3個馬腿碎塊斷裂面分割、輪廓曲線和角點提取及匹配結果如圖7所示,其中F2、F3是碎塊2的兩個不同的斷裂面,斷裂面F1、F2的輪廓曲線完全匹配,F3、F4的輪廓曲線也完全匹配,通過跨界切矢連續(xù)檢測,相應斷裂面也完全匹配。斷裂面粗糙的2個brick碎塊曲面分割、輪廓曲線和角點提取及匹配結果如圖8所示,其中斷裂面F2和F1只有部分輪廓曲線匹配。brick碎塊和cake碎塊的匹配結果如圖9所示,其中cake碎塊的第i塊和第j塊匹配記為cakei-j,brick碎塊的第i塊和第j塊匹配記為bricki-j。由圖9可知,本文算法對于光滑或粗糙斷裂面均適合,且能實現(xiàn)斷裂面部分和完全匹配。

圖7 馬腿碎塊和匹配結果

圖8 birck碎塊和匹配結果

(1)cake1-3 (2)cake2-4 (3)cake7-8

(4)cake6-7 (5)cake9-10 (6)cake2-10

(7)brick1-2 (8)brick1-3 (9)brick2-5 (10)brick5-6圖9 匹配結果

圖9中各個碎塊的大小、包含的斷裂面數(shù)目、需匹配的斷裂面對數(shù)目和算法執(zhí)行時間如表1所示,其中碎塊的大小指其包含的三角網(wǎng)格數(shù)目,執(zhí)行時間是指碎塊所有斷裂面間的匹配時間,包括本文算法中所有步驟,分別是曲度的計算、輪廓曲線的提取及相似性計算、平移旋轉變換的計算和跨界切矢連續(xù)檢測。實驗中10對碎塊,共有59對斷裂面進行了匹配,平均每對斷裂面匹配時間為2.78 s。

表1 碎塊大小、斷裂面數(shù)目和算法執(zhí)行時間

圖10 無法識別的匹配碎塊

算法的準確程度受各個閾值影響較大,但如何選取合適的閾值是算法的難點,各閾值取值和碎塊的網(wǎng)格精度、尺寸、材質等因素有關,通過統(tǒng)計獲取初始閾值,然后根據(jù)實驗結果人工進行調整獲得最終閾值。對于輪廓比較復雜或輪廓曲線重合較少的碎塊,算法可能存在著不能正確匹配的情況,如圖10所示。由圖10可知,這兩個斷裂面標出的部分應該是匹配的,即一個斷裂面和另一個斷裂面部分匹配。還有一種情況是因為算法采取角點距離矩陣進行輪廓曲線的粗匹配,所以當輪廓曲線無角點或只有一個角點時,本文算法無法使用。

5 結 論

針對當前斷裂面匹配算法大多只適合表面粗糙特征豐富的斷裂面、表面光滑特征稀少的斷裂面無法匹配的現(xiàn)狀,本文提出以輪廓曲線為特征進行斷裂面匹配。算法通過將區(qū)域生長算法和邊界跟蹤算法相結合,避免了兩個算法各自的不足之處,分割出的斷裂面邊界光滑準確,提取的輪廓頂點形成封閉且序列化的曲線。采用的兩級輪廓曲線匹配算法,先排除了大部分不匹配的輪廓曲線,大大減少了細匹配的搜索空間,提高了匹配的速度和準確率。以輪廓曲線為特征,不要求斷裂面必須具有豐富的特征,因此對于光滑和粗糙的斷裂面均適合,實驗結果表明該算法能實現(xiàn)較復雜碎塊的匹配,且具有較快的匹配速度。

[1] PAPAIOANNOU G, EVAGGELIA A K. Reconstruction of three-dimensional objects through matching of their parts [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(1): 184-187.

[2] CHEN Hui, BHANU B. 3D free-form object recognition in range images using local surface patches [J]. Pattern Recognition Letters, 2007, 28(10): 1252-1262.

[3] HUANG Q X, FLORY S, GELFAND N. Reassembling fractured objects by geometric matching [J]. ACM Transactions on Graphics, 2006, 25(3): 569-578.

[4] WINKELBACH S, FRIEDRICH M. Pairwise matching of 3D fragments using cluster trees [J]. International Journal of Computer Vision, 2008, 78(1): 1-13.

[5] 王堅, 周來水. 基于最大權團的曲面粗匹配算法 [J]. 計算機輔助設計與圖形學學報, 2008, 20(2): 167-173. WANG Jian, ZHOU Laishui. Surface rough matching algorithm based on maximum weight clique [J]. Journal of Computer-Aided Design & Computer Graphics, 2008, 20(2): 167-173.

[6] ALTANTSETSEG E, MATSUYAMA K, KONNO K. Pairwise matching of 3D fragments using fast Fourier transform [J]. The Visual Computer, 2014, 30(6): 929-938.

[7] POKRASS J, BRONSTEIN A M. Partial shape matching without point-wise correspondence [J]. Numerical Mathematics: Theory, Methods and Applications, 2013, 6(1): 223-244.

[8] PAPAODYSSEUS C, ARABADJIS D, EXARHOS M. Efficient solution to the 3D problem of automatic wall paintings reassembly [J]. Computers & Mathematics with Applications, 2012, 64(8): 2712-2734.

[9] 劉勝蘭. 逆向工程中自由曲面與規(guī)則曲面重建關鍵技術研究 [D]. 南京: 南京航空航天大學, 2004.

[10]曾接賢, 劉秀朋, 符祥. 角點距離矩陣和同心圓劃分的曲線描述與匹配 [J]. 中國圖象圖形學報, 2012, 17(8): 1011-1020. ZENG Jiexian, LIU Xiupeng, FU Xiang. Representation and matching for planar curve based on corner distance matrix and concentric circles [J]. Journal of Image and Graphics, 2012, 17(8): 1011-1020.

[11]張小洪, 雷明, 楊丹. 基于多尺度曲率乘積的魯棒圖像角點檢測 [J]. 中國圖象圖形學報, 2007, 12(7): 1270-1275. ZHANG Xiaohong, LEI Ming, YANG Dan. Robust image corner detection based on multi-scale curvature product [J]. Journal of Image and Graphics, 2007, 12(7): 1270-1275.

[12]丁愛玲, 周琳, 李鵬. 計算機圖形學 [M]. 西安: 西安電子科技大學出版社, 2005: 99-104.

[13]劉嘉敏, 王玲, 蘭逸君, 等. 基于外耳輪廓邊緣信息的人耳識別 [J]. 計算機輔助設計與圖形學學報, 2008, 20(3): 337-342. LIU Jiamin, WANG Ling, LAN Yijun, et al. Ear recognition based on the edge information of the auricle contour [J]. Journal of Computer-Aided Design & Computer Graphics, 2008, 20(3): 337-342.

[14]江剛武. 空間目標相對位置和姿態(tài)的抗差四元數(shù)估計 [D]. 鄭州: 解放軍信息工程大學, 2009.

[15]HUANG Q X. 3D puzzles: reassembling fractured objects by geometric matching[EB/OL]. [2015-09-29]. http: ∥www.geometrie.tuwien.ac.at/ig/3dpuzzles. html.

(編輯 趙煒)

Fracture Surfaces Matching Based on Contour Curve

LI Qunhui1,ZHANG Junzu1,GENG Guohua2,ZHOU Mingquan3

(1. School of Sciences, Chang’an University, Xi’an 710064, China; 2. School of Information and Technology, Northwest University, Xi’an 710069, China; 3. College of Information Science and Technology, Beijing Normal University, Beijing 100875, China)

The existing matching algorithm of fracture surfaces is mainly suitable for rough surfaces with rich features but not for smooth surfaces with rare features. To solve this problem, an algorithm based on contour curve is proposed for fracture surfaces matching. Firstly, the algorithm combines region growing algorithm and boundary tracking algorithm for surface segmentation and contour extraction simultaneously. Next, the contour matching includes rough matching based on the corner point distance matrix, which can eliminate most of the dissimilar contour pairs, and fine matching based on Hausdorff distance according to the curvatures and torsions of all contour curve vertices. Finally, the quaternion method is used to calculate rigid transformation based on contour pairs. The optimal matching is the fragment pairs which satisfy the cross-boundary continuity detection and have minimum errors. We use a variety of rough and smooth fracture surfaces of different materials to test the algorithm. Experimental results show that the algorithm can achieve better matching of fracture surfaces with rare or abundant features.

fracture surfaces matching; fracture surfaces segmentation; contour curve matching; cross-boundary continuity detection

2015-12-08。 作者簡介:李群輝(1975—),女,博士,講師。 基金項目:國家自然科學基金資助項目(61373117);陜西省科技計劃資助項目(2016JM6081)。

時間:2016-07-14

10.7652/xjtuxb201609017

TP301.6

A

0253-987X(2016)09-0105-06

網(wǎng)絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20160714.1117.006.html