阿依薩代提·阿卜力孜，加合買提·司馬義，卡米力·木依丁，艾斯卡爾·艾木都拉AYSADET·Abliz,HOJAHMAT·Ismayil,KAMIL·Muyidin,ASKAR·Hamdulla

新疆大學(xué) 信息科學(xué)與工程學(xué)院，烏魯木齊 830046

Institute of Information Science and Engineering,Xinjiang University,Urumqi 830046,China

1 引言

文本行中的單詞切分，是文本圖像中比較重要的一步。它為后續(xù)的單詞識別、字符切分和識別等技術(shù)奠定了基礎(chǔ)。正確的切分才會有正確的識別，切分不當(dāng)帶來的識別錯誤是不容忽略的問題。文本行圖像中單詞的切分，在關(guān)鍵詞搜索，單詞為整體的文字識別等領(lǐng)域中占重要的地位。國內(nèi)現(xiàn)在對印刷維吾爾文本圖像中單詞或連體段的研究比較多，相對脫機手寫維吾爾文本圖像的研究較少。對于印刷維吾爾文本圖像中單詞，連體段切分，靳簡明[1]用連通體分析的方法，即文本行中的文字進行連通體標(biāo)注，把其分三類，再用距離信息對主題部分和附加部分歸并的方法切分出印刷體維吾爾文中的連體段；萬金娥[2]印刷體維吾爾文文本行中的單詞和連體段的切分階段，利用印刷體維吾爾文中單詞內(nèi)空白間隙比單詞間空白間隙小得多且有規(guī)律的特點，通過文本行垂直投影得到的結(jié)果確定閾值來把文本行中的單詞和連體段都切分開；李亞男[3]用連通域搜索的方法來實現(xiàn)對印刷維吾爾文中連體段切分問題，該方法充分利用了字符的連通性，較好地解決了相鄰連體段在水平方向覆蓋的問題；朱蘭[4]針對每一行內(nèi)相鄰的連體段之間存在重疊的現(xiàn)象提出了一種基于改進的滴水算法的切分方法。該方法首先判斷兩個連體段之間的關(guān)系，若存在空白間隙，則選擇空白間隙的左右端作為切分點；若存在重疊現(xiàn)象，則選擇基線空白間隙的中點作為切分點，然后根據(jù)滴落規(guī)則對兩個連體段進行切分，得到了較好的切分結(jié)果；姑麗祖熱[5]針對于印刷體維吾爾文中單詞內(nèi)的字符之間存在重疊而沒有正確切分連體段的問題提出了基于跑長碼的連通段標(biāo)記法，該方法解決了垂直投影法中字符之間存在重疊而帶來的切分錯誤情況。對于脫機手寫維吾爾文本圖像行切分易曉芳等[6-7]提出了基于連通域特征的維吾爾手寫文本行分割和基于分段式前景涂抹和背景細化的文本行分割；艾斯卡爾·艾木都拉等[8]提出了基于著色處理的維吾爾文手寫文本行分割。

脫機手寫維吾爾文由于手寫的隨意性和文本圖像中字符的唯一性，給單詞切分帶來了比較大的困難。根據(jù)維吾爾文的書寫特征，在書寫時單詞和單詞之間有一定的空白間距，一個單詞內(nèi)連體段之間也是有一定的空白間距，而且單詞之間的距離比單詞內(nèi)的距離大。但是在手寫中這種特征根據(jù)書寫者的寫作習(xí)慣，在不規(guī)律的發(fā)生變化。簡單的投影，確定一個閾值進行單詞切分，在脫機手寫中不適用。針對這種問題，本文采用FCM融合K-means的聚類算法，結(jié)合后期合并等處理方法實現(xiàn)單詞切分。

在切分的過程中，是以大篇幅的手寫文本圖像為研究對象，對文本圖像整體處理。

2 文本行中的單詞切分

單詞切分指的是，文本行圖像中把單詞整體的切分出來[9]。對于本文，研究對象是大篇幅的脫機手寫文本圖像。對此，本文提出的算法流程圖如圖1所示，主要包含以下4個步驟：（1）對整片文本圖像進行預(yù)處理和文本行的切分；（2）對每一行應(yīng)用聚類算法；（3）對每一行中的文字區(qū)域進行合并，確定切分點；（4）對切分點內(nèi)的文字區(qū)域連通域標(biāo)注，著色處理。

2.1 預(yù)處理

本文采集了50個人的筆跡，將筆跡以300 dot/inch分辨率通過掃描儀，輸入到計算機，二值化后以bmp格式存儲到樣本庫里。

2.2 文本行切分

本文對脫機手寫的文本圖像的行切分階段使用了文獻[6]的自適應(yīng)涂抹細化算法。比起傳統(tǒng)的水平投影等行切分的算法，該算法能夠根據(jù)文字的疏密程度，對文本行定位和切分。圖2是使用該算法行切分結(jié)果。

