基于多特征信息融合與進(jìn)化計(jì)算的碎片重組

黨悅晨， 李 婉， 周 強(qiáng)*

(1.陜西科技大學(xué) 電氣與控制工程學(xué)院 , 陜西 西安 710021; 2.陜西科技大學(xué) 電子信息與人工智能學(xué)院, 陜西 西安 710021)

0 引言

三維碎片的拼接重構(gòu)對(duì)文物修復(fù)的相關(guān)工作具有重要的指導(dǎo)意義.通常的人工拼接不僅耗時(shí)耗力，且在碎片已經(jīng)破損的基礎(chǔ)上易造成二次破壞.隨著科學(xué)技術(shù)的不斷提高，利用計(jì)算機(jī)輔助進(jìn)行文物碎片拼接的相關(guān)研究也在不斷提升.

針對(duì)旋轉(zhuǎn)體類器型碎片.歐陽(yáng)磊廣[1]與王堅(jiān)[2]依據(jù)法向量擬合出旋轉(zhuǎn)軸，進(jìn)而計(jì)算出母線，基于軸對(duì)齊以及母線配準(zhǔn)來(lái)實(shí)現(xiàn)拼接.但此類方法不適用于不存在旋轉(zhuǎn)軸的非旋轉(zhuǎn)體類器型.

針對(duì)具有參考模板的修復(fù)問(wèn)題.高宏娟等[3]利用形狀簽名算法提取碎片與模板上的關(guān)鍵點(diǎn)，并計(jì)算特征直方圖描述子，根據(jù)相似度構(gòu)建匹配關(guān)系.Zhang K等[4]整合碎片與模板以及碎片與碎片之間的匹配情況，通過(guò)尋找全局一致性高的碎片組合實(shí)現(xiàn)對(duì)頭骨碎片的拼接.但對(duì)于文物碎片，預(yù)先無(wú)法獲取其完整器型，故對(duì)于模板的獲取存在困難.

針對(duì)非薄壁類器型碎片的拼接.Huang等[5]基于體積積分不變量建立多尺度特征描述符并結(jié)合表面粗糙度，從完整碎片中分割出斷裂面，通過(guò)特征區(qū)間聚類以及聚類重疊檢測(cè)實(shí)現(xiàn)特征對(duì)應(yīng)，提高匹配的魯棒性.劉曉寧等[6]建立多尺度SURF特征描述符，通過(guò)計(jì)算Jaccard距離[7]得到最佳匹配.王飄等[8]使用Splatting lines生成碎片紋理特征線，進(jìn)行基于紋理形狀約束的初匹配以及基于斷裂邊緣的校準(zhǔn)匹配.對(duì)于斷裂區(qū)域面積較大的情況，常用點(diǎn)云配準(zhǔn)來(lái)尋找碎片間的幾何變換關(guān)系，例如ICP[9]、FPFH[10]、4PCS[11]、RANSAC[12]以及全局配準(zhǔn)[13]等，但由于薄壁碎片斷裂區(qū)域面積狹窄且相對(duì)平滑的特性，難以基于斷裂面上的凹凸特征進(jìn)行特征匹配，故上述方法均不適用.

針對(duì)表面具有顯著溝壑的碎片，Papaioannou等[14]利用完整區(qū)域上線性結(jié)構(gòu)，通過(guò)跟蹤外推曲線來(lái)實(shí)現(xiàn)拼接.針對(duì)平面碎片，Derech等[15]提出邊沿外推法對(duì)可能存在的磨損區(qū)域進(jìn)行預(yù)測(cè)，通過(guò)計(jì)算相異度和置信度來(lái)確保碎片剛體變換的準(zhǔn)確性.

針對(duì)薄壁文物碎片，王金梅等[16]提出樣條插值曲線擬合的方法提取輪廓曲線，通過(guò)比較曲線的幾何特征實(shí)現(xiàn)匹配.但曲線擬合的時(shí)間復(fù)雜度較高.藺素珍等[17]與譚鑫剛等[18]通過(guò)篩選曲率局部極大值得到角點(diǎn)，計(jì)算角點(diǎn)間弦長(zhǎng)，將碎片匹配轉(zhuǎn)化為弦長(zhǎng)序列匹配.但此類方法嚴(yán)重依賴角點(diǎn)獲取的準(zhǔn)確度，一旦錯(cuò)誤角點(diǎn)被標(biāo)記或真實(shí)角點(diǎn)被漏選，必然導(dǎo)致整體拼接的錯(cuò)誤，故成功率存在一定局限.

