基于局部離群因子和波動(dòng)閾值的古籍版面圖像分析方法

賈 運(yùn)， 田學(xué)東， 左麗娜

(河北大學(xué)網(wǎng)絡(luò)空間安全與計(jì)算機(jī)學(xué)院， 保定 071002)

中國歷史悠久，珍貴的古籍藏書豐富。隨著計(jì)算機(jī)技術(shù)的高速發(fā)展，利用計(jì)算機(jī)輔助古籍研究是必由之路。古籍文獻(xiàn)版面成分豐富，除漢字外，還包括雕版印刷框線、插圖等成分，需要自動(dòng)、高效地對其進(jìn)行分析，定位其中的字形成分，以便通過文字切分提取出單個(gè)的漢字圖像，從而為實(shí)現(xiàn)古籍漢字圖像的識(shí)別與檢索打下基礎(chǔ)。

目前，專門針對古籍文獻(xiàn)圖像的版面分析研究相對較少，可供參考的是傳統(tǒng)的面向印刷文獻(xiàn)的版面分析方法，包括自頂向下方法、自底向上方法和混合方法等3類[1-2]?；谕队暗姆椒ㄊ亲畹湫偷淖皂斚蛳路椒?，該方法簡單且速度快，適用于排版規(guī)范的版面，復(fù)雜版面效果不佳。自底向上方法的代表是基于連通區(qū)域分析的方法，此法可處理復(fù)雜版面，但計(jì)算量較大且效率低?；旌戏椒ㄊ菍⒆皂斚蛳潞妥缘紫蛏蟽煞N方法組合運(yùn)用，解決了單一方法的不足。

針對排版較為規(guī)范的印刷文檔版面圖像，研究者提出了多種版面分析方法。Dai-Ton等[3]提出自適應(yīng)過分割和融合的印刷版面分割方法。利用背景白色矩形信息將圖像過分割，通過連通區(qū)域分析得到候選文本，根據(jù)預(yù)定義的規(guī)則將字體大小相同、距離相近的候選文本組合成一個(gè)連通區(qū)域，使用段落分布模型將不同段落分割開。此方法在處理現(xiàn)代報(bào)紙、雜志等出版物取得了較好的效果。Yadav等[4]提出基于角點(diǎn)檢測的圖像文本塊提取方法，將文本圖像均分成較小的塊, 利用角點(diǎn)密度對圖像塊進(jìn)行分類。此方法在不同語言的印刷圖像數(shù)據(jù)集上都得到了較好的結(jié)果。段露等[5]提出連通區(qū)域和神經(jīng)網(wǎng)絡(luò)相結(jié)合的問卷圖像版面分析方法，利用水平投影分割圖像得到問卷行，提取問卷行首個(gè)連通區(qū)域定位圖像表格問卷行，并對其進(jìn)行表格區(qū)域分布分析和表格類型判斷,得到可能的答案區(qū)域，利用神經(jīng)網(wǎng)絡(luò)篩選答案區(qū)域的類型，得到最終的答案填寫區(qū)域。該算法可以準(zhǔn)確地識(shí)別各種問卷圖像中的信息填寫區(qū)域。任榮梓等[6]提出基于反饋合并的中英文混排印刷文檔圖像版面分析方法，采用投影法分割圖像，設(shè)立評估系數(shù)、評估標(biāo)志位和反饋因子實(shí)現(xiàn)粘連字符的檢測和二次分割。該方法成功分離出中英文混合文檔中的中文、英文和數(shù)字字符，較好地解決了傳統(tǒng)方法對粘連字符處理效果不佳的問題。郭曉宇等[7]提出基于連通區(qū)域的傳真圖像版面分割與分類算法，以連通區(qū)域?yàn)閱挝?，通過合并連通區(qū)域快速分割圖像，根據(jù)區(qū)域的大小建立矩陣，提取表征區(qū)域信息的八維特征，使用BP神經(jīng)網(wǎng)絡(luò)進(jìn)行分類。該方法優(yōu)點(diǎn)為分類過程充分使用分割過程獲取的信息，減小了計(jì)算量,提高了運(yùn)算速度。

