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

    文檔圖像一般意為含有文字信息的圖像，目前大多數(shù)信息是以數(shù)字化形式存在的，并以文檔的形式組織起來存放在數(shù)據(jù)庫(kù)中。在這樣的數(shù)據(jù)庫(kù)中查找有關(guān)資料其技術(shù)是關(guān)鍵。常見的文檔圖像檢索方法是基于內(nèi)容的文檔圖像檢索(CBIR)。它是利用圖像本身的信息，通常以圖像特征(顏色、紋理、形狀、結(jié)構(gòu)布局和語義特征等)的相似性為檢索依據(jù)，根據(jù)每幅圖像都有的可比較特征進(jìn)行檢索。
    雖然目前OCR技術(shù)已經(jīng)能夠提供很高的打印體字符識(shí)別正確率，但是往往需要人工交互來提高字符識(shí)別的正確性。這對(duì)一個(gè)大規(guī)模的文檔圖像數(shù)據(jù)庫(kù)來說，其代價(jià)是相當(dāng)大的。手寫體字符的識(shí)別本身相當(dāng)困難，而語言相關(guān)性也是這類算法的一個(gè)明顯的缺點(diǎn)。因?yàn)椴煌恼Z言文字要求依靠不同的OCR系統(tǒng)去處理混合多種語言的文檔圖像，這將影響檢索系統(tǒng)的使用范圍。
    BEUSEKOM J V.等人提出了一種基于版面分析的文檔圖像檢索的距離度量方法，將文本區(qū)域分為不同的矩形塊，然后找到塊的中心點(diǎn)，利用角點(diǎn)的曼哈頓距離來計(jì)算塊之間的距離，再利用三種不同的方法進(jìn)行匹配[1]；WONG K Y.使用游程平滑算法進(jìn)行版面信息提取的方法[2]；BREUEL T M.提出了使用Whitespace算法來提取版面信息[3]。
    本文提出了一種在文檔圖像數(shù)據(jù)庫(kù)中使用版面特征進(jìn)行檢索的方法，具體定義了文檔頁面中均具有的行的版面特征。該方法直接作用于圖像數(shù)據(jù)，具有抗傾斜和抗縮放的好處。
    具體步驟是先將文檔圖像進(jìn)行梯度和最大梯度差MGD(Maximum Gradient Different)計(jì)算[4]，然后使用MGD值作為一個(gè)窗口對(duì)文本區(qū)域進(jìn)行融合，提取出行塊并用行線的形式標(biāo)示出來，計(jì)算出相對(duì)坐標(biāo)，再計(jì)算兩版面之間的距離進(jì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)，用它的最大梯度差來進(jìn)行填充，以達(dá)到文本融合的目的。因?yàn)橛⑽暮椭形牡淖址麑挾炔煌?，根?jù)具體的情況選擇n，大于字符間距即可。將計(jì)算出來的梯度求它的最大值和最小值，然后相減，即為最大梯度差。將得到的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ǔ)算法來消除階躍跳變，算法的復(fù)雜度相對(duì)較低。
    在像素級(jí)上進(jìn)行處理是：當(dāng)出現(xiàn)行階躍跳變的情況時(shí)，使用如圖2的模板來對(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所示。

1.3 行線標(biāo)記
    通過對(duì)得到的二值圖像的行跳變的填補(bǔ)，文本行的變化相對(duì)比較平滑，這有利于行線的標(biāo)記。本方法取每個(gè)文本行的下邊緣來作為行線。因?yàn)楸尘皡^(qū)域?yàn)楹谏?，文字區(qū)域?yàn)榘咨?，所以?duì)文檔圖像進(jìn)行掃描，從黑色區(qū)域進(jìn)入白色區(qū)域時(shí)所遇到的第一個(gè)像素進(jìn)行標(biāo)記，這樣就把每一行的行線標(biāo)記出來了，所得到的行線是單像素的。這種方法的優(yōu)點(diǎn)是可以抗傾斜。
    圖5(a)為對(duì)圖1中的圖像中的行用直線的方式標(biāo)記出來。為了驗(yàn)證提取出的行線與原圖是否一致，將它與原圖(如圖5(b)所示)進(jìn)行了匹配，可以看出，所得結(jié)果是比較滿意的。

