基于內(nèi)表面特征的碗狀碎塊匹配方法

孫 進(jìn)，丁 煜，習(xí)俊通，朱興龍

（1.揚(yáng)州大學(xué)機(jī)械工程學(xué)院，江蘇 揚(yáng)州 225100；2.上海交通大學(xué)機(jī)械系統(tǒng)與振動(dòng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，上海 200240）

1 引言

人類燦爛的文明和悠久的歷史使得河流、湖泊、海洋下隱藏著眾多的文化遺跡，其中以碗、瓶、罐、壺、盤(pán)等為器型的瓷器在水下文物研究中占有重要地位。備受矚目的宋代沉船“南海Ⅰ號(hào)”近期結(jié)束清理工作，出水的十八多萬(wàn)件文物中以碗狀器型存在的瓷器為多數(shù)[1]。這些水下文物在水底經(jīng)過(guò)長(zhǎng)時(shí)間的侵蝕和顛簸，大多數(shù)變得破碎殘缺。隨著信息技術(shù)的不斷發(fā)展，利用計(jì)算機(jī)的虛擬復(fù)原技術(shù)來(lái)輔助文物碎塊的實(shí)體拼合逐漸成為可能。為便于文物數(shù)字化表征，基于厚度值大致將破損物體分為兩類：厚度小于1mm的如紙幣、油畫(huà)和地圖等，稱為碎片；厚度大于1mm的如碗、壁畫(huà)和兵馬俑等，稱為碎塊。考慮到水下文物中大部分是以碗狀器型存在的物件，故以碗狀碎塊為研究對(duì)象。

傳統(tǒng)的碎塊匹配方法主要圍繞斷裂曲面展開(kāi)研究。研究方向上大體可分為三類：第一類是基于碎塊斷裂曲面特征的重組匹配。文獻(xiàn)[2]提出利用碎塊表面的積分不變量刻畫(huà)斷裂曲面的彎曲能量，并采用向前搜索算法以及表面一致性約束完成碎塊斷裂曲面的匹配。文獻(xiàn)[3]直接根據(jù)斷裂曲面上所有頂點(diǎn)的三維坐標(biāo)和曲率信息，采用基于隨機(jī)采樣算法和分級(jí)二叉樹(shù)進(jìn)行碎塊的配對(duì)。目前，文獻(xiàn)[4]提出了確定碎塊匹配對(duì)的四個(gè)準(zhǔn)則，即兩個(gè)匹配碎塊的間隙體積、碎塊在匹配位置上的重疊性、兩個(gè)接觸面的平均曲率和接觸弧的長(zhǎng)度，該準(zhǔn)則也得到了廣泛應(yīng)用。在此基礎(chǔ)上，文獻(xiàn)[5]先是根據(jù)斷裂曲面的顯著性區(qū)域?qū)崿F(xiàn)碎塊的粗匹配，然后通過(guò)加入高斯概率模型、角度約束和動(dòng)態(tài)迭代系數(shù)的方式來(lái)改進(jìn)ICP算法完成精匹配，提高了碎塊匹配的正確率和對(duì)齊精度。但是斷裂曲面的面特征信息過(guò)多，直接運(yùn)算會(huì)造成算法的效率低下。一些專家學(xué)者受到碎片拼接方法[6-7]的啟發(fā)，提出基于碎塊輪廓曲線特征的重組匹配。文獻(xiàn)[8]引進(jìn)一種新的描述子表示碎塊輪廓曲線上的特征點(diǎn)和曲線，然后使用快速傅里葉變換完成碎塊的兩兩匹配，其中特征點(diǎn)的描述子是由曲率計(jì)算得到的，曲線的描述子用傅里葉級(jí)數(shù)表示。文獻(xiàn)[9]針對(duì)碎塊表面的特征輪廓線，提出了一種使用曲線矩的不變量和創(chuàng)建在碎塊邊界區(qū)域的錨點(diǎn)來(lái)實(shí)現(xiàn)碎塊匹配和對(duì)齊的方法，并通過(guò)距離誤差度量來(lái)估算特征輪廓線對(duì)齊的準(zhǔn)確性。文獻(xiàn)[10]識(shí)別出砂粒碎塊特征曲線網(wǎng)絡(luò)中所有簡(jiǎn)單的無(wú)弦周期，然后采用Hausdorff距離法和四點(diǎn)同余集算法對(duì)潛在的無(wú)弦周期進(jìn)行匹配，從而完成對(duì)斷裂砂粒碎塊的重組匹配。又由于基于輪廓曲線的拼合方案被限定在碎塊形狀互補(bǔ)的理想條件下，任何幾何外形上微小的缺失都會(huì)對(duì)算法產(chǎn)生很大的影響，基于自適應(yīng)交互式的匹配方法應(yīng)運(yùn)而生。文獻(xiàn)[11]提出一種基于自適應(yīng)鄰域的多特征融合文物碎塊自動(dòng)拼接方法，該方法基于自適應(yīng)鄰域機(jī)制融合碎塊斷裂面及原曲面上的多種特征，將斷裂部位輪廓線的匹配轉(zhuǎn)化為輪廓帶的匹配，通過(guò)自適應(yīng)鄰域的匹配反饋碎塊的匹配關(guān)系。

