趙夫群, 周明全

?

一種有效的秦俑碎塊匹配算法①

趙夫群1,2, 周明全2

1(咸陽師范學(xué)院教育科學(xué)學(xué)院, 咸陽 712000)2(西北大學(xué)信息科學(xué)與技術(shù)學(xué)院, 西安 710127)

針對秦俑碎塊的三維網(wǎng)格數(shù)據(jù)模型, 提出了一種基于特征輪廓線的碎塊斷裂面匹配算法. 首先, 對數(shù)據(jù)模型進(jìn)行紋理貼圖、去噪、補(bǔ)洞、簡化數(shù)據(jù)模型等預(yù)處理, 然后提取碎塊的主輪廓線和次輪廓線, 進(jìn)而提取出碎塊的特征輪廓線, 最后根據(jù)角點(diǎn)對特征輪廓線進(jìn)行分段, 并采用計(jì)算最長公共子序列的方法對分段曲線進(jìn)行匹配, 完成特征輪廓線的匹配, 從而實(shí)現(xiàn)碎塊斷裂面的匹配. 實(shí)驗(yàn)結(jié)果表明, 該算法是一種有效的、精確的秦俑碎塊匹配方法.

秦俑; 碎塊匹配; 特征輪廓線; 角點(diǎn); 最長公共子序列; 曲率; 撓率

近年來, 圖像配準(zhǔn)技術(shù)發(fā)展迅速, 應(yīng)用廣泛[1-3], 三維破碎剛體的匹配拼接也成為了一個(gè)研究熱點(diǎn). 破碎剛體的匹配方法主要分為兩大類: 基于輪廓線的匹配方法和基于斷裂面的匹配方法. 對于薄壁類的文物碎片, 如陶器碎片、壁畫等, 以輪廓線為特征的碎片匹配是目前運(yùn)用的主要方法[4,5]. 而對于厚度不可忽略的碎塊, 既可以根據(jù)輪廓曲線進(jìn)行匹配, 也可以根據(jù)斷裂面進(jìn)行匹配. 若以輪廓線為特征進(jìn)行匹配, 那斷裂面輪廓線的提取就是其中關(guān)鍵的一步, 提取結(jié)果的好壞往往對匹配的結(jié)果影響特別大. 目前針對基于輪廓線的碎塊匹配, 很多研究者提出了一些匹配算法[6-9], 這些算法都是運(yùn)用斷裂面面上的某些特征直接提取斷裂面的輪廓曲線, 因而在匹配精度上還存在一定的不足, 而本文則是采用基于特征輪廓線的方法來進(jìn)行秦俑碎塊斷裂面的匹配[10]. 這里的特征輪廓線與一般提到的輪廓線有所不同, 是指模型斷裂面和外表面的交線, 是由主輪廓線和次輪廓線的片段共同形成的. 主輪廓線是指模型的邊界線, 它是構(gòu)成特征輪廓線的主要部分, 次輪廓線是指碎塊的外表面與斷裂面的交線. 由于秦俑碎塊存在一定程度的磨損和損壞, 特征輪廓線能更好地描述碎塊的輪廓特征.

由于通過三維激光掃描儀采集到的秦俑碎塊的三角網(wǎng)格模型不僅數(shù)據(jù)量非常大, 含有大量噪聲, 而且還存在孔洞, 因此不能直接用于碎塊的匹配拼接, 需要進(jìn)行預(yù)處理. 本文主要進(jìn)行了以下幾個(gè)方面的預(yù)處理: 采用基于OpenGL的新式OBJ文件紋理貼圖方法進(jìn)行了紋理貼圖處理[11], 將紋理圖像映射到數(shù)據(jù)模型的對應(yīng)位置上, 使得數(shù)字化后的三維模型看起來更加逼真. 在確保數(shù)據(jù)模型的重要特征不會丟失的情況下, 采用三邊濾波去噪算法對數(shù)據(jù)模型進(jìn)行去噪處理[12]. 采用區(qū)域生長算法對三角網(wǎng)格模型的孔洞進(jìn)行修補(bǔ)[13], 使得數(shù)據(jù)模型更加完整. 最后, 采用基于特征保持和三角形優(yōu)化的方法對三角網(wǎng)格模型進(jìn)行簡化[14], 在保持原有模型的幾何形狀不變的基礎(chǔ)上, 大幅地減少了模型中三角面片的數(shù)量, 有效地提高了算法的執(zhí)行效率.

