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

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

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

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

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

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

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

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

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

　　利用灰度信息匹配方法的主要缺陷是計(jì)算量太大，因?yàn)槭褂脠?chǎng)合一般都有一定的速度要求，所以這些方法很少被使用?，F(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)記算法實(shí)現(xiàn)文字區(qū)域的行定位。本文使用[-1，0，1]對(duì)圖像進(jìn)行處理計(jì)算其梯度，然后計(jì)算其MGD。MGD計(jì)算方法如下：在一個(gè)大小為n的窗口內(nèi)，用它的最大梯度差來(lái)進(jìn)行填充，以達(dá)到文本融合的目的。因?yàn)橛⑽暮椭形牡淖址麑挾炔煌?，根?jù)具體的情況選擇n，大于字符間距即可。將計(jì)算出來(lái)的梯度求它的最大值和最小值，然后相減，即為最大梯度差。將得到的MGD圖像使用最大類間方差方法[5]（OTSU）求出閾值得到二值圖像[2]。圖1為使用上述方法對(duì)行塊進(jìn)行標(biāo)記的圖像。

　　1.2 消除階躍跳變

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

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

[!--empirenews.page--]

　　1.3 行線標(biāo)記

　　通過(guò)對(duì)得到的二值圖像的行跳變的填補(bǔ)，文本行的變化相對(duì)比較平滑，這有利于行線的標(biāo)記。本方法取每個(gè)文本行的下邊緣來(lái)作為行線。因?yàn)楸尘皡^(qū)域?yàn)楹谏?，文字區(qū)域?yàn)榘咨詫?duì)文檔圖像進(jìn)行掃描，從黑色區(qū)域進(jìn)入白色區(qū)域時(shí)所遇到的第一個(gè)像素進(jìn)行標(biāo)記，這樣就把每一行的行線標(biāo)記出來(lái)了，所得到的行線是單像素的。這種方法的優(yōu)點(diǎn)是可以抗傾斜。

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

　　2 匹配算法

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

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

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

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

　　（2）距離匹配模式計(jì)算

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

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

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

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

　　3 實(shí)驗(yàn)結(jié)果與分析

　　應(yīng)用上述方法進(jìn)行了實(shí)驗(yàn)，數(shù)據(jù)為手寫體英文，數(shù)據(jù)采集分辨率為100 dpi，256級(jí)灰度圖像，數(shù)據(jù)量為100幅文檔圖像。對(duì)不同的圖像分別比較它們的相似度。圖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)具有差異的幾種圖像類型。

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

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

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

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