東巴象形文字文檔圖像的文本行自動(dòng)分割算法研究

康厚良，楊玉婷

東巴象形文字文檔圖像的文本行自動(dòng)分割算法研究

康厚良1，楊玉婷2

(1. 蘇州市職業(yè)大學(xué)體育部，江蘇 蘇州 215000；2. 蘇州市職業(yè)大學(xué)計(jì)算機(jī)工程學(xué)院，江蘇 蘇州 215000)

以卷積神經(jīng)網(wǎng)絡(luò)(CNN)為代表的深度學(xué)習(xí)技術(shù)在圖像分類(lèi)和識(shí)別領(lǐng)域表現(xiàn)出了非常優(yōu)異的性能。但東巴象形文字未有標(biāo)準(zhǔn)、公開(kāi)的數(shù)據(jù)集，無(wú)法借鑒或使用已有的深度學(xué)習(xí)算法。為了快速建立權(quán)威、有效的東巴文字庫(kù)，分析已出版東巴文檔的版面結(jié)構(gòu)，從文檔中提取文本行、東巴字成為了當(dāng)前的首要任務(wù)。因此，結(jié)合東巴象形文字文檔圖像的結(jié)構(gòu)特點(diǎn)，給出了東巴文檔圖像的文本行自動(dòng)分割算法。首先利用基于密度和距離的k-均值聚類(lèi)算法確定了文本行的分類(lèi)數(shù)量和分類(lèi)標(biāo)準(zhǔn)；然后，通過(guò)文字塊的二次處理矯正了分割中的錯(cuò)誤結(jié)果，提高了算法的準(zhǔn)確率。在充分利用東巴字文檔結(jié)構(gòu)特征的同時(shí)，保留了機(jī)器學(xué)習(xí)模型客觀、無(wú)主觀經(jīng)驗(yàn)影響的優(yōu)勢(shì)。通過(guò)實(shí)驗(yàn)表明，該算法可用于東巴文檔圖像、脫機(jī)手寫(xiě)漢字、東巴經(jīng)的文本行分割，以及文本行中東巴字和漢字的分割，具有實(shí)現(xiàn)簡(jiǎn)單、準(zhǔn)確性高、適應(yīng)性強(qiáng)的特點(diǎn)，從而為東巴文字庫(kù)的建立奠定基礎(chǔ)。

東巴象形文字；東巴文檔分析；文本行分割；投影分割；d-K-means

1 東巴象形文字手寫(xiě)文檔分析

東巴文是一種十分原始的圖畫(huà)象形文字，是人類(lèi)早期圖畫(huà)文字中象形文字、標(biāo)音文字過(guò)渡的一種文字形式[1-2]，主要是由東巴法師用于抄寫(xiě)經(jīng)文。由于其還未發(fā)展成為一種字形比較固定、統(tǒng)一的表意文字[3-4]，因書(shū)寫(xiě)的東巴法師不同而具有明顯的個(gè)體差異性，導(dǎo)致非常多異體字[5]的存在，使得通過(guò)計(jì)算機(jī)實(shí)現(xiàn)東巴字的自動(dòng)識(shí)別面臨很多挑戰(zhàn)。

隨著以卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural networks，CNN)為代表的深度學(xué)習(xí)技術(shù)的設(shè)計(jì)越來(lái)越深層化，圖像特征的標(biāo)識(shí)能力越來(lái)越強(qiáng)，深度學(xué)習(xí)在圖像分類(lèi)和識(shí)別領(lǐng)域表現(xiàn)出了非常優(yōu)異的性能[6-8]。但深度學(xué)習(xí)的優(yōu)勢(shì)有賴(lài)于大數(shù)據(jù)，數(shù)據(jù)量的不足會(huì)直接導(dǎo)致模型出現(xiàn)過(guò)擬合的問(wèn)題[9]。雖然很多專(zhuān)家也針對(duì)此問(wèn)題提出了小樣本學(xué)習(xí)[10]，甚至是1-樣本學(xué)習(xí)(one-shot learning)[11]的解決方案，但對(duì)樣本仍有一些限制條件。如，樣本需要達(dá)到一定的數(shù)量或具有某些方面的特征(文字樣本需包含某些筆劃特征或書(shū)寫(xiě)順序[11]等)。因此，擁有權(quán)威、充足的東巴字樣本才能為東巴字的自動(dòng)識(shí)別提供更多的途徑，但目前東巴字還未有標(biāo)準(zhǔn)、公開(kāi)的數(shù)據(jù)集，并且大量的文檔資料均是非常古老的紙質(zhì)資料，且多珍藏于世界各大著名圖書(shū)館和博物館，使東巴字的樣本采集難度增大。

電子文檔的普及化、共享化使東巴字的樣本采集有了更加方便、快捷的途徑，通過(guò)對(duì)原有已出版書(shū)籍，特別是絕版、權(quán)威書(shū)籍文檔圖像中東巴字的提取，可快速擴(kuò)充文字庫(kù)，增加字庫(kù)的容量。而原有的樣本采集工作也轉(zhuǎn)化為對(duì)文檔圖像的版面分析和識(shí)別、文本的分割和提取工作。