數(shù)據(jù)預(yù)處理完成后, 就可以進(jìn)行碎塊的匹配操作了. 本文首先采用邊界提取算法提取碎塊的主輪廓線, 再提取斷裂面的次輪廓線, 并由主輪廓線和次輪廓線的片段共同形成特征輪廓線. 然后, 采用四次B樣條曲線將特征輪廓線擬合成光滑的空間曲線, 并根據(jù)角點(diǎn)對該曲線進(jìn)行分段, 提取分段曲線上頂點(diǎn)的曲率和撓率, 組成特征字符串. 最后, 通過特征字符串匹配的方式完成特征輪廓曲線的匹配, 從而實(shí)現(xiàn)斷裂面的匹配.

1 提取特征輪廓線

本文通過改進(jìn)文獻(xiàn)[7]提出的特征輪廓線提取方法來提取秦俑碎塊的特征輪廓線. 首先提取主輪廓線, 然后提取次輪廓線, 再由主輪廓線和次輪廓線的片段共同形成特征輪廓線. 碎塊主輪廓線、次輪廓線和特征輪廓線的示意圖如圖1所示.

(a)主輪廓線 (b)次輪廓線 (c)特征輪廓線

1.1 提取主輪廓線

主輪廓線的提取采用基于邊的重?cái)?shù)判斷的模型邊界提取算法, 即根據(jù)邊的重?cái)?shù)的值判斷該邊是否為邊界邊. 設(shè)是三維模型的邊集,表示模型中頂點(diǎn)的個(gè)數(shù),表示模型中邊的條數(shù), 則邊集定義為:

主輪廓線的具體提取步驟如下:

①設(shè)置兩個(gè)堆棧Stack1和Stack2, 用于存儲主輪廓線的點(diǎn)集, 初始將中的邊都標(biāo)記為False.

③取堆棧Stack1和Stack2的棧頂元素為當(dāng)前兩個(gè)頂點(diǎn), 分別按照相反方向搜索模型的邊集, 在當(dāng)前點(diǎn)的鄰接點(diǎn)集中搜索與其構(gòu)成的邊的重?cái)?shù)為1的點(diǎn), 且這條邊標(biāo)記為false, 并將該點(diǎn)加入當(dāng)前堆棧.

④判斷堆棧Stack1和Stack2的棧頂元素是否相同, 若相同則轉(zhuǎn)步驟⑤, 表示兩個(gè)搜索方向搜索的點(diǎn)已匯合, 構(gòu)成了封閉的主輪廓線, 否則轉(zhuǎn)步驟③, 繼續(xù)搜索.

⑤將堆棧Stack1和Stack2中所有的頂點(diǎn)出棧, 由此構(gòu)成了該三角網(wǎng)格模型的主輪廓線點(diǎn)集.

1.2提取次輪廓線

因?yàn)榇屋喞€是碎塊外表面和斷裂面的交線, 所以構(gòu)成次輪廓線的點(diǎn)位于碎片斷裂面的邊緣, 因此識別碎塊的斷裂面是提取次輪廓線的關(guān)鍵一步. 首先對三維網(wǎng)格模型進(jìn)行曲面分割, 然后根據(jù)曲面特征區(qū)分出斷裂面和原始面, 再對識別出的斷裂面提取次輪廓線點(diǎn)集.

1.2.1曲面分割

秦俑碎塊的曲面分割是一個(gè)將碎塊的外表面以棱邊為界限分割成多張曲面的過程. 通常斷裂面與原始面的交界處存在突變, 在幾何上表現(xiàn)為棱邊兩側(cè)位于不同曲面的兩個(gè)相鄰三角面片的法矢夾角比較大. 本文采用區(qū)域生長算法[15]來完成曲面的分割, 具體步驟如下:

① 判斷相鄰三角面片法矢的夾角是否大于給定閾值, 若大于給定閾值則這兩個(gè)三角面片被分割在兩個(gè)不同的曲面上, 若小于給定閾值則這兩個(gè)三角片屬于同一曲面. 重復(fù)該過程, 直到所有三角面 片分割完成為止.

② 逐一檢查分割曲面, 若曲面特別小, 則將其合并到相鄰的曲面中; 若曲面較大, 則要判斷該曲面與其相鄰曲面的平均法矢夾角, 若小于給定閾值則進(jìn)行合并, 否則不合并.

1.2.2提取斷裂面

一般情況下, 斷裂面和原始面的顯著區(qū)別在于斷裂面較原始面更為粗糙, 在幾何特征的表現(xiàn)上就是斷裂面上頂點(diǎn)的法向量變化較大, 因此可以根據(jù)斷裂面上所有頂點(diǎn)的法向量的變化情況來區(qū)分?jǐn)嗔衙婧驮济?

1.2.3提取次輪廓線

次輪廓線位于斷裂面的邊界, 是特征值變化的極值點(diǎn). 在曲面分割階段提取的斷裂面的邊界可能會不完整, 所以要首先進(jìn)行斷裂面的二級鄰接生長, 然后再對生長后的斷裂面提取特征極值點(diǎn), 進(jìn)而提取次輪廓線.

