碎紙片拼接復原問題研究

1、基于旅行商規(guī)劃模型的碎紙片拼接復原問題研究摘要本文分別針對RSSTD(Reconstruction of Strip Shredded Text Document）、RCCSTD(Reconstruction of cross-cut Shredded Text Document)和Two-Sides RCCSTD三種類型的碎紙片拼接復原問題進行了建模與求解算法設計。首先我們對于RSSTD問題，建立了基于二值匹配度的TSP模型，并將其轉化為線性規(guī)劃模型，利用貪心策略復原了該問題的中文和英文碎片；然后對于RCCSTD問題，由于中英文字的差別，我們分別建立了基于改進誤差評估的漢字拼接模型和基于文字

2、基線的誤差評估的英文字拼接模型，并利用誤差評估匹配算法，復原了該問題的中文和英文碎片；隨后我們針對正反兩面的RCCSTD問題，利用基線的概念將正反兩面分行，轉化為RCCSTD問題，并復原了該問題的英文碎片。最后，我們對模型的算法和結果進行了檢驗和分析。 問題一：我們針對僅縱切的情況，首先將圖像進行數字化處理，轉換為了二值圖像，然后得到各圖像的邊緣，并計算所有碎片與其他碎片邊緣的匹配程度。然后，根據兩兩碎片之間的匹配程度建立了TSP模型，并將其劃歸為線性規(guī)劃模型。最終，我們根據左邊距的信息確定了左邊第一碎片，隨后設計了基于匹配度的貪心算法從左向右得到了所有碎片的拼接復原結果。結果表明我們的方法對

3、于中英文兩種情況適用性均較好，且該過程不需要人工干預。 問題二：我們針對既縱切又橫切的情況，由于中英文的差異性，我們在進行分行聚類時應采用不同的標準。首先根據左右邊距的信息確定了左邊和右邊的碎片，隨后分別利用基于改進誤差評估的漢字拼接模型和基于文字基線的誤差評估模型，將剩余的碎片進行分行聚類，然后再利用基于誤差評估的行內匹配算法對行內進行了拼接，最終利用行間匹配算法對行間的碎片進行了再拼接，最終得到了拼接復原結果。對于拼接過程中可能出現(xiàn)誤判的情況，我們利用GUI編寫了人機交互的人工干預界面，用人的直覺判斷提高匹配的成功率和完整性。 問題三：我們針對正反兩面的情況，首先根據正反基線信息，分別確定

4、了左右兩邊的碎片，然后利用基線差值將其兩兩聚類，聚類以后其正反方向也一并確定，隨后我們將其與剩余碎片進行分行聚類，最終又利用行內匹配和行間匹配算法得到了最終拼接復原結果。其中，對于可能出現(xiàn)的誤判情況，我們同樣在匹配算法中使用了基于GUI的人機交互干預方式，利用人的直覺提高了結果的可靠性和完整性。 關鍵字：碎片復原、TSP、誤差評估匹配、基線誤差、人工干預一、 問題重述 破碎文件的拼接復原工作在傳統(tǒng)上主要需由人工完成，準確率較高，但效率很低。特別是當碎片數量巨大，人工拼接很難在短時間內完成任務。隨著計算機技術的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術，以提高拼接復原效率。請討論以下問題： 1. 對

5、于給定的來自同一頁印刷文字文件的碎紙機破碎紙片（僅縱切），建立碎紙片拼接復原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎片數據進行拼接復原。如果復原過程需要人工干預，請寫出干預方式及干預的時間節(jié)點。復原結果以圖片形式及表格形式表達。 2. 對于碎紙機既縱切又橫切的情形，請設計碎紙片拼接復原模型和算法，并針對附件3、附件4給出的中、英文各一頁文件的碎片數據進行拼接復原。如果復原過程需要人工干預，請寫出干預方式及干預的時間節(jié)點。 3. 上述所給碎片數據均為單面打印文件，從現(xiàn)實情形出發(fā)，還可能有雙面打印文件的碎紙片拼接復原問題需要解決。請嘗試設計相應的碎紙片拼接復原模型與算法，并就附

6、件5的碎片數據給出拼接復原結果。二、 問題分析 破碎文件的拼接復原工作，傳統(tǒng)人工處理準確率高，但是效率低。隨著計算機技術的發(fā)展，本問題試圖尋找碎紙片的自動拼接方法。本文的碎片均為矩形，且大小一樣，這就給碎片的拼接帶來了困難，因為難以利用碎片的輪廓信息，從而只能利用碎片邊緣的圖像像素信息來進行拼接。 對于問題一，給出了縱切的19條碎紙片，碎片為1980*72，總切線的像素點較多，并且碎紙片的數量較少，從效率出發(fā)，可以直接考慮縱切條上的像素統(tǒng)計信息。為了衡量匹配程度，需要建立誤差評估函數。本文考慮采用TSP模型，將碎紙片作為節(jié)點，將誤差評估函數的值作為節(jié)點之間的權值，尋找最優(yōu)解。在本問題的情況下，

7、中英文的差別并無太大影響。 對于問題二，由于給出的數據是橫縱切的中英文碎片，碎片大小為180*72，各208張。因為碎紙片的數量較多，直接匹配則為NP問題中的無法用多項式解決的問題，所以先將行分組匹配完成后再把各行拼接起來。本問題主要解決：1）如何正確高效分組；2）如何準確高效拼接?？紤]到中文和英文在字形和印刷結構上的不同，需要定義不同的特征向量去描述中文和英文的碎紙片上的信息。文字各行的位置和間距將作為重要的分組依據。在問題一的基礎上，由于每個碎紙片的邊緣像素較少，為了充分利用包含信息，誤差評估函數的定義將會比問題一中更加細化。行之間的拼接將會利用邊緣像素和間距匹配。在本問題中，中英文的基線