現(xiàn)有研究，在針對(duì)陶瓷碎片這類即缺失紋理信息又包含薄壁器型難點(diǎn)的拼接領(lǐng)域略有空缺，難以實(shí)現(xiàn)高成功率以及高準(zhǔn)確度的拼接.故本文提出基于邊緣線的多特征提取與融合，全面且細(xì)致的對(duì)斷裂區(qū)域輪廓進(jìn)行量化，同時(shí)提出球體空間點(diǎn)共存檢測(cè)算法用于評(píng)價(jià)碎片組斷裂區(qū)域之間的拼接情況，設(shè)計(jì)進(jìn)化計(jì)算基于全局迭代出最優(yōu)拼合方案，避免錯(cuò)誤回溯產(chǎn)生的高時(shí)間復(fù)雜度.該方法通用性廣，不局限于器型的對(duì)稱性以及厚度，可在無(wú)模板的情況下成功實(shí)現(xiàn)拼接精準(zhǔn)度高的三維碎片拼接重構(gòu).

1 基于多特征信息融合的曲線表示

本文以三角網(wǎng)格模型為研究對(duì)象，通過(guò)匹配斷裂區(qū)域輪廓線，進(jìn)而實(shí)現(xiàn)碎片間拼合.因此，本節(jié)針對(duì)薄壁器型提出基于多特征提取與融合的斷裂區(qū)域輪廓線量化表示.通過(guò)提取基于曲率半徑向量的初級(jí)特征以及深度特征，結(jié)合撓率特征，將抽象的輪廓線實(shí)現(xiàn)量化，在表征空間幾何結(jié)構(gòu)特征的同時(shí)，對(duì)方向變化趨勢(shì)進(jìn)行預(yù)測(cè).從而克服單一描述量難以具體以及全面的表征曲線獨(dú)有特征，而導(dǎo)致出現(xiàn)大量相似片段，增加后期篩選工作量以及算法時(shí)間復(fù)雜度的問(wèn)題.同時(shí)，本文使用一維特征序列作為最終的表示形式，降低數(shù)據(jù)維度，增加算法效率.

1.1 曲率半徑特征

(1)對(duì)于一組由邊緣輪廓點(diǎn)連接而成的線段L=(P1,P2,…,Pn)，其中輪廓線段頂點(diǎn)Pi=(xi,yi,zi)，i=1,2,…,n，n為所包含斷裂邊緣頂點(diǎn)個(gè)數(shù).對(duì)于待計(jì)算位置頂點(diǎn)Pi，提取其前后相鄰兩個(gè)位置頂點(diǎn)Pi-1與Pi+1.

(2)根據(jù)三個(gè)空間點(diǎn)共面，確定平面約束方程：

根據(jù)三個(gè)空間點(diǎn)到圓心坐標(biāo)距離相等，確定距離約束方程：

將兩個(gè)約束方程聯(lián)立，得到圓心空間坐標(biāo)的線性代數(shù)方程：

圖1 曲率半徑向量

曲率特征描述量一：曲率半徑向量模值.

針對(duì)邊緣曲線上的每一個(gè)頂點(diǎn)計(jì)算出曲率半徑向量，再對(duì)向量進(jìn)行模值計(jì)算,如式(1)所示，從而得到該斷裂邊緣的曲率半徑集合r，即r={r1,r2,…,rj,…,rn}作為初級(jí)特征，該集合反映了曲線的彎曲程度，描述出邊緣輪廓的局部平面幾何結(jié)構(gòu).

(1)

曲率特征描述量二：曲率半徑向量變化.