近年來，隨著古籍文獻(xiàn)數(shù)字化和相關(guān)研究的深入，對古籍圖像的版面分析方法研究受到關(guān)注，該類方法多依賴于所處理圖像的版面特點(diǎn)，通常針對不同的古籍版面布局使用特定的版面分析方法。Chen等[8]提出基于超像素分類的無監(jiān)督學(xué)習(xí)方法來分析歷史文獻(xiàn)版面，利用簡單線性迭代聚類(simple linear iterative clustering，SLIC)算法將歷史文獻(xiàn)圖像過度分割為超像素，通過堆疊卷積自動(dòng)編碼器提取超像素特征，使用支持向量機(jī)(support vector machine，SVM)分類器對超像素進(jìn)行分類。與原有方法相比，此方法具有更快的速度和更好的性能。Bukhari等[9]提出基于機(jī)器學(xué)習(xí)的手寫阿拉伯歷史文獻(xiàn)圖像版面分割方法，提取連通區(qū)域的形狀特征和上下文特征組成特征向量，利用自多層感知機(jī)(auto multi-layer perception，AutoMLP)分類器并結(jié)合最近鄰分析實(shí)現(xiàn)正文和側(cè)邊注釋的分割。張西群等[10]提出基于卷積降噪自編碼器的藏文歷史文獻(xiàn)版面分析方法，對藏文歷史文獻(xiàn)進(jìn)行超像素聚類，訓(xùn)練卷積降噪自編碼器提取特征，使用SVM分類器進(jìn)行分類預(yù)測，最終實(shí)現(xiàn)了對藏文歷史文獻(xiàn)的不同版面元素的有效分離。

上述版面分析方法在各自的適用范圍上取得良好的效果。由于古籍版面的規(guī)范度遠(yuǎn)低于現(xiàn)代印刷版面，且年代久遠(yuǎn)，版面質(zhì)量退化現(xiàn)象較為普遍，需要有針對性地開展研究?，F(xiàn)面向《四庫全書》版面，基于對其版面特點(diǎn)的分析與歸納，提出基于局部離群因子(local outlier factor，LOF)和波動(dòng)閾值的古籍圖像版面分析方法，通過版面分析、分割過程中所需閾值動(dòng)態(tài)獲取等措施，增強(qiáng)算法對古籍文獻(xiàn)版面的適應(yīng)性。

1 基于LOF和波動(dòng)閾值的古籍版面分析

基于LOF和波動(dòng)閾值的古籍版面分析流程如圖1所示。

圖1 古籍圖像版面分析流程Fig.1 The flow chart of the layout image analysis of ancient Chinese books

首先，采用基于LOF的分類算法對古籍圖像投影分割后的版面區(qū)域進(jìn)行分類；然后，利用波動(dòng)閾值對文字與框線相粘連的版面混合區(qū)域進(jìn)行分割；最后，確定古籍版面中的文字區(qū)域并輸出。

1.1 古籍版面圖像特征分析

《四庫全書》中的版面遵循如下規(guī)范[11-12]。

(1)版面框線采用雕版印刷，最外側(cè)有一個(gè)雙邊矩形邊框，內(nèi)部有若干道間距相等的分隔框線。

(2)版面文字有大有小，大小字在同一行混合豎排列，其中單排大字為正文文字，雙排小字為注文文字。

(3)版面內(nèi)有16列豎排文字行，在正中間有一列版心(版心左右各有8列文字行)。

(4)版心裝飾為紅色單魚尾，魚尾上載“欽定四庫全書”，魚尾下文字雙行夾寫，右載書名，左載卷數(shù)，再下僅于橫線上右面注頁數(shù)。

一幅典型的《四庫全書》版面圖像的成分分布情況如圖2所示。

圖2 《四庫全書》版面圖像的成分分布情況Fig.2 Composition distribution of layout image for Imperial Collection of Four

除上述提到的規(guī)范外，《四庫全書》版面還存在不少特殊情況。通過對2 000多幅《四庫全書》版面圖像的分析，歸納出古籍圖像版面具有以下分析特征：①文字與相鄰框線發(fā)生粘連的情況很多;②圖像退化嚴(yán)重，邊框線不完整或者彎曲、文字行間框線不連續(xù)和傾斜。

