基于SURF特征描述符和杰卡德距離的文物碎片拼接

劉曉寧，狄宏璋，楊 穩(wěn)，林芃樾，王世雄

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

1 引 言

破碎文物的拼接在文物虛擬復(fù)原工作中的意義不言而喻,它是虛擬復(fù)原中至為關(guān)鍵的一步。由于信息技術(shù)的不斷更新，文物的數(shù)字化虛擬拼接也不斷有新的突破。目前文物的虛擬拼接技術(shù)大致可以分為斷裂面受損和斷裂面完整兩種。

對(duì)于斷裂面完整類文物，一般是采用基于斷裂面輪廓線以及模型表面幾何紋飾特征來進(jìn)行匹配。比如劉軍等[1]提出一種將斷裂面幾何特征與輪廓線特征相融合的拼接方法。袁潔[2]通過定義表面約束點(diǎn)來提取斷裂面上的特征點(diǎn),實(shí)現(xiàn)交互式文物拼接。趙夫群等[3]通過計(jì)算最長公共子序列實(shí)現(xiàn)斷裂面的細(xì)匹配，從而確定其鄰接關(guān)系。Schmid C等[4]提出一種高效的三維輪廓曲線來實(shí)現(xiàn)文物的拼接。

對(duì)于斷裂面受損類文物，一般是從斷裂面厚度出發(fā)，提取出魯棒性能較好的斷裂面顯著特征來實(shí)現(xiàn)拼接。比如李珊珊[5]提出基于表面鄰接約束并借助于領(lǐng)域?qū)＜蚁闰?yàn)知識(shí)的交互式文物拼接。袁潔等[6]提出基于Morse-smale拓?fù)涮卣鞯奈奈锲唇铀惴?，通過Morse-smale復(fù)形理論來構(gòu)建斷裂面的幾何四邊形拓?fù)鋱D，計(jì)算4個(gè)頂點(diǎn)到基準(zhǔn)面的高度差來構(gòu)建拓?fù)鋱D的特征描述符，來實(shí)現(xiàn)相似性檢索。

目前現(xiàn)有的文物拼接算法，對(duì)于局部碎片缺失、數(shù)據(jù)量大的碎片模型，拼合效果不是特別的準(zhǔn)確。因此，本文基于SURF(Speeded Up Robust Features)特征描述符和Jaccard距離來實(shí)現(xiàn)文物的精準(zhǔn)拼接。首先采用Canny邊緣檢測(cè)算子[7-10]提取出文物模型周圍的邊沿線和表面幾何紋飾線條，作為下一步特征提取的基礎(chǔ)。其次,通過構(gòu)造多尺度空間，在模型邊緣線表面上提取出特征點(diǎn)，對(duì)其構(gòu)造一系列具有強(qiáng)魯棒性更顯著的SURF特征點(diǎn)描述符[11-18]。然后,用Jaccard距離[19-22]計(jì)算特征點(diǎn)集相似度并篩選最優(yōu)匹配點(diǎn)集，確定其鄰接關(guān)系。最后，采用ICP(Iterative Closest Point)算法[23]多次迭代計(jì)算出剛體變化的參數(shù),從而實(shí)現(xiàn)碎片拼接。實(shí)驗(yàn)表明在保證較精確拼接的同時(shí)，本文方法具有高效率、低冗余、強(qiáng)魯棒等特點(diǎn)。

2 Canny邊緣檢測(cè)

2.1 邊緣檢測(cè)

對(duì)于三維模型來說，邊緣是最直觀、最能體現(xiàn)其幾何紋飾信息的一種表示。Canny邊緣檢測(cè)滿足以下要求:(1)檢測(cè)出來的邊緣線是基于人的視覺感受；(2)提取出來的邊緣線不會(huì)影響模型表面的紋飾特征；(3)邊緣線較細(xì)，并且無縫連接，不會(huì)出現(xiàn)局部斷開。所以本文用Canny算子提取碎片模型邊緣線。

2.2 高斯濾波平滑圖像

