閻少宏，彭亞綿，楊?lèi)?ài)民，周明陶

(河北聯(lián)合大學(xué)理學(xué)院，河北唐山063009)

近年來(lái)，隨著計(jì)算機(jī)的發(fā)展，模式識(shí)別技術(shù)不斷取得新的進(jìn)展，大大提高了人機(jī)間的交互能力。計(jì)算機(jī)文字識(shí)別是模式識(shí)別的一個(gè)重要分支，它包括數(shù)字字符識(shí)別、西方文字字符識(shí)別、東方文字字符識(shí)別等。它使?jié)h字和其他字符高速自動(dòng)輸入計(jì)算機(jī)成為可能，較好地解決了漢字等信息處理系統(tǒng)中手動(dòng)輸入效率低的問(wèn)題，對(duì)大規(guī)模數(shù)據(jù)統(tǒng)計(jì)、辦公自動(dòng)化、智能計(jì)算機(jī)、信息壓縮與傳輸?shù)阮I(lǐng)域的研究有著深刻的意義。但是，在上述問(wèn)題中，隨著數(shù)據(jù)規(guī)模的不斷擴(kuò)大，極易引發(fā)“維數(shù)災(zāi)難”，為了消除數(shù)據(jù)冗余，找到數(shù)據(jù)間的內(nèi)在聯(lián)系，將這些高維數(shù)據(jù)映射到低維空間中去，這是本文的關(guān)鍵點(diǎn)，所采用的局部線性嵌入(Locally Linear Embedding，LLE)是一種常見(jiàn)的非線性降維方法。

1 LLE算法

LLE算法是基于幾何直覺(jué)的，它把高維空間數(shù)據(jù)點(diǎn)按一定規(guī)則映射到低維嵌入空間中。主要步驟為:尋找初始數(shù)據(jù)點(diǎn)的近鄰數(shù)據(jù)點(diǎn)個(gè)數(shù)k，計(jì)算點(diǎn)的局部重建權(quán)值矩陣Wij，確定權(quán)值矩陣Wij的特征值，構(gòu)造滿足低維要求的降維數(shù)據(jù)點(diǎn)，即得到低維映射結(jié)果，算法過(guò)程如圖1所示。

圖1 LLE算法

1.1 計(jì)算數(shù)據(jù)點(diǎn)的近鄰點(diǎn)個(gè)數(shù)k

選取合理的k值是LLE算法降維成功與否的關(guān)鍵所在。本文利用輸入矩陣與輸出矩陣的耦合關(guān)系給出了一種選取最優(yōu)k值的方法，如(1)式所示。

1.2 計(jì)算權(quán)值矩陣Wij

設(shè)原始高維空間D中有N個(gè)數(shù)據(jù)點(diǎn)，記做，假設(shè)數(shù)據(jù)由光滑的多面體取樣而來(lái)，故每一數(shù)據(jù)點(diǎn)和它的鄰近點(diǎn)都可認(rèn)為位于或近似位于某多面體的局部線性平面上。這樣就能通過(guò)線性組合系數(shù)刻畫(huà)出局部平面的幾何特征。在LLE算法中，可通過(guò)度量歐氏距離或測(cè)地距離等方法找到每個(gè)數(shù)據(jù)點(diǎn)X→i的k個(gè)近鄰點(diǎn)，每個(gè)數(shù)據(jù)點(diǎn)的重構(gòu)誤差用(2)式給出的成本函數(shù)來(lái)衡量。

式中，ε(W)為成本函數(shù);Xi(i=1，2，3，…，N)為高維空間D的樣本點(diǎn);Xij(j=1，2…k)為高維空間Xi

的k個(gè)近鄰點(diǎn);Wij為Xi與Xij之間的權(quán)值，且滿足條件

1.3 計(jì)算低維向量

(3)式的目的是求損失函數(shù)。其中Yi是Xi的輸出向量，同高維空間中類(lèi)似;Yij(j=1，2，3…k)是Yi的k個(gè)近鄰點(diǎn)，并且此式也有約束條件(4)和(5)式。

式中，E是D×D的單位矩陣;低維坐標(biāo)Yi是輸出矩陣的列向量;Wi是權(quán)值矩陣W的列向量;Ei是單位矩陣E的第i列。由上述的約束條件可以看出從高維空間到低維空間映射后的輸出結(jié)果的重心應(yīng)該在坐標(biāo)原點(diǎn)上。

2 文字識(shí)別原理