上述的碎塊匹配算法比較單一，僅圍繞斷裂曲面的幾何特征進(jìn)行。倘若碎塊的斷裂曲面有部分幾何特征遺失，那么容易在重組過(guò)程中產(chǎn)生錯(cuò)誤的匹配；而且在曲面分割過(guò)程中，斷裂曲面的“過(guò)分割”現(xiàn)象嚴(yán)重，需要研究者在提取斷裂曲面特征前進(jìn)行曲面合并，增加了重組算法的運(yùn)行時(shí)間。相較于斷裂曲面可能存在的問(wèn)題，碗狀碎塊的內(nèi)表面不僅具有和斷裂曲面一樣的幾何信息，還擁有比斷裂曲面更豐富的顏色信息和紋理信息，同時(shí)內(nèi)表面的識(shí)別方法不需要對(duì)斷裂曲面分割后產(chǎn)生的眾多曲面進(jìn)行合并，只需要正確區(qū)分出內(nèi)表面即可，可以巧妙地避開(kāi)過(guò)分割帶來(lái)的問(wèn)題。另外，當(dāng)現(xiàn)有文獻(xiàn)在討論碎塊匹配算法時(shí)，往往默認(rèn)待匹配的一對(duì)碎塊是可以拼接的，并沒(méi)有展開(kāi)碎塊篩選方法的研究，而從碎塊集中篩選出最佳匹配的一對(duì)碎塊是計(jì)算機(jī)實(shí)現(xiàn)自動(dòng)重組的必經(jīng)之路。受碎片拼接算法[12]的啟發(fā)，考慮到碎塊的表面都是由復(fù)雜的曲面構(gòu)成的，不同的曲面都具有自身的特殊性，這里將這些曲面的幾何特征和顏色特征通過(guò)高斯映射在擴(kuò)展高斯球[13]中表現(xiàn)出來(lái)。鑒于此，提出一種基于內(nèi)表面特征的碗狀碎塊匹配方法，用于協(xié)助計(jì)算機(jī)自動(dòng)篩選出兩個(gè)最相似的待匹配碎塊。

2 方法

2.1 碗狀碎塊的內(nèi)表面提取

在一般的碎塊模型中，主要存在兩種類型的曲面：斷裂曲面和非斷裂曲面，通常可以根據(jù)曲面的粗糙程度[5]來(lái)識(shí)別斷裂曲面。相比于非斷裂曲面，斷裂曲面上空間點(diǎn)的法向量變化程度更大，表面更凹凸不平。而對(duì)于碗狀碎塊的點(diǎn)云數(shù)據(jù)模型，采用區(qū)域生長(zhǎng)算法[14]經(jīng)過(guò)曲面分割后，如圖1所示。可以將非斷裂曲面細(xì)分為底面、原始表面、外表面和內(nèi)表面四種類型，其中原始表面指的是區(qū)域生長(zhǎng)算法在外表面和內(nèi)表面交界處過(guò)度分割的曲面，這部分曲面表面積較小，僅存在外表面和內(nèi)表面相鄰的部分碗狀碎塊中。

圖1 碗狀碎塊的曲面分類Fig.1 Surface Classification of Bowl-Shaped Broken Pieces

