基于高階相關聚類的脫機手寫文本行分割

殷亞林， 劉愛民， 周祥東

(1.江漢大學 數字媒體技術系， 武漢 430056； 2.華中師范大學 實驗室與設備處， 武漢 430079；3.中國科學院 綠色智能技術研究院, 重慶 400714)

基于高階相關聚類的脫機手寫文本行分割

殷亞林1*， 劉愛民2， 周祥東3

(1.江漢大學 數字媒體技術系， 武漢 430056； 2.華中師范大學 實驗室與設備處， 武漢 430079；3.中國科學院 綠色智能技術研究院, 重慶 400714)

從手寫文檔圖像中提取出文本行是文檔分析的一個重要預處理步驟，但是由于手寫文本行之間通常行方向不平行，甚至存在著交疊和彎曲，所以它仍然是一個具有挑戰性的問題. 針對該問題，提出了一種基于高階相關聚類的脫機中文手寫文本行的分割算法.首先，使用連通部件構成一個文檔超圖，然后，在學習所得的相似性度量準則的約束下，通過高階相關聚類算法將連通部件對標記為屬于或者不屬于同一文本行；最后，使用union-find算法將連通部件連接成為不同的文本行.該算法在HIT-MW脫機手寫數據庫上的803幅文檔上取得了較好的效果，召回率99.05%，錯誤率為1.96%.

手寫文本行分割； 高階相關聚類； 超圖

文本行分割是文檔分析的一個重要預處理步驟，它是字符分割，字符串識別和文檔檢索等一系列文檔分析任務的基礎.印刷文檔文本行分割的難點在于它復雜的版面結構和低劣的圖像質量；而手寫文檔文本行分割的難點來自于手寫文檔書寫隨意，不存在明顯易于分割的版式特點.例如，印刷文檔的文本行都是筆直而且相互平行的，但是手寫文本行基本都存在不同程度的彎曲，而且行與行之間的空隙也不明確，甚至存在嚴重的重疊和粘連.因此，對手寫文檔進行文本行分割要比對印刷體文檔進行文本行分割要難的多，大量成熟的印刷文檔的文本行分割算法在手寫文檔上基本失去了作用.

近年來，很多研究者就手寫文本行分割展開了深入的研究，并提出了一系列的解決方法.這些方法從解決問題的策略上可以分為3大類：自頂向下的方法、自底向上的方法和混合的方法.基于自頂向下的策略方法的主要思路是依照一定的規則將文檔不斷地細分為文本塊、段落、直至文本行.這類方法包含基于投影(projection-profile)分析的方法[1]和基于蓄水池(water reservoir)的方法[2].自頂向下策略的分割方法雖然在文本行比較平直規則的圖像上效果較好，但是在文本行存在嚴重的交疊和粘連的情況下性能會大幅下降.基于自底向上策略的方法可以看成是一類基于聚類的方法，在該策略下一些文檔圖像的基本組成部件(比如：像素，連通部件)在預定義的相似性度量的約束下聚類為文字，文本行，甚至文本段落.基于K近鄰連通部件聚類的方法[3]、基于拖尾效應(smearing)的方法[4]、基于霍夫(Hough)變換的方法[5]和基于最小生成樹聚類的方法[6]都是這一類算法的典型代表.基于自底向上策略方法的優點是能夠較好的分割出彎曲，傾斜的文本行，但是它們的效果也受制于聚類時所利用的各種啟發式規則、經驗參數和聚類算法.基于混合策略的方法是采用不同的融合策略將多種自頂向下或者自底向上的方法結合在一起，以期得到更好的分割結果.文獻[7]就是將基于拖尾效應方法和基于最小生成樹聚類方法的分割結果通過圖的集成聚類框架融合在一起.基于混合策略的方法相對前兩種策略的方法，一般能夠取得更好的結果，但是該類方法也有一個明顯的缺點就是實現復雜、計算量大，而且效果也受制于算法中使用的融合策略.

本文提出了一種有效的采用自底向上策略的脫機手寫文本行的分割方法.本方法首先使用連通部件構成一個文檔超圖，然后在學習所得的相似性度量準則的約束下，通過高階相關聚類算法[8]將近鄰連通部件對標記為屬于或者不屬于同一文本行；最后使用union-find算法[9]將連通部件連接成為不同的文本行.本方法最大的特點是不需要人工預先指定相似性度量，而是通過結構學習獲取聚合相似性度量參數，這樣有效地避免了經驗參數的影響，大大地增強了算法在不同風格文檔上的魯棒性.

