基于貪婪算法的文檔圖像中干擾線的去除①

王 平，張曉峰，王宜懷，程仁貴

1(武夷學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，武夷山 354300)

2(南通大學(xué) 信息科學(xué)技術(shù)學(xué)院，南通 226019)

3(蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，蘇州 215006)

4(認(rèn)知計(jì)算與智能信息處理福建省高校重點(diǎn)實(shí)驗(yàn)室，武夷山 354300)

紙質(zhì)文檔的內(nèi)容數(shù)字化處理工作，在各行各業(yè)中廣泛應(yīng)用，目前較為典型、高效的方式是通過(guò)將紙質(zhì)等重要文檔通過(guò)掃描、照相等方法獲得其數(shù)字化文檔圖像.這些包含大量文字內(nèi)容信息的數(shù)字化圖像資料的好處在于，一方面這些資料是數(shù)字化的文件，很容易保存在計(jì)算機(jī)的存儲(chǔ)器中，方便存儲(chǔ)和管理；另一方面，這些文檔可以進(jìn)一步使用OCR 軟件進(jìn)行識(shí)別，能夠快速地獲得文檔圖像中的內(nèi)容，避免了繁瑣的文字輸入工作.目前，如果文檔僅僅是只包含文字的文檔圖像，尤其是印刷體文字，其OCR 的識(shí)別率非常高，能達(dá)到99%以上，已經(jīng)在各種領(lǐng)域中得到應(yīng)用.然而，大多數(shù)文檔中經(jīng)常包含各種干擾信息，如各種干擾線，例如當(dāng)人們?cè)谠嘉臋n上留下橫線等來(lái)標(biāo)記文檔中的重要內(nèi)容，或者文檔本身就存在各種橫線表示需要填寫(xiě)信息或者其他提醒時(shí)，則文檔圖像的OCR 的識(shí)別率會(huì)急劇下降.因此，如何去除文檔圖像中的干擾線成為文檔圖像OCR 前的一個(gè)重要的預(yù)處理問(wèn)題.

1 研究概況

文檔圖像去除干擾線的以往工作可以分為兩類，一類是規(guī)則線段，另一類是不規(guī)則的手劃線.規(guī)則線段一般表現(xiàn)為印刷的下劃線、表格的邊緣線等.對(duì)于規(guī)則線段的處理，Bai 等人[1]通過(guò)連通分量分析和下邊緣分析策略獲得干擾線的位置，并去除，但是該方法只能處理文檔圖像中標(biāo)準(zhǔn)的下劃線去除；Shi 等人[2]為了去除手寫(xiě)阿拉伯?dāng)?shù)字中的規(guī)則的線段使用了一種directional local profiling 方法，但是該方法只能檢測(cè)和去除預(yù)打印規(guī)則行線段；Alipour 等人[3]利用了規(guī)則橫線的特征去除手寫(xiě)文檔中的橫線，重點(diǎn)考慮了線的邊緣檢測(cè)；Imtiaz 等人[4]使用滑動(dòng)窗口中的熵來(lái)判斷當(dāng)前區(qū)域中是否包含干擾線，以便達(dá)到去除水平規(guī)則線和垂直邊緣線的目的.而對(duì)于不規(guī)則的干擾線，比如手劃線的表現(xiàn)較規(guī)則的線段去除復(fù)雜得多，各種文獻(xiàn)中也出現(xiàn)了多種方法，Cheng 等人[5]使用超圖來(lái)檢測(cè)圖像中的干擾線，采用主曲線方法、改進(jìn)的最短路徑法和方向偏移算法實(shí)現(xiàn)，整個(gè)方法稍顯復(fù)雜，且沒(méi)有說(shuō)明當(dāng)干擾線與字符筆畫(huà)重合時(shí)如何只去掉干擾線，而保留字符；Kaur 等人[6]基于連通元的FCM 聚類、分類方法找到干擾線的區(qū)域并去除，但其要求是取定類型的標(biāo)注和下劃線；Banerjee 等人[7]也使用連通元檢測(cè)干擾線區(qū)域，并對(duì)與文字粘連的干擾線特殊處理；Rehman 等人[8]首先處理了粘連的字符和干擾線，然后判斷連通元；Pratihar 等人[9]利用文檔圖像中的像素間的幾何關(guān)系檢測(cè)干擾線；Das 等人[10]利用Gabor 濾波器和連通分量分析并檢測(cè)干擾線；近年來(lái)深度學(xué)習(xí)發(fā)展迅速，干擾線去除領(lǐng)域也出現(xiàn)了許多使用深度學(xué)習(xí)網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)的方法[11，12].

