一種文檔圖像檢索算法設(shè)計和實現(xiàn)

摘  要： 介紹了一種基于版面結(jié)構(gòu)距離的文檔圖像檢索算法，使用版面特征作為文檔圖像的特征檢索圖像。先將文檔圖像進(jìn)行梯度和最大梯度差（MGD）計算，然后使用MGD值作為一個窗口對文本區(qū)域進(jìn)行融合，將文檔圖像以行線的形式標(biāo)示出來。同時給出了檢索的匹配方法，并對匹配方法進(jìn)行了實驗。實驗結(jié)果表明，該檢索方法具有較高的查準(zhǔn)率，具有很好的抗傾斜和抗縮放效果。

　　文檔圖像一般意為含有文字信息的圖像，目前大多數(shù)信息是以數(shù)字化形式存在的，并以文檔的形式組織起來存放在數(shù)據(jù)庫中。在這樣的數(shù)據(jù)庫中查找有關(guān)資料其技術(shù)是關(guān)鍵。常見的文檔圖像檢索方法是基于內(nèi)容的文檔圖像檢索（CBIR）。它是利用圖像本身的信息，通常以圖像特征（顏色、紋理、形狀、結(jié)構(gòu)布局和語義特征等）的相似性為檢索依據(jù)，根據(jù)每幅圖像都有的可比較特征進(jìn)行檢索。

　　近年來，數(shù)字化文檔被廣泛應(yīng)用于辦公自動化、數(shù)字化圖書館、工業(yè)自動化等領(lǐng)域。隨著科技的發(fā)展，傳統(tǒng)掃描儀體積大、效率低、攜帶不方便等不足之處日益突出，而數(shù)字照相機(jī)體積小、價位低，可以很容易地攜帶并結(jié)合到手機(jī)、 手提電腦以及各種網(wǎng)絡(luò)設(shè)備中去，它還可以遠(yuǎn)距離地對背景文字及脆弱的珍貴文檔拍照， 更適用于無約束環(huán)境下的數(shù)字化操作。因此，將數(shù)字照相機(jī)引入文檔圖像分析已經(jīng)引起越來越多人的關(guān)注。

　　Newman的調(diào)查表明，從報紙上提取段落時，基于PC攝像頭的OCR操作比基于掃描儀的OCR操作效率高得多；Fisher等調(diào)查了在戰(zhàn)場上用數(shù)字?jǐn)z像機(jī)替換士兵攜帶sheet-fed掃描儀的可能性。經(jīng)證實，數(shù)字?jǐn)z像機(jī)能夠以200dpi拍攝整張A4文檔紙，已經(jīng)達(dá)到OCR所要求的分辨率。

　　BEUSEKOM J V.等人提出了一種基于版面分析的文檔圖像檢索的距離度量方法，將文本區(qū)域分為不同的矩形塊，然后找到塊的中心點，利用角點的曼哈頓距離來計算塊之間的距離，再利用三種不同的方法進(jìn)行匹配[1]；WONG K Y.使用游程平滑算法進(jìn)行版面信息提取的方法[2]；BREUEL T M.提出了使用Whitespace算法來提取版面信息[3]。

　　圖像匹配是指通過一定的匹配算法在兩幅或多幅圖像之間識別同名點，如二維圖像匹配中通過比較目標(biāo)區(qū)和搜索區(qū)中相同大小的窗口的相關(guān)系數(shù)，取搜索區(qū)中相關(guān)系數(shù)最大所對應(yīng)的窗口中心點作為同名點。其實質(zhì)是在基元相似性的條件下，運用匹配準(zhǔn)則的最佳搜索問題。

　　灰度匹配的基本思想：以統(tǒng)計的觀點將圖像看成是二維信號，采用統(tǒng)計相關(guān)的方法尋找信號間的相關(guān)匹配。利用兩個信號的相關(guān)函數(shù)，評價它們的相似性以確定同名點。

　　灰度匹配通過利用某種相似性度量，如相關(guān)函數(shù)、協(xié)方差函數(shù)、差平方和、差絕對值和等測度極值，判定兩幅圖像中的對應(yīng)關(guān)系。

　　最經(jīng)典的灰度匹配法是歸一化的灰度匹配 法，其基本原理是逐像素的把一個以一定大小的實時圖像窗口的灰度矩陣，與參考圖像的所有可能的窗口灰度陣列，按某種相似性度量方法進(jìn)行搜索比較的匹配方法，從理論上說就是采用圖像相關(guān)技術(shù)。

