二維碎片拼接的局部匹配

摘 要： 基于輪廓的二維非規則碎片拼接問題，通常分為局部匹配和全局匹配兩個步驟，這里提出一種新的局部匹配的方法，首先對輪廓進行多邊形逼近得到多邊形頂點序列，然后獲取多邊形頂點的轉角序列特征并計算相鄰頂點間長度，對該轉角序列使用改進過的“坦克算法”，應用一定篩選規則，尋找到多邊形頂點的若干候選匹配信息。改進的算法可降低時間復雜度，提高匹配效率。

關鍵詞： 碎片拼接； 多邊形逼近； 旋轉角度； 局部匹配

中圖分類號： TN911.73?34； TP391 文獻標識碼： A 文章編號： 1004?373X（2015）09?0054?03

Abstract： The 2?D irregular fragments reassembling issue based on contour is usually divided into two steps： local matching and global matching. A new local matching method based on improved Tank algorithm is proposed. Firstly the sequence of polygon vertices is obtained by polygonal approximation to the contour， then the corner sequence signature of the polygon is acquired， the distance between two adjacent vertices is calculated. The improved Tank algorithm is applied in the corner sequence to find some candidate matching information of the polygon vertices by some screening rules. The improved algorithm can reduce time complexity and improve matching efficiency.

Keywords： fragment reassembling； polygon approximation； rotation angle； local matching

0 引 言

在考古文物復原（如破碎壁畫、瓷片等）、司法物證鑒定、破碎人民幣拼合等領域普遍存在碎片拼接問題，當碎片數量較大時，人工比對實現拼合是一項重復而繁瑣的任務，耗費大量時間和精力，還可能對物件造成二次損壞。計算機技術的發展使得用計算機實現碎片復原成為可能。二維碎片自動拼接的相關研究，具有較強的理論和實際意義。

按照碎片特征，二維非規則碎片拼接可分為基于輪廓和基于內容（色彩、紋理等）的碎片拼接，還可以分為有基準圖像和無基準圖像的拼接。基于輪廓的二維碎片拼接研究較多，可分兩個步驟：

（1） 根據碎片的輪廓信息進行兩兩匹配，找到任意兩個碎片之間可能的匹配部分，即局部匹配；

（2） 全局匹配重建。

本文提出的方法主要針對基于輪廓的二維碎片拼接的局部匹配部分。

目前，國內外針對二維碎片局部輪廓匹配的研究較多。Wolfson H提出一種基于曲線累積轉角串的輪廓曲線匹配方法[1]。Leita o H C等人給出一種多尺度的二維碎片拼接方法[2]，通過對輪廓采樣點的曲率串進行多尺度分析，利用動態規劃技術對匹配對進行精化處理。Kimia B等學者提出了一種先粗尺度后精尺度的動態規劃局部匹配[3]，可以提高匹配效率，但對兩對應曲線的采樣分布有較強的依賴性。Amigoni等人提出一種新的基于局部曲率和色彩的局部匹配方法[4]，有較好的容錯性。朱良家等提出一種對弧長-累積轉角序列差進行直方圖分析的局部匹配方法[5]。國內也有較多學者進行了相關研究。朱延娟等提出了一種基于Hausdorff距離的多尺度輪廓匹配算法[6]。周豐等人提出了一種基于角序列并與多尺度空間相結合的輪廓匹配算法[7]。饒芮菱等人也提出了一種基于鏈碼的輪廓匹配算法[8]。

本文的方法是先對碎片輪廓進行多邊形逼近，并計算多邊形的轉角，再用基于文獻[4]方法的改進算法，尋找碎片多邊形的候選匹配對。

1 預處理

圖像碎片預處理步驟如下：

（1） 采用掃描儀獲取碎片灰度圖像，如圖1所示。

（2） 對得到的灰度圖像進行直方圖分析，把灰度圖像轉換為二值圖，其中1表示碎片，0表示背景，然后提取二值圖像的邊緣，碎片的邊緣像素就是與背景像素相鄰但屬于碎片的元素，順時針逐一順次尋找八連通的碎片邊緣像素，得到碎片邊緣，如圖2所示，碎片邊緣表示為順時針的坐標序列。

2 輪廓曲線的表示

在提取到邊緣輪廓后，對輪廓曲線進行多邊形逼近，用得到的多邊形頂點序列表示輪廓曲線，并且計算多邊形的轉角，用于后面的匹配。多邊形逼近可分為基于參數的[9]和非參數的[10]，本文采用閾值法迭代獲得多邊形頂點。每個碎片的多邊形頂點個數大約為8～20個。