文本行分割作為東巴字提取、東巴字譯注段落分析、特定樣本采集等一系列文檔分析和采集工作的基礎(chǔ)，有著非常重要的意義，但是卻鮮有研究對(duì)其進(jìn)行探討。由于東巴文檔圖像中兼有東巴文和脫機(jī)手寫(xiě)漢字(例如：《納西象形文字譜》)，若能借鑒或使用已有的脫機(jī)手寫(xiě)漢字版面分析技術(shù)，則可大幅提高工作效率。文獻(xiàn)[12-14]結(jié)合脫機(jī)手寫(xiě)文檔圖像的結(jié)構(gòu)特征，采用改進(jìn)的投影分割算法以直觀的方式實(shí)現(xiàn)了手寫(xiě)文本行的分割。這類(lèi)算法符合人類(lèi)分割文本行的習(xí)慣，具有直觀、簡(jiǎn)單、易實(shí)現(xiàn)的特點(diǎn)，但仍或多或少地受到經(jīng)驗(yàn)參數(shù)的影響(如，實(shí)現(xiàn)上下兩行粘連字符分割時(shí)，憑經(jīng)驗(yàn)將行分割線(xiàn)設(shè)置為文字高度的1/10[12]，文本行分割和合并時(shí)將手寫(xiě)字的大小限定在一定范圍之內(nèi)[13]等)。為了克服這一問(wèn)題，目前學(xué)者們更多是采用與深度學(xué)習(xí)相結(jié)合的方法。GRüNING等[15]提出了一種兩階段的歷史古籍文本行檢測(cè)算法。該方法通過(guò)ARU-Net深度學(xué)習(xí)網(wǎng)絡(luò)，結(jié)合數(shù)據(jù)增強(qiáng)策略，將全頁(yè)訓(xùn)練樣本的數(shù)量降低至50張以下，并且能夠用于任意方向和曲線(xiàn)的文本行檢測(cè)。HAZEM等[16]采用以主題為單位的文檔分割思想，按照祈禱者的時(shí)間順序?qū)崿F(xiàn)了對(duì)中世紀(jì)手稿的文本行分割及段落、文檔結(jié)構(gòu)等更高層次的分析，并建立了對(duì)應(yīng)的數(shù)據(jù)集。但由于缺乏大量的標(biāo)注訓(xùn)練數(shù)據(jù)，無(wú)法采用深度學(xué)習(xí)的方法來(lái)測(cè)試數(shù)據(jù)集。BOILLET等[17]在Doc-UFCN[18]，dhSegment[19]和ARU-Net[15]等3種深度學(xué)習(xí)網(wǎng)絡(luò)的基礎(chǔ)上給出了具有通用性的歷史古籍文本行分割算法，并提出了統(tǒng)一的數(shù)據(jù)標(biāo)注方式以提高識(shí)別效率。WANG等[20]提出了端到端的中文文本頁(yè)面檢測(cè)、識(shí)別系統(tǒng)。通過(guò)將文本檢測(cè)和文字識(shí)別統(tǒng)一到一個(gè)框架中，實(shí)現(xiàn)了全局文本特征與文本核的結(jié)合，降低了文字識(shí)別對(duì)文本檢測(cè)的依賴(lài)性，提高了系統(tǒng)的魯棒性。LIU等[21]提出了基于圖卷積網(wǎng)絡(luò)(graph convolutional network，GCN)的文本行檢測(cè)算法。該算法將文檔中的單詞作為基本單元，以單詞為基礎(chǔ)得到文本行，再以文本行為基礎(chǔ)得到段落，是非常少有的既能檢測(cè)脫機(jī)手寫(xiě)文本行，又能檢測(cè)文檔段落的方法。但是，該方法以脫機(jī)手寫(xiě)單詞為基本單元，單詞在文檔中的識(shí)別效率將直接影響算法最終的準(zhǔn)確率。

基于深度學(xué)習(xí)的方法具有精度高、健壯性好、不受經(jīng)驗(yàn)參數(shù)影響等優(yōu)點(diǎn)，但針對(duì)于特定領(lǐng)域，對(duì)訓(xùn)練數(shù)據(jù)的規(guī)模、數(shù)據(jù)標(biāo)記方式等均有著不同的要求。并且，一些研究[15,17,19,21]對(duì)文檔中文本行的分割及文檔結(jié)構(gòu)的分析是建立在利用已有的文字檢測(cè)和識(shí)別算法的基礎(chǔ)上完成的。這與本文通過(guò)分析東巴文檔圖像的結(jié)構(gòu)，分割并提取其中的東巴字、脫機(jī)手寫(xiě)漢字，形成完整的東巴象形文字?jǐn)?shù)據(jù)集的思路是相悖的。

因此，結(jié)合東巴象形文字文檔圖像的結(jié)構(gòu)特點(diǎn)，本文提出一種適用于東巴字文檔圖像的文本行自動(dòng)分割(automatic text line segmentation，ATLS)算法，以傳統(tǒng)投影分割算法為基礎(chǔ)加入了基于密度和距離的k-均值聚類(lèi)算法(distance & density K-means，d-K-means)，保證了文本行分割的合理性和徹底性。ATLS算法充分利用了東巴字文檔的結(jié)構(gòu)特征，同時(shí)又保留了機(jī)器學(xué)習(xí)模型客觀、無(wú)主觀經(jīng)驗(yàn)影響的優(yōu)勢(shì)，使算法的健壯性更好、準(zhǔn)確性更高、適用范圍更廣，從而為以更小的文檔單位研究東巴字，建立具有權(quán)威性的東巴字庫(kù)奠定基礎(chǔ)。

2 東巴字文檔圖像的文本行自動(dòng)分割算法

2.1 東巴字文檔圖像研究對(duì)象的選擇

《納西象形文字譜》[22]、《納西族象形標(biāo)音文字字典》[23]和《納西語(yǔ)英語(yǔ)漢語(yǔ)語(yǔ)匯》[24]是代表東巴文編撰領(lǐng)域較高水平的三部字典，如圖1所示。其中，方國(guó)瑜先生編撰的《納西象形文字譜》是一本純手寫(xiě)的字典，與其他兩本字典相比，其排版、布局更加復(fù)雜，加之全部為脫機(jī)手寫(xiě)字文檔，文字的大小、文本行的間距、段落的縮進(jìn)距離等隨意性更強(qiáng)，難以做到完全一致。因此，選擇《納西象形文字譜》作為研究對(duì)象具有一定代表性，有利于提高ATLS算法的適用性和擴(kuò)展性。

