一種基于鄰接約束的交互式文物模型復(fù)原系統(tǒng)

李姬俊男,耿國華,周明全,李姍姍

(西北大學 信息科學與技術(shù)學院， 陜西 西安　710127)

?

一種基于鄰接約束的交互式文物模型復(fù)原系統(tǒng)

李姬俊男,耿國華,周明全,李姍姍

(西北大學 信息科學與技術(shù)學院， 陜西 西安710127)

提出了一種基于鄰接約束的計算機輔助匹配方法,該方法的重點在于關(guān)注處理流程中的用戶領(lǐng)域經(jīng)驗和直覺。通過對拼合過程中幾何約束的定性和定量分析,并定義一種靈活、可擴展的描述符,將碎片的所屬位置限制在一個合理的空間范圍內(nèi),由此確定拼合線索。在系統(tǒng)的設(shè)計上考慮到專家的領(lǐng)域知識,通過規(guī)范其操作規(guī)則,引導(dǎo)受損文物的重組。實驗表明該系統(tǒng)的有效性。

文物虛擬復(fù)原;人機交互;鄰接約束;幾何特征可視化

虛擬復(fù)原問題是計算機圖形學、模式識別、可視化技術(shù)和機器智能眾多領(lǐng)域里一個頗具挑戰(zhàn)的問題。20世紀初是該問題研究較為集中的時期,此后也不斷有學者從事這一領(lǐng)域的深入研究,至今虛擬復(fù)原作為圖形學落地的重要代表性技術(shù)依然是研究的熱點。根據(jù)虛擬復(fù)原過程中是否有人為干涉,可分為自動化的復(fù)原方法和半自動的復(fù)原方法;在自動化復(fù)原中,根據(jù)所選取的不同特征,可分為基于幾何特征的虛擬復(fù)原和非幾何特征的復(fù)原。

根據(jù)對文物模型數(shù)據(jù)的不同抽象表示方法,虛擬復(fù)原技術(shù)大體上可以分為兩類:一類將文物視為厚度可以忽略的薄壁碎片,針對這種數(shù)據(jù)特性設(shè)計出了基于空間輪廓曲線的拼合方案,代表性研究為茹少峰[1]提出的復(fù)原技術(shù),其解決問題的思想是以幾何特征參數(shù)對空間曲線進行編碼,通過對比編碼確定曲線的匹配程度,進而確定輪廓曲線所屬物體的拼合關(guān)系,在他的實驗中選取了微分幾何量作為特征參數(shù)。這一方法是對二維平面曲線匹配的延伸,二維曲線的匹配通常應(yīng)用于研究壁畫等物體的拼合[5]。此外還有學者在空間曲線的編碼策略和匹配策略上不斷改進算法,Cristina[6]運用動態(tài)規(guī)劃的思想將曲線上頂點的曲率進行編碼,對比編碼求得曲線的相鄰關(guān)系。針對空間三維的輪廓線匹配拼接,ü?oluk[7]將離散的幾何特征參數(shù)構(gòu)成特征向量,把空間曲線匹配轉(zhuǎn)換成簡單的特征串匹配,繼而完成兩碎片的拼接。Kong[8]給出了曲線親密度的定義,通過親密度得到曲線的鄰接關(guān)系,計算能量最小化將相鄰的空間曲線進行對齊。Wolfson[9]等人對輪廓線先進行重采樣,以采樣點的曲率值進行字符編碼,最后運用哈希算法進行匹配。Oxholm[10]等人綜合輪廓曲線上頂點的曲率、撓率和顏色值為特征描述符,采用最長公共子串的匹配方法尋找最佳相鄰碎片對,該方法能夠較好地支持碎片的部分匹配。Cohen[11]提出了以輪廓曲線上頂點的矩不變量為特征,尋找特征匹配的對應(yīng)關(guān)系,以距離的誤差作為曲線對齊的評價標準。

另一類方法則將文物厚度作為重要的拼合線索,針對這一類型的數(shù)據(jù)特性設(shè)計出了基于斷裂部位空間曲面匹配的拼合方案,代表性研究為Huang[4],其設(shè)計了一個完整的復(fù)原管線,包括斷裂面的分割與識別、積分特征的提取與表示、兩兩對齊和多碎片拼合,并率先采用積分幾何量勾勒出碎片表面的尖銳特征,從而對斷裂面進行分割提取,采用基于向前搜索技術(shù)將兩兩斷裂面進行匹配對齊,將對齊的碎片進行融合從而重組文物。決定這一算法有效與否的關(guān)鍵在于曲面的分割和特征的匹配。