針對(duì)斷裂邊緣曲線的曲率半徑向量集合，計(jì)算出相鄰向量間的變化向量，再進(jìn)行模值計(jì)算，如式(2)所示，從而得到該斷裂邊緣的曲率變化趨勢(shì)集合rΔ，即rΔ={rΔ1,rΔ2,…,rΔj,…,rΔn}，作為深度特征，通過(guò)深層次分析三維曲線彎曲程度，實(shí)現(xiàn)了對(duì)斷裂邊緣曲線變化趨勢(shì)的預(yù)測(cè).

(2)

1.2 撓率特征

撓率即曲線上鄰近兩點(diǎn)的次法向量之間的夾角對(duì)弧長(zhǎng)的變化率，代表曲率平面的扭曲程度.將撓率作為特征量應(yīng)用于輪廓線的描述，可以更加準(zhǔn)確地反映出曲線的空間結(jié)構(gòu).

針對(duì)三維離散曲線難以擬合參數(shù)方程的問(wèn)題，本文采用微中心差分算法[22]，以離散曲線的目標(biāo)點(diǎn)為中心，進(jìn)行局部范圍內(nèi)的逐階差商計(jì)算，即:

一階差商：

二階差商：

三階差商：

其中k1、k2和k3為鄰域半徑，即每階差商目標(biāo)點(diǎn)單側(cè)需要上一階差商值的個(gè)數(shù).

根據(jù)所得各階差商，帶入到撓率計(jì)算公式(3)中，即得到離散曲線上各點(diǎn)處的撓率τ(t).

(3)

撓率特征描述量：

針對(duì)斷裂邊緣曲線上的每一個(gè)頂點(diǎn)，使用微中心差分算法，得到相應(yīng)的撓率特征集合τ，即τ={τ1,τ2,…,τi,…,τn}，該集合反映曲率平面扭曲程度，描述出三維曲線的空間幾何結(jié)構(gòu).

1.3 邊緣輪廓的多特征融合與量化表示

多組特征描述量之間相互獨(dú)立，分別從不同衡量角度對(duì)三維曲線進(jìn)行表征.為了降低分批次比對(duì)特征帶來(lái)的時(shí)間復(fù)雜度，同時(shí)方便于匹配段的搜索，本文提出多特征融合與量化表示的方法，將多組特征按權(quán)值進(jìn)行融合，從而得到邊緣線的總特征描述集合f，其表示形式即f={f1,f2,…,fi,…,fn}，實(shí)現(xiàn)將多目標(biāo)分次比較問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題.再對(duì)曲線進(jìn)行等間距采樣并賦值，將其轉(zhuǎn)化成一維特征序列的形式，從而同時(shí)反映出某一特征描述所對(duì)應(yīng)的片段長(zhǎng)度，將后期的碎片匹配轉(zhuǎn)化為特征序列的比對(duì)，降低了數(shù)據(jù)維度，提高了算法效率.最終形式即：

Cf={f1,…,f1,f2,…,f2,fi,…,fi,fn,…,fn}

表示過(guò)程如圖2所示，其中特征序列所包含的連續(xù)元素值相同的個(gè)數(shù)即表征為所對(duì)應(yīng)邊緣線段的長(zhǎng)度.截取部分輪廓線的多特征量化結(jié)果如圖3所示.

圖2 一維特征序列表示過(guò)程

圖3 邊緣輪廓的多特征量化

2 碎片組間拼接與度量

對(duì)于相互獨(dú)立的碎片，需要建立出碎片間的相互依賴關(guān)系.本文首先通過(guò)特征比較與匹配尋找出兩個(gè)碎片之間的相似匹配段，并通過(guò)幾何變換實(shí)現(xiàn)兩兩匹配拼接.再次，提出球體空間點(diǎn)共存檢測(cè)算法，設(shè)立評(píng)價(jià)指標(biāo)對(duì)兩兩拼接的結(jié)果進(jìn)行評(píng)分.

2.1 碎片組匹配與拼接

通過(guò)動(dòng)態(tài)比較匹配的方法，以采樣點(diǎn)為單位移動(dòng)特征序列，進(jìn)行特征相減得到特征差值序列.標(biāo)記差值連續(xù)小于閾值的最長(zhǎng)片段為最佳匹配段，并以其特征差值平均值作為匹配段的特征差值函數(shù)F(i,j)，用于度量匹配段間的誤差.對(duì)于碎片組拼接，為避免歐拉變換多次計(jì)算旋轉(zhuǎn)角所帶來(lái)的時(shí)間復(fù)雜度，本文基于羅德里格斯旋轉(zhuǎn)公式，高效以及高精度的實(shí)現(xiàn)碎片組之間的變換.