8、選擇方法將會有很大不同。 對于問題三，在問題二的基礎上，加入了正反面信息，碎紙片的形狀并沒有改變。因此，需要在問題二的誤差評估函數的基礎上，綜合考慮正反面的匹配誤差。分組的方法與行間的拼接方式與問題二基本相同。 綜上所述，本問題可以看做是TSP問題，碎紙片為節(jié)點，誤差評估函數值為邊的權值，尋求最優(yōu)解的問題。三、模型假設 1. 假設需要復原的碎片是來自同一張紙，且對于該張紙具有完備性。 2. 假設同一頁中，文字的種類、行間距和段落分布情況是相同的。四、模型建立與求解文件碎片拼接主要有兩類不同的技術標準： （1） Reconstruction of Strip Shredded Text Docu

9、ments(RSSTD) 碎片的長度和原始文件的長度相等，同時所有碎紙片都是等寬的長方形。 （2）Reconstruction of Cross-cut Shredded Text Document(RCCSTD) 所有的文件碎片都是長方形且大小相等，但其長度小于原始文件的長度。 問題一為典型的RSSTD問題，我們通過分析碎紙片文字的行特征，建立了一種基于匹配度的求解模型，下面就對該模型的建立進行詳細的討論。5.1 問題1基于匹配度的RSSTD問題研究為了便于對圖像數據進行分析，我們首先需要對其進行數字化處理以及文字行特征的提取，而后再建立基于匹配度的模型。 5.1.1圖像數字化處理 圖像的數

10、字化處理主要包括以下幾個方面： （1） 二值化處理 由于縱切碎紙片的長度特征（碎片長度與原始文件長度相等），其邊緣像素點信息量豐富。因此我們采取二值化而非灰度對圖像進行了處理，進一步簡化了算法的復雜度，得到每條碎片像素大小為72´1980（長´寬），像素點值取0,1，其中0和1分別表示顏色的黑與白。 （2） edge矩陣的建立 edgei,j為19´2的矩陣，儲存每一條碎片的邊緣像素點信息。其中i表示碎片的編號，j=0表示左側邊緣像素點信息，j=1表示右側邊緣像素點信息。例如，edge0,0儲存001號碎片左側邊緣像素點信息。 （3） count矩陣的建立 根據e

11、dgei,j矩陣，我們可以計算得到一個19´2的counti,j矩陣，該矩陣儲存每一條碎片邊緣取值為0的像素點的數量。例如，count0,0=350表示001號碎片左側邊緣共有350個黑色像素點。 （4） shred with blank left的選取 根據count矩陣，若edgei,0=0，那么我們就認為該碎片在原始文件中處于類、行間距和段落分布情況是相同的。最左端，即為選取的shred with blank left。（5） 碎片行特征的提取 由于原始文件文字行特征明顯，因此我們需要提取碎片的行特征（其具體的原因見匹配度的定義）。首先確定碎片頂端取值為0的像素點的位置，以此作