1.2 基于LOF的古籍版面區(qū)域分類

針對古籍版面分析特征，采用X-Y投影法[13-14]對古籍圖像進(jìn)行版面分割。根據(jù)框線與文字之間的空白行，通過區(qū)域內(nèi)容差異判別方法，將所得到的區(qū)域分為框線區(qū)域、文字區(qū)域和混合區(qū)域等3種類型，如圖3所示。其中，框線區(qū)域中僅包含獨(dú)立的橫豎框線，其按框線方向可分為水平或豎直框線區(qū)域；文字區(qū)域僅包含獨(dú)立的文字行；混合區(qū)域?yàn)槲淖峙c框線粘連的區(qū)域。

圖3 古籍圖像版面區(qū)域類型Fig.3 Types of the layout areas in ancient Chinese books image

定義1 設(shè)古籍圖像版面區(qū)域Di為四元組，即

Di=(ADi，Xis，Xie，WYmax_i)

(1)

式(1)中：ADi為版面區(qū)域Di的方向?qū)傩?，ADi=0：水平，ADi=1：豎直；(Xis,0)、(Xie,0)分別是版面區(qū)域Di投影曲線的起點(diǎn)、終點(diǎn)坐標(biāo)；WYmax_i為投影曲線的最大峰值。

定義2 設(shè)版面區(qū)域Di的寬度、面積特征分別為

WDi=Xie-Xis

(2)

SDi=(Xie-Xis)WYmax_i

(3)

根據(jù)方向?qū)傩訟Di=0，快速分類出水平框線。豎直框線寬度一般是固定的或者是有限的幾個(gè)值，其值遠(yuǎn)小于其他兩類。使用寬度均值TL來衡量豎直框線與其他區(qū)域的差異，計(jì)算公式為

(4)

式(4)中：m為古籍圖像分割后版面區(qū)域個(gè)數(shù)。

混合區(qū)域面積大于文字區(qū)域，利用這兩類區(qū)域的平均面積來衡量二者的差異。但古籍版面中存在一些異常區(qū)域，這些區(qū)域的面積極大或極小，影響了分類文字區(qū)域和混合區(qū)域的正確率，采用LOF算法將其剔除。

LOF[15-18]是一種經(jīng)典的異常點(diǎn)檢測算法，該算法通過計(jì)算數(shù)據(jù)集中每個(gè)數(shù)據(jù)點(diǎn)的局部離群因子值來確定該點(diǎn)是否是異常點(diǎn)，且離群因子越大是異常點(diǎn)的可能性越大?；谖墨I(xiàn)[19]的研究，局部異常點(diǎn)的離群程度和其他數(shù)據(jù)點(diǎn)的分布有關(guān)。涉及的相關(guān)定義如下。

定義3k距離：設(shè)k為任意的正整數(shù)，數(shù)據(jù)點(diǎn)q的k距離是數(shù)據(jù)集B中到q距離最近的第k個(gè)點(diǎn)與點(diǎn)q之間的距離，記作k-distance(q)。

定義4k距離鄰域：數(shù)據(jù)集B中與點(diǎn)q的距離不超過k距離的所有數(shù)據(jù)點(diǎn)的集合，即為

Nk-distance(q)={p∈B/{q}|d(q,p)≤k-distance(q)}

(5)

式(5)中：Nk-distance(q)簡記為Nk(q)；d(q,p)表示p到q的歐氏距離。

定義5 可達(dá)距離：點(diǎn)q到其k距離鄰域中點(diǎn)p的可達(dá)距離定義為

reach-distk(p,q)=max[k-distance(q),

d(p,q)]

(6)

定義6 局部可達(dá)密度：點(diǎn)q的局部可達(dá)密度是點(diǎn)q到其k距離鄰域內(nèi)所有數(shù)據(jù)點(diǎn)的平均可達(dá)距離的倒數(shù)，即

(7)

式(7)中：|Nk(q)|是q的k距離鄰域內(nèi)點(diǎn)個(gè)數(shù)。

定義7 局部離群因子：數(shù)據(jù)點(diǎn)的離群程度，計(jì)算公式為

(8)

在實(shí)際應(yīng)用中LOF算法存在如下兩個(gè)缺陷[20]。

