基于特征區(qū)域劃分的文物碎片自動匹配算法

趙夫群，耿國華

（1. 西安財經(jīng)大學信息學院，陜西西安 710100；2. 西北大學信息科學與技術學院，陜西西安 710127）

1 引言

隨著3D 掃描技術的日趨成熟，得到文物的精確的三維模型坐標已經(jīng)非常容易，而如何將破損文物進行修復和展示則逐漸成為3D 建模的關鍵. 傳統(tǒng)的文物修復主要采用手工方式實現(xiàn)，不僅修復速度慢、準確率低、可逆性差，而且容易造成二次破壞、數(shù)字化展示困難等問題［1，2］. 因此，利用計算機技術可以高速、便捷、無破壞地實現(xiàn)文物虛擬復原，提高文物修復的效率和準確率，并以虛擬復原指導文物實體復原，對文物數(shù)字化保護和展示有著至關重要的意義.

碎片匹配是文物虛擬復原的重要研究內容之一，通過碎片匹配可以將文物碎片進行對齊拼接，為后續(xù)的碎片融合和虛擬展示提供技術支持. 碎片匹配算法主要分為兩大類：一類是無特征的碎片匹配，另一類是基于特征的碎片匹配. 其中，基于特征的碎片匹配算法的應用更為廣泛，如點特征、線特征、法線和曲率特征等. Ouyang 等［3］利用特征點實現(xiàn)碎片匹配，但效率較低、穩(wěn)定性較差；Patel［4］提出基于改進SURF 的匹配算法，可以提高匹配速度，但對低重疊點云的匹配誤差較大；周光兵等［5］提利用圖像灰度值實現(xiàn)3D 剛性匹配，可以獲得較高的匹配精度；廖夢怡等［6］利用投影角點檢測算法實現(xiàn)點云匹配，可以有效提高匹配精度；陳寶華等［7］提出一種稠密三維點云與圖像的匹配算法，實現(xiàn)了不同視場圖形的匹配問題；任明榮等［8］提出一種三維模型匹配的條件隨機場算法，有效提高了匹配精度；Xu 等［9］提出基于幾何特征向量的點云匹配算法，可以降低耗時，提高魯棒性和可靠性；Shi 等［10］提出一種基于輪廓特征的點云匹配算法，但是該算法對輪廓特征破損嚴重碎片模型的匹配效果不佳；Wu等［11］提出一種基于距離誤差評價高密度點云匹配算法，但是對低重疊率點云的匹配精度不高；Yan等［12］提出一種基于遺傳算法（Genetic Algorithm，GA）的點云匹配算法，可以避免陷入局部最優(yōu)解，但同樣不適用于低重疊點云匹配.

以上基于特征的匹配算法均存在一定的問題，如：匹配精度低，收斂速度慢；約束條件過于嚴格，容易造成局部最佳匹配；花費大量時間在無用的匹配上；重疊比例較低點云的匹配效果不佳. 鑒于此，針對文物的點云模型，本文提出一種基于特征區(qū)域劃分的匹配算法，通過獲取點云特征點并對特征點集進行區(qū)域劃分以降低匹配規(guī)模，同時提高點云區(qū)域的重疊率，從而達到點云快速精確匹配的目的，提高低重疊斷裂面文物的匹配精度.

2 特征點提取

對于待匹配的文物碎片，首先采用基于法矢的斷裂面分割算法［13］提取其斷裂面，然后提取斷裂面上的特征點并對其進行區(qū)域劃分，由此提高低重疊斷裂面的匹配精度和速度.

假設某一斷裂面φ1對應的點云模型為P，對于其上任意一點p，以圓心為p、半徑為r的球型區(qū)域內的點來構建協(xié)方差矩陣C，并求解該協(xié)方差矩陣C的特征向量和特征值，其中最小特征值對應的特征向量就是點p的法向量.

構建點p及其鄰域內點的協(xié)方差矩陣C為