圖1 手寫維吾爾文圖像單詞提取框架

圖2 文本圖像行切分

2.3 單詞切分

2.3.1 維吾爾文單詞的書寫特點

維吾爾文的有個書寫特點是，在書寫時單詞和單詞之間在水平方向有一定的距離。這個距離在印刷體上是有規(guī)律可尋的。但是在手寫中，由于手寫的隨意性，這個距離根據(jù)書寫者的書寫特點在不斷的變化。但是還要明確的一點是，單詞之間的距離，比起單詞內(nèi)連體段之間的距離是明顯大的。雖然手寫維吾爾文很隨意，但是每個書寫者基本上都會遵守這種基本的書寫規(guī)則。因此正是這種書寫特點，把每個單詞從文本行中切分出來的切入點。圖3表示出了這個特點。

2.3.2 文本行的投影

觀察脫機手寫維吾爾文的特點可以發(fā)現(xiàn)，文本行單詞之間存在重疊情況。垂直投影時，重疊的相鄰兩個單詞之間沒有空白間距，因此也不存在候選切分點。例如等字母出現(xiàn)的位置，由于書寫時拉長下面部位，因此在文本行圖像的下面出現(xiàn)重疊現(xiàn)象。選對于這個問題，采取了每個文本行圖像，底部1/5的白像素部分置黑的方法。通過此方法，能夠把拉長的文字區(qū)域部分變成背景區(qū)域，兩個重疊單詞之間出現(xiàn)空白間距，能夠得到候選切分點。通過這一步得到的效果如圖4所示。

圖3 手寫維吾爾文單詞的書寫特征

圖4 解決重疊現(xiàn)象

對整個文本圖像進行行切分的過程中，記錄每個行的切分點，并按照此順序，對初步處理后的每一文本行圖像進行垂直投影。垂直投影的目的是找出每個文本行圖像中文字區(qū)域之間的空白區(qū)域。通過垂直投影的結(jié)果，可以計算出每個文字區(qū)域和空白區(qū)域的長度和記錄相應(yīng)的切分點。記錄的長度作為合并步驟的依據(jù)，而記錄的切分點作為初始的切分點。圖5為對文本行進行垂直投影的結(jié)果。

2.3.3 FCM融合K-means的聚類算法

垂直投影得到的空白間距，根據(jù)以上描述的維吾爾文單詞的書寫特點，可以聚類成單詞間距離和單詞內(nèi)距離[10-11]。這個距離在印刷體中，可以通過確定一個閾值來分開。因為在印刷體維吾爾文中，單詞內(nèi)距離和單詞間距離之間有規(guī)律可尋。而在脫機手寫的文檔圖像中不可取的。因為輸入的每一張文檔圖像都有自己的書寫特點，顯然這種單詞之間的距離等特點也是根據(jù)書寫者的不同而變化的。因此適合一張文檔圖像的閾值，遇到其他種書寫風(fēng)格的文檔圖像時，可能不適用或者需要人為地進行閾值的調(diào)整。因此為了解決這個問題，提出了對垂直投影得到的空白間距進行聚類算法。聚類算法是無監(jiān)督的學(xué)習(xí)方法。每次輸入不同的圖片，根據(jù)每一行中單詞間和單詞內(nèi)的距離的情況，對空白間距進行聚類，不需要人為地設(shè)定一個閾值。本文FCM融合K-means的聚類方法應(yīng)用到單詞切分中。FCM（模糊c均值聚類）和K-means（K均值聚類）都是基于劃分的聚類算法，其中FCM是K-means算法的改進，是一種柔性的模糊劃分，而K-means是硬性的聚類算法。它們基本的思想是被劃分到同一簇對象之間的相似度大，不同簇之間的相似度小[12-13]。但是FCM算法仍然對聚類中心比較敏感，因此用文獻[14]的方法，用K-means算法得到的聚類中心來初始化FCM的聚類中心。圖6為對文本圖像中的任一的文本行圖像進行聚類之后的結(jié)果。

圖5 文本行的垂直投影

實驗過程中，用了兩次聚類算法。分別對空白間距和文字區(qū)域進行聚類。對于文字區(qū)域聚類成三類，分別為單個字符、標(biāo)點符號和一些散點作為第一類，連體段為第二類，單個的單詞為第三類。當(dāng)然通過這種分類得到的第三類不是都屬于單個的單詞。因為僅靠文字的長度得到的這種分類，只能說明對得到的文字區(qū)域需要進一步地合并，并不能說明得到的第三種分類都是單個單詞。因為維吾爾文單詞長度之間沒有規(guī)律，有些單詞很短，跟連體段的長度相當(dāng)，而有些連體段也是比較長，錯誤地分類成單個的單詞。因此在合并的過程中，再結(jié)合每個文字區(qū)域之間的空白間距來進行合并。文字區(qū)域之間的距離和每個文字區(qū)域長度，是根據(jù)書寫者的寫作習(xí)慣的不同而變化的，為了保證合并結(jié)果的正確性，有必要對每一行都進行一次聚類算法。圖7是三個不同的書寫者對同一行文字的筆跡，進行聚類后的對比圖。

