碎紙片的拼接復原研究

趙辰 喬振宇 李思漫

（遼寧工程技術大學電子與信息工程學院，遼寧葫蘆島 125105）

1 問題重述

對于只有縱切的碎片文件（要求其來自同一種印刷格式），建立拼接模型以及算法，進行碎片的拼合，在復原過程中，若需要部分人工干預，表示出干預方式及干預過程的時間節點。最后，通過完整圖片表示出復原結果。

在既有縱切又有橫切的情況下，請設計模型以及算法，進行碎片的拼合，復原結果以圖片形式表達。

2 模型的假設

2.1 假設題目所給的所有碎片擁有相同的大小及尺寸，其邊緣的輪廓是正常且形狀規則的矩形。

2.2 假設所給破碎文件四周邊界上的文字和符號都是完整的。

2.3 所有碎片中的文字印刷格式、顏色、字號一致，同時字體顏色與背景顏色有較大的區別。

3 問題的分析

針對在碎紙片被縱切的特殊情況下，是首先利用matlab 轉化，分別通過轉化計算出各一張碎紙片的轉化灰度和二值矩陣，然后通過轉化灰度為二和一值矩陣，得出兩張不同碎紙片上的邊緣二和一值矩陣向量值在矩陣上的差異，同時通過轉化灰度和二值矩陣計算得出紙片文字號和行列號在位置上的差異，按照此方法依次從左至右找到相鄰碎片，最終復原碎片。

針對紙片被縱切和橫切的情況下，這個問題屬于二維復原問題，不僅要考慮碎片左右端特征，還要考慮上下端特征。考慮到特征因子難以滿足問題的要求，故增加兩個特征因子-空白行和向左（向右）最小邊距。

4 模型的建立與求解

4.1 紙片縱切問題的求解

首先將每幅圖片依次進行灰度處理，得到一個1980 行、72列的灰度值矩陣。碎紙片的測量尋找灰度方向一般為從左向右，找到左側每塊碎紙片的兩個灰度測量矩陣的最后一列，再依次找到右側碎片硬紙片的灰度矩陣第一列，讓這兩列的灰度值相同，則這兩個碎片為相鄰圖片。按這種循環多次比較，直到判斷出碎紙片的正確順序。

4.1.1 首先選取一個圖片，先將它進行格式轉化，將其灰度化和二值化。

4.1.2 將這些灰度后的圖片進行二值化，二值化之后產生矩陣部分矩陣不予給出，最后得到全部矩陣。

①首先進行濾波的處理，濾出其的噪聲，再進行平滑圖像處理為第一步；

②其次就是進行直線邊界的分析提取。依據關于形態邊界梯度的數學算子分析公式，通過3*3 的8 個不同連通邊際結構邊界元素，分別對其圖像進行連通邊界的運算提取，得到8 幅不同的連通邊界結構圖像，其次就是得到這些邊界圖像在其固定的邊界位置上的每個像素的數值，運算之后得到所在邊界上的圖像e1；

③系統使用直方照片圖閾的二值化計算方法，對計算得到的直方圖片數據進行圖像二值化，最終用戶可以接收到圖片二值化后的圖像；

④對應的圖像圖象e1 使用閾值統計分析方法二次閾值化，得到二次閾值化的圖像圖象e2；

⑤將二值化圖像e2 的每個像素，通過位反運算，得到一個新的二值圖像e3；

⑥最終結合之前的三個圖，輸出二值圖像G。

4.1.3 按照此方法依次對碎紙片進行處理，分別求得每一幅圖片右側吻合度最高的圖片，最后讀取十九張圖片之后得到全部的邊緣距離矩陣，依據這些邊緣距離矩陣求出和紙片右相鄰的紙片，最后求出文件中最左邊的碎片，從而記錄上一張碎紙條，然后記錄下一張碎紙片。最后存取整張圖片，得到復原圖。（表1、2）

表1 問題一附件1 的拼接序號表

4.2 紙片被縱切和橫切的求解

