基于投影的文本圖像版面分割算法研究

魏傳義，陳　勤，2，張　旻，2

（1．杭州電子科技大學信息安全部級重點實驗室，杭州310018；2．杭州電子科技大學計算機學院，杭州　310018）

?

基于投影的文本圖像版面分割算法研究

魏傳義1，陳勤1，2，張旻1，2

（1．杭州電子科技大學信息安全部級重點實驗室，杭州310018；2．杭州電子科技大學計算機學院，杭州310018）

摘要：版面分割算法是版面分析的重要組成部分，考慮自頂向下方法的效率優勢以及所處理對象的特殊性，提出一種分列投影版面分割算法。該算法首先將文本圖像進行列分區，劃分為若干個列，然后對每一列進行投影掃描，通過多次投影將文本圖像分割成若干個子區域。實驗結果表明，該方法繼承投影法本身計算速度快的特點，同時還可以避免圖像信息弧度對版面分割的影響，并且對版面較復雜的文本圖像也能夠準確地分割。

關鍵詞：文本圖像；版面分割；自頂向下；分列投影

0　引言

信息時代發展之迅速，信息的不斷膨脹對文本圖像的存儲產生巨大壓力，因此需要對這些信息進行分層壓縮。分層是把文本圖像分離成前景層和背景層，然后采用不同的壓縮編碼技術，前景層主要包括文本和線條組成的一些區域，背景層包括紙的背景紋理和一些圖片區域。分層的過程是對文本圖像進行理解分析的過程，因此要通過版面分析的手段對文本圖像進行分層。首先將文本圖像劃分為若干個子區域，然后通過區域識別將這些子區域進行分類。

文本圖像的版面分割算法可以分為兩類：自頂向下[1-2]和自底向上[3]。自頂向下方法從全局出發，逐步劃分為多個子區域，代表性的方法有投影法[4-6]和游程平滑算法[7]。自頂向下方法的優點是速度快，但是對版面較復雜的情形適應性差。自底向上方法從像素或小區域出發，將具有相似特征的區域進行合并，最終形成多個子區域，常用的方法有區域生長法和區域分裂合并法。自底向上方法注重細節，但是計算量大。由于至今仍沒有一個通用的方法，針對特定的場景要使用特定的方法。考慮到所要處理對象的特殊性，光照不均勻的情況可以由局部自適應二值化方法進行處理，傾斜的圖像可以由傾斜校正方法處理，但是有時候會出現拍照的時候由于紙張不平或者角度不正確，導致圖像中的文字、表格和圖形會產生一定的弧度。標準的投影法從全局出發，將整個文本圖像進行水平和豎直投影，通過投影輪廓圖進行區域劃分。當采集到的文本圖像中含有弧度信息時，投影所產生的輪廓圖特征就不明顯，為版面分割帶來了一定的困難。

本文提出一種分列投影版面分割算法，首先將文本圖像劃分為N列，然后對每一列進行水平和垂直方向投影，通過多次投影將文本信息劃分為多個子區域。實驗結果表明，該方法繼承了投影法本身計算速度快的特點，同時還可以避免圖像弧度對版面分割的影響，并且對排版較復雜的文本圖像也有很好的適應性。

1　文本圖像版面分割主要思路

首先將整個圖像分成N個部分，每一部分高度不變，寬度是原來的1/N，劃分結構如圖1所示。由圖1可以看出，對于一個含有一定弧度信息的文本圖像，如果將整個文本圖像劃分為多列，每一列中信息的弧度基本可以忽略不計。因此可以有效地避免弧度對投影的影響，提高分割的準確度。

圖1　含有弧度文本圖像的分列結構圖

經過分列之后，對每一列進行投影掃描，為了能更準確地進行版面分割，本文采用多次投影法。

文本圖像版面分割的算法流程分為以下幾個步驟：

（1）首先對文本圖像進行預處理等一系列操作，然后在水平方向上進行投影掃描，通過投影圖確定區域的上下邊界。

（2）對每一個確定上下邊界的區域，在豎直方向上進行投影掃描，同時運用游程平滑算法，確定區域的左右邊界，形成了若干個矩形區域。

（3）對每一個矩形區域，在水平方向上進行二次投影掃描，將每個矩形區域劃分出多個子矩形區域。

（4）對每一個子矩形區域進行特征提取，并將這些子區域進行識別分類。

2　分列投影版面分割

在上面的步驟中，投影方法分為3類：（1）水平方向投影；（2）豎直投影；（3）二次水平方向投影。

