基于多約束條件的中文碎片拼接復(fù)原算法設(shè)計

摘 要：文章對縱橫切中文碎紙片的拼接復(fù)原問題進(jìn)行了分析，對碎片圖像進(jìn)行數(shù)字化處理，采用灰度相似性比較的方法，利用循環(huán)遍歷的思想匹配碎片；接著對圖像進(jìn)行二值化降噪處理，去除干擾元素，考慮到傳統(tǒng)匹配算法下存在多種匹配、錯誤匹配、重復(fù)匹配的問題，設(shè)計基于多種約束條件的中文碎片拼接算法；最后利用編程實現(xiàn)得到完整的復(fù)原圖形，該算法提高了碎片拼接復(fù)原效率和精準(zhǔn)度。

關(guān)鍵詞：碎片復(fù)原；相似性比較；多約束；匹配模型

中圖分類號：TP391.41 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-8937（2014）6-0132-02

傳統(tǒng)破碎文件的拼接復(fù)原工作需由人工完成，效率很低。隨著計算機(jī)技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復(fù)原效率。本文對2013高教社杯全國大學(xué)生數(shù)學(xué)建模競賽B題中提出的碎紙片拼接復(fù)原問題進(jìn)行研究，主要研究縱橫切中文碎紙片的拼接復(fù)原問題。

1 灰度值的相似性比較

1.1 提取邊緣灰度值

①在得到所有圖像的灰度值矩陣后，提取每組矩陣左邊緣的灰度值，根據(jù)左邊緣的灰度值的特點，判斷該圖像是否為第一張圖片，若左邊緣灰度值均為255（全白），則表示該列無文字信息，即可確定復(fù)原的第一張圖片。

②提取第一張圖像灰度值矩陣的右邊緣灰度值，并與其他圖像的左邊緣灰度值作相似性比較，確定與之匹配的圖像。

1.2 歐氏距離比較矩陣邊緣灰度值相似性

歐氏距離（Euclid Distance）也稱歐幾里得距離，是一個通常采用的距離定義，它是在維空間中兩個點之間的真實距離。在二維空間中的歐氏距離則為兩點之間的直線段距離，其表達(dá)如下：

d=■

在確定灰度值相似性時，根據(jù)歐氏距離最短的準(zhǔn)則，對于一張分辨率為m×n的數(shù)字圖像，用歐氏距離法確定出的的表達(dá)式為：

d=■

其中i=1，2……19，且i≠k，k表示要匹配的圖片序號。

1.3 循環(huán)遍歷搜索

根據(jù)歐氏距離最小原則的相似性比較，匹配出與第一張圖片相匹配的圖像，然后將該圖像作為待匹配的圖像，尋找下一張與之匹配的圖像，利用循環(huán)遍歷搜索的方法，得到匹配順序。最后按照匹配順序，繪制復(fù)原圖像。

2 算法設(shè)計與模型求解

2.1 圖像二值化降噪處理

由于每張圖片都存在著噪點這些干擾因素，所以接下來運用二值化的方法對圖片進(jìn)行降噪處理，為了改善圖像上的顯示效果，需要人為的選取適當(dāng)?shù)拈撝狄员愕玫礁侠淼亩祷瘓D像。

具體算法步驟如下

①計算機(jī)編程讀取BMP圖片灰度值；

②選取適當(dāng)?shù)拈撝担?/p>

③判斷該像素點是否為噪點。若是，則視為背景色像素，否則視為文本內(nèi)容；

④根據(jù)背景色與文本內(nèi)容確定出文本內(nèi)容邊界；

⑤重復(fù)步驟3，直到識別出清晰圖像；

⑥重置灰度；

⑦存儲BMP灰度數(shù)據(jù)。

在得到每一行首張圖像的基礎(chǔ)上，采用問題一的算法，比較灰度值矩陣的相似性，找出水平方向上與第一張圖像相匹配的碎片，然后利用循環(huán)遍歷搜索法，找出與上一張匹配的碎片。

理論上能夠搜索出每一行的所有匹配圖像，但程序運行中會出現(xiàn)多種情況而導(dǎo)致程序停止運行，不能匹配出一行的圖像。出現(xiàn)有以下情況：匹配過程中出現(xiàn)多張碎片能夠與上一張匹配、圖像的錯誤匹配、圖像的重復(fù)匹配。

2.2 圖像黑白間隔化——條件1

為了減少“出現(xiàn)多張碎片能夠與上一張匹配”和“圖像的錯誤匹配”情況發(fā)生的概率，采用將碎片圖像黑白間隔化的方法，使圖像的匹配精度更高。

具體實現(xiàn)方法如下：

①對各個圖像矩陣進(jìn)行二值化處理，使矩陣中的值只包含0和1；

②對于有72×180個像素點的圖像，從矩陣上邊緣開始搜索，判斷是否出現(xiàn)文字信息（即該行中出現(xiàn)0）；

③若出現(xiàn)文字信息，則將該行的值全部賦予0，即全黑化；

④重復(fù)的步驟，是含有文字信息的行均變成全黑；

⑤搜索出180個像素點后，圖像即呈現(xiàn)出黑白間隔化。

例如，將附件3中序號049和054碎片拼接后作黑白間隔化處理過程如下圖1所示。

特別地，對于某些碎片圖像有較大一部分空白的情況，根據(jù)我國文字分段常識，可以判斷出這些空白區(qū)域是可以有文字的，但可能由于分段原因，使得這一部分看起來沒有文字。若空白區(qū)域有文字信息，則碎片的匹配準(zhǔn)確率更高。對于這種情況，處理方法如下：

