一種新的商務(wù)名片的快速二值化算法

剛亞州，黃元元，戴 群

GANG Yazhou,HUANG Yuanyuan,DAI Qun

南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京210016

Institute of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China

1 引言

名片是人們?nèi)粘Ｉ虅?wù)活動(dòng)中重要的信息載體之一，但是隨著經(jīng)濟(jì)交往的日益頻繁，名片的數(shù)量大大增加，給名片信息的保存和管理帶來(lái)了很大的困難。隨著通信技術(shù)的不斷發(fā)展，通訊終端越來(lái)越普及。運(yùn)用嵌入式識(shí)別系統(tǒng)，手機(jī)可以獨(dú)立完成名片的掃描識(shí)別，實(shí)現(xiàn)對(duì)名片的識(shí)別管理功能，將在很大程度上節(jié)省人力和時(shí)間。

圖像分割在模式識(shí)別、計(jì)算機(jī)視覺(jué)和圖像、視頻的檢索中起著很重要的作用，而二值化處理則是圖像分割的最重要的技術(shù)之一[1-4]。在名片識(shí)別中，名片的文本信息是名片的關(guān)鍵信息。從彩色名片圖像到最終的識(shí)別名片關(guān)鍵信息，需要經(jīng)歷圖像預(yù)處理，版面分析、字符分割、字符識(shí)別等復(fù)雜的過(guò)程。然而通常這些處理都是基于對(duì)原始圖像做好二值化處理的基礎(chǔ)之上，因此名片圖像的二值化處理是整個(gè)名片識(shí)別的關(guān)鍵一步。常規(guī)的二值化處理算法是基于灰度圖像的二值化算法[1-5]，需要針對(duì)灰度化名片圖像特點(diǎn)選擇一個(gè)合適的閾值以便將名片背景和文本字符有效地分割開(kāi)來(lái)。通常，確定閾值的方法有全局閾值法和局部閾值法。全局閾值法是利用圖像的全局信息對(duì)整幅圖像求出一個(gè)最優(yōu)分割閾值。常用的全局閾值法，如簡(jiǎn)單二值化、人際交互、p-參數(shù)法[6]、直方圖法[7]、最大類(lèi)間方差法[7]、最大熵法[8]等；局部閾值法[9]則是把整幅圖像分成若干個(gè)子圖像，在對(duì)每個(gè)子圖像運(yùn)用全局閾值法求出最優(yōu)分割閾值，如Bernsen法。在實(shí)際應(yīng)用中，有效的算法是極其需要的。

2 存在的問(wèn)題

目前常用的全局閾值法是最大類(lèi)間方差法和最大熵法。這兩種二值化方法若直接應(yīng)用于嵌入式環(huán)境下的商務(wù)名片圖像，存在的問(wèn)題有：

（1）假定圖像中存在有L個(gè)灰度等級(jí)，最大類(lèi)間方差方法是使用窮盡的方法來(lái)得到最優(yōu)閾值，其算法的時(shí)間復(fù)雜度為O(L2)。該算法在處理灰度級(jí)不連續(xù)的圖像時(shí)，所求出的閾值不能很好地收斂到全局最優(yōu)[10]。當(dāng)背景和目標(biāo)的兩個(gè)總體分布差異很大時(shí)，該算法將會(huì)失效。

（2）最大熵法二值化強(qiáng)調(diào)系統(tǒng)內(nèi)部的均勻性[11]，應(yīng)用于閾值化分割中就是搜索使目標(biāo)或背景內(nèi)部的灰度分布盡可能均勻的最優(yōu)閾值。該算法的時(shí)空開(kāi)銷(xiāo)大，數(shù)據(jù)稀疏問(wèn)題嚴(yán)重，對(duì)直方圖的分布依賴(lài)性較強(qiáng)。

（3）現(xiàn)在很多的商務(wù)名片中都包含一些圖案和紋理，這些圖案與紋理對(duì)于名片信息并無(wú)任何幫助，但是會(huì)對(duì)名片的版面分割以及后期的字符識(shí)別帶來(lái)諸多影響。但是目前的二值化算法對(duì)此并沒(méi)有做任何處理，只是依靠后期的處理將圖案與文字區(qū)分開(kāi)來(lái)，在一定程度上影響了識(shí)別的效率。

（4）在嵌入式環(huán)境中處理器處理速度比較慢，內(nèi)存資源有限，現(xiàn)有的這些算法處理起來(lái)需要較長(zhǎng)的時(shí)間且空間需求也不能得到很好的滿足[12]。

3 算法設(shè)計(jì)

