二維碎片拼接的局部匹配

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

關(guān)鍵詞： 碎片拼接； 多邊形逼近； 旋轉(zhuǎn)角度； 局部匹配

中圖分類(lèi)號(hào)： TN911.73?34； TP391 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

在考古文物復(fù)原（如破碎壁畫(huà)、瓷片等）、司法物證鑒定、破碎人民幣拼合等領(lǐng)域普遍存在碎片拼接問(wèn)題，當(dāng)碎片數(shù)量較大時(shí)，人工比對(duì)實(shí)現(xiàn)拼合是一項(xiàng)重復(fù)而繁瑣的任務(wù)，耗費(fèi)大量時(shí)間和精力，還可能對(duì)物件造成二次損壞。計(jì)算機(jī)技術(shù)的發(fā)展使得用計(jì)算機(jī)實(shí)現(xiàn)碎片復(fù)原成為可能。二維碎片自動(dòng)拼接的相關(guān)研究，具有較強(qiáng)的理論和實(shí)際意義。

按照碎片特征，二維非規(guī)則碎片拼接可分為基于輪廓和基于內(nèi)容（色彩、紋理等）的碎片拼接，還可以分為有基準(zhǔn)圖像和無(wú)基準(zhǔn)圖像的拼接?；谳喞亩S碎片拼接研究較多，可分兩個(gè)步驟：

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

（2） 全局匹配重建。

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

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

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

1 預(yù)處理

圖像碎片預(yù)處理步驟如下：

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

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

2 輪廓曲線(xiàn)的表示

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

如圖2中，輪廓上的星號(hào)表示碎片邊緣的近似多邊形頂點(diǎn)。假設(shè)得到多邊形的頂點(diǎn)坐標(biāo)序列[v1v2…vn，]每個(gè)頂點(diǎn)用橫坐標(biāo)和縱坐標(biāo)表示。從第一個(gè)頂點(diǎn)開(kāi)始計(jì)算旋轉(zhuǎn)角度。頂點(diǎn)[vi（1

如果兩個(gè)多邊形匹配，由于凸角跟凹角匹配，則匹配頂點(diǎn)處的旋轉(zhuǎn)角度是大小相同、正負(fù)相反的。

3 局部匹配

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

（1） 將兩序列視為環(huán)形，不需要進(jìn)行序列的復(fù)制，也不再要求移動(dòng)的序列短于不移動(dòng)的序列；

（2） 兩序列中的對(duì)應(yīng)元素采用相加的方式計(jì)算誤差；

（3） 用匹配度量Match_Deg來(lái)表示每個(gè)匹配段的匹配程度。

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

假設(shè)待比較的兩序列為shape1，shape2，其中shape2序列是逆序排列的。shape2從對(duì)應(yīng)shape1第一個(gè)元素的位置開(kāi)始，每次移動(dòng)一個(gè)位置，一直移動(dòng)到shape1的最后一個(gè)元素。當(dāng)shape2移動(dòng)到shape1的某個(gè)位置時(shí)，shape1和shape2的對(duì)應(yīng)元素將進(jìn)行從左到右的比較，若發(fā)現(xiàn)某兩個(gè)對(duì)應(yīng)元素匹配，則將這兩個(gè)元素視為匹配段的起始點(diǎn)，從這兩點(diǎn)開(kāi)始一段匹配，并計(jì)算累積總誤差：

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

繼續(xù)向右比較，直到某兩個(gè)元素的[|e|]超出[ε，]或ErrorTank超出閾值ErrorTankCapacity，這個(gè)匹配段就結(jié)束，計(jì)算該段的匹配度量Match_Deg。把該匹配的起始點(diǎn)、終止點(diǎn)及匹配度量信息記錄下來(lái)，最后會(huì)得到若干個(gè)匹配信息，選取匹配程度最高的即Match_Deg最小的匹配段，作為shape2此次移動(dòng)的最佳匹配，存入結(jié)果中。當(dāng)shape1每個(gè)位置都被shape2移動(dòng)到后，再?gòu)拿看我苿?dòng)的匹配結(jié)果中選擇匹配程度最高的一個(gè)匹配，作為這兩個(gè)碎片最可能的匹配，稱(chēng)為候選匹配。

假設(shè)shape1，shape2長(zhǎng)度分別為[M，][N，]文獻(xiàn)[4]中坦克算法要進(jìn)行[M]次位移，每次位移要比較[2N]次，會(huì)導(dǎo)致重復(fù)比較，從而產(chǎn)生重復(fù)的匹配結(jié)果，而改進(jìn)后的算法，shape2共移動(dòng)[M]個(gè)位置，每次位移進(jìn)行[N]次比較，提高了效率。由于本文的算法過(guò)程是基于近似多邊形的，一般多邊形頂點(diǎn)數(shù)約為8～20個(gè)，而“坦克算法”是基于像素的，故本文算法的時(shí)間復(fù)雜度遠(yuǎn)遠(yuǎn)小于文獻(xiàn)[4]中曲率串的“坦克算法”。

本文的實(shí)驗(yàn)最終返回了如圖4（a）中的一個(gè)候選匹配，Match_Deg=0.095 25，圖4（b）顯示了這兩片碎片的真實(shí)匹配，結(jié)果表明，實(shí)驗(yàn)返回的候選匹配是真實(shí)匹配。

4 結(jié) 語(yǔ)

本文提出的方法是基于多邊形逼近的，提取出多邊形的轉(zhuǎn)角和邊長(zhǎng)，并對(duì)轉(zhuǎn)角序列和邊長(zhǎng)進(jìn)行比較，由于多邊形頂點(diǎn)數(shù)遠(yuǎn)小于實(shí)際像素?cái)?shù)，所以基于多邊形的方法相對(duì)于基于像素的方法可減少計(jì)算量，提高效率。下一步可將這種方法應(yīng)用于多片碎片的局部匹配和全局匹配，從而實(shí)現(xiàn)拼接。

參考文獻(xiàn)

[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] 朱延娟，周來(lái)水，張麗艷，等.基于Hausdorff距離的多尺度輪廓匹配算法[J].中國(guó)機(jī)械工程，2004，15（17）：1553?1561.

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

[8] 饒芮菱，金雪峰，魯懷偉.基于鏈碼的二維碎片輪廓匹配算法[J].計(jì)算技術(shù)與自動(dòng)化，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.