根據(jù)該碎片中已有文字的行間距計算空白區(qū)域中可有文字的位置，行間距值d為上一行文字的下邊緣與下一行文字的上邊緣的高度差，即為

d=ai-aj

則空白區(qū)域中文字可占用的位置為

s=az+d

其中，ai、aj、az分別為文字圖像的矩陣各個位置的行向量。

利用matlab編程得到該情況黑白間隔化圖像如下圖2所示：

2.3 重復(fù)匹配的限制——條件2

為了消除“圖像重復(fù)匹配”的現(xiàn)象，采用數(shù)據(jù)結(jié)構(gòu)中設(shè)置哨兵的方法，使圖像的匹配準(zhǔn)確度更高。

①在圖像匹配過程中，為了避免重復(fù)匹配，需要加入一些限制，使結(jié)果更優(yōu)化。在匹配過程中，系統(tǒng)每次從209個圖像中查找與上一張圖片相匹配的圖像，每次搜索過程中，將要匹配的圖片序號存入數(shù)組中，可看做壓入堆棧。

r（j）=n

其中j為下標(biāo)，n為圖片序號。

②另外設(shè)置一個哨兵存放每個圖片匹配其它圖片的可能值，該值越小，匹配率越高。當(dāng)一張圖片匹配完成時，該圖片便不再與其它圖片匹配，此時便可以設(shè)置哨兵。

b（r）=inf

其中r、b均為為數(shù)組。

③在以后的搜索最優(yōu)匹配圖片過程中，讀取哨兵信息，根據(jù)最優(yōu)匹配方法，所有已經(jīng)匹配過的圖片便不會再和其它圖片匹配，從而達(dá)到避免重復(fù)匹配的目的。

2.4 基于文字特征的漢字匹配——條件3

當(dāng)用matlab編程時，在算法已經(jīng)滿足上述三個條件下，仍然有部分碎片不能正確拼接，例如下列情況（如圖3所示）。

很顯然，右邊的圖像拼接結(jié)果才是正確的拼接結(jié)果，但是根據(jù)前三個條件得到的左邊的結(jié)果也是合理的，說明在算法滿足前三個條件時無法確定出唯一的碎片拼接圖像。進(jìn)一步分析其文字的特征，找出解決的辦法如下圖4所示。

①按條件1所給步驟將兩個圖像中可能會拼接的文字黑白間隔化；

②設(shè)左邊碎片中全黑部分的左邊緣到右邊框的距離為i，右邊碎片中全黑部分的右邊緣到左邊框的距離為j；

③在本文中，通過比較每個漢字在點陣的大概位置，統(tǒng)計出每個漢字所占像素點數(shù)約為40×40，于是可以通過判斷一個漢字所占像素點的大小來確定碎片匹配是否正確；

④針對圖4，若i+j≤40，則該拼接結(jié)果符合文字特征，否則不符合。但考慮到實際拼接效果小于理想拼接效果，因此需要考慮誤差情況，引入誤差值D，則拼接漢字圖像特征應(yīng)滿足i+j=40±？著（其中，誤差大小應(yīng)在10%以內(nèi)，即的取值范圍為-4≤？著≤4）；

⑤若i+j的值在誤差允許范圍內(nèi)，則說明該拼接匹配圖像是合理且正確的。

2.5 基于符號特征的符號匹配——條件4

根據(jù)條件4文字特征的識別，易想到基于符號特征的匹配模式，類似于文字特征匹配，通過符號特征識別處理下列情況，如圖5所示。

在本文中，通過比較各個符號在點陣的大概位置，為簡化算法，本文只考慮句號的情況，可以統(tǒng)計出每個句號所占像素點數(shù)約為10×10，于是可以通過判斷一個句號所占像素點的大小來確定碎片匹配是否正確。同樣設(shè)定i、j值，若i+j的值在誤差允許范圍內(nèi)，則說明該拼接匹配圖像是合理且正確的。

2.6 編程求解拼接結(jié)果

根據(jù)上述4個條件，可建立碎片圖像的橫向匹配模型，利用matlab編程實現(xiàn)其算法，可求解出11條橫向匹配圖像，并對11個圖片編號。

在確定了11個橫向匹配結(jié)果后，將11張橫向拼接圖作為一個整體來縱向拼接，即可得到完整的碎片圖像拼接復(fù)原圖。

3 結(jié) 語

本文對對碎片圖像進(jìn)行數(shù)字化處理，采用灰度相似性比較的方法確定首張圖像，在模型建立之前，對圖像做了降噪處理，使碎片圖像更加清晰。在建立中文碎片復(fù)原模型時，給出了多個約束條件，降低了匹配圖像的難度，同時減小了錯誤匹配和重復(fù)匹配的概率，提高了匹配精準(zhǔn)度。

參考文獻(xiàn)：

[1] 王鑫.文字圖像二值化及降噪處理[J].信息時代期刊，2010，（6）.

[2] 羅智中.基于文字特征的文檔碎紙片半自動拼接[J].計算機(jī)工程與應(yīng)用學(xué)報，2012，（5）.

[3] 楊小岡，曹菲，繆棟，等.基于相似度比較的圖像灰度匹配算法研究[J].系統(tǒng)工程與電子技術(shù)，2005，（5）.

[4] 賈海燕，朱良家，周宗潭，等.一種碎紙自動拼接中的形狀匹配方法[J].計算機(jī)仿真，2006，（11）.