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

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

（1．杭州電子科技大學(xué)信息安全部級重點(diǎn)實(shí)驗(yàn)室，杭州310018；2．杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，杭州　310018）

?

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

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

（1．杭州電子科技大學(xué)信息安全部級重點(diǎn)實(shí)驗(yàn)室，杭州310018；2．杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，杭州310018）

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

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

0　引言

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

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

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

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

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

圖1　含有弧度文本圖像的分列結(jié)構(gòu)圖

經(jīng)過分列之后，對每一列進(jìn)行投影掃描，為了能更準(zhǔn)確地進(jìn)行版面分割，本文采用多次投影法。

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

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

（2）對每一個(gè)確定上下邊界的區(qū)域，在豎直方向上進(jìn)行投影掃描，同時(shí)運(yùn)用游程平滑算法，確定區(qū)域的左右邊界，形成了若干個(gè)矩形區(qū)域。

（3）對每一個(gè)矩形區(qū)域，在水平方向上進(jìn)行二次投影掃描，將每個(gè)矩形區(qū)域劃分出多個(gè)子矩形區(qū)域。

（4）對每一個(gè)子矩形區(qū)域進(jìn)行特征提取，并將這些子區(qū)域進(jìn)行識(shí)別分類。

2　分列投影版面分割

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

2.1水平方向的投影

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

對二值圖像從上到下逐行進(jìn)行掃描，并同時(shí)獲取每個(gè)掃描行的黑像素點(diǎn)，并統(tǒng)計(jì)黑像素點(diǎn)（即value（i，j）=1）的個(gè)數(shù)。即：

設(shè)定適當(dāng)?shù)拈撝礧，當(dāng)pixelRow[j]＞W(wǎng)時(shí)，記為1，否則記為0。即：

對于計(jì)算后得到的值Horizontal[j]，遍歷整個(gè)數(shù)組，當(dāng)數(shù)組里的值由0變?yōu)?時(shí)，把j的值記錄在flagStart[ ]中，當(dāng)值由1變?yōu)?時(shí)，把j的值記錄在flagEnd[ ]中，這兩個(gè)標(biāo)記所記錄的是連續(xù)黑像素的上下邊界，記錄邊界是為了能夠更好地定位出所要分割的區(qū)域。

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

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

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

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

2.2豎直方向的投影

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

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

平滑前：1111100000 1111100011

平滑后：1111100000 1111111111

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

2.3二次水平方向的投影

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

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

3　區(qū)域識(shí)別

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

（1）投影特征

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

（2）交錯(cuò)計(jì)數(shù)

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

式（4）中：⊕表示異或運(yùn)算。由于文字區(qū)域和表格區(qū)域主要是由線條組成，區(qū)域內(nèi)會(huì)出現(xiàn)頻繁的黑白像素交替，同樣，對于大號(hào)黑體和粗體文字，黑白交替也會(huì)比較頻繁，而圖片區(qū)域則不會(huì)。

（3）邊緣比

邊緣比定義為子區(qū)域Di中邊緣化后黑像素點(diǎn)總數(shù)和Di中黑像素點(diǎn)總數(shù)的比值。計(jì)算如公式（7）所示：

其中：

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

對投影特征、交錯(cuò)計(jì)數(shù)和邊緣比這些特征值的提取之后，通過這些特征值設(shè)計(jì)一個(gè)合適的判定策略，當(dāng)子區(qū)域Di符合圖片的特征時(shí)，記錄其區(qū)域范圍，并令Mi=1；否則，予以排除。

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

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

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

由圖（c）可知，部分的粗體文字也被分割了出來。因?yàn)檫@些粗體文字同樣還有大量的像素點(diǎn)，具有和圖片區(qū)域類似的特征，可以劃分到該區(qū)域內(nèi)。但是還有一部分粗體文字被劃分到了圖（d）的部分，主要是由于那部分區(qū)域的弧度較大所引起的。

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

總共500幅樣本圖像，經(jīng)過人工篩選后，其中213幅為純文本圖像，287幅為圖文混合圖像，通過圖3所示的流程對文本圖像進(jìn)行處理，實(shí)驗(yàn)結(jié)果如表1所示。

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

參考文獻(xiàn)：

[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]陳明，丁曉青，吳佑壽.多層次可信度指導(dǎo)下的自底向上的版面分析算法.模式識(shí)別與人工智能，2003，16（2）: 198-203.

[4]王海琴，戴汝為.基于投影和遞歸的版面理解算法[J].模式識(shí)別與人工智能，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　實(shí)驗(yàn)數(shù)據(jù)結(jié)果統(tǒng)計(jì)

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

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

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

圖4　自底向上方法的區(qū)域合并

由圖4可知，當(dāng)使用自底向上方法對文本圖像進(jìn)行區(qū)域合并時(shí)，由于弧度的影響，會(huì)使不同類型的區(qū)域進(jìn)行粘連，容易導(dǎo)致分割不徹底，會(huì)將不同類型的區(qū)域混合在一起，產(chǎn)生錯(cuò)誤的分割結(jié)果。

5　結(jié)語

本文所提出的分列投影版面分割算法，實(shí)現(xiàn)不復(fù)雜，運(yùn)算速度快。對于目前大部分的文件資料、圖書館學(xué)習(xí)資料都有較好地分割效果。相對于標(biāo)準(zhǔn)的投影法，當(dāng)文本圖像是混合文本圖像時(shí)，分割的準(zhǔn)確率有了較大地提升。不僅可以有效地避免弧度對投影的影響，同時(shí)還有效地避免了雙欄錯(cuò)位對投影的影響，對版面較復(fù)雜的文本圖像也有較好的適應(yīng)性。

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

[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]王緒.文本圖像處理與表格圖像識(shí)別算法研究[D].解放軍信息工程大學(xué)，2010.

[9]靳從.中文版面分析關(guān)鍵技術(shù)的研究[D].南京理工大學(xué)，2007.

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

陳勤，男，教授，碩士生導(dǎo)師

張旻，男，博士，講師

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-），男，河南商丘人，碩士研究生，研究方向?yàn)橹悄軋D像處理

文章編號(hào)：1007-1423（2016）10-0033-06

DOI：10.3969/j.issn.1007-1423.2016.10.008

基金項(xiàng)目：浙江省重大科技計(jì)劃項(xiàng)目