基于Fisher算法在手寫識別系統(tǒng)中的應(yīng)用

王堂旺，劉必旺，王寶忠

（1.江蘇科技大學(xué) 江蘇 鎮(zhèn)江212003；2.常州信息職業(yè)技術(shù)學(xué)院 江蘇 常州213164）

基于Fisher算法在手寫識別系統(tǒng)中的應(yīng)用

王堂旺1，劉必旺2，王寶忠1

（1.江蘇科技大學(xué) 江蘇 鎮(zhèn)江212003；2.常州信息職業(yè)技術(shù)學(xué)院 江蘇 常州213164）

為了實現(xiàn)智能移動設(shè)備輸入識別的需求，文中設(shè)計了一種單片機(jī)實現(xiàn)智能手寫識別系統(tǒng)。在分析Fisher線性鑒別算法的基礎(chǔ)上，以單片機(jī)為硬件載體，實現(xiàn)Fisher線性鑒別算法在手寫識別中的應(yīng)用。該系統(tǒng)的硬件部分主要使用STM32F407單片機(jī)為核心，編程實現(xiàn)Fisher線性鑒別算法，實驗過程中對不同字符進(jìn)行多次識別。實驗表明該系統(tǒng)具有操作簡單、識別率高、識別速度快等優(yōu)點，具有實際使用價值，達(dá)到設(shè)計要求。

Fisher；STM32F407；單片機(jī)；手寫識別

隨著智能手機(jī)和平板電腦等移動設(shè)備的普及，手寫識別的應(yīng)用也被越來越多的設(shè)備采用。隨著觸摸屏的廣泛使用，加之手寫識別技術(shù)的告訴發(fā)展，移動終端的輸入形式不再局限于鍵盤形式，手寫輸入也逐漸流行起來［1-2］。手寫識別，是指對在手寫設(shè)備上書寫時產(chǎn)生的有序軌跡信息進(jìn)行識別的過程。手寫識別能夠使用戶按照最自然、最方便的輸入方式進(jìn)行文字輸入，易學(xué)易用，可取代鍵盤或者鼠標(biāo)。用于手寫輸入的設(shè)備有許多種，比如電磁感應(yīng)手寫板、壓感式手寫板、觸摸屏、觸控板、超聲波筆等。手寫識別是利用某種輸入設(shè)備直接書寫文字，經(jīng)過系統(tǒng)識別處理之后，轉(zhuǎn)換為文字統(tǒng)一表示的輸入方法。在書寫字符時，觸筆在觸摸屏上的接觸點的電壓將會發(fā)生變化，通過ADC轉(zhuǎn)換器可以轉(zhuǎn)換為LCD屏的坐標(biāo)，因此手寫筆的運動軌跡被轉(zhuǎn)化為坐標(biāo)序列，從這些坐標(biāo)序列可以比較容易第抽取書寫文字的筆畫和筆順等信息，對書寫者所書寫的字符筆跡進(jìn)行識別，根據(jù)識別結(jié)果轉(zhuǎn)換成字符輸出顯示到LCD屏上［2-3］。

文中在分析Fisher線性鑒別算法的基礎(chǔ)上，以STM32單片機(jī)為硬件載體，編程實現(xiàn)Fisher線性鑒別算法，并將其應(yīng)用到手寫識別系統(tǒng)中去，能夠快速準(zhǔn)確地識別出數(shù)字以及大小寫字母。

1 系統(tǒng)結(jié)構(gòu)

1.1 系統(tǒng)硬件設(shè)計

系統(tǒng)主要采用STM32F407ZG，它是基于高性能的ARM Cortex-M4F的32位RISC內(nèi)核，工作頻率高達(dá)168 MHz的Cortex-M4F核心功能支持所有ARM單精度數(shù)據(jù)處理指令和數(shù)據(jù)類型的單精度浮點單元（FPU）。它還實現(xiàn)了一套完整的DSP指令和內(nèi)存保護(hù)單元（MPU），從而提高應(yīng)用程序的安全性。該STM32F407ZG系列采用高速嵌入式存儲器 （多達(dá)1 MB閃存，高達(dá)192 KB的SRAM），最多4字節(jié)的備份SRAM，以及廣泛的增強(qiáng)I/O的連接到兩條APB總線和外設(shè)，兩個AHB總線和一個32位的多AHB總線矩陣。