基于以上文獻(xiàn)的處理方法及分析其不足之處，本文提出一種新的與文字耦合粘連干擾線的去除方法，該方法處理中首先將文檔圖像進(jìn)行二值化，去除部分噪聲像素后得到文檔的主要部分；然后通過(guò)細(xì)化，得到單像素的線條；接著計(jì)算這些線條的代價(jià)，若代價(jià)超過(guò)預(yù)先設(shè)定的閾值，則認(rèn)為其是存在的一條干擾線；最后，通過(guò)前景像素與干擾線的距離判斷其歸屬，達(dá)到文字文檔干擾線去除的目的.此所提出的方法使用了貪婪算法計(jì)算線條代價(jià)，整個(gè)算法速度較快，并將提出的算法在多種類型的文檔圖像的測(cè)試中，獲得了較好的效果.

2 圖像預(yù)處理

文檔圖像的預(yù)處理是為了提取出文字的主要特征部分，減少噪聲的干擾.本文方法的預(yù)處理包含兩個(gè)步驟，圖像二值化和圖像細(xì)化，其中圖像二值化是為了提取出文檔圖像的前景內(nèi)容部分，而圖像細(xì)化目的則是將前景部分的內(nèi)容描述為中心線的形式呈現(xiàn)，以減少線條的粗細(xì)對(duì)干擾線檢測(cè)的影響.

2.1 圖像二值化

圖像二值化是一種常規(guī)的圖像預(yù)處理方法，且二值化的算法有很多，性能也不盡相同.對(duì)于文字比較清晰的圖像，用全局閾值的方法就可以獲得較好的二值化效果，但是若獲取的文檔圖像的質(zhì)量較差，就需要采用局部閾值方法進(jìn)行處理.考慮到實(shí)際應(yīng)用中，諸如通過(guò)掃描、照相等方法獲得的文檔圖像的亮度變化不太均勻，故而本文使用一種由局部閾值插值產(chǎn)生全部位置閾值的方法.

局部閾值是一個(gè)針對(duì)局部區(qū)域塊的閾值，這種局部區(qū)域塊范圍不能太大，若太大則設(shè)置的閾值可能不適用，無(wú)法有效檢測(cè)出干擾線，也不能很小，若很小則也無(wú)法反映該局部區(qū)域塊的前景和背景的像素強(qiáng)度分布.

本文將一幅大小為m×n的文檔圖像等分成大小相等的塊，假設(shè)等分成m1×n1個(gè)塊(即列方向等分成m1份，行方向等分成n1份)，則每塊中像素的數(shù)目為(m×n)/(m1×n1).為了保證每塊中像素?cái)?shù)目不太少，m1和n1均不能太大，實(shí)驗(yàn)中它們的取值范圍是5～10 之間的整數(shù).每個(gè)小塊中的局部閾值使用大津法獲得，然后使用線性插值法從局部閾值獲得每個(gè)位置的閾值T(i,j)，當(dāng)然，若使用非線性插值也許可以獲得更好的效果，但是消耗的時(shí)間開(kāi)銷也會(huì)相應(yīng)增加.因此，此處的圖像二值化可以描述為：

如圖1所示，圖1(a)是一幅原始的文檔圖像，圖1(b)是其圖像二值化的結(jié)果.從圖中可以看出，提出的圖像二值化方法在不均勻光照的文檔圖像中取得了較好的二值化效果.

2.2 圖像細(xì)化

一般情況下，文檔中的文字和相關(guān)干擾線都可以通過(guò)筆畫(huà)的中心線來(lái)判斷，而且中心線有效地去除了其他像素所引起的干擾因素，能有效地降低判斷的難度.本文使用matlab 中常用的圖像細(xì)化方法，該方法通過(guò)8 個(gè)模板不斷地消減二值化圖中邊緣多余像素，能得到較好的細(xì)化效果.如圖2所示，顯示了圖像細(xì)化的效果，圖2(a)是包含干擾線的圖，圖2(b)是圖2(a)的細(xì)化結(jié)果，可以看出，該方法細(xì)化后的能較好地保留文字的特征輪廓.

3 基于貪婪算法的圖像干擾線檢測(cè)

通過(guò)上述圖像二值化和細(xì)化的預(yù)處理操作之后，能獲得文檔的中心線.進(jìn)一步通過(guò)觀察和分析，干擾線的中心線具有以下和文字不同的表現(xiàn)特征：

(1)干擾線一般為橫向，偶爾出現(xiàn)豎方向，極少出現(xiàn)旋轉(zhuǎn)方向；

(2)干擾線一般較長(zhǎng)，遠(yuǎn)遠(yuǎn)大于文字字體的大小.

圖1 圖像二值化

圖2 圖像細(xì)化

因此本文方法中考慮去除的干擾線具有以下特征：?jiǎn)我环较?橫向或者豎向)，且大于一定長(zhǎng)度.這兩種特征既符合干擾線的特性，又極大地降低了檢測(cè)干擾線的難度.其中“單一方向”通過(guò)掃描圖像時(shí)只遵循“從下往上，從右到左”的原則來(lái)保障，而“大于一定長(zhǎng)度”通過(guò)線段的權(quán)值Vli大于閾值Tl保證，即：

