基于AP聚類的中文字符分割

鄭澤鴻， 黃成泉， 梁 毅， 冉龍才， 田文英

(貴州民族大學， 貴陽 550025)

引言

隨著智能設備及光學字符識別軟件的發展、普及，字符分割已經成為圖像分割領域中的一個熱點問題。目前研究中的字符分割對象主要是中文漢字，但由于漢字構造的特殊性，基于現有漢字分割方法的效果并不好，從而也限制了光學字符識別軟件的研制發展。因此，如何更好地分割漢字字符成為時下學界的研究重點。

對于文本圖像，傳統的分割方法有全局閾值二值法、局部閾值二值法和基于灰度等級的分割方法[1]。這些方法只適用于某些特定的情況，不適用于特殊排版、斷筆和字體大小不一等特殊情況下的字符分割。

對于二值化的文本圖像進行分割處理的研究方法主要有：基于邊緣特征的文本分割、基于區域的文本分割和基于學習的文本分割等方法[2]。其中，基于邊緣的方法是利用目標區域和背景區域的灰度存在變化的特點，把目標圖像從背景中分割出來，常用的邊緣檢測算子有Sobel算子[3]、Roberts算子[4]、Prewitt算子[5]、Laplace算子[6]和Canny算子[7]等。基于邊緣的方法實現容易，但抗干擾能力差。基于區域的方法是將圖像二值化后進行水平和垂直分割從而得到字符，該方法針對排列整齊的文本具有良好效果，但當文本排列出現變化時分割效果欠佳。基于學習的文本分割重點是采集樣本，對樣本進行訓練從而得到訓練結果，并以訓練結果為標準實現分割，因此樣本的選取直接影響分割的效果。

文本圖像包含的內容復雜、例如古籍、少數民族文字等載體并非只有一種字體、字號，而且隨著年代的變化一些載體質量差的，上面的文字變得模糊，使得文字的分割變得更加困難。因此，本文研究提出了使用聚類方法來分割文本圖像的文字，傳統的聚類方法無法直接用于大規模文字分割，必須與區域或邊緣等方法相結合。而本文運用的AP聚類方法則因為無需預先設置聚類中心點的特性，使其能夠直接運用到文本圖像的分割中。

1 傳統的中文字符分割方法

傳統的二值化分割是學界堪稱經典的字符分割方法，并且相繼研究提出了2類有效的可行方法，即全局閾值法和局部閾值法。具體來說，全局閾值方法是找到一個能適應整個圖像中所有像素的閾值，通過該閾值把像素分成前景和背景，如Otsu、Kittler、Kapur等方法。局部閾值法是通過計算每個像素點的鄰域在每個灰度值相同的區域取一個閾值，如Trier、Niblack、Bersen等方法。

1.1 Otsu方法

Otsu法是一種自適應的閾值確定方法，又叫最大類間方差法。該算法按圖像的灰度特性，將圖像分成背景和目標兩個部分。背景和目標之間的類間方差越大，則說明構成圖像的2個部分的差別越大，當部分目標錯分為背景或部分背景錯分為目標都會導致兩個部分差別變小。因此，使類間方差最大的分割則表征著錯分概率最小。

設圖像I(x,y)，目標和背景的分割閾值記為T，屬于目標的像素點數占整幅圖像的比值記為α1，其平均灰度為μ1；背景像素點數占整幅圖像的比例為α2，其平均灰度為μ2。圖像的總平均灰度記為μ，類間方差記為σ。

當圖像的大小為M×N時，將圖像中像素的灰度值小于閾值T的像素個數記作θ1，像素灰度大于閾值T的像素個數記作θ2，則有：

(1)

(2)

θ1+θ2=M×N

(3)

α1+α2=1

(4)

μ=α1*μ1+α2*μ2

(5)

σ=α1(μ1-μ)2+α2(μ2-μ)2

(6)

將式(5)代入式(6)，得到等價公式：

σ=α1α2(μ1-μ2)2