ATLS算法的核心思路是：首先，采用垂直和水平投影對(duì)東巴文檔圖像進(jìn)行初次分割，提取文字塊；其次，將文字塊作為聚類(lèi)的數(shù)據(jù)樣本，結(jié)合d-K-means算法對(duì)文字塊進(jìn)行自動(dòng)分類(lèi)，確定文字塊的屬性；最后，對(duì)其中的異常文字塊進(jìn)行二次處理，保證文檔中單個(gè)文本行的獨(dú)立性和完整性。

2.2 文檔圖像的預(yù)處理及初次分割

由于東巴文檔圖像中的頁(yè)眉和頁(yè)腳一般為印刷體，排版位置固定、大小相同(圖1)。因此，在預(yù)處理階段，首先計(jì)算文檔中頁(yè)眉和頁(yè)腳的位置并去除，以減少對(duì)文檔正文結(jié)構(gòu)的干擾，效果如圖2(a)和(b)所示；其次，采用水平和垂直投影算法對(duì)文檔圖像進(jìn)行初分割，分割時(shí)將投影值為0的像素行作為文檔圖像的分割行/列，并提取文檔中的文字塊，如圖2(a)和(c)所示。其中，圖2(a)為初次水平分割的結(jié)果，圖2(c)為初次垂直分割的結(jié)果。

由于脫機(jī)手寫(xiě)文檔的書(shū)寫(xiě)比較隨意，文本行的間距大小不同，單個(gè)字符內(nèi)部可能存在局部分離，而字符間又易發(fā)生重疊、粘連和交錯(cuò)，加之東巴字大小不一，使得由初次分割得到的文字塊中存在分割不徹底或過(guò)渡分割的文字塊，如圖2(a)和(c)所示。并且，初次分割得到的文字塊屬于無(wú)標(biāo)記樣本，文字塊的屬性、包含的文本行數(shù)量或文字塊的有效性都是未知的。為了找出無(wú)標(biāo)記樣本的內(nèi)在特征，實(shí)現(xiàn)文檔中文本行的有效提取，選擇無(wú)監(jiān)督學(xué)習(xí)(unsupervised learning)中廣泛應(yīng)用的聚類(lèi)算法[23]——K-means來(lái)分析文字塊的屬性。

圖2 文檔圖像的預(yù)處理和初次分割((a)原始文檔圖像；(b)去除頁(yè)眉和頁(yè)腳；(c)初次垂直投影；(d)垂直投影合并)

2.3 基于密度和距離的k-均值聚類(lèi)算法

K-means基于“以物聚物”的原理是將一組個(gè)體按照相似性歸為若干類(lèi)，使得屬于同一類(lèi)別的個(gè)體之間的差異性盡可能的小，而不同類(lèi)別則盡可能的大，具有簡(jiǎn)潔、快速的優(yōu)點(diǎn)[25]。但是，K-means一般要求事先指定分類(lèi)數(shù)量，且對(duì)初始點(diǎn)敏感，導(dǎo)致聚類(lèi)結(jié)果穩(wěn)定性差，使用范圍受限。為克服原始算法的缺陷，選擇基于密度和距離的k-均值聚類(lèi)算法(d-K-means)[26]。該算法在K-means算法的基礎(chǔ)上權(quán)衡了密度和距離對(duì)聚類(lèi)的影響，首先在權(quán)值的基礎(chǔ)上通過(guò)引入最小最大原則來(lái)選擇初始聚類(lèi)中心，避免初始聚類(lèi)中心選擇隨機(jī)性引起的局部最優(yōu)解問(wèn)題，減少算法的迭代次數(shù)；其次，通過(guò)比較預(yù)分類(lèi)前后所有數(shù)據(jù)點(diǎn)BWP指標(biāo)[27]平均值的變化來(lái)自動(dòng)確定類(lèi)中心及其個(gè)數(shù)，保證了K-means聚類(lèi)中心及其數(shù)量的有效性。使用d-K-means算法實(shí)現(xiàn)東巴文檔圖像中文字塊的分類(lèi)與屬性識(shí)別的操作步驟為：

步驟1.確定樣本集合及采樣特征。將投影算法得到的文字塊作為聚類(lèi)分析的數(shù)據(jù)樣本。由圖2可知，在水平方向上，文字塊的屬性判斷與文字塊的高度有關(guān)(過(guò)大，可能是分割不徹底；過(guò)小，可能是過(guò)分割)，因此將文字塊的高度及其在文檔圖像中的序號(hào)作為水平樣本的特征。在垂直方向上，由于空白分割列的位置相對(duì)固定，變化幅度較少，因此選擇文檔中連續(xù)的空白分割列作為垂直樣本，將其起始位置和列寬作為樣本特征。那么，對(duì)于包含個(gè)文字塊的樣本集合，其水平樣本及垂直樣本的特征描述為

其中，和分別為水平樣本的序號(hào)和行高；和分別為垂直樣本的起始位置和列寬。由于在水平和垂直方向上的文字塊處理方式類(lèi)似，且水平分割的處理過(guò)程更為復(fù)雜，因此以水平樣本的分類(lèi)過(guò)程為例來(lái)描述整個(gè)算法的流程。圖3(a)和圖4(a)的分布給出了《納西象形文字譜》文檔圖像水平和垂直樣本的特征分布情況。

步驟2.計(jì)算水平樣本P的半徑，得

其中，P_nearest()為與水平樣本P距離最近的個(gè)樣本；()為2個(gè)樣本點(diǎn)之間的歐氏距離；為初始時(shí)每個(gè)聚類(lèi)包含的樣本數(shù)，在二維空間中一般取m=4[28]。

