毛星雨

（西南科技大學理學院 四川 綿陽 621010）

1 引言

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

2 模型預處理

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

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

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

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

3 模型建立

為了衡量兩個碎片間的匹配程度，本文引入匹配度Mij定義如下：

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

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

可以看出，這個問題類似于旅行商問題，將它們進行類比后進一步解釋為：

圖1 問題簡化示意圖

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

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

4 模型求解

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

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

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

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

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

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

5 結語

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