式（1）、式（2）中，m表示以p為圓心、r為半徑的鄰域內點的數(shù)量；pˉ表示該鄰域的質心；pi是p鄰域內的點；λj表示協(xié)方差矩陣C的特征值；vj表示特征值λj對應的特征向量. 當特征值最小時，將其所對應的特征向量作為點p在該鄰域下的法向量n.

假設點p在半徑r1和r2(r1≠r2)鄰域下的法向量分別為n1和n2. 由于在不同的半徑下鄰域曲面的變化程度不同，因此兩個方向量n1和n2之間必然存在角度偏差，且角度偏差越大，表示曲面變化越劇烈. 通過計算兩個法向量n1和n2間夾角余弦來設定閾值ε1，以提取特征點，即

式（3）中，閾值ε1的值要根據(jù)具體實驗情況來確定.對于點云P如果其外表面法向量變化較大，則需要提取的特征點較多，那么ε1的值要設置得大一些，否則設置得小一些，但ε1的值不能大于符合式（3）的最大值.

對于兩個待匹配的斷裂面φ1和φ2，假設其對應的點云模型分別為P和Q，利用上述特征點提取方法對其進行特征點提取，得到的特征點集分別為P'和Q'. 接下來對特征點集P'和Q'進行區(qū)域劃分，為后續(xù)區(qū)域匹配提供數(shù)據(jù)基礎.

3 基于區(qū)域劃分的初始匹配

3.1 特征點區(qū)域劃分

3.2 區(qū)域匹配

式（4）中，L=MN；ωi表示線性組合系數(shù)，i=1,2,…,L.

在理想情況下，ωi的非零元素集合所對應的區(qū)域匹配程度會比較高，所對應的剛體變換與真實剛體變換是最接近的. 線性組合系數(shù)ωi通過最大化能量函數(shù)E(ω)來計算，計算式為

式（6）中，參數(shù)σ是一個大于0 的實數(shù)，用來控制可信性和一致性信息的相對重要程度.

參數(shù)σ的值越大，一致性信息所起的作用就越大.當兩個待匹配斷裂面的重疊區(qū)域較小并且重疊區(qū)域內的特征比較明顯時，需要依靠該特征區(qū)域來恢復全局變換，σ的取值應該較??；反之，σ的取值應該較大. 在實際實驗中，配準結果對σ的取值默認設置為1.0 即可.d(Ti,Tj)表示剛體變換Ti和Tj的距離，采用標準化的歐氏距離計算，即

由于矩陣A是對稱的，因此它的最大特征值所對應的特征向量是ω，最大化能量函數(shù)為E(ω). 根據(jù)Perron-Frobenius 定理［16］，ω的所有分量具有相同的符號，因此可以選擇合適的ω使得它的各個分量都是正數(shù)，那么該ω就是需要求解的最優(yōu)組合系數(shù).

剛體變換T可分解為一個3×3 旋轉矩陣R和一個3×1 平移向量t. 對于平移向量t，直接平移計算即可.而對于旋轉矩陣R，采用四元數(shù)法［17］來計算，即

通過計算旋轉矩陣R和平移向量t即可求得剛體變換T，實現(xiàn)特征點集P'和Q'的初始配準. 最后，采用一種基于閾值約束的改進ICP算法實現(xiàn)點云精確配準.

4 基于閾值約束ICP的精確匹配

ICP 算法通過不斷迭代來求解兩組點云之間的剛體變換，每次迭代都會求解點云變換矩陣，使得通過該矩陣變換得到的點云與目標點云對之間空間距離最?。?8］. 該算法具有較高的匹配精度，但耗時較長，且要求待匹配點云存在包含關系. 鑒于此，在碎片斷裂面精匹配階段，本文采用一種基于閾值約束的ICP算法［19］將特征點集P'和Q'進行進一步匹配.

采用該基于閾值約束的ICP 算法對P'和Q'精確匹配的具體步驟如下.

（1）設置初值：旋轉矩陣R'0，平移矢量t'0，迭代次數(shù)k=1.

（2）計算目標函數(shù)Fk，計算式為