圖6 聚類結(jié)果

圖7 不同書寫者書寫特點之間的對比

從這對比圖表中可以看出，初步確定切分點后，根據(jù)對空白間距的聚類得到的結(jié)果對文字單區(qū)域進行合并是很必要的。

2.3.4 文字區(qū)域之間的合并

每一行的空白間距分成單詞內(nèi)距離和單詞間距離，把這一分類結(jié)果作為判斷依據(jù)，對每一行的文字區(qū)域進行合并。

整個文本圖像是從左到右掃描的，因此該文也是從左到右對文字區(qū)域間的空白間距進行判斷。圖8中的空白間距是通過垂直投影得到的距離。合并過程中，當(dāng)?shù)谝粋€空白間距判斷為單詞內(nèi)距離時，不記錄切分點，繼續(xù)判斷第二個空白間距。若判斷為單詞間距離時，記錄為切分點。通過這種循環(huán)的方法，對手寫文本圖像每一行中的空白間距進行判斷，最后得到切分點。

圖8 合并過程

2.3.5 對切分點的著色處理

本文通過對切分點內(nèi)的文字給予不同的顏色，來表示單詞已經(jīng)被切分出的結(jié)果[15-16]。為了對文字區(qū)域著色，先對一行圖像中每一切分點之間連通域標(biāo)注，本文用的是八連通域的標(biāo)注。著色過程，是對一個切分點之間標(biāo)注好的連通域給予一樣的顏色，相鄰的兩個切分點之間給予不同的顏色。這里為了更明顯地看出切分效果，本文對相鄰的切分點給予了藍色和紅色兩種顏色交替著色，見圖9。

圖9 手寫文本圖像單詞切分結(jié)果

通過實驗發(fā)現(xiàn)，所提出的方法用在印刷體維吾爾文本圖像時，得到了很高的切分率。對于印刷體維吾爾文本圖像，對空白間距分類，用閾值的方法來解決。通過實驗統(tǒng)計，在印刷體維吾爾文本圖像中，空白間距小于5為單詞內(nèi)距離，空白間距大于5時為單詞間距離來處理。合并，著色處理部分都用脫機手寫維吾爾文本圖像的處理方法來解決。根據(jù)實驗結(jié)果可知，除了一些漢族人的姓和名切分開和一些特殊符號沒被切分出來以外其他單詞都可以完整地切分出來，圖10為切分結(jié)果。

圖10 印刷維吾爾文本圖像單詞提取結(jié)果

3 實驗結(jié)果與分析

3.1 實驗結(jié)果

本文的實驗平臺為3.4 GHz，內(nèi)存為8 GB，運行環(huán)境為MATLAB R2014b。實驗對象為50幅不同的人書寫的維吾爾脫機手寫文本圖像。其中50幅圖像共有536行和4 002個單詞。實驗過程中所使用的公式如下：

其中Pi為每i幅圖像中單詞正確切分率，為全部圖像的單詞平均正確切分率。ni為第i幅圖像中正確切分單詞數(shù)量，Ni為第i幅圖像中總單詞數(shù)量的理論值，m為做實驗的總的圖像數(shù)量，本文中m=50。實驗結(jié)果表1所示。

從表格中可以看出，單詞平均正確切分率為80.68%。根據(jù)實驗結(jié)果還能觀察到，50幅圖像中最大的正確單詞切分率達到95.74%，而最小正確單詞切分率只有51.28%。因此書寫者的寫作習(xí)慣，對單詞切分正確率帶來的影響較明顯。

通過本文的方法，解決了一個單詞切分成幾個連體段的現(xiàn)象和部分的重疊現(xiàn)象。同時實現(xiàn)了大篇幅脫機手寫文本圖像的整體處理。

表1 聚類算法單詞切分的結(jié)果

通過做對比實驗還可以發(fā)現(xiàn)，分別用FCM聚類算法和FCM和K-means融合的聚類算法得到的聚類結(jié)果是一樣。因為兩個聚類算法中，任何一種聚類算法得到的兩個聚類中心大小之間的差距比較大，因此對聚類結(jié)果的好壞不造成影響。但是FCM融合K-means的算法迭代次數(shù)明顯少于FCM聚類算法，因此聚類所耗的時間也有所減少。圖11所示，為使用兩種算法得到的，每一幅圖像平均迭代次數(shù)的對比圖。