系統(tǒng)的主體框架如圖1所示，各個模塊的作用：STM32單片機(jī)作為主控芯片，完成相關(guān)硬件的初始化，F(xiàn)isher算法的實現(xiàn)載體以及整個系統(tǒng)的協(xié)同工作；TFT LCD和觸摸屏模塊，實現(xiàn)手寫輸入以及識別結(jié)果顯示；W25Q128主要用于存儲識別數(shù)據(jù)資源，比如字庫等資源；按鍵主要用于觸摸屏的校準(zhǔn)設(shè)置；識別的結(jié)果可以通過串口發(fā)送到PC上顯示。

圖1 系統(tǒng)框圖

1.2 主要硬件電路

如圖 2所示，LCD接口連接在 STM32F407ZGT6的FSMC總線上面，可以顯著提高 LCD的刷屏速度。圖中的T_MISO/T_MOSI/T_PEN/T_CS/T_CS用來實現(xiàn)對液晶觸摸屏的控制，LCD_BL則控制LCD的背光。液晶復(fù)位信號RESET則是直接連接在開發(fā)板的復(fù)位按鈕上，和MCU共用一個復(fù)位電路。

圖2 TFT LCD以及觸摸屏電路

SPIFLASH芯片型號為W25Q128，該芯片的容量為128Mb，也就是16 M字節(jié)。圖3中F_CS連接在MCU的PB14上，SPI1_SCK/SPI1_MOSI/SPI1_MISO則分別連接在STM32單片機(jī)的PB3/PB5/PB4上。

圖3 W25Q128電路圖

按鍵電路，KEY0用作模式選擇，其中模式包括“全部識別”、“僅識別數(shù)字”、“僅識別大寫字母”、“僅識別小寫字母”4種。KEY1用作觸摸屏校正，通常在第一次使用的時候進(jìn)行校正，將校正的數(shù)據(jù)存入FLASH，方便下次校正使用。

圖4 按鍵電路

2 Fisher線性判別算法

在解決模式識別匹配問題時，F(xiàn)isher線性判別算法是一種有效的模式分類算法。它要解決的基本問題就是求出一個最佳分類向量特征值，將原來高維的樣本特征向量投影到最佳分類向量空間以達(dá)到減少特征維數(shù)的目的［4-5］。

Fisher判別的基本思路就是投影，針對n維空間中的某點x=（x1，x2…，xn）尋找一個能使它降為一維數(shù)值的線性函數(shù)y（x）：y（x）=∑Cjxj，然后應(yīng)用這個線性函數(shù)把n維空間中的已知類別總體以及求知類別歸屬的樣本都變換為一維數(shù)據(jù)，再根據(jù)其間的親疏程度把未知歸屬的樣本點判定其歸屬。這個線性函數(shù)應(yīng)該能夠在把P維空間中的所有點轉(zhuǎn)化為一維數(shù)值之后，既能最大限度地縮小同類中各個樣本點之間的差異，又能最大限度地擴(kuò)大不同類別中各個樣本點之間的差異，這樣才可能獲得較高的判別效率。在這里借用了一元方差分析的思想，即依據(jù)組間均方差與組內(nèi)均方差之比最大的原則來進(jìn)行判別［7］。

假設(shè)對于一個Rn空間m個樣本分別為：x1，x2，…，xm，即每個x是一個n行的矩陣，其中ni表示屬于i類的樣本個數(shù)，假設(shè)一個有C個類，則m=n1+n2+…+ni…+nc。其中，xi表示第i個樣本，u表示所有樣本的均值，ui表示i類樣本均值。