通過以上對特征點集P'和Q'的精確匹配，即可達到文物碎片斷裂面最終精確匹配拼接的目的.

5 匹配算法步驟描述

基于以上斷裂面初始匹配和精確匹配方法，該基于特征區(qū)域劃分的文物碎片匹配算法的具體步驟描述如下.

（1）假設兩個待匹配的文物碎片為B1和B2，提取的其斷裂面集合分別為F1={S11,S12,…,S1n}和F2={S21,S22,…,S2m}，n和m分別表示碎片B1和B2所含斷裂面的數(shù)目.

（2）在斷裂面集合F1和F2中，任取兩個未匹配過的斷裂面S1i和S2j，i=1,2,…,n，j=1,2,…,m，提取斷裂面S1i和S2j上的特征點，得到特征點集特征點集P'和Q'.

（3）對特征點集P'和Q'進行區(qū)域劃分和區(qū)域匹配，從而將斷裂面S1i和S2j初步對齊.

（4）采用該基于閾值約束的ICP 算法對特征點集P'和Q'進行進一步精確匹配，從而實現(xiàn)斷裂面S1i和S2j的進一步對齊.

（5）判斷斷裂面S1i和S2j的匹配誤差，若小于給定閾值，S1i和S2j匹配成功，否則從斷裂面集合F1和F2中取下一對未匹配過的斷裂面S1i和S2j，重復步驟（2）到步驟（5），直到找到可以成功匹配的兩個斷裂面或所有斷裂面匹配完為止.

6 實驗結果與分析

算法在Visual studio 2010 環(huán)境下，Intel Core i7 3.33GHz 的CPU、16GB 內存的Windows 7 64 位PC 機上進行實現(xiàn). 實驗數(shù)據(jù)是采用加拿大手持式Handyscan3 D激光掃描儀獲取的兵馬俑碎片的obj格式的點云數(shù)據(jù)模型.

6.1 兩個碎片的匹配

四組待匹配的兵馬俑碎片如圖1 所示. 首先，提取碎片斷裂面上的特征點，并對其進行區(qū)域劃分；然后采用4PCS 算法進行區(qū)域匹配，從而實現(xiàn)兩個碎片斷裂面的初始匹配；最后采用基于閾值約束的ICP算法將特征點集進行精確匹配，從而將斷裂面進行最終匹配. 碎片初始匹配和精確匹配結果分別如圖2和圖3所示.

圖1 待匹配的兵馬俑碎片

從圖2 和圖3 匹配結果可見，該基于特征區(qū)域劃分的碎片匹配算法通過提取特征點并將特征點集進行區(qū)域劃分和匹配，實現(xiàn)文物碎片的初始對齊，再利用基于閾值約束的ICP算法實現(xiàn)碎片斷裂面的最終精確匹配.為了進一步驗證該基于特征區(qū)域劃分的碎片匹配算法的性能，對于圖1 的四組文物碎片，再分別采用ICP 算法［15］、文獻［10］算法、文獻［11］算法和文獻［12］算法對其斷裂面進行匹配，匹配結果如表1所示.

圖2 兵馬俑碎片的初始匹配結果

圖3 兵馬俑碎片的最終匹配結果

從表1可見，該基于特征區(qū)域劃分的匹配算法具有最高的匹配精度、最快的匹配速度. 與ICP 算法、文獻［10］算法、文獻［11］算法和文獻［12］算法相比，該基于特征區(qū)域劃分的匹配算法的匹配精度分別提高了約45%，35%，33%，22%，耗時分別降低了約26%，20%，16%，12%.

表1 五種算法的匹配結果

