基于文本布局塊距離度量的文檔圖像檢索

王牡丹，鄔春學(xué)

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

基于文本布局塊距離度量的文檔圖像檢索

王牡丹，鄔春學(xué)

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

針對(duì)現(xiàn)有基于圖像文檔轉(zhuǎn)換為文本后進(jìn)行文檔檢索的方法，無(wú)法滿足當(dāng)今超大量數(shù)字圖像庫(kù)的處理場(chǎng)景。文中提出一種基于文本布局塊的文檔圖像檢索方法。根據(jù)文本布局塊之間的距離特征，定義了新的距離函數(shù)，利用新的距離函數(shù)計(jì)算得到文本布局塊之間的距離矩陣，并結(jié)合匈牙利算法求出文檔圖像的最佳匹配結(jié)果。通過(guò)大量實(shí)驗(yàn)證明，所提方法能夠有效地提高圖像文檔檢索準(zhǔn)確度，并且能保證78.2%的正確率。

圖像文檔檢索；文檔圖像分割；文本布局塊；距離函數(shù)；匈牙利算法

在新媒體時(shí)代，數(shù)字文檔具有信息量大、方便攜帶、便于閱讀等優(yōu)點(diǎn)，在圖書館和期刊雜志的文檔庫(kù)中，大多數(shù)文檔都是以文檔圖像形式保存的。現(xiàn)有的文檔圖像檢索方式是通過(guò)將文檔圖像轉(zhuǎn)換為文本，然后根據(jù)文本信息來(lái)檢索文檔圖像。該方法依賴高昂的光學(xué)掃描識(shí)別以及查詢索引的建立，耗時(shí)耗力[1-5]。

近年來(lái)，一種通過(guò)文檔布局檢索文檔圖像的新方法被應(yīng)用于文檔圖像檢索，該方法根據(jù)不同文本布局的布局塊之間的相似距離來(lái)匹配文檔圖像。其直接基于文檔圖像的布局塊進(jìn)行檢索的特點(diǎn)，能夠有效縮短檢索復(fù)雜性和檢索耗時(shí)，降低成本[6-10]?，F(xiàn)有的處理方法有：文獻(xiàn)[6]提出了一種布局對(duì)比的two-step方法，首先將文檔圖像分割為等尺寸的塊，然后在使用不同的方法計(jì)算塊距離。文獻(xiàn)[11]提出使用布局塊的覆蓋面積來(lái)找出參考圖像和查詢圖像之間的關(guān)系。

1 問(wèn)題描述

20世紀(jì)70年代，基于圖像檢索的文本圖像搜索的相關(guān)研究就已經(jīng)開始，主流的圖像檢索技術(shù)是基于文本信息的圖像檢索。該技術(shù)主要是利用光學(xué)掃描的方式來(lái)提取圖像的文本信息特征，并將這些文本信息存放在一個(gè)數(shù)據(jù)庫(kù)管理系統(tǒng)中，建立與圖像關(guān)系索引，最后通過(guò)查詢數(shù)據(jù)庫(kù)完成圖像檢索。此技術(shù)有兩個(gè)缺點(diǎn)：(1)需要依靠手工完成大量圖像特征的標(biāo)記；(2)手工標(biāo)記的圖像特征會(huì)受主觀因素影響過(guò)大。因此，如何有效地對(duì)文檔圖像進(jìn)行檢索以及如何對(duì)文檔圖像進(jìn)行布局分析成為提取文檔圖像信息的關(guān)鍵問(wèn)題。

本文的研究重點(diǎn)是基于布局塊距離度量的文檔圖像檢索，在后續(xù)章節(jié)中，將結(jié)合圖像處理系統(tǒng)中的3個(gè)模塊分別介紹這一技術(shù)，即圖像分割、圖像特征提取和圖像匹配，處理流程如圖1所示?；诂F(xiàn)有的多種塊距離計(jì)算方式和圖像塊匹配算法，對(duì)文本圖像檢索進(jìn)行深入研究和學(xué)習(xí)，對(duì)其中的基于區(qū)域覆蓋面積的塊距離計(jì)算方式進(jìn)行改進(jìn)，并結(jié)合匈牙利圖像塊匹配算法，定義新的距離函數(shù)。

