基于灰度矩陣的中文碎紙片的拼接復(fù)原算法

王欣潔

摘要：主要對(duì)碎紙片的拼接復(fù)原問題進(jìn)行分析，分別對(duì)僅縱切和橫縱切兩種切割方式建立了模型進(jìn)行求解，主要思想是對(duì)碎片的灰度值矩陣進(jìn)行處理，利用文字所處的位置信息、空格的分布情況、碎片的邊界信息（文字的鏈接情況）等信息，對(duì)所給的碎紙片進(jìn)行拼接復(fù)原。對(duì)2013年“高教社杯”大學(xué)生數(shù)學(xué)建模競賽B題附件中的中文碎片進(jìn)行拼接，拼接效率高，算法可行。

關(guān)鍵詞：灰度值矩陣； 差異度量； 貪心算法； 相容性； 邊界特征

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-2163（2013）06-0095-04

0問題提出

破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。為了提高拼接復(fù)原效率，人們試圖利用計(jì)算機(jī)，實(shí)現(xiàn)碎紙片的自動(dòng)拼接。本文對(duì)2013高教社杯全國大學(xué)生數(shù)學(xué)建模競賽B題中提出的碎紙片拼接復(fù)原問題進(jìn)行研究，主要研究其中中文碎片的拼接復(fù)原。

1模型假設(shè)和符號(hào)說明

研究前，需要做出如下假設(shè)：假設(shè)所給碎片均無噪聲污染；各碎片之間互有關(guān)聯(lián)；并且只考慮打印稿，而不涉及手寫稿；同時(shí)也要假設(shè)文件中的文字行間距確定；沒有相同的兩個(gè)碎片；以及附件所給碎片的原文件頁邊距不為零。

本文中用到的符號(hào)如下：

Ai：第i個(gè)碎片圖像的灰度值矩陣；

aikm：第i個(gè)碎片圖像的灰度值矩陣中第k行m列元素；

d（Ai，Aj）：兩矩陣的列差異度；

N1：附件1、2碎片個(gè)數(shù)；

N2 ：附件3、4碎片個(gè)數(shù)；

F：復(fù)原序列；

d（r）（Ai，Aj）：兩矩陣的行差異度；

S1R：排在左側(cè)的第R張碎片；

GR：第R個(gè)相容的碎片集合

2問題分析

2.1僅縱切問題的分析

對(duì)于僅縱切的情形，各碎片的邊界特征信息（文字的鏈接情況）較為豐富，故可以利用邊界特征進(jìn)行拼接復(fù)原。首先根據(jù)左側(cè)的第一張碎片通常存在著左邊的頁邊距的特點(diǎn)，即其灰度值矩陣中左邊幾列的元素均為255，從而可以找出排在左邊的第一張碎片。對(duì)于僅縱切的規(guī)則圖形的拼接問題，只需考慮橫向連接，由于縱切產(chǎn)生的邊界特征信息較多，在此引入相鄰的兩幅碎片的邊界差異度量[1]。

定義1：設(shè)Ai和Aj均為r×l矩陣，aikm為矩陣Ai中第k行m列元素，ajkn為矩陣Aj中第k行n列元素，稱

dm，n（Ai，Aj）=∑rk=1|aikm-ajkn|

為矩陣Ai第m列與Aj的第n列的差異度量，其中1≤k≤r，1≤m，n≤l。特殊地，用d（Ai，Aj）表示矩陣Ai最后一列與Aj的第1列的差異度量。

2.2橫縱切問題的分析

對(duì)于縱橫切的情形，在增加橫切之后，兩圖片邊界處共同信息量大大減少，故需要更進(jìn)一步地挖掘可用信息。漢字是方塊字，每個(gè)字所占的位置基本都是一致的，均可以填在一個(gè)“田”字格中。

首先找出排在左側(cè)的11張圖片，可以判定兩碎片中漢字所在位置位于同一行的圖片應(yīng)該拼接在同一行中，將這樣的碎片定義為相容的碎片，下面給出碎片相容性的定義。

定義2：如果兩幅碎片上的漢字所在行的位置不矛盾時(shí)稱為兩幅碎片是相容的。

例如：圖1中所給的七幅圖片均為相容的，圖中黑色部分為漢字所在的位置，其中漢字也可以是半個(gè)字。

