碎紙片的拼接復原

平安 左帥 平靜

摘要：本文利用各碎紙片的灰度值矩陣相似程度進行匹配，解決了同頁縱切、同頁橫縱切不同情況的碎紙片拼接復原問題。

關鍵詞：灰度值相似度模型;聚類;分區(qū)塊匹配;模擬退火

一、背景分析

碎紙片的拼接主要依據(jù)各紙片邊緣的灰度值，邊緣灰度值相似程度高的紙片其拼接成功的可能性就較大。分別針對同頁縱切和同頁橫縱切不同情況的碎紙片進行分析復原。

要解決同頁單面縱切的碎紙片拼接復原問題。建立碎紙片拼接復原模型和算法，對中、英文各一頁文件的碎紙片數(shù)據(jù)進行處理，得到灰度值矩陣，利用文件邊緣的特性確定其最左邊的碎紙片，根據(jù)篩選出的最左邊碎紙片將其他碎紙片進行聚類處理。最終找到邊界灰度值相似程度較高的碎紙片進行匹配處理，完成拼接復原。要解決同頁單面橫縱切的碎紙片拼接復原問題，碎紙片數(shù)量的增多為該問題加大了難度。可將屬于同一橫向條狀紙片的碎紙片進行聚類，模擬退火算法使碎紙片拼接復原成橫向條狀紙片，解決縱切產(chǎn)生的橫向無序性問題。再對橫向條狀紙片進行縱向排序，從而解決碎片由于橫切產(chǎn)生的縱向無序性問題。必要時，引入人工干預以幫助拼接順利進行，提高拼接的效率和正確率。

二、模型假設及說明

1.假設碎紙片的完整性良好，即：每個附件中的碎紙片都來自同一文件，且同一文件的所有碎紙片都存在與附件中。

2.假設每個碎紙片的邊緣光滑，切割時無毛邊產(chǎn)生。

3.假設切割產(chǎn)生的碎紙片尺寸完全相等，即每個碎紙片的灰度值矩陣形式相同。

三、模型的建立與求解

3.1單面縱切碎紙片模型的建立與求解

3.1.1圖像的數(shù)據(jù)處理

對碎紙片進行數(shù)據(jù)處理，將碎紙片的圖像分別導入到 matlab 中，依次得到每個圖像的灰度值矩陣，例如第2張碎紙片的灰度值矩陣C1：

其中ai，j（n）意為編號為n的碎紙片的圖形灰度值矩陣中第i行第j列的灰度值，滿足{a|a∈[0，255]且a∈Z}。

3.1.2建立圖像邊界的灰度值相似度模型

對于單面縱切的碎紙片復原問題，利用可拼接的兩碎紙片相鄰邊界灰度值相似的原理，從首先確定的文件左邊緣的碎紙片開始，其他碎紙片左邊界的灰度值逐個與其右邊界灰度值對比，找到最相似的碎紙片進行匹配，以此類推，使得破碎文件從左到右依次拼接復原。

首先確定求解灰度值相似的基本函數(shù)：

f（b，c）即為編號為 b 的碎紙片最右一列與編號為 c 的碎紙片最左一列對應灰度值的離差和，其中b，c=0，1，...，18且b≠c。f（b，c）min表明此碎紙片b與碎紙片c邊界匹配程度最高，其拼接成功的可能性最大，因此選擇將碎紙片b與碎紙片c進行拼接。

3.1.3模型的求解

為避免在匹配過程中文件最左邊的碎紙片與最右邊的碎紙片誤接，所以首先進行位于原文件最左側(cè)碎紙片的搜索。通過分析存儲的碎紙片灰度值矩陣信息，搜索碎紙片灰度值矩陣左列灰度值元素全為 255 的碎紙片，在圖像中表現(xiàn)為左側(cè)全為白色，由此位于原中文文件的最左側(cè)的碎紙片，再分別用附件中的其他碎紙片與已確定的左邊界碎紙片進行灰度值匹配，找到使得灰度值相似度函數(shù)f（b，c）最小時的碎紙片 c 進行拼接。以此類推，實現(xiàn)碎紙片由左向右依次拼接復原。

3.2縱、橫切碎紙片文件復原的模型建立與求解

3.2.1圖像的處理