圖1 圖像檢索處理流程

2 設(shè)計(jì)與實(shí)現(xiàn)

基于文本布局塊距離度量的文檔圖像檢索技術(shù)包括圖像分割、圖像特征提取和圖像匹配3個(gè)步驟。圖像分割，即通過(guò)幾何版面分析和版面理解工具獲得文檔圖像的版面邏輯結(jié)構(gòu)信息，并使用XY-CUT算法分割文本圖像得到布局塊；圖像特征提取則利用自定義距離函數(shù)計(jì)算布局塊之間的距離相似度，得到表示布局塊之間的圖像特征的距離矩陣；將得到的距離矩陣作為匈牙利匹配算法的輸入，完成圖像匹配。

2.1 文檔圖像分割

對(duì)于文本格式規(guī)整的文檔圖像，采用水平投影和垂直投影相結(jié)合的方法即可實(shí)現(xiàn)良好的塊分割。XY-CUT分割方法通過(guò)逐步遞歸的方式對(duì)文檔圖像按照X方向和Y方向進(jìn)行切割，將整個(gè)文檔圖像劃分成多個(gè)布局塊。在每步劃分時(shí)，計(jì)算當(dāng)前劃分的節(jié)點(diǎn)在X方向和Y方向的投影輪廓，通過(guò)尋找X方向和Y方向投影輪廓的谷底得到切割點(diǎn)。

圖2 文檔部分圖像布局塊集合

具體分割步驟如下：(1)輸入灰度圖像，使用雙線性插值法對(duì)圖形進(jìn)行歸一化處理；(2)采用Otsu算法對(duì)圖像進(jìn)行二值化的處理；(3)對(duì)文檔圖像進(jìn)行X-Y cut 分割處理。經(jīng)過(guò)多次的X方向投影和Y方向投影交替進(jìn)行的過(guò)程得到文本圖像布局塊集合，如圖2所示。

2.2 文檔圖像布局塊的信息表示

文檔圖像經(jīng)過(guò)XY-CUT方法被分割成多個(gè)文檔布局塊的集合，圖3表示一個(gè)布局塊信息，定義下列布局塊圖像信息：(1)查詢文檔圖像布局，QL={QB1,…,QBn}；(2)參考文檔圖像布局，RL={RB1,…,RBn}；(3)布局塊，每個(gè)布局塊由一對(duì)頂點(diǎn)P表示，B=(p1,p2)；(4)頂點(diǎn)，由一對(duì)x，y坐標(biāo)表示頂點(diǎn)P，P=(x,y)。

圖3 布局塊

2.3 距離函數(shù)

文檔布局的相似性，即布局之間的距離，需要通過(guò)布局塊之間的關(guān)系進(jìn)行計(jì)算，布局塊之間距離度量的好壞，直接影響全局距離的計(jì)算。布局塊之間的關(guān)系通過(guò)以下幾個(gè)屬性進(jìn)行表示：(1)位置。如果兩個(gè)布局塊的位置相似，則有利于分析布局的相似性；(2)寬度。如果布局塊的寬度相同，則兩個(gè)布局可能具有相同的列寬。(3)面積。如果不同布局的兩個(gè)塊的面積不同，則暗示這些塊互相是不匹配的?；谏鲜?種塊屬性，存在多種布局塊距離度量的方式，各距離函數(shù)的計(jì)算公式及應(yīng)用可采用多種方式進(jìn)行。

2.3.1 簡(jiǎn)單塊距離

寬度差與高度差的積

DP(QBi,RBj)=Dh(QBi,RBj)×Dw(QBi,RBj)