(1)若數(shù)據(jù)集已確定，離群因子值只和參數(shù)k有關(guān)。當(dāng)k取值不同時(shí)，之前是離群點(diǎn)的數(shù)據(jù)可能不再是離群點(diǎn)。

(2)對于未知離群點(diǎn)個(gè)數(shù)的數(shù)據(jù)集，選擇參數(shù)k以保證離群點(diǎn)的挖掘數(shù)量合理難以做到。

為了削弱k值對實(shí)驗(yàn)的影響，文獻(xiàn)[21]對參數(shù)k設(shè)定了一個(gè)范圍，k∈[Minpts,Maxpts]。對于每一個(gè)k，算法執(zhí)行一次后都會(huì)得到一個(gè)離群因子。針對k的所有取值分別執(zhí)行算法，對每個(gè)點(diǎn)獲得的離群因子求均值，即

(9)

式(9)中：Minpts=1，Maxpts為B中數(shù)據(jù)點(diǎn)個(gè)數(shù)。

若SLOF(q)遠(yuǎn)大于1，則點(diǎn)q的密度與所有數(shù)據(jù)點(diǎn)的密度差異較大，視為離群點(diǎn)。若SLOF(q)越趨近于1，則點(diǎn)q越正常。

定義8 設(shè)TF為衡量文字區(qū)域與混合區(qū)域差異的閾值，計(jì)算公式為

(10)

式(10)中：n為離群點(diǎn)個(gè)數(shù)；C為離群點(diǎn)集；μ為浮動(dòng)參數(shù)，經(jīng)大量實(shí)驗(yàn)樣本驗(yàn)證得到μ∈[0,0.15]，使用μ對閾值TF進(jìn)行細(xì)微調(diào)節(jié)。分離古籍版面區(qū)域的具體過程如算法1所示。

算法1基于LOF的古籍版面區(qū)域分類算法：

輸入已初始分割的版面區(qū)域。

輸出存在分割問題的候選混合區(qū)域集V。

步驟1利用式(4)計(jì)算框線區(qū)域分離閾值TL。

步驟2設(shè)定參數(shù)k范圍，并對每一個(gè)k值，利用式(7)、式(8)計(jì)算每個(gè)對象的局部可達(dá)密度及局部離群因子。

步驟3利用式(9)計(jì)算每個(gè)對象所有k值的均值離群因子，獲取離群點(diǎn)個(gè)數(shù)n及離群點(diǎn)集C。

步驟4利用式(10)計(jì)算衡量文字區(qū)域與混合區(qū)域差異的閾值TF。

1.3 基于波動(dòng)閾值的版面混合區(qū)域分割

古籍版面混合區(qū)域內(nèi)的文字和框線存在多個(gè)交點(diǎn)，如果將所有交點(diǎn)逐一檢測并進(jìn)行分割，計(jì)算量大且費(fèi)時(shí)。利用混合區(qū)域投影曲線中字與框線的粘連分割點(diǎn)來代替實(shí)際所有交點(diǎn)，如圖4所示。

圖4 混合區(qū)域投影曲線Fig.4 The projection curve of mixed area

粘連分割點(diǎn)表現(xiàn)為波動(dòng)尺度較大的波谷點(diǎn)，因此曲線上的大尺度波谷點(diǎn)都可能是粘連分割位置。曲線上潛在的波谷點(diǎn)或波峰點(diǎn)分別為

(11)

假設(shè)上一輪已成功定位滿足波動(dòng)閾值的波谷點(diǎn)Pn，Pn和下一個(gè)待搜索波谷點(diǎn)之間存在若干小尺度波峰點(diǎn)，設(shè)Pj[tj,W(tj)]是Pi[ci,W(ci)]之后的一個(gè)波谷點(diǎn)，則

n

(12)

如果使得Pi[ci,W(ci)]和Pj[tj,W(tj)]滿足：

W(ci)-W(tj)>threshod

(13)

那么Pj即為下一個(gè)大尺度波谷點(diǎn)。

上述大尺度波谷點(diǎn)搜索過程中，所用波動(dòng)閾值計(jì)算公式為

threshod=|W(ctop)-W(tbot)|

