一種基于馬爾科夫隨機場的蒙古文古籍圖像恢復方法

白淑霞 鮑玉來* 敖 權

1(內蒙古大學圖書館 內蒙古 呼和浩特010021)2(內蒙古大學計算機學院 內蒙古 呼和浩特 010021)

一種基于馬爾科夫隨機場的蒙古文古籍圖像恢復方法

白淑霞1鮑玉來1*敖 權2

1(內蒙古大學圖書館 內蒙古 呼和浩特010021)2(內蒙古大學計算機學院 內蒙古 呼和浩特 010021)

針對蒙古文古籍圖像檢索領域中對同一查詢關鍵詞，不同的二值化算法對整體檢索性能影響問題，提出一種基于馬爾科夫隨機場的蒙古文古籍圖像二值化方法，從而提高蒙古文古籍圖像的檢索性能。利用馬爾科夫隨機場模型在灰度圖像和二值圖像之間建模，通過訓練碼本估計隱藏層的先驗概率，并分析灰度圖像的直方圖估計可觀察層的概率密度。利用這兩種先驗知識實現(xiàn)圖像二值化。實驗數(shù)據(jù)集為100頁蒙古文《甘珠爾經(jīng)》，為了驗證本文所提方法的性能，實驗采用R-Precision作為評價指標。實驗結果表明，基于馬爾科夫隨機場的二值化方法不僅可以有效修復受損圖像，還可以進一步提高其檢索性能。

蒙古文古籍 文檔圖像檢索 圖像二值化 馬爾科夫隨機場

0 引 言

古籍文獻資料作為人類的寶貴文化遺產(chǎn)，由于其具有珍貴的歷史和文物價值，它們大多被珍藏于博物館、圖書館，除了少數(shù)專家和學者之外，公眾很少有機會能翻閱它們。近年來，數(shù)字化技術的迅猛發(fā)展，進一步推動了古籍文獻資料(包括蒙古文古籍文獻)向數(shù)字圖像的轉換工作，從而實現(xiàn)對古籍文獻資料的長久保存。同時，通過互聯(lián)網(wǎng)，公眾可以便捷地翻閱這些古籍文獻的數(shù)字圖像。然而，古籍文獻的數(shù)字圖像只記錄了像素顏色、亮度等底層(圖像)信息，并沒有描述文獻內容的高層(索引)信息，因此無法對其全文檢索。

在古籍圖像檢索領域HDIR(Historical Document Image Retrieval)，詞定位技術能夠通過圖像匹配的方式從古籍圖像中定位(檢索)查詢關鍵詞出現(xiàn)的位置，并能夠較好地解決古籍圖像檢索中涉及的相關問題(如圖像質量差、文字書寫不規(guī)范、變形嚴重等)[1]。在詞定位技術中，通常將古籍圖像集合表示成單詞圖像集合，即古籍圖像被分割成單詞圖像。在檢索時，依據(jù)用戶提供的查詢關鍵詞的示例圖像，計算示例圖像與單詞圖像集合中每個單詞圖像之間的相似度，并按照相似度降序返回檢索結果[2]。

蒙古文古籍圖像檢索問題中已經(jīng)有應用詞定位技術的先例。在之前的研究工作中，以清代康熙版(1720年印制)蒙古文《甘珠爾經(jīng)》為對象，通過以下方法實現(xiàn)蒙古文古籍圖像的檢索[3]：首先，每幅彩色掃描圖像先經(jīng)過預處理(包括灰度化、平滑濾波、二值化)，被轉換成二值(黑白)圖像，再經(jīng)過版面分割，從中獲得相應單詞圖像[4]。其次，分別從單詞圖像的每行和每列中提取如下輪廓特征：左輪廓、右輪廓、水平投影、水平方向筆劃穿越數(shù)、上輪廓、下輪廓、垂直投影和垂直方向筆劃穿越數(shù)。這樣，每個單詞圖像可被描述成與單詞圖像寬度相同的四個“行”特征向量和與單詞圖像高度相同的四個“列”特征向量[5]。然后，將單詞圖像的每個特征向量分別執(zhí)行離散傅里葉變換，僅保留頻域空間中前10個低頻復系數(shù)的模，從而可將每個單詞圖像表示成長度為80維的特征向量[6]。最后，在檢索時，通過提出的單詞圖像生成方法，由相應字形拼接生成所需查詢關鍵詞的示例圖像；示例圖像也經(jīng)上述過程的處理，轉換成長度為80維的特征向量；再通過計算示例圖像與其他單詞圖像特征向量之間的相似度可獲得檢索(排序)結果[7]。