(1)

塊中心距離

Dbc(QBi,RBj)=dmh(center(QBi),center(RBj))

(2)

這兩種方法僅僅通過(guò)對(duì)布局塊不同屬性值計(jì)算得到塊距離，不能證明得到的所有塊距離都是有意義的，與預(yù)期結(jié)果存在比較大的偏差。

2.3.2 重疊區(qū)域面積

重疊區(qū)域面積方法利用布局塊之間重疊區(qū)域來(lái)計(jì)算兩個(gè)布局塊之間距離，重疊區(qū)域面積是指同時(shí)屬于兩個(gè)布局塊的像素?cái)?shù)量總和。對(duì)于每一對(duì)布局塊(Bi,Bj)，Bi和Bj是分別屬于兩個(gè)文檔圖像的布局塊，即查詢布局RL與參考布局RL。其距離函數(shù)定義為

(3)

其中，area(RBi)表示布局塊RBi中像素的數(shù)量；area(QBi)表示布局塊QBi中像素的數(shù)量；Qv(QBi,RBj)表示QBi和RBj布局塊的重疊區(qū)域內(nèi)像素?cái)?shù)量總和；每一對(duì)布局塊的重疊區(qū)域面積取值區(qū)間為(0,1)，0表示完全重疊，1表示無(wú)重疊。

2.3.3 改進(jìn)距離函數(shù)

單純地用重疊區(qū)域面積作為塊距離的度量依舊會(huì)存在一定偏差。例如兩塊面積相同，但位置不同的布局塊，若只考慮重疊覆蓋面積，則無(wú)法準(zhǔn)確得到兩個(gè)布局塊的匹配精度，同時(shí)會(huì)出現(xiàn)如圖4所示的情況。

圖4 重疊區(qū)域面積方法計(jì)算結(jié)果與期望結(jié)果

為避免上述情況，需要在選擇距離度量時(shí)考慮布局塊的位置因素。如圖5所示，對(duì)于重疊面積相同的兩個(gè)查詢布局塊QB1和QB2，分別計(jì)算它們各自中心點(diǎn)與參考布局塊RB中心點(diǎn) 之間的距離，即可得到兩個(gè)塊之間的差異，由此可知考慮中心距離有助于提高匹配精度。

圖5 查詢布局塊中心點(diǎn)與參考布局塊中心點(diǎn)距離

結(jié)合布局塊的重疊區(qū)域面積和布局塊中心點(diǎn)之間的距離計(jì)算方法，提出一種新的距離函數(shù)，定義為

(4)

在式(4)中，Dbc(QBi,RBj)表示兩個(gè)布局塊中心點(diǎn)之間的距離。如果使用式(3)進(jìn)行距離計(jì)算，當(dāng)兩個(gè)布局塊面積相同而位置不同時(shí)，將得到相同的距離值，無(wú)法計(jì)算兩個(gè)布局塊的相似度。此時(shí)使用式(4)，所得到中心點(diǎn)之間的距離不同，得到的距離函數(shù)值也不同，即能夠更加精確的計(jì)算出兩個(gè)區(qū)域塊的匹配精度。

2.4 塊匹配算法

通過(guò)求解距離函數(shù)，可得到一個(gè)N×N階的整數(shù)矩陣，現(xiàn)將問(wèn)題簡(jiǎn)化為求該矩陣的最優(yōu)匹配，即對(duì)一個(gè)N×N階的整數(shù)矩陣求解，最終求得一個(gè)具有最小和的n個(gè)元素的獨(dú)立集。已知矩陣任意一排減去常數(shù)C，或任意一列減去常數(shù)C，對(duì)匹配結(jié)果的次序無(wú)影響。