(7)

遍歷圖像得到使類間方差最大的閾值T，即為所求。

1.2 Bersen算法

Bernsen算法[8]的核心是根據每個像素點所在局部窗口中像素的最大值和最小值來獲取該像素的閾值。假設在局部窗口內，像素的灰度值的最大值為max(i,j)，最小值為min(i,j)，根據下式可求得該窗口的局部閾值T：

(8)

按照順序掃描文本圖像中的每個像素點，使用式(8)獲得該點的閾值，然后對該點進行二值化處理。

2 基于AP聚類的中文字符分割方法

采用區域或邊緣的方法并不能精準分割特殊排版、斷字等情況下的文本圖像。而且傳統的聚類方法還要預先設置聚類中心點，這在處理大量文本時并不適用。因此，本文設計選用了AP聚類分割文本圖像。

AP(Affinity Propagation)算法[9]、即為近鄰傳播算法或者親和力傳播算法，是在2007年由Frey等提出的一種新的聚類算法。AP算法的基本思想是將全部樣本點都當作潛在的聚類中心(稱之為exemplar)，并將樣本點兩兩之間連線構成一個網絡(相似度矩陣S)，再通過網絡中各條線的消息Responsibility(吸引度，R)和Availability(歸屬度，A)[10]傳遞計算出各樣本的聚類中心。

從AP聚類的設計思想分析得知，相似度矩陣、吸引度和歸屬度是AP聚類的重要研究內容，因此本文將對其著重展開如下研究分析。

2.1 構造相似度矩陣S

AP算法是一種根據樣本對象之間的相似度自動實現聚類的方法。本文選擇負歐式距離作為樣本對象之間相似度的衡量準則，這些相似度組成N*N(N為數據對象的數目)的相似矩陣S[11]，利用該矩陣進行自動迭代計算。其中，S(i,j)表示樣本點i與j之間的相似度，數學公式如下所示：

S(i,j)=-‖xi-xj‖2

其中,

S(i,j)∈(-,0]

(9)

AP算法根據相似度矩陣S中的對角線數值大小作為某個點能否成為聚類中心的評判標準，該值越大，該點成為簇中心的可能性越大。對角線上的值稱為參考度p，p的大小影響簇中心的數目。

2.2 吸引度R與歸屬度A

吸引度R(i,j)是樣本i向候選聚類中心k發出的信息，指明樣本i對聚類中心k的支持程度，其值越大，表示k越有機會成為i的類中心；歸屬度A(i,j)是候選聚類中心k向樣本i發出的信息，指明候選聚類中心k作為樣本i的中心的合適程度，其值越大，表明i越可能屬于以k為中心的類。

(1)吸引度R(i,j)迭代公式

Rt+1(i,k)=(1-λ)*Rt+1(i,k)+λ*Rt(i,k)

(10)

其中，

Rt+1(i,k)=

(11)

(2)歸屬度A(i,j)迭代公式

At+1(i,k)=(1-λ)*At+1(i,k)+λ*At(i,k)

(12)

其中，

At+1(i,k)=

(13)

由上述公式可以看出，當S(k,k)較大使得R(k,k)較大時，A(i,j)也較大，從而類代表k作為最終聚類中心的可能性較大；同樣，當越多的S(k,k)較大時，越多的類代表傾向于成為最終的聚類中心。因此，增大或減小S(k,k)可以增加或減少AP輸出的聚類數目。

式(10)和式(12)中的λ稱為阻尼系數(Damping factor)，主要是發揮收斂作用。AP算法每次迭代，吸引度Ri+1和歸屬度Ai+1要與上一次迭代的Ri和Ai進行加權更新。

2.3 基于AP聚類的中文文本圖像分割算法實現

輸入含中文文本的圖像

輸出分割得到的帶不同顏色的文本字符

Step1對按比例切割過的文本進行二值化處理；

Step2將字符像素作為特征值，并把坐標賦值給二維矩陣；