首先，進(jìn)行模型預(yù)處理操作,消除噪聲等因素對(duì)文物邊緣線檢測(cè)產(chǎn)生的影響。高斯濾波器計(jì)算如公式(1)：

i≤2k+1,j≤2k+1，

(1)

然后要與8鄰域像素矩陣做卷積運(yùn)算，為了計(jì)算的高效性與實(shí)效性，故令k=1,ε=1.2,經(jīng)過數(shù)據(jù)歸一化后的高斯濾波器H如公式(2)所示:

(2)

設(shè)模型中某一點(diǎn)像素值為e，其8鄰域像素值矩陣為B。將其與3×3的高斯濾波器模板的中心位置對(duì)齊從而進(jìn)行卷積操作，即將該像素點(diǎn)8鄰域乘積權(quán)值疊加，作為該點(diǎn)高斯模糊后的亮度值w。則有:

(3)

2.3 邊緣梯度檢測(cè)

由于碎片原始模型大多紋理豐富、特征復(fù)雜，若在其上直接提取特征點(diǎn)會(huì)導(dǎo)致特征點(diǎn)集不夠泛化，無法更進(jìn)一步匹配。因此，用Canny算子檢測(cè)出其水平、垂直以及斜對(duì)角線方向的邊緣線。Canny算子x方向和y方向的3×3模板分別為:

(4)

梯度計(jì)算公式如式(5)所示，H代表計(jì)算得到的梯度值，θ代表其梯度方向。

(5)

2.4 邊緣線生成

生成的邊緣線要最大程度反應(yīng)碎片的邊緣信息和表面紋飾特征，即先進(jìn)一步縮小范圍確定當(dāng)前局部區(qū)域內(nèi)最優(yōu)點(diǎn)，對(duì)任一像素點(diǎn)P,若其梯度值大于我們?cè)O(shè)定的高閾值，則認(rèn)為P為強(qiáng)邊緣像素，將其保留并納入邊緣像素點(diǎn)集合M={mi|i=1,2,3,...,n}。若其梯度值大于低閾值并且小于高閾值，則認(rèn)為其為弱邊緣像素，再去觀察其8鄰接像素點(diǎn)梯度值，若存在梯度值大于高閾值的像素，則將其也納入到邊緣像素點(diǎn)集合M里，否則將其刪除。若任一像素點(diǎn)的梯度值小于低閾值，則直接將其刪除。其偽代碼描述如下:

Algorithm: Progress of picking up four-element pixel1 Input: P: One of a pixel;2Hthreshold: high threshold;3Lthreshold: low threshold;4 Output: P is edge pixel or not;5 if P>hthreshold then6 P must be on edge7 end if8 else if P>Lthreshold and P>Hthreshold then9 for each ∑p' do10 if p' Hthreshold then11 P must be an edge

12 break13 end if14 end for15 end if16 else17 P must be renamed

其中，P代表當(dāng)前像素點(diǎn)，Hthreshold=0.8,Lthreshold=0.4分別為設(shè)定的高低閾值，它是通過多次實(shí)驗(yàn)計(jì)算得出，當(dāng)高閾值與低閾值的比值為2∶1時(shí)，提取出的邊緣線效果更優(yōu)。

該算法提取的模型邊緣線更加符合人類視覺觀感，可以清晰的表示模型表面幾何紋飾特征以及邊緣輪廓信息，為下一步碎片特征點(diǎn)提取打下了良好的基礎(chǔ)，如圖1所示分別C2-4-065，C2-4-064，C2-4-033號(hào)碎片模型及其對(duì)應(yīng)的邊緣線圖。

圖1 模型邊緣線提取Fig.1 Model edge line extraction

3 特征提取

提取碎片顯著特征點(diǎn)大都是通過曲率、極大值及極小值的計(jì)算來確定。本文結(jié)合以往先驗(yàn)知識(shí)，通過構(gòu)造多尺度空間使提取出來的特征點(diǎn)更加泛化，具有一般性。其主要步驟如下:

