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

剛亞州，黃元元，戴 群

GANG Yazhou,HUANG Yuanyuan,DAI Qun

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

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

1 引言

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

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

2 存在的問題

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

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

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

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

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

3 算法設(shè)計

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

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

3.1 算法描述

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

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

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

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

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

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

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

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

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

3.2 算法實現(xiàn)

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

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

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

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

（1）在均值陣列中所有小于T1的像素點即為背景點，置為0；其余的像素點在方差陣列中再與T2來進行比較。

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

3.3 與最大類間方差算法比較

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

其中

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

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

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

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

4 實驗分析

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

圖1 實驗結(jié)果一

圖2 實驗結(jié)果二

圖3 實驗結(jié)果三

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

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

表1 三種算法的時間和效果比較

表2 版面分割效果比較

5 結(jié)束語

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

[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é)報：自然科學(xué)版，2008，45（2）：331-335.

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

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