這里采用點(diǎn)云占比定性分析碗狀碎塊各分割曲面的性質(zhì)，這主要是源于工程實(shí)踐中的發(fā)現(xiàn)：相比于其他類型的碎塊，碗狀碎塊的厚度較薄，導(dǎo)致其外表面和內(nèi)表面的表面積要大于其他曲面，也造成外表面和內(nèi)表面的點(diǎn)云占比明顯大于其他曲面。點(diǎn)云占比可以描述碎塊中各分割曲面的大小，一般采用曲面的空間點(diǎn)個(gè)數(shù)在碎塊點(diǎn)云中所占的百分比來(lái)表示某一曲面的點(diǎn)云占比數(shù)值。通常根據(jù)各個(gè)曲面的點(diǎn)云占比，可以從碗狀碎塊的眾多分割曲面中識(shí)別出外表面和內(nèi)表面。

考慮到碗狀物體在平時(shí)生活中的實(shí)際應(yīng)用，外表面常用于抓取接觸，內(nèi)表面要便于清洗使用，而且一般情況下外表面還會(huì)設(shè)計(jì)一些凸出的紋飾特征，因此內(nèi)表面一般比外表面更加光滑平整。數(shù)學(xué)表征為：相比于外表面，內(nèi)表面上某一空間點(diǎn)的法向量與其周圍點(diǎn)的法向量變化程度較小。為了便于定量表征，這里引入平滑度的概念。假設(shè)曲面S由n個(gè)點(diǎn)構(gòu)成，即S={p1,p2,…,pn}，其中第i個(gè)點(diǎn)pi(1 ≤i≤n)的鄰域點(diǎn)為pj(1 ≤j≤k)，那么曲面S的平滑度ε可以表示為：

式中：φi,j—pi的法向量與其鄰域點(diǎn)pj的法向量的夾角。

ε的大小可以定量地反映曲面S的平滑度，曲面中相鄰點(diǎn)之間的法向量變化愈小，則說(shuō)明曲面的平滑度愈大，因此碗狀碎塊內(nèi)表面的平滑度數(shù)值要大于外表面的平滑度數(shù)值，這樣基于點(diǎn)云占比和平滑度能從碗狀碎塊的眾多分割曲面中識(shí)別出內(nèi)表面。接著采用KD樹(shù)[15]建立內(nèi)表面上各空間點(diǎn)的位置關(guān)系，然后進(jìn)行K鄰域搜索并求出各點(diǎn)的法向量和曲率，最后依據(jù)這些信息進(jìn)行內(nèi)表面邊緣點(diǎn)的檢測(cè)和提取。

2.2 碗狀碎塊內(nèi)表面的特征提取

2.2.1 內(nèi)表面邊緣點(diǎn)的特征圓曲率計(jì)算

內(nèi)表面邊緣點(diǎn)所構(gòu)成的輪廓線可以被看成是由一系列凹凸的平滑曲線組成，這些曲線凹凸部分的形狀類似拋物線。對(duì)于一段類拋物線，采用弧長(zhǎng)、短邊與特征圓半徑之比、長(zhǎng)邊與特征圓半徑之比和弦長(zhǎng)與特征圓半徑之比來(lái)進(jìn)行描述。P1、P2和P3均為碎塊內(nèi)表面的邊緣點(diǎn)，P1P3的弧長(zhǎng)用s表示，O是由P1、P2和P3確定的特征圓的圓心，該特征圓的半徑用r表示，如圖2所示。類拋物線的幾何描述符可以表示為(s，a，b，c)，其中a表示長(zhǎng)邊與特征圓半徑之比即a=| |P2P1/r，b表示短邊與特征圓半徑之比即b=|P2P3|/r，c表示弦長(zhǎng)與特征圓半徑之比即c=|P1P3|/r。

圖2 類拋物線模型Fig.2 Likeness Parabolic Model

在類拋物線模型中，根據(jù)圓周角定理、扇形弧長(zhǎng)公式和余弦定理可以計(jì)算出特征圓半徑r，又因?yàn)樘卣鲌A曲率在數(shù)值上等于r的倒數(shù)，則內(nèi)表面上第n個(gè)邊緣點(diǎn)的特征圓曲率gn可以表示為：

2.2.2 改進(jìn)后的擴(kuò)展高斯球