②采用步驟①的方法, 對一階鄰接生長的曲面再進(jìn)行一次鄰接曲面生長, 就得到了二級鄰接生長曲面.

1.3 提取特征輪廓線

在提取了秦俑碎塊的三角網(wǎng)格模型的主輪廓線和次輪廓線后, 就可以提取模型的特征輪廓線了. 這里的特征輪廓線是指模型斷裂面和外表面的交線, 是由主輪廓線的片段和次輪廓線的片段共同形成的. 特征輪廓線的具體提取方法是: 對于存在斷裂面的部分只選取相應(yīng)的次輪廓線, 否則就選取主輪廓線, 這些選取的線段就構(gòu)成了三角網(wǎng)格曲面模型的最終特征輪廓線. 但是, 這里提取到的特征輪廓線是空間離散曲線, 需要采用四次B樣條曲線將其擬合成光滑的空間曲線. B樣條曲線的定義如下[17]:

2 基于特征輪廓線的斷裂面匹配

本文的特征輪廓線的匹配思想是: 首先根據(jù)角點(diǎn)對特征輪廓線分段, 然后計(jì)算分段曲線上每個(gè)頂點(diǎn)的曲率和撓率, 由此得到了用曲率和撓率所描述的特征串, 最后通過對特征串的匹配來完成特征輪廓線的匹配, 進(jìn)而實(shí)現(xiàn)了斷裂面的匹配.

2.1 計(jì)算曲率和撓率

2.2 斷裂面的匹配

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

為了驗(yàn)證本文算法的有效性, 這里選取了三組K9901坑出土的秦俑碎塊, 如圖2所示. 第1組數(shù)據(jù)是掃描的秦俑肩膀部位的碎塊, 第2組和第3組數(shù)據(jù)是掃描的不同秦俑胸前部位的碎塊.

(a) 第1組碎塊

(b) 第2組碎塊

(c) 第3組碎塊

對這三組碎塊, 首先根據(jù)本文算法提取其斷裂面的主輪廓線、次輪廓線和特征輪廓線, 然后分別基于主輪廓線和特征輪廓線進(jìn)行碎塊的匹配, 匹配結(jié)果如圖3所示, 這里的每組碎塊的匹配結(jié)果中的圖(a)是基于主輪廓線的匹配結(jié)果, 圖(b)是基于特征輪廓線的匹配結(jié)果, 很明顯, 第1組圖(a)的匹配中出現(xiàn)了部分錯(cuò)位, 第2組圖(a)的匹配結(jié)果不理想, 存在很大的斷裂面拼接處的縫隙, 存在較大誤差, 第3組圖(a)的匹配結(jié)果同樣存在較大孔洞. 而這三組碎塊的圖(b)的匹配結(jié)果較為理想, 基本做到了符合實(shí)際效果的匹配結(jié)果, 因此基于特征輪廓線的匹配是一種較為有效準(zhǔn)確的碎塊匹配方法.

(a)主輪廓線匹配結(jié)果 (b)特征輪廓線匹配結(jié)果

第1組碎塊的匹配結(jié)果

(a)主輪廓線匹配結(jié)果 (b)特征輪廓線匹配結(jié)果

第2組碎塊的匹配結(jié)果

(a)主輪廓線匹配結(jié)果 (b)特征輪廓線匹配結(jié)果

4 結(jié)語

通過對秦俑碎塊的數(shù)據(jù)分析發(fā)現(xiàn), 簡單的特征輪廓線不能很好地描述其輪廓特點(diǎn), 因此本文采用特征輪廓線特征來進(jìn)行碎塊的匹配. 首先通過紋理貼圖、去噪、孔洞修補(bǔ)、簡化網(wǎng)格數(shù)據(jù)模型等操作進(jìn)行數(shù)據(jù)預(yù)處理, 然后提取碎塊的主輪廓線和次輪廓線, 進(jìn)而提取碎塊的特征輪廓線, 再次采用四次B樣條曲線將特征輪廓線擬合成光滑的空間曲線, 并對該曲線進(jìn)行分段以完成特征輪廓曲線的匹配, 從而實(shí)現(xiàn)斷裂面的匹配. 實(shí)驗(yàn)證明, 較一般的輪廓線匹配算法, 本文的特征輪廓線匹配算法在匹配精度上有了很大的提高, 是一種有效的秦俑碎塊斷裂面匹配算法. 但是由于歷史原因, 秦俑的碎塊可能存在缺失、風(fēng)化、二次斷裂、受潮和變形等各個(gè)方面的問題, 因此數(shù)據(jù)比較復(fù)雜, 今后的研究中要綜合考慮各個(gè)方面的因素, 提出更加有效的秦俑碎塊匹配算法.