根據(jù)類間離散度矩陣和類內(nèi)離散度矩陣定義，可以得到如下式子：

式中，Sb表示類間離散度矩陣，Sw類內(nèi)離散度矩陣；

這里引入Fisher鑒別準(zhǔn)則表達(dá)式：

其中，φ為任一n維列矢量。

Fisher線性鑒別分析就是選取使得J（φ）達(dá)到最大值的矢量φ作為投影方向，其物理意義就是投影后的樣本具有最大的類間離散度和最小的類內(nèi)離散度。

把公式（3）和公式（4）帶入公式（5）得到：

設(shè)矩陣R=φT（ui-u）；其中φ可以看成一個空間，也就是說φT（ui-u）是（ui-u）構(gòu)成的低維空間的投影。φT（ui-u）（ui-u）Tφ也可以表示為RRT，而當(dāng)樣本為列向量時，RRT即表示（ui-u）在φ空間的幾何距離的平方，所以，可以推出Fisher線性鑒別分析表達(dá)式的分子即為樣本在投影φ空間下的類間幾何距離的平方和；同理，可以推導(dǎo)出分母即為樣本在投影φ空間下的類內(nèi)幾何距離的平方差。所以，分類問題就轉(zhuǎn)換成找一個低維空間使得樣本投影到該空間下時，類間距離平方和與類內(nèi)距離平方差之比最大，即最佳分類效果［8］。

根據(jù)上面分析，通過最優(yōu)化準(zhǔn)則函數(shù)找到有一組最優(yōu)鑒別矢量構(gòu)成的投影矩陣Wopt：

可以證明，當(dāng)Sw為非奇異時，最佳投影矩陣Wopt的列向量恰為廣義特征方程的d個最大的特征值所對應(yīng)的特征向量（S-1wSb的特征向量）

且最優(yōu)投影軸的個數(shù)d＜=c-1，根據(jù)（8）式可以推出

又由于W=［w1，w2…wn］，把（8）式帶入（6）式可得：

所以根據(jù)公式（7）分解可知，

所以要使得max最大，則只需要取λi即可，所以投影矩陣的列向量為d（自?。﹤€最大特征值所對應(yīng)的特征向量，其中d＜=c-1。

3 軟件設(shè)計

3.1 主程序設(shè)計

主程序主要完成系統(tǒng)初始化，觸摸屏以及LCD等硬件初始化，手寫識別器初始化。

圖5 主程序流程

3.2 手寫識別過程

手寫識別過程和圖像識別、語音識別一樣，主要分為兩個過程：1）訓(xùn)練樣本過程；2）手寫識別。如圖6所示。

3.2.1 樣本訓(xùn)練過程

首先需要采集大量數(shù)據(jù)樣本，樣本類別數(shù)目總共62類（0～9，a~z，A~Z），每個類別（5～10）樣本不等（樣本越多識別率就越高）。對這些樣本進(jìn)行特征提取，提取后為維數(shù)為512維，這對于STM32單片機(jī)計算量和模板庫的存儲量來說都很難接受，所以需要使用Fisher線性鑒別分析算法進(jìn)行降維處理。本設(shè)計中將維度降到64維，然后針對各個樣本類別進(jìn)行平均計算得到該類別的樣本模板［6］。

圖6 手寫識別流程

3.2.2 對于識別過程

首先得到觸屏輸入的有序軌跡，進(jìn)行預(yù)處理，主要是重采樣和歸一化處理。重采樣主要是因為不同的輸入設(shè)備不同的輸入處理方式產(chǎn)生的有序軌跡序列有所不同，為了達(dá)到更好的識別結(jié)果我們需要對訓(xùn)練樣本和識別輸入的樣本進(jìn)行重采樣處理，這里主要應(yīng)用隔點重采樣的方法對輸入的序列進(jìn)行重采樣；而歸一化就是因為不同的書寫風(fēng)格采樣分辨率的差異會導(dǎo)致字體太小不同，因此需要對輸入軌跡進(jìn)行歸一化［9］。這里把樣本進(jìn)行線性縮放的方法歸一化為64×64像素。