(14)

在大尺度波谷點(diǎn)集合ΩPj={P1,P2,…,Pj,Pt,…,Pm}中，對于任意3個(gè)相鄰的波谷點(diǎn)Pt-1、Pt、Pt+1，兩兩橫向距離分別為dt-1,t和dt，t+1，若滿足：

(15)

則判定Pt這個(gè)點(diǎn)是粘連分割點(diǎn)。式(15)中：α=[Lmin,Lmax]，Lmax和Lmin分別是框線的最大寬度和最小寬度。最后通過直線x=Pt將混合區(qū)域中的文字與框線分割開?；旌蠀^(qū)域粘連分割的具體步驟如算法2所示。

算法2基于波動(dòng)閾值的版面混合區(qū)域分割算法：

輸入候選混合區(qū)域v。

輸出混合區(qū)域粘連分割點(diǎn)坐標(biāo)Pt。

步驟1設(shè)上一輪已成功定位滿足波動(dòng)閾值的波谷點(diǎn)Pn，下一個(gè)待檢測大尺度波谷點(diǎn)為Pj，利用式(12)求取Pn與Pj之間的最大高度波峰Pi。

步驟2若Pi和Pj滿足不等式(13)，則Pj即為新一輪搜索到的滿足波動(dòng)閾值的波谷點(diǎn)，并存入集合ΩPj；否則j=j+1。

步驟3若Pj不等于終點(diǎn)坐標(biāo)(Xie,0)，繼續(xù)執(zhí)行步驟1～2；否則執(zhí)行步驟4。

步驟4將所得集合ΩPj中任意3個(gè)相鄰的波谷點(diǎn)Pt-1、Pt、Pt+1，兩兩計(jì)算橫向距離。若滿足式(15)，則Pt為粘連分割點(diǎn)；否則t=t+1，繼續(xù)執(zhí)行步驟4。

2 實(shí)驗(yàn)結(jié)果與分析

2.1 版面分類結(jié)果分析

從《四庫全書》中任意選取了4 080幅圖像作為版面分類的實(shí)驗(yàn)樣本，用NYB表示。為驗(yàn)證分類算法的優(yōu)劣，使用準(zhǔn)確率P和召回率R對分類結(jié)果進(jìn)行評價(jià)。準(zhǔn)確率和召回率公式為

(16)

(17)

式中：A表示類別中的某一類；NAR為A中分類正確的區(qū)域個(gè)數(shù)；NA為分類為A的區(qū)域個(gè)數(shù)；ND為樣本中A的實(shí)際個(gè)數(shù)。

在實(shí)驗(yàn)中，選擇文獻(xiàn)[7]中的版面分類算法作為對比算法。需要注意的是，由于對原文獻(xiàn)方法理解程度以及所采用實(shí)驗(yàn)樣張方面的差異，本文的對比實(shí)驗(yàn)結(jié)果只是在一定程度上反映了算法的實(shí)際情況。

按式(16)、式(17)計(jì)算得到的評價(jià)值如表1所示，其中，最后的實(shí)驗(yàn)結(jié)果由樣本圖像的平均值得出。

從表1可以看出，本文算法分類結(jié)果的準(zhǔn)確率和召回率分別達(dá)到了87.02%、81.31%，優(yōu)于文獻(xiàn)[7]算法。但實(shí)驗(yàn)結(jié)果中存在分類錯(cuò)誤的版面區(qū)域，主要原因是古籍圖像退化嚴(yán)重，版面內(nèi)存在較多噪聲，部分文字區(qū)域與混合區(qū)域特征極為相似，從而導(dǎo)致分類錯(cuò)誤。

表1 版面分類實(shí)驗(yàn)結(jié)果Table 1 Experimental results of layout classification

2.2 混合區(qū)域粘連分割結(jié)果分析

從4 080幅樣本中挑選存在粘連問題較多的759幅圖像作為實(shí)驗(yàn)樣本，經(jīng)版面分割后共得到3 952幅混合區(qū)域圖像。對其進(jìn)行人工分類，其中包括單排大字圖像1 064幅，中間版心圖像759幅，雙排小字圖像2 129幅。為評價(jià)混合區(qū)域粘連分割的效果，定義分割準(zhǔn)確率PG為