1 趙靜,趙小樂.基于Laplace的LSSIM圖像配準(zhǔn)算法.計(jì)算機(jī)系統(tǒng)應(yīng)用,2015,24(9):160–165.

2 陳欲勐,馬無錫.基于快速模板匹配的金標(biāo)試紙條圖像配準(zhǔn). 計(jì)算機(jī)系統(tǒng)應(yīng)用,2015,24(5):19–25.

3 葛盼盼,陳強(qiáng).基于SURF特征提取的遙感圖像自動配準(zhǔn). 計(jì)算機(jī)系統(tǒng)應(yīng)用,2014,23(3):16–24.

4 潘榮江,孟祥旭,屠長河.一種基于LCS 的物體碎片自動拼接方法.計(jì)算機(jī)學(xué)報(bào),2005,28(3): 351–356.

5 Shin H, Doumas C, Funkhouser T, et al. Analyzing fracture patterns in Theran wall paintings. Proc. of the 11th International Conference on Virtual Reality, Archaeology and Cultural Heritage. Eurographics Association. 2010. 71–78.

6 李姬俊男,耿國華,周明全,等.一種基于鄰接約束的交互式文物模型復(fù)原系統(tǒng).西北大學(xué)學(xué)報(bào)(自然科學(xué)版),2016, 46(1):55–60.

7 杜建麗,茹少峰,樊少榮,等.基于B-樣條表示的物體輪廓曲線匹配.西北大學(xué)學(xué)報(bào)(自然科學(xué)版),2005,35(5):527–530.

8 呂科,耿國華,周明全,等.基于傅立葉變換的三維輪廓線快速匹配算法.西北大學(xué)學(xué)報(bào)(自然科學(xué)版),2003,33(2): 151–154.

9 Cohen F, Taslidere E, Liu ZX, et al. Virtual reconstruction of archaeological vessels using expert priors & surface markings. Proc. of IEEE Conference on Computer Vision and Pattern Recognition. San Francisco, USA. Computer Society. 2010. 7–14.

10 李康,李靜,孫家澤.一種改進(jìn)的薄壁文物碎片特征輪廓線提取技術(shù).圖學(xué)學(xué)報(bào),2015,36(2):251–256.

11 王波,孫蔚.基于OpenGL的新式OBJ文件紋理貼圖方法研究.計(jì)算機(jī)與數(shù)字工程,2015,310(8):1497–1500.

12 張鑫,王章野,范涵奇,等.保特征的三維模型的三邊濾波去噪算法.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2009,21(7): 936–942.

13 劉云華,呂劍,朱林,等.基于區(qū)域生長的三角網(wǎng)格模型孔洞修補(bǔ)方法.計(jì)算機(jī)工程,2014,40(10):239–244.

14 張必強(qiáng),邢淵,阮雪榆.基于特征保持和三角形優(yōu)化的網(wǎng)格模型簡化.上海交通大學(xué)學(xué)報(bào),2004,38(8):1373–1377.

15 李群輝,周明全,耿國華.破碎剛體三角網(wǎng)格模型的斷裂面分割.計(jì)算機(jī)應(yīng)用,2011,31(8):2204–2205,2216.

16 Deschenes F, Ziou D. Detection of line junctions and line terminations using curvilinear features. Pattern Recognition Letters, 2000, 21(6): 637–649.

17 丁愛玲,周琳,李鵬.計(jì)算機(jī)圖形學(xué).西安:西安電子科技大學(xué)出版社,2005.

Effective Blocks Matching Algorithm of Terracotta Warrior

ZHAO Fu-Qun1,2, ZHOU Ming-Quan2

1(School of Education Science, Xianyang Normal University, Xianyang 712000, China)2(School of Information Science and Technology, Northwest University, Xi’an 710127, China)

Aiming at 3D mesh data model of Terracotta Warrior blocks, a block fracture surface matching algorithm based on feature contour is proposed in the paper. Firstly, the data model is pretreated, such as texture map, data denoising, hole filling, data model simplification and so on. Secondly, the primary contour and secondary contour are extracted, and then the feature contour is extracted too. Lastly, the feature contour is segmented according to the corner point in order to match the feature contour by the longest common subsequence method, then the contour feature matching is completed, and the fracture surface matching is achieved. The experimental results show that the algorithm proposed in the paper is an effective and accurate Terracotta Warrior blocks matching method.

Terracotta Warrior; blocks matching; feature contour; corner point; the longest common subsequence; curvature; torsion

國家自然科學(xué)基金(61373117)

2016-06-29;

2016-08-31

[10.15888/j.cnki.csa.005654]