原始文本用掃描儀或攝像機(jī)進(jìn)行光電轉(zhuǎn)換輸入到計(jì)算機(jī)中，經(jīng)過(guò)光電轉(zhuǎn)換的文本是一幅兩維的矩陣圖像，圖像可以是灰度的，也可以是二值的。現(xiàn)在一般都采用二值圖像，即圖像中所有象素點(diǎn)的取值非0即1，值為1的點(diǎn)稱為前景點(diǎn)或黑點(diǎn)，為0的點(diǎn)稱為背景點(diǎn)或白點(diǎn)。由于目前字符識(shí)別算法仍是以每個(gè)字符為一個(gè)識(shí)別單位，因此首先要把單個(gè)字符的圖像塊從文本圖像中分割出來(lái)，這一過(guò)程稱為行字分割。通常只要采用投影方法就能有效地解決這一問(wèn)題。

單字圖像塊分離出來(lái)后，進(jìn)入識(shí)別環(huán)節(jié)，這是整個(gè)識(shí)別系統(tǒng)的核心，包括預(yù)處理、特征提取和識(shí)別三個(gè)部分。一般情況下所說(shuō)的手寫(xiě)體字符識(shí)別通常是指單字識(shí)別。預(yù)處理的目的是去除噪聲，加強(qiáng)有用信息、壓縮冗余信息并盡可能對(duì)手寫(xiě)字符產(chǎn)生的大小、位置和形狀等方面的變化進(jìn)行吸收，為特征提取做好準(zhǔn)備。預(yù)處理后，數(shù)據(jù)的維數(shù)依然很高。特征提取的目的是將圖像信息壓縮成一組維數(shù)較低的、能夠反映原始圖像的本質(zhì)特征。一組穩(wěn)定且具有代表性的特征，是一個(gè)識(shí)別算法的核心，這里采用LLE算法對(duì)數(shù)據(jù)進(jìn)行降維，達(dá)到保留其拓?fù)浣Y(jié)構(gòu)特征的目的。

3 計(jì)算機(jī)文字識(shí)別過(guò)程

手寫(xiě)漢子識(shí)別系統(tǒng)框圖如圖2所示。

圖2 手寫(xiě)漢字識(shí)別系統(tǒng)框圖

3.1 圖像獲取

書(shū)寫(xiě)在紙張上的手寫(xiě)體文稿用數(shù)碼相機(jī)或其他攝像設(shè)備拍下成“JPG”格式的圖片，待識(shí)別。

3.2 預(yù)處理

由于脫機(jī)手寫(xiě)體漢字識(shí)別只需要處理圖像中的字形信息，對(duì)顏色等信息不做處理，所以須對(duì)掃描得到的文本圖像進(jìn)行二值化處理，以去掉不必要的信息。之后，需要進(jìn)行文字剝離操作，這主要包括域分離、行切割、字切割等過(guò)程。最后，需對(duì)圖像進(jìn)行歸一化處理，使得待識(shí)別文字大小一樣、位置一致，滿足進(jìn)一步識(shí)別的要求。

3.3 特征提取

基于字符結(jié)構(gòu)的特征提取是識(shí)別的前提，一般而言，按某種特征就對(duì)應(yīng)了某種分類(lèi)方法，有些特征用于粗分類(lèi)，有些特征用于細(xì)分類(lèi)，還有些特征可用于識(shí)別后的檢驗(yàn)。常用的字符特征有重心位置、中心位置、筆畫(huà)的方向、端點(diǎn)、岐點(diǎn)、交點(diǎn)、折點(diǎn)、特定背景點(diǎn)、每行或每列前景像素?cái)?shù)目、筆畫(huà)分布情況、筆畫(huà)的粗細(xì)和灰度、字符周?chē)P畫(huà)分布密度等。

3.4 字符分類(lèi)

字符分類(lèi)是基于特征提取的，不同的特征提取對(duì)應(yīng)了不同的分類(lèi)方法。分類(lèi)算法是識(shí)別的關(guān)鍵，其優(yōu)劣也決定了識(shí)別系統(tǒng)的好壞。一般的，分類(lèi)是分級(jí)的，也就是說(shuō)先對(duì)待識(shí)別字符進(jìn)行粗分類(lèi)，然后逐步細(xì)分類(lèi)，直到識(shí)別出該字符。

3.5 字符識(shí)別

字符簡(jiǎn)化過(guò)程即是將上述預(yù)處理后的字符矩陣進(jìn)一步細(xì)化，因?yàn)榧?xì)化后的信息量比文字二值化矩陣要少得多，降低了后面字符處理的工作量，這里利用LLE算法對(duì)其進(jìn)行簡(jiǎn)化。