針對(duì)上述問(wèn)題，本文提出了一種適用于嵌入式環(huán)境，專(zhuān)門(mén)針對(duì)商務(wù)名片圖像的快速二值化算法。在絕大多數(shù)的商務(wù)名片中，圖案或者紋理僅僅是起到裝飾作用，通常都是彩色設(shè)計(jì)，而文字通常都是深黑色。采集到的原始圖像一般都采用RGB 顏色模型，對(duì)于一幅M×N的圖像，那么在x行y列處像素點(diǎn)的RGB 顏色分量 則 分 別 用R(x，y)、G(x，y)、B(x，y) 來(lái) 表 示，均 值 為μ(x，y)，方差為δ2(x，y)。定義

其中，

O2(x，y)=(R(x，y)-G(x，y))2

P2(x，y)=(R(x，y)-B(x，y))2

Q2(x，y)=(G(x，y)-B(x，y))2

由此可以得到圖像的均值矩陣與方差矩陣。圖像的二值化過(guò)程類(lèi)似數(shù)據(jù)按近似屬性聚類(lèi)，即模式識(shí)別中的兩類(lèi)問(wèn)題。本文的算法思想即是利用一種改進(jìn)的誤差平方和函數(shù)對(duì)圖像的均值陣列與方差陣列分別進(jìn)行聚類(lèi)，找到最佳分類(lèi)閾值。對(duì)方差陣列的聚類(lèi)有助于去除圖像中的彩色圖案紋理信息，而對(duì)均值陣列的聚類(lèi)則可以將文字信息突顯出來(lái)。

3.1 算法描述

假設(shè)在一組M×N的數(shù)據(jù)集中，數(shù)據(jù)的取值范圍是{0，1，…，L-1}L個(gè)等級(jí)。那么二值化問(wèn)題就可以看做是一個(gè)兩類(lèi)問(wèn)題，即找到一個(gè)最佳閾值T，該閾值將所有數(shù)據(jù)分為ω1與ω2兩類(lèi)，兩類(lèi)的重心分別為u1和u2。那么分類(lèi)的結(jié)果應(yīng)該使得每一個(gè)類(lèi)別內(nèi)的數(shù)據(jù)與該類(lèi)的重心偏差最小，即使得

達(dá)到最小。由此，可以設(shè)定一個(gè)目標(biāo)函數(shù)：

該目標(biāo)函數(shù)h(u1，u2)為帶權(quán)的誤差平方和函數(shù)。其中nj表示取值為j的數(shù)據(jù)的出現(xiàn)頻率，即權(quán)重因子，那么類(lèi)的重心為：

最終的分類(lèi)，應(yīng)該讓目標(biāo)函數(shù)式（4）達(dá)到最小。為了使目標(biāo)函數(shù)h(u1，u2)最小，進(jìn)行以下推導(dǎo)。

假設(shè)一個(gè)數(shù)據(jù)等級(jí)k當(dāng)前在ω1類(lèi)中，它在整個(gè)M×N的數(shù)據(jù)集中出現(xiàn)的頻率為nk，現(xiàn)在若將它歸入到ω2類(lèi)中，則ω2的重心u2變?yōu)閡2＇：

同時(shí)h2變?yōu)閡2＇：

由此當(dāng)d1≠nk時(shí)，通過(guò)類(lèi)似推導(dǎo)，可以得到u1和h1變化以后的公式：

由此可以看出，若將k從ω1類(lèi)中移除，而將其歸入到ω2類(lèi)中，應(yīng)該要使得目標(biāo)函數(shù)減小，那么條件就是：

從上面的分析和推導(dǎo)過(guò)程，可以得到一個(gè)迭代算法。

3.2 算法實(shí)現(xiàn)

（3）若Q1>Q2，則將k從ω1中取出，歸入ω2，同時(shí)更新兩類(lèi)的重心，并置標(biāo)志量flag=1；否則，保持k的類(lèi)別不變，遍歷下一數(shù)據(jù)等級(jí)。

（4）遍歷完所有L個(gè)數(shù)據(jù)等級(jí)后，觀察標(biāo)志量flag的取值，若flag 為0，表示當(dāng)前分類(lèi)即是最佳分類(lèi)，分類(lèi)過(guò)程結(jié)束；若flag=1，表示當(dāng)前還未達(dá)到最佳分類(lèi)效果，繼續(xù)新一輪的遍歷，將flag 重新歸0。

這個(gè)算法的目的就是使目標(biāo)函數(shù)不斷地減小，迭代過(guò)程一直重復(fù)，直到兩類(lèi)的重心不再變化為止。算法的時(shí)間復(fù)雜度為O(S×L)，其中S為遍歷所有數(shù)據(jù)等級(jí)的次數(shù)。通過(guò)對(duì)大量的實(shí)際商務(wù)名片圖像做實(shí)驗(yàn)的結(jié)果證明，通常遍歷的次數(shù)S＜8。因此，在實(shí)際的使用中，本文算法的時(shí)間復(fù)雜度要遠(yuǎn)低于最大類(lèi)間方差法和最大熵法。