2.1水平方向的投影

二值化后的圖像只有黑白兩種顏色，像素灰度值為0和255，這里約定黑像素點記為1，白像素點記為0。即：

對二值圖像從上到下逐行進行掃描，并同時獲取每個掃描行的黑像素點，并統計黑像素點（即value（i，j）=1）的個數。即：

設定適當的閾值W，當pixelRow[j]＞W時，記為1，否則記為0。即：

對于計算后得到的值Horizontal[j]，遍歷整個數組，當數組里的值由0變為1時，把j的值記錄在flagStart[ ]中，當值由1變為0時，把j的值記錄在flagEnd[ ]中，這兩個標記所記錄的是連續黑像素的上下邊界，記錄邊界是為了能夠更好地定位出所要分割的區域。

將Horizontal[j]中連續的黑像素值進行累加，得到多個值，每個值都表示一段連續的長度（L1，L2，…，Li，…，Ln），n為連續長度段的個數。文本圖像中可能會包含有部分圖片區域，由于圖片區域的像素點比較密集，所以圖片的黑像素的連續長度一般要比文字的要長，為了能夠準確地定位出圖片所在的大概區域，可以分為以下3種情況：

（1）由大量的文本圖像統計可知：對于鋪滿整張的文本圖像，當n≤8時，文本圖像中必然存在較多的圖片、表格等，在這種情況下，設定閾值T1，當Li＞T1時，記錄Li的上下邊界；對于只鋪滿一部分的文本圖像，閾值T1同樣適用。

（2）對于鋪滿整張的文本圖像，當n＞8時，文本圖像中存在較少的圖片、表格等，在這種情況下，設置閾值T2，當Li＞T2時，記錄Li的上下邊界；對于只鋪滿一部分的文本圖像，閾值T2同樣適用。

（3）對于純文字的文本圖像，通常會有一些大號字體，粗體等文字，這些字體的特征有時會和圖片、表格的特征有些類似。這樣的情況下，無論是鋪滿整張的文本圖像，還是只鋪滿一部分的文本圖像，都適用于上述兩種情況下的閾值T1和T2，并記錄Li的上下邊界。

2.2豎直方向的投影

對于二值化處理后的文本圖像，經過水平方向的投影之后，基本確定了一些區域（d1，d2，…，di，…，dn），這些區域具有可能包含圖片、表格等具有類似特征的上下邊界，然后對區域di從左到右進行掃描。由于字與字之間是有間隙的，不同特征的區域之間也是有間隙的。一般情況下，不同特征區域間的間隙要比文字間的間隙大，為了能更好地分割出一塊整體的區域，不至于把每個字符都分割開來，需要把文字間的間隙進行填充。

游程平滑算法（RLSA）是掃描并檢測同一行上的黑像素點之間的距離，當任意兩個相鄰黑像素之間的白像素游程長度小于設定的閾值時，則將這兩點之間的所有白像素點轉換為黑像素點。例如，對于水平掃描線上的一段游程，L=（P1，P2，…，Pi，Pi+1，…，Pj-1，Pj，…，Pn），其中游程L1=（P1，…，Pi）和L3=（Pj，…，Pn）是1-游程（即黑像素游程），而L2=（Pi+1，…，Pj-1）是0-游程（即白像素游程），設定閾值T，當L2的長度j-i-1小于設定的閾值T時，則將兩個黑像素游程L1和L3連接起來（即把游程L2的全部平滑成黑像素點）。以T=4為例，如圖所示的平滑過程中，其中有兩個1-游程之間的0-游程長度為3，因此要被平滑為1-游程，這樣通過游程掃描連接起來的1-游程的長度為10。

平滑前：1111100000 1111100011

平滑后：1111100000 1111111111

利用游程平滑算法，設定閾值T3，當字符內以及字符間的間隙小于T3時就被填充，不同的區域就更加明顯了，然后再通過豎直方向的投影，把不同的區域劃分開并記錄不同區域的左右邊界（原理同水平方向的投影），有了上下邊界和左右邊界，基本可以確定一些完整的矩形區域。

2.3二次水平方向的投影

經過豎直方向的投影之后，不同區域的上下邊界和左右邊界雖然已經確定，但是由于文字和圖片或者表格在同一矩形區域的情況，以及部分水平區域錯位的情況下，已經形成的矩形區域中不完全只包含圖片、表格等。為了提高分割的準確率，對這些矩形區域再次進行水平投影，并把每一段連續的黑像素都進行分割，并重新記錄上下邊界，最終形成一系列的矩形區域（D1，D2，…，Di，…，Dn），并為每一個Di設置標記Mi=0。

