李姬俊男,耿國華,周明全,李?yuàn)檴?/p>

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

?

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

李姬俊男,耿國華,周明全,李?yuàn)檴?/p>

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

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

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

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

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

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

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

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

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

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

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

鄰接約束被定義為允許用戶交互地選擇相鄰兩個(gè)碎片之間預(yù)期的拼合區(qū)域,以選取對(duì)應(yīng)點(diǎn)為主要手段,由這些對(duì)應(yīng)點(diǎn)確定的潛在對(duì)應(yīng)區(qū)域?qū)?huì)被用于計(jì)算匹配實(shí)體所需的剛體變換,最終輸出一個(gè)滿足給定約束集合中的最優(yōu)映射,圖2為選取鄰接約束的示意圖。針對(duì)鄰接約束,量化的標(biāo)準(zhǔn)為預(yù)期拼合區(qū)域的相似程度,描述該相似程度可類比部分匹配問題中的配準(zhǔn)求解,通過定義碎片間的距離能量函數(shù)予以度量。

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

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

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

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

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

1　約束圖構(gòu)造

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

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

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

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

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

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

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

2　交互式拼合過程

2.1能量最小化

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

2.2剛體變換

剛體變換的過程中通常不考慮碎片或碎片組的縮放或傾斜因素。對(duì)于給定的碎片A或碎片組G,定義剛性變換為一個(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)矩陣之后對(duì)樣本進(jìn)行更新,從而使迭代過程達(dá)到收斂,收斂條件通過檢查優(yōu)化過程中剩余能量是否因?yàn)榧s束而增加予以判斷。此外,可以采用旋轉(zhuǎn)矩陣的斜對(duì)稱矩陣進(jìn)行編碼加以優(yōu)化,這樣可以使每個(gè)旋轉(zhuǎn)矩陣的編碼變量由9減少到3。

2.3交互設(shè)計(jì)

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

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

2)在重組過程中用戶對(duì)碎片進(jìn)行操作的同時(shí)還需要靈活地?cái)U(kuò)展所需約束。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4　總　結(jié)

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

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

[1]茹少峰. 破碎物體復(fù)原技術(shù)與計(jì)算機(jī)輔助文物復(fù)原研究[D].西安：西北大學(xué),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

國家自然科學(xué)基金資助項(xiàng)目(61373117)

李姬俊男，男，陜西西安人，從事計(jì)算機(jī)圖形學(xué)和機(jī)器視覺的研究。

TP391

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