　　利用灰度信息匹配方法的主要缺陷是計算量太大，因為使用場合一般都有一定的速度要求，所以這些方法很少被使用。現(xiàn)在已經(jīng)提出了一些相關(guān)的快速算法，如幅度排序相關(guān)算法，F(xiàn)FT相關(guān)算法和分層搜索的序列判斷算法等。

　　1 相關(guān)工作

　　1.1 文本行標(biāo)記

　　將得到的文檔圖像進(jìn)行預(yù)處理，具體的處理方法是：使用文本行標(biāo)記算法實現(xiàn)文字區(qū)域的行定位。本文使用[-1，0，1]對圖像進(jìn)行處理計算其梯度，然后計算其MGD。MGD計算方法如下：在一個大小為n的窗口內(nèi)，用它的最大梯度差來進(jìn)行填充，以達(dá)到文本融合的目的。因為英文和中文的字符寬度不同，根據(jù)具體的情況選擇n，大于字符間距即可。將計算出來的梯度求它的最大值和最小值，然后相減，即為最大梯度差。將得到的MGD圖像使用最大類間方差方法[5]（OTSU）求出閾值得到二值圖像[2]。圖1為使用上述方法對行塊進(jìn)行標(biāo)記的圖像。

　　1.2 消除階躍跳變

　　對于手寫體或者英文的文檔，會出現(xiàn)字符高低不一、筆畫不連續(xù)等情況。線特征產(chǎn)生的斷點可采用形態(tài)學(xué)方法、凸凹點處理和噪聲處理三種基本策略提高直線的連續(xù)性，然后采用階梯插補(bǔ)算法來消除階躍跳變，算法的復(fù)雜度相對較低。

　　在像素級上進(jìn)行處理是：當(dāng)出現(xiàn)行階躍跳變的情況時，使用如圖2的模板來對其進(jìn)行填充。因為文檔圖像的行塊在4個方向上都有可能出現(xiàn)這種階躍，所以采用一個3×3的模板，以位置5為中心點，如圖3所示，4種情況都包含其中：1和4為非文本像素，對4進(jìn)行填充；3和6為非文本像素，對6進(jìn)行填充；4和7為非文本像素，對4進(jìn)行填充；6和9為非文本像素，對6進(jìn)行填充。如果填充之后依然有符合結(jié)構(gòu)的像素，則繼續(xù)填充，即把需要填充的區(qū)域都填充完整。填充前后的圖像如圖4所示。

[!--empirenews.page--]

　　1.3 行線標(biāo)記

　　通過對得到的二值圖像的行跳變的填補(bǔ)，文本行的變化相對比較平滑，這有利于行線的標(biāo)記。本方法取每個文本行的下邊緣來作為行線。因為背景區(qū)域為黑色，文字區(qū)域為白色，所以對文檔圖像進(jìn)行掃描，從黑色區(qū)域進(jìn)入白色區(qū)域時所遇到的第一個像素進(jìn)行標(biāo)記，這樣就把每一行的行線標(biāo)記出來了，所得到的行線是單像素的。這種方法的優(yōu)點是可以抗傾斜。

　　圖5（a）為對圖1中的圖像中的行用直線的方式標(biāo)記出來。為了驗證提取出的行線與原圖是否一致，將它與原圖（如圖5（b）所示）進(jìn)行了匹配，可以看出，所得結(jié)果是比較滿意的。

　　2 匹配算法

　　本文所采用的方法是將行線抽象為空間中的一個點，點的灰度值定義為行線的長度。全局匹配模式考慮版面的加權(quán)平均，用于全局位置進(jìn)行匹配，這個過程相當(dāng)于文本區(qū)定位過程。局部匹配模式是定義兩個行在位置、尺寸上的變化情況，通過位置優(yōu)先（版面）得到匹配模式，進(jìn)而對匹配誤差能量進(jìn)行計算。

　　匹配方法轉(zhuǎn)化為兩組點之間的匹配定義問題，點模式簡化了問題的復(fù)雜性，只包含了版面結(jié)構(gòu)信息、長度信息和尺寸信息。

　　中心點加權(quán)匹配方式不能完全解決問題，圖像在兩個尺度上的縮放對這種方式影響極大。使用歸一化的尺寸可部分解決這個問題，但歸一化后仍需計算中心點的位置，通過中心點進(jìn)行坐標(biāo)轉(zhuǎn)換，使用坐標(biāo)轉(zhuǎn)換后的新的點模式對差異性進(jìn)行度量。

　　每一行起始坐標(biāo)的相對坐標(biāo)是（xi′，yi′），xi′=xi-x0，yi′=yi-y0。圖6為將行線抽象為空間中的點的圖像，其中亮度代表該行的長度，位置為起點坐標(biāo)。