步驟3.根據(jù)水平樣本P的_領(lǐng)域，計(jì)算權(quán)值，選擇權(quán)值最大的樣本點(diǎn)作為聚類(lèi)的第一個(gè)中心點(diǎn)，即

其中，Q為P的_領(lǐng)域內(nèi)的樣本；為樣本P的_領(lǐng)域內(nèi)的樣本數(shù)量；()為2個(gè)樣本點(diǎn)之間的歐氏距離；為樣本集向量空間的大??；max和min為樣本集合二維特征的最大值和最小值；|| ||2為歐氏距離的平方。

步驟4.計(jì)算每個(gè)水平樣本的中心點(diǎn)指標(biāo)C，選取中心點(diǎn)指標(biāo)最大的樣本作為新的備選聚類(lèi)中心，并加入到中心點(diǎn)列表中，對(duì)樣本集合進(jìn)行預(yù)分類(lèi)，即

圖3 基于d-K-means的東巴文檔水平文字塊的分類(lèi)((a)文檔中水平樣本的分布；(b) BWP平均值的變化情況；(c)基于d-K-means的分類(lèi))

Fig. 3 Classification of horizontal text blocks in Dongba documents based on d-K-means ((a) Distribution of horizontal samples in the document; (b) Variation of BWP mean; (c) Classification based on d-K-means)

圖4 基于d-K-means的東巴文檔垂直文字塊的分類(lèi)((a)文檔中垂直樣本的分布；(b) BWP平均值的變化情況；(c)基于d-K-means的分類(lèi))

其中，為水平樣本P的權(quán)值；為水平樣本P與距離自身最近的類(lèi)簇中心點(diǎn)之間的距離，為當(dāng)前中心點(diǎn)的數(shù)量。

步驟5.計(jì)算類(lèi)間距離。類(lèi)間距離(,)指的是第類(lèi)中的第個(gè)樣本P到其他每個(gè)類(lèi)中樣本的歐式距離平均值的最小值。顯然，(,)的值越大，則類(lèi)間分離性越好，得

步驟6.計(jì)算類(lèi)內(nèi)距離。類(lèi)內(nèi)距離(,)指的是第類(lèi)中的第個(gè)樣本P到類(lèi)中其他樣本距離的平均值。顯然，(,)越小，類(lèi)內(nèi)緊密性越好，密度越高，即

步驟7.根據(jù)預(yù)分類(lèi)結(jié)果，計(jì)算集合中所有水平樣本BWP指標(biāo)的平均值，即

其中，為集合中的樣本數(shù)。若BWP指標(biāo)的平均值增大，則將該點(diǎn)作為聚類(lèi)中心，并刪除其領(lǐng)域中的數(shù)據(jù)，然后接著尋找下一個(gè)聚類(lèi)中心；若BWP指標(biāo)的平均值減小或不存在可選取的數(shù)據(jù)點(diǎn)，說(shuō)明所有聚類(lèi)中心已找到，則停止算法。通過(guò)5次迭代過(guò)程，BWP指標(biāo)平均值的變化情況如圖3(b)所示。由此可知，文檔圖像中的水平樣本可分為4類(lèi)，根據(jù)中心點(diǎn)列表中的4個(gè)聚類(lèi)中心位置，使用K-means對(duì)水平樣本進(jìn)行分類(lèi)的結(jié)果如圖3(c)所示。

圖3(c)中，4個(gè)聚類(lèi)行高的取值范圍分別為：橙色聚類(lèi)[17, 58]；藍(lán)色聚類(lèi)[71, 207]；綠色聚類(lèi)[239, 346]；紅色聚類(lèi)[426, 449]。結(jié)合圖2(a)的分割結(jié)果可看出，藍(lán)色聚類(lèi)為單個(gè)文本行的聚類(lèi)，橙色聚類(lèi)為過(guò)分割文字塊的聚類(lèi)，而綠色和紅色聚類(lèi)為分割不徹底的大文字塊的聚類(lèi)。同理，對(duì)垂直樣本進(jìn)行處理得到的樣本特征分布情況、BWP值和分類(lèi)結(jié)果如圖4所示。結(jié)合圖2(c)的垂直樣本分布情況可知，橙色和紫色聚類(lèi)為文檔最左側(cè)和最右側(cè)的空白列，綠色和藍(lán)色聚類(lèi)為文檔中的分割列，而紅色聚類(lèi)為過(guò)分割空白列。由此，根據(jù)不同聚類(lèi)的取值范圍，可快速判斷文字塊的類(lèi)別屬性，并針對(duì)異常字塊進(jìn)行二次處理。

2.4 文字塊的二次處理

文字塊的二次處理包括：過(guò)分割文字塊的合并和大文字塊的二次分割。

(1)過(guò)分割文字塊的合并。垂直方向上，只需去除紅色聚類(lèi)中無(wú)效的空白分割列即可，實(shí)現(xiàn)簡(jiǎn)單，合并前后的效果如圖2(c)和(d)所示。水平方向上，由圖3(c)的分類(lèi)結(jié)果可知，單個(gè)文本行的高度范圍為[71, 207]，那么當(dāng)文字塊的高度<71時(shí)，該文字塊為過(guò)分割文字塊，需要合并。結(jié)合文字排版和書(shū)寫(xiě)習(xí)慣可知，一般情況下，行內(nèi)字塊的上下間距一定小于行間字塊的上下間距，也就是說(shuō)，距離越近的文字塊，其關(guān)系越親密。因此，將過(guò)分割文字塊與其間距更近的相鄰文字塊進(jìn)行合并。即，對(duì)于相鄰的3個(gè)文字塊block-1，block和block+1，其起止點(diǎn)的坐標(biāo)分別為：(0, sy-1)和(0, ey-1)，(0, sy)和(0, ey)，(0, sy1)和(0, ey+1)，則文字塊block-1和block之間的上下間距為

那么，可合并文字塊combine為

