劉穎，哈力木拉提·買買提

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

基于HMM的聯(lián)機(jī)維吾爾文整詞識(shí)別方法研究

劉穎，哈力木拉提·買買提

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

提出一種維吾爾文手寫(xiě)整詞識(shí)別方法，通過(guò)拼接單詞中各連體段的特征構(gòu)建單詞的特征向量，用K-means聚類算法對(duì)連體段進(jìn)行聚類操作降低單詞特征向量的維度并輸出離散的數(shù)字序列，通過(guò)隱馬爾科夫模型完成單詞的建模和識(shí)別。

維吾爾文整詞；隱馬爾科夫模型；特征降維；聯(lián)機(jī)

0 引言

隱馬爾科夫模型是一種對(duì)時(shí)序變化信號(hào)進(jìn)行處理的概率模型，它的成功應(yīng)用在于它對(duì)時(shí)間序列具有較強(qiáng)的建模能力[1]，并被廣泛應(yīng)用于模式識(shí)別領(lǐng)域，例如：語(yǔ)音識(shí)別、字符識(shí)別、人臉識(shí)別等領(lǐng)域。由于維吾爾文聯(lián)機(jī)手寫(xiě)單詞，具有時(shí)序性，與語(yǔ)音識(shí)別中的語(yǔ)言信號(hào)有一定的相似性，所以將HMM模型應(yīng)用到維吾爾文聯(lián)機(jī)手寫(xiě)識(shí)別中是合理的。

維吾爾文是屬于阿爾泰語(yǔ)系突厥語(yǔ)族，借用了阿拉伯文和部分波斯文字符，目前已有大量針對(duì)阿拉伯文手寫(xiě)體識(shí)別的研究[2][3]，Maqqor[4]提出了基于HTK的脫機(jī)手寫(xiě)字符識(shí)別系統(tǒng)，考慮了阿拉伯文的腳本特點(diǎn)和草書(shū)傾向，提高了字符識(shí)別效率。Hamdani[5]提出了基于RWTH的針對(duì)大量連續(xù)詞匯的阿拉伯文手寫(xiě)識(shí)別系統(tǒng)，該系統(tǒng)使用人工神經(jīng)網(wǎng)（ANN）和隱馬爾可夫模（HMM）作為識(shí)別器，在阿拉伯文手寫(xiě)識(shí)別比賽中獲得了較高的名次。

維吾爾文字識(shí)別包括印刷體識(shí)別和聯(lián)機(jī)手寫(xiě)體識(shí)別[6-8]。其中，文獻(xiàn)[6]中，將維吾爾文字符分成了主筆劃和附加筆劃兩部分，分別進(jìn)行特征提取。文獻(xiàn)[7]中，提出了基于支持向量機(jī)的維吾爾文聯(lián)機(jī)手寫(xiě)字母識(shí)別方法，系統(tǒng)研究了樣本采集、預(yù)處理、特征提取和分類等模塊。文獻(xiàn)[8]中，提出了一種基于BP神經(jīng)網(wǎng)絡(luò)的維吾爾文字母識(shí)別方法。目前大多數(shù)的識(shí)別技術(shù)都是針對(duì)維吾爾文單個(gè)字母的。但維吾爾文通常都是以單詞為基本單位進(jìn)行書(shū)寫(xiě)，僅能識(shí)別單個(gè)字母，并不能滿足人們的應(yīng)用需求；同時(shí)，對(duì)單個(gè)字母進(jìn)行識(shí)別時(shí)，通常要涉及到字母的切分，而高精度的字符切分仍然是該領(lǐng)域的一個(gè)難題。本文，提出了一種針對(duì)連體段進(jìn)行特征提取，以維吾爾文單詞為識(shí)別基元的手寫(xiě)識(shí)別方法，該系統(tǒng)通過(guò)使用隱馬爾科夫模型對(duì)維吾爾文整詞進(jìn)行建模，達(dá)到識(shí)別維吾爾文整詞的目的，滿足了人們的基本手寫(xiě)需求，并有效地避開(kāi)了字符切分困難問(wèn)題。

1 特征提取