除上述研究外,還有半自動或以人機交互為主要手段的虛擬復(fù)原方法。半自動的典型方法是“傳統(tǒng)復(fù)原方式”,即考古學家和文物修復(fù)工作者采用的重組方法，不以數(shù)字模型為基礎(chǔ),而是直接用手工或者聯(lián)合技術(shù),例如攝影技術(shù)對碎片復(fù)原。此過程涉及碎片的分類、碎片類型目錄的構(gòu)造、碎片配對等。這一方法的問題在于,復(fù)原的好壞很大程度取決于操作者的經(jīng)驗,并且耗時間過長;此外還有Papaioannou[12]采用的人工智能方法處理幾何特征的重組流程。采用交互手段解決虛擬復(fù)原研究的代表為Parikh[13],該方法通過從碎片集合中迭代地選取明顯的可匹配部件,使用戶輕易的重組出文物模型的外形,在此基礎(chǔ)上對細小的、拼合線索不明顯的碎片采用自動化方法做拼合驗證;Mellado[14]提出了一種可以實時反饋的重組流程,并通過一個觸摸屏用戶界面設(shè)計,允許領(lǐng)域?qū)＜抑贫ㄋ槠g初始相對位置和方向。上述方法為解決復(fù)雜拼合問題提供了研究思路。

復(fù)雜拼合問題的特殊性,客觀反映出了過分依賴算法求解的局限性,基于幾何形狀度量的方法在這類文物模型上難以得到正確的參數(shù)信息,因而對拼合階段的算法魯棒性提出了苛刻的要求,也促使本研究轉(zhuǎn)向交互手段以尋求突破。本文提出了一種基于鄰接約束的計算機輔助匹配方法,該方法的重點在于關(guān)注處理流程中的用戶領(lǐng)域經(jīng)驗和直覺。

對于斷裂面受損嚴重的情況,斷裂面信息和輪廓線信息均難以保證實驗結(jié)果的有效,如圖1所示,由于該陶俑其他部位的碎片都已完成拼合,余下的碎片在幾何外形上沒有明顯的拼合線索,并且對于是否存在缺失碎片的情況也是未知的,從而為拼合工作帶來了極大的挑戰(zhàn);此時只能引入交互手段,在給出可視化特征的基礎(chǔ)上,由領(lǐng)域?qū)＜掖_定碎片的鄰接關(guān)系。

圖1　幾何特征失效的拼合情況Fig.1　The failure case of merging by geometric features

約束的選擇通常可以指定一個或多個,例如本研究所采用的鄰接約束,以及有標注過部位信息的部位約束,甚至是厚度信息、紋理信息等物理約束;約束的選擇和具體的案例有關(guān),需要根據(jù)文物的外形、材質(zhì)等予以綜合考慮。因而，這種描述符的優(yōu)點是靈活、可擴展,限制在于所選擇的約束是必須能夠合理量化的;并且約束條件的選取范圍應(yīng)當盡可能的小,約束范圍的增大可以增加系統(tǒng)的靈活性和描述能力,但同時也會增大實現(xiàn)的復(fù)雜性。

鄰接約束被定義為允許用戶交互地選擇相鄰兩個碎片之間預(yù)期的拼合區(qū)域,以選取對應(yīng)點為主要手段,由這些對應(yīng)點確定的潛在對應(yīng)區(qū)域?qū)挥糜谟嬎闫ヅ鋵嶓w所需的剛體變換,最終輸出一個滿足給定約束集合中的最優(yōu)映射,圖2為選取鄰接約束的示意圖。針對鄰接約束,量化的標準為預(yù)期拼合區(qū)域的相似程度,描述該相似程度可類比部分匹配問題中的配準求解,通過定義碎片間的距離能量函數(shù)予以度量。

圖2　鄰接約束的選取以及對拼合結(jié)果的影響Fig.2　Select the adjacent constraints and impact on the registration results

該方法中還涉及以下定義:

碎片:數(shù)字化后的文物碎片模型,可由點云或網(wǎng)格數(shù)據(jù)類型表示。

約束:一條約束規(guī)則定義了兩個碎片間的空間關(guān)系,這種空間關(guān)系不一定直觀地反映在幾何外形上,可能蘊涵在其他物理屬性中。