過(guò)分割文字塊的合并效果如圖5(c)所示。

(2) 大文字塊的二次分割。由于受文檔圖像中東巴字及手寫(xiě)字上下行粘連的影響，使文本行在分割的過(guò)程中產(chǎn)生了很多無(wú)法分割的大文字塊，有的包含2個(gè)文本行，也有的包含多個(gè)文本行，如圖5(a)所示。為了實(shí)現(xiàn)大文字塊的有效分割，一種簡(jiǎn)單、快捷的方式是選擇字塊中水平投影值較小的行作為分割行。但這又會(huì)將處于文字塊上下邊界處投影值較小的像素行也錯(cuò)誤地作為分割行。因此，在選擇分割行時(shí)，首先對(duì)所有像素行的投影值按照從小到大的順序排列，選擇投影值較小的行作為備選分割行；然后，計(jì)算備選分割行與文字塊上下邊界的高度差，如果高度差大于單個(gè)文本行的最小值，則將其作為分割行，否則繼續(xù)從備選行中查找滿(mǎn)足條件的像素行。

因此，設(shè)單個(gè)文本行的高度范圍為[1,2]，則對(duì)于行高為h的文字塊block，若文字塊的起止坐標(biāo)為(0,sy)和(0,ey)，且h>s2，該文字塊的分割步驟為：

步驟1.計(jì)算第sy行至第ey行的水平投影值，并存儲(chǔ)到集合中；

步驟2.選擇集合中投影值最小且與sy或ey的高度差均>1的像素行作為分割行，并將該行從集合中刪除。滿(mǎn)足條件

圖5 文本行的水平分割與合并((a)文本行的水平分割效果；(b)大文字塊的水平投影值統(tǒng)計(jì)；(c)文字塊的二次合并與分割)

步驟3.使用分割行對(duì)文字塊進(jìn)行二次分割，得到2個(gè)子塊。

步驟4.判斷每個(gè)子塊的行高，若子塊的行高>2，則重復(fù)執(zhí)行步驟1～步驟3，直至所有子塊的高度介于[1,2]為止。

由圖3(c)的分類(lèi)結(jié)果可知，單個(gè)文本行的高度范圍為[71, 207]，則對(duì)文檔中的大文字塊進(jìn)行判斷和分割，結(jié)果如圖5(c)所示。通過(guò)二次處理，東巴文檔圖像中的單個(gè)文本行得到了有效提取，保證了文本行的獨(dú)立性和完整性。

2.5 算法的復(fù)雜度分析

ATLS算法由3個(gè)核心模塊組成，即：基于投影的文檔分割、基于d-K-means的文字塊分類(lèi)及文字塊的二次處理。假設(shè)單個(gè)文檔圖像包含行列(>)像素點(diǎn)，一本書(shū)籍包括頁(yè)文檔，且投影分割最多得到個(gè)文字塊，則：

(1) 基于投影的文檔分割，需要計(jì)算每個(gè)像素行或列的投影值，因此時(shí)間復(fù)雜度(1)=(×)≈(2)；

(3) 文字塊的二次處理包括異常文字塊的合并及大文字塊的二次分割。其中，異常文字塊的合并需計(jì)算文字塊的高度及與其上下相鄰文字塊的間距。最壞情況下，需合并的文字塊數(shù)量為，則時(shí)間復(fù)雜度(31)=()；大文字塊的二次分割需要根據(jù)文字塊的高度再次進(jìn)行分割線(xiàn)的篩選和投影分割。最壞情況下，大文字塊的高度為，其時(shí)間復(fù)雜度為(32)=(2)。因此，該階段的時(shí)間復(fù)雜度(3)=(31)+(32)≈(2)。

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

3.1 準(zhǔn)確性測(cè)試

三部字典中，正文部分《納西象形文字譜》包括554頁(yè)，《納西族象形標(biāo)音文字字典》包括360頁(yè)，《納西語(yǔ)英語(yǔ)漢語(yǔ)語(yǔ)匯》包括655頁(yè)。由于這些文檔中，有部分文檔頁(yè)不包括東巴字(如，前言、緒論等)，為了準(zhǔn)確分析最終文本行的提取效果，從三部字典中隨機(jī)抽取150頁(yè)含有東巴字的文檔圖像和30頁(yè)不含東巴字的文檔圖像作為測(cè)試樣本，分別選擇基于圖像結(jié)構(gòu)特征分析的文本行提取算法[12]、集成了PANNet，ResNet和DenseNet等3種神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的端到端文本行提取算法[18]和本文算法進(jìn)行比較，結(jié)果見(jiàn)表1。

表1 不同類(lèi)型算法提取東巴文檔文本行的正確率

為了便于比較，文獻(xiàn)[18]采用了由CASIA- HWDB2.0-2.2數(shù)據(jù)集訓(xùn)練后得到的網(wǎng)絡(luò)模型，由于該數(shù)據(jù)集中不包含東巴字，因此在采用該模型提取包含東巴字的文本行時(shí)，準(zhǔn)確率較低，而在處理不含東巴字的脫機(jī)手寫(xiě)文檔時(shí)，由于受到表格、文字下劃線(xiàn)等其他因素的影響，正確率也低于其他2種算法。但是，當(dāng)文檔中僅含印刷體漢字時(shí)，其準(zhǔn)確率顯著提高。文獻(xiàn)[12]的整體表現(xiàn)均優(yōu)于文獻(xiàn)[18]，但是當(dāng)文檔中含東巴字時(shí)，由于文檔的排版結(jié)構(gòu)發(fā)生較大變化，因此文獻(xiàn)[12]的正確率也受到較大影響。

3.2 擴(kuò)展性測(cè)試