分列投影的版面分割算法使用了多次投影的方法，投影次數為三次，并同時使用游程平滑算法。分列投影不僅可以有效地避免弧度對投影的影響，同時還有效地避免了雙欄錯位對投影的影響，提高了分割的準確度。在第二次投影時，使用了游程平滑算法，可以避免對文本行的過度分割。該算法速度快，執行效率高。不僅重視全局信息，同時也間接從局部出發，對于版面排版較復雜的文本圖像也能較好地適應。

3　區域識別

對于得到的一系列矩形區域（D1，D2，…，Di，…，Dn），每一個Di可能是純文字、圖片、或者表格等，為了能更好地區分，需要對它們進行一些特征值的提取。因為最終需要的只有圖片區域，對于其他區域予以排除即可。圖片區域在二值化之后仍有大量而又密集的黑像素點，并且分布也不規則；而文字和表格等主要是由線條組成，字與字之間存在間隙，通過提取有效的特征值，可以準確地區分圖片區域和其他區域。

（1）投影特征

版面分割得到的各個子區域Di在豎直方向上的投影存在著比較大的差異，文字區域和表格區域的投影峰值具有明顯的周期性，而圖片區域并不具有這些特點。文字區域由于文字間有間隙，因此垂直投影會出現周期性間斷，表格區域由于存在表格框線，水平和垂直投影都會出現明顯的周期性峰值。

（2）交錯計數

交錯計數所表示的是在圖像某個方向上，像素黑白交替變換的頻率。本文提取圖像各個矩形區域Di在水平方向（PH）、豎直方向（PV）、對角線方向（PD）的交錯計數。如公式（4）、（5）、（6）所示：

式（4）中：⊕表示異或運算。由于文字區域和表格區域主要是由線條組成，區域內會出現頻繁的黑白像素交替，同樣，對于大號黑體和粗體文字，黑白交替也會比較頻繁，而圖片區域則不會。

（3）邊緣比

邊緣比定義為子區域Di中邊緣化后黑像素點總數和Di中黑像素點總數的比值。計算如公式（7）所示：

其中：

式（8）中，pixel'（i，j）表示區域Di中先進行二值化處理，再邊緣化后的像素灰度值。由于文字和表格區域中是由大量的線條組成，邊緣化后的信息非常豐富，因此，在進行邊緣提取后，會保留大量的邊緣像素點。而圖片區域則并不具備這個特點。

對投影特征、交錯計數和邊緣比這些特征值的提取之后，通過這些特征值設計一個合適的判定策略，當子區域Di符合圖片的特征時，記錄其區域范圍，并令Mi=1；否則，予以排除。

4　實驗結果與分析

為了驗證本章所提出的分列投影版面分割算法的有效性，針對含有弧度區域信息的文本圖像，實驗結果如圖2（c）和（d）所示。

由圖2可以看出，圖（a）是原圖，圖（b）是二值化圖，圖（c）和（d）是由圖（a）通過分列投影版面分割算法得到的結果。實驗結果表明，該算法對于含有弧度的文本圖像能夠較好地進行分割，并且對于版面較為復雜的文本圖像也能得到較好的結果。

由圖（c）可知，部分的粗體文字也被分割了出來。因為這些粗體文字同樣還有大量的像素點，具有和圖片區域類似的特征，可以劃分到該區域內。但是還有一部分粗體文字被劃分到了圖（d）的部分，主要是由于那部分區域的弧度較大所引起的。

同時本文還搜集了500幅文本圖像，并對每幅圖像都進行處理，處理步驟如圖3所示。

總共500幅樣本圖像，經過人工篩選后，其中213幅為純文本圖像，287幅為圖文混合圖像，通過圖3所示的流程對文本圖像進行處理，實驗結果如表1所示。

圖2　弧度型文本圖像分割效果圖

參考文獻：

[1]G. Nagy and S. Seth. Hierarchical Representation of Optically Scanned Documents[C]. ICPR（7），1984: 347-349.

[2]F.M. Whal，K.Y. Wong and R.G. Casey. Block Segmentation and Text Extration in Mixed Text/Image Documents[C]. CGIP，1982，20: 375-390.