1.1 預(yù)處理

維吾爾文一般具有草書(shū)特點(diǎn)[9]，導(dǎo)致原始手寫(xiě)樣本中存在噪聲，會(huì)影響后續(xù)的特征提取的效率和準(zhǔn)確率，所以要先對(duì)原始樣本進(jìn)行預(yù)處理，通常包括點(diǎn)平滑、歸一化、點(diǎn)聚類[10]，拐點(diǎn)提取等操作。圖1所示，表示單詞預(yù)處理之后的效果圖。

1.2 特征提取

完成預(yù)處理操作后，接下來(lái)就是單詞特征的提取。一般特征選取原則要求穩(wěn)定性強(qiáng)、分類性能好，能高效地反映出該單詞的特點(diǎn)。本文基于聯(lián)機(jī)手寫(xiě)維吾爾文單詞的特點(diǎn)，將單詞分為了若干個(gè)連體段，分別提取每個(gè)連體段的特征。

圖1 單詞預(yù)處理效果圖

圖2 單詞分為三個(gè)連體段

本文中分別選取方向碼特征、環(huán)路特征、向量角度特征、附加筆畫(huà)特征和穿越特征作為連體段的特征，用于后續(xù)單詞特征向量的構(gòu)建。其具體描述如下：

（1）方向碼特征：方向碼特征是對(duì)筆劃方向進(jìn)行編碼，來(lái)確定筆劃走向的。本文中按維吾爾文的書(shū)寫(xiě)特點(diǎn)，將360度的坐標(biāo)平面平均分成8個(gè)方向（0，45，90，135，180，225，270，315），分別對(duì)應(yīng)編碼 0~7，計(jì)算主筆劃中相鄰骨架點(diǎn)組成的向量與X軸的夾角，夾角落在哪個(gè)區(qū)域，則特征值就取該區(qū)域的編碼。

（2）環(huán)路：統(tǒng)計(jì)主筆劃中環(huán)路的個(gè)數(shù)

（3）向量角度特征：先連接連體段中相鄰的點(diǎn)，然后計(jì)算相鄰向量之間的夾角，作為一種局部角特征。例如 pi-1，pi，pi+1為點(diǎn)集中相鄰的三個(gè)點(diǎn)，則表示向量之間的夾角，作為一個(gè)局部角特征。

（4）附加筆劃特征：先通過(guò)水平投影的方法計(jì)算基線位置，再判斷附加筆劃相對(duì)于基線的位置，即基線上方還是下方。

（5）穿越特征：針對(duì)于單個(gè)連體段，找出它的質(zhì)心，在質(zhì)心的y坐標(biāo)，水平畫(huà)直線，統(tǒng)計(jì)該水平線與連體段的相交次數(shù)，同理，在質(zhì)心的x坐標(biāo)，垂直畫(huà)線，統(tǒng)計(jì)垂直線與連體段的相交次數(shù)。

2 訓(xùn)練

2.1 特征降維

采用第1節(jié)中的方法，對(duì)單詞中的各連體段完成特征提取后，通過(guò)拼接這些連體段的特征就可以形成單詞的特征向量。例如，單詞的特征向量如圖3所示：

圖3 單詞的特征

由于原始的單詞特征向量維數(shù)太高，不利于后續(xù)的訓(xùn)練識(shí)別，并且特征向量的數(shù)值都是連續(xù)的，需要先對(duì)特征向量進(jìn)行離散化。

本文將采用K-means聚類算法對(duì)單詞特征向量進(jìn)行降維。具體方法如下：

（1）提取所有連體段的特征，構(gòu)建連體段的特征庫(kù)

（2）使用K-means算法，對(duì)所有連體段進(jìn)行聚類操作，將生成的類中心保存在一個(gè)碼本中。為碼本中的每個(gè)類中心指定一個(gè)數(shù)字編號(hào)。聚類的目的主要是為了將相同的連體段聚到同一個(gè)類中。

（3）判斷單詞中每個(gè)連體段屬于碼本中的哪個(gè)類，用該類中心的數(shù)字編號(hào)表示該連體段。

