碎紙片的拼接復(fù)原研究

趙辰 喬振宇 李思漫

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

1 問題重述

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

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

2 模型的假設(shè)

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

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

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

3 問題的分析

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

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

4 模型的建立與求解

4.1 紙片縱切問題的求解

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

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

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

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

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

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

④對應(yīng)的圖像圖象e1 使用閾值統(tǒng)計分析方法二次閾值化，得到二次閾值化的圖像圖象e2；

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

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

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

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

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

我們先利用上述模型中的的灰度化后的模型進行二值化處理，得到相對應(yīng)的二值化模型，進行碎片的復(fù)原。然后再將拼接好的已經(jīng)被拼接的部分變?yōu)樗槠詈罂梢缘玫浇?jīng)過還原處理出來的碎片紙張，利用由每個碎片紙張組成的數(shù)據(jù)文件夾對數(shù)據(jù)模塊進行綜合模擬并用仿真進行處理。

4.2.1 空白行特征因子定義

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

圖1 像素矩陣示意圖

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

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

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

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

4.2.4 復(fù)原同行碎片的最優(yōu)化模型

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

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

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

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

4.2.5 復(fù)原同行碎片的圖論模型

現(xiàn)為灰度矩陣A1尋找右相鄰碎片。

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

4.2.6 人工干預(yù)方式與時間節(jié)點

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

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

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

5 模型的評價

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