在相容碎片的集合中，按照上小節(jié)中問題一的方法，找出列差異度量最小的排列，即可將每一類相容碎片進(jìn)行橫向拼接復(fù)原，然后還需要對(duì)碎片進(jìn)行縱向拼接，如果橫切時(shí)是從字中間切開的，則需要考慮碎片的灰度值矩陣的行差異度量。下面定義兩矩陣的行差異度量。[2]

定義3：設(shè)Ai和Aj均為r×l矩陣，aimk為矩陣Ai中第m行k列元素，ajnk為矩陣Aj中第n行k列元素，稱

d（r）m，n（Ai，Aj）=∑lk=1|aimk-ajnk|（1）

為矩陣Ai第m行與Aj的第n行的差異度量，其中1≤k≤r，1≤m，n≤l。特殊地，用d（r）（Ai，Aj）表示矩陣Ai最后一行與Aj的第1行的差異度量。

如果橫切時(shí)是從空行之間切開的，則上下兩個(gè)碎片的差異度量為0，則可能會(huì)出現(xiàn)拼接錯(cuò)誤，這時(shí)可以在假設(shè)每行的行距相等的基礎(chǔ)上，若計(jì)算得到一張碎片下邊界的空白處在其相應(yīng)的灰度值矩陣中所占的行數(shù)和另一張碎片上邊界的空白處在其相應(yīng)的灰度值矩陣中所占的行數(shù)之和恰好等于文字間因行距所形成的的空白處而構(gòu)成的灰度值矩陣行數(shù)，則這兩張碎片即為上下拼接[3]。

3模型建立與求解

3.1僅縱切的模型建立與求解

如果兩個(gè)碎片的列差異度越小，說明這兩塊碎片拼接在一起的可能性就越大，建立基于矩陣列邊緣差異度的碎片復(fù)原模型，目標(biāo)函數(shù)為尋找所有碎片全排列中邊緣的列差異度和的最小值， 其公式為：

min f=∑N1-1i=1d（Aki，Aki+1）（2）

式中，k1，…，ki，ki+1，…，kN1為1，…，i，i+1，…，N1的全排列，由最小值對(duì)應(yīng)的排列可以得到拼接序列[4]。

文中利用貪心算法[5]求解上述問題，具體算法過程如下：

算法1：

（1）將附件碎片文件用imread命令導(dǎo)入MATLAB中，生成N1個(gè)r×l的灰度值矩陣Ai，存儲(chǔ)于1×N1的元胞cell中，cell={datal，…，datai}，每個(gè)Ai中的元素aikm存儲(chǔ)在元胞內(nèi)的數(shù)組datai中；

（2）對(duì)每個(gè)Ai的左側(cè)的4列灰度值進(jìn)行按列求和，找出最大值的碎片，即為排在最左側(cè)的第一張碎片，記錄其灰度值矩陣為A1，同時(shí)記錄位置并保存于向量sorts中[6]；

（3）根據(jù)定義1，在其余Ai中找出與A1的列差異度量最大的灰度值矩陣，記為A2，則A2應(yīng)與A1拼接；并把矩陣A1與A2按行連接，存入數(shù)組dataall中，再將其位置添加入向量sorts中；

（4）從A2出發(fā)重復(fù)步驟（3），依次找出A3，A4，…，AN1；

（5）輸出F即為碎片復(fù)原順序；

（6）將灰度值矩陣（dataall）轉(zhuǎn)化為復(fù)原圖片，并輸出到當(dāng)前MATLAB工作目錄中。

利用MATLAB7.0對(duì)算法1編程求解[4，6-8]，其中N1=19，r=1 980，l=72，i，j=1，2，… 19，m=72，n=1，經(jīng)調(diào)試可知，最左邊第一張碎片灰度值矩陣中左邊8列元素均為255，將2013高教社杯全國大學(xué)生數(shù)學(xué)建模競賽B題中附件1中的圖片存入MATLAB當(dāng)前工作目錄，即可輸出碎片復(fù)原順序如表1所示。因篇幅所限，復(fù)原圖片本文并未列出。

表1附件1碎片復(fù)原順序

3.2橫縱切模型的建立與求解

由問題分析可知，對(duì)于縱橫切片的情形，建立基于相容性的碎片復(fù)原模型[9]，目標(biāo)函數(shù)為尋找所有碎片全排列中邊緣的列差異度和的最小值[2，9]，如同式（2），利用貪心算法求解上述問題，具體算法過程如下：

算法2：

（1）將附件碎片文件導(dǎo)入MATLAB中，生成N2個(gè)r×l的灰度值矩陣Ai，存儲(chǔ)于1×N2的元胞中；