聚類時(shí)使用連體段間的歐式距離作為距離度量準(zhǔn)則。計(jì)算兩個(gè)連體段之間的距離時(shí)，先分別計(jì)算各特征（附加筆畫(huà)特征、環(huán)數(shù)特征、八方向特征、局部角度特征等）之間的距離，不足的位補(bǔ)零，然后將各特征之間的距離相加作為連體段之間的距離。

將單詞特征向量轉(zhuǎn)化為離散數(shù)字序列的具體過(guò)程如圖4所示：

圖4 特征向量的降維流程

2.2 HMM的實(shí)現(xiàn)

通過(guò)上一小節(jié)中介紹的特征降維方法將單詞特征向量轉(zhuǎn)化為離散觀察值序列后，接下來(lái)就可以用HMM中的Baum-Welch算法訓(xùn)練這些觀察值序列的單詞模型。

在利用HMM解決實(shí)際問(wèn)題時(shí)，首先需要確定模型的結(jié)構(gòu)以及狀態(tài)數(shù)，常用的結(jié)構(gòu)類型為左右模型，而狀態(tài)數(shù)的確定要根據(jù)實(shí)際情況進(jìn)行設(shè)定。

本文將采用左右結(jié)構(gòu)的隱馬爾科夫模型，因?yàn)檫@種拓?fù)浣Y(jié)構(gòu)已經(jīng)在語(yǔ)音識(shí)別中取得了成功的應(yīng)用[11]。

設(shè)置狀態(tài)概率轉(zhuǎn)移矩陣的初始值為，前N-1行，aij=0.5，if j=i||j=i+1；第 N 行，ann=1。 π1=1;πi=0 for i>1。通過(guò)多次實(shí)驗(yàn)結(jié)果，本文中將狀態(tài)個(gè)數(shù)N設(shè)置為20。觀察符號(hào)個(gè)數(shù)M由聚類后生成的簇的個(gè)數(shù)確定[12]，本文中設(shè)置為50。

圖5 左右HMM的結(jié)構(gòu)圖

3 識(shí)別框架

圖6 手寫(xiě)單詞識(shí)別系統(tǒng)結(jié)構(gòu)圖

本文中我們一共收集了70個(gè)人的手寫(xiě)樣本，每個(gè)手寫(xiě)樣本中包含58個(gè)維吾爾文單詞，這些單詞包括全部的字母及其所有的形式。其中，隨機(jī)抽取50個(gè)人的手寫(xiě)樣本作為訓(xùn)練集，剩余20個(gè)人的手寫(xiě)樣本作為測(cè)試集。具體手寫(xiě)識(shí)別系統(tǒng)結(jié)構(gòu)如圖六所示。單詞識(shí)別使用的是HMM中Viterbi解碼算法，具體迭代過(guò)程如下：

（1）初始化

（2）遞歸

其中，argmax運(yùn)算符表示使括號(hào)中表達(dá)式的值最大的索引j。

（3）終止，1≤i≤N，2≤t≤T

（4）回溯查找路徑，T-1≥t≥1

最終實(shí)驗(yàn)結(jié)果如表1所示：

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

從表1實(shí)驗(yàn)數(shù)據(jù)可知，本系統(tǒng)最高識(shí)別率達(dá)到75.43%，最低69.38%?？偨Y(jié)分析發(fā)現(xiàn)主要有以下幾個(gè)因素造成系統(tǒng)識(shí)別錯(cuò)誤：a.主筆劃識(shí)別錯(cuò)誤，誤將主筆劃識(shí)別為了附加筆畫(huà)，如圖7所示；b.手寫(xiě)過(guò)程中的斷筆問(wèn)題，將一個(gè)連體段分成了多筆書(shū)寫(xiě)。c.使用K-means聚類算法時(shí)，k值的選取也會(huì)影響最終單詞的識(shí)別率。

圖7 將主筆劃識(shí)別為了附加筆畫(huà)

4 結(jié)語(yǔ)