曲線和曲面的幾何特征可通過(guò)高斯映射[16]來(lái)表示。高斯映射是將曲線或曲面上所有點(diǎn)的法矢先進(jìn)行單位化，并將法矢的起點(diǎn)平移至同一個(gè)端點(diǎn)上，則曲線的各法矢端點(diǎn)落在半徑為1 的單位圓上，曲面的各法矢端點(diǎn)落在單位球面上。法矢端點(diǎn)在圓上的投影點(diǎn)所構(gòu)成的圖像即為高斯圖，在球上的投影點(diǎn)所構(gòu)成的圖像即為高斯球。傳統(tǒng)擴(kuò)展高斯球[17]的建立依賴于法向量和曲率，只能表征曲面的幾何特征，這里為同時(shí)表征碗狀碎塊內(nèi)表面的顏色特征和幾何特征，改進(jìn)擴(kuò)展高斯球的建立方法。

首先單位化內(nèi)表面邊緣點(diǎn)的顏色矢量。為了讓內(nèi)表面邊緣點(diǎn)的顏色矢量能均勻分布在各個(gè)卦限內(nèi)，將RGB顏色空間模型的重心平移至坐標(biāo)系的原點(diǎn)，如圖3所示。那么單位化后的邊緣點(diǎn)顏色矢量γn可表示為：

圖3 RGB顏色空間模型Fig.3 RGB Color Space Model

式中：x=r-255/2，y=g-255/2，z=b-255/2，且(r，g，b)—內(nèi)表面邊緣點(diǎn)的RGB 顏色值；ε，μ和φ—x軸，y軸和z軸上的單位向量。

然后附加特征圓曲率信息。將單位化后的顏色矢量起點(diǎn)平移至原點(diǎn)，則其端點(diǎn)落在高斯球的球面上，再將特征圓曲率信息附加至高斯球的端點(diǎn)便形成擴(kuò)展高斯球。改進(jìn)后的擴(kuò)展高斯球，邊緣點(diǎn)顏色矢量的起點(diǎn)落在擴(kuò)展高斯球的球心上，端點(diǎn)落在球面上，每個(gè)顏色矢量都帶有該點(diǎn)的特征圓曲率。

2.3 基于相似度的碗狀碎塊篩選

建立擴(kuò)展高斯球的目的是為了尋找兩塊相似的待匹配碎塊之間的對(duì)應(yīng)點(diǎn)，由于碎塊內(nèi)表面輪廓曲線的擴(kuò)展高斯球都是在球坐標(biāo)系下，所以使尋找對(duì)應(yīng)點(diǎn)成為可能。相似的兩塊待匹配碎塊之間由于RGB顏色特征和特征圓曲率的計(jì)算方法相同，其擴(kuò)展高斯球上必有一部分形狀相似。在球坐標(biāo)系下，計(jì)算碎塊內(nèi)表面邊緣點(diǎn)的顏色矢量與平面XOY的夾角，并按照夾角的大小沿著球半徑將擴(kuò)展高斯球平均分割成q個(gè)空間區(qū)域，令gM()為碎塊內(nèi)表面輪廓曲線M在第x個(gè)空間區(qū)域qx內(nèi)第i個(gè)邊緣點(diǎn)的特征圓曲率，其中i=1，2，…，m，同樣令gN()為碎塊內(nèi)表面輪廓曲線N在第x個(gè)空間區(qū)域qx內(nèi)第j個(gè)邊緣點(diǎn)的特征圓曲率，其中j=1，2，…，n，若將M和N在空間區(qū)域qx內(nèi)具有相同特征圓曲率的邊緣點(diǎn)個(gè)數(shù)記為f(qx)，則f(qx)可用如下公式表示：

式中：gM(qx)，gN(qx)—M和N在第x個(gè)空間區(qū)域qx內(nèi)的邊緣點(diǎn)個(gè)數(shù)；q—沿著球半徑將擴(kuò)展高斯球分割得到的空間區(qū)域數(shù)量。相似度的數(shù)值越大，則代表兩塊待匹配的碗狀碎塊越相似。

2.4 匹配策略

結(jié)合基于內(nèi)表面輪廓特征的粗匹配方法和基于ICP算法的精匹配方法[5]，提出一種基于內(nèi)表面特征的碗狀碎塊重組策略，如圖4所示。