Step 1.構(gòu)造多尺度空間。為了更進(jìn)一步縮小特征點(diǎn)的范圍，使ε分別取值為1.1、1.3、1.4，得到的高斯濾波器分別為h1,h2和h3，如公式(6)所示。將高斯濾波器與碎片模型卷積操作會(huì)得到不同尺度空間下的模型。

(6)

Step 2.空間特征點(diǎn)檢測(cè)。為了保證關(guān)鍵點(diǎn)的尺度不變性以及高魯棒性,需要對(duì)模型鄰域和尺度空間鄰域點(diǎn)進(jìn)行大小比較。如下圖所示,取中間的檢測(cè)點(diǎn)p和其鄰域8個(gè)點(diǎn)進(jìn)行大小比較。在其尺度空間內(nèi),和其上下鄰域共18個(gè)檢測(cè)點(diǎn)進(jìn)行大小比較。若檢測(cè)點(diǎn)p在其鄰域和空間鄰域內(nèi)是最大值或最小值,就認(rèn)為點(diǎn)p為候選特征點(diǎn)。

圖2 不同尺度空間的圖像Fig.2 Images in different scale spaces

Step 3.特征點(diǎn)精確定位。Step2中得到的特征點(diǎn)其實(shí)是屬于多尺度空間中候選特征點(diǎn)，其具有不穩(wěn)定性與發(fā)散性，并不一定是真實(shí)的特征點(diǎn)。還需要對(duì)其進(jìn)行曲線擬合來使其線性化,精確的確定特征點(diǎn)的位置，剔除掉低分辨率的特征點(diǎn),增強(qiáng)匹配的穩(wěn)定性與完整性。

圖3 特征點(diǎn)定位Fig.3 Feature point positioning

這里曲線擬合函數(shù)的展開式為:

(7)

對(duì)其求導(dǎo)取0，得到:

(8)

將該值代入展開式里得到:

(9)

4 構(gòu)建SURF特征描述符

構(gòu)建特征描述符大都以斷面特征點(diǎn)為基礎(chǔ)，這樣如果提取的特征點(diǎn)存在誤差，也會(huì)導(dǎo)致特征描述符失真。本文基于SURF特征描述符的魯棒性與一般性，構(gòu)建出不僅包括該特征點(diǎn)的相關(guān)信息,還會(huì)包含其鄰域范圍內(nèi)有較強(qiáng)光譜映射的特征點(diǎn)信息的SURF特征描述符。

圖4 構(gòu)建特征描述符Fig.4 Construct feature description factor

如圖4中心紅點(diǎn)Q為所選擇的特征點(diǎn)，以Q為中心點(diǎn)結(jié)合直方圖映射構(gòu)造一個(gè)4×4模板，在這個(gè)模板內(nèi)每一小塊都認(rèn)為是點(diǎn)Q的一個(gè)鄰域生長點(diǎn)(彩圖見期刊電子版)。箭頭方向表示每個(gè)鄰域生長點(diǎn)的8個(gè)梯度方向。再用卷積核與每一塊進(jìn)行卷積加權(quán)運(yùn)算,可得到每個(gè)鄰域生長點(diǎn)的8個(gè)梯度描述符。故對(duì)于任一特征點(diǎn)Q來說,其特征描述符可以用4×4×8維的梯度描述向量W來表示,W=(w1,w2,w3,....,w128)。在對(duì)其進(jìn)行歸一化得到L=(l1,l2,...,l128)。歸一化公式如式(10):

(10)

5 相似性匹配

由于碎片模型拓?fù)涮卣鞯膹?fù)雜性以及特征點(diǎn)的多維度特性,若用歐氏距離計(jì)算特征點(diǎn)集的匹配關(guān)系,其運(yùn)算結(jié)果時(shí)間復(fù)雜度會(huì)特別的高并且會(huì)存在一定的誤差?；诖?為了對(duì)待拼接文物碎片斷裂面及模型表面紋飾特征點(diǎn)的相似型進(jìn)行精確檢測(cè),本文采用Jaccard距離來構(gòu)造最優(yōu)特征點(diǎn)匹配集合,從而確定其鄰接關(guān)系,大大提高了匹配檢測(cè)的效率。其步驟如下:

