平安 左帥 平靜

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

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

一、背景分析

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

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

二、模型假設(shè)及說明

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

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

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

三、模型的建立與求解

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

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

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

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

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

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

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

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

3.1.3模型的求解

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

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

3.2.1圖像的處理

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

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

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

Step2：聚類模型的建立

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

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

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

Step3 對碎紙片進(jìn)行橫向拼接

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

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

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

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

f（n（k），n（k+1））意為第 k 張碎紙片與第 k+1 張碎紙片的邊緣對應(yīng)灰度值的離差和。當(dāng) F（N）取得最小值時(shí)，此時(shí)的復(fù)原順序?yàn)樽罴雅判颉?/p>

（3）接受準(zhǔn)則

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

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

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

（4）結(jié)束條件

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

四、模型分析與評價(jià)

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

參考文獻(xiàn)

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

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