對(duì)于原始采集到的彩色商務(wù)名片圖像，首先根據(jù)式（1）和式（2）計(jì)算其均值陣列與方差陣列。然后將這兩個(gè)數(shù)據(jù)陣列按照上述的迭代算法分別進(jìn)行聚類(lèi)，從而得到T1與T2兩個(gè)最佳閾值。假設(shè)T1為均值陣列的分類(lèi)閾值，T2為方差陣列的分類(lèi)閾值。那么二值化處理的過(guò)程為：

（1）在均值陣列中所有小于T1的像素點(diǎn)即為背景點(diǎn)，置為0；其余的像素點(diǎn)在方差陣列中再與T2來(lái)進(jìn)行比較。

（2）大于T2的像素點(diǎn)，說(shuō)明是彩色的，直接將其置為0，其余的置1，說(shuō)明是表示文字的像素點(diǎn)。

3.3 與最大類(lèi)間方差算法比較

最大類(lèi)間方差法是采用窮舉法尋找閾值對(duì)數(shù)據(jù)進(jìn)行分類(lèi)，該閾值的分類(lèi)效果是使得兩類(lèi)間的方差達(dá)到最大。因此，理論上，最大類(lèi)間方差法尋找的是最佳閾值。假設(shè)在一組M×N的數(shù)據(jù)集中，數(shù)據(jù)的取值范圍是{0，1，…，L-1}L個(gè)等級(jí)，nj表示取值為j的數(shù)據(jù)在整個(gè)數(shù)據(jù)集中出現(xiàn)的頻率。若閾值T將所有數(shù)據(jù)分為ω1={0，1，…，T}和ω2={T+1，T+2，…，L-1}兩類(lèi)，用δ2ω(T)、δ2B(T)和δ2T分別表示此時(shí)的類(lèi)內(nèi)方差、類(lèi)間方差和數(shù)據(jù)總方差，那么使得δ2B(T)達(dá)到最大值的T即為最佳閾值。定義：

其中

則最優(yōu)閾值T可以由下面式子得到：

下面證明本文的算法與最大類(lèi)間方差法在理論上的等效性，也就是當(dāng)閾值T使得式（4）達(dá)到最小時(shí)，同時(shí)會(huì)使得式（19）達(dá)到最大。

通過(guò)比較式（16）與式（5），可以發(fā)現(xiàn)式（20）中的μi與式（5）中的ui是等價(jià)的(i=1，2)。因此由式（4）和式（20），得到

上式表明，當(dāng)選定了最佳閾值T可以使得h(u1，u2)達(dá)到最小，這個(gè)閾值同樣可以使得兩類(lèi)間的方差達(dá)到最大，得到最優(yōu)的分類(lèi)效果。雖然最大類(lèi)間方差法提出的二值化方法來(lái)自統(tǒng)計(jì)學(xué)的觀點(diǎn)，而本文的方法是基于數(shù)據(jù)聚類(lèi)，實(shí)際證明它們理論上是等效的。是對(duì)圖像二值化問(wèn)題的新的數(shù)學(xué)描述，實(shí)現(xiàn)了一個(gè)新的更有效的算法，該算法在時(shí)間復(fù)雜度上比最大類(lèi)間方差法有了顯著的提升。

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

實(shí)驗(yàn)中，搭建了android 應(yīng)用開(kāi)發(fā)的實(shí)驗(yàn)環(huán)境。實(shí)驗(yàn)選取WindowsXP、奔騰雙核處理器，測(cè)試所用嵌入式設(shè)備為小米手機(jī)1S。實(shí)驗(yàn)是對(duì)200 張名片圖像進(jìn)行二值化處理，分別采用最大類(lèi)間方差法、最大熵法以及本文的算法，以下是三組實(shí)驗(yàn)效果圖。

圖1 實(shí)驗(yàn)結(jié)果一

圖2 實(shí)驗(yàn)結(jié)果二

圖3 實(shí)驗(yàn)結(jié)果三

由實(shí)驗(yàn)結(jié)果可以看出，利用本文的算法，不僅在處理時(shí)間上有顯著改善，而且還有效地去除了名片中的彩色圖案紋理信息。在二值化的基礎(chǔ)上，繼續(xù)做了版面分割[13-15]。由于本文算法可以最大限度地去除原始圖像中的彩色干擾信息，因此其后續(xù)的版面分割與文字的識(shí)別更加準(zhǔn)確而容易。