Step 1.構(gòu)建Jaccard系數(shù)?。設(shè)碎片SA和碎片SB的特征點(diǎn)集合分別為A和B：

A={Ai|i=1,2,...,n}

B={Bj|j=1,2,...,k}

(11)

其中：∩表示特征點(diǎn)集合A與B的交集,∪表示特征點(diǎn)集合A與B的并集。

Step 2.構(gòu)建Jaccard距離d。其公式為:

(12)

對(duì)碎片SA中任一特征點(diǎn)Ai,遍歷碎片SB的特征點(diǎn)集合B,若存在特征點(diǎn)Bj滿足Jaccard距離d(Ai,Bj)(j=1,2,...,n)納入匹配集合Q內(nèi)。此時(shí)還不是最優(yōu),因?yàn)樵贐中會(huì)存在多個(gè)特征點(diǎn)。所以需要遍歷匹配集合Q，找出滿足Jaccard距離最小的特征點(diǎn)Bj,從而構(gòu)成最佳匹配組。

6 剛體拼合

經(jīng)過上述操作,已經(jīng)得到了待拼接碎片間最優(yōu)匹配特征點(diǎn)集合H={〈SAi,SBi〉|i=1,2,...,n}。這一步主要是將位于不同坐標(biāo)系下的特征點(diǎn)集,轉(zhuǎn)化為同一坐標(biāo)系下,來完成文物碎片的準(zhǔn)確拼接。本文采用ICP算法來求解旋轉(zhuǎn)矩陣R和平移矩陣T，從而實(shí)現(xiàn)碎片模型的剛體變化。主要步驟如下:

Step 1:從最優(yōu)匹配特征點(diǎn)集合中任意選取兩組不共線的特征點(diǎn)對(duì)〈SAj,SBj〉〈SAk,SBk〉(j,k∈[1,n],j≠k)。利用ICP算法計(jì)算出旋轉(zhuǎn)矩陣R和平移矩陣T,將其保存在剛體變化數(shù)組V[m]中。

Step 2:經(jīng)過上述操作得到m個(gè)剛體變化參數(shù),則剛體變化數(shù)組記為V[m]={v0,v1,v2，...,vm},其中v[i]={(Ri,Ti)|i∈[0,m]}。

Step 3: 遍歷剛體變化數(shù)組V[m],將其代入目標(biāo)函數(shù)求解。則求解最優(yōu)變化參數(shù)R和T就可以轉(zhuǎn)化為求滿足目標(biāo)函數(shù)W最小值的最優(yōu)解問題。

(13)

Step 4:求解得到最優(yōu)參數(shù)R和T,完成碎片的精確拼接。

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

本實(shí)驗(yàn)采用VicualC++和Open CV編程,在Intel i7-6700k CPU/4.0 GHz,32 G內(nèi)存的PC機(jī)上實(shí)現(xiàn)。以1號(hào)坑的C2-4號(hào)121塊右驂馬碎片模型作為實(shí)驗(yàn)數(shù)據(jù)。

圖5 C2-4號(hào)右驂馬發(fā)掘現(xiàn)場圖Fig.5 Excavation site of No. C2-4

7.1 重組實(shí)驗(yàn)結(jié)果

圖5所示為采用本文算法對(duì)c2-4號(hào)右驂馬碎片重組后的效果圖，分別為右視圖、左視圖、正視圖及其對(duì)應(yīng)的邊緣線圖與提取出的三維特征點(diǎn)云圖。拼合時(shí)間如表1所示,其中n表示碎片塊數(shù),t1表示提取模型邊緣線所需的時(shí)間,t2表示確定碎片及周邊碎片的幾何鄰接關(guān)系所需的時(shí)間,t3表示碎片重組拼接需要的時(shí)間。

圖6 右驂馬三視圖Fig.6 Three views of horse

表1 右驂馬拼接所需時(shí)間