為了提高檢索的精度，我們嘗試尋求更好的二值化方法。盡管蒙古文古籍文檔圖像的背景和光照強度變化并不劇烈，但是，由于蒙古文古籍風化、破損嚴重，使得圖像本身包含很多破洞和掉色的情況，加之本實驗使用的筆劃穿越數(shù)特征對圖像破洞十分敏感，預處理過程中，采用傳統(tǒng)的二值化方法很難獲得令人滿意的檢索效果。傳統(tǒng)的二值化方法[8-13]通過閾值分割將圖像上的每一個像素歸類為前景或背景，其中主要包括兩大類：全局閾值和局部適應閾值。在全局閾值中，整張圖像只選取一個閾值，所有的像素灰度值通過與該閾值比較來確定其屬于前景或背景。Otsu算法[8]作為全局閾值的經(jīng)典算法，通過最大化類間方差來選取最佳的閾值。局部適應閾值則是依據(jù)像素的鄰域塊的灰度分布來確定該像素位置上的二值化閾值，局部適應閾值可以有效緩解光照變化劇烈?guī)淼挠绊懀菀讛喙P和偽影等現(xiàn)象。Niblack[11]、Sauvola[13]兩種算法是經(jīng)典的局部閾值算法。最近，馬爾科夫隨機場理論被用作圖像的二值化[14-17]。在文獻[16]中，Cao等首先將輸入觀察圖像y和輸出二值圖像x都分成大小相同且互不重復圖像塊yi和xi，利用馬爾科夫隨機場(MRF)模型來模擬相鄰圖像塊之間的條件依賴關系，通過求解最大化后驗概率(MAP)來對圖像進行二值化處理。

1 馬爾科夫隨機場模型

本文使用文獻[16]中所描述的MRF模型，該MRF模型被定義為G={V,E}的圖模型。該模型中，二值圖像被分割成不重疊的方塊x1,x2,…,xN，并且觀察圖像也被分割成同樣大小y1,y2,…,yN，其中1≤i≤N，二值圖像塊xi與觀察圖像塊yi相對應，并且xi,yi∈V。二維馬爾科夫隨機場模型中存在兩種不同的邊，其中一種邊用來連接節(jié)點xi和節(jié)點xj，xj表示xi水平方向和垂直方向上的四個相鄰節(jié)點，可以表述為：每一個二值圖像塊在水平和垂直方向上條件依賴該塊的四個相鄰塊；另一種邊用來連接節(jié)點xi和yi，表示xi條件依賴yi，用來表達二值圖像和灰度圖像之間的條件依賴。條件依賴關系可以由下面公式表示：

P(xi|x1,x2,xi-1,xi+1,…,xN,y1,y2,…,yN)=

P(xi|xn1,i,xn2,i,xn3,i,xn4,i) 1≤i≤N

(1)

其中，xn1,i,xn2,i,xn3,i,xn4,i表示xi的四個鄰接圖像塊，觀察圖像塊與二值圖像塊之間的條件依賴關系可以表示為：

P(yi|x1,x2,…,xN,y1,y2,…,yi-1,yi+1,…,yN)=

P(yi|xi) 1≤i≤N

(2)

二維MRF模型表示如圖1所示。

圖1 二維馬爾科夫隨機場模型

(3)

直接通過式(3)計算xj是不太現(xiàn)實的，因為隨著節(jié)點個數(shù)的增加，計算量會呈指數(shù)形式增長。利用置信傳播(BP)[16]迭代的方式來近似MAP估計為本文提供了一種解決方法，該方法的計算量隨節(jié)點個數(shù)增加呈線性增長。

為了通過MRF模型得到優(yōu)化的二值化圖像，需要按照圖2所示的流程，即：將MRF模型定義為二維圖模型，然后通過計算MAP來估計最終的二值圖像。其中，計算MAP，首先利用置信傳播(BP)迭代計算，再進行二值塊先驗概率估計，最后估算觀察模型。

圖2 馬爾科夫隨機場(MRF)模型

1.1 置信傳播(BP)

(4)

(5)

(6)

(7)

(8)

并且使用聯(lián)合概率表示Φ，公式如下：