接下來進(jìn)行同樣的八方向特征提取操作。所謂八方向特征就是首先將經(jīng)過預(yù)處理后的輸入進(jìn)行切分成8×8的小方格，每個方格8×8個像素；然后對每個個小格進(jìn)行各個方向的點數(shù)統(tǒng)計。如某個方格內(nèi)一共有10個點，其中8個方向的點分別為：1、3、5、2、3、4、3、2那么這個格子得到的8個特征向量為［0.1，0.3，0.5，0.2，0.3，0.4，0.3，0.2］?？偣灿?4個格子于是一個樣本最終能得到64×8=512維特征［7-9］。

由于訓(xùn)練過程進(jìn)行了Fisher降維計算，所以識別過程同樣需要對應(yīng)的Fisher降維過程得到最終的 64維特征。這個計算過程就是在訓(xùn)練模板的過程中可以運算得到一個512× 64維的矩陣，那么我們通過矩陣乘運算可以得到 64維的最終特征值。

最后將這64維特征分別與模板中的特征進(jìn)行求距離運算，得到最小的距離為該輸入的最佳識別結(jié)果輸出。

3.3 手寫識別實現(xiàn)過程

我們根據(jù)3.2分析的算法實現(xiàn)做成一個數(shù)字字母識別庫，由以下幾步實現(xiàn)手寫識別：

1）調(diào)用alientek_ncr_init函數(shù)，初始化識別程序

該函數(shù)用來初始化識別器，在手寫識別進(jìn)行之前，必須調(diào)用該初始化函數(shù)。

2）獲取輸入的點陣數(shù)據(jù)

此步，我們通過觸摸屏獲取輸入軌跡點陣坐標(biāo)，然后存放到一個緩存區(qū)里面，由于識別器至少輸入2個不同坐標(biāo)的點陣數(shù)據(jù)，才能正常識別。

3）調(diào)用alientek_ncr函數(shù)，得到識別結(jié)果

通過調(diào)用alientek_ncr函數(shù)，可以得到輸入點陣的識別結(jié)果，結(jié)果保存在result參數(shù)里邊，采用ASCII碼格式存儲。

4）通過調(diào)用alientek_ncr_stop函數(shù)，終止識別

如果不需要繼續(xù)識別，則調(diào)用alientek_ncr_stop函數(shù)，終止識別器；如果還需要繼續(xù)識別，重復(fù)步驟2）和步驟3）即可。

4 實驗及結(jié)果分析

4.1 實驗過程

開機(jī)的時候先初始化手寫識別器，然后檢測字庫，之后進(jìn)入等待輸入，此時，我們在手寫區(qū)寫數(shù)字/字符，在每次寫入結(jié)束后，自動進(jìn)入識別狀態(tài)，進(jìn)行識別，然后將識別結(jié)果輸出在LCD模塊上面。通過按KEY0可以進(jìn)行模式切換（4種模式都可以測試），通過按KEY2，可以進(jìn)入觸摸屏校準(zhǔn)（如果發(fā)現(xiàn)觸摸屏不準(zhǔn)，請執(zhí)行此操作）。DS0用于指示程序運行狀態(tài)。

4.2 實驗結(jié)果

實驗結(jié)果如圖7、圖8所示。

圖7 數(shù)字"3"和"8"識別

圖8 大寫字母“K”識別和小寫字母“m”識別

4.3 實驗性能分析

實驗過程中對數(shù)字“3”和“8”，大寫字母“K”以及小寫字母“m”分別進(jìn)行50次手寫輸入識別，得到不同字符的識別率，如下表格所示：

表1 字符識別率