2 匹配算法
    本文所采用的方法是將行線抽象為空間中的一個(gè)點(diǎn)，點(diǎn)的灰度值定義為行線的長(zhǎng)度。全局匹配模式考慮版面的加權(quán)平均，用于全局位置進(jìn)行匹配，這個(gè)過程相當(dāng)于文本區(qū)定位過程。局部匹配模式是定義兩個(gè)行在位置、尺寸上的變化情況，通過位置優(yōu)先(版面)得到匹配模式，進(jìn)而對(duì)匹配誤差能量進(jìn)行計(jì)算。
匹配方法轉(zhuǎn)化為兩組點(diǎn)之間的匹配定義問題，點(diǎn)模式簡(jiǎn)化了問題的復(fù)雜性，只包含了版面結(jié)構(gòu)信息、長(zhǎng)度信息和尺寸信息。

    中心點(diǎn)加權(quán)匹配方式不能完全解決問題，圖像在兩個(gè)尺度上的縮放對(duì)這種方式影響極大。使用歸一化的尺寸可部分解決這個(gè)問題，但歸一化后仍需計(jì)算中心點(diǎn)的位置，通過中心點(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è)頁面的中心點(diǎn)對(duì)齊，從第一個(gè)頁面的第一行開始，與另一個(gè)頁面每行進(jìn)行比較。假如另一個(gè)頁面的相對(duì)坐標(biāo)是(uj′，vj′)，j=0，…，n-1，每行長(zhǎng)度為wj。計(jì)算兩個(gè)待比較頁面的坐標(biāo)及長(zhǎng)度的差Δxi、Δyi、Δzi，其中：Δxi=xi′-uj′，Δyi=yi′-vj′，Δzi=zi-wj。則定義差異能量為：
dEnerge(i)=Δxi+Δyi+Δzi
    將第一個(gè)頁面的第一行與第二個(gè)頁面的每一行進(jìn)行比較，得到n個(gè)差異能量，求這n個(gè)差異能量的最小值min(dEnerge(i))。第一個(gè)頁面共有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)模式位置掩模距離，該距離用來度量點(diǎn)模式全局匹配能力。如果一個(gè)點(diǎn)模式為另一個(gè)點(diǎn)模式的子模式，則該方法實(shí)現(xiàn)子圖檢索功能，模式距離最小時(shí)，產(chǎn)生最佳匹配。最佳匹配時(shí)，產(chǎn)生更為細(xì)致的行線檢索能力。使用掩模方法是為了產(chǎn)生更好的查準(zhǔn)率。
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)記，找出頁面的中心點(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ù)差異能量來進(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í)圖像處理。
參考文獻(xiàn)
[1] BEUSEKOM J V， KEYSERS D， SHAFAIT F， et al. Distance measures for layout-based document image retrieval[C].In：2nd IEEE International Conference on Document Image Analysis for Libraries， yon， France， (2006)： 232-242.
[2] WONG K Y， CASEY R G， WAHL F M. Document analysis system[J].  IBM Journal of Research and Development， 1982， 26(6)： 647-656.
[3] BREUEL T M. Two geometric algorithms for layout analysis[C]. In DAS ’02： Proceedings of the 5th International Workshop on Document Analysis Systems V， Springer-Verlag， London， UK， 2002： 188-199.
[4] JAE H K， TAE T P， YANG H C， et al. Photo-text segmentation in complex color document[C]. The 5th Japan-Korean Joint Symposium on Imaging Materials and Technologies， Kyoto， Japan， Nov. 2004： 44-47.
[5] OTSU N. A threshold selection method from gray-level histograms[J]. IEEE Trans. Systems， Man and Cybernetics， 1979， 9(1)：62-66.