R=I+sin(θ)K+(1-cos(θ))K2

(4)

2.2 球體空間點(diǎn)共存檢測(cè)算法

完成匹配拼接的碎片組，在實(shí)際情況下不一定為相鄰碎片，因?yàn)榇嬖谶吘壘€相似度十分高，但實(shí)際毫無(wú)關(guān)聯(lián)的碎片.對(duì)于此類情況，拼接后會(huì)呈現(xiàn)錯(cuò)位、空隙以及重疊滲透問(wèn)題.故本文提出球體空間點(diǎn)共存檢測(cè)算法，針對(duì)拼接后的結(jié)果，進(jìn)行局部重疊檢測(cè)，從而度量出拼接貼合程度，并設(shè)置閾值，區(qū)分出真正匹配組與偽匹配組.拼接貼合度對(duì)后期全局拼接也有十分重要的作用.算法步驟如下：

Step1：計(jì)算斷裂邊緣輪廓相鄰頂點(diǎn)間的距離，記錄距離最小值dmin.

Step2：設(shè)定小序號(hào)碎片為A，大序號(hào)碎片為B;提取A碎片上第i個(gè)斷裂邊緣頂點(diǎn)Pi，i=1,2,…,n,n為所包含斷裂邊緣頂點(diǎn)個(gè)數(shù).

Step3：以Pi為球心，以dmin為半徑，建立球體.

Step4：對(duì)B碎片上的斷裂邊緣頂點(diǎn)依次進(jìn)行檢測(cè)，當(dāng)檢測(cè)到其包含在所建立球體區(qū)域內(nèi)，則停止檢測(cè)，標(biāo)記Pi為1；若遍歷B碎片全部頂點(diǎn)，且未發(fā)現(xiàn)滿足條件者，則標(biāo)記Pi為0.

Step5：判斷是否i=n，若是，則轉(zhuǎn)至step 6；若否，則i=i+1且轉(zhuǎn)至step 2.

Step6：統(tǒng)計(jì)A碎片被標(biāo)記的頂點(diǎn)個(gè)數(shù)，即為該碎片組的拼接貼合程度M(i,j).

球體空間點(diǎn)共存檢測(cè)算法原理如圖4所示，正確拼合碎片組以及偽拼合碎片組之間的拼接貼合度差異十分明顯，圖中所示情況包含的點(diǎn)共存?zhèn)€數(shù)分別為36與6.針對(duì)不同形狀的碎片類型，可通過(guò)改變球體半徑dmin的比例系數(shù)來(lái)進(jìn)行相應(yīng)的調(diào)整，得到更加準(zhǔn)確的評(píng)價(jià).

通過(guò)本文所提出算法，可以準(zhǔn)確的實(shí)現(xiàn)對(duì)兩碎片拼合優(yōu)劣的度量，成功地區(qū)分出正確拼合碎片.

(a)正確拼合碎片組 (b)正確拼合局部圖

(c)偽拼合碎片組 (d)偽拼合局部圖圖4 球體空間點(diǎn)共存檢測(cè)算法原理圖

3 基于進(jìn)化計(jì)算的全局拼接

碎片最終拼接，需要基于兩兩匹配結(jié)果選出可以組成完整器型的碎片組.作為非確定性多項(xiàng)式問(wèn)題，窮舉法的時(shí)間復(fù)雜度十分高，且若通過(guò)傳統(tǒng)算法尋找局部最優(yōu)解直接進(jìn)行拼接，則又會(huì)導(dǎo)致較高的回溯率.針對(duì)這一問(wèn)題，本文提出一種基于進(jìn)化計(jì)算的全局拼接，以“優(yōu)勝劣汰”的方式從全局出發(fā)尋找適應(yīng)度最高的匹配方案.算法總流程圖如圖5所示.

圖5 進(jìn)化計(jì)算總體流程

3.1 編碼方式