從表1中可以看出，基于Fisher線性鑒別分析算法，對數(shù)字的準(zhǔn)確率達(dá)到98%，對于字母的識別準(zhǔn)確率達(dá)到了97%，平均識別準(zhǔn)確率達(dá)到了97.3%，達(dá)到了設(shè)計的要求，具有一定的使用價值。

5 結(jié) 論

文中采用Fisher線性鑒別分析的方法實現(xiàn)了手寫識別系統(tǒng)，該手寫識別系統(tǒng)采用具有高性能的STM32單片機(jī)作為硬件載體，將Fisher線性鑒別分析算法在硬件上實現(xiàn)；軟件采用模塊化的設(shè)計思想，提高了系統(tǒng)的可靠性和維護(hù)性。經(jīng)過多組手寫數(shù)字和字母實際測試，能夠快速、準(zhǔn)確地識別出手寫數(shù)字和字母，達(dá)到了實驗?zāi)康?，完成了低成本手寫識別系統(tǒng)的設(shè)計要求。

［1］趙繼印，鄭蕊蕊，吳寶春，等.脫機(jī)手寫體漢子識別綜述［J］.電子學(xué)報，2010（2）:406-407.

［2］陳軍勝.組合結(jié)構(gòu)特征的自由手寫體數(shù)字識別算法研究［J］.計算機(jī)工程與應(yīng)用，2013，49（5）:179.

［3］雙小川，張克.基于統(tǒng)計和結(jié)構(gòu)特征的手寫數(shù)字識別研究［J］.計算機(jī)工程與設(shè)計，2012（33）:1534-1537.

［4］孫艷豐，齊光磊，胡永利，等.基于改進(jìn)Fisher準(zhǔn)則的深度卷積神經(jīng)網(wǎng)絡(luò)識別算法 ［J］.北京工業(yè)大學(xué)學(xué)報，2015，41: 836-838.

［5］李峰，王正群，徐春林，等.基于馬氏距離的局部邊界Fisher分析降維算法［J］.計算機(jī)應(yīng)用，2013，33（7）:1930-1934.

［6］高學(xué)，王有旺.基于CNN和隨機(jī)彈性形變的相似手寫漢字識別［J］.華南理工大學(xué)學(xué)報，2014（42）:73.

［7］劉桂紅，李丹，孫勁光.結(jié)合Gabor特征和自適應(yīng)加權(quán) Fisher準(zhǔn)則的人臉識別［J］.計算機(jī)工程與應(yīng)用，2015（10）:2-4.

［8］張潤蓮，張昭，彭小金，等.基于Fisher分和支持向量機(jī)的特征選擇算法［J］.計算機(jī)工程與設(shè)計，2014（35）:4145-4146.

［9］鄭建煒，王萬良，姚曉敏，等.張量局部Fisher判別分析的人臉識別［J］.自動化學(xué)報，2012（38）:1486-1489.

Fisher linear differential analysis in the application of handw ritten recognition system

WANG Tang-wang1，LIU Bi-wang2，WANGBao-zhong1
（1.Jiangsu University of Science and Technology，Zhenjiang 212003，China；2.Changzhou College of Information Technology，Changzhou 213164，China）

In order to achieve the intelligent recognition ofmobile equipment input requirements，this paper designed a kind of single chipmicrocomputer intelligenthandwritten recognition system.Based on the analysis of the Fisher linear differential algorithm，the carrier，with the single chip processor as the hardware realization of Fisher linear identification algorithm in the application of handwriting recognition.The hardware partmainly use STM32F407 MCU as the core，the programming to realize the Fisher linear differentialalgorithm，in the processof the experimentmany timeswith differentcharacter recognition. Experiments show that the system has simple operation and high recognition rate and recognition speed，has practical use value，meet the design requirements.

Fisher；STM32F407；single chip microcomputer；handwriting recognition

TN702

A

1674－6236（2016）20-0163-04

2015-10-30 稿件編號：201510227

王堂旺（1989—），男，云南昭通人，碩士。研究方向：嵌入式系統(tǒng)。