群組:用于描述碎片拼合的層次結(jié)構(gòu),存儲形式為一個碎片的集合,這些碎片可以滿足約束條件下的匹配;同時群組的定義是遞歸的,群組可以由其他群組組成。

1　約束圖構(gòu)造

約束圖是對鄰接碎片關(guān)系的編碼,參與編碼的內(nèi)容包括:碎片、碎片所在的群組以及它們之間的約束,通過碎片間的關(guān)聯(lián)約束對不同的碎片或碎片組進行分層編碼。約束圖為每個碎片或組定義一個節(jié)點,每條邊代表一個約束,整個圖代表了一個求解序列,即約束序列應(yīng)能夠利用用戶定義的層次結(jié)構(gòu)進行重新調(diào)整并且形成合適的序列。為了確保求解序列的唯一性,設(shè)計約束圖為樹形結(jié)構(gòu),并以剛體變換要能夠縮減樣本之間距離為鄰接約束條件。

圖3　鄰接約束下的二維約束圖示例Fig.3　An example of two-dimensional constraint graph adjacency constraint

圖3給出了采用約束圖求解的具體步驟:

步驟1根據(jù)碎片及其約束的層次結(jié)構(gòu)初始化約束圖,并根據(jù)分層策略,對低層次的碎片對(即約束圖中的葉節(jié)點)進行相對變換。然后分別調(diào)整碎片A與碎片B、碎片C與碎片D的相對轉(zhuǎn)換使之滿足約束條件,過程如圖3(b)所示。

步驟2對得到的碎片構(gòu)成的碎片組,重復(fù)步驟1。但是,在重組E和F的時候要注意,對它們進行轉(zhuǎn)換的同時要考慮到其碎片成員。圖3(c)給出了重組碎片通過相互匹配形成約束圖的過程。

步驟3根據(jù)用戶所定義的約束圖重復(fù)上述兩個步驟,使重組過程在約束圖中向上擴散,直到所有的碎片被放置在最終位置,實現(xiàn)對象的完整重組。

步驟4刪除中間層來減少全局能量消耗,最終得到全局連貫性更好的重組結(jié)果，結(jié)果見圖3(d)。

2　交互式拼合過程

2.1能量最小化

對于每個鄰接約束,要盡量減少兩個樣本之間的距離,這一過程類似幾何驅(qū)動下的最近點迭代。從該角度出發(fā),可以定義每個約束的局部能量函數(shù),并采用模型間的加權(quán)平方距離予以度量,優(yōu)化目標是使全局范圍內(nèi)每個約束的能量之和最小,定義為

2.2剛體變換

剛體變換的過程中通常不考慮碎片或碎片組的縮放或傾斜因素。對于給定的碎片A或碎片組G,定義剛性變換為一個3×3旋轉(zhuǎn)矩陣RA和平移向量TA。能量方程(1)可這樣定義

碎片A的最小化輸出集是一組變換(RA,TA),但旋轉(zhuǎn)矩陣的性質(zhì)det(R)=1和RT=R-1不是線性的,不能保證所得的變換是剛性的,因此不能直接用它們來定義線性約束。在此采用迭代的方法尋找旋轉(zhuǎn)矩陣R′A,它相似于矩陣RA。找到旋轉(zhuǎn)矩陣之后對樣本進行更新,從而使迭代過程達到收斂,收斂條件通過檢查優(yōu)化過程中剩余能量是否因為約束而增加予以判斷。此外,可以采用旋轉(zhuǎn)矩陣的斜對稱矩陣進行編碼加以優(yōu)化,這樣可以使每個旋轉(zhuǎn)矩陣的編碼變量由9減少到3。

2.3交互設(shè)計

交互式的用戶界面設(shè)計對重組方法同樣重要,本研究對考古專家的用戶體驗反饋中分析發(fā)現(xiàn)得出以下4點需求:

1)交互界面設(shè)計需要支持利用約束條件對碎片進行實時的拼合,并且能夠清晰明確地反映出重組碎片過程中生成的層次約束圖。

2)在重組過程中用戶對碎片進行操作的同時還需要靈活地擴展所需約束。

3)設(shè)計的系統(tǒng)不僅能夠通過能量最小化的方法確定每個碎片的最終位置，同時還應(yīng)對拼合的結(jié)果進行評估。

4)對于漫長、復(fù)雜的碎片重組過程,任何中間狀態(tài)都要能夠修改和恢復(fù)。