Φ(xk,yk)=P(xk,yk)

(9)

將式(8)、式(9)代入到式(6)、式(7)中，可以得到：

(10)

(11)

為了防止算數(shù)溢出，將式(10)、式(11)函數(shù)取對數(shù)：

(12)

(13)

置信傳播算法的參考代碼如下：

Function reco_image=belief_propagation(test_image,patch)

% 文中1.1節(jié)算法實現(xiàn)

% 置信傳播(belief_propagation)算法，通過迭代的方式回復出二值圖像

% 輸入?yún)?shù)：test_image待恢復圖像，patch為碼本(對應本文圖3)

% 輸出參數(shù)：reco_image恢復后圖像

patch_size=size(patch,1);

patch_num=size(patch,3);

%采用文獻[8]的方法估計前景和背景的均值與方差，并

%將灰度圖進行二值化

[bina_image,fore_mean,fore_std,back_mean,back_std]=Binarization(test_image);

hor_num=size(test_image,1)/patch_size;

ver_num=size(test_image,2)/patch_size;

bina_patch=reshape(bina_image,[patch_size,patch_size,hor_num,ver_num]);

gray_patch=reshape(test_image,[patch_size,patch_size,hor_num,ver_num]);

% 計算式(13)中的條件概率P(yk|xk);

for i=1:hor_num

for j=1:ver_num

for k=1:patch_num

log_pr_yk_xk(i,j,k)=observe_model(gray_patch(:,:,i,j),bina_patch(:,:,k),…back_mean,back_std,fore_mean,fore_std);

end

end

end

L_jk=zeros(patch_num,hor_num,ver_num,4);

while 1

% 調用式(13)

L_jk=max_xk(hor_num,ver_num,patch,L_jk,log_hor_xk_xj,log_ver_xk,xj,log_x);

% 調用式(12)

reco_patch=argmax(hor_num,ver_num,patch,L_jk,log_x,log_pr_yk_xk);

if isequal(reco_patch,bina_patch)

break;

else

bina_patch=reco_patch;

end

end

%得到最終恢復圖像

reco_image=reshape(bina_patch,[hor_num,ver_num])&bina_image;

end

1.2 二值塊先驗概率

為了求解P(xj)和P(xk|xj)，首先想到能否直接統(tǒng)計xj出現(xiàn)的每一種情況的概率，顯然這樣是不行的。假設選用的圖像塊的大小為b×b，那么xj所有可能的情況會有2b2種，當b=15時，xj所有可能出現(xiàn)的情況有2225種，這樣大的計算量遠遠超出了實驗室計算機的計算能力。由于所用圖像之間及內部存在大量的相似的圖像塊(patch)，訓練碼本為本實驗提供了一種可行的解決思路：利用碼本中少量的碼字來近似表達圖像塊所有可能出現(xiàn)的情況，將碼字作為訓練集中圖像塊{pi}的代表，從而使得計算變得可行。

(14)

(15)

圖3 233個碼字組成的碼本

(16)

其中l(wèi)1,l2=1,2,…,M。以水平方向為例，(pi1,pi2)表示訓練樣本中相鄰的兩個圖像塊，并且pi1在pi2的左邊，Npi1·pi2表示水平相鄰塊的總對數(shù)。

1.3 觀察模型

(17)

可以證明：

(18)

(19)

觀察模型的參考代碼如下所示：

% 文中1.3節(jié)算法實現(xiàn)，用以計算原始圖像每個patch與碼本

%的條件概率，即，式(19)

% 輸入?yún)?shù)：gray_patch原始圖像的patch，bina_patch為第k個

%碼本

function log_pr=observe_model(gray_patch,bina_patch,back_mean,back_std,fore_mean,fore_std)

log_pr=0;

for i=1:patch_size

for j=1:patch_size

if bina_patch(i,j)==0

log_pr=log_pr+log(normpdf(gray_patch(i,j),fore_mean,fore_std));

else

log_pr=log_pr+log(normpdf(gray_patch(i,j),back_mean,back_std));

end

end

end

end

2 實 驗

2.1 實驗數(shù)據(jù)集

本實驗采用的數(shù)據(jù)集是從內蒙古大學圖書館獲取的100頁蒙古文《甘珠爾經(jīng)》的彩色掃描圖像，掃描分辨率為600 DPI。每幅彩色掃描圖像均經(jīng)過文獻[4]提出的預處理方法，被轉換為灰度圖像，并通過版面分析共獲得24 827個單詞(灰度)圖像。本實驗將對這些單詞(灰度)圖像使用本文提出的MRF算法進行二值化。