1文本行分割系統框架

文檔的邏輯結構可以被描述為一個層次樹.處于該層次樹最頂端的是文檔頁面，處于第二層的是一個或多個文本段落，每個文本段落又由處于第三層的多個文本行組成，而每個文本行則包含幾個到幾十個不等的連通部件，處于最底層的則是構成文字的圖像像素點.因此，只要能夠方便地提取出該文檔層次樹中合適的基元，然后根據不同的任務設計出一系列有效的相似性度量準則，最后采用合適的聚類算法將這些基元自下而上的逐步聚合在一起，就能得到任何層次的文檔邏輯結構.在本文的算法中，由于連通部件易于檢測和數目遠遠小于文檔中的文字像素的數目，所以我們把連通部件作為文檔的基本組成結構來參與生成文本行的聚類過程.很顯然，如何獲取“相似性度量準則”和采用何種“聚類算法”是本文算法的兩個關鍵問題.

一個好的相似性度量準則應該能夠使得屬于同一文本行的近鄰連通部件對在特征空間中有著較近的距離，而不屬于同一文本行的近鄰連通部件對有著較遠的距離.但是人工經驗設置的相似性度量準則泛化性能欠佳，只是在其針對的某些類型的文檔上擁有很好的性能.因此，本文采用基于結構學習的方法來獲取相似性度量參數，這樣既能得到更加準確的相似性度量準則，而且在面對不同風格的文檔時，只需要添加對應的訓練數據就能自動地調整相似性度量的參數，減輕人工干預的負擔.

K近鄰聚類和最小生成樹聚類等算法常常被用來完成連通部件的聚類[3，6]，但是我們認為這些算法并沒有充分利用連通部件之間已有的信息，因為這類算法聚類時一般只考慮相鄰的一對連通部件之間的相似關系，但是文本行分類通常需要綜合考慮多個近鄰連通部件的關系，才能更好的做出判斷.高階相關聚類正好能夠將相鄰兩個連通部件對和多個近鄰的連通部件集合之間的關系融合在一個聚類框架中，能夠利用更多的已有信息完成聚類工作.

圖1 手寫文本行分割系統框架圖Fig.1 The framework of handwritting textline segmentation system

因此，本文搭建的文本行分割系統包含兩個主要的模塊，它們分別是相似性度量學習模塊和文本行聚合模塊，如圖1所示.該系統的輸入為文檔圖像，輸出為分割出來的文本行連通部件集合.相似性度量學習模塊包含在圖1上半部分的虛線框內，該模塊在已知標記的訓練數據集上，通過結構學習的方法學習出相似性度量參數；文本行聚合模塊包含在圖1下半部分的虛線框內，它包含預處理、高階相關聚類和后處理3個子模塊.其中，預處理子模塊主要完成圖像二值化，連通部件提取和粘連切分(由于直接提取得到的連通部件會包含文本行之間或者字符之間的筆畫粘連，因此需要對文本行連通部件進行過切分來切斷粘連筆畫[10])；高階相關聚類子模塊主要完成連通部件的聚類，在該模塊中首先使用聯通部件生成文檔超圖， 接著將超圖邊集合分為二階邊集和高階邊集分別提取幾何特征，然后采用高階相關聚類將相鄰連通部件對標記為是否屬于同一文本行，最后使用union-find將連通部件連接成不同文本行；雖然高階相關聚類能夠得到很好的聚合結果，但是并不完美，得到的候選文本行可能存在“斷行”的問題，因此，還需要采用類似文獻[6]提出的后處理方法將斷行進行拼接.

2文本行聚合算法

文本行聚合算法是本文系統的核心，而該算法又涉及到的4個關鍵問題：文檔超圖的構建、高階相關聚類、幾何特征提取和相似性度量學習.因此，本小節將對這些關鍵問題分別展開詳細的論述.

2.1文檔超圖構建

對二值文檔圖像提取連通部件之后，得到連通部件的集合為C={ci|ci∈I，i=1，2，…，n}(I為文檔中全部文字像素的集合).在此基礎上，我們定義一個無向超圖(hypergraph)HG=(V，E)，其中：V=C為該圖的頂點集合，即每個連通部件為該圖的一個頂點；E={ej||ej|≥2;j=1，2，…，m}為該圖超邊(hyperdege)的集合，其中ej表示一條能夠連接至少2個頂點的超邊；因此，可以將超邊劃分為兩個子集：二階邊集合E2={e∈E||e|=2}以及高階邊集合Eh={e∈E||e|>2}，于是有E2∪Eh=E.顯然，如果超圖中只有二階邊集合，那么這個超圖就會退化為一般的圖.

