白淑霞 鮑玉來* 敖 權(quán)
1(內(nèi)蒙古大學(xué)圖書館 內(nèi)蒙古 呼和浩特010021)2(內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院 內(nèi)蒙古 呼和浩特 010021)
一種基于馬爾科夫隨機(jī)場(chǎng)的蒙古文古籍圖像恢復(fù)方法
白淑霞1鮑玉來1*敖 權(quán)2
1(內(nèi)蒙古大學(xué)圖書館 內(nèi)蒙古 呼和浩特010021)2(內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院 內(nèi)蒙古 呼和浩特 010021)
針對(duì)蒙古文古籍圖像檢索領(lǐng)域中對(duì)同一查詢關(guān)鍵詞,不同的二值化算法對(duì)整體檢索性能影響問題,提出一種基于馬爾科夫隨機(jī)場(chǎng)的蒙古文古籍圖像二值化方法,從而提高蒙古文古籍圖像的檢索性能。利用馬爾科夫隨機(jī)場(chǎng)模型在灰度圖像和二值圖像之間建模,通過訓(xùn)練碼本估計(jì)隱藏層的先驗(yàn)概率,并分析灰度圖像的直方圖估計(jì)可觀察層的概率密度。利用這兩種先驗(yàn)知識(shí)實(shí)現(xiàn)圖像二值化。實(shí)驗(yàn)數(shù)據(jù)集為100頁(yè)蒙古文《甘珠爾經(jīng)》,為了驗(yàn)證本文所提方法的性能,實(shí)驗(yàn)采用R-Precision作為評(píng)價(jià)指標(biāo)。實(shí)驗(yàn)結(jié)果表明,基于馬爾科夫隨機(jī)場(chǎng)的二值化方法不僅可以有效修復(fù)受損圖像,還可以進(jìn)一步提高其檢索性能。
蒙古文古籍 文檔圖像檢索 圖像二值化 馬爾科夫隨機(jī)場(chǎng)
古籍文獻(xiàn)資料作為人類的寶貴文化遺產(chǎn),由于其具有珍貴的歷史和文物價(jià)值,它們大多被珍藏于博物館、圖書館,除了少數(shù)專家和學(xué)者之外,公眾很少有機(jī)會(huì)能翻閱它們。近年來,數(shù)字化技術(shù)的迅猛發(fā)展,進(jìn)一步推動(dòng)了古籍文獻(xiàn)資料(包括蒙古文古籍文獻(xiàn))向數(shù)字圖像的轉(zhuǎn)換工作,從而實(shí)現(xiàn)對(duì)古籍文獻(xiàn)資料的長(zhǎng)久保存。同時(shí),通過互聯(lián)網(wǎng),公眾可以便捷地翻閱這些古籍文獻(xiàn)的數(shù)字圖像。然而,古籍文獻(xiàn)的數(shù)字圖像只記錄了像素顏色、亮度等底層(圖像)信息,并沒有描述文獻(xiàn)內(nèi)容的高層(索引)信息,因此無(wú)法對(duì)其全文檢索。
在古籍圖像檢索領(lǐng)域HDIR(Historical Document Image Retrieval),詞定位技術(shù)能夠通過圖像匹配的方式從古籍圖像中定位(檢索)查詢關(guān)鍵詞出現(xiàn)的位置,并能夠較好地解決古籍圖像檢索中涉及的相關(guān)問題(如圖像質(zhì)量差、文字書寫不規(guī)范、變形嚴(yán)重等)[1]。在詞定位技術(shù)中,通常將古籍圖像集合表示成單詞圖像集合,即古籍圖像被分割成單詞圖像。在檢索時(shí),依據(jù)用戶提供的查詢關(guān)鍵詞的示例圖像,計(jì)算示例圖像與單詞圖像集合中每個(gè)單詞圖像之間的相似度,并按照相似度降序返回檢索結(jié)果[2]。
蒙古文古籍圖像檢索問題中已經(jīng)有應(yīng)用詞定位技術(shù)的先例。在之前的研究工作中,以清代康熙版(1720年印制)蒙古文《甘珠爾經(jīng)》為對(duì)象,通過以下方法實(shí)現(xiàn)蒙古文古籍圖像的檢索[3]:首先,每幅彩色掃描圖像先經(jīng)過預(yù)處理(包括灰度化、平滑濾波、二值化),被轉(zhuǎn)換成二值(黑白)圖像,再經(jīng)過版面分割,從中獲得相應(yīng)單詞圖像[4]。其次,分別從單詞圖像的每行和每列中提取如下輪廓特征:左輪廓、右輪廓、水平投影、水平方向筆劃穿越數(shù)、上輪廓、下輪廓、垂直投影和垂直方向筆劃穿越數(shù)。這樣,每個(gè)單詞圖像可被描述成與單詞圖像寬度相同的四個(gè)“行”特征向量和與單詞圖像高度相同的四個(gè)“列”特征向量[5]。然后,將單詞圖像的每個(gè)特征向量分別執(zhí)行離散傅里葉變換,僅保留頻域空間中前10個(gè)低頻復(fù)系數(shù)的模,從而可將每個(gè)單詞圖像表示成長(zhǎng)度為80維的特征向量[6]。最后,在檢索時(shí),通過提出的單詞圖像生成方法,由相應(yīng)字形拼接生成所需查詢關(guān)鍵詞的示例圖像;示例圖像也經(jīng)上述過程的處理,轉(zhuǎn)換成長(zhǎng)度為80維的特征向量;再通過計(jì)算示例圖像與其他單詞圖像特征向量之間的相似度可獲得檢索(排序)結(jié)果[7]。
為了提高檢索的精度,我們嘗試尋求更好的二值化方法。盡管蒙古文古籍文檔圖像的背景和光照強(qiáng)度變化并不劇烈,但是,由于蒙古文古籍風(fēng)化、破損嚴(yán)重,使得圖像本身包含很多破洞和掉色的情況,加之本實(shí)驗(yàn)使用的筆劃穿越數(shù)特征對(duì)圖像破洞十分敏感,預(yù)處理過程中,采用傳統(tǒng)的二值化方法很難獲得令人滿意的檢索效果。傳統(tǒng)的二值化方法[8-13]通過閾值分割將圖像上的每一個(gè)像素歸類為前景或背景,其中主要包括兩大類:全局閾值和局部適應(yīng)閾值。在全局閾值中,整張圖像只選取一個(gè)閾值,所有的像素灰度值通過與該閾值比較來確定其屬于前景或背景。Otsu算法[8]作為全局閾值的經(jīng)典算法,通過最大化類間方差來選取最佳的閾值。局部適應(yīng)閾值則是依據(jù)像素的鄰域塊的灰度分布來確定該像素位置上的二值化閾值,局部適應(yīng)閾值可以有效緩解光照變化劇烈?guī)淼挠绊?,但容易斷筆和偽影等現(xiàn)象。Niblack[11]、Sauvola[13]兩種算法是經(jīng)典的局部閾值算法。最近,馬爾科夫隨機(jī)場(chǎng)理論被用作圖像的二值化[14-17]。在文獻(xiàn)[16]中,Cao等首先將輸入觀察圖像y和輸出二值圖像x都分成大小相同且互不重復(fù)圖像塊yi和xi,利用馬爾科夫隨機(jī)場(chǎng)(MRF)模型來模擬相鄰圖像塊之間的條件依賴關(guān)系,通過求解最大化后驗(yàn)概率(MAP)來對(duì)圖像進(jìn)行二值化處理。
本文使用文獻(xiàn)[16]中所描述的MRF模型,該MRF模型被定義為G={V,E}的圖模型。該模型中,二值圖像被分割成不重疊的方塊x1,x2,…,xN,并且觀察圖像也被分割成同樣大小y1,y2,…,yN,其中1≤i≤N,二值圖像塊xi與觀察圖像塊yi相對(duì)應(yīng),并且xi,yi∈V。二維馬爾科夫隨機(jī)場(chǎng)模型中存在兩種不同的邊,其中一種邊用來連接節(jié)點(diǎn)xi和節(jié)點(diǎn)xj,xj表示xi水平方向和垂直方向上的四個(gè)相鄰節(jié)點(diǎn),可以表述為:每一個(gè)二值圖像塊在水平和垂直方向上條件依賴該塊的四個(gè)相鄰塊;另一種邊用來連接節(jié)點(diǎn)xi和yi,表示xi條件依賴yi,用來表達(dá)二值圖像和灰度圖像之間的條件依賴。條件依賴關(guān)系可以由下面公式表示:
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的四個(gè)鄰接圖像塊,觀察圖像塊與二值圖像塊之間的條件依賴關(guān)系可以表示為:
P(yi|x1,x2,…,xN,y1,y2,…,yi-1,yi+1,…,yN)=
P(yi|xi) 1≤i≤N
(2)
二維MRF模型表示如圖1所示。
圖1 二維馬爾科夫隨機(jī)場(chǎng)模型
(3)
直接通過式(3)計(jì)算xj是不太現(xiàn)實(shí)的,因?yàn)殡S著節(jié)點(diǎn)個(gè)數(shù)的增加,計(jì)算量會(huì)呈指數(shù)形式增長(zhǎng)。利用置信傳播(BP)[16]迭代的方式來近似MAP估計(jì)為本文提供了一種解決方法,該方法的計(jì)算量隨節(jié)點(diǎn)個(gè)數(shù)增加呈線性增長(zhǎng)。
為了通過MRF模型得到優(yōu)化的二值化圖像,需要按照?qǐng)D2所示的流程,即:將MRF模型定義為二維圖模型,然后通過計(jì)算MAP來估計(jì)最終的二值圖像。其中,計(jì)算MAP,首先利用置信傳播(BP)迭代計(jì)算,再進(jìn)行二值塊先驗(yàn)概率估計(jì),最后估算觀察模型。
圖2 馬爾科夫隨機(jī)場(chǎng)(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ù)取對(duì)數(shù):
(12)
(13)
置信傳播算法的參考代碼如下:
Function reco_image=belief_propagation(test_image,patch)
% 文中1.1節(jié)算法實(shí)現(xiàn)
% 置信傳播(belief_propagation)算法,通過迭代的方式回復(fù)出二值圖像
% 輸入?yún)?shù):test_image待恢復(fù)圖像,patch為碼本(對(duì)應(yīng)本文圖3)
% 輸出參數(shù):reco_image恢復(fù)后圖像
patch_size=size(patch,1);
patch_num=size(patch,3);
%采用文獻(xiàn)[8]的方法估計(jì)前景和背景的均值與方差,并
%將灰度圖進(jìn)行二值化
[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]);
% 計(jì)算式(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
% 調(diào)用式(13)
L_jk=max_xk(hor_num,ver_num,patch,L_jk,log_hor_xk_xj,log_ver_xk,xj,log_x);
% 調(diào)用式(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
%得到最終恢復(fù)圖像
reco_image=reshape(bina_patch,[hor_num,ver_num])&bina_image;
end
1.2 二值塊先驗(yàn)概率
為了求解P(xj)和P(xk|xj),首先想到能否直接統(tǒng)計(jì)xj出現(xiàn)的每一種情況的概率,顯然這樣是不行的。假設(shè)選用的圖像塊的大小為b×b,那么xj所有可能的情況會(huì)有2b2種,當(dāng)b=15時(shí),xj所有可能出現(xiàn)的情況有2225種,這樣大的計(jì)算量遠(yuǎn)遠(yuǎn)超出了實(shí)驗(yàn)室計(jì)算機(jī)的計(jì)算能力。由于所用圖像之間及內(nèi)部存在大量的相似的圖像塊(patch),訓(xùn)練碼本為本實(shí)驗(yàn)提供了一種可行的解決思路:利用碼本中少量的碼字來近似表達(dá)圖像塊所有可能出現(xiàn)的情況,將碼字作為訓(xùn)練集中圖像塊{pi}的代表,從而使得計(jì)算變得可行。
(14)
(15)
圖3 233個(gè)碼字組成的碼本
(16)
其中l(wèi)1,l2=1,2,…,M。以水平方向?yàn)槔?pi1,pi2)表示訓(xùn)練樣本中相鄰的兩個(gè)圖像塊,并且pi1在pi2的左邊,Npi1·pi2表示水平相鄰塊的總對(duì)數(shù)。
1.3 觀察模型
(17)
可以證明:
(18)
(19)
觀察模型的參考代碼如下所示:
% 文中1.3節(jié)算法實(shí)現(xiàn),用以計(jì)算原始圖像每個(gè)patch與碼本
%的條件概率,即,式(19)
% 輸入?yún)?shù):gray_patch原始圖像的patch,bina_patch為第k個(gè)
%碼本
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.1 實(shí)驗(yàn)數(shù)據(jù)集
本實(shí)驗(yàn)采用的數(shù)據(jù)集是從內(nèi)蒙古大學(xué)圖書館獲取的100頁(yè)蒙古文《甘珠爾經(jīng)》的彩色掃描圖像,掃描分辨率為600 DPI。每幅彩色掃描圖像均經(jīng)過文獻(xiàn)[4]提出的預(yù)處理方法,被轉(zhuǎn)換為灰度圖像,并通過版面分析共獲得24 827個(gè)單詞(灰度)圖像。本實(shí)驗(yàn)將對(duì)這些單詞(灰度)圖像使用本文提出的MRF算法進(jìn)行二值化。
為了便于統(tǒng)計(jì)相關(guān)性能指標(biāo),數(shù)據(jù)集的每一頁(yè)掃描圖像都采用Unicode編碼進(jìn)行了文本標(biāo)注。該實(shí)驗(yàn)數(shù)據(jù)集已被用于統(tǒng)計(jì)文獻(xiàn)[3]中檢索系統(tǒng)的性能。在本研究中,繼續(xù)沿用文獻(xiàn)[3]使用的查詢關(guān)鍵詞(一個(gè)“查詢關(guān)鍵詞”相當(dāng)于文本信息檢索中的一個(gè)“Topic(主題)”),共計(jì)20個(gè)。這些查詢關(guān)鍵詞是對(duì)100頁(yè)掃描圖像的文本標(biāo)注統(tǒng)計(jì)詞頻之后隨機(jī)挑選出來的。挑選標(biāo)準(zhǔn)是詞頻(出現(xiàn)次數(shù))不少于20次,且具有實(shí)際意義的單詞(如名詞、動(dòng)詞等),如表1所示。
表1 查詢關(guān)鍵詞列表
2.2 實(shí)驗(yàn)直觀結(jié)果對(duì)比
在蒙古文古籍圖像檢索以前的研究中,《甘珠爾經(jīng)》曾被嘗試多種方法二值化,例如Otsu算法[8]、Kittler算法[9]和FCM算法[10],但二值化結(jié)果都不太理想。在先前的圖像檢索中,本文使用Otsu、Kittler和FCM三種算法的綜合結(jié)果,即三種算法投票的方式,若兩種或三種算法將某一像素歸類為前景或背景,則該像素為前景或背景。實(shí)驗(yàn)結(jié)果對(duì)比如圖4所示,(a)、(d)為原始破損灰度圖像,(b)、(e)為采用FCM、Kittler和Otsu投票二值化之后的二值圖像,(c)、(f)為采用MRF算法二值化之后的二值圖像。
圖4 二值化效果對(duì)比
2.3 評(píng)價(jià)指標(biāo)
本文采用的性能評(píng)價(jià)指標(biāo)是信息檢索中常用的R-Precision。R-Precision的定義如下[19]:
(20)
其中,Rel是表示與與查詢關(guān)鍵詞相關(guān)的單詞個(gè)數(shù),r表示在是前Rel個(gè)檢索結(jié)果中出現(xiàn)的相關(guān)單詞的個(gè)數(shù)。如果相關(guān)單詞出現(xiàn)在前Rel個(gè)檢索結(jié)果中的數(shù)目越多,則R-Precision的值越高,其最大值為1(前Rel個(gè)檢索結(jié)果中全部為相關(guān)單詞),最小值為0(前Rel個(gè)檢索結(jié)果中無(wú)相關(guān)單詞)。對(duì)每個(gè)查詢關(guān)鍵詞,可按上述公式由其檢索結(jié)果計(jì)算各自的R-Precision。
2.4 實(shí)驗(yàn)過程、結(jié)果與分析
在實(shí)驗(yàn)中,對(duì)每個(gè)查詢關(guān)鍵詞都執(zhí)行以下過程:首先利用本文中所述的方法來對(duì)圖像進(jìn)行二值化;第二步,在二值圖像的基礎(chǔ)上提取本實(shí)驗(yàn)所需要的80維輪廓特征;接下來,將該特征放到特征庫(kù)匹配,按相似度降序形成的檢索結(jié)果(單詞圖像列表);最后統(tǒng)計(jì)結(jié)果中的R-Precision指標(biāo)(如圖5所示)。
圖5 每個(gè)關(guān)鍵字的R-Precision
從圖5可以看出,使用MRF之后大部分查詢關(guān)鍵詞的檢索性能都有所提高,部分查詢關(guān)鍵詞的檢索性能未發(fā)生變化。
本文采用了一種更加適合蒙古文古籍文檔檢索中預(yù)處理的二值化算法。該方法能夠緩解低質(zhì)量古籍文檔中的因?yàn)槠茡p、掉色造成的圖像信息損失,不僅在視覺上獲得了比較好的結(jié)果,而且也提高了檢索性能。從整體來看,不使用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 技術(shù)的蒙古文古籍圖像檢索中的特征選擇[J].計(jì)算機(jī)應(yīng)用, 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。國(guó)家自然科學(xué)基金項(xiàng)目(71163029)。白淑霞,館員,主研領(lǐng)域:蒙古文信息檢索。鮑玉來,副研究館員。敖權(quán),本科。
TP319.3
A
10.3969/j.issn.1000-386x.2017.04.035