其中，計(jì)算每條中心線的權(quán)值Vli的算法，如下所述：

(1)初始化，設(shè)Vli=0(i=1,···,n)，其中n是圖像中包含中心線的數(shù)目；

(2)掃描前方的像素點(diǎn)，并加上相應(yīng)的權(quán)值；

(3)循環(huán)步驟(2)，直到遍歷了細(xì)化圖像中每個(gè)像素點(diǎn).

為了讓Tl的設(shè)置具有自適應(yīng)性，其取值如下：

其中，Vlm是所有Vli的中值.這樣就可以根據(jù)當(dāng)前文檔圖像的情況，獲得閾值.

如圖3所示，其顯示了上述步驟(2)中處理的3 類情況，黑色的為當(dāng)前像素點(diǎn)，灰色的是前方像素點(diǎn)，這些都是中心線上的像素點(diǎn).其中，當(dāng)前像素點(diǎn)的前方像素點(diǎn)分3 種情況：圖3(a)表示正前方有像素點(diǎn)，圖3(b)表示側(cè)前方有像素點(diǎn)，而圖3(c)的傾斜的角度更大一些.圖3(a)情況的權(quán)值為3，圖3(b)為2，圖3(c)為1.對(duì)于一個(gè)位置，只能屬于這3 種情況其中的一種，并且優(yōu)先屬于權(quán)重較大的.比如一個(gè)位置既滿足圖3(a)和圖3(b)時(shí)，它只屬于圖3(a)，其他情況依次類推.由于在一個(gè)位置只取了權(quán)值的最大值，因此該提出的算法屬于貪婪算法的一種.

圖3 當(dāng)前像素的前方像素3 類情況

另外，上述算法過(guò)程中主要考慮的是橫向的干擾線，對(duì)于豎向的干擾線的檢測(cè)，則有兩種方案：旋轉(zhuǎn)模板或者旋轉(zhuǎn)圖像，這兩種方法都是可行的，而斜向的干擾線在橫向和豎向的檢測(cè)過(guò)程中都有兼顧，因此不需要單獨(dú)列出來(lái).

由此，通過(guò)采用本節(jié)基于貪婪算法的干擾線檢測(cè)算法，可計(jì)算如圖2所示的中心線權(quán)值，得到干擾線的中心線Cg，如圖4所示.去除掉干擾線的中心線Cg部分余下的則是文字中心線Cw，下一節(jié)給出相應(yīng)的方法.

圖4 檢測(cè)出的干擾線部分

4 圖像干擾線去除

通過(guò)上面的方法，檢測(cè)出干擾線的具體位置后，需要將二值化圖像中的干擾線去除，只留下文字部分.一般情況下，某個(gè)前景像素到文字中心線Cw和干擾線中心線Cg哪個(gè)距離近，就可以認(rèn)為它屬于距離近的那個(gè)部分.即：

其中，D是像素I(x,y) 到Cw或Cg的 距離，Ib為干擾線像素集合，If為文字像素集合.

直接求解距離的計(jì)算量比較大，因此可以使用以下方案(這里以求到文字中心線Cw的距離為例)：

(1)初始化距離矩陣(與圖像大小相同)中所有的位置為一個(gè)極大值max(實(shí)驗(yàn)中可取值10 000)；

(2)設(shè)置Cw中所有的像素對(duì)應(yīng)位置的距離為0；

(3)設(shè)置所有距離為max且與距離0 相鄰的位置距離為1；

(4)循環(huán)步驟(3)，設(shè)置所有距離為max且與距離i相鄰的位置距離為i+1.

通過(guò)本節(jié)圖像干擾線去除算法的處理，將如圖2所示的內(nèi)容去除干擾線之后的效果如圖5所示，可以看出，本方法對(duì)文字內(nèi)容的輪廓、文字線條的連續(xù)性等都具有較好的保留.

圖5 干擾線去除效果圖

5 實(shí)驗(yàn)分析

本文所提的方法，主要針對(duì)文檔圖像OCR 處理之前的相關(guān)干擾線的去除預(yù)處理，采用了原始文檔圖像二值化、細(xì)化獲得中心線，再采用貪婪算法的方式對(duì)所有中心線中的相關(guān)干擾線進(jìn)行檢測(cè)和去除，實(shí)驗(yàn)分別在人造文檔圖像和真實(shí)掃描文檔圖像上進(jìn)行.