《創(chuàng)世紀(jì)》是一部非常具有代表性的東巴經(jīng)典，很多東巴經(jīng)均采用此類(lèi)格式排版。這類(lèi)文檔一般由東巴經(jīng)原文和中文譯注兩部分組成，文檔內(nèi)容往往與表格交疊，比前述東巴文檔圖像更加復(fù)雜。并且，一些東巴祭祀在書(shū)寫(xiě)東巴經(jīng)時(shí)，還經(jīng)常將表格的下框線(xiàn)作為東巴文字的一種補(bǔ)充，實(shí)現(xiàn)連字成句的效果，使文本行的分割難度增大，如圖6所示。

圖6 《創(chuàng)世紀(jì)》的文檔結(jié)構(gòu)

由于《創(chuàng)世紀(jì)》中東巴經(jīng)部分和漢字注解部分的位置固定，對(duì)上下2個(gè)組成部分的內(nèi)容單獨(dú)使用ALTS算法進(jìn)行初次分割、計(jì)算BWP指標(biāo)、分類(lèi)，結(jié)果如圖7(a)～(e)所示。由此可知，東巴經(jīng)部分的聚類(lèi)中心數(shù)量為3，單個(gè)文本行的高度范圍為[57, 83]；而漢字注解部分的聚類(lèi)中心數(shù)量也為3，單個(gè)文本行的高度范圍為[23, 42]。因此，結(jié)合文本行的高度范圍，對(duì)圖7(e)的初次分割結(jié)果進(jìn)行二次處理的效果如圖7(f)所示。此時(shí)，原有文檔中存在的過(guò)分割文字塊得到了有效合并，文檔的整體結(jié)構(gòu)更加顯著?？梢?jiàn)，當(dāng)文本行中既有東巴字，又有脫機(jī)手寫(xiě)漢字，甚至文檔中包含少量噪音時(shí)，ATLS算法也能得到較好的效果。

同時(shí)，分別使用文獻(xiàn)[12]、文獻(xiàn)[18]和ATLS算法對(duì)《創(chuàng)世紀(jì)》全書(shū)37頁(yè)文檔圖像的東巴字部分和脫機(jī)手寫(xiě)漢字部分分別進(jìn)行文本行分割，其正確率見(jiàn)表2。可見(jiàn)，ATLS的可擴(kuò)展性?xún)?yōu)于其他2種算法。

3.3 文字分割測(cè)試

由于文本行中的文字分割過(guò)程，與文檔中的垂直分割過(guò)程非常相似。因此，將ATLS算法進(jìn)一步應(yīng)用到文本行上單個(gè)文字的分割中。首先，將已提取的文本行進(jìn)行垂直投影分割，得到文字樣本，如圖8(a)所示。其次，將文字樣本的寬度及其在文本行中的序號(hào)作為特征，求出其BWP指標(biāo)，并使用K-means進(jìn)行分類(lèi)，如圖8(b)～(d)所示。其中，藍(lán)色聚類(lèi)中文字樣本的寬度范圍為[18, 150]，紅色聚類(lèi)中為[154, 278]。結(jié)合圖8(a)可知，紅色聚類(lèi)中的文字樣本為分割不完全的大文字塊。因此，對(duì)大文字塊進(jìn)行二次分割，結(jié)果如圖8(e)所示。

圖7 《創(chuàng)世紀(jì)》文檔分割過(guò)程((a)東巴經(jīng)的BWP值；(b)東巴經(jīng)的分類(lèi)結(jié)果；(c)漢字注解的BWP值；(d)漢字注解的分類(lèi)結(jié)果；(e)文檔圖像的初始分割；(f)文檔圖像的二次處理)

Fig. 7 “Genesis” document segmentation process ((a) The BWP of the Dongba scripture; (b) The classification of the Dongba scripture; (c) The BWP of the Chinese annotation; (d) The classification of the Chinese annotation; (e) Initial segmentation of the document; (f) Secondary processing of the document)

表2 不同類(lèi)型算法提取《創(chuàng)世紀(jì)》文本行的正確率(%)

圖8 基于d-K-means的文字樣本分類(lèi)((a)文本行的垂直分割；(b)文字樣本的分布；(c) BWP平均值的變化情況；(d)基于d-K-means的分類(lèi)；(e)文字塊的二次分割)

由于文本行中除了包含脫機(jī)手寫(xiě)漢字之外，還包含國(guó)際音標(biāo)、東巴字、數(shù)字和標(biāo)點(diǎn)符號(hào)等多種類(lèi)型的文字樣本，如圖9(a)所示。當(dāng)文本行中存在文字過(guò)分割時(shí)，ATLS算法可能無(wú)法有效地辨別和合并，如圖9(b)和(c)所示。但是，ATLS算法在文字分割方面仍能取得較好的效果，準(zhǔn)確率整體上達(dá)到了95.26%。說(shuō)明，ATLS算法也可用于文本行中單個(gè)文字的分割。

圖9 文本行的組成((a)包括東巴字的文本行；(b)存在大字塊和過(guò)分割的文本行；(c)大字塊的細(xì)分)

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

文本行分割是一項(xiàng)重要的預(yù)處理工作，是字符分割、東巴字提取、東巴字譯注分析、不同層次樣本采集等是一系列文檔分析和采集工作的基礎(chǔ)。因此，結(jié)合東巴字的特殊形態(tài)及文檔的獨(dú)有結(jié)構(gòu)特征給出了適用于東巴字文檔圖像的ATLS算法。通過(guò)引入d-K-means聚類(lèi)分析和文字塊的二次處理，使文本行分割更加準(zhǔn)確、徹底。通過(guò)實(shí)驗(yàn)表明，本文算法除了可用于東巴字文檔圖像的文本行分割之外，也可用于東巴經(jīng)的文本行分割及文本行中的文字分割，算法具有實(shí)現(xiàn)簡(jiǎn)單、準(zhǔn)確性高、適應(yīng)性強(qiáng)的特點(diǎn)。后續(xù)將結(jié)合ATLS算法進(jìn)一步細(xì)化文檔結(jié)構(gòu)分析，完成東巴典籍中東巴象形文字的提取及文字注釋的分離，從而為東巴文檔的分析和數(shù)據(jù)采集，建立東巴文字集奠定基礎(chǔ)。