識(shí)別字符首先要對(duì)標(biāo)準(zhǔn)字符進(jìn)行位置調(diào)整、尺寸調(diào)整、字符簡(jiǎn)化、特征提取等一系列預(yù)處理，再用LLE算法對(duì)文字矩陣進(jìn)行數(shù)字化處理，本文采用數(shù)學(xué)軟件Matlab進(jìn)行具體操作:

(1)導(dǎo)入圖片，應(yīng)用語(yǔ)句imread(＇*.JPG＇)，圖片導(dǎo)入后，圖片信息以數(shù)字矩陣的形式儲(chǔ)存在系統(tǒng)里。

(2)數(shù)據(jù)預(yù)處理，應(yīng)用語(yǔ)句rgb2gray，索引圖像向灰度圖像轉(zhuǎn)換。

(3)應(yīng)用LLE算法將上一步轉(zhuǎn)換后的數(shù)字矩陣做進(jìn)一步處理，方便文字?jǐn)?shù)據(jù)庫(kù)的建立和以后在文字識(shí)別中提取。

經(jīng)上述處理后所有文字都變成一個(gè)簡(jiǎn)化后的數(shù)字矩陣Y。

圖3為處理前后文字矩陣的圖形表示對(duì)比。

圖3 處理前后的文字

由圖3可見(jiàn)，由于LLE是一種降維算法，處理后圖像與原圖像維數(shù)不一致，所以處理后圖像與原圖像存在較大差距，但是處理后的圖像數(shù)據(jù)量大大減少。

4 識(shí)別后的處理

識(shí)別后的處理是依據(jù)文字所處的上下文或者其他約束條件，對(duì)識(shí)別結(jié)果的校驗(yàn)。利用字符所在上下文對(duì)識(shí)別結(jié)果進(jìn)行校正或檢驗(yàn)效果是顯然的。

5 試驗(yàn)結(jié)果

以下以單字識(shí)別相容度比較法進(jìn)行識(shí)別效果分析。這里以形似字“我”“找”“錢(qián)”對(duì)比相容度，找出數(shù)值關(guān)系，判別識(shí)別效果。試驗(yàn)以“我”為標(biāo)準(zhǔn)漢字，手寫(xiě)漢字中“我”為正確漢字，其他作為對(duì)比，以檢驗(yàn)LLE算法的效果。為了對(duì)比方便，記手寫(xiě)“我”為A，手寫(xiě)“找”為B，手寫(xiě)“錢(qián)”為C，標(biāo)準(zhǔn)字庫(kù)中的“我”為D，降維前后的文字相容度列于表1。

圖4 手寫(xiě)文字示例圖片

表1 降維前后的文字相容度表

由表1可看出，降維前后手寫(xiě)“我”與標(biāo)準(zhǔn)“我”的相容度最高。“錢(qián)”與“我”的相似度稍大于“找”。此外，LLE算法簡(jiǎn)化后文字相容度都有所降低，但整體上保持了降維前的大小順序，這說(shuō)明經(jīng)LLE算法簡(jiǎn)化后，各個(gè)字很好的保持了自身的拓?fù)潢P(guān)系，字體結(jié)構(gòu)特征得到保留，此簡(jiǎn)化算法可以應(yīng)用于手寫(xiě)文字識(shí)別。

6 結(jié)論

LLE算法在手寫(xiě)文字識(shí)別中具有很大的潛力，對(duì)文字識(shí)別率的提高起著非常關(guān)鍵的作用，若能更好的研究算法中的各種距離，低維空間維數(shù)d和近鄰點(diǎn)個(gè)數(shù)k的選取等關(guān)鍵問(wèn)題，并結(jié)合手寫(xiě)文字識(shí)別領(lǐng)域的預(yù)處理、特征提取等最新的方法，會(huì)有更大的應(yīng)用空間。

［1］ S T Roweis，L K Saul.Nonlinear Dimensionality Reduction by Locally Linear Embedding［J］.Science，2000，(290):2323 － 2326.

［2］ Kouropteva O，Okun O，Hadid A，etal.Beyond locally linear embedding algorithm.Technical ReportMVG-01-2002，Machine Vision Group，University of Oulu，F(xiàn)inland，2002.

［3］ 邊肇棋，張學(xué)工等.模式識(shí)別［M］.北京:清華大學(xué)出版社，2001.

［4］ 劉卓，高維數(shù)據(jù)分析中的降維方法研究［D］.國(guó)防科技大學(xué)，2002.

［5］ 譚璐，吳詡，易東云，穩(wěn)健局部線性嵌入方法［J］.國(guó)防科技大學(xué)學(xué)報(bào)，2004，26(6):91-95.

［6］ 鄭杰，一種非線性降維方法的研究［D］.中山大學(xué)，2005.