首先，本文所提出的方法在一組人為制造的圖像上進(jìn)行測(cè)試，人為制造的文檔局部圖像如圖6(a)所示.由于該人為制造出的圖像中的干擾線與文字內(nèi)容較為粘連耦合，這增加了干擾線去除的精度，對(duì)方法的要求較高，因此能夠考驗(yàn)本文方法在這種極端條件下的性能.如圖6(b)所示為本文方法去除干擾線效果，其中，在第一組中，由于人為干擾線與文字的粘連耦合度很高，故而造成干擾線去除時(shí)將個(gè)別文字的一些筆畫(huà)也去除掉，但文字上下文內(nèi)容仍然保留精確，后續(xù)的OCR 處理仍然基本是有效的，實(shí)際情況處理中，這種極度粘連耦合的情況應(yīng)該是極少的；在第二組中，人為干擾線與文字的粘連耦合度一般，可以看出干擾線去除效果很好，極大地保留了文字內(nèi)容的完整性和可讀性，經(jīng)進(jìn)一步的清華紫光OCR 軟件測(cè)試能100%正確獲取該局部圖像的文字內(nèi)容.

然后，本文所提方法再在一組真實(shí)文檔的掃描圖像上進(jìn)行實(shí)驗(yàn)測(cè)試.原始文檔圖像如圖7(a)至圖7(c)所示，這組圖像是掃描現(xiàn)實(shí)文檔獲得的，并希望通過(guò)OCR 獲取其中的文字.這些圖像中均包含了較多的干擾線，如規(guī)則的長(zhǎng)橫線、不規(guī)則的劃線等.由于干擾線的判斷具有一定主觀性，而本文干擾線去除方法的目的重點(diǎn)在于保留文檔的文字內(nèi)容，以便OCR 能以高精度獲取文字內(nèi)容，因此本方法主要實(shí)現(xiàn)將規(guī)則的長(zhǎng)橫線、不規(guī)則的劃線等理論上都識(shí)別成相關(guān)干擾線，并根據(jù)自適應(yīng)獲取的閾值進(jìn)行相關(guān)干擾線的判斷檢測(cè)，進(jìn)而予以去除，結(jié)果如圖8所示.從圖中可以看出，本文所提方法對(duì)長(zhǎng)度超過(guò)閾值的干擾線，包括原文中的長(zhǎng)橫線、劃線等都能有效去除，較為清晰的保留了文字內(nèi)容的完整性，而一些短劃線的殘留分兩種情況，一種是短劃線與文字的粘連耦合度高，如與文字筆畫(huà)重合，影響了閾值判斷，另一種是本身其長(zhǎng)度低于了閾值.

圖6 人造圖像的實(shí)驗(yàn)結(jié)果

為了測(cè)試與類似算法的性能，原始文檔圖像經(jīng)本文方法去除相關(guān)干擾線之后，經(jīng)過(guò)清華紫光OCR 軟件測(cè)試，如表1所示，能正確獲取文字內(nèi)容的占比率大幅提高，表明本文方法在去除原始文檔干擾線預(yù)處理中是有效的.另外與類似算法的比較中，本文提出的算法，雖然在正確率上沒(méi)有絕對(duì)的優(yōu)勢(shì)，但由于算法步驟少，在速度上超越了原有的一些方法，如表2所示.

通過(guò)上述實(shí)驗(yàn)測(cè)試，本文提出的算法能夠有效地去除文檔圖像中的相關(guān)干擾線且處理速度快，特別是對(duì)于和文字粘連在一起的干擾線去除也能有較好的效果，自適應(yīng)長(zhǎng)度閾值的處理方法使得本文方法可以針對(duì)各種各樣的文檔圖像的相關(guān)干擾線進(jìn)行檢測(cè)和去除.

圖8 真實(shí)掃描圖像去除干擾線的實(shí)驗(yàn)結(jié)果

表1 與原始文檔圖的測(cè)試正確率OCR 識(shí)別性能對(duì)比(%)

表2 與文獻(xiàn)[7]、文獻(xiàn)[9]的速度對(duì)比(毫秒)

6 結(jié)論與展望

本文提出了一種干擾線去除的方法，該方法先通過(guò)預(yù)處理得到每個(gè)文字或線條的中心線，然后利用貪婪算法計(jì)算每條中心線的權(quán)值，并認(rèn)為權(quán)值大于閾值的中心線處存在干擾線，最后結(jié)合形態(tài)學(xué)操作去除干擾線并盡可能保留文字.提出的算法能較為有效地去除干擾線部分，同時(shí)對(duì)規(guī)則的長(zhǎng)橫線、豎線以及不規(guī)則的劃線也能一并消除，從而降低了文檔圖像中的OCR 處理的干擾因素，經(jīng)實(shí)驗(yàn)測(cè)試表明該方法是有效的.另外，由于采用的細(xì)化算法會(huì)產(chǎn)生毛刺，從而影響最終的去除效果，因此下一步工作中需要優(yōu)化細(xì)化算法.