將N×N階矩陣A=(Cij)每行(列)中的各個(gè)元素減去該行(列)中的最小元素，得到新矩陣D=(Cij)，將求最優(yōu)解問(wèn)題轉(zhuǎn)換為求解系數(shù)矩陣D=(Cij)的最大獨(dú)立集問(wèn)題，運(yùn)用匈牙利算法的思想來(lái)解決當(dāng)前問(wèn)題。

改進(jìn)“匈牙利算法”：

步驟1 對(duì)系數(shù)矩陣進(jìn)行變換，使每行每列都出現(xiàn)0元素。(1)從系數(shù)矩陣中每行減去該行最小元素；(2)再在所得矩陣每列減去每列最小元素；

步驟2 確定一個(gè)0的最大獨(dú)立集：在矩陣中找出一個(gè)0的最大獨(dú)立集S；

步驟3 如果|S|

While |S|

設(shè)k是不在這個(gè)覆蓋的排上的最小的矩陣元素；

將不在覆蓋的排上的每個(gè)元素減去k；

將既在這個(gè)覆蓋的行中又在這個(gè)覆蓋的列中的每個(gè)元素加上k；

用一個(gè)新的0的最大獨(dú)立集替代S；

end While

步驟4 輸出：集合S是具有最小和的n個(gè)元素的獨(dú)立集。

3 實(shí)驗(yàn)分析

從IEEE期刊文檔圖像庫(kù)中選取120篇文檔圖像進(jìn)行文檔圖像檢索實(shí)驗(yàn)。這些文檔圖像在文檔行或者文檔區(qū)域的布局上表現(xiàn)出較為明顯的布局塊圖像特征，因此非常適合作為實(shí)驗(yàn)對(duì)象。綜合文章提出的文檔圖像分割方法和距離，以及改進(jìn)的匈牙利算法，運(yùn)用4種距離函數(shù)進(jìn)行文檔圖像檢索實(shí)驗(yàn)。

實(shí)驗(yàn)檢索的輸出結(jié)果為兩個(gè)文檔圖像以及兩個(gè)坐標(biāo)文件，如圖6所示，圖6(a)為覆蓋面積距離函數(shù)計(jì)算結(jié)果，圖6(b)為改進(jìn)距離函數(shù)得到的結(jié)果。從實(shí)驗(yàn)結(jié)果中可以看出，雖然匹配結(jié)果存在一定的偏差，但通過(guò)大量數(shù)據(jù)實(shí)驗(yàn)統(tǒng)計(jì)，正確率可達(dá)78.2%，表示此方法有效提高了文檔圖像的檢索準(zhǔn)確度。

圖6 匹配結(jié)果

表1的實(shí)驗(yàn)結(jié)果表明，在綜合考慮重疊區(qū)域面積及布局塊中心點(diǎn)位置等因素后提出的距離函數(shù)能夠有效提高文檔匹配的準(zhǔn)確度，相比于原有的寬度差與高度差之積的方法、塊中心距離方法以及重疊區(qū)域面積等文檔圖像檢索方式，準(zhǔn)確率分別提高26.5%、15.7%、8.9%。

表1 距離函數(shù)實(shí)驗(yàn)結(jié)果

4 結(jié)束語(yǔ)

本文提出的基于文本布局塊的圖像文檔檢索方式，適用于檢索具有典型布局的文檔，如期刊雜志和數(shù)字文檔圖像庫(kù)中的文檔圖像。隨著當(dāng)前文檔圖像檢索領(lǐng)域發(fā)展，需要用于具有更加復(fù)雜文檔布局的文檔檢索方法，以提供更優(yōu)的文檔圖像查詢。目前在文檔圖像檢索技術(shù)的研究已取得了部分成果，提出了許多有價(jià)值的概念和方法，對(duì)文檔圖像檢索的研究也在不斷深入。面對(duì)當(dāng)前數(shù)字信息迅速增長(zhǎng)的情況，將圖像文檔檢索與Hadoop、Spark等分布式技術(shù)結(jié)合，帶來(lái)了新的研究方向。