12、水平線為上邊界，依次向下取w為行寬（這里取w=40 pixels以保證能容納每一個文字）直至下邊緣，得到每條碎片的行數為n1, n2, n19；然后取n=maxn1, n2, n19作為最終確定的行數，并以該條碎片的行化方式為標準對每一條碎片進行行化；最終每一條碎片被劃分為28行。 每條碎片維護著以下的特征數據表：表 1 碎片i特征數據表 k 1 2 3 27 28 nkl ni1l ni2l ni3l ni27l ni28l nkr ni1r ni2r ni3r ni27r ni28r 其中，k為行號；nkl為第k行左側邊緣取值為0的像素點的數量，nkr為第k行右側邊緣取值為0的像素點的數量

13、；nikl為第i條碎片第k行左側邊緣取值為0的像素點的數量。5.1.2匹配度的定義 為了衡量兩個碎片之間的匹配程度，我們定義匹配度Mij作為評價的標準，其計算公式如下：= =å其中，n為總的行數（如28n=）；ijkm表示碎片i和碎片j第k行之間的匹配度；ijM表示碎片i和碎片j之間的匹配度。 這里我們不選擇通過統(tǒng)計碎片邊緣總黑色像素點的數量來計算兩碎片之間的匹配度，而是通過計算兩碎片行匹配度來間接計算其匹配度，原因在于： 若以總的邊緣黑色像素點計算匹配度，行與行之間的差異性無法體現(xiàn)，匹配結果誤差過大； 通過行匹配度計算碎片之間的匹配程度，更加充分的挖掘了碎片邊緣的信息，更為精確。5

14、.1.3.1 模型的建立 根據匹配度的定義，我們可以計算得到19個碎片兩兩之間邊緣的匹配度，現(xiàn)可將問題化簡為：已知起始碎片和其他碎片之間的匹配度，尋找一序列使得碎片之間總的匹配度達到最大。如右圖所示： （1） 為簡化問題，我們引入空白碎片0，同樣可計算得到空白碎片與其他碎片的匹配度； （2） （2）其中節(jié)點表示碎片，有向線段長度表示費用wij，且wij=1-Mij，箭頭所指方向表示前一條碎片右側邊緣到后一條碎片左側邊緣。如表示1號的碎片右側邊緣與2號碎片左側邊緣的費用；（3） 現(xiàn)要求尋找一條回路遍歷所有的節(jié)點使得費用達到最小。 通過分析，可以發(fā)現(xiàn)這是一典型的TSP問題。為解決上述問題，我們建立

15、模型如下： 假設圖中存在Hamilton回路，有n個節(jié)點，圖中(i,j)邊的權重為wij，設決策變量為xij=1說明弧(i,j)進入到Hamilton回路中，則線性規(guī)劃模型可表達6為：求解該問題就是求解該線性規(guī)劃問題的最優(yōu)解。 5.1.3.2 模型的求解 為了進一步求解上述模型，我們設計的算法如右 圖所示： （1）將所有碎片放入地址池中； （2）選出左側全為白色像素點的碎片作為基準碎片，記為si，并將其從碎片池中剔除；（3）依次計算si右側邊緣與地址池中其他碎片sj左側邊緣的匹配度Mij； （4）選擇匹配度最大的碎片st作為碎片si的右側碎片，并將其記為si，從碎片池中剔除該碎片； （5）重復

16、（3）（4）步直至碎片池為空。 由于該算法使用統(tǒng)計量構建匹配度，很好的避免了中英文之間的差異性，適用性較好，在實際的應用中都收到了很好的效果。最終可以得到附件1與附件2中碎片的正確序列如下所示：通過求解結果發(fā)現(xiàn)，我們利用貪心策略求解得到了全局最優(yōu)解，原因在于匹配度的定義較好。同時由于碎片兩側提供的信息量大，很好的避免了中英文之間的差異性。若碎片規(guī)格變小，信息量減少，中英文之間差異性的討論顯得十分有必要。 5.2 問題2基于誤差評估的RCCSTD問題研究 由于中英文的字存在顯著的差異性，對算法的設計有很大影響，因此我們需要對它們進行具體的討論。 如右圖所示，我們可以分析得到如下的差異性特征： （

