林 川，張學新

(1.武漢大學 經(jīng)濟與管理學院，湖北 武漢 430072；2.湖北工程學院 數(shù)學與統(tǒng)計學院，湖北 孝感 432000)

破損文檔圖像的拼接與恢復是攝影測量、計算機視覺、計算機圖形學以及檔案研究和調查科學領域中一個非?；钴S的研究課題。例如，在大型圖片的掃描和跨多頁內容的打印過程中，常常會出現(xiàn)失真，不可能理想地完全重構原來的圖片；由于材料老化，人為或遭遇機器切碎，文件可能被撕掉等等。針對這些場合場合，設計原始文檔的自動或半自動重建算法能顯著減輕復雜、費時的人工操作。

圖像拼接是指從一組單獨的或重疊的子圖像重建或拼接成一個單一的、連續(xù)的圖像的技術。通常兩個片段之間的匹配僅出現(xiàn)在其相應的輪廓線上一小部分區(qū)域，所以圖像拼接過程中必須進行部分曲線的匹配。根據(jù)碎片曲線的抽樣是否均勻，匹配方法大體分為兩類。一類是基于字符串匹配的方法，其中的碎片曲線通過均勻抽樣的點表示，另類是基于特征匹配的方法，其中的碎片曲線通常由臨界點或多邊形近似表示。Peter & Adelson[1]使用多分辨率樣條技術把多個圖像拼接成一個較大的全景圖。針對圖像存在大量旋轉拍攝、縮放和透視失真問題，Yasushi Kanazawaa & Kenichi Kanatani[2]提出了分層匹配方法，該方法首先提取特征點，然后通過隨機投票和變量模板匹配方式逐步估計兩張圖像間的匹配關系。Ramesh Babu & Ravishankar[3]提出基于四叉樹技術的全自動無縫圖像拼接方法，但在實際應用中，難以用一個給定的成像源在一次拍攝中捕捉一個很大的圖像。Durga Patidar & Akshay Jain[4]使用一種互相關的重疊去除算法確定和選擇在新圖像與先前合成圖像間最相關性的點。為了快速計算相關性，他們組合快速傅立葉變換和基于梯度的圖像融合算法，消除圖像連接處的尖銳圖像強度變化，逐步將一個個圖像混合到相鄰的復合圖。Sevcenco等[5]假定圖像的重疊區(qū)域中的光度不一致，提出基于Haar小波2D集成技術的無縫拼接圖像方法。Rajesh Kumar等[6]采用無特色配準和最小混合方法，該方法適應于拼接一個在每兩個連續(xù)圖像間具有一定程度重疊的靜止圖像序列。在基于邊緣點、角點、拐點等特征，基于碎片文字行特征、表格線特征的確定與匹配方面及小波域方法的研究方面，國內也有一些成果[7-10]，它們主要針對彩色圖像及有明顯特征的碎片文檔。目前，很多圖像拼接方法需要圖像間有精確重疊和相同的場景以獲得無縫的拼接結果。當需要拼接的圖像無明顯特征時，例如，當兩個圖像之間的關系完全未知時，匹配算法很難奏效。當前，研究無特征的圖像拼接問題仍是一個挑戰(zhàn)性的課題。

對那些重疊區(qū)域較大，平移和旋轉量較小的圖像拼接問題，基于字符串匹配的方法是有效的?；谔卣鞯钠ヅ浞椒ㄍǔＴ谔幚硇〉闹丿B區(qū)域時，一般比基于字符串匹配的方法更準確，但計算密集。鑒于此，本文提出了一種面向同一頁印刷文字文件的縱切碎紙片的無特征圖像拼接算法，該方法基于圖像灰度，在矩陣行和相關度最大準則下，先選取每個碎片右列的灰度點集，然后分析每點編碼空間鄰居的碎片結構(即左列)，通過與其他碎片的局部特征進行相關度匹配，將破碎紙片成功復原。

1 基本原理

在掃描圖像或打印文檔時，相鄰圖像或文檔之間存在部分重疊，因此，在進行相似性匹配后，可以確定出相鄰碎片間的重疊位置，根據(jù)相對位置建立相鄰圖像或文檔對，實現(xiàn)兩個及多個圖像的拼接。理論上，由于存在成對相關的補償數(shù)據(jù)，任何相鄰圖像對可以完美地被拼接在一起。由于失真的出現(xiàn)，使得并非所有成對的相對位置可以同時實現(xiàn)拼接，需要根據(jù)某種相似度準則建立優(yōu)化模型。

圖像拼接的基本原則是整體對齊、局部調整、自動選擇、圖像融合、手動曝光補償。通常，圖像拼接與破損文檔的恢復遵循如圖1所示的步驟。

圖1 圖像拼接流程

其中，圖像配準和圖像合并是圖像拼接中兩個主要組成部分。圖像配準的目的是找到需要拼接的圖像之間的幾何關系，而圖像合并是生成一個完整的組合圖像。

2 縱切碎紙片拼接算法

2.1 問題描述

將文檔掃描圖像沿縱向切分為19條碎片，得到來自同一頁紙的縱切碎片數(shù)據(jù)集。部分中、英文碎片圖像樣例見圖2?？v切碎紙片拼接的主要任務是試對給定的來自同一頁印刷文字文件的碎紙機破碎紙片(僅縱切)，建立碎紙片拼接復原模型和算法。

圖2 部分縱切碎片圖像

2.2 模型假設

本文設計的算法基于如下三個方面的假設：

(1)每個碎紙片上字的大小、粗細相同；

(2)每個碎紙片上每一行的行間距相同；

(3)每個碎紙片內容沒有缺損。

2.3 拼接模型