為了便于統(tǒng)計相關性能指標，數(shù)據(jù)集的每一頁掃描圖像都采用Unicode編碼進行了文本標注。該實驗數(shù)據(jù)集已被用于統(tǒng)計文獻[3]中檢索系統(tǒng)的性能。在本研究中，繼續(xù)沿用文獻[3]使用的查詢關鍵詞(一個“查詢關鍵詞”相當于文本信息檢索中的一個“Topic(主題)”)，共計20個。這些查詢關鍵詞是對100頁掃描圖像的文本標注統(tǒng)計詞頻之后隨機挑選出來的。挑選標準是詞頻(出現(xiàn)次數(shù))不少于20次，且具有實際意義的單詞(如名詞、動詞等)，如表1所示。

表1 查詢關鍵詞列表

2.2 實驗直觀結果對比

在蒙古文古籍圖像檢索以前的研究中，《甘珠爾經(jīng)》曾被嘗試多種方法二值化，例如Otsu算法[8]、Kittler算法[9]和FCM算法[10]，但二值化結果都不太理想。在先前的圖像檢索中，本文使用Otsu、Kittler和FCM三種算法的綜合結果，即三種算法投票的方式，若兩種或三種算法將某一像素歸類為前景或背景，則該像素為前景或背景。實驗結果對比如圖4所示，(a)、(d)為原始破損灰度圖像，(b)、(e)為采用FCM、Kittler和Otsu投票二值化之后的二值圖像，(c)、(f)為采用MRF算法二值化之后的二值圖像。

圖4 二值化效果對比

2.3 評價指標

本文采用的性能評價指標是信息檢索中常用的R-Precision。R-Precision的定義如下[19]：

(20)

其中，Rel是表示與與查詢關鍵詞相關的單詞個數(shù)，r表示在是前Rel個檢索結果中出現(xiàn)的相關單詞的個數(shù)。如果相關單詞出現(xiàn)在前Rel個檢索結果中的數(shù)目越多，則R-Precision的值越高，其最大值為1(前Rel個檢索結果中全部為相關單詞)，最小值為0(前Rel個檢索結果中無相關單詞)。對每個查詢關鍵詞，可按上述公式由其檢索結果計算各自的R-Precision。

2.4 實驗過程、結果與分析

在實驗中，對每個查詢關鍵詞都執(zhí)行以下過程：首先利用本文中所述的方法來對圖像進行二值化；第二步，在二值圖像的基礎上提取本實驗所需要的80維輪廓特征；接下來，將該特征放到特征庫匹配，按相似度降序形成的檢索結果(單詞圖像列表)；最后統(tǒng)計結果中的R-Precision指標(如圖5所示)。

圖5 每個關鍵字的R-Precision

從圖5可以看出，使用MRF之后大部分查詢關鍵詞的檢索性能都有所提高，部分查詢關鍵詞的檢索性能未發(fā)生變化。

3 結 語

本文采用了一種更加適合蒙古文古籍文檔檢索中預處理的二值化算法。該方法能夠緩解低質量古籍文檔中的因為破損、掉色造成的圖像信息損失，不僅在視覺上獲得了比較好的結果，而且也提高了檢索性能。從整體來看，不使用MRF的平均R-Precision為57.76%，MRF處理之后的平均R-Precision為59.73%，檢索性能提高了近2%。在后續(xù)的研究中，我們將致力于選擇檢索精度更高、維度更少的特征來描述單詞圖像，以提高檢索精度和性能。

[1] Manmatha R, Han C, Riseman E M, et al., Indexing Handwriting Using Word Matching [C]// Fox E A, Marchionini G. Proceedings of the First ACM International Conference on Digital Libraries.

[2] Rath M T, Manmatha R. Word spotting for historical documents[J]. International Journal on Document Analysis and Recognition, 2007, 9(2-4): 139-152.

[3] Wei H X, Gao G L. A keyword Retrieval System for Historical Mongolian Document images[J]. International Journal on Document Analysis and Recognition, 2014, 17(1): 33-45.