（2）在N2個(gè)灰度值矩陣Ai中尋找左側(cè)幾列灰度值均為255的碎片，即為排在左側(cè)的R張碎片：S11，S12，…，S1R；

（3）對(duì)S11，尋找與之相容的碎片，放入一個(gè)集合G1中；

（4）重復(fù)步驟（3），依次尋找分別與S12，…， S1R相容的碎片，也按序放入集合G2，…，GR中；

（5）在G1中，利用算法1的步驟（3），從S11出發(fā)，尋找差異度量最小的排列，并保存此排列的灰度值矩陣，且輸出；

（6）從G2出發(fā)到GR，重復(fù)步驟（5）；

（7）按照定義3計(jì)算G1復(fù)原圖與G2到GR復(fù)原圖的灰度值矩陣的行差異度量，同時(shí)尋找行差異度量最小的排列，并保存此排列的灰度值矩陣；

（8）將灰度值矩陣轉(zhuǎn)化為復(fù)原圖片，并輸出到當(dāng)前MATLAB工作目錄中。

利用MATLAB7.0對(duì)算法2編寫程序求解，其中R=11，L=19，N2=209，r=180，l=72，i，j=1，2，…，R，m=180，n=1，將2013高教社杯全國大學(xué)生數(shù)學(xué)建模競賽B題中附件3中的圖片存入MATLAB當(dāng)前工作目錄，運(yùn)行程序，首先輸出排在左側(cè)的11張碎片序號(hào)，如表3所示。表3附件3中排在左側(cè)的11張碎片序號(hào)

4模型評(píng)價(jià)

4.1模型的優(yōu)點(diǎn)

在模型一中將各碎片數(shù)字化產(chǎn)生相應(yīng)的灰度值矩陣，作為處理對(duì)象，定義兩矩陣列差異度量，作為衡量拼接是否合理的標(biāo)準(zhǔn)，目標(biāo)函數(shù)簡單明了，便于理解，且同時(shí)具有較高的準(zhǔn)確度；在模型二中巧妙運(yùn)用漢字文字及排版特征，定義了相容集合和兩矩陣行差異度量，作為衡量拼接是否合理的標(biāo)準(zhǔn)，利用文字的位置、空格位置、文字在邊緣處的鏈接情況進(jìn)行還原。此模型可以有效解決縱橫切的大量碎片拼接復(fù)原的實(shí)際問題；

4.2模型的缺點(diǎn)

在模型一中的灰度值矩陣中，只考慮了邊緣列向量或行向量，卻未有效利用碎片數(shù)據(jù)；在模型二中只考慮打印版的漢字文件，不能較為有效地處理手寫體文件和英文文件碎片拼接問題。

這些模型中只用邊界的空格信息、文字的位置、文字在邊緣處的鏈接情況。另外，由于不同字體的結(jié)構(gòu)不同，所以此算法只適用于中文碎片的拼接復(fù)原，對(duì)于更加復(fù)雜的還原問題，則需要考慮更多的信息。

參考文獻(xiàn)：

[1]沈庭芝，方子文.數(shù)字圖像處理及模式識(shí)別[M].北京：北京理工大學(xué)出版社，1998-06

[2]羅智中. 基于文字特征的文檔碎紙片半自動(dòng)拼接[J].計(jì)算機(jī)工程與應(yīng)用，2012（5）：207-210.

[3]何鵬飛， 周宗潭，胡德文. 基于蟻群優(yōu)化算法的碎紙拼接[J].計(jì)算機(jī)工程與科學(xué)，2011（7）：67-73.

[4]蘇金鵬，阮沈勇.MATLAB實(shí)用教程[M].北京：電子工業(yè)出版社 ，2005-07

[5]姜啟源，謝金星，葉俊. 數(shù)學(xué)模型（第四版）[M]. 北京：高等教育出版社，2011-01.

[6]于殿泓. 圖像檢測與處理技術(shù)[M].西安：西安電子科技大學(xué)出版，2006-12.

[7]楊淑瑩，李蘭友. 圖像模式識(shí)別—VC++技術(shù)實(shí)現(xiàn)[M].北京：清華大學(xué)出版社，2005-07.

[8]任玉杰. 數(shù)值分析及其MATLAB實(shí)現(xiàn)[M].北京：高等教育出版社，2007-03.

[9]賈海燕.碎紙自動(dòng)拼接關(guān)鍵技術(shù)研究[D].國防科技大學(xué)碩士論文，2005-11.