最終設(shè)計出的界面由三大部分組成:

1)圖修改區(qū)。這部分是用來定義約束圖。它可以創(chuàng)建一個新的組或?qū)F(xiàn)有的組進行分割,并且能夠添加、刪除和修改現(xiàn)有的約束。

2)工作區(qū)。這個區(qū)域允許用戶在兩個不同的碎片或碎片組中選擇點來定義新的鄰接約束。這兩個工作區(qū)的主要目的是讓用戶能夠仔細觀察每一塊碎片并且能夠從碎片中選擇出距離最接近的樣本。

3)結(jié)果顯示區(qū)。這個區(qū)域用來展示重建的中間過程和最終結(jié)果,即每個能量最小化的迭代結(jié)果。

由于碎片的重組過程是一個用戶驅(qū)動的交互方式,在這一過程中可能會出現(xiàn)約束的不一致性,需要借助系統(tǒng)輔助來實現(xiàn)結(jié)果的驗證。采用以下兩種交互設(shè)計方法對這種不一致性進行檢測:

1)約束能量可視化。在最小化過程中使用不同的顏色比例來表示約束的剩余能量,藍色代表低能量,紅色代表高能量。

2)滲透。不一致的約束會造成碎片斷裂部位間的相互滲透;但與碰撞檢測不同的是,領(lǐng)域?qū)＜宜P(guān)注的不是幾何變換的過程,而是用戶界面上更為直觀的反映。本文采用GPU深度剝離方法[14]來檢測滲透,并在交互界面的約束插入?yún)^(qū)域和結(jié)果可視區(qū)域中用紅色來表示滲透現(xiàn)象。圖4顯示了滲透的例子。

在實例化過程中，如果約束數(shù)量不足或者相關(guān)點位置定義不正確,都會導(dǎo)致不合理的碎片拼合結(jié)果,可通過適當?shù)匾攵鄠€鄰接約束,對剛體變換進行微調(diào);但由于需要提供實時的能量可視化,鄰接約束會增大運算開銷。此外針對本節(jié)提出的第四點需求,將恢復(fù)當前工作所需的碎片、碎片組、樣本、層次約束圖以及約束條件,生成所含信息的XML文件,從而完成項目的恢復(fù)和加載工作。

圖4　交互環(huán)境下鄰接約束造成的模型滲透的可視化展示Fig.4　The visual display of model penetration caused by adjacency constraint in the interactive environment

3　實驗結(jié)果及分析

本文設(shè)計的交互式系統(tǒng)在Meshlab平臺上開發(fā),采用Qt5.2版本,硬件環(huán)境為IntelCorei5CPU/4GB內(nèi)存/NVIDIAGeForceGT420,工作平臺的操作系統(tǒng)是Windows7?？梢钥闯?，采用鄰接約束的方法由于引入了領(lǐng)域?qū)＜业慕?jīng)驗,使得一些幾何上無法辨別的碎片能夠拼合在一起。

表1為采用鄰接約束對無明顯幾何可匹配特征碎片拼合時,能量最小化階段的參數(shù)。通過鄰接約束的引入,迭代次數(shù)明顯降低,這是由于能量最小化只考慮鄰接約束點確定的剛體運動;從實驗結(jié)果中還可以看出,隨著待拼合碎片數(shù)目的提升,還需要在拼合得到群組上定義鄰接約束,這一過程會顯著增加迭代次數(shù)和運算開銷,因而在實際操作中應(yīng)盡量在碎片間定義鄰接約束,避免在碎片和群組間定義。

表1鄰接約束求解過程中的實驗參數(shù)

Tab.1Experimental parameters in the process of solving the adjacency constraint

模型拼合碎片數(shù)/片鄰接約束/個運算開銷/s迭代次數(shù)/次230.0173230.0245220.01125160.167

4　總　結(jié)

本文討論的重點在于復(fù)雜拼合問題的求解,通過對這一問題的細化，設(shè)計出了采用交互設(shè)計的一種求解方法,將自動拼合方法中的關(guān)鍵判定信息可視化,從而形成了一種對考古專家直觀、易于接受的系統(tǒng)。并在此基礎(chǔ)上制定了可擴展的約束描述符,以及能實時反映拼合階段的層次約束圖,實驗表明這一設(shè)計思路是靈活且有效的。