因碎片形狀的不規(guī)則性以及碎裂位置的隨機(jī)性，無(wú)法使用傳統(tǒng)方法中個(gè)體表示拼接順序的編碼方式.故針對(duì)碎片組拼接結(jié)果，利用二值符號(hào)集合{0,1}表示兩兩拼接組合的選取與否，得到更加靈活的編碼方式.

待拼接碎片總數(shù)目為x，設(shè)置種群大小為m，染色體長(zhǎng)度為n，隨機(jī)生成m×n的矩陣即為種群.種群中第1號(hào)染色體上的基因序列表示為公式(5)：

chr1={g(1,2),g(1,3),…,g(i,j),…,g(x-1,x)}

(5)

其中

截取某個(gè)體部分編碼片段如圖6所示.

圖6 個(gè)體編碼示意圖

3.2 適應(yīng)度函數(shù)確立

進(jìn)化計(jì)算運(yùn)行時(shí)，不需要利用外部信息，通過(guò)判斷種群中個(gè)體的適應(yīng)度值來(lái)實(shí)現(xiàn)搜索.作為個(gè)體性能的評(píng)價(jià)指標(biāo)，適應(yīng)度函數(shù)在“優(yōu)勝劣汰”過(guò)程中發(fā)揮著重要的作用，同時(shí)決定著算法的收斂速度以及能否得到最優(yōu)解.

本文適應(yīng)度函數(shù)的設(shè)計(jì)，由2.1節(jié)所得到的拼接貼合度M(i,j)，結(jié)合特征差值函數(shù)F(i,j)以及豪斯多夫距離H(i,j)構(gòu)成，得到多目標(biāo)優(yōu)化問(wèn)題，再通過(guò)加權(quán)和，轉(zhuǎn)化為單目標(biāo)問(wèn)題，如式所示(6)，其中λ,μ和υ為三個(gè)評(píng)價(jià)參數(shù)相應(yīng)的權(quán)值系數(shù)，用于將其轉(zhuǎn)化為同一數(shù)量級(jí)，本實(shí)驗(yàn)所使用的初始化參數(shù)設(shè)置為[1,10,0.1]，具體可根據(jù)實(shí)際拼接效果適當(dāng)調(diào)整.

υ×M(i,j))

(6)

通過(guò)本文所設(shè)計(jì)的適應(yīng)度函數(shù)，可以全面的對(duì)個(gè)體進(jìn)行評(píng)價(jià)，有效地完成最優(yōu)個(gè)體的搜索，同時(shí)實(shí)現(xiàn)快速收斂.

3.3 全局拼接

在解空間進(jìn)行尋優(yōu)的過(guò)程，要求行為具有隨機(jī)性與趨勢(shì)性，從而在深度搜索與廣度搜索中實(shí)現(xiàn)平衡.選擇算子負(fù)責(zé)深度搜索，進(jìn)行信息積累.交叉算子和變異算子負(fù)責(zé)廣度搜索解空間中新的區(qū)域.

選擇算子作為實(shí)現(xiàn)“優(yōu)勝劣汰”思想的具體實(shí)施步驟，本文采用輪盤賭選擇法.即在每一次的迭代過(guò)程中，結(jié)合個(gè)體的適應(yīng)度函數(shù)，計(jì)算出其累積概率，從而分配被選中概率來(lái)進(jìn)行選擇.該方法在保證種群多樣性的同時(shí)，使算法快速收斂至最優(yōu)結(jié)果.交叉算子采用一點(diǎn)交叉.當(dāng)條件滿足交叉概率時(shí)，將相鄰兩個(gè)染色體從中間位置進(jìn)行一點(diǎn)交叉，從而提高遺傳算法的搜索能力.變異算子采用二進(jìn)制變異.當(dāng)條件滿足變異概率時(shí)，隨機(jī)選取染色體上任一基因位，對(duì)該位置的基因進(jìn)行取反，保證種群的多樣性.

按照所設(shè)置規(guī)則以及參數(shù)進(jìn)行種群初始化，通過(guò)遺傳算子的操作增加種群多樣性，反復(fù)進(jìn)行迭代.當(dāng)?shù)螖?shù)達(dá)到預(yù)設(shè)值或擬合收斂時(shí)，算法終止.

