基于多約束條件的中文碎片拼接復原算法設計

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

關鍵詞：碎片復原；相似性比較；多約束；匹配模型

中圖分類號：TP391.41 文獻標識碼：A 文章編號：1006-8937（2014）6-0132-02

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

1 灰度值的相似性比較

1.1 提取邊緣灰度值

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

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

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

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

d=■

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

d=■

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

1.3 循環遍歷搜索

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

2 算法設計與模型求解

2.1 圖像二值化降噪處理

由于每張圖片都存在著噪點這些干擾因素，所以接下來運用二值化的方法對圖片進行降噪處理，為了改善圖像上的顯示效果，需要人為的選取適當的閾值以便得到更合理的二值化圖像。

具體算法步驟如下

①計算機編程讀取BMP圖片灰度值；

②選取適當的閾值；

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

④根據背景色與文本內容確定出文本內容邊界；

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

⑥重置灰度；

⑦存儲BMP灰度數據。

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

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

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

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

具體實現方法如下：

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

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

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

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

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

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

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

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

d=ai-aj

則空白區域中文字可占用的位置為

s=az+d

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

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

2.3 重復匹配的限制——條件2

為了消除“圖像重復匹配”的現象，采用數據結構中設置哨兵的方法，使圖像的匹配準確度更高。

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

r（j）=n

其中j為下標，n為圖片序號。

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

b（r）=inf

其中r、b均為為數組。

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

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

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

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

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

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

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

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

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

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

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

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

2.6 編程求解拼接結果

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

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

3 結 語

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

參考文獻：

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

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

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

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