圖4 碗狀碎塊的整體匹配策略Fig.4 Whole Reassembly Strategy of Bowl-Shaped Broken Pieces

具體方法步驟如下：

（1）將待匹配的碎塊分別標(biāo)記為block1,block2,…,blockn，狀態(tài)設(shè)置為未訪問(wèn)，然后提取這些未訪問(wèn)碎塊的內(nèi)表面及其輪廓曲線，以碎塊blocki(1 ≤i≤n)為基準(zhǔn)模型，計(jì)算其他碎塊內(nèi)表面輪廓曲線與碎塊blocki內(nèi)表面輪廓曲線的相似度；

（3）若拼接誤差在允許范圍內(nèi)，則選擇ICP算法完成精匹配，并將碎塊blocki的狀態(tài)設(shè)置為已訪問(wèn)，然后將更新輪廓后的碎塊設(shè)置為基準(zhǔn)，回到（1）繼續(xù)計(jì)算相似度；若拼接誤差不在允許范圍內(nèi)，則回到（2），選擇s值第二大的碎塊與基準(zhǔn)碎塊進(jìn)行拼接，直至拼接誤差在允許范圍內(nèi)；若拼接誤差始終不在允許范圍內(nèi)，則將碎塊blocki剔除出待匹配的碎塊集合，重新選擇基準(zhǔn)碎塊進(jìn)行拼接；

（4）每次精匹配結(jié)束后更新碎塊的輪廓，直至完成碎塊的整體拼合，待所有碎塊均標(biāo)記為已訪問(wèn)狀態(tài)時(shí)，拼接結(jié)束。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)的軟件架構(gòu)為Visual Studio 2010，VTK 5.8.0（Visualization Toolkit，視覺(jué)化工具函式庫(kù)）和PCL1.7.2（Point Cloud Library，點(diǎn)云庫(kù)），實(shí)驗(yàn)在Intel Core i3-4160 CPU@3.60Hz 處理器，4.0GB內(nèi)存的PC上運(yùn)行。碗狀碎塊的三維點(diǎn)云數(shù)據(jù)由Einscan-S三維激光掃描儀采集，首先建立碗狀碎塊的擴(kuò)展高斯球模型，如圖5所示。高斯球上點(diǎn)的矢量方向代表了邊緣點(diǎn)的顏色特征，擴(kuò)展高斯球上點(diǎn)的向量模代表了邊緣點(diǎn)的特征圓曲率，此時(shí)擴(kuò)展高斯球能完整地表征出碗狀碎塊內(nèi)表面的幾何特征和顏色特征。

圖5 擴(kuò)展高斯球的建立過(guò)程Fig.5 Establishment Process of the Extended Gauss Sphere

接著本實(shí)驗(yàn)將碎塊01作為基準(zhǔn)碎塊，剩余的碎塊作為待匹配碎塊，進(jìn)行相似度的交叉計(jì)算，如圖6所示。相似度計(jì)算結(jié)果表明與碎塊01最相似的是碎塊10。根據(jù)2.4節(jié)中所提出的匹配策略，對(duì)篩選出碎塊01和碎塊10進(jìn)行拼接匹配。在一對(duì)碎塊的重組完成后進(jìn)行輪廓更新，篩選出下一個(gè)最佳待匹配碎塊，然后進(jìn)行下一步的拼接匹配，最后直至完成碎塊集中所有碗狀碎塊的整體拼合。

3.2 實(shí)驗(yàn)討論

傳統(tǒng)的擴(kuò)展高斯球模型建立方法依賴于點(diǎn)云的法向量和曲率值[16-18]，對(duì)于幾何特征明顯的碗狀碎塊可以很好地篩選出最佳待匹配碎塊。但是對(duì)于區(qū)域相對(duì)平坦的碗狀碎塊，單純依靠幾何特征的方法容易產(chǎn)生錯(cuò)誤篩選。如圖7所示，傳統(tǒng)的擴(kuò)展高斯球建立方法在最佳待匹配模型的篩選過(guò)程中存在明顯的錯(cuò)誤。碗狀碎塊集B中碎塊01的最佳待匹配碎塊應(yīng)為碎塊02，而相似度計(jì)算結(jié)果卻表明碎塊01的最佳待匹配碎塊是碎塊06。在同樣的情況下，如圖8所示。基于RGB顏色特征和特征圓曲率的擴(kuò)展高斯球模型建立方法，可以正確地完成碎塊01的最佳待匹配碎塊的篩選。