4 實(shí)驗(yàn)結(jié)果與分析

本文使用Matlab 2016b為仿真平臺(tái)，在Intel(R) Core(TM) i9-9900k 3.36GHz內(nèi)存為32GB的PC機(jī)上完成.實(shí)驗(yàn)對(duì)象為一組破裂的蓮花碗器型碎片以及一組仿汝窯青瓷尊碎片.

4.1 碎片重組實(shí)驗(yàn)結(jié)果

針對(duì)實(shí)驗(yàn)碎片，部分碎片組間的匹配拼接與度量結(jié)果如表1所示.對(duì)全部碎片拼接組進(jìn)行排列，按照表2設(shè)置進(jìn)化計(jì)算參數(shù)，迭代過(guò)程如圖7所示，最終拼接重構(gòu)結(jié)果如圖8所示.實(shí)驗(yàn)證明，本文所進(jìn)行的算法研究，可以成功將破碎的三維碎片數(shù)據(jù)實(shí)現(xiàn)拼接重組，還原其完整的原始器型.

表1 部分碎片組匹配拼接

表2 進(jìn)化計(jì)算參數(shù)設(shè)置

(a)Iterations:5 (b)Iterations:20

(c)Iterations:50 (d)Iterations:100圖7 進(jìn)化計(jì)算迭代過(guò)程

(a)蓮花碗俯視圖 (b)蓮花碗側(cè)視圖

(c)青瓷尊俯視圖 (d)青瓷尊側(cè)視圖圖8 碎片重組結(jié)果

4.2 對(duì)比實(shí)驗(yàn)結(jié)果

方法一[24]：基于轉(zhuǎn)向角特征邊緣表示.

方法二[17]：基于曲率特征的邊緣表示.

本文方法：基于曲率半徑多級(jí)特征與撓率特征融合的邊緣表示.

罐子器型碎片組拼接對(duì)比結(jié)果如圖9所示.蓮花碗器型重構(gòu)對(duì)比結(jié)果如圖10所示.

(a)方法一 (b)方法二 (c)本文方法圖9 罐子器型對(duì)比結(jié)果

(a)方法一 (b)方法二 (c)本文方法圖10 蓮花碗器型對(duì)比結(jié)果

所對(duì)比方法的平均拼接準(zhǔn)確率如表3所示，可以看出，本文所用方法在重構(gòu)準(zhǔn)確率上明顯優(yōu)于其它兩種方法，針對(duì)薄壁器型可以更加具體以及全面的描述出邊緣的個(gè)性化特征，區(qū)分出相似匹配段.

表3 不同方法拼接準(zhǔn)確率比較

5 結(jié)論

本文工作的主要貢獻(xiàn)如下：

(1)針對(duì)陶瓷碎片等薄壁類器型提出基于多特征信息融合與進(jìn)化計(jì)算的碎片重組整體流程.克服薄壁碎片斷裂面狹窄、規(guī)則且難以提取特征點(diǎn)的問(wèn)題，實(shí)現(xiàn)由碎片到原始器型的還原；

(2)提出球體空間點(diǎn)共存檢測(cè)算法，通過(guò)局部重疊檢測(cè)對(duì)兩碎片間拼接貼合度進(jìn)行評(píng)價(jià)；

(3)在最終拼接階段，引入進(jìn)化計(jì)算，利用“優(yōu)勝劣汰”的思想迭代得到基于全局的最優(yōu)拼合方案.

實(shí)驗(yàn)結(jié)果表明，本文所提出的特征描述方法具有更高的拼接準(zhǔn)確率，且通過(guò)進(jìn)化計(jì)算避免了局部融合產(chǎn)生的回溯問(wèn)題，提升拼接效率.同時(shí)算法適應(yīng)范圍廣，可應(yīng)用于多種碎片類型，十分有利于破損文物的復(fù)原工作.由于本文算法所采用了球體空間點(diǎn)共存檢測(cè)策略，因此在進(jìn)行拼接貼合度計(jì)算時(shí)較為耗時(shí)，如何進(jìn)一步優(yōu)化算法減少計(jì)算量，將是下一步研究的重點(diǎn).