Tab.1 Splicing time required for horse

n t1/s t2/st3/s12170.34657.44223.212

7.2 局部拼接實(shí)驗(yàn)結(jié)果

圖6所示分別為C2-4-064,C2-4-063和C2-4-033號(hào)碎片及其拼接關(guān)系圖，其位置如圖藍(lán)色標(biāo)注處(彩圖見期刊電子版)，直線標(biāo)明的是其周邊鄰接碎片的位置?？梢钥吹郊词勾嬖诓糠?jǐn)嗔衙媸軗p的碎片，采用本文方法也能較準(zhǔn)確地定位出其鄰接位置，取得較好的拼合效果。

圖7 拼接關(guān)系圖Fig.7 Splicing diagram

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

圖7(a)為采用本文方法對(duì)C2-4-18(藍(lán)色標(biāo)注處)號(hào)碎片進(jìn)行拼接的效果。圖7(b)為用文獻(xiàn)[22]方法的拼接效果圖(紅色標(biāo)注處，彩圖見期刊電子版)，可以看到其幾何特征無法正確的反映出其鄰接關(guān)系，呈現(xiàn)出浸透現(xiàn)象，如黑色方框所標(biāo)注。

圖8 C2-4-18號(hào)碎片拼接效果圖Fig.8 No.C2-4-18 effect drawing of fragment splicing

圖9 C2-4-13號(hào)碎片拼接效果圖Fig.9 No.C2-4-18 effect drawing of fragment splicing

圖8(a)為采用本文方法對(duì)C2-4-13號(hào)碎片(藍(lán)色標(biāo)注處)進(jìn)行拼接的效果。圖8(b)為用文獻(xiàn)[18]方法的拼接效果圖(紅色標(biāo)注處，彩圖見期刊電子版)，可以看到存在明顯的縫隙過大現(xiàn)象，如黑色圓圈標(biāo)注處所示。

表2所示為本文算法與文獻(xiàn)[18]、文獻(xiàn)[22]算法的運(yùn)行時(shí)間和拼合誤差對(duì)比，拼合誤差為鄰接碎片斷裂面輪廓線上特征點(diǎn)集間的歐式距離之和的平均值。本文算法的運(yùn)行時(shí)間與文獻(xiàn)[18]相比提高了16%，與文獻(xiàn)[22]相比提高了12%。拼合誤差相對(duì)于文獻(xiàn)[18]和文獻(xiàn)[22]來說更小，不超過0.750 mm，拼合效果更準(zhǔn)確，適用于斷裂面受損的碎片拼接。

表2 運(yùn)行時(shí)間與拼合誤差對(duì)比

8 結(jié) 論

本文主要針對(duì)文物多碎片拼接過程中出現(xiàn)的局部碎片缺失、紋飾幾何特征點(diǎn)受損而不能準(zhǔn)確提取斷裂面紋飾特征等嚴(yán)重問題，提出基于SURF特征描述符和Jaccard距離的碎片拼接方法。先用Canny算子提取出碎片模型中能夠表示其幾何紋飾特征的邊緣線，從而進(jìn)一步簡化其幾何模型。再構(gòu)造多Scale空間來提取碎片模型斷裂面的特征點(diǎn)，構(gòu)建SURF特征描述子。利用特征點(diǎn)集間的鄰接幾何特性，不同于歐式距離計(jì)算的高復(fù)雜度與低時(shí)性，本文用Jaccard距離計(jì)算特征點(diǎn)集相似度。實(shí)驗(yàn)結(jié)果表明，本文方法使得拼合誤差減少到0.750 mm內(nèi)，算法運(yùn)行時(shí)間與文獻(xiàn)[18]和文獻(xiàn)[22]相比分別提高了12%和16%，可以有效地減少因斷裂面破損而造成的拼接縫隙過大、出現(xiàn)滲透等現(xiàn)象。

由于構(gòu)建特征描述符的維數(shù)比較大，因此尋找更加魯棒、高效的特征描述符將是下一步著重的研究方向。