圖2 構建K+1階邊過程Fig. 2 Constructing K+1 order edge

2.2高階相關聚類

當完成文檔超圖構建之后，對超邊引入一個二值標簽ye，那么對于超邊e∈E有

(1)

那么，可以定義一個基于文檔C和標簽y的判別函數：

(2)

(3)

其中，Y(HG)代表合法分割集合.針對文本分割問題，通過觀察還有兩個實際的約束關系：1)當一條高階邊被標記為1時，其包含的二階邊關系對應元素的標簽必然為1；2)如果高階邊被標記為0，那么其包含的所有二階邊中必然存在標簽為0的二階邊.將這兩個約束關系表示如下：

(4)

那么通過文獻[11]中給出的線性規劃松弛方法(linear programming relaxation)就可以得到上面優化問題的近似解.

2.3特征提取

針對文本行分割問題，構建一個98維的特征向量φe(C)，該特征向量由兩部分組成：二階邊特征向量φe2(C)和高階邊特征向量φeh(C).

表1 基于相鄰連通部件的一元幾何特征

表2 基于相鄰連通部件的二元幾何特征

表1和表2的最后一列表示該值是否需要采用文檔連通部件平均高度歸一化，該操作主要是為了文字大小不一的文檔上的特征歸一化到基本相當的尺度．

2.4相似性度量學習

s.t. 〈w， ΔΦ(Cn，y)〉 ≥Δ(yn，y)-ξn，

?n，y∈Yyn，

ξn≥0， ?n，

(5)

其中，ΔΦ(Cn，y)=Φ(Cn，yn)-Φ(Cn，y)，α>0用于控制模型的復雜度，Δ(yn，y)是損失函數，y由2.2小節的高階相關聚類獲取.由于漢明距離可以很方便地用來統計yn與y錯誤匹配的個數，所以我們定義損失函數為：

(6)

對于該模型，可以使用文獻[12]介紹的切平面算法進行優化求解.

3實驗結果

本文使用哈爾濱工業大學提供的HIT-MW脫機手寫中文文檔數據庫[13]，該數據庫包含由780多人書寫的853幅掃描文檔，一共包含8677個手寫文本行，每副圖像大約包含530個連通部件.我們隨機選取其中的50幅圖像作為訓練文檔(包含509行)，剩下的803幅圖像作為測試集(包含8164行).

本文采用檢測文本行與標記文本行的像素匹配率在文本行級別評價所有算法的性能.即任何一個檢測的文本行和對應的標記文本行共享超過95%的像素，則定義該文本行被正確檢測到了[7].因此，召回率為所有正確檢測到的文本行與所有標記文本行的百分比；錯誤檢測率為所有錯誤檢測文本行占所有已檢測文本行的百分比.

本文提出的基于高階相關聚類的文本行分割算法用VS2008實現，在IntelCore(TM)i7-3770， 8GRAM的個人計算機上完成一幅圖像的文本行分割大約需要1秒左右，其性能如表3所示.實驗表明相對于文獻[6]算法，由于本文算法可以利用更高階的上下文信息，所以能取得更好的性能.盡管本文算法比文獻[7]算法(一幅圖像耗時大約6～8s)的速度快了至少5倍以上，但是檢測性能稍遜，這表明本文算法需要尋找更合適的幾何特征，在保證算法速度的情況下，進一步提升性能.

圖3給出了一些文本分割失敗的案例，可以看到，本文的算法還不能很好地處理傾斜度較大的文本行.

表3 測試集上文本行分割結果及對比

圖3 錯誤分割樣例Fig.3 Error segmentation samples

4結論

本文提出了一種采用自底向上策略的脫機手寫文本行的分割方法.該方法首先在文檔內構成超圖，然后在學習所得的相似性度量準則的約束下，通過高階相關聚類算法將近鄰連通部件對標記為屬于或者不屬于同一文本行，最后使用union-find算法將連通部件連接成為不同的文本行.本方法不需要人工預先指定相似性度量，而是通過結構學習獲取聚合相似性度量參數；并且與之前的工作相比，可以在保證較高分割精度的同時減少處理時間.接下來的工作中，我們可以尋找更合適的幾何特征，在保證算法速度的情況下，進一步提升分割性能.