[3]陳明，丁曉青，吳佑壽.多層次可信度指導下的自底向上的版面分析算法.模式識別與人工智能，2003，16（2）: 198-203.

[4]王海琴，戴汝為.基于投影和遞歸的版面理解算法[J].模式識別與人工智能，1997，10（2）: 118-126.

[5]Laurence Likforman-Sulem，Abderrazak Zahour. Text Line Segmentation of Historical Documents:a Survey [J]. International Journal on Document Analysis and Recognition，2007，9: 123-138.

[6]Zujovic. J，Pappas T N，Neuhoff D L. Structural Similarity Metrics for Texture Analysis and Retrieval[C]. Proceedings of the 2009 16th IEEE International Conference on Image Processing，Egypt: 2009. 225-228.

圖3　文本圖像處理流程圖

表1　實驗數據結果統計

如表1所示，N為分列數。當N=4時，無論是純文本圖像，還是圖文混合圖像，都有較好的結果。對于純文本圖像，不同分列數的分割效果都比較好，雖然此時N=8的效果要好于N=4，但是對于圖文混合圖像，參數N越大，越容易對圖片區域的過度分割，導致部分信息丟失，分割出錯。

綜合考慮以上情況，取參數N=4較好。

圖2和表1的實驗結果表明，有弧度的情形適合使用分列投影的方法。該方法從全局出發，將整體進行分列，并對每一部分進行版面分割，避免了弧度對投影分割所產生的影響。而自底向上的方法是從局部到整體的思想，對每一部分進行合并形成不同的區域。由于文本圖像中含有弧度，在進行合并的時候，會把不同的區域進行粘連。如圖4所示。

圖4　自底向上方法的區域合并

由圖4可知，當使用自底向上方法對文本圖像進行區域合并時，由于弧度的影響，會使不同類型的區域進行粘連，容易導致分割不徹底，會將不同類型的區域混合在一起，產生錯誤的分割結果。

5　結語

本文所提出的分列投影版面分割算法，實現不復雜，運算速度快。對于目前大部分的文件資料、圖書館學習資料都有較好地分割效果。相對于標準的投影法，當文本圖像是混合文本圖像時，分割的準確率有了較大地提升。不僅可以有效地避免弧度對投影的影響，同時還有效地避免了雙欄錯位對投影的影響，對版面較復雜的文本圖像也有較好的適應性。

研究過程中發現該方法仍然存在一些不足之處，閾值的選取對版面分割起到了關鍵的作用，直接影響分割的效果，對于版面很復雜的文本圖像，該算法雖然有所改善，但是適應性依然不高。這些不足之處需要在以后的深入研究中逐步解決。

[7]C Strouthopoulos，N Papamarkos，C Chamzas. PLA Using RLSA and A Neural Network[J]. Engineering Applications of Artifical Intelligence，1999，12：119-138.

[8]王緒.文本圖像處理與表格圖像識別算法研究[D].解放軍信息工程大學，2010.

[9]靳從.中文版面分析關鍵技術的研究[D].南京理工大學，2007.

[10]郭麗，孫興華，王正群，等.一種基于連通域的版面分割方法[J].計算機工程與應用，2003，5：103-107.

陳勤，男，教授，碩士生導師

張旻，男，博士，講師

Research on Document Image Layout Segmentation Algorithm Based on Projection

WEI Chuan-yi1，CHEN Qin1，2，ZHANG Min1，2
（1．Ministerial Key Laboratory of Information Security，Hangzhou Dianzi University，Hangzhou 310018；2．College of Computer Science，Hangzhou Dianzi University，Hangzhou 310018）

Abstract：Layout segmentation algorithm is an important part of layout analysis, considers the efficiency advantage of the top-down approach and the special properties of the processed object, presents a breakdown projection layout segmentation algorithm. Firstly, the text image column partition, is divided into several columns. Then for each column projection scanning, by repeatedly projected the text image split into several sub-regions. Experimental results show, this method inherits the projection method to calculate the characteristics of speed, while avoids the influence of the curvature of the page segmentation, and for more complex text layout image also be able to accurately split.

Keywords：Document Image; Layout Segmentation; Top Down; Breakdown Projection

收稿日期：2016-01-21修稿日期：2016-03-24

作者簡介：魏傳義（1990-），男，河南商丘人，碩士研究生，研究方向為智能圖像處理

文章編號：1007-1423（2016）10-0033-06

DOI：10.3969/j.issn.1007-1423.2016.10.008

基金項目：浙江省重大科技計劃項目