Step3構造矩陣中各像素的相似度矩陣；

Step4計算相似度矩陣中每個點的吸引度信息；

Step5更新相似度矩陣中每個點的吸引度信息，計算歸屬度信息；

Step6更新歸屬度信息，計算吸引度信息；

Step7對樣本點的吸引度信息和歸屬度信息求和(R(i,j)+A(i,j))，檢測其選擇聚類中心的決策。如果經過若干次迭代之后其聚類中心不變、或者迭代次數超過既定的次數、又或者一個子區域內的關于樣本點的決策經過數次迭代后依然保持不變，則得到最佳聚類中心數；

Step8通過得到的聚類中心對像素點進行歸類；

Step9對不同類的像素點賦值，標記為不同顏色，算法結束。

相比K-means等傳統聚類算法，基于AP的聚類算法不需要事先給定聚類中心個數，算法在迭代過程中展示數據集的內部結構，并確定合適的聚類個數，精準度非常高。

3 實驗結果

為了驗證本文所應用的AP聚類方法的可行性，選取某高校圖書館館藏古籍的掃描圖像為實驗樣本。由圖1(a)可知，該圖像具有背景模糊，字符豎直排列等特點，(b)是圖像二值化后的結果，(c)是使用AP聚類算法分割出來的結果，分割出來的每個字符用不同的顏色來標識區分。

(a)古籍樣本掃描圖像 (b)樣本二值化圖像 (c)樣本分割結果

(a)Scanning images of ancient books (b)Binary image of sample (c)Segmentation results of sample

圖1算法實現圖

Fig.1Algorithmimplementationdiagram

將該古籍掃描圖像作為實驗樣本，共分割到500多個，統計結果表明，在同種圖像質量條件下，使用AP聚類分割方法，分割正確率達到84.8%。

4 結束語

本文提出應用AP聚類算法分割圖像，利用AP聚類算法無需預先指定聚類中心的特性來確定分割的字符數，在圖像質量較差、不規則排版等復雜情況的文本圖像處理中，該方法取得了比傳統方法更好的效果，分割的正確率顯著提高。為進一步完善該方法，如何選取更有效的參考度p將是今后的研究方向。

[1] 陳艷, 孫羽菲, 張玉志. 灰度圖像中字符切分方法的研究[J]. 中文信息學報, 2004, 18(4):44-49.

[2] 吳春法, 潘亞文, 王敬. 基于K-means顏色聚類分割與邊緣檢測的文字提取[J]. 電腦知識與技術, 2017, 13(28):206-207，210.

[3] 袁春蘭, 熊宗龍, 周雪花,等. 基于Sobel算子的圖像邊緣檢測研究[J]. 激光與紅外, 2009, 39(1):85-87.

[4] 王冰. 用Roberts算子進行邊緣處理[J]. 甘肅科技, 2008, 24(10):18-20.

[5] 楊道普, 馬秋禾, 石磊. 邊緣檢測Prewitt算子的改進算法[J]. 測繪科學, 2008，33(S3):100-101.

[6] 鄭瑩, 孫燮華. 圖像邊緣檢測Laplace算子的改進[J]. 沈陽建筑大學學報(自然科學版), 2005, 21(3):268-271.

[7] 張帆, 彭中偉, 蒙水金. 基于自適應閾值的改進Canny邊緣檢測方法[J]. 計算機應用, 2012, 32(8):2296-2298.

[8] 張紅穎. 改進的Bernsen算法實證研究[J]. 電子世界, 2013(4):105.

[9] FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814):972.

[10]DUECK D, FREY B J. Non-metric affinity propagation for unsupervised image categorization[C]// 2007 International Conference on Computer Vision.Rio de Janeiro, Brazil:IEEE, 2007:1-8.

[11]VLASBLOM J, WODAK S J. Markov clustering versus affinity propagation for the partitioning of protein interaction graphs[J]. Bmc Bioinformatics, 2009, 10(1):99.