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

趙夫群, 周明全

?

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

趙夫群1,2, 周明全2

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

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

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

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

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

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

1 提取特征輪廓線

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

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

1.1 提取主輪廓線

主輪廓線的提取采用基于邊的重數判斷的模型邊界提取算法, 即根據邊的重數的值判斷該邊是否為邊界邊. 設是三維模型的邊集,表示模型中頂點的個數,表示模型中邊的條數, 則邊集定義為:

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

①設置兩個堆棧Stack1和Stack2, 用于存儲主輪廓線的點集, 初始將中的邊都標記為False.

③取堆棧Stack1和Stack2的棧頂元素為當前兩個頂點, 分別按照相反方向搜索模型的邊集, 在當前點的鄰接點集中搜索與其構成的邊的重數為1的點, 且這條邊標記為false, 并將該點加入當前堆棧.

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

⑤將堆棧Stack1和Stack2中所有的頂點出棧, 由此構成了該三角網格模型的主輪廓線點集.

1.2提取次輪廓線

因為次輪廓線是碎塊外表面和斷裂面的交線, 所以構成次輪廓線的點位于碎片斷裂面的邊緣, 因此識別碎塊的斷裂面是提取次輪廓線的關鍵一步. 首先對三維網格模型進行曲面分割, 然后根據曲面特征區分出斷裂面和原始面, 再對識別出的斷裂面提取次輪廓線點集.

1.2.1曲面分割

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

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

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

1.2.2提取斷裂面

一般情況下, 斷裂面和原始面的顯著區別在于斷裂面較原始面更為粗糙, 在幾何特征的表現上就是斷裂面上頂點的法向量變化較大, 因此可以根據斷裂面上所有頂點的法向量的變化情況來區分斷裂面和原始面.

1.2.3提取次輪廓線

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

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

1.3 提取特征輪廓線

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

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

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

2.1 計算曲率和撓率

2.2 斷裂面的匹配

3 實驗結果與分析

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

(a) 第1組碎塊

(b) 第2組碎塊

(c) 第3組碎塊

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

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

第1組碎塊的匹配結果

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

第2組碎塊的匹配結果

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

4 結語

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

1 趙靜,趙小樂.基于Laplace的LSSIM圖像配準算法.計算機系統應用,2015,24(9):160–165.

2 陳欲勐,馬無錫.基于快速模板匹配的金標試紙條圖像配準. 計算機系統應用,2015,24(5):19–25.

3 葛盼盼,陳強.基于SURF特征提取的遙感圖像自動配準. 計算機系統應用,2014,23(3):16–24.

4 潘榮江,孟祥旭,屠長河.一種基于LCS 的物體碎片自動拼接方法.計算機學報,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 李姬俊男,耿國華,周明全,等.一種基于鄰接約束的交互式文物模型復原系統.西北大學學報(自然科學版),2016, 46(1):55–60.

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

8 呂科,耿國華,周明全,等.基于傅立葉變換的三維輪廓線快速匹配算法.西北大學學報(自然科學版),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 李康,李靜,孫家澤.一種改進的薄壁文物碎片特征輪廓線提取技術.圖學學報,2015,36(2):251–256.

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

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

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

14 張必強,邢淵,阮雪榆.基于特征保持和三角形優化的網格模型簡化.上海交通大學學報,2004,38(8):1373–1377.

15 李群輝,周明全,耿國華.破碎剛體三角網格模型的斷裂面分割.計算機應用,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 丁愛玲,周琳,李鵬.計算機圖形學.西安:西安電子科技大學出版社,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

國家自然科學基金(61373117)

2016-06-29;

2016-08-31

[10.15888/j.cnki.csa.005654]