康厚良，楊玉婷

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

康厚良1，楊玉婷2

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

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

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

1 東巴象形文字手寫文檔分析

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

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

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

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

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

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

2 東巴字文檔圖像的文本行自動分割算法

2.1 東巴字文檔圖像研究對象的選擇

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

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

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

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

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

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

2.3 基于密度和距離的k-均值聚類算法

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

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

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

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

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

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

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

步驟4.計算每個水平樣本的中心點指標C，選取中心點指標最大的樣本作為新的備選聚類中心，并加入到中心點列表中，對樣本集合進行預(yù)分類，即

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

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的東巴文檔垂直文字塊的分類((a)文檔中垂直樣本的分布；(b) BWP平均值的變化情況；(c)基于d-K-means的分類)

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

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

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

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

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

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

2.4 文字塊的二次處理

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

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

那么，可合并文字塊combine為

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

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

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

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

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

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

步驟3.使用分割行對文字塊進行二次分割，得到2個子塊。

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

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

2.5 算法的復雜度分析

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

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

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

3 實 驗

3.1 準確性測試

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

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

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

3.2 擴展性測試

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

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

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

同時，分別使用文獻[12]、文獻[18]和ATLS算法對《創(chuàng)世紀》全書37頁文檔圖像的東巴字部分和脫機手寫漢字部分分別進行文本行分割，其正確率見表2?？梢姡珹TLS的可擴展性優(yōu)于其他2種算法。

3.3 文字分割測試

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

圖7 《創(chuàng)世紀》文檔分割過程((a)東巴經(jīng)的BWP值；(b)東巴經(jīng)的分類結(jié)果；(c)漢字注解的BWP值；(d)漢字注解的分類結(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 不同類型算法提取《創(chuàng)世紀》文本行的正確率(%)

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

由于文本行中除了包含脫機手寫漢字之外，還包含國際音標、東巴字、數(shù)字和標點符號等多種類型的文字樣本，如圖9(a)所示。當文本行中存在文字過分割時，ATLS算法可能無法有效地辨別和合并，如圖9(b)和(c)所示。但是，ATLS算法在文字分割方面仍能取得較好的效果，準確率整體上達到了95.26%。說明，ATLS算法也可用于文本行中單個文字的分割。

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

4 結(jié)束語

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

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

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

[2] 楊玉婷, 康厚良. 東巴象形文字特征曲線提取算法研究[J]. 圖學學報, 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è)學院學報: 社會科學版, 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] 楊玉婷, 康厚良, 廖國富. 東巴象形文字特征曲線簡化算法研究[J]. 圖學學報, 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] 劉穎, 雷研博, 范九倫, 等. 基于小樣本學習的圖像分類技術(shù)綜述[J]. 自動化學報, 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)分割路徑的古籍手寫漢字多步切分方法[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] 朱宗曉, 楊兵. 特征離散點計算在手寫文本行分割中的應(yīng)用[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] 雷鑫, 李俊陽, 宋宇, 等. 用于手寫漢字識別的文本分割方法[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] 方國瑜. 納西象形文字譜[M]. 昆明: 云南人民出版社, 2005: 25-247.

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

[23] 李霖燦. 納西族象形標音文字字典[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-均值問題的理論與算法綜述[J]. 中國科學: 數(shù)學, 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]. 計算機應(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]. 計算機學報, 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] 孫凌燕. 基于密度的聚類算法研究[D]. 太原: 中北大學, 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è)大學引進人才科研啟動金項目(201905000034)

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

康厚良(1979-)，男，教授，碩士。主要研究方向為民族文化及數(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-)，女，副教授，碩士。主要研究方向為圖形圖像處理、計算機視覺等。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