圖8 我們方法在碎塊集B的正確篩選Fig.8 Correct Screening Result in Broken Pieces Set B with Our Method

為了進(jìn)一步驗(yàn)證以RGB顏色特征與特征圓曲率為基礎(chǔ)建立的擴(kuò)展高斯球模型更適合于最佳待匹配碎塊的篩選，分別使用我們方法（即RGB顏色特征與特征圓曲率相結(jié)合的方法），初始方法（即HSV顏色特征與曲率相結(jié)合的方法）和傳統(tǒng)方法（即法向量與曲率相結(jié)合的方法[16-18]）對(duì)碎塊集A（圖6所示的碎塊）和碎塊集B（圖7和圖8所示的碎塊）進(jìn)行重組匹配。如表1所示，相似度計(jì)算結(jié)果包括篩選準(zhǔn)確率和算法運(yùn)行時(shí)間。計(jì)算結(jié)果表明結(jié)合RGB顏色特征與特征圓曲率建立擴(kuò)展高斯球模型來(lái)進(jìn)行最佳待匹配碎塊的篩選，碎塊篩選的平均準(zhǔn)確率可達(dá)到93.87%。與初始方法相比，我們方法的計(jì)算準(zhǔn)確率比其高5.78%，平均運(yùn)算速度提高了20.64%；與傳統(tǒng)方法相比，我們方法的計(jì)算準(zhǔn)確率比其高6.60%，平均運(yùn)算速度提高了16.08%。因此基于RGB 顏色特征與特征圓曲率建立擴(kuò)展高斯球模型的方法更適合于碗狀碎塊最佳待匹配碎塊的篩選，在不同碗狀碎塊數(shù)據(jù)上的實(shí)驗(yàn)表明，該方法相比于其他擴(kuò)展高斯球模型的建立方法更加優(yōu)越。

表1 相似度交叉計(jì)算結(jié)果的比較Tab.1 Comparison of Similarity Calculation Result

4 結(jié)束語(yǔ)

傳統(tǒng)的碎塊匹配方法通過(guò)研究斷裂曲面的幾何性質(zhì)來(lái)達(dá)到目的，容易在曲面分割時(shí)產(chǎn)生過(guò)分割現(xiàn)象，從而增加了拼接過(guò)程的時(shí)間，為了避免這一情況，這里結(jié)合點(diǎn)云占比和平滑度提取碗狀碎塊的內(nèi)表面，并將碗狀碎塊的內(nèi)表面作為研究對(duì)象。此外，為了幫助計(jì)算機(jī)自動(dòng)識(shí)別兩個(gè)最相似的待匹配碎塊，建立擴(kuò)展高斯球模型將碎塊內(nèi)表面邊緣點(diǎn)的幾何特征和顏色特征融合起來(lái)，并通過(guò)構(gòu)造類拋物線模型描述內(nèi)表面邊緣點(diǎn)的幾何特征，然后定義相似度度量函數(shù)來(lái)描述擴(kuò)展高斯球模型的全局特征，最后選擇相似度最大的一對(duì)碎塊進(jìn)行碎塊匹配，從而完成對(duì)碗狀碎塊的整體拼合。

實(shí)驗(yàn)表明結(jié)合RGB顏色特征與特征圓曲率建立擴(kuò)展高斯球模型來(lái)進(jìn)行相似度計(jì)算，相似度的平均計(jì)算準(zhǔn)確率可達(dá)到93.87%，相比于傳統(tǒng)的擴(kuò)展高斯球模型建立方法，結(jié)合RGB顏色特征與特征圓曲率的方法在相似度計(jì)算準(zhǔn)確率和平均運(yùn)算速度上分別提高了6.60%和16.08%。在接下來(lái)的工作中，研究者不會(huì)僅僅局限于提高碗狀碎塊的匹配準(zhǔn)確率和拼接效率，將進(jìn)一步展開(kāi)對(duì)不同形狀碎塊的相似度計(jì)算方法和匹配策略的研究，從而為建立水下文物虛擬拼接復(fù)原的工程化體系框架作鋪墊。