一種基于鄰接約束的交互式文物模型復原系統

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

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

?

一種基于鄰接約束的交互式文物模型復原系統

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

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

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

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

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

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

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

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

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

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

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

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

鄰接約束被定義為允許用戶交互地選擇相鄰兩個碎片之間預期的拼合區域,以選取對應點為主要手段,由這些對應點確定的潛在對應區域將會被用于計算匹配實體所需的剛體變換,最終輸出一個滿足給定約束集合中的最優映射,圖2為選取鄰接約束的示意圖。針對鄰接約束,量化的標準為預期拼合區域的相似程度,描述該相似程度可類比部分匹配問題中的配準求解,通過定義碎片間的距離能量函數予以度量。

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

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

碎片:數字化后的文物碎片模型,可由點云或網格數據類型表示。

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

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

1　約束圖構造

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

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

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

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

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

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

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

2　交互式拼合過程

2.1能量最小化

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

2.2剛體變換

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

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

2.3交互設計

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

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

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

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

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

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

1)圖修改區。這部分是用來定義約束圖。它可以創建一個新的組或將現有的組進行分割,并且能夠添加、刪除和修改現有的約束。

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

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

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

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

2)滲透。不一致的約束會造成碎片斷裂部位間的相互滲透;但與碰撞檢測不同的是,領域專家所關注的不是幾何變換的過程,而是用戶界面上更為直觀的反映。本文采用GPU深度剝離方法[14]來檢測滲透,并在交互界面的約束插入區域和結果可視區域中用紅色來表示滲透現象。圖4顯示了滲透的例子。

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

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

3　實驗結果及分析

本文設計的交互式系統在Meshlab平臺上開發,采用Qt5.2版本,硬件環境為IntelCorei5CPU/4GB內存/NVIDIAGeForceGT420,工作平臺的操作系統是Windows7。可以看出，采用鄰接約束的方法由于引入了領域專家的經驗,使得一些幾何上無法辨別的碎片能夠拼合在一起。

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

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

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

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

4　總　結

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

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

[1]茹少峰. 破碎物體復原技術與計算機輔助文物復原研究[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