圖11 兩種算法平均迭代次數(shù)的對比

3.2 實驗結(jié)果錯誤分析

對脫機手寫文本圖像單詞切分中出現(xiàn)的19.32%的平均錯誤率，主要是因為在書寫時的不規(guī)范帶來的。在整個算法的切分過程中，當(dāng)遇到有些字符的下面部位水平方向拖尾帶來的重疊、單詞間距離較小被錯誤地分類成單詞內(nèi)距離等情況時，把兩個單詞合并成一個單詞。有些單詞內(nèi)距離過大時，聚類過程中被誤判為單詞間距離，把一個單詞切分成兩個單詞。這些錯誤切分的情況圖12所示。

圖12 錯誤切分分析

4 結(jié)束語

對于從大篇幅脫機手寫維吾爾文本圖像中單詞切分的問題，提出了一種基于FCM融合K-means的算法。算法先對每一行進行垂直投影，把空白間距的位置確定為初始切分點。其次再對文本行圖像中，文字區(qū)域之間的空白間距進行聚類，把距離分成單詞內(nèi)距離和單詞間距離，再對單詞內(nèi)距離的位置，和其周圍的文字區(qū)域進行合并，得到最后的切分點，再對每個切分點進行著色處理得到了最終的切分結(jié)果，得到了80.68%的平均切分正確率。在脫機手寫維吾爾文本圖像中，相鄰單詞之間出現(xiàn)的重疊情況和因個人書寫習(xí)慣把相鄰單詞寫太近的現(xiàn)象，導(dǎo)致切分錯誤。

參考文獻：

[1]靳簡明，丁曉青，彭良瑞，等.印刷維吾爾文本切割[J].中文信息學(xué)報，2005（5）：76-83.

[2]萬金娥，袁保社，李曉，等.一種改進的印刷體維吾爾文投影切分方法[J]計算機工程，2013（4）：263-266.

[3]李亞男，陳興文，張丹.印刷體維文切分算法的改進——基于像素積分投影法和連通域搜索法[J].大連民族學(xué)院學(xué)報，2014（3）：315-318.

[4]朱蘭，袁保社，余偉.基于滴水算法的印刷體維吾爾文切分方法[J].計算機技術(shù)與發(fā)展，2015（7）：107-110.

[5]姑麗祖熱·吐爾遜，尤努斯·艾沙，吐爾根·依布拉音，庫爾班·吾布力.連通域結(jié)合重疊度的維吾爾文檔圖像文字切分[J].計算機工程與設(shè)計，2016（7）：1892-1897.

[6]易曉芳，卡米力·木依丁，艾斯卡爾·艾木都拉.基于連通域特征的維吾爾手寫文本行分割[J].計算機工程與應(yīng)用，2014，50（18）：142-146.

[7]易曉芳，卡米力·木依丁，艾斯卡爾·艾木都拉.基于分段式前景涂抹和背景細化的文本行分割[J].計算機工程，2013（5）：204-208.

[8]艾斯卡爾·艾木都拉，易曉芳，卡米力·木依丁.基于著色處理的維吾爾文手寫文本行分割[J].清華大學(xué)學(xué)報：自然科學(xué)版，2013（2）：259-264.

[9]Al-Dmour A，F(xiàn)raij F.Segmenting arabic handwritten documents into text lines and words[J].International Journal of Advancements in Computing Technology，2014，6（3）：109-119.

[10]Louloudis G，Stamatopoulos N，Gatos B.A novel two stage evaluation methodology for word segmentation techniques[C]//10th International Conference on Document Analysis and Recognition，Barcelona，2009：686-690.

[11]Kim S H，Jeong S，Lee G S，et al.Word segmentation in handwritten Korean text lines based on gap clustering techniques[C]//Proceedings of Sixth International Conference on Document Analysis and Recognition，Seattle，WA，2001：189-193.

[12]戈國華，肖海波，張敏.基于FCM的數(shù)據(jù)聚類分析及Matlab實現(xiàn)[J].福建電腦，2007（4）：89.

[13]王千，王成，馮振元，等.K-means聚類算法研究綜述[J].電子設(shè)計工程，2012（7）：21-24.

[14]王與，陳壽文.K-means融合FCM算法聚類研究[J].滁州學(xué)院學(xué)報，2014（5）：51-54.

[15]Ryu J，Koo H I，Cho N I.Word segmentation method for handwritten documents based on structured learning[J].IEEE Signal Processing Letters，2015，22（8）：1161-1165.

[16]Kavallieratou E.Word segmentation using Wigner-Ville distribution[C]//13th International Conference on Document Analysis and Recognition（ICDAR），Tunis，2015：701-705.