[1] 和力民. 試論東巴文化的傳承[J]. 云南社會(huì)科學(xué), 2004(1): 83-87.

HE L M. On transition of dongba culture[J]. Social Sciences in Yunnan, 2004(1): 83-87 (in Chinese).

[2] 楊玉婷, 康厚良. 東巴象形文字特征曲線(xiàn)提取算法研究[J]. 圖學(xué)學(xué)報(bào), 2019, 40(3): 591-599.

YANG Y T, KANG H L. Research on the extracting algorithm of dongba hieroglyphic feature curves[J]. Journal of Graphics, 2019, 40(3): 591-599 (in Chinese).

[3] 胡瑞波, 張曉松, 徐人平, 等. 納西族東巴象形文字字體構(gòu)造研究[J]. 鄭州輕工業(yè)學(xué)院學(xué)報(bào): 社會(huì)科學(xué)版, 2013, 14(2): 94-100.

HU R B, ZHANG X S, XU R P, et al. A Study on the Font Structure of Naxi Dongba Hieroglyphs[J]. Journal of Zhengzhou University of Light Industry: Social Science, 2013, 14(2): 94-100 (in Chinese).

[4] 楊玉婷, 康厚良, 廖國(guó)富. 東巴象形文字特征曲線(xiàn)簡(jiǎn)化算法研究[J]. 圖學(xué)學(xué)報(bào), 2019, 40(4): 697-703.

YANG Y T, KANG H L, LIAO G F. Research on simplification algorithm of dongba hieroglyphic feature curve[J]. Journal of Graphics, 2019, 40(4): 697-703 (in Chinese).

[5] 鄭飛洲. 納西東巴文字字素研究[M]. 北京: 民族出版社, 2005: 45-127.

ZHENG F Z. Research on Naxi Dongba character grapheme[M]. Beijing: National Publishing House Press, 2005: 45-127 (in Chinese).

[6] WANG L, LI S J, LV Y J. Learning to rank semantic coherence for topic segmentation[C]//2017 Conference on Empirical Methods in Natural Language Processing. Stroudsburg: Association for Computational Linguistics , 2017: 1340-1344.

[7] KOSHOREK O, COHEN A, MOR N, et al. Text segmentation as a supervised learning task[C]//2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Stroudsburg: Association for Computational Linguistics, 2018: 469-473.

[8] ARNOLD S, SCHNEIDER R, CUDRé-MAUROUX P, et al. SECTOR: a neural model for coherent topic segmentation and classification[J]. Transactions of the Association for Computational Linguistics, 2019, 7: 169-184.

[9] 劉穎, 雷研博, 范九倫, 等. 基于小樣本學(xué)習(xí)的圖像分類(lèi)技術(shù)綜述[J]. 自動(dòng)化學(xué)報(bào), 2021, 47(2): 297-315.

LIU Y, LEI Y B, FAN J L, et al. Survey on image classification technology based on small sample learning[J]. Acta Automatica Sinica, 2021, 47(2): 297-315 (in Chinese).

[10] GAO H H, XIAO J S, YIN Y Y, et al. A mutually supervised graph attention network for few-shot segmentation: the perspective of fully utilizing limited samples[J]. IEEE Transactions on Neural Networks and Learning Systems, 2022, PP(99): 1-13.

[11] LAKE B M, SALAKHUTDINOV R, TENENBAUM J B. Human-level concept learning through probabilistic program induction[J]. Science, 2015, 350(6266): 1332-1338.

[12] 周雙飛, 劉純平, 柳恭, 等. 最小加權(quán)分割路徑的古籍手寫(xiě)漢字多步切分方法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2012, 33(3): 614-620.

ZHOU S F, LIU C P, LIU G, et al. Multi-step segmentation method based on minimum weight segmentation path for ancient handwritten Chinese character[J]. Journal of Chinese Computer Systems, 2012, 33(3): 614-620 (in Chinese).

[13] 朱宗曉, 楊兵. 特征離散點(diǎn)計(jì)算在手寫(xiě)文本行分割中的應(yīng)用[J]. 計(jì)算機(jī)工程與應(yīng)用, 2015, 51(8): 148-152, 204.

ZHU Z X, YANG B. Using feature discrete-point computing in handwritten documents line segmentation[J]. Computer Engineering and Applications, 2015, 51(8): 148-152, 204 (in Chinese).

[14] 雷鑫, 李俊陽(yáng), 宋宇, 等. 用于手寫(xiě)漢字識(shí)別的文本分割方法[J]. 智能計(jì)算機(jī)與應(yīng)用, 2018, 8(2): 126-128.

LEI X, LI J Y, SONG Y, et al. Text segmentation method applied for handwritten Chinese characters recognition[J]. Intelligent Computer and Applications, 2018, 8(2): 126-128 (in Chinese).

[15] GRüNING T, LEIFERT G, STRAU? T, et al. A two-stage method for text line detection in historical documents[J]. International Journal on Document Analysis and Recognition: IJDAR, 2019, 22(3): 285-302.

[16] HAZEM A, DAILLE B, STUTZMANN D, et al. Hierarchical text segmentation for medieval manuscripts[C]//The 28th International Conference on Computational Linguistics. Stroudsburg: International Committee on Computational Linguistics, 2020: 6240-6251.

[17] BOILLET M, KERMORVANT C, PAQUET T. Robust text line detection in historical documents: learning and evaluation methods[J]. International Journal on Document Analysis and Recognition: IJDAR, 2022, 25(2): 95-114.

