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

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

（1.揚州大學(xué)機械工程學(xué)院，江蘇 揚州 225100；2.上海交通大學(xué)機械系統(tǒng)與振動國家重點實驗室，上海 200240）

1 引言

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

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

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

2 方法

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

在一般的碎塊模型中，主要存在兩種類型的曲面：斷裂曲面和非斷裂曲面，通?？梢愿鶕?jù)曲面的粗糙程度[5]來識別斷裂曲面。相比于非斷裂曲面，斷裂曲面上空間點的法向量變化程度更大，表面更凹凸不平。而對于碗狀碎塊的點云數(shù)據(jù)模型，采用區(qū)域生長算法[14]經(jīng)過曲面分割后，如圖1所示?？梢詫⒎菙嗔亚婕毞譃榈酌妗⒃急砻?、外表面和內(nèi)表面四種類型，其中原始表面指的是區(qū)域生長算法在外表面和內(nèi)表面交界處過度分割的曲面，這部分曲面表面積較小，僅存在外表面和內(nèi)表面相鄰的部分碗狀碎塊中。

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

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

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

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

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

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

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

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

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

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

2.2.2 改進后的擴展高斯球

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

首先單位化內(nèi)表面邊緣點的顏色矢量。為了讓內(nèi)表面邊緣點的顏色矢量能均勻分布在各個卦限內(nèi)，將RGB顏色空間模型的重心平移至坐標(biāo)系的原點，如圖3所示。那么單位化后的邊緣點顏色矢量γ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)表面邊緣點的RGB 顏色值；ε，μ和φ—x軸，y軸和z軸上的單位向量。

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

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

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

式中：gM(qx)，gN(qx)—M和N在第x個空間區(qū)域qx內(nèi)的邊緣點個數(shù)；q—沿著球半徑將擴展高斯球分割得到的空間區(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è)置為未訪問，然后提取這些未訪問碎塊的內(nèi)表面及其輪廓曲線，以碎塊blocki(1 ≤i≤n)為基準(zhǔn)模型，計算其他碎塊內(nèi)表面輪廓曲線與碎塊blocki內(nèi)表面輪廓曲線的相似度；

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

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

3 實驗

3.1 實驗結(jié)果

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

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

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

3.2 實驗討論

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

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

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

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

4 結(jié)束語

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

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