基于Morse-Smale拓?fù)涮卣鞯奈奈锼槠唇铀惴?/h1>
2018-10-18 06:12:06袁潔周明全耿國華張雨禾
自動化學(xué)報 2018年8期
袁潔 周明全 耿國華 張雨禾
三維破碎物體的匹配與拼接是計算機(jī)圖形學(xué)、模式識別、可視化技術(shù)等眾多領(lǐng)域里一個頗具挑戰(zhàn)的問題.20世紀(jì)末,隨著計算機(jī)技術(shù)的快速發(fā)展,將計算機(jī)技術(shù)引入到文物碎片的虛擬拼接過程中,提高了文物復(fù)原的效率,對文物保護(hù)和復(fù)原至今有著重要的意義.
文物數(shù)字化虛擬拼接技術(shù),根據(jù)復(fù)原過程中是否有專家參與可分為自動復(fù)原方法和交互式復(fù)原方法.其中,現(xiàn)有的剛體匹配算法主要結(jié)合破損文物斷裂區(qū)域的幾何特征,作為判斷相鄰碎片之間相似性的主要依據(jù),從而實現(xiàn)破損文物的完整拼合[1].
根據(jù)文物的厚度信息,自動化虛擬復(fù)原技術(shù)可大致分為兩類:薄壁類和非薄壁類文物碎片.早期薄壁類破損文物的虛擬拼接,主要以提取斷裂面輪廓線,并將其映射成為二維平面曲線,實現(xiàn)碎片拼合[1?6].例如Cooper等[1]通過結(jié)合碎片輪廓線及其法向,以最大似然函數(shù)為基礎(chǔ)進(jìn)行自底向上的搜索,完成碎片模型的自動拼合.樊少榮等[2]區(qū)分三角網(wǎng)格曲面模型的外表面與斷裂面從而正確提取出內(nèi)輪廓線和外輪廓線,實現(xiàn)碎片的精確拼合.Oxholm等[3]將斷裂面輪廓線上頂點的曲率、撓率以及顏色信息進(jìn)行結(jié)合,組成特征屬性串,采用最長公共子串的方法實現(xiàn)輪廓線間的匹配.Willi等[4]將貝葉斯分析應(yīng)用在半自動拼合方法中,該算法對斷裂面光滑平整且軸對稱的三維模型有很好的匹配效果,其局限性是只能作用于有限形狀的三維模型.Zhang等[5]基于模板匹配的思想確定顱骨碎片的位置關(guān)系,再結(jié)合相鄰碎片輪廓曲線實現(xiàn)碎片拼接.Huang等[6]通過計算模型表面頂點的積分不變量值提取碎塊表面尖銳的邊緣線,基于向前搜索技術(shù)和表面一致性的約束方法實現(xiàn)碎片的兩兩拼合.空間輪廓曲線匹配方法在幾何特征的數(shù)值化計算時具有簡單高效的特點;但由于其采樣點數(shù)量有限,因此這類方法對噪聲較敏感并且易忽略厚度信息的部分文物碎片模型效果較差.
非薄壁類剛體匹配對文物重建、數(shù)字化遺產(chǎn)保護(hù)有著重要的意義[7].Papaioannou等[8]采用Z緩沖方法,獲取三維模型斷裂面投影,計算當(dāng)前位置斷裂區(qū)域的“位置誤差”,通過最小化誤差獲得最優(yōu)匹配,實現(xiàn)虛擬復(fù)原,該方法適用于雕塑、紀(jì)念碑等大體積破碎模型的修復(fù).李姬俊男等[9]基于相鄰斷裂面間的凹凸互補(bǔ)性,通過提取約束性的特征簇完成碎片間的兩兩拼合.Sahner等[10]通過計算斷裂區(qū)域頂點的坐標(biāo)和法向,采用層次聚類方法進(jìn)行破損文物碎塊之間的拼合.由于斷裂面中包含了較多的特征信息,能夠準(zhǔn)確地反映模型斷裂區(qū)域的鄰接關(guān)系,因此,針對非薄壁類文物碎片,基于空間曲面的碎片拼合,具有一定優(yōu)勢,但針對斷裂面部位受損較嚴(yán)重的碎塊,匹配的正確性無法保證.
因此針對破損文物斷裂部位邊緣受損而引起的輪廓線不能充分表示斷裂面幾何信息的問題,本文基于文獻(xiàn)[11]中的特征線提取方法,提出一種基于Morse-Smale的斷裂面拓?fù)鋷缀翁卣鞯钠扑閯傮w自動拼接方法.本文算法包括斷裂面拓?fù)鋱D的生成、四邊形描述符的定義、匹配集的確定以及碎片拼合4個主要部分,步驟如圖1所示.本文算法的核心思想是采用曲面四邊形描述符表示斷裂面幾何特征信息.在傳統(tǒng)的基于空間曲線的碎片拼合方法中,針對斷裂部位邊緣受損而提取的輪廓線不精確,錯誤的曲線匹配導(dǎo)致斷裂面滲透;傳統(tǒng)的基于空間曲面的碎片拼合方法,并沒有考慮斷裂面特征點之間的拓?fù)潢P(guān)系,可能出現(xiàn)斷裂面的錯誤配準(zhǔn).因此,為了提高碎片拼合的效果,基于Morse-Smale復(fù)形[12]本身的四邊形性質(zhì)及其可控性和魯棒性,本文借助能有效融合斷裂面上凹凸信息的四邊形曲面,更好地反映空間曲面特征,并且可精確地確定鄰接碎片的匹配關(guān)系,同時采用凹凸互補(bǔ)閾值方法篩選出最優(yōu)匹配集,將計算量較大的空間點對應(yīng)關(guān)系轉(zhuǎn)換成少數(shù)的四邊形匹配,有效地提高了剛體轉(zhuǎn)換的效率,最后采用窮舉搜索的方法實現(xiàn)破損碎片精確拼接.
圖1 本文方法步驟Fig.1 Procedures for the method proposed in the paper
1 拓?fù)鋱D提取及相關(guān)術(shù)語
本文通過曲面四邊形表示斷裂面上的幾何特征,從而實現(xiàn)碎片拼合,因此,本節(jié)提取能有效融合斷裂面幾何特征的拓?fù)鋱D.以三角網(wǎng)格模型為研究對象,首先,依據(jù)頂點的顯著度指標(biāo)函數(shù),提取關(guān)鍵點并分類;然后,采用最大角度法構(gòu)建特征線;最后,對提取的斷裂面Morse-Smale復(fù)形進(jìn)行簡化.
1.1 Morse-Smale理論
Morse理論主要用來研究n維空間內(nèi)的d維流行M(M?Rn)的形狀,通過Morse函數(shù),將二維流行表面分割為一系列Morse單元,而Morse-Smale復(fù)形為這些莫斯單元的集合.其主要思想是將形狀的拓?fù)溲芯客成浜瘮?shù)集合特性的定量分析結(jié)合起來,通過定義特征點并判斷其類型,按照一定的尋徑方法利用特征線將其連接起來,形成關(guān)鍵網(wǎng)絡(luò)或轉(zhuǎn)換成其他數(shù)據(jù)模型,從而表達(dá)流形表面的拓?fù)浣Y(jié)構(gòu)與形態(tài)特征,是對特征提取和幾何形狀的分析,保存其拓?fù)湫再|(zhì)及形態(tài)的強(qiáng)大工具.
拓?fù)涮卣魇菍D像中區(qū)域結(jié)構(gòu)形狀的總體描述,其特點是不受旋轉(zhuǎn)與平移等變形影響,描述能力強(qiáng)、計算速度快的優(yōu)點,可有效、準(zhǔn)確地表示物體模型或圖像的局部形狀.常見的圖像拓?fù)涮卣饔谢诠羌芙Y(jié)構(gòu)表示的目標(biāo)檢測算法和基于形態(tài)圖表示的三維識別算法.
基于Morse函數(shù)的特征提取算法在由二維圖像擴(kuò)展到三模型表面時,依據(jù)三角網(wǎng)格頂點的顯著度度量指標(biāo)(曲率值、法向量改變值等頂點屬性)提取的極值點、升降線與Morse-Smale復(fù)形做為模型表面的顯著特征,避免了沒有實際意義的非顯著特征提取,保證了Morse-Smale復(fù)形的拓?fù)渫暾?
1.2 特征點提取
針對三維模型表面的網(wǎng)格數(shù)據(jù),特征提取是指采用指標(biāo)函數(shù)來提取出具有明顯特征的點集合.本文采用曲度函數(shù)f(v)作為三角網(wǎng)格上各頂點的顯著度指標(biāo)函數(shù)[13],定義如下:
其中,v為三角網(wǎng)格上任意一個頂點;k2max(v)和k2min(v)分別為頂點v的最大和最小主曲率.
采用曲度函數(shù)作為指標(biāo)函數(shù)是為了將曲率絕對值最大的特征點提取出來.斷裂面上曲率絕對值最大的點即為凹點、凸點和鞍點,均是能夠表示物體模型表面幾何特征的點.
1.3 特征線構(gòu)建
基于上節(jié)提取的斷裂面特征點,本節(jié)通過最大角度法[14]構(gòu)建特征線,構(gòu)造能完整表示斷裂面幾何關(guān)系的拓?fù)鋱D.
首先,對提取的特征點進(jìn)行判定,并對其進(jìn)行分類.定義vi(i=1,2,···,n)為兵馬俑碎塊斷裂面的三角網(wǎng)格上的任意頂點,其中,n為三角網(wǎng)格數(shù),其所對應(yīng)的顯著度指標(biāo)函數(shù)為f(vi).若其一階鄰域點的顯著度函數(shù)值均小于該頂點的顯著度函數(shù)值,則定義該頂點為極大值點;同理,若其一階鄰域點的顯著度函數(shù)值均大于該頂點的顯著度函數(shù)值,該頂點則被定義為極小值點.若目標(biāo)點的鄰域中有某段連續(xù)區(qū)域內(nèi)的頂點,其指標(biāo)函數(shù)值均大于目標(biāo)點的函數(shù)值,則稱該段連續(xù)區(qū)域能取得的最大范圍為上升區(qū)間;若其指標(biāo)函數(shù)值均小于目標(biāo)點的函數(shù)值,則稱該段連續(xù)區(qū)域能取得的最大范圍為下降區(qū)間.定義鞍點是同時連接兩個上升區(qū)間和兩個下降區(qū)間的特征點.如圖2所示,分別對應(yīng)斷裂面上曲率絕對值最大的頂點,即特征點.
圖2 頂點鄰域關(guān)系圖Fig.2 Diagrams of vertex neighborhoods
基于以上分析,本文采用最大角度法構(gòu)建特征線,構(gòu)建規(guī)則如下:對任意一個鞍點都存在2條沿著指標(biāo)函數(shù)值下降至極小值點和2條沿著指標(biāo)函數(shù)值上升到極大值點的特征線,計算鞍點與其鄰域頂點的邊,選擇上升或下降最快的點作為下一個路徑點位,構(gòu)成特征線.以升弧為例,以鞍點為出發(fā)點,方向為鞍點上升區(qū)間中指標(biāo)函數(shù)值最大的鄰點所指示的方向,直至到達(dá)極大值點.設(shè)vi為三角網(wǎng)格上的任意頂點,其方向為則有:
式中,vj為vi的一階鄰域點.降弧構(gòu)造方式與升弧類似,沿著最大角度反方向搜索.
1.4 拓?fù)浜喕?/h3>
針對所提取的斷裂面拓?fù)鋱D,本節(jié)采用注銷和移動操作[15]進(jìn)行簡化,從而獲取準(zhǔn)確的純四邊形拓?fù)鋱D.
Morse-Smale復(fù)形中的特征點以及升弧、降弧構(gòu)成初始特征集合.一般情況,特征線會將模型表面劃分成若干四邊形區(qū)域,所有四邊形都是由兩個鞍點,一個極大值點和一個極小值點構(gòu)成.在現(xiàn)實情況中,存在一些特殊問題,如圖3(a)深色弧線部分生成的環(huán)狀,對某個鞍點在上升空間中尋找極大值點時,兩條升弧同時連接到一個極大值點,使得拓?fù)鋱D中出現(xiàn)環(huán)狀回路,以及中心區(qū)域可能出現(xiàn)孤立極值點,如圖3(c).
圖3 環(huán)狀和孤立臨界點Fig.3 Diagrams of cyclic and solitary critical points
綜上所述,針對拓?fù)鋱D中環(huán)狀回路的問題,本文采用注銷的方法消除多余或者不規(guī)則的關(guān)鍵點.注銷是一種雙重邊緣收縮的方法,即去除鞍點與極值點之間連成的兩條重復(fù)特征線,其中包含所有的弧線以及這個鞍點和兩個胞腔,結(jié)果如圖3(b).若鞍點v所連接的兩條降弧和鞍點x的極小值點重復(fù),而特征線均為升弧,因此將這些升弧合并為一條升弧,且刪除重復(fù)的兩條降線,簡化結(jié)果如圖3(d).
針對初始特征集合,某些鞍點在特征線構(gòu)建過程中,搜索下一個路徑點位時可能存在微小誤差,線段間誤差積累,導(dǎo)致構(gòu)建的初始莫爾斯復(fù)形中存在一些次要特征線,如圖4所示,鞍點的下一個最優(yōu)路徑點位可能是沿著圖4(c)中虛線所示的方向,而實際在構(gòu)建過程中是沿著圖4(a)或4(b)中三角形邊方向.
圖4 路徑點位選擇Fig.4 Paths selected by points
文獻(xiàn)[15]中將這些次要特征線及其所連接的臨界點一并刪除,但是針對模型表面的幾何特征,刪除誤差積累導(dǎo)致的次要特征線可能會造成模型表面特征的不完整性,因此本文基于此方法進(jìn)行改進(jìn),簡化規(guī)則如下:1)通過定義特征線的顯著度,確定其重要性程度;2)設(shè)定閾值δ0,當(dāng)特征線的顯著度低于該閾值時,定義為次要特征線;3)針對次要特征線進(jìn)行移動操作從而尋找最準(zhǔn)確的特征線.
一般地,升弧上的指標(biāo)函數(shù)值與其所在區(qū)域的指標(biāo)函數(shù)差值越大,則該升弧越重要,顯著度越高;降弧上的函數(shù)值與其所在區(qū)域的函數(shù)值差值越小,則該降弧越重要,顯著度越高[16].因此,本文定義特征線的顯著度為該特征線與其鄰接區(qū)域的平均指標(biāo)函數(shù)值之差.
基于以上分析,每個鞍點連接2條升弧和2條降弧,本文將其合并為一條升弧R和一條降弧r,假設(shè)降弧r,其所對應(yīng)的上升域為D(m1)和D(m2);升弧R,對應(yīng)的下降域為A(m1)和A(m2).則升弧R相對于A(mi)的顯著度為
其中,i=1,2.
最大角度法構(gòu)建特征線過程中,特征線方向沿著三角網(wǎng)格上三角形邊前進(jìn).因此,每條特征線都是由若干個特征點pi(i=1,2,···,n)連接而成的,即升弧R是由若干首尾相連的線段組成,如圖5所示.
圖5 特征線構(gòu)成Fig.5 Feature line composition
因此,R上的積分可近似表示為
式中,pj1,pj2是特征線R上的第j條線段上的2個端點,區(qū)域A(Mi)上的積分則可近似表示為
式中,pk1,pk2以及pk3分別為區(qū)域A(Mi)中第k個三角形的頂點;Ak為該三角形的面積.
通常,對任意的特征線都有兩個鄰接區(qū)域,因此會相應(yīng)的有兩個顯著度.假設(shè)特征線R的2個鄰域分別為A(M1)和A(M2),相對應(yīng)的2個顯著度為δ(R,A(M1))和δ(R,A(M2)),取較小值為該特征線的整體顯著度:
同理,降弧r的兩個鄰接區(qū)域為D(m1)和D(m2),則r的顯著度為
其中,i=1,2.則該條降弧的整體顯著度為
對任意特征線,若其特征線顯著度低于所給定的閾值,則將該特征線進(jìn)行移動操作,即從該特征線的起始鞍點開始,重新搜索下一個最優(yōu)的路徑點位,從而獲取該區(qū)域內(nèi)最準(zhǔn)確并且顯著度最高的特征線,構(gòu)造斷裂面上的純四邊形拓?fù)鋱D.
2 特征描述符定義及搜索
為了將拓?fù)鋱D中曲面四邊形構(gòu)造成能夠有效表示斷裂面幾何信息的四邊形描述符,首先,定義基準(zhǔn)點和0值面,采用頂點高度差的方法對曲面四邊形進(jìn)行編碼,獲得四邊形描述符;然后,通過凹凸互補(bǔ)誤差篩選出最優(yōu)四邊形匹配集.
2.1 四邊形定義
斷裂面上的Morse-Smale復(fù)形,由多個四邊形曲面構(gòu)成,這些曲面四邊形將斷裂面進(jìn)行剖分,四邊形本身具有各向異性的特點,使得四邊形網(wǎng)格更易與模型特征對應(yīng),因此本文將斷裂面上的曲面四邊形作為特征描述符,以相鄰碎片斷裂面間的凹凸特性為基準(zhǔn)進(jìn)行碎塊拼合.設(shè)待匹配的兩個斷裂面分別為?A和?B,定義?A為源面,?B為目標(biāo)面,對于源面?A上的Morse-Smale復(fù)形中的任意曲面四邊形,假設(shè)兩個鞍點分別為s1和s2,極大值為M1,極小值為m1.
如圖6所示,設(shè)以極大值點M1所在的切平面l0為0值面,定義極大值點M1為基準(zhǔn)點,鞍點s1、s2,極小值點m1為目標(biāo)點.用h1表示鞍點s1到該切平面的垂直距離,極小值點m1到該切平面的垂直距離為h2,鞍點s2的對應(yīng)距離為h3,極大值點的對應(yīng)距離為h0,將該高度差值作為每個頂點的屬性值,并按照一定規(guī)則進(jìn)行編碼.
圖6 頂點高度差值Fig.6 Vertex height difference
編碼規(guī)則:本文以源面?A上任意曲面四邊形為例,以四邊形中極大值點開始,順時針編碼,如圖6所示的四邊形中,極大值點M1為基準(zhǔn)點,則定義hA0=0;依次鞍點s1、極小值點m1、鞍點s2所對應(yīng)的屬性值為hA1,hA2,hA3,則該四邊形的一個屬性編碼為.
類似地,目標(biāo)面?B在選取基準(zhǔn)點時,根據(jù)匹配碎塊斷裂面的凹凸互補(bǔ)性,基準(zhǔn)點選擇特征四邊形中的極小值點m1,以其切平面作為0值面,然后求得其余三個目標(biāo)點到0直面的垂直距離,以同一編碼規(guī)則獲得任意特征四邊形的屬性編碼.
2.2 最優(yōu)匹配集搜索
基于本文定義的四邊形屬性,從破損的兵馬俑斷裂面上提取出特征四邊形集,如圖7所示,但由于特征四邊形的數(shù)目較多,斷裂面?A和?B之間的匹配關(guān)系會比較復(fù)雜.因此,本文設(shè)置凹凸互補(bǔ)閾值條件,減少誤匹配四邊形集合個數(shù),求取少量的最優(yōu)匹配集合.
圖7 斷裂面拓?fù)鋱DFig.7 Topological diagram of fracture surface
假設(shè)?A和?B為兩個待匹配的斷裂面,和分別為上的初始特征四邊形集合.設(shè)sAi和sBi是待匹配的兩個斷裂面?A和?B上相對應(yīng)的可匹配特征四邊形,則定義凹凸互補(bǔ)誤差為
假設(shè)四邊形sA1為斷裂面?A上的任意特征曲面四邊形,屬性編碼如下:
相對應(yīng)的,斷裂面?B上對應(yīng)的特征四邊形sB1為
則凹凸互補(bǔ)誤差公式為
其中,x1=hA0?hB0,x2=hA1?hB2,x3=hA3?hB3,x4=hA2?hB1.當(dāng)ε越接近0,表示該對特征四邊形的匹配度越高.因此,設(shè)定凹凸互補(bǔ)閾值ε0＞0,對四邊形sA1,若在斷裂面?B上滿足ε(sA1,sBi)＜ε0的特征四邊形存在m個,則取最優(yōu)匹配對 (sA1,sB1)=, 并將該最優(yōu)匹配對加入到最優(yōu)匹配集s=;否則,刪除該匹配對.本文通過凹凸互補(bǔ)閾值方法約束特征四邊形,篩選出匹配度較高的匹配集,提高斷裂面的匹配精度并且降低剛體轉(zhuǎn)換的復(fù)雜性.圖8是初始特征匹配到最優(yōu)特征集匹配的結(jié)果對比圖.
圖8 匹配集優(yōu)化結(jié)果Fig.8 Optimization results of matching set
3 剛體變換
對特征四邊形進(jìn)行初步篩選后,確定了待匹配斷裂面上的最優(yōu)特征集合S′A和,以及由此構(gòu)成的最優(yōu)匹配集S=, 但由于兩個碎片之間的方向與位置均不同,為了能將碎塊完整的拼合,需根據(jù)兩個四邊形匹配集計算出對齊碎片的旋轉(zhuǎn)矩陣R和平移矩陣T[17].
基于特征四邊形區(qū)域的質(zhì)心坐標(biāo),采用四元組方法[18]求解出最優(yōu)匹配集中的3組質(zhì)心不共線特征四邊形匹配對的旋轉(zhuǎn)矩陣R和平移矩陣T,并采用窮舉搜索法[19]篩選出匹配正確率較高的剛體變換,實現(xiàn)碎片的精確拼合,算法步驟如下:
步驟1.設(shè)任意特征四邊形S的4個頂點為{p1,p2,p3,p4},點pi的三維坐標(biāo)為(xi,yi,zi),定義S的質(zhì)心為.
步驟2.根據(jù)三角形理論,從匹配集中篩選出所有滿足該條件且質(zhì)心不共線的3組特征四邊形對,構(gòu)成集合,其中,,設(shè)M中的元素個數(shù)為e個.
步驟3.從上述集合M中選取任意一組特征四邊形對,采用四元組法計算出斷裂面?A和?B之間的剛體變換矩陣R和T,遍歷集合M中所有的特征對元素,求得剛體變換數(shù)組D.
步驟4.計算D[t],t=1,···,e的匹配正確率;c為正確匹配對個數(shù),初值設(shè)為0;集合S中任意的特征四邊形對經(jīng)過D[t]變換之后,若滿足,則表明該特征四邊形對匹配正確,c=c+1,否則為錯誤匹配;遍歷集合S可求出D[t]的匹配正確率q=c/m;遍歷整個數(shù)組D[e],計算所有特征對剛體變換的正確匹配率.
步驟5.選取匹配正確率最高的剛體變換,完成待拼接碎片的精確對齊.
4 實驗結(jié)果與分析
為檢驗本文算法的有效性,以秦始皇陵1號坑出土的部分兵馬俑碎片網(wǎng)格模型作為實驗數(shù)據(jù).本文實驗采用Visual C++(Visual studio 2010)和 OpenGL編程,在 Intel Core i7-3770 CPU/3.4GHz,4GB內(nèi)存的PC機(jī)上實現(xiàn).實驗閾值均是通過經(jīng)驗值以及數(shù)據(jù)統(tǒng)計獲取的,δ0=0.02,ε0=5.0mm,σ1=2.0mm,碎片在斷裂處均存在邊界受損,幾何特征缺失現(xiàn)象.
4.1 本文算法結(jié)果
圖9～11所示為G10-26號俑、G10-19號俑和G10-23號俑采用本文算法在部分鄰接碎片上的實驗結(jié)果,可以看出,本文算法在邊緣受損的碎片模型上可取得較好的拼合結(jié)果.圖12～14所示為本文算法在一組整俑上的拼接結(jié)果,實驗結(jié)果表明,本文算法在斷裂部位邊緣受損的整俑模型上,如圖12中矩形框標(biāo)注的有小部分缺失的碎片,仍可取得較好的拼合結(jié)果.本文實驗數(shù)據(jù)采用的兵馬俑模型均為陶俑模型,碎片斷裂面具有一定厚度,碎片數(shù)量較多并且網(wǎng)格數(shù)據(jù)總量較大,因此在鄰接碎片的搜索時復(fù)雜度較高.實驗數(shù)據(jù)如表1所示,鄰接碎片在斷裂面提取的特征四邊形隨碎片網(wǎng)格數(shù)增加,碎片的數(shù)量決定了鄰接碎片的斷裂面?zhèn)€數(shù),其對特征四邊形個數(shù)也有直接的影響;由表1中數(shù)據(jù)可得,本文算法可取得較高的匹配精度.
圖9 G10-26號俑部分鄰接碎片拼接結(jié)果Fig.9 Reassembly results of some adjacent fragments of Warriors G10-26
圖10 G10-19號俑部分鄰接碎片拼接結(jié)果Fig.10 Reassembly results of some adjacent fragments of Warriors G10-19
圖11 G10-23號俑部分鄰接碎片拼接結(jié)果Fig.11 Reassembly results of some adjacent fragments of Warriors G10-23
圖12 G10-18號俑部分鄰接碎片拼接結(jié)果Fig.12 Reassembly results of some adjacent fragments of Warriors G10-18
本文將圖7中的碎片裁剪為薄壁模型后,斷裂面上的特征四邊形提取結(jié)果示意圖如圖15,有效特征四邊形定義為四邊均處于碎片模型斷裂面上的四邊形,如圖15中矩形框標(biāo)注所示.由于薄壁模型斷裂面上的特征點數(shù)量較少,提取的有效特征四邊形數(shù)量不足從而無法完整表示斷裂面的幾何結(jié)構(gòu),造成特征匹配不準(zhǔn)確的問題,從而影響后續(xù)鄰接碎片位置的判斷.因此,本文算法針對薄壁類文物碎片模型,拼合效果較差.
表1 兵馬俑碎片實驗數(shù)據(jù)Table 1 Experimental datas of the Terracotta Army fragments
圖13 G10-36號俑部分鄰接碎片拼接結(jié)果Fig.13 Reassembly results of some adjacent fragments of Warriors G10-36
4.2 算法運行時間
本文算法針對成組的兵馬俑碎片拼合時間如表2所示,其中,斷裂面曲面四邊形特征提取為T1,本文每次提取2個碎片的斷裂面四邊形特征;特征匹配集獲取為T2,同理,每次獲取2個碎片的特征匹配集;T3為碎片拼合.實驗數(shù)據(jù)表明,隨著碎片數(shù)據(jù)的增加,運行時間也會隨之增加,這是因為斷裂面上四邊形特征描述符提取為本文算法最耗時的部分,需要遍歷斷裂面網(wǎng)格上的所有頂點.
圖14 G10-22號俑部分鄰接碎片拼接結(jié)果Fig.14 Reassembly results of some adjacent fragments of Warriors G10-22
圖15 薄壁碎片斷裂面特征提取圖Fig.15 Feature extraction in thin fragments
4.3 對比實驗結(jié)果
圖16所示分別為采用基于形態(tài)圖方法[20]及基于斷裂面幾何特征方法[7]的碎片拼合結(jié)果,選取3組碎片模型為實驗數(shù)據(jù),分別為:G10-18號俑,G10-19號俑及G10-36號俑部分鄰接碎片.該3組鄰接碎片具有不同的特點:G10-18號俑碎片模型斷裂部位邊緣受損較少;G10-19號俑碎片模型斷裂部位邊緣受損較嚴(yán)重且斷裂面存在缺損;G10-36號俑鄰接碎片斷裂部位面積較大,碎片存在缺失.
表2 本文算法運行時間Table 2 Execute times of the proposed algorithm
若兩個斷裂面可實現(xiàn)正確匹配,那么當(dāng)兩個碎片完成精確配準(zhǔn)之后,相鄰的兩個斷裂面之間不應(yīng)該發(fā)生明顯的碰撞,存在縫隙過大以及相互重疊交錯[21].圖16(a)所示為G10-18號俑碎片采用文獻(xiàn)[20]中提出的基于形態(tài)圖方法的拼合結(jié)果,將碎片模型轉(zhuǎn)換成點云數(shù)據(jù),可看出,當(dāng)碎片的斷裂處存在缺損時,基于斷裂面出輪廓線的拼合方法會出現(xiàn)相互滲透的現(xiàn)象,如圖16(a)中矩形框中標(biāo)注所示,難以達(dá)到較好的拼合結(jié)果;圖16(b)中所示為采用文獻(xiàn)[7]的基于斷裂面特征簇的拼合方法對G10-19號俑部分碎片的拼合結(jié)果,由于碎片斷裂面存在缺損,則導(dǎo)致幾何信息無法有效表示斷裂面結(jié)構(gòu),造成斷裂面相互滲透現(xiàn)象,如圖16(b)中矩形框標(biāo)注所示;當(dāng)碎片存在小部分的缺損時,則會造成不準(zhǔn)確的位置匹配,出現(xiàn)碎片表面紋飾信息不連續(xù)的現(xiàn)象,如圖16(c)所示.
實驗結(jié)果表明,相較于其他拓?fù)涮卣鞯钠春戏椒ê突跀嗔衙鎺缀翁卣鞯钠春戏椒?本文算法通過融合斷裂面幾何特征的四邊形曲面,增強(qiáng)了特征描述符的約束性,能夠準(zhǔn)確有效地判斷碎片的鄰接位置,針對斷裂面邊緣受損的碎片具有更好的拼合效果.
5 結(jié)語
針對破損文物斷裂部位邊緣受損而引起的輪廓線不能充分表示斷裂面幾何特征的問題,本文提出了一種基于Morse-Smale的斷裂面拓?fù)涮卣鞯钠茡p文物自動拼接算法.該算法將斷裂面上特征點的曲度函數(shù)作為特征檢測算法,根據(jù)斷裂面幾何特征提取特征點;采用最大角度法對特征點進(jìn)行特征線構(gòu)建,并計算特征線重要度簡化拓?fù)鋱D,得到斷裂面的純四邊形拓?fù)鋱D;將拓?fù)鋱D中四邊形曲面構(gòu)造成為能有效表示斷裂面集合特征的描述符,彌補(bǔ)了傳統(tǒng)方法反映局部特征的不足,提高了匹配的精度和效率,同時擴(kuò)展了匹配算法的使用范圍.本文算法需要較為精確地識別出碎片的斷裂面,解決薄壁類破損碎片斷裂面特征平滑,無法取得精確地拼合結(jié)果的難題.
由于本文算法采用了拓?fù)鋱D四邊形為特征描述符,因此在提取特征描述符時較耗時,尋找一種更加魯棒、高效地特征提取算法以減少計算量,將是我們下一步工作的重點.
圖16 傳統(tǒng)算法實驗結(jié)果Fig.16 Experimental results of traditional methods
猜你喜歡
一半模型童話王國·奇妙邏輯推理(2024年5期)2024-06-19 16:03:38 抓住特征巧觀察數(shù)學(xué)小靈通·3-4年級(2024年2期)2024-05-15 02:02:28 重要模型『一線三等角』中學(xué)生數(shù)理化·七年級數(shù)學(xué)人教版(2020年10期)2020-11-26 08:24:50 新型冠狀病毒及其流行病學(xué)特征認(rèn)識世界科學(xué)技術(shù)-中醫(yī)藥現(xiàn)代化(2020年2期)2020-07-25 02:05:36 重尾非線性自回歸模型自加權(quán)M-估計的漸近分布數(shù)學(xué)物理學(xué)報(2020年2期)2020-06-02 11:29:24 如何表達(dá)“特征”瘋狂英語·新策略(2019年10期)2019-12-13 08:43:28 不忠誠的四個特征當(dāng)代陜西(2019年10期)2019-06-03 10:12:04 抓住特征巧觀察數(shù)學(xué)小靈通·3-4年級(2017年9期)2017-10-13 08:10:54 3D打印中的模型分割與打包光學(xué)精密工程(2016年6期)2016-11-07 09:07:19 FLUKA幾何模型到CAD幾何模型轉(zhuǎn)換方法初步研究核科學(xué)與工程(2015年4期)2015-09-26 11:59:03
袁潔 周明全 耿國華 張雨禾
三維破碎物體的匹配與拼接是計算機(jī)圖形學(xué)、模式識別、可視化技術(shù)等眾多領(lǐng)域里一個頗具挑戰(zhàn)的問題.20世紀(jì)末,隨著計算機(jī)技術(shù)的快速發(fā)展,將計算機(jī)技術(shù)引入到文物碎片的虛擬拼接過程中,提高了文物復(fù)原的效率,對文物保護(hù)和復(fù)原至今有著重要的意義.
文物數(shù)字化虛擬拼接技術(shù),根據(jù)復(fù)原過程中是否有專家參與可分為自動復(fù)原方法和交互式復(fù)原方法.其中,現(xiàn)有的剛體匹配算法主要結(jié)合破損文物斷裂區(qū)域的幾何特征,作為判斷相鄰碎片之間相似性的主要依據(jù),從而實現(xiàn)破損文物的完整拼合[1].
根據(jù)文物的厚度信息,自動化虛擬復(fù)原技術(shù)可大致分為兩類:薄壁類和非薄壁類文物碎片.早期薄壁類破損文物的虛擬拼接,主要以提取斷裂面輪廓線,并將其映射成為二維平面曲線,實現(xiàn)碎片拼合[1?6].例如Cooper等[1]通過結(jié)合碎片輪廓線及其法向,以最大似然函數(shù)為基礎(chǔ)進(jìn)行自底向上的搜索,完成碎片模型的自動拼合.樊少榮等[2]區(qū)分三角網(wǎng)格曲面模型的外表面與斷裂面從而正確提取出內(nèi)輪廓線和外輪廓線,實現(xiàn)碎片的精確拼合.Oxholm等[3]將斷裂面輪廓線上頂點的曲率、撓率以及顏色信息進(jìn)行結(jié)合,組成特征屬性串,采用最長公共子串的方法實現(xiàn)輪廓線間的匹配.Willi等[4]將貝葉斯分析應(yīng)用在半自動拼合方法中,該算法對斷裂面光滑平整且軸對稱的三維模型有很好的匹配效果,其局限性是只能作用于有限形狀的三維模型.Zhang等[5]基于模板匹配的思想確定顱骨碎片的位置關(guān)系,再結(jié)合相鄰碎片輪廓曲線實現(xiàn)碎片拼接.Huang等[6]通過計算模型表面頂點的積分不變量值提取碎塊表面尖銳的邊緣線,基于向前搜索技術(shù)和表面一致性的約束方法實現(xiàn)碎片的兩兩拼合.空間輪廓曲線匹配方法在幾何特征的數(shù)值化計算時具有簡單高效的特點;但由于其采樣點數(shù)量有限,因此這類方法對噪聲較敏感并且易忽略厚度信息的部分文物碎片模型效果較差.
非薄壁類剛體匹配對文物重建、數(shù)字化遺產(chǎn)保護(hù)有著重要的意義[7].Papaioannou等[8]采用Z緩沖方法,獲取三維模型斷裂面投影,計算當(dāng)前位置斷裂區(qū)域的“位置誤差”,通過最小化誤差獲得最優(yōu)匹配,實現(xiàn)虛擬復(fù)原,該方法適用于雕塑、紀(jì)念碑等大體積破碎模型的修復(fù).李姬俊男等[9]基于相鄰斷裂面間的凹凸互補(bǔ)性,通過提取約束性的特征簇完成碎片間的兩兩拼合.Sahner等[10]通過計算斷裂區(qū)域頂點的坐標(biāo)和法向,采用層次聚類方法進(jìn)行破損文物碎塊之間的拼合.由于斷裂面中包含了較多的特征信息,能夠準(zhǔn)確地反映模型斷裂區(qū)域的鄰接關(guān)系,因此,針對非薄壁類文物碎片,基于空間曲面的碎片拼合,具有一定優(yōu)勢,但針對斷裂面部位受損較嚴(yán)重的碎塊,匹配的正確性無法保證.
因此針對破損文物斷裂部位邊緣受損而引起的輪廓線不能充分表示斷裂面幾何信息的問題,本文基于文獻(xiàn)[11]中的特征線提取方法,提出一種基于Morse-Smale的斷裂面拓?fù)鋷缀翁卣鞯钠扑閯傮w自動拼接方法.本文算法包括斷裂面拓?fù)鋱D的生成、四邊形描述符的定義、匹配集的確定以及碎片拼合4個主要部分,步驟如圖1所示.本文算法的核心思想是采用曲面四邊形描述符表示斷裂面幾何特征信息.在傳統(tǒng)的基于空間曲線的碎片拼合方法中,針對斷裂部位邊緣受損而提取的輪廓線不精確,錯誤的曲線匹配導(dǎo)致斷裂面滲透;傳統(tǒng)的基于空間曲面的碎片拼合方法,并沒有考慮斷裂面特征點之間的拓?fù)潢P(guān)系,可能出現(xiàn)斷裂面的錯誤配準(zhǔn).因此,為了提高碎片拼合的效果,基于Morse-Smale復(fù)形[12]本身的四邊形性質(zhì)及其可控性和魯棒性,本文借助能有效融合斷裂面上凹凸信息的四邊形曲面,更好地反映空間曲面特征,并且可精確地確定鄰接碎片的匹配關(guān)系,同時采用凹凸互補(bǔ)閾值方法篩選出最優(yōu)匹配集,將計算量較大的空間點對應(yīng)關(guān)系轉(zhuǎn)換成少數(shù)的四邊形匹配,有效地提高了剛體轉(zhuǎn)換的效率,最后采用窮舉搜索的方法實現(xiàn)破損碎片精確拼接.
圖1 本文方法步驟Fig.1 Procedures for the method proposed in the paper
1 拓?fù)鋱D提取及相關(guān)術(shù)語
本文通過曲面四邊形表示斷裂面上的幾何特征,從而實現(xiàn)碎片拼合,因此,本節(jié)提取能有效融合斷裂面幾何特征的拓?fù)鋱D.以三角網(wǎng)格模型為研究對象,首先,依據(jù)頂點的顯著度指標(biāo)函數(shù),提取關(guān)鍵點并分類;然后,采用最大角度法構(gòu)建特征線;最后,對提取的斷裂面Morse-Smale復(fù)形進(jìn)行簡化.
1.1 Morse-Smale理論
Morse理論主要用來研究n維空間內(nèi)的d維流行M(M?Rn)的形狀,通過Morse函數(shù),將二維流行表面分割為一系列Morse單元,而Morse-Smale復(fù)形為這些莫斯單元的集合.其主要思想是將形狀的拓?fù)溲芯客成浜瘮?shù)集合特性的定量分析結(jié)合起來,通過定義特征點并判斷其類型,按照一定的尋徑方法利用特征線將其連接起來,形成關(guān)鍵網(wǎng)絡(luò)或轉(zhuǎn)換成其他數(shù)據(jù)模型,從而表達(dá)流形表面的拓?fù)浣Y(jié)構(gòu)與形態(tài)特征,是對特征提取和幾何形狀的分析,保存其拓?fù)湫再|(zhì)及形態(tài)的強(qiáng)大工具.
拓?fù)涮卣魇菍D像中區(qū)域結(jié)構(gòu)形狀的總體描述,其特點是不受旋轉(zhuǎn)與平移等變形影響,描述能力強(qiáng)、計算速度快的優(yōu)點,可有效、準(zhǔn)確地表示物體模型或圖像的局部形狀.常見的圖像拓?fù)涮卣饔谢诠羌芙Y(jié)構(gòu)表示的目標(biāo)檢測算法和基于形態(tài)圖表示的三維識別算法.
基于Morse函數(shù)的特征提取算法在由二維圖像擴(kuò)展到三模型表面時,依據(jù)三角網(wǎng)格頂點的顯著度度量指標(biāo)(曲率值、法向量改變值等頂點屬性)提取的極值點、升降線與Morse-Smale復(fù)形做為模型表面的顯著特征,避免了沒有實際意義的非顯著特征提取,保證了Morse-Smale復(fù)形的拓?fù)渫暾?
1.2 特征點提取
針對三維模型表面的網(wǎng)格數(shù)據(jù),特征提取是指采用指標(biāo)函數(shù)來提取出具有明顯特征的點集合.本文采用曲度函數(shù)f(v)作為三角網(wǎng)格上各頂點的顯著度指標(biāo)函數(shù)[13],定義如下:
其中,v為三角網(wǎng)格上任意一個頂點;k2max(v)和k2min(v)分別為頂點v的最大和最小主曲率.
采用曲度函數(shù)作為指標(biāo)函數(shù)是為了將曲率絕對值最大的特征點提取出來.斷裂面上曲率絕對值最大的點即為凹點、凸點和鞍點,均是能夠表示物體模型表面幾何特征的點.
1.3 特征線構(gòu)建
基于上節(jié)提取的斷裂面特征點,本節(jié)通過最大角度法[14]構(gòu)建特征線,構(gòu)造能完整表示斷裂面幾何關(guān)系的拓?fù)鋱D.
首先,對提取的特征點進(jìn)行判定,并對其進(jìn)行分類.定義vi(i=1,2,···,n)為兵馬俑碎塊斷裂面的三角網(wǎng)格上的任意頂點,其中,n為三角網(wǎng)格數(shù),其所對應(yīng)的顯著度指標(biāo)函數(shù)為f(vi).若其一階鄰域點的顯著度函數(shù)值均小于該頂點的顯著度函數(shù)值,則定義該頂點為極大值點;同理,若其一階鄰域點的顯著度函數(shù)值均大于該頂點的顯著度函數(shù)值,該頂點則被定義為極小值點.若目標(biāo)點的鄰域中有某段連續(xù)區(qū)域內(nèi)的頂點,其指標(biāo)函數(shù)值均大于目標(biāo)點的函數(shù)值,則稱該段連續(xù)區(qū)域能取得的最大范圍為上升區(qū)間;若其指標(biāo)函數(shù)值均小于目標(biāo)點的函數(shù)值,則稱該段連續(xù)區(qū)域能取得的最大范圍為下降區(qū)間.定義鞍點是同時連接兩個上升區(qū)間和兩個下降區(qū)間的特征點.如圖2所示,分別對應(yīng)斷裂面上曲率絕對值最大的頂點,即特征點.
圖2 頂點鄰域關(guān)系圖Fig.2 Diagrams of vertex neighborhoods
基于以上分析,本文采用最大角度法構(gòu)建特征線,構(gòu)建規(guī)則如下:對任意一個鞍點都存在2條沿著指標(biāo)函數(shù)值下降至極小值點和2條沿著指標(biāo)函數(shù)值上升到極大值點的特征線,計算鞍點與其鄰域頂點的邊,選擇上升或下降最快的點作為下一個路徑點位,構(gòu)成特征線.以升弧為例,以鞍點為出發(fā)點,方向為鞍點上升區(qū)間中指標(biāo)函數(shù)值最大的鄰點所指示的方向,直至到達(dá)極大值點.設(shè)vi為三角網(wǎng)格上的任意頂點,其方向為則有:
式中,vj為vi的一階鄰域點.降弧構(gòu)造方式與升弧類似,沿著最大角度反方向搜索.
1.4 拓?fù)浜喕?/h3>
針對所提取的斷裂面拓?fù)鋱D,本節(jié)采用注銷和移動操作[15]進(jìn)行簡化,從而獲取準(zhǔn)確的純四邊形拓?fù)鋱D.
Morse-Smale復(fù)形中的特征點以及升弧、降弧構(gòu)成初始特征集合.一般情況,特征線會將模型表面劃分成若干四邊形區(qū)域,所有四邊形都是由兩個鞍點,一個極大值點和一個極小值點構(gòu)成.在現(xiàn)實情況中,存在一些特殊問題,如圖3(a)深色弧線部分生成的環(huán)狀,對某個鞍點在上升空間中尋找極大值點時,兩條升弧同時連接到一個極大值點,使得拓?fù)鋱D中出現(xiàn)環(huán)狀回路,以及中心區(qū)域可能出現(xiàn)孤立極值點,如圖3(c).
圖3 環(huán)狀和孤立臨界點Fig.3 Diagrams of cyclic and solitary critical points
綜上所述,針對拓?fù)鋱D中環(huán)狀回路的問題,本文采用注銷的方法消除多余或者不規(guī)則的關(guān)鍵點.注銷是一種雙重邊緣收縮的方法,即去除鞍點與極值點之間連成的兩條重復(fù)特征線,其中包含所有的弧線以及這個鞍點和兩個胞腔,結(jié)果如圖3(b).若鞍點v所連接的兩條降弧和鞍點x的極小值點重復(fù),而特征線均為升弧,因此將這些升弧合并為一條升弧,且刪除重復(fù)的兩條降線,簡化結(jié)果如圖3(d).
針對初始特征集合,某些鞍點在特征線構(gòu)建過程中,搜索下一個路徑點位時可能存在微小誤差,線段間誤差積累,導(dǎo)致構(gòu)建的初始莫爾斯復(fù)形中存在一些次要特征線,如圖4所示,鞍點的下一個最優(yōu)路徑點位可能是沿著圖4(c)中虛線所示的方向,而實際在構(gòu)建過程中是沿著圖4(a)或4(b)中三角形邊方向.
圖4 路徑點位選擇Fig.4 Paths selected by points
文獻(xiàn)[15]中將這些次要特征線及其所連接的臨界點一并刪除,但是針對模型表面的幾何特征,刪除誤差積累導(dǎo)致的次要特征線可能會造成模型表面特征的不完整性,因此本文基于此方法進(jìn)行改進(jìn),簡化規(guī)則如下:1)通過定義特征線的顯著度,確定其重要性程度;2)設(shè)定閾值δ0,當(dāng)特征線的顯著度低于該閾值時,定義為次要特征線;3)針對次要特征線進(jìn)行移動操作從而尋找最準(zhǔn)確的特征線.
一般地,升弧上的指標(biāo)函數(shù)值與其所在區(qū)域的指標(biāo)函數(shù)差值越大,則該升弧越重要,顯著度越高;降弧上的函數(shù)值與其所在區(qū)域的函數(shù)值差值越小,則該降弧越重要,顯著度越高[16].因此,本文定義特征線的顯著度為該特征線與其鄰接區(qū)域的平均指標(biāo)函數(shù)值之差.
基于以上分析,每個鞍點連接2條升弧和2條降弧,本文將其合并為一條升弧R和一條降弧r,假設(shè)降弧r,其所對應(yīng)的上升域為D(m1)和D(m2);升弧R,對應(yīng)的下降域為A(m1)和A(m2).則升弧R相對于A(mi)的顯著度為
其中,i=1,2.
最大角度法構(gòu)建特征線過程中,特征線方向沿著三角網(wǎng)格上三角形邊前進(jìn).因此,每條特征線都是由若干個特征點pi(i=1,2,···,n)連接而成的,即升弧R是由若干首尾相連的線段組成,如圖5所示.
圖5 特征線構(gòu)成Fig.5 Feature line composition
因此,R上的積分可近似表示為
式中,pj1,pj2是特征線R上的第j條線段上的2個端點,區(qū)域A(Mi)上的積分則可近似表示為
式中,pk1,pk2以及pk3分別為區(qū)域A(Mi)中第k個三角形的頂點;Ak為該三角形的面積.
通常,對任意的特征線都有兩個鄰接區(qū)域,因此會相應(yīng)的有兩個顯著度.假設(shè)特征線R的2個鄰域分別為A(M1)和A(M2),相對應(yīng)的2個顯著度為δ(R,A(M1))和δ(R,A(M2)),取較小值為該特征線的整體顯著度:
同理,降弧r的兩個鄰接區(qū)域為D(m1)和D(m2),則r的顯著度為
其中,i=1,2.則該條降弧的整體顯著度為
對任意特征線,若其特征線顯著度低于所給定的閾值,則將該特征線進(jìn)行移動操作,即從該特征線的起始鞍點開始,重新搜索下一個最優(yōu)的路徑點位,從而獲取該區(qū)域內(nèi)最準(zhǔn)確并且顯著度最高的特征線,構(gòu)造斷裂面上的純四邊形拓?fù)鋱D.
2 特征描述符定義及搜索
為了將拓?fù)鋱D中曲面四邊形構(gòu)造成能夠有效表示斷裂面幾何信息的四邊形描述符,首先,定義基準(zhǔn)點和0值面,采用頂點高度差的方法對曲面四邊形進(jìn)行編碼,獲得四邊形描述符;然后,通過凹凸互補(bǔ)誤差篩選出最優(yōu)四邊形匹配集.
2.1 四邊形定義
斷裂面上的Morse-Smale復(fù)形,由多個四邊形曲面構(gòu)成,這些曲面四邊形將斷裂面進(jìn)行剖分,四邊形本身具有各向異性的特點,使得四邊形網(wǎng)格更易與模型特征對應(yīng),因此本文將斷裂面上的曲面四邊形作為特征描述符,以相鄰碎片斷裂面間的凹凸特性為基準(zhǔn)進(jìn)行碎塊拼合.設(shè)待匹配的兩個斷裂面分別為?A和?B,定義?A為源面,?B為目標(biāo)面,對于源面?A上的Morse-Smale復(fù)形中的任意曲面四邊形,假設(shè)兩個鞍點分別為s1和s2,極大值為M1,極小值為m1.
如圖6所示,設(shè)以極大值點M1所在的切平面l0為0值面,定義極大值點M1為基準(zhǔn)點,鞍點s1、s2,極小值點m1為目標(biāo)點.用h1表示鞍點s1到該切平面的垂直距離,極小值點m1到該切平面的垂直距離為h2,鞍點s2的對應(yīng)距離為h3,極大值點的對應(yīng)距離為h0,將該高度差值作為每個頂點的屬性值,并按照一定規(guī)則進(jìn)行編碼.
圖6 頂點高度差值Fig.6 Vertex height difference
編碼規(guī)則:本文以源面?A上任意曲面四邊形為例,以四邊形中極大值點開始,順時針編碼,如圖6所示的四邊形中,極大值點M1為基準(zhǔn)點,則定義hA0=0;依次鞍點s1、極小值點m1、鞍點s2所對應(yīng)的屬性值為hA1,hA2,hA3,則該四邊形的一個屬性編碼為.
類似地,目標(biāo)面?B在選取基準(zhǔn)點時,根據(jù)匹配碎塊斷裂面的凹凸互補(bǔ)性,基準(zhǔn)點選擇特征四邊形中的極小值點m1,以其切平面作為0值面,然后求得其余三個目標(biāo)點到0直面的垂直距離,以同一編碼規(guī)則獲得任意特征四邊形的屬性編碼.
2.2 最優(yōu)匹配集搜索
基于本文定義的四邊形屬性,從破損的兵馬俑斷裂面上提取出特征四邊形集,如圖7所示,但由于特征四邊形的數(shù)目較多,斷裂面?A和?B之間的匹配關(guān)系會比較復(fù)雜.因此,本文設(shè)置凹凸互補(bǔ)閾值條件,減少誤匹配四邊形集合個數(shù),求取少量的最優(yōu)匹配集合.
圖7 斷裂面拓?fù)鋱DFig.7 Topological diagram of fracture surface
假設(shè)?A和?B為兩個待匹配的斷裂面,和分別為上的初始特征四邊形集合.設(shè)sAi和sBi是待匹配的兩個斷裂面?A和?B上相對應(yīng)的可匹配特征四邊形,則定義凹凸互補(bǔ)誤差為
假設(shè)四邊形sA1為斷裂面?A上的任意特征曲面四邊形,屬性編碼如下:
相對應(yīng)的,斷裂面?B上對應(yīng)的特征四邊形sB1為
則凹凸互補(bǔ)誤差公式為
其中,x1=hA0?hB0,x2=hA1?hB2,x3=hA3?hB3,x4=hA2?hB1.當(dāng)ε越接近0,表示該對特征四邊形的匹配度越高.因此,設(shè)定凹凸互補(bǔ)閾值ε0＞0,對四邊形sA1,若在斷裂面?B上滿足ε(sA1,sBi)＜ε0的特征四邊形存在m個,則取最優(yōu)匹配對 (sA1,sB1)=, 并將該最優(yōu)匹配對加入到最優(yōu)匹配集s=;否則,刪除該匹配對.本文通過凹凸互補(bǔ)閾值方法約束特征四邊形,篩選出匹配度較高的匹配集,提高斷裂面的匹配精度并且降低剛體轉(zhuǎn)換的復(fù)雜性.圖8是初始特征匹配到最優(yōu)特征集匹配的結(jié)果對比圖.
圖8 匹配集優(yōu)化結(jié)果Fig.8 Optimization results of matching set
3 剛體變換
對特征四邊形進(jìn)行初步篩選后,確定了待匹配斷裂面上的最優(yōu)特征集合S′A和,以及由此構(gòu)成的最優(yōu)匹配集S=, 但由于兩個碎片之間的方向與位置均不同,為了能將碎塊完整的拼合,需根據(jù)兩個四邊形匹配集計算出對齊碎片的旋轉(zhuǎn)矩陣R和平移矩陣T[17].
基于特征四邊形區(qū)域的質(zhì)心坐標(biāo),采用四元組方法[18]求解出最優(yōu)匹配集中的3組質(zhì)心不共線特征四邊形匹配對的旋轉(zhuǎn)矩陣R和平移矩陣T,并采用窮舉搜索法[19]篩選出匹配正確率較高的剛體變換,實現(xiàn)碎片的精確拼合,算法步驟如下:
步驟1.設(shè)任意特征四邊形S的4個頂點為{p1,p2,p3,p4},點pi的三維坐標(biāo)為(xi,yi,zi),定義S的質(zhì)心為.
步驟2.根據(jù)三角形理論,從匹配集中篩選出所有滿足該條件且質(zhì)心不共線的3組特征四邊形對,構(gòu)成集合,其中,,設(shè)M中的元素個數(shù)為e個.
步驟3.從上述集合M中選取任意一組特征四邊形對,采用四元組法計算出斷裂面?A和?B之間的剛體變換矩陣R和T,遍歷集合M中所有的特征對元素,求得剛體變換數(shù)組D.
步驟4.計算D[t],t=1,···,e的匹配正確率;c為正確匹配對個數(shù),初值設(shè)為0;集合S中任意的特征四邊形對經(jīng)過D[t]變換之后,若滿足,則表明該特征四邊形對匹配正確,c=c+1,否則為錯誤匹配;遍歷集合S可求出D[t]的匹配正確率q=c/m;遍歷整個數(shù)組D[e],計算所有特征對剛體變換的正確匹配率.
步驟5.選取匹配正確率最高的剛體變換,完成待拼接碎片的精確對齊.
4 實驗結(jié)果與分析
為檢驗本文算法的有效性,以秦始皇陵1號坑出土的部分兵馬俑碎片網(wǎng)格模型作為實驗數(shù)據(jù).本文實驗采用Visual C++(Visual studio 2010)和 OpenGL編程,在 Intel Core i7-3770 CPU/3.4GHz,4GB內(nèi)存的PC機(jī)上實現(xiàn).實驗閾值均是通過經(jīng)驗值以及數(shù)據(jù)統(tǒng)計獲取的,δ0=0.02,ε0=5.0mm,σ1=2.0mm,碎片在斷裂處均存在邊界受損,幾何特征缺失現(xiàn)象.
4.1 本文算法結(jié)果
圖9～11所示為G10-26號俑、G10-19號俑和G10-23號俑采用本文算法在部分鄰接碎片上的實驗結(jié)果,可以看出,本文算法在邊緣受損的碎片模型上可取得較好的拼合結(jié)果.圖12～14所示為本文算法在一組整俑上的拼接結(jié)果,實驗結(jié)果表明,本文算法在斷裂部位邊緣受損的整俑模型上,如圖12中矩形框標(biāo)注的有小部分缺失的碎片,仍可取得較好的拼合結(jié)果.本文實驗數(shù)據(jù)采用的兵馬俑模型均為陶俑模型,碎片斷裂面具有一定厚度,碎片數(shù)量較多并且網(wǎng)格數(shù)據(jù)總量較大,因此在鄰接碎片的搜索時復(fù)雜度較高.實驗數(shù)據(jù)如表1所示,鄰接碎片在斷裂面提取的特征四邊形隨碎片網(wǎng)格數(shù)增加,碎片的數(shù)量決定了鄰接碎片的斷裂面?zhèn)€數(shù),其對特征四邊形個數(shù)也有直接的影響;由表1中數(shù)據(jù)可得,本文算法可取得較高的匹配精度.
圖9 G10-26號俑部分鄰接碎片拼接結(jié)果Fig.9 Reassembly results of some adjacent fragments of Warriors G10-26
圖10 G10-19號俑部分鄰接碎片拼接結(jié)果Fig.10 Reassembly results of some adjacent fragments of Warriors G10-19
圖11 G10-23號俑部分鄰接碎片拼接結(jié)果Fig.11 Reassembly results of some adjacent fragments of Warriors G10-23
圖12 G10-18號俑部分鄰接碎片拼接結(jié)果Fig.12 Reassembly results of some adjacent fragments of Warriors G10-18
本文將圖7中的碎片裁剪為薄壁模型后,斷裂面上的特征四邊形提取結(jié)果示意圖如圖15,有效特征四邊形定義為四邊均處于碎片模型斷裂面上的四邊形,如圖15中矩形框標(biāo)注所示.由于薄壁模型斷裂面上的特征點數(shù)量較少,提取的有效特征四邊形數(shù)量不足從而無法完整表示斷裂面的幾何結(jié)構(gòu),造成特征匹配不準(zhǔn)確的問題,從而影響后續(xù)鄰接碎片位置的判斷.因此,本文算法針對薄壁類文物碎片模型,拼合效果較差.
表1 兵馬俑碎片實驗數(shù)據(jù)Table 1 Experimental datas of the Terracotta Army fragments
圖13 G10-36號俑部分鄰接碎片拼接結(jié)果Fig.13 Reassembly results of some adjacent fragments of Warriors G10-36
4.2 算法運行時間
本文算法針對成組的兵馬俑碎片拼合時間如表2所示,其中,斷裂面曲面四邊形特征提取為T1,本文每次提取2個碎片的斷裂面四邊形特征;特征匹配集獲取為T2,同理,每次獲取2個碎片的特征匹配集;T3為碎片拼合.實驗數(shù)據(jù)表明,隨著碎片數(shù)據(jù)的增加,運行時間也會隨之增加,這是因為斷裂面上四邊形特征描述符提取為本文算法最耗時的部分,需要遍歷斷裂面網(wǎng)格上的所有頂點.
圖14 G10-22號俑部分鄰接碎片拼接結(jié)果Fig.14 Reassembly results of some adjacent fragments of Warriors G10-22
圖15 薄壁碎片斷裂面特征提取圖Fig.15 Feature extraction in thin fragments
4.3 對比實驗結(jié)果
圖16所示分別為采用基于形態(tài)圖方法[20]及基于斷裂面幾何特征方法[7]的碎片拼合結(jié)果,選取3組碎片模型為實驗數(shù)據(jù),分別為:G10-18號俑,G10-19號俑及G10-36號俑部分鄰接碎片.該3組鄰接碎片具有不同的特點:G10-18號俑碎片模型斷裂部位邊緣受損較少;G10-19號俑碎片模型斷裂部位邊緣受損較嚴(yán)重且斷裂面存在缺損;G10-36號俑鄰接碎片斷裂部位面積較大,碎片存在缺失.
表2 本文算法運行時間Table 2 Execute times of the proposed algorithm
若兩個斷裂面可實現(xiàn)正確匹配,那么當(dāng)兩個碎片完成精確配準(zhǔn)之后,相鄰的兩個斷裂面之間不應(yīng)該發(fā)生明顯的碰撞,存在縫隙過大以及相互重疊交錯[21].圖16(a)所示為G10-18號俑碎片采用文獻(xiàn)[20]中提出的基于形態(tài)圖方法的拼合結(jié)果,將碎片模型轉(zhuǎn)換成點云數(shù)據(jù),可看出,當(dāng)碎片的斷裂處存在缺損時,基于斷裂面出輪廓線的拼合方法會出現(xiàn)相互滲透的現(xiàn)象,如圖16(a)中矩形框中標(biāo)注所示,難以達(dá)到較好的拼合結(jié)果;圖16(b)中所示為采用文獻(xiàn)[7]的基于斷裂面特征簇的拼合方法對G10-19號俑部分碎片的拼合結(jié)果,由于碎片斷裂面存在缺損,則導(dǎo)致幾何信息無法有效表示斷裂面結(jié)構(gòu),造成斷裂面相互滲透現(xiàn)象,如圖16(b)中矩形框標(biāo)注所示;當(dāng)碎片存在小部分的缺損時,則會造成不準(zhǔn)確的位置匹配,出現(xiàn)碎片表面紋飾信息不連續(xù)的現(xiàn)象,如圖16(c)所示.
實驗結(jié)果表明,相較于其他拓?fù)涮卣鞯钠春戏椒ê突跀嗔衙鎺缀翁卣鞯钠春戏椒?本文算法通過融合斷裂面幾何特征的四邊形曲面,增強(qiáng)了特征描述符的約束性,能夠準(zhǔn)確有效地判斷碎片的鄰接位置,針對斷裂面邊緣受損的碎片具有更好的拼合效果.
5 結(jié)語
針對破損文物斷裂部位邊緣受損而引起的輪廓線不能充分表示斷裂面幾何特征的問題,本文提出了一種基于Morse-Smale的斷裂面拓?fù)涮卣鞯钠茡p文物自動拼接算法.該算法將斷裂面上特征點的曲度函數(shù)作為特征檢測算法,根據(jù)斷裂面幾何特征提取特征點;采用最大角度法對特征點進(jìn)行特征線構(gòu)建,并計算特征線重要度簡化拓?fù)鋱D,得到斷裂面的純四邊形拓?fù)鋱D;將拓?fù)鋱D中四邊形曲面構(gòu)造成為能有效表示斷裂面集合特征的描述符,彌補(bǔ)了傳統(tǒng)方法反映局部特征的不足,提高了匹配的精度和效率,同時擴(kuò)展了匹配算法的使用范圍.本文算法需要較為精確地識別出碎片的斷裂面,解決薄壁類破損碎片斷裂面特征平滑,無法取得精確地拼合結(jié)果的難題.
由于本文算法采用了拓?fù)鋱D四邊形為特征描述符,因此在提取特征描述符時較耗時,尋找一種更加魯棒、高效地特征提取算法以減少計算量,將是我們下一步工作的重點.
圖16 傳統(tǒng)算法實驗結(jié)果Fig.16 Experimental results of traditional methods
猜你喜歡
童話王國·奇妙邏輯推理(2024年5期)2024-06-19 16:03:38
數(shù)學(xué)小靈通·3-4年級(2024年2期)2024-05-15 02:02:28
中學(xué)生數(shù)理化·七年級數(shù)學(xué)人教版(2020年10期)2020-11-26 08:24:50
世界科學(xué)技術(shù)-中醫(yī)藥現(xiàn)代化(2020年2期)2020-07-25 02:05:36
數(shù)學(xué)物理學(xué)報(2020年2期)2020-06-02 11:29:24
瘋狂英語·新策略(2019年10期)2019-12-13 08:43:28
當(dāng)代陜西(2019年10期)2019-06-03 10:12:04
數(shù)學(xué)小靈通·3-4年級(2017年9期)2017-10-13 08:10:54
光學(xué)精密工程(2016年6期)2016-11-07 09:07:19
核科學(xué)與工程(2015年4期)2015-09-26 11:59:03