這是由于：ICP 算法對碎片的相對初始位置要求較高，且要求兩個待匹配的碎片斷裂面間存在包含關系，因此匹配精度和速度較差，其時間復雜度為O(MN)，M和N分別表示兩個待匹配點集的點數(shù)；文獻［10］算法是一種基于X 射線層析成像數(shù)據(jù)的點云匹配算法，并將其用于跟蹤原始沙粒中破碎碎片，但是該算法利用輪廓特征進行匹配，對輪廓特征破損嚴重碎片模型的匹配效果不佳，其時間復雜度為O(NlogM)；文獻［11］是一種基于距離誤差評價的ICP 算法，可以實現(xiàn)高密度點云的有效匹配，但是對低重疊率斷裂面的點云模型的匹配并無明顯優(yōu)勢，其時間復雜度為O(NlogM)；文獻［12］算法是一種結合GA 和ICP 的點云匹配算法，利用最大歸一化匹配分數(shù)配準模型實現(xiàn)匹配，可以克服ICP 算法依賴初始解和GA 容易陷入局部最優(yōu)解的缺點，但是該算法不能提高低重疊斷裂面的局部重疊率，因此對重疊率較低碎片斷裂面的匹配效果不佳，其時間復雜度為O(max(M,N))；而本文提出的基于特征區(qū)域劃分的匹配算法不僅通過提取特征點大大降低了匹配的規(guī)模，而且通過區(qū)域劃分大大提高了區(qū)域點云的重疊率，并通過在ICP算法中加入閾值約束提高了低重疊點云的匹配精度和速度，其時間復雜度為O(log(max(M,N))). 由此可見，該基于特征區(qū)域劃分的匹配算法是一種快速精確的文物碎片匹配算法，尤其對低重疊斷裂面的碎片具有良好的匹配結果.

6.2 多個碎片的整體拼合

基于本文提出的兩個碎片斷裂面的匹配算法，接下來采用子圖融合法［10］實現(xiàn)多個兵馬俑碎片的整體拼合. 首先采用基于特征區(qū)域劃分的碎片匹配算法將碎片進行兩兩匹配，確定碎片間的匹配關系，并根據(jù)該匹配關系確定所有碎片的匹配關系圖；然后將滿足匹配條件的碎片進行融合，直至所有的碎片融合為一個整體為止. 在融合的過程中允許回溯，即對于碎片融合過程中出現(xiàn)的無法融合的碎片可以進行重新融合.

以G10-52 號兵馬俑的拼合為例，該兵馬俑含碎片68個，部分碎片如圖4所示. 該68個碎片可拼合成一個俑，不存在孤立的碎片. 通常一個碎片的斷裂面不止一個，因此一個碎片可能對應多個不同的匹配碎片，從而使得碎片間存在一對多的匹配關系.G10-50 號俑的所有碎片的整體拼合結果如圖5 所示. 由圖5 可見，本文提出的碎片匹配算法可以實現(xiàn)兵馬俑碎片斷裂面的有效匹配.

圖4 部分待拼合兵馬俑碎片

圖5 碎片整體拼合結果

7 結論

在文物碎片自動匹配拼接過程中，針對傳統(tǒng)基于幾何特征匹配算法不能有效解決斷裂面重疊比例較碎片的匹配問題，本文提出了一種基于特征區(qū)域劃分的碎片斷裂面匹配算法. 首先，通過構造特征點局部區(qū)域的法線向量特征，獲得斷裂面的特征點及特征點集；然后，將提取的特征點集劃分為多個區(qū)域，并進行區(qū)域匹配以實現(xiàn)碎片初步匹配；最后，采用基于閾值約束的ICP 算法實現(xiàn)斷裂面的進一步的精確匹配，從而達到文物碎片匹配拼接的目的. 該算法不僅可以大大減少匹配的數(shù)據(jù)規(guī)模，而且可以有效改善特征區(qū)域的重疊范圍，其匹配的時間效率和匹配精度比許多傳統(tǒng)算法至少可以分別提高10%和20%. 但是，算法中沒有考慮大量噪聲對碎片匹配結果的影響，使用的數(shù)據(jù)模型都是低噪聲的文物碎片點云數(shù)據(jù)模型. 因此，在今后要繼續(xù)研究更加通用的文物碎片匹配算法，著重加強噪聲和點密度對匹配結果的影響，提高文物虛擬復原的正確率.