表1 是將本文算法與現(xiàn)有算法做比較的結(jié)果。其中的適應(yīng)性，一方面是指算法的運(yùn)行環(huán)境，即算法在PC機(jī)或者嵌入式環(huán)境下運(yùn)行的時(shí)間效率；另一方面是指算法的穩(wěn)定性，即在拍攝名片圖像時(shí)光照不均或者名片本身包含復(fù)雜圖案紋理，在這些情況下算法是否依然能給出好的處理效果——去除干擾，突出有用信息。這一點(diǎn)尤其對(duì)后續(xù)版面的分割影響重大。若是不能將無(wú)用的圖案或者紋理信息處理好，會(huì)對(duì)版面分割造成極大的干擾，以至于分割出的版面包含文字與紋理圖案雙重信息，導(dǎo)致后續(xù)的字符分割的困難。正確的版面分割，應(yīng)該是相對(duì)獨(dú)立的功能塊的正確分割，利用本文的二值化算法處理名片圖像后，版面分割的正確率相對(duì)較高，如表2 所示。表2 是利用目前已有的名片識(shí)別系統(tǒng)做版面分割的實(shí)驗(yàn)比較。

表1 三種算法的時(shí)間和效果比較

表2 版面分割效果比較

5 結(jié)束語(yǔ)

本文對(duì)常用的幾種二值化處理算法進(jìn)行深入分析，并提出了一個(gè)非常有效的專(zhuān)門(mén)針對(duì)商務(wù)名片圖像的二值化方法，該方法處理時(shí)間快，處理效果好。相比于傳統(tǒng)的圖像二值化方法，本文算法處理的名片圖像能夠完全保留有用的信息，去掉無(wú)用的或無(wú)關(guān)緊要的信息，為名片識(shí)別的后續(xù)處理奠定良好的基礎(chǔ)，尤其適用于嵌入式環(huán)境下的快速名片識(shí)別。通過(guò)對(duì)比實(shí)驗(yàn)，該方法可以明顯提高最終結(jié)果的正確率。由于OCR 部分的識(shí)別率對(duì)信息分類(lèi)和最終識(shí)別結(jié)果的影響仍然存在，因此，如何減少OCR 識(shí)別對(duì)信息分類(lèi)和最終結(jié)果的影響是后續(xù)研究的問(wèn)題。

[1] Sankur B，Sezgin M.A survey over image thresholding techniques and quantitative performance evaluation[J].Journal of Electronic Imaging，2004，13（1）：146-165.

[2] Trier O D，Jain A K.Goal-directed evaluation of binarization methods[J].IEEE Trans Pattern Anal Machine Intell，1995，17：1191-1201.

[3] Otsu N A.Threshold selection method from grey-level histograms[J].IEEE Trans on Syst Man Cybern，1979，8（2）：62-66.

[4] Trier O D，Taxt T.Evaluation of binarization methods for document images[J].IEEE Trans on Pattern Anal Machine Intell，1995，17（2）：312-315.

[5] Su Bolan，Lu Shijian，Tan Chew Lim.Binarization of historical document images using the local maximum and minimum[C]//Proceeding DAS’10 Proceedings of the 9th IAPR International Workshop on Document Analysis Systems.ACM，2010：159-166.

[6] Packer T L，Lutes J F，Stewart A P，et al.Extracting person names from diverse and noisy OCR text[J].Proceeding AND’10 Proceedings of the Fourth Workshop on Analytics for Noisy Unstructured Text Data.ACM，2010：19-26.

[7] Parist R.Car plate recognition by neural networks and image processing[C]//IEEE International Symposium on Circuits and Systems，2000，5（10）：98-106.

[8] Zhu Haoyue，Geng Guohua，Zhou Mingquan.Research for binaryzation in license plate recognition technology[J].Computer Applications and Software，2007，1（2）：56-70.

[9] Zhu Yuanping.Augment document image binarization by learning[C]//19th International Conference on Pattern Recognition，2008：1-4.

[10] Bawa R K，Sethi G K.A review on binarization algorithms for camera based natural scene images[C]//Proceeding ICACCI’12 Proceedings of the International Conference on Advances in Computing，Communications and Informatics.ACM，2012：873-878.

[11] Patvardhan C，Verma A K，Lakshmi C V.Document image binarization using wavelets for OCR applications[C]//Proceeding ICVGIP’12 Proceedings of the Eighth Indian Conference on Computer Vision，Graphics and Image Processing.ACM，2012.

[12] Gatos B，Pratikakis I，Perantonis S J.Improved document image binarization by using a combination of multiple binarization techniques and adapted edge information[C]//19th International Conference on Pattern Recognition，2008：1-4.

[13] 徐銳義，吳煒，何小海，楊玉科.中文商務(wù)名片版面分割研究[J].四川大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，45（2）：331-335.

[14] 支東霖.名片OCR 識(shí)別知識(shí)后處理[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2003.

[15] 楊志華，齊東旭，楊力華.基于經(jīng)驗(yàn)?zāi)Ｊ椒纸獾臐h字字體識(shí)別方法研究[J].軟件學(xué)報(bào)，2005，16（8）：1438-1444.