(18)

式(18)中：NR為準(zhǔn)確分割圖像個(gè)數(shù)；N為混合區(qū)域圖像個(gè)數(shù)。

實(shí)驗(yàn)發(fā)現(xiàn)，版面分割結(jié)果的優(yōu)劣僅通過準(zhǔn)確率來判斷不夠充分。混合區(qū)域分割過程中，圖像傾斜、粘連框線不完整、波動(dòng)閾值選取不合適等因素都會(huì)使實(shí)際的粘連分割點(diǎn)定位困難，導(dǎo)致分割結(jié)果中殘余小部分框線。這些短小框線并不影響后續(xù)的漢字切分等環(huán)節(jié)，故將這類圖像定義為微錯(cuò)分割圖像，并在原有基礎(chǔ)上加入了微錯(cuò)分割準(zhǔn)確率[22]PW的評價(jià)標(biāo)準(zhǔn)：

(19)

式(19)中：NW為微錯(cuò)分割圖像個(gè)數(shù)。

版面分割結(jié)果如表2所示。從表2可以看出，本文算法切分單排大字效果最好，分割準(zhǔn)確率和微錯(cuò)分割準(zhǔn)確率分別為87.97%、91.92%；中間版心效果次之，分割準(zhǔn)確率和微錯(cuò)分割準(zhǔn)確率分別為83.14%、86.17%；雙排小字粘連分割效果最差，分割準(zhǔn)確率只有72.47%。最后通過計(jì)算上述3種圖像的平均值得到最終的版面分割實(shí)驗(yàn)結(jié)果，分割準(zhǔn)確率和微錯(cuò)分割準(zhǔn)確率分別為78.69%、81.30%。

表2 版面分割實(shí)驗(yàn)結(jié)果Table 2 Experimental results of layout segmentation

2.3 時(shí)間性能分析

(20)

式(20)中：T為樣本圖像版面分析所用的總時(shí)間。

算法時(shí)間數(shù)據(jù)如表3所示。從表3可以看出，本文算法耗時(shí)少于文獻(xiàn)[7]。因?yàn)楹笳咭赃B通區(qū)域?yàn)樘幚碓? 重復(fù)合并連通區(qū)域分割圖像，并選取BP神經(jīng)網(wǎng)絡(luò)進(jìn)行版面分類，增加了時(shí)間復(fù)雜度。而本文算法根據(jù)投影分割后的版面區(qū)域特征的明顯差異求取分類閾值，整個(gè)版面分析過程中未使用結(jié)構(gòu)復(fù)雜的模型。

表3 兩種算法時(shí)間性能對比Table 3 Comparison of time performance of two algorithms

圖5所示為本文算法對一幅古籍文獻(xiàn)版面圖像的分析結(jié)果，框線區(qū)域用藍(lán)顏色標(biāo)記?？梢钥闯鑫淖謪^(qū)域完整性較高，能較好地解決古籍版面框線影響文字切分的問題。

圖5 版面分析結(jié)果Fig.5 The results of layout analysis

3 結(jié)論

基于對《四庫全書》版面特點(diǎn)的分析與歸納，提出了一種基于LOF和波動(dòng)閾值的古籍版面分析方法。首先，采用基于LOF的分類算法對古籍圖像投影分割后的版面區(qū)域進(jìn)行分類；然后，利用波動(dòng)閾值對文字與框線相粘連的版面混合區(qū)域進(jìn)行分割；最后，將古籍版面中的文字區(qū)域輸出。實(shí)驗(yàn)證明，在古籍圖像具有一定程度傾斜、文字與框線存在較多粘連、框線大多不完整的情況下，本文方法分離古籍版面文字區(qū)域和框線區(qū)域仍具有較好的效果。同時(shí)本文設(shè)計(jì)的算法結(jié)構(gòu)簡單，執(zhí)行速度較快，版面分析耗時(shí)較少。但也存在一些不足，對于蓋有印章的古籍圖像，印章與文字、框線交織在一起，三者的分離較為困難，分析準(zhǔn)確率受到影響，后續(xù)將繼續(xù)研究改進(jìn)。