首先讀出圖2中19張碎紙片圖像的像素獲得19個矩陣。然后把各個矩陣的第一列依次讀出，形成First矩陣；把各個矩陣的最后一列依次讀出，形成Last矩陣。最后把像素小于128的替換為0(表示黑字)，將像素大于128的替換為1(表示空白)，將First矩陣、Last矩陣轉變?yōu)槎M制的矩陣BF=(bfij)19×180，BL=(blij)19×180。

建立模型。將BF矩陣的每一列與BL矩陣的每一列進行匹配，如果兩個矩陣相同行的像素同時為1，則該行匹配，以行匹配成功總數(shù)最大為目標函數(shù)建立優(yōu)化模型。即

maxz=∑xijt，i=1，2，…，19，j=1，2，…，19，t=1，2，…，1 980

約束條件為：

1)比較BF的第i列與BL的第j列的相同的第t行像素值是否同時為1， 即

yit+zjt≥2×xijt，i=1，2，…，19，j=1，2，…，19，t=1，2，…，1 980

(1)

2)BL的每一列與BF的固定列的每一行配對成功的次數(shù)如果小于1 980，則該張對應的碎紙片為最左邊的，即

(2)

3)BF的每一列與BL的固定列的每一行配對成功的次數(shù)如果小于1 980，則該張對應的碎紙片為最右邊的，即

(3)

綜上，最佳的配對模型為：

maxz=∑xijt，

(4)

模型物理含義。如果把矩陣BF與矩陣BL的每一列視為19維空間上的一個點，則maxz=∑xijt本質上是最小化歐式空間上的兩點間距離，等同于最大化兩向量的夾角的余弦值。

2.4 算法實現(xiàn)

算法1是本文提出方法的總結。

算法1:縱切碎紙片拼接算法輸入:碎紙片數(shù)據(jù)像素矩陣。第1步 :邊界檢測與裁剪圖像。讀取碎紙片數(shù)據(jù)像素矩陣,進行邊界檢測,裁剪各像素矩陣的第一列和最后一列,將剪裁出的所有第一列依次拼接到First矩陣中,剪裁出的所有最后一列依次拼接到Last矩陣中并分別保存;第2步 :圖像二值化。把像素小于128的替換為0,表示黑字;將像素大于128的替換為1,表示空白,將所求的矩陣轉變?yōu)槎M制的矩陣,求得 矩陣和 矩陣分別保存。第3步 :碎紙片配對。比較 矩陣的每一列與 矩陣的每一列,如果相同行的像素同時為1,則該認為行匹配成功。以行匹配成功總數(shù)為目標函數(shù),極大化之。輸出:碎片序號的復原順序號。

3 實驗結果與分析

對模型(4)使用Matlab編寫拼接程序，排列最佳方案的矩陣并將碎紙片復原，紙片順序復原結果見表1和表2。中文文檔圖像碎片拼接結果見圖3，英文文檔圖像碎片拼接結果見圖4。從圖3和圖4的拼接結果可以看出，本文算法能有效實現(xiàn)縱切文檔圖像的無縫拼接，拼接后的圖像內容完整，無明顯的拼接痕跡。

表1 中文文檔圖像碎片序號復原順序

表2 英文文檔圖像碎片序號復原順序

圖3中文文檔圖像碎片拼接結果

圖4英文文檔圖像碎片拼接結果

4 結論

本文提出了一種基于灰度相關匹配的縱切碎紙片拼接方法，該方法以相鄰匹配的相容性作為相似性度量，以行匹配成功總數(shù)最大作為全局優(yōu)化的準則函數(shù)，進行優(yōu)化求解。在拼接過程中，首先兩兩配對，并將所有匹配的列序號排序，然后進行人工干預，求得最佳方案，最后通過消除匹配的模糊性以恢復原始文檔。本文算法的優(yōu)點在于不需復雜的圖像預處理過程，適合于圖像畸變小、切割規(guī)則的碎片拼接。

[參 考 文 獻]

[1] Burt P J，Adelson E H.A multiresolution spline with application to image mosaics [J].ACM Transactions on Graphics，1983，2(4): 217-236.

[2] Kanazawa Y.Kanatani K.Image mosaicing by stratified matching[J].Image and Vision Computing，2004，22(2): 93-03.

[3] Ramesh B D R，Ravishankar M.Automatic seamless image mosaicing: an approach based on quad-tree technique//Proceedings of the World Congress on Engineering，2010: 687-691.

[4] Patidar M D，Jain M A .Automatic Image Mosaicing: An approach based on FFT[J].International Journal of Scientific Engineering and Technology，2011，1(1): 1-4.

[5] Ioana S S，Peter J H，Pan Agathoklis.Seamless stitching of images based on a Haar wavelet 2D integration method//Proceedings of the 17th International Conference on Digital Signal Processing，2011:1-6.

[6] Kumar C R，Nikhita N，Roy S，Murthy V V S.An image stitching system using featureless registration and minimal blending[J].International Journal of Engineering Research and Applications，2012，2(2): 1215-1222.

[7] 劉金根,吳志鵬,劉上乾，等.一種基于特征區(qū)域分割的圖像拼接算法[J].西安電子科技大學學報：自然科學版，2002，29(6): 768-772.

[8] 張欣,卜彥龍,朱良家，等.物證復原系統(tǒng)中的碎紙輪廓提取技術研究[J].計算機仿真，2006，23(11): 184-187.

[9] 羅智中.基于文字特征的文檔碎紙片半自動拼接[J].計算機工程與應用，2012，48(5): 207-210.

[10] 李波.一種基于小波和區(qū)域的圖像拼接方法[J].電子科技，2005(4): 49-52.