　?。?）距離匹配模式計算

　　將兩個頁面的中心點對齊，從第一個頁面的第一行開始，與另一個頁面每行進(jìn)行比較。假如另一個頁面的相對坐標(biāo)是（uj′，vj′），j=0，…，n-1，每行長度為wj。計算兩個待比較頁面的坐標(biāo)及長度的差Δxi、Δyi、Δzi，其中：Δxi=xi′-uj′，Δyi=yi′-vj′，Δzi=zi-wj。則定義差異能量為：

　　dEnerge（i）=Δxi+Δyi+Δzi

　　將第一個頁面的第一行與第二個頁面的每一行進(jìn)行比較，得到n個差異能量，求這n個差異能量的最小值min（dEnerge（i））。第一個頁面共有m行，將得到m個值，對其求和：

　　不匹配的情況經(jīng)常發(fā)生，例如一個圖像中含有4個點模式，另一個圖像中含有10個點模式，內(nèi)部點模式之間具有結(jié)構(gòu)相關(guān)性，結(jié)構(gòu)上的相關(guān)性定義為點模式位置掩模距離，該距離用來度量點模式全局匹配能力。如果一個點模式為另一個點模式的子模式，則該方法實現(xiàn)子圖檢索功能，模式距離最小時，產(chǎn)生最佳匹配。最佳匹配時，產(chǎn)生更為細(xì)致的行線檢索能力。使用掩模方法是為了產(chǎn)生更好的查準(zhǔn)率。[!--empirenews.page--]

　　3 實驗結(jié)果與分析

　　應(yīng)用上述方法進(jìn)行了實驗，數(shù)據(jù)為手寫體英文，數(shù)據(jù)采集分辨率為100 dpi，256級灰度圖像，數(shù)據(jù)量為100幅文檔圖像。對不同的圖像分別比較它們的相似度。圖7（b）、（c）、（d）是與圖7（a）的相似度分別為40.422 9、45.760 7和43.407 8的圖像。圖8（b）、（c）、（d）是與圖8（a）原圖像版面結(jié)構(gòu)相似的幾種圖像類型。圖9（b）、（c）、（d）是與圖9（a）原圖像版面結(jié)構(gòu)具有差異的幾種圖像類型。

　　本文使用對100幅文檔圖像兩兩進(jìn)行版面結(jié)構(gòu)的匹配，共有4 950種結(jié)果。實驗結(jié)果表明，兩種不同版面的能量差異最大的在340左右，如圖10所示。橫坐標(biāo)顯示的是100幅圖像兩兩匹配出現(xiàn)的情況的數(shù)目，可以取到的最大坐標(biāo)為4 950，縱坐標(biāo)為各匹配情況對應(yīng)的能量差異，最大值350。從圖中可以看出能量差異主要集中在50~200之間。

　　各個能量點的頻數(shù)的直方圖如圖11所示，圖中橫坐標(biāo)為能量差異數(shù)據(jù)，最大為340左右，提取到350?？v坐標(biāo)為取到各個能量的情況的數(shù)目的累加。從圖11可以更直觀地觀察到能量差異在50~200之間的數(shù)目最多。

　　實驗結(jié)果表明：（1）文檔圖像的版面結(jié)構(gòu)具有相對的穩(wěn)定性。（2）點匹配模式計算了最小距離，可有效表示圖像的文本行基本信息。（3）距離匹配較為簡單，使用了三個維度的一維距離，有較好的區(qū)分性。對距離計算統(tǒng)計表明，具有正態(tài)分布特性。（4）點匹配模式需進(jìn)一步進(jìn)行研究，算法的復(fù)雜度需進(jìn)一步降低，以進(jìn)行實時圖像處理。

　　本文針對文檔圖像的檢索方法進(jìn)行了研究，提出一種文檔圖像檢索的新方法。分析了文檔圖像版面特性，使用分割方法確定文本行，將文本行進(jìn)行標(biāo)記，找出頁面的中心點坐標(biāo)，中心點坐標(biāo)將文本行的長度作為權(quán)重考慮在內(nèi)，得到相對坐標(biāo)。根據(jù)相對坐標(biāo)和文本行長度得到一個差異能量，根據(jù)差異能量來進(jìn)行匹配。并對該方法進(jìn)行了實驗和結(jié)果分析。本方法的優(yōu)點是，當(dāng)文檔的行出現(xiàn)傾斜和縮放時，不影響匹配的進(jìn)行。但需要進(jìn)一步降低所用的點匹配模式時間復(fù)雜度，以進(jìn)行實時圖像處理。