從目前的進展來看,本文對需要采取何種約束方法給出了判定依據(jù),但未能給出嚴格的定量標準,實踐中還需要根據(jù)特定文物數(shù)據(jù)類型制定解決方案。

[1]茹少峰. 破碎物體復(fù)原技術(shù)與計算機輔助文物復(fù)原研究[D].西安：西北大學,2005.

[2]RAN G, DANIEL C O. Salient geometric features for partial shape matching and similarity[J]. ACM Transactions on Graphics, 2006, 25(1):130-150.

[3]POTTMANN H, WALLNER J, HUANG Q X, et al. Integral invariants for robust geometry processing[J]. Computer Aided Geometric Design, 2009, 26(1): 37-60.

[4]HUANG Q X, Fl?RY S, GELFAND N, et al. Reassembling fractured objects by geometric matching[J]. ACM Transactions on Graphics (TOG), 2006，25(3): 569-578.

[5]SHIN H, DOUMAS C, FUNKHOUSER T, et al. Analyzing fracture patterns in Theran wall paintings[C]. Proceedings of the 11th International conference on Virtual Reality, Archaeology and Cultural Heritage: Eurographics Association, 2010: 71-78.

[6]CRISTINA H, LEITO G, STOLFI J. A multi-scale method for the re-assembly of fragmented objects[C]∥BMVC. 2000:1-10.

[7]ü?OLUK G, HAKKI T I. Automatic reconstruction of broken 3-D surface objects[J]. Computers & Graphics, 1999, 23(4): 573-582.

[8]KONG W, KIMIA B B. On solving 2D and 3D puzzles using curve matching[C]. Computer Vision and Pattern Recognition, 2001. CVPR 2001. Proceedings of the 2001 IEEE Computer Society Conference on: IEEE, 2001: 583-590.

[9]WOLFSON H J. On curve matching[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 1990, 12(5): 483-489.

[10] OXHOLM G, NISHINO K. Reassembling thin artifacts of unknown geometry[C]. Proceedings of the 12th International conference on Virtual Reality, Archaeology and Cultural Heritage: Eurographics Association, 2011: 49-56.

[11] COHEN F, LIU Z, EZGI T. Virtual reconstruction of archeological vessels using expert priors and intrinsic differential geometry information[J]. Computers & Graphics, 2013, 37(1): 41-53.

[12] PAPAIOANNOU G, KARABASSI E, THEOHARIS T. Virtual archaeologist: assembling the past[J]. IEEE Computer Graphics and Applications, 2001, 21(2):40-45.

[13] PARIKH D, SUKTHANKAR R, CHEN T, et al. Feature-based part retrieval for interactive 3D reassembly[C]∥Applications of Computer Vision, 2007. WACV′07. IEEE Workshop on IEEE,2007:14.

[14] MELLADO N, REUTER P, SCHLICK C. Semi-automatic geometry-driven reassembly of fractured archeological objects[C]. Proceeding of VAST 2010. Eurographics, 2010:33-38.

(編輯李靜，曹大剛)

A computer-assisted system for virtual relic assembling based on adjacency constraint

LI Ji-junnan, GENG Guo-hua, ZHOU Ming-quan, LI Shan-shan

(School of Information Science and Technology, Northwest University, Xi′an 710127， China)

A computer-assisted constraint-based methodology was propose for virtual reassembly of Cultural Heritage (CH) artworks. Instead of focusing on automatic, unassisted reassembly, the study targeted the scenarios where the reconstruction process is not only based on shape properties, but also is built over the experience and intuition of a CH expert. The purpose is therefore to design a flexible interactive system, based on the selection of a set of constraints which relates different fragments, according to the understanding and experience of the CH operator. Once the user has defined those constraints, the system searches for a suitable solution, using a global energy minimization strategy that considers simultaneously all the pieces involved in the reconstruction process. Additionally, the framework provides the possibility to work in a hierarchical way, mimicking the traditional physical procedure that archaeologists use to reassemble tangible fractured objects. The framework is designed to work even with fragments that have been severely damaged or eroded. On those data sets, automatic approaches may often fail, since the fractured regions do not contain enough geometric information to infer the correct matches.

virtual relic assembling; human-computer interaction; adjacency constraint; geometric feature visualization

2015-03-14

國家自然科學基金資助項目(61373117)

李姬俊男，男，陜西西安人，從事計算機圖形學和機器視覺的研究。

TP391

ADOI：10.16152/j.cnki.xdxbzr.2016-01-010