如圖2中，輪廓上的星號表示碎片邊緣的近似多邊形頂點。假設得到多邊形的頂點坐標序列[v1v2…vn，]每個頂點用橫坐標和縱坐標表示。從第一個頂點開始計算旋轉角度。頂點[vi（1

如果兩個多邊形匹配，由于凸角跟凹角匹配，則匹配頂點處的旋轉角度是大小相同、正負相反的。

3 局部匹配

為了使用“坦克算法”比較兩個碎片輪廓的旋轉角度序列從而找到匹配部分，本文對“坦克算法”進行了改進：

（1） 將兩序列視為環形，不需要進行序列的復制，也不再要求移動的序列短于不移動的序列；

（2） 兩序列中的對應元素采用相加的方式計算誤差；

（3） 用匹配度量Match_Deg來表示每個匹配段的匹配程度。

首先，由于旋轉角度序列都是按順時針獲得的，而兩個序列要從相反的方向來比較，所以要將其中一個序列逆序排列；其次，考慮到碎片邊緣是閉合的，所以要將兩個旋轉角度序列看做環狀，再進行比較。由于匹配頂點的旋轉角度是大小相同、正負相反的，所以在“坦克算法”中，比較兩個序列的對應元素時，計算兩者和的絕對值|e|，如果|e|=0，則認為這兩個元素對應的多邊形頂角是匹配的。由于掃描噪聲等的影響，旋轉角度序列匹配部分不是完全一樣，有一定誤差，所以需要給定一個閾值ε（ε>0）來容忍|e|，即如果兩個元素的絕對誤差|e|在ε范圍內，則認定它們對應的頂角是匹配的。對得到的匹配段，為便于比較匹配程度，計算其匹配度量：

假設待比較的兩序列為shape1，shape2，其中shape2序列是逆序排列的。shape2從對應shape1第一個元素的位置開始，每次移動一個位置，一直移動到shape1的最后一個元素。當shape2移動到shape1的某個位置時，shape1和shape2的對應元素將進行從左到右的比較，若發現某兩個對應元素匹配，則將這兩個元素視為匹配段的起始點，從這兩點開始一段匹配，并計算累積總誤差：

[ErrorTank=e，] [ErrorTank]初值為0

繼續向右比較，直到某兩個元素的[|e|]超出[ε，]或ErrorTank超出閾值ErrorTankCapacity，這個匹配段就結束，計算該段的匹配度量Match_Deg。把該匹配的起始點、終止點及匹配度量信息記錄下來，最后會得到若干個匹配信息，選取匹配程度最高的即Match_Deg最小的匹配段，作為shape2此次移動的最佳匹配，存入結果中。當shape1每個位置都被shape2移動到后，再從每次移動的匹配結果中選擇匹配程度最高的一個匹配，作為這兩個碎片最可能的匹配，稱為候選匹配。

假設shape1，shape2長度分別為[M，][N，]文獻[4]中坦克算法要進行[M]次位移，每次位移要比較[2N]次，會導致重復比較，從而產生重復的匹配結果，而改進后的算法，shape2共移動[M]個位置，每次位移進行[N]次比較，提高了效率。由于本文的算法過程是基于近似多邊形的，一般多邊形頂點數約為8～20個，而“坦克算法”是基于像素的，故本文算法的時間復雜度遠遠小于文獻[4]中曲率串的“坦克算法”。

本文的實驗最終返回了如圖4（a）中的一個候選匹配，Match_Deg=0.095 25，圖4（b）顯示了這兩片碎片的真實匹配，結果表明，實驗返回的候選匹配是真實匹配。

4 結 語

本文提出的方法是基于多邊形逼近的，提取出多邊形的轉角和邊長，并對轉角序列和邊長進行比較，由于多邊形頂點數遠小于實際像素數，所以基于多邊形的方法相對于基于像素的方法可減少計算量，提高效率。下一步可將這種方法應用于多片碎片的局部匹配和全局匹配，從而實現拼接。

參考文獻

[1] WOLFSON H. On curve matching [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1990， 12（5）： 483?489.

[2] DA GAMA LEITAO H C， STOLFI J. A multiscale method for the reassembly of two?dimensional fragmented objects [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2002， 24（9）： 1239?1251.

[3] KONG Wei?xin， KIMIA B B. On solving 2D and 3D puzzles using curve matching [C]// Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. [S.l.]： IEEE， 2001， 2： 583?590.

[4] AMIGONI F， GAZZANI S， PODICO S. A method for reassembling fragments in image reconstruction [C]// Proceedings of 2003 International Conference on Image Processing. [S.l.]： IEEE， 2003， 2： 581?584.

[5] ZHU Liang?jia， ZHOU Zong?tan， HU De?wen. Globally consistent reconstruction of ripped?up documents [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2008， 30（1）： 1?13.

[6] 朱延娟，周來水，張麗艷，等.基于Hausdorff距離的多尺度輪廓匹配算法[J].中國機械工程，2004，15（17）：1553?1561.

[7] 周豐，黃曉鳴.基于角序列的二維碎片輪廓匹配算法[J].科學技術與工程，2007，7（15）：3757?3760.

[8] 饒芮菱，金雪峰，魯懷偉.基于鏈碼的二維碎片輪廓匹配算法[J].計算技術與自動化，2007，26（2）：34?37.

[9] JUSTINO E， OLIVEIRA L S， FREITAS C. Reconstructing shredded documents through feature matching [J]. Forensic Science International， 2006， 160（2）： 140?147.

[10] ROSIN P L， WEST G A W. Non?parametric segmentation of curves into various representations [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1995， 17（2）： 1140?1153.