[1]PALU，DATTAS.SegmentationofBanglaunconstrainedhandwrittentext[C]//7thInt’lConferenceDocumentAnalysisandRecognition.Edinburgh,Scotland,UK,IEEEPress， 2003:1128-1132．

[2]SHIZ，SETLURS，GOVINDARAJUV.Textextractionfromgrayscalehistoricaldocumentimagesusingadaptivelocalconnectivitymap[C]//8thInt’lConferenceonDocumentAnalysisandRecognition.Seoul,Korea,IEEEPress， 2005： 794-798．

[3]O’GORMANL.Thedocumentspectrumforpagelayoutanalysis[J].IEEETransonPatternAnalysisandMachineIntelligence， 1993， 15(11): 1162-1173．

[4]BASUS，CHAUDHURIC，KUNDUM，etal.Textlineextractionfrommulti-skewedhandwrittendocuments[J].PatternRecognition， 2007， 40(6):1825-1839．

[5]LOULOUDISG，GATOSB，PRATIKAKISI，etal.Ablock-basedHoughtransformmappingfortextlinedetectioninhandwrittendocument[C]//10thInt’lWorkshoponFrontiersinHandwritingRecognition.LaBaule,France,IEEEPress， 2006： 515-520．

[6]YINF，LIUCL.Handwrittentextlinesegmentationbyclusteringwithdistancemetriclearning[J].PatternRecognition， 2009， 42(12): 3146-3157．

[7] 黃 亮， 殷 飛， 陳慶虎. 基于圖聚類的脫機手寫文檔圖像文本行分割[J]. 華中科技大學學報(自然科學版)， 2014， 42(3) : 33-36．

[8]KIMSW，YOOCD，NOWOZINS，etal.Imagesegmentationusinghigher-ordercorrelationclustering[J].IEEETransonPatternAnalysisandMachineIntelligence， 2014， 36(9):1761-1774．

[9]SEDGEWICKR，WAYNEK.Algorithms[M].USA:Addison-WesleyProfessional， 2011．

[10]LIUCL，KOGAM，FUJISAWAH.Lexicon-drivensegmentationandrecognitionofhandwrittencharacterstringsforJapaneseaddressreading[J].IEEETransactionsonPatternAnalysisandMachineIntelligence， 2002， 24(11):1425-1437．

[11]NOWOZINS，JEGELKAS.Solutionstabilityinlinearprogrammingrelaxations:Graphpartitioningandunsupervisedlearning[C]//Int’lConferenceonMachineLearning.Montreal,Canada,IEEEPress， 2009： 618-622．

[12]TSOCHANTARIDISI，JOACHIMST，HOFMANNT，etal.Largemarginmethodsforstructuredandindependentoutputvariables[J].JournalofMachineLearningResearch， 2005(6):1453-1484．

[13]SUTH，ZHANGTW.Corpus-basedHIT-MWdatabaseforofflinerecognitionofgeneral-purposeChinesehandwrittentext[J].InternationalJournalofDocumentAnalysisandRecognition， 2007， 10(1):27-38．

Offline handwritten text line segmentationbased on high-order correlation clustering

YIN Yalin1, LIU Aimin2, ZHOU Xiangdong3

(1.Department of Digital Media Technology, Jianghan University, Wuhan 430056;2.Laboratory and Equipment Department, Central China Normal University, Wuhan 430079;3.Institute of Green and Intelligent Technology, Chinese Academy of Sciences, Chongqing 400714)

Text line segmentation from handwritten document images is one of important pre-processing steps in document image analysis, however, it remains a challenge because the handwritten text lines are often multi-skewed, curved and overlapped. This paper proposed a novel handwritten text line segmentation method based on high-order correlation clustering. First, a hypergraph was constructed with the nodes corresponding to connected components and the edge connecting at least two connected components. Then under the learned similarity measure, the pairs of connected components were labeled as belonging or not belonging to the same text line. Finally, the connected components were merged into different text lines using union-find algorithm. In experiments on a database with 803 unconstrained handwritten Chinese document images(HIT-MW), the proposed method achieved a correct rate 99.05%, and an error rate of 1.96%.

handwritten text line segmentation; high-order correlation clustering; hypergraph

2016-09-11.

國家自然科學基金項目(61273269).

1000-1190(2017)01-0018-05

TP317.2

A

*E-mail: yinyalin@jhun.edu.cn.