[4] Wei H X, Gao G L, Bao Y L, et al. An Efficient Binarization Method for Ancient Mongolian Document images [C]// Proceedings of the Third International Conference on Advanced Computer Theory and Engineering. Washington DC: IEEE Computer Society, 2010: 43-46.

[5] 魏宏喜, 高光來. 基于Word Spotting 技術的蒙古文古籍圖像檢索中的特征選擇[J].計算機應用, 2011, 31(11):3038-3041.

[6] Wei H X, Gao G L, Zhang X L. Indexing for Mongolian Kanjur Images in Word Spotting[J]. Journal of Computational Information Systems, 2013, 9(4):1501-1508.

[7] Wei H X, Gao G L. Word Spotting Application in Historical Mongolian Document Images[C]// Huang D S, Bevilacqua V, Figueroa J C, et al. Proceedings of the Ninth International Conference on Intelligent Computing. Berlin Heidelberg: Springer-Verlag, 2013: 256-274.

[8] Ohtsu N. A Threshold Selection Method from Gray-Level Histograms[J]. IEEE Transactions on Systems Man & Cybernetics, 1979, 9(1):62-66.

[9] Kittler J, Illingworth J. Minimum error thresholding[J]. Pattern Recognition, 1986, 19(1):41-47.

[10] Duda R, Hart P, David G. Pattern Classification[M]. 2nd ed.Wiley, New York, 2001:528-530.

[11] Niblack W. An Introduction to Digital Image Processing[M]. Prentice Hall, Englewood Cliffs, 1986:1251-1255.

[12] Yang Y, Yan H. An adaptive logical method for binarization of degraded document images[J]. Pattern Recognition, 2000, 33(5):787-807.

[13] Sauvola J,Seppanen T,Haapakoski S,et al.Adaptive Document Binarization[C]// Proceedings of 4th Internationl Conference on Document Analysis and Recogntion,1997:147-152.

[14] Gupa M D, Rajaram S, Petrotic N, et al. Restoration and Recognition in a Loop[C]// Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2005.

[15] Wolf C, Doermann D. Binarization of Low Quality Text Using a Markov Random Field Model[C]// International Conference on Pattern Recognition, 2002. Proceedings. IEEE, 2002,3:160-163.

[16] Cao H, Govindaraju V. Preprocessing of Low-Quality Handwritten Documents Using Markov Random Fields[J]. Pattern Analysis & Machine Intelligence IEEE Transactions on, 2009, 31(7):1184-1194.

[17] Su B, Lu S, Tan C L. A learning framework for degraded document image binarization using Markov Random Field[C]// Pattern Recognition (ICPR), 2012 21st International Conference on. IEEE, 2012:3200-3203.

[18] Freeman W T, Pasztor E C, Carmicheal O T. Learning Low-level Vision[J]. International Journal of Computer Vision, 2000, 40(1):25-47.

[19] Manning C D, Raghavan P, Schutze H. Introduction to Information Retrieval [M].Cambridge: Cambridge University Press, 2009: 158-164.

AN IMAGE RETRIEVAL METHOD OF HISTORICAL MONGOLIAN DOCUMENT BASED ON MARKOV RANDOM FIELD

Bai Shuxia1Bao Yulai1*Ao Quan2

1(Library,InnerMongoliaUniversity,Hohhot010021,InnerMongolia,China)2(SchoolofComputerScience,InnerMongoliaUniversity,Hohhot010021,InnerMongolia,China)

Aiming at the problem of the influence of the same query keyword and different binarization algorithms on the overall retrieval performance in historical Mongolian document images retrieval, this paper presents an image binarization method of historical Mongolian document based on Markov random field to improve the retrieval performance of historical Mongolian documents. The MRF model is used to model the gray level image and the binary image. The prior probability of the hidden-layer is estimated by the training codebook, and the probability density of the observable-layer is estimated by analyzing the histogram of the gray image. The two kinds of prior knowledge are used to realize image binarization. The experimental data set is 100-page Mongolian Kanjur. In order to verify the performance of the proposed method, R-Precision is used as the evaluation index. Experimental results show that the binarization method based on Markov random field can not only effectively repair the damaged image, but also can improve its retrieval performance.

Historical Mongolian document Document image retrieval Image binarization Markov random field

2016-10-24。國家自然科學基金項目(71163029)。白淑霞，館員，主研領域：蒙古文信息檢索。鮑玉來，副研究館員。敖權，本科。

TP319.3

A

10.3969/j.issn.1000-386x.2017.04.035