基于線性規劃的碎紙片拼接復原模型

毛星雨

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

1 引言

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

2 模型預處理

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

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

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

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

3 模型建立

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

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

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

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

圖1 問題簡化示意圖

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

現在問題轉變為尋找一條回路遍歷所有的節點使得權值之和達到最小的TSP問題。假設圖中存在Hamilton回路，有n個節點，圖中（i，j）邊的權重為ωij，設決策變量為χij=1說明弧進入到Hamilton回路中。

4 模型求解

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

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

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

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

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

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

5 結語

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