一種基于版面結構距離的文檔圖像檢索算法

趙 慧 ，王希常 ，劉 江

(1.山東師范大學 信息科學與工程學院，山東 濟南 250014；2.山東山大鷗瑪軟件有限公司數據研究中心，山東 濟南 250100)

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

雖然目前OCR技術已經能夠提供很高的打印體字符識別正確率，但是往往需要人工交互來提高字符識別的正確性。這對一個大規模的文檔圖像數據庫來說，其代價是相當大的。手寫體字符的識別本身相當困難，而語言相關性也是這類算法的一個明顯的缺點。因為不同的語言文字要求依靠不同的OCR系統去處理混合多種語言的文檔圖像，這將影響檢索系統的使用范圍。

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

本文提出了一種在文檔圖像數據庫中使用版面特征進行檢索的方法，具體定義了文檔頁面中均具有的行的版面特征。該方法直接作用于圖像數據，具有抗傾斜和抗縮放的好處。

具體步驟是先將文檔圖像進行梯度和最大梯度差MGD(Maximum Gradient Different)計 算[4]，然 后 使 用 MGD值作為一個窗口對文本區域進行融合，提取出行塊并用行線的形式標示出來，計算出相對坐標，再計算兩版面之間的距離進行匹配。

1 相關工作

1.1 文本行標記

將得到的文檔圖像進行預處理，具體的處理方法是：

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

圖1 使用上述方法對行塊進行標記的圖

1.2 消除階躍跳變

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

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

圖2 3×3 模板

1.3 行線標記

圖3 階躍跳變的四種可能情況

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

圖4 填充前后的圖像

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

圖5 對圖1的圖像行用直線標記出

2 匹配算法

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

匹配方法轉化為兩組點之間的匹配定義問題，點模式簡化了問題的復雜性，只包含了版面結構信息、長度信息和尺寸信息。

(1)點模式匹配

假如一個頁面上總共有m行，從第一行開始，因為行線為單像素，所以每一行的起始坐標為(xi，yi)，其中i=0，…，m-1，將每行的長度定義為 zi，i=0，…，m-1。 總共有m個點，這m個點的中心點的位置坐標為(x0，y0)。在計算中心點的位置坐標時，將它的每行的長度作為權重考慮在內，即：

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

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

圖6 將行線抽象為空間中的點的圖像

(2)距離匹配模式計算

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

dEnerge(i)=Δxi+Δyi+Δzi

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

不匹配的情況經常發生，例如一個圖像中含有4個點模式，另一個圖像中含有10個點模式，內部點模式之間具有結構相關性，結構上的相關性定義為點模式位置掩模距離，該距離用來度量點模式全局匹配能力。如果一個點模式為另一個點模式的子模式，則該方法實現子圖檢索功能，模式距離最小時，產生最佳匹配。最佳匹配時，產生更為細致的行線檢索能力。使用掩模方法是為了產生更好的查準率。

3 實驗結果與分析

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

本文使用對100幅文檔圖像兩兩進行版面結構的匹配，共有4 950種結果。實驗結果表明，兩種不同版面的能量差異最大的在340左右，如圖10所示。橫坐標顯示的是100幅圖像兩兩匹配出現的情況的數目，可以取到的最大坐標為4 950，縱坐標為各匹配情況對應的能量差異，最大值350。從圖中可以看出能量差異主要集中在 50～200之間。

圖7 不同圖像的比較

圖8 與原圖像(a)版面結構相似的圖像類型

圖9 與原圖像(a)版面結構具有差異的圖像類型

各個能量點的頻數的直方圖如圖11所示，圖中橫坐標為能量差異數據，最大為340左右，提取到350。縱坐標為取到各個能量的情況的數目的累加。從圖11可以更直觀地觀察到能量差異在50～200之間的數目最多。

實驗結果表明：(1)文檔圖像的版面結構具有相對的穩定性。(2)點匹配模式計算了最小距離，可有效表示圖像的文本行基本信息。(3)距離匹配較為簡單，使用了三個維度的一維距離，有較好的區分性。對距離計算統計表明，具有正態分布特性。(4)點匹配模式需進一步進行研究，算法的復雜度需進一步降低，以進行實時圖像處理。

圖10 能量分布圖

圖11 直立圖頻數

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

[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： Proceedingsofthe 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.