我們先利用上述模型中的的灰度化后的模型進行二值化處理，得到相對應的二值化模型，進行碎片的復原。然后再將拼接好的已經被拼接的部分變為碎片，最后可以得到經過還原處理出來的碎片紙張，利用由每個碎片紙張組成的數據文件夾對數據模塊進行綜合模擬并用仿真進行處理。

4.2.1 空白行特征因子定義

對于碎片的灰度矩陣Aj（j=1，2，……，19），構造的列向量cj，cj（m）代表列向量第m 行元素。cj用以記錄Aj的空白行位置。

圖1 像素矩陣示意圖

4.2.2 向左（向右）最小邊距特征因子定義

將Ai灰度作為矩陣的向左或者向右的最小邊的間距分別記為li1，li2。向左的最小邊長間距為每個碎片最左端向右然后開始繼續排列的碎片空白最小像素的排列次序個數；同時向右的最小邊長間距為每個碎片最左中右端向左然后開始繼續排列的碎片空白最小像素的排列次序個數。

4.2.3 找到與頭碎片同行的剩余碎片，并給出模型和算法

找到與頭碎片Aleft1同行的剩余碎片。若碎片Aj與Aleft1屬于同一行排列，在理論上有cleft1=cj。但由于本問題利用未二值化的灰度矩陣分析，故需要考慮字符邊緣白噪聲造成的誤差。故給出一個閾值DH，若有|cleft1-cj|

4.2.4 復原同行碎片的最優化模型

現為灰度矩陣As尋找右相鄰碎片。目標為在可供匹配的所有灰度矩陣中找尋與灰度矩陣As邊緣匹配程度最大者，即邊緣誤差最小者。據劈開位置可分為兩類分別對應情況一：從兩字符間留白部分劈開；情況二從某字符中間劈開。

觀察發現部分碎片無法根據邊緣匹配程度來選擇相鄰圖片，進過試用比較，可以利用下述不等式來排除此類圖片的干擾。

表2 問題一附件2 的拼接序號表

其中Th 為可以復原一個圖片的集合文字灰度間距，集合F是由一個可以提供完整匹配的文字碎片點和全體文字灰度矩陣集合構成。Th 單位：像素。

4.2.5 復原同行碎片的圖論模型

現為灰度矩陣A1尋找右相鄰碎片。

則求問題轉化為在非負有向圖中尋找一條權值最小的哈密爾頓路徑的問題。

4.2.6 人工干預方式與時間節點

在對每行碎片利用復原同行碎片的最優化模型復原時，當兩圖片間的ε 值雖較其余的小，但圖片實際上是不連續的，此外還可能發生多組合的ε 值相同且最優，這時候也需要人工干預獲得連續的相鄰圖片組合。

通過MATLAB 程序求解得。（表3）

表3 問題二附件3 的拼接序號表

5 模型的評價

針對不同情況碎紙機的碎片類型、大小和紙片尺寸，我們在問題模型中對具體不同問題模型進行了具體的數據分析，設計了不同的模型算法應用來正確應對每種不同情況，并重新復原了碎片機紙片。對于英文模型中，中文和簡體英文的不同字符匹配特點，本文對模型充分進行挖掘，使得本模型的字符匹配度和準確度較高。在紙片模型中及其相關匹配參數對不同算法的紙片匹配度和準確率的提高影響較大，因此在對于不同碎片的紙片時，相關匹配參數都必需被重新進行設定。模型中對于缺乏針對性和碎紙片的正確語義進行分析，同時對于其他模型，應該進一步考慮減少人工干預的實際參與者數量。在碎片調整碎塊行距的計算過程中，可以直接根據碎片行的調整行距物理特征直接判斷計算行距得出調整結果，而不是先判斷調整碎塊行片段再直接評判調整行距。分組時如果考慮到了帶有碎片的部分具有文本結構特征，所以還是你可以選擇可慮用碎片聚合歸類分組方法或者使用人工智能中模式識別分類方法來叫做碎片分組用來代替用本文所用的碎片分類分組算法。