毛星雨

（西南科技大學(xué)理學(xué)院 四川 綿陽(yáng) 621010）

1 引言

破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時(shí)間內(nèi)完成任務(wù)。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們?cè)噲D開(kāi)發(fā)碎紙片的自動(dòng)拼接技術(shù)，以提高拼接復(fù)原效率。

2 模型預(yù)處理

由于圖片信息中僅有字的黑色和空白處的白色兩種截然相反的信息，而且為了進(jìn)一步簡(jiǎn)化計(jì)算，本文采用二值化而非灰度圖像進(jìn)行碎紙片圖像的處理，得到每條碎紙片像素大小為1980×72（長(zhǎng)×寬），像素點(diǎn)取值0或1，分別表示圖像顏色的黑與白。

為進(jìn)行圖像的整合，首先對(duì)其邊緣信息進(jìn)行提取，并用19×2的矩陣edge[i，j]存儲(chǔ)每一條碎片的邊緣像素點(diǎn)信息。從而可以進(jìn)一步就建立一個(gè)19×2的count[i，j]矩陣，該矩陣存儲(chǔ)每一條碎片邊緣取值為0的像素點(diǎn)的數(shù)量。

根據(jù)count矩陣，可得到edge[i，0]=0的碎片，由于其黑色像素點(diǎn)的數(shù)量為0，所以該碎片在原始文件中處于最左端的位置。

為進(jìn)一步提高匹配精確性，需要另外一個(gè)參數(shù)對(duì)碎片進(jìn)行數(shù)據(jù)采集。而由于圖片的行上像素點(diǎn)較列上像素點(diǎn)少很多，所以本文提取碎片圖像的行特征進(jìn)行處理。首先確定碎片頂端取值為0的像素點(diǎn)的位置，以其作為上邊界，依次向下取w為行寬（這里取w=40pixels以保證能容納每一個(gè)文字）直至下邊緣，得到每一條碎片的行數(shù)為然后取作為最終確定的行數(shù)，然后同理對(duì)生育碎片進(jìn)行行化。最終將每一條碎片劃分為28行。

3 模型建立

為了衡量?jī)蓚€(gè)碎片間的匹配程度，本文引入匹配度Mij定義如下：

其中，n為行的總數(shù)，mijk表示碎片i和碎片j第k行之間的匹配度，Mij表示碎片i和碎片j之間的匹配度。

首先需要確定最左側(cè)的碎片，然后根據(jù)匹配度的定義可以計(jì)算各個(gè)碎片兩兩之間的匹配度，從而將問(wèn)題簡(jiǎn)化為：已知最左側(cè)的碎片，然后一個(gè)個(gè)根據(jù)匹配度最大原則拼接。

可以看出，這個(gè)問(wèn)題類似于旅行商問(wèn)題，將它們進(jìn)行類比后進(jìn)一步解釋為：

圖1 問(wèn)題簡(jiǎn)化示意圖

圖中 節(jié)點(diǎn)表示碎片，有向線段長(zhǎng)度表示權(quán)值ωij，且ωij=1-Mij，箭頭指向表示前一條碎片右側(cè)邊緣到后一條碎片左側(cè)邊緣。

現(xiàn)在問(wèn)題轉(zhuǎn)變?yōu)閷ふ乙粭l回路遍歷所有的節(jié)點(diǎn)使得權(quán)值之和達(dá)到最小的TSP問(wèn)題。假設(shè)圖中存在Hamilton回路，有n個(gè)節(jié)點(diǎn)，圖中（i，j）邊的權(quán)重為ωij，設(shè)決策變量為χij=1說(shuō)明弧進(jìn)入到Hamilton回路中。

4 模型求解

通過(guò)一系列分析，將求解轉(zhuǎn)化為線性規(guī)劃最大值的求解，具體步驟為：

（1）將所有碎片數(shù)據(jù)進(jìn)行處理，組成碎片集，選擇出最左端的碎片，記為Si，然后將其從碎片集合中移除。

（2）提取Si碎片右側(cè)邊緣數(shù)據(jù)，將其與碎片池中碎片左側(cè)邊緣數(shù)據(jù)意義配對(duì)并求出匹配度Mij。

（3）選擇匹配度最大的碎片作為碎片Si的右側(cè)碎片，并將其更新為新的Si碎片，將該碎片從碎片集合中移除。

（4）重復(fù)步驟2～3直至碎片集合為空。

由于該算法使用統(tǒng)計(jì)量構(gòu)建匹配度，很好的避免了中英文之間的差異性，適用性較好，在實(shí)際的應(yīng)用中都收到了很好的效果。通過(guò)求解結(jié)果發(fā)現(xiàn)，利用貪心策略求解得到了全局最優(yōu)解，原因在于匹配度的定義較好。同時(shí)由于碎片兩側(cè)提供的信息量大，很好的避免了中英文之間的差異性。若碎片規(guī)格變小，信息量減少，中英文之間差異性的討論顯得十分有必要。

5 結(jié)語(yǔ)

本文解決的是紙片規(guī)則豎直切割的拼接復(fù)原問(wèn)題，但是實(shí)際生活中許多類似的紙片的損傷很可能是不規(guī)則的如按照斜線分割。所以考慮如果將紙片分割，將平行于切割方向的方向看做水平或者豎直的情況，剩下的部分再單獨(dú)討論，這樣可以將本文的模型推向更普適的情況。此模型整體效果較好，人為干預(yù)較少，能夠在較復(fù)雜的情況下完成碎紙片的拼接。