基于文字特征的碎紙片拼接復原

【摘 要】本文主要從碎紙片中文字和背景的灰度值差異出發，通過對比任意兩張圖片灰度值矩陣邊界找到相互匹配的紙片。匹配算法具體分為圖像預處理、圖像匹配和人工驗證三部分。在圖像預處理部分利用MATLAB對圖像進行數字化處理，獲取圖像的像素矩陣，進而提取出圖像邊界特征向量。在圖像匹配階段，根據拼接圖片的不同類型需要采取不同的模型進行計算。

【關鍵詞】MATLAB 灰度值矩陣 特征向量 二值化 半自動拼接技術

【中圖分類號】TP391 【文獻標識碼】A 【文章編號】1674-4810（2013）26-0060-02

一 背景介紹

破碎文件的拼接在司法物證復原、歷史文獻修復以及軍事情報獲取等領域都有著重要的應用。隨著計算機技術的發展，人們試圖開發碎紙片的自動拼接技術用以替代現有的人工拼接，以提高拼接復原效率。

二 模型的建立

1.縱切拼接模型

碎紙機在切割紙張過程中如果僅采用縱切的方法，那在拼接過程中我們只需確定左右相鄰圖片并按順序拼接即可。

用MATLAB將圖片數字化后得到的矩陣一般過于龐大，我們需要對其進行簡化、精煉，從而選取可用于排序的特征向量。

首先對矩陣的橫行方向進行簡化。由于圖片拼接最重要的影響因素集中在圖片邊界，所以我們分別提取每個數字化矩陣的第一列和最后一列作為碎紙片的左右邊界特征向量，并可根據此特征向量判斷出頁面邊界的圖片，作為排序的開始端，然后再對矩陣的縱列方向進行簡化。由于矩陣在列方向上存在明顯分行規律（文字行和行間距），占用大量不必要的存儲和計算空間，可適當簡化為以文字行（同一文字行內特征數據為一組）為單元進行后續處理。此時將邊界上的文字特征區分為兩類，一類文字完整（即未被切割開，單個文字完全屬于一張圖片），另一類是文字被切割到兩張圖片的邊界上。很明顯，僅有完整的文字只能與另一完整的文字拼接，不完整的文字只能與另一不完整文字拼接，從而可根據此原理選擇任一圖片的相鄰圖片。利用簡化算法在MATLAB中將圖片邊界的文字特征點（即非白像素點）在特征向量和中簡化為“1”，反之簡化為“0”，使得特征向量的行數簡化（文字行），減小運算難度。

簡化方法如下：（1）確定每一文字行所占邊界像素數量；（2）確定文字行在頁眉頁腳的預留像素數量，一般情況下，上下預留空間大小相同，暫且認為以上數據正確并按照此數據計算；（3）如一個像素為2016×72的圖片，不考慮頁眉和頁腳的冗余像素，按照每70個像素數據為一組的規則進行簡化，將每個特征向量簡化為28個元素，用非黑即白原則：一旦在一組的70個像素數據中出現非零數字，即定義特征數列在該位置的簡化結果為“1”；反之，70個數字都為零時定義為“0”。這樣，我們可以得到第i個圖像簡化后的特征矩陣。

定義匹配指數矩陣，其任意元素稱為圖像配合差異度，元素的值越小，表示第i個圖像的左和第j個圖像的右邊配合差異越小，即匹配度越大，為了挑選出兩個最適匹配的圖像，我們將其二值化為0，1矩陣，1表示兩個圖像可以匹配，0表示兩個圖像不能匹配。因此，只要挑選出矩陣中含元素1的行與列就可以找出可能相互匹配的兩張圖像。

在實際匹配過程中，由于已經通過圖像的特征向量找到最左邊和最右邊的圖片，采取左右同時匹配的方法：（1）從左邊第一張圖片開始向右排列；（2）從右邊第一張圖片開始向左排列。這樣可以避免排列過程中出現“死循環”，并且根據左右排列的順序同時定義還沒有排列的圖像的優先級，提高匹配的準確率。

值得注意的是：在圖像原始矩陣中存在一定概率遇到某些完整的文字，其邊界正好與圖片邊界重合，即存在“1”與“0”配對的可能性，這種情況下就會出現“漏判”，為此，我們用閾值篩選的方法減小這種可能性，但還需要一定的人工校驗。

2.分步拼接模型

第一，按紙片頂部行特征分組。如果每個圖片都與其他圖片只進行左右配合拼接必然導致效率低下，為此，考慮到裁紙機只能進行橫切和縱切，可先按每張圖片文字的首行高度特征進行分組，將每一組內的圖片分別按行拼接得到“圖片行”，具體操作步驟如下：（1）在分組前首先要進行預處理工作，根據像素確定行高；（2）對圖片進行自上而下的逐行掃描，獲取頂部行特征，此時我們定義頂部文字行的底端所處位置為其圖片特征，用其距離上邊界的像素數目m表示；（3）根據以上方法得出每張圖片的頂部行特征值m，用來表征每張圖片復原后所處位置特點，并根據m的不同取值范圍，將所有圖片分組。

第二，按行拼接（縱切拼接模型）。由于與第一問不同，每個紙片尺寸相對較小，數字化后的圖像含有的像素點也會較少（180×72的矩陣），我們可以不用簡化數據，直接提取矩陣左右兩邊的特征向量，按照第一問中的縱切拼接模型進行處理。

按照縱切拼接模型中的方法計算匹配指數矩陣，將其二值化后作為圖片拼接的依據得到每一行的碎紙片的初步拼接結果，然后進行人工校驗最終確定拼接完成的圖片。

第三，“圖片行”的縱向排列。由于行與行之間的拼接會受到行間距、段間距的影響，因此，不適宜用像素點陣匹配的方法進行拼接。由于本題中縱向圖片數量較少，因此可以采用人工干預的方法對圖片進行人工拼接。這樣不僅可以簡化拼接流程，而且人工拼接過程相比計算機拼接還有一個很大的優勢，即人可以根據文字內容的語意進行拼接，相比之下可以進一步提高拼接效率和準確率。

參考文獻

[1]歐陽鑫玉、趙楠楠、宋蕾等.圖像分割技術的發展[J].鞍山鋼鐵學院學報，2002（5）

[2]王愛民、沈蘭蓀.圖像分割研究綜述[J].測控技術，2000（5）

[3]章毓晉.圖像分割[M].北京：科學出版社，2001

〔責任編輯：范可〕