17、1）中英文的字行存在顯著的差異性，中文字結構復雜，筆畫繁多，無法確定固定的基準線； （2）英文字印刷格式固定，一般為“四線三格” 的形式，容易通過基準線來確定具體字母的位置信息。 基于以上分析，我們需要針對中英文設計不同的模型進行碎紙片的拼接復原。下面首先建立文字的拼接復原模型。5.2.1基于誤差評估的漢字拼接模型 5.2.1.1 碎片的逐行分組 （1）逐行分組原因分析 首先參考問題一中的算法提取位于原始文件左右邊界位置的22塊碎片，以此為基礎將所有碎片分為22組，而非按列分組或分為11組，主要原因如下： 若按列分組，由于碎片上下邊緣信息量少，分組誤差較大，不可??； 若以原始文件左側邊緣的11

18、塊碎片為基礎將所有碎片分為11組，可能存在以下的問題：如右圖所示，014塊碎片為原始文件的左側邊緣碎片，128塊碎片為其右側碎片。但由于014塊碎片處于一自然段的開始位置，上半部分基本為空白，而128塊碎片上半部分信息豐富，兩者匹配失敗率高，很可能導致該組元素個數為0。因此我們將碎片分為22組，同時考慮左側邊緣與右側邊緣的信息，分組效率高且準確率高。（2） 分組標準的確定 我們確立四個參數dtb，dbb，dtw，dbw其意義如右圖所示。其中dtb，dbb代表由上下邊緣至中間像素點由黑過度到白的距離；dtw，dbw代表上下邊緣至中間像素點由白過度到黑的距離。 根據上述定義，對于每一幅圖像，首先判

19、斷其上下邊緣的過度情況，由此可以確定上下邊緣的兩個參數。那么我們認為若兩個碎片具有相同的參數，如同樣為dtb和dbw，同時相同參數之間的差值不超過4pixels，即：那么，我們認為兩碎片在同一組內。最終可以得到分組情況如下表所示：由上表可知，由于某些碎片的特殊性，仍不能歸入任何一組。這些碎片有1，15，17，27，30，33，58，80，81，83，86，95，105，114，117，132，133，156，165，170，178，198，200，202。我們可以將他們放入碎片池中，這一部分碎片后續(xù)將進行單獨的處理。5.2.1.2 組內碎片匹配算法的設計 評價兩塊碎片拼接的好壞程度，我們用誤差

20、評估函數來描述。 由題可知，每頁被分為了11´19個碎片，每個碎片具有同樣的規(guī)格。那么，就有ijhh=，表示兩碎片的高度相等。我們定義誤差評估函數(,)hcij為：其中，每個像素點以8位數值表示，有：如上圖所示，我們將一碎片邊緣等分為三分。在考慮像素點y時，對其鄰域y+1，y+2，y-1，y-2共5個像素點進行分析，并賦予不同的權重，那么可以分別計算得到三段的誤差評估函數為123(,),(,),(,)hhhcijcijcij。參考問題一，設計組內匹配算法如下： （1）將組內碎片以及剩余未分組的碎片放入碎片池中； （2）以左側全為白色像素點的碎片為基準碎片，記為si，并將其從碎片池中剔

21、除； （3）依次計算si右側邊緣與地址池中其他碎片sj左側邊緣的誤差評估值123(,),(,),(,)hhhcijcijcij； （4）依次計算碎片si與池中其他碎片sj的相對誤差:1其中，j表示當前比較的碎片，j¢為碎片池中其他的碎片，k表示上下三段， 如123,h1h2h3；（5）選取相對偏差最小的碎片，且x¢£時，將該碎片作為碎片si的右側碎片，并記該碎片為si，將其從碎片池中刪除；（6）重復（3）（5）步18次直至結束。 1222組可以根據同樣的算法進行碎片的拼接復原。在此過程中由于最小相對誤差的碎片存在多個，計算機很難進行取舍。因此，在程序中，我們設計了

22、人機交互的界面，當遇到此類情況時，通過人工干預的方式來選擇最佳的碎片。最后，可以得到22個拼接好的片段。5.2.1.3 組間片段的匹配 組間片段的匹配，我們主要依據以下兩點原則： （1）若兩個片段在同一行，那么兩個片段內碎片的數量應當互補（和為19）； （2）以一個片段為基礎，計算其與右側片段的相對偏差，相對偏差越小，匹配程度越高。 根據以上原則，最終可以得到左右兩側片段按行匹配的結果如下圖所示：5.2.1.4 行間匹配 類似于組內碎片匹配的算法，通過計算行片段之間上下邊緣的誤差評估值，最終可以得到行片段的正確序列。行誤差評估值2的計算公式如下：5.3問題三Two-Sides RCCSTD問題研究 通過對問題三的分析，發(fā)現(xiàn)問題的解決方案基本與問題二類似，但針對正反碎片的