本文提出了一種基于HMM模型的維吾爾文整詞識(shí)別研究方法。該方法的主要特點(diǎn)是以連體段為特征提取單位，將單詞特征向量表示為各連體段特征的組合，再采用K-means算法對(duì)單詞特征向量進(jìn)行降維操作，生成離散的數(shù)字序列，接下來(lái)用HMM模型進(jìn)行單詞訓(xùn)練和識(shí)別，最終達(dá)到對(duì)維吾爾文整詞進(jìn)行識(shí)別的目的。后續(xù)的工作可以進(jìn)一步改善附加筆劃的識(shí)別方法，可以嘗試不同的聚類算法，提高聚類純度，以提高單詞的識(shí)別率。

[1]Bengio Y.Markovian Models for Sequential Data.Neural Computing Surveys,1999,2:129-162.

[2]Ahmed H，Azeem S A.Online Arabic Handwriting Recognition System based on HMM[C].Proc of the 2011 International Conf on Document Analysis and Recognition，2011：1324-1328.

[3]Kherallah M，Tagougui N，Alimi A M.Online Arabic Handwriting Recognition Competition[C].International Conference on Document Analysis and Recognition，2011：1454-1458.

[4]Maqqor A,Halli A,Satori K,Et Al.Using HMM Toolkit（HTK）For Recognition of Arabic Manuscripts Characters[C].International Conference on Multimedia Computing And Systems，2014:475-479.

[5]Hamdani M,Doetsch P,Kozielski M,Et Al.The RWTH Large Vocabulary Arabic Handwriting Recognition System[C].Brazilian Symposium on Software Engineering.IEEE Computer Society,2014:111-115.

[6]袁保社，吾守爾·斯拉木.一種手寫(xiě)維吾爾文字母識(shí)別算法[J].計(jì)算機(jī)工程，2010，36（2）：186-188.

[7]木塔力甫·沙塔爾，李春庚，艾斯卡爾·艾木都拉，等.基于可訓(xùn)練機(jī)制的聯(lián)機(jī)維吾爾手寫(xiě)字母識(shí)別技術(shù)研究[J].計(jì)算機(jī)應(yīng)用與軟件，2011，28（9）：41-44.

[8]任宏宇.基于BP神經(jīng)網(wǎng)絡(luò)的聯(lián)機(jī)手寫(xiě)維吾爾字符識(shí)別[D].新疆大學(xué)碩士學(xué)位論文，2011.

[9]哈力木拉提，阿孜古麗.多字體印刷維吾爾文字符識(shí)別系統(tǒng)的研究與開(kāi)發(fā)[J].計(jì)算機(jī)學(xué)報(bào):2004,27:1480-1484.

[10]阿力木江·亞森，哈力木拉提.維吾爾文聯(lián)機(jī)手寫(xiě)識(shí)別的預(yù)處理和特征提取[J].新疆大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，27（2）：232-241.

[11]Rabiner L R.A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition[J].Proceedings of the IEEE，1989，77（2）：257-286.

[12]Hassin A H，TANG Xiang-long，LIU Jia-feng.Printed Arabic Character Recognition Using HMM[J].J Comput Sci&Technol，2004，19（4）：538-543.

作者簡(jiǎn)介:

劉穎（1991-），男，碩士研究生，研究方向?yàn)槟Ｊ阶R(shí)別、新疆少數(shù)民族信息處理技術(shù)

哈力木拉提·買買提（1959-），男，教授，研究方向?yàn)槟Ｊ阶R(shí)別、新疆少數(shù)民族信息處理技術(shù)

Research on Online Uighur Whole Word Recognition Method Based on HMM

LIU Ying，Halmurat·MAMAT
（College of Information Science and Technology，Xinjiang University，Urumqi 830046）

Illustrates a recognition method to Uyghur whole word,constructs the word feature vector by splicing feature of each segment in words,then reduces the dimension of the feature vector and output word discrete sequence of numbers by K-means algorithm,completes the modeling and identification of words by using hidden Markov model.

2017-04-06

2017-06-10

1007-1423（2017）17-0050-05

10.3969/j.issn.1007-1423.2017.17.010

Uighur Whole Word;Hidden Markoff Model;Feature Reduction;Online