[1] 杜丙新.圖像檢索研究綜述及系統(tǒng)實(shí)現(xiàn)[J].電子科技,2016, 29(6):185-189.

[2] 蔣從文,李隱峰,齊鵬,等.學(xué)術(shù)期刊電子論文檢索系統(tǒng)設(shè)計(jì)[J].電子科技,2014,27(2):122-124.

[3] Breuel T M,Janssen W C,Popat K,et al.Paper to PDA[C].PF,USA:International Conference On pattern Recognition,2002.

[4] Shafait F,Keysers D,Breuel T.Performance evaluation and benchmarking of six-page segmentation algorithms[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2008,30(6):941-54.

[5] Breuel T M.Hign performance document layout analysis[C].NG,USA:Symposium on Document Image Understanding Technology,2003.

[6] Hu J,Kashi R,Wilfong G T.Document image layout comparison and classification[C].HW,USA:Proceedings of the International Conference on Document Analysis and Recognition,1999.

[7] Liang J,Phillips I T,Haralick R M.Performance evaluation of document structure extraction algorithms[J].Computer Vision and Image Understanding，2001，84(1)：144-159.

[8] 胡芝蘭,林行剛,嚴(yán)洪.基于分層密度特征的文檔圖像檢索[J].清華大學(xué)學(xué)報(bào):自然科學(xué)版,2006,46(7):1231-1234.

[9] 宋濤,劉剛.一種基于內(nèi)容的文檔圖像檢索方法[J].鄭州大學(xué)學(xué)報(bào):工學(xué)版,2010,31(1):120-124.

[10] 張?zhí)?綜合文字和非文字區(qū)域特征的文檔圖像檢索[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(12):5-8.

[11] 趙慧.基于版面分析的文檔圖像檢索算法研究[D].濟(jì)南:山東師范大學(xué),2011.

[12] 趙慧,王希常,劉江.一種基于版面結(jié)構(gòu)距離的文檔圖像檢索算法[J].微型機(jī)與應(yīng)用,2010,29(21):42-44.

[13] 張敏.基于紋理特征的數(shù)字圖書館文檔圖像檢索技術(shù)[J].河南理工大學(xué)學(xué)報(bào):自然科學(xué)版,2014,33(4):506-509.

[14] 張?zhí)?一種基于特征的文檔圖像檢索方法[C].北京:全國(guó)模式識(shí)別學(xué)術(shù)會(huì)議,2008.

[15] 郭加旋.面向非純文本文檔圖像的檢索技術(shù)研究與實(shí)現(xiàn)[D].重慶:西南大學(xué),2014.

[16] 周靜雯.基于布局相似性的文本圖像檢索[D].上海:華東師范大學(xué),2014.

Document Image Retrieval Based on Text Layout Block Distance

WANG Mudan,WU Chunxue

(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093, China)

The existing methods of document retrieval based on the conversion of image documents into text can not meet the processing scenes of today’s large number of digital image databases. This paper proposes a document image retrieval method based on text layout block. According to the feature of distance between text blocks, a new distance function is defined. Then, the new distance function is used to calculate the distance matrix between text blocks. Finally, the best matching result is obtained by combining the Hungarian algorithm. A lot of experiments show that this method can effectively improve the image document retrieval accuracy, and can guarantee the correct rate of 78.2%.

image document retrieval; document image segmentation; text layout block; distance function; Hungarian algorithm

2016- 11- 21

國(guó)家自然科學(xué)基金(61202376)；上海市教育基金會(huì)晨光計(jì)劃基金(10CG49)

王牡丹(1990-)，女，碩士研究生。研究方向：數(shù)字圖像處理。鄔春學(xué)(1964-)，男，博士，教授。研究方向：嵌入式系統(tǒng)及應(yīng)用等。

10.16180/j.cnki.issn1007-7820.2017.09.013

TN911.73；TP391.41

A

1007-7820(2017)09-046-04