[18] BOILLET M, KERMORVANT C, PAQUET T. Multiple document datasets pre-training improves text line detection with deep neural networks[C]//2020 25th International Conference on Pattern Recognition. New York: IEEE Press, 2021: 2134-2141.

[19] ARES OLIVEIRA S, SEGUIN B, KAPLAN F. dhSegment: a generic deep-learning approach for document segmentation[C]//2018 16th International Conference on Frontiers in Handwriting Recognition . New York: IEEE Press, 2018: 7-12.

[20] WANG Z H, YU Y W, WANG Y B, et al. Robust end-to-end offline Chinese handwriting text page spotter with text kernel[M]//Document Analysis and Recognition - ICDAR 2021 Workshops. Cham: Springer International Publishing, 2021: 21-35.

[21] LIU S, WANG R S, RAPTIS M, et al. Unified line and paragraph detection by graph convolutional networks[M]// Document Analysis Systems. Cham: Springer International Publishing, 2022: 33-47.

[22] 方國(guó)瑜. 納西象形文字譜[M]. 昆明: 云南人民出版社, 2005: 25-247.

FANG G Y. Naxi hieroglyphs dictionary[M]. Kunming: Yunnan People’s Publishing House, 2005: 25-247 (in Chinese).

[23] 李霖燦. 納西族象形標(biāo)音文字字典[M]. 昆明: 云南民族出版社, 2001: 15-70.

LI L C. Naxi pictographs and transcription characters dictionary[M]. Kunming： Yunnan People’s Publishing House, 2001: 15-70 (in Chinese).

[24] ROCK J F. A Na-Khi-English encyclopedic dictionary (Part I)[M]. Roma: Roma Istituto Italiano Peril Medio ed Estreme Prientale, 1963: 45-655.

[25] 張冬梅, 李敏, 徐大川, 等. k-均值問(wèn)題的理論與算法綜述[J]. 中國(guó)科學(xué): 數(shù)學(xué), 2020, 50(9): 1387-1404.

ZHANG D M, LI M, XU D C, et al. A survey on theory and algorithms for k-means problems[J]. Scientia Sinica: Mathematica, 2020, 50(9): 1387-1404 (in Chinese).

[26] 唐澤坤, 朱澤宇, 楊裔, 等. 基于距離和密度的d-K-means算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2020, 37(6): 1719-1723.

TANG Z K, ZHU Z Y, YANG Y, et al. D-K-means algorithm based on distance and density[J]. Application Research of Computers, 2020, 37(6): 1719-1723 (in Chinese).

[27] 王法勝, 魯明羽, 趙清杰, 等. 粒子濾波算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(8): 1679-1694.

WANG F S, LU M Y, ZHAO Q J, et al. Particle filtering algorithm[J]. Chinese Journal of Computers, 2014, 37(8): 1679-1694 (in Chinese).

[28] 孫凌燕. 基于密度的聚類(lèi)算法研究[D]. 太原: 中北大學(xué), 2009.

SUN L Y. Research of clustering algorithm based on density[D]. Taiyuan: North University of China, 2009 (in Chinese).

Automatic segmentation algorithm for text lines of Dongba hieroglyphs document image

KANG Hou-liang1, YANG Yu-ting2

(1. Sports Department, Suzhou Vocational University, Suzhou Jiangsu 215000, China; 2. School of Computer Engineering, Suzhou Vocational University, Suzhou Jiangsu 215000, China)

Deep learning technologies represented by convolutional neural networks (CNN) have shown excellent performance in the field of image classification and recognition. However, since there is no standard and public dataset for Dongba hieroglyphs, we cannot draw on or use the existing deep learning algorithms. In order to establish an authoritative and effective Dongba hieroglyphs dataset, the current primary task is to analyze the layout structure of the published Dongba classic documents, and extract the text lines and Dongba hieroglyphs in the documents. Therefore, based on the structural features of Dongba hieroglyphic document images, an automatic text-line segmentation algorithm was proposed for Dongba document images. The algorithm first employed the d-k-means clustering algorithm to determine the classification quantity and classification standard of text lines; then, the wrong results in the segmentation were corrected through the secondary processing of the text blocks, so as to enhance the accuracy of the algorithm. While making full use of the structural features of Dongba characters, the algorithm retained such advantages of the machine-learning model as objectivity and immunity to subjective experience. Experiments show that the algorithm can be used for the text line segmentation of Dongba document images, offline handwritten Chinese characters, Dongba scriptures, and the segmentation of individual Dongba and Chinese characters in text lines. It is simple in implementation, high in accuracy, and strong in adaptability, thus laying the foundation for the establishment of the Dongba character library.

Dongba hieroglyph; Dongba documents analysis; text line segmentation; projection segmentation; d-K-means

TP 391

10.11996/JG.j.2095-302X.2022050865

A

2095-302X(2022)05-0865-10

2021-12-31；

2022-05-05

31 December，2021；

5 May，2022

蘇州市職業(yè)大學(xué)引進(jìn)人才科研啟動(dòng)金項(xiàng)目(201905000034)

Suzhou Vocational University Introduced Talents Scientific Research Start-up Fund Project (201905000034)

康厚良(1979-)，男，教授，碩士。主要研究方向?yàn)槊褡逦幕皵?shù)字化。E-mail：kangfu1979110@163.com

KANG Hou-liang (1979-), professor, master. His main research interests cover national culture and its digitization. E-mail：kangfu1979110@163.com

楊玉婷(1983-)，女，副教授，碩士。主要研究方向?yàn)閳D形圖像處理、計(jì)算機(jī)視覺(jué)等。E-mail：tudou-yeah@163.com

YANG Yu-ting (1983-), associate professor, master. Her main research interests cover digital image processing and pattern recognition, etc. E-mail：tudou-yeah@163.com