讀取每個碎紙片的灰度信息，得到對應的灰度值矩陣Cn，例如第一張碎紙片的灰度值矩陣記為C1;將得到的灰度值矩陣簡化處理，得到 0-1 黑白矩陣Bn;在簡化的 0-1 矩陣中，我們將灰度值矩陣中非白的像素行存儲為 0，否則存儲為1。

3.2.2中文碎紙片橫向拼接的模型建立與求解

Step1：利用前文的模型和算法，找到文件中的最有可能位于原文件左側(cè)的碎紙片和最有可能位于原文件右側(cè)的碎紙片。引入第一次人工干預，將明顯不符合要求的碎紙片淘汰，確定位于原文件兩側(cè)的碎紙片。

Step2：聚類模型的建立

0-1 矩陣的黑白分塊匹配法，步驟如下，對左側(cè)邊緣的圖片的 0-1 矩陣進行分析，每次 0-1 變換的交界處即為斷點，n 個斷點將紙塊分成了 n+1 個區(qū)域。

區(qū)域匹配：首先將奇數(shù)區(qū)域所在行與其他圖片對應行做差，判斷差的絕對值之和是否小于所定模糊像素長度。若奇數(shù)區(qū)域全部符合條件，則將被匹配碎紙片與此邊緣碎紙片歸為一類;否則，對偶數(shù)區(qū)域進行同樣匹配，若偶數(shù)區(qū)域全部匹配成功，則歸為一類，否則不歸為一類。對處理得到的 0-1 矩陣進行聚類分析以減少計算量提高拼接效率。

考慮到碎紙片每行文字的高度不盡相同，反映在圖像上就是兩碎紙片雖相鄰，但其0-1 矩陣中連續(xù)為 0 或 1 的行數(shù)并非完全相同。所以我們將黑色和白色的邊界模糊化，并分析得出，當模糊長度設定為 4 時，每類碎紙片的個數(shù)都接近 19，即聚類效果最好。

Step3 對碎紙片進行橫向拼接

記每一類碎紙片的復原結果為 N，其中n（k）是復原結果中由左至右的第 k 張碎紙片。則有：

N=（n（1），n（2），...，n（19））.

解空間M可記為M={N（1），N（2），...，N（m）}，其中，N（m）記為碎紙片的第m種拼接順序。

（2）目標函數(shù)：

f（n（k），n（k+1））意為第 k 張碎紙片與第 k+1 張碎紙片的邊緣對應灰度值的離差和。當 F（N）取得最小值時，此時的復原順序為最佳排序。

（3）接受準則

假設碎紙片在拼接順序為 p 時的匹配程度為F（Np ） ，那么拼接順序由 p 到 q時就遵循以下規(guī)律：

若F（Np）≤F（Nq），接受拼接順序q;則接受概率：e

確定Tmax =120，Tmin =1;取降溫系數(shù) c=0.9。

（4）結束條件

選定的終止溫度Tmin=1，判斷退火過程是否結束。若T

四、模型分析與評價

通過對結果進行分析，可知本文的模型精確度較高，并對某些特殊情況進行了處理，可以有效合理的解決規(guī)則切割的碎紙片拼接復原問題。但該模型也存在缺點，如特殊結構的碎紙片數(shù)量過多時，在采用分區(qū)塊匹配進行聚類時，淘汰的碎紙片數(shù)量就會增多，這時引入人工干預拼接的碎紙片數(shù)量也加大，一定程度上降低了拼接復原的效率。在邊界灰度值相似度模型中，我們運用相鄰圖片灰度值相似的原理，當兩碎紙片相鄰邊界對應的元素越小越有可能拼接成功，此模型計算簡單，運算時間復雜度也不高。但也有可能出現(xiàn)錯誤拼接的情況，當處于碎紙片左邊緣的文字由于切割產(chǎn)生的斷線過于細小，這時當某一碎紙片右邊緣全白時與之匹配的f（b，c）值也很小，這時這兩張碎紙片就會錯誤拼接。

參考文獻

[1]司守奎，孫璽菁，數(shù)學建模算法與應用[M]，北京：國防工業(yè)出版社，2011

[2]卓金武，Matlab在數(shù)學建模中的應用[M]，北京：國防工業(yè)出版社，2011