王堂旺,劉必旺,王寶忠
(1.江蘇科技大學(xué) 江蘇 鎮(zhèn)江212003;2.常州信息職業(yè)技術(shù)學(xué)院 江蘇 常州213164)
基于Fisher算法在手寫識(shí)別系統(tǒng)中的應(yīng)用
王堂旺1,劉必旺2,王寶忠1
(1.江蘇科技大學(xué) 江蘇 鎮(zhèn)江212003;2.常州信息職業(yè)技術(shù)學(xué)院 江蘇 常州213164)
為了實(shí)現(xiàn)智能移動(dòng)設(shè)備輸入識(shí)別的需求,文中設(shè)計(jì)了一種單片機(jī)實(shí)現(xiàn)智能手寫識(shí)別系統(tǒng)。在分析Fisher線性鑒別算法的基礎(chǔ)上,以單片機(jī)為硬件載體,實(shí)現(xiàn)Fisher線性鑒別算法在手寫識(shí)別中的應(yīng)用。該系統(tǒng)的硬件部分主要使用STM32F407單片機(jī)為核心,編程實(shí)現(xiàn)Fisher線性鑒別算法,實(shí)驗(yàn)過程中對(duì)不同字符進(jìn)行多次識(shí)別。實(shí)驗(yàn)表明該系統(tǒng)具有操作簡(jiǎn)單、識(shí)別率高、識(shí)別速度快等優(yōu)點(diǎn),具有實(shí)際使用價(jià)值,達(dá)到設(shè)計(jì)要求。
Fisher;STM32F407;單片機(jī);手寫識(shí)別
隨著智能手機(jī)和平板電腦等移動(dòng)設(shè)備的普及,手寫識(shí)別的應(yīng)用也被越來(lái)越多的設(shè)備采用。隨著觸摸屏的廣泛使用,加之手寫識(shí)別技術(shù)的告訴發(fā)展,移動(dòng)終端的輸入形式不再局限于鍵盤形式,手寫輸入也逐漸流行起來(lái)[1-2]。手寫識(shí)別,是指對(duì)在手寫設(shè)備上書寫時(shí)產(chǎn)生的有序軌跡信息進(jìn)行識(shí)別的過程。手寫識(shí)別能夠使用戶按照最自然、最方便的輸入方式進(jìn)行文字輸入,易學(xué)易用,可取代鍵盤或者鼠標(biāo)。用于手寫輸入的設(shè)備有許多種,比如電磁感應(yīng)手寫板、壓感式手寫板、觸摸屏、觸控板、超聲波筆等。手寫識(shí)別是利用某種輸入設(shè)備直接書寫文字,經(jīng)過系統(tǒng)識(shí)別處理之后,轉(zhuǎn)換為文字統(tǒng)一表示的輸入方法。在書寫字符時(shí),觸筆在觸摸屏上的接觸點(diǎn)的電壓將會(huì)發(fā)生變化,通過ADC轉(zhuǎn)換器可以轉(zhuǎn)換為L(zhǎng)CD屏的坐標(biāo),因此手寫筆的運(yùn)動(dòng)軌跡被轉(zhuǎn)化為坐標(biāo)序列,從這些坐標(biāo)序列可以比較容易第抽取書寫文字的筆畫和筆順等信息,對(duì)書寫者所書寫的字符筆跡進(jìn)行識(shí)別,根據(jù)識(shí)別結(jié)果轉(zhuǎn)換成字符輸出顯示到LCD屏上[2-3]。
文中在分析Fisher線性鑒別算法的基礎(chǔ)上,以STM32單片機(jī)為硬件載體,編程實(shí)現(xiàn)Fisher線性鑒別算法,并將其應(yīng)用到手寫識(shí)別系統(tǒng)中去,能夠快速準(zhǔn)確地識(shí)別出數(shù)字以及大小寫字母。
1.1 系統(tǒng)硬件設(shè)計(jì)
系統(tǒng)主要采用STM32F407ZG,它是基于高性能的ARM Cortex-M4F的32位RISC內(nèi)核,工作頻率高達(dá)168 MHz的Cortex-M4F核心功能支持所有ARM單精度數(shù)據(jù)處理指令和數(shù)據(jù)類型的單精度浮點(diǎn)單元(FPU)。它還實(shí)現(xiàn)了一套完整的DSP指令和內(nèi)存保護(hù)單元(MPU),從而提高應(yīng)用程序的安全性。該STM32F407ZG系列采用高速嵌入式存儲(chǔ)器 (多達(dá)1 MB閃存,高達(dá)192 KB的SRAM),最多4字節(jié)的備份SRAM,以及廣泛的增強(qiáng)I/O的連接到兩條APB總線和外設(shè),兩個(gè)AHB總線和一個(gè)32位的多AHB總線矩陣。
系統(tǒng)的主體框架如圖1所示,各個(gè)模塊的作用:STM32單片機(jī)作為主控芯片,完成相關(guān)硬件的初始化,F(xiàn)isher算法的實(shí)現(xiàn)載體以及整個(gè)系統(tǒng)的協(xié)同工作;TFT LCD和觸摸屏模塊,實(shí)現(xiàn)手寫輸入以及識(shí)別結(jié)果顯示;W25Q128主要用于存儲(chǔ)識(shí)別數(shù)據(jù)資源,比如字庫(kù)等資源;按鍵主要用于觸摸屏的校準(zhǔn)設(shè)置;識(shí)別的結(jié)果可以通過串口發(fā)送到PC上顯示。
圖1 系統(tǒng)框圖
1.2 主要硬件電路
如圖 2所示,LCD接口連接在 STM32F407ZGT6的FSMC總線上面,可以顯著提高 LCD的刷屏速度。圖中的T_MISO/T_MOSI/T_PEN/T_CS/T_CS用來(lái)實(shí)現(xiàn)對(duì)液晶觸摸屏的控制,LCD_BL則控制LCD的背光。液晶復(fù)位信號(hào)RESET則是直接連接在開發(fā)板的復(fù)位按鈕上,和MCU共用一個(gè)復(fù)位電路。
圖2 TFT LCD以及觸摸屏電路
SPIFLASH芯片型號(hào)為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í)別”、“僅識(shí)別數(shù)字”、“僅識(shí)別大寫字母”、“僅識(shí)別小寫字母”4種。KEY1用作觸摸屏校正,通常在第一次使用的時(shí)候進(jìn)行校正,將校正的數(shù)據(jù)存入FLASH,方便下次校正使用。
圖4 按鍵電路
在解決模式識(shí)別匹配問題時(shí),F(xiàn)isher線性判別算法是一種有效的模式分類算法。它要解決的基本問題就是求出一個(gè)最佳分類向量特征值,將原來(lái)高維的樣本特征向量投影到最佳分類向量空間以達(dá)到減少特征維數(shù)的目的[4-5]。
Fisher判別的基本思路就是投影,針對(duì)n維空間中的某點(diǎn)x=(x1,x2…,xn)尋找一個(gè)能使它降為一維數(shù)值的線性函數(shù)y(x):y(x)=∑Cjxj,然后應(yīng)用這個(gè)線性函數(shù)把n維空間中的已知類別總體以及求知類別歸屬的樣本都變換為一維數(shù)據(jù),再根據(jù)其間的親疏程度把未知?dú)w屬的樣本點(diǎn)判定其歸屬。這個(gè)線性函數(shù)應(yīng)該能夠在把P維空間中的所有點(diǎn)轉(zhuǎn)化為一維數(shù)值之后,既能最大限度地縮小同類中各個(gè)樣本點(diǎn)之間的差異,又能最大限度地?cái)U(kuò)大不同類別中各個(gè)樣本點(diǎn)之間的差異,這樣才可能獲得較高的判別效率。在這里借用了一元方差分析的思想,即依據(jù)組間均方差與組內(nèi)均方差之比最大的原則來(lái)進(jìn)行判別[7]。
假設(shè)對(duì)于一個(gè)Rn空間m個(gè)樣本分別為:x1,x2,…,xm,即每個(gè)x是一個(gè)n行的矩陣,其中ni表示屬于i類的樣本個(gè)數(shù),假設(shè)一個(gè)有C個(gè)類,則m=n1+n2+…+ni…+nc。其中,xi表示第i個(gè)樣本,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);其中φ可以看成一個(gè)空間,也就是說(shuō)φT(ui-u)是(ui-u)構(gòu)成的低維空間的投影。φT(ui-u)(ui-u)Tφ也可以表示為RRT,而當(dāng)樣本為列向量時(shí),RRT即表示(ui-u)在φ空間的幾何距離的平方,所以,可以推出Fisher線性鑒別分析表達(dá)式的分子即為樣本在投影φ空間下的類間幾何距離的平方和;同理,可以推導(dǎo)出分母即為樣本在投影φ空間下的類內(nèi)幾何距離的平方差。所以,分類問題就轉(zhuǎn)換成找一個(gè)低維空間使得樣本投影到該空間下時(shí),類間距離平方和與類內(nèi)距離平方差之比最大,即最佳分類效果[8]。
根據(jù)上面分析,通過最優(yōu)化準(zhǔn)則函數(shù)找到有一組最優(yōu)鑒別矢量構(gòu)成的投影矩陣Wopt:
可以證明,當(dāng)Sw為非奇異時(shí),最佳投影矩陣Wopt的列向量恰為廣義特征方程的d個(gè)最大的特征值所對(duì)應(yīng)的特征向量(S-1wSb的特征向量)
且最優(yōu)投影軸的個(gè)數(shù)d<=c-1,根據(jù)(8)式可以推出
又由于W=[w1,w2…wn],把(8)式帶入(6)式可得:
所以根據(jù)公式(7)分解可知,
所以要使得max最大,則只需要取λi即可,所以投影矩陣的列向量為d(自?。﹤€(gè)最大特征值所對(duì)應(yīng)的特征向量,其中d<=c-1。
3.1 主程序設(shè)計(jì)
主程序主要完成系統(tǒng)初始化,觸摸屏以及LCD等硬件初始化,手寫識(shí)別器初始化。
圖5 主程序流程
3.2 手寫識(shí)別過程
手寫識(shí)別過程和圖像識(shí)別、語(yǔ)音識(shí)別一樣,主要分為兩個(gè)過程:1)訓(xùn)練樣本過程;2)手寫識(shí)別。如圖6所示。
3.2.1 樣本訓(xùn)練過程
首先需要采集大量數(shù)據(jù)樣本,樣本類別數(shù)目總共62類(0~9,a~z,A~Z),每個(gè)類別(5~10)樣本不等(樣本越多識(shí)別率就越高)。對(duì)這些樣本進(jìn)行特征提取,提取后為維數(shù)為512維,這對(duì)于STM32單片機(jī)計(jì)算量和模板庫(kù)的存儲(chǔ)量來(lái)說(shuō)都很難接受,所以需要使用Fisher線性鑒別分析算法進(jìn)行降維處理。本設(shè)計(jì)中將維度降到64維,然后針對(duì)各個(gè)樣本類別進(jìn)行平均計(jì)算得到該類別的樣本模板[6]。
圖6 手寫識(shí)別流程
3.2.2 對(duì)于識(shí)別過程
首先得到觸屏輸入的有序軌跡,進(jìn)行預(yù)處理,主要是重采樣和歸一化處理。重采樣主要是因?yàn)椴煌妮斎朐O(shè)備不同的輸入處理方式產(chǎn)生的有序軌跡序列有所不同,為了達(dá)到更好的識(shí)別結(jié)果我們需要對(duì)訓(xùn)練樣本和識(shí)別輸入的樣本進(jìn)行重采樣處理,這里主要應(yīng)用隔點(diǎn)重采樣的方法對(duì)輸入的序列進(jìn)行重采樣;而歸一化就是因?yàn)椴煌臅鴮戯L(fēng)格采樣分辨率的差異會(huì)導(dǎo)致字體太小不同,因此需要對(duì)輸入軌跡進(jìn)行歸一化[9]。這里把樣本進(jìn)行線性縮放的方法歸一化為64×64像素。
接下來(lái)進(jìn)行同樣的八方向特征提取操作。所謂八方向特征就是首先將經(jīng)過預(yù)處理后的輸入進(jìn)行切分成8×8的小方格,每個(gè)方格8×8個(gè)像素;然后對(duì)每個(gè)個(gè)小格進(jìn)行各個(gè)方向的點(diǎn)數(shù)統(tǒng)計(jì)。如某個(gè)方格內(nèi)一共有10個(gè)點(diǎn),其中8個(gè)方向的點(diǎn)分別為:1、3、5、2、3、4、3、2那么這個(gè)格子得到的8個(gè)特征向量為[0.1,0.3,0.5,0.2,0.3,0.4,0.3,0.2]??偣灿?4個(gè)格子于是一個(gè)樣本最終能得到64×8=512維特征[7-9]。
由于訓(xùn)練過程進(jìn)行了Fisher降維計(jì)算,所以識(shí)別過程同樣需要對(duì)應(yīng)的Fisher降維過程得到最終的 64維特征。這個(gè)計(jì)算過程就是在訓(xùn)練模板的過程中可以運(yùn)算得到一個(gè)512× 64維的矩陣,那么我們通過矩陣乘運(yùn)算可以得到 64維的最終特征值。
最后將這64維特征分別與模板中的特征進(jìn)行求距離運(yùn)算,得到最小的距離為該輸入的最佳識(shí)別結(jié)果輸出。
3.3 手寫識(shí)別實(shí)現(xiàn)過程
我們根據(jù)3.2分析的算法實(shí)現(xiàn)做成一個(gè)數(shù)字字母識(shí)別庫(kù),由以下幾步實(shí)現(xiàn)手寫識(shí)別:
1)調(diào)用alientek_ncr_init函數(shù),初始化識(shí)別程序
該函數(shù)用來(lái)初始化識(shí)別器,在手寫識(shí)別進(jìn)行之前,必須調(diào)用該初始化函數(shù)。
2)獲取輸入的點(diǎn)陣數(shù)據(jù)
此步,我們通過觸摸屏獲取輸入軌跡點(diǎn)陣坐標(biāo),然后存放到一個(gè)緩存區(qū)里面,由于識(shí)別器至少輸入2個(gè)不同坐標(biāo)的點(diǎn)陣數(shù)據(jù),才能正常識(shí)別。
3)調(diào)用alientek_ncr函數(shù),得到識(shí)別結(jié)果
通過調(diào)用alientek_ncr函數(shù),可以得到輸入點(diǎn)陣的識(shí)別結(jié)果,結(jié)果保存在result參數(shù)里邊,采用ASCII碼格式存儲(chǔ)。
4)通過調(diào)用alientek_ncr_stop函數(shù),終止識(shí)別
如果不需要繼續(xù)識(shí)別,則調(diào)用alientek_ncr_stop函數(shù),終止識(shí)別器;如果還需要繼續(xù)識(shí)別,重復(fù)步驟2)和步驟3)即可。
4.1 實(shí)驗(yàn)過程
開機(jī)的時(shí)候先初始化手寫識(shí)別器,然后檢測(cè)字庫(kù),之后進(jìn)入等待輸入,此時(shí),我們?cè)谑謱憛^(qū)寫數(shù)字/字符,在每次寫入結(jié)束后,自動(dòng)進(jìn)入識(shí)別狀態(tài),進(jìn)行識(shí)別,然后將識(shí)別結(jié)果輸出在LCD模塊上面。通過按KEY0可以進(jìn)行模式切換(4種模式都可以測(cè)試),通過按KEY2,可以進(jìn)入觸摸屏校準(zhǔn)(如果發(fā)現(xiàn)觸摸屏不準(zhǔn),請(qǐng)執(zhí)行此操作)。DS0用于指示程序運(yùn)行狀態(tài)。
4.2 實(shí)驗(yàn)結(jié)果
實(shí)驗(yàn)結(jié)果如圖7、圖8所示。
圖7 數(shù)字"3"和"8"識(shí)別
圖8 大寫字母“K”識(shí)別和小寫字母“m”識(shí)別
4.3 實(shí)驗(yàn)性能分析
實(shí)驗(yàn)過程中對(duì)數(shù)字“3”和“8”,大寫字母“K”以及小寫字母“m”分別進(jìn)行50次手寫輸入識(shí)別,得到不同字符的識(shí)別率,如下表格所示:
表1 字符識(shí)別率
從表1中可以看出,基于Fisher線性鑒別分析算法,對(duì)數(shù)字的準(zhǔn)確率達(dá)到98%,對(duì)于字母的識(shí)別準(zhǔn)確率達(dá)到了97%,平均識(shí)別準(zhǔn)確率達(dá)到了97.3%,達(dá)到了設(shè)計(jì)的要求,具有一定的使用價(jià)值。
文中采用Fisher線性鑒別分析的方法實(shí)現(xiàn)了手寫識(shí)別系統(tǒng),該手寫識(shí)別系統(tǒng)采用具有高性能的STM32單片機(jī)作為硬件載體,將Fisher線性鑒別分析算法在硬件上實(shí)現(xiàn);軟件采用模塊化的設(shè)計(jì)思想,提高了系統(tǒng)的可靠性和維護(hù)性。經(jīng)過多組手寫數(shù)字和字母實(shí)際測(cè)試,能夠快速、準(zhǔn)確地識(shí)別出手寫數(shù)字和字母,達(dá)到了實(shí)驗(yàn)?zāi)康模瓿闪说统杀臼謱懽R(shí)別系統(tǒng)的設(shè)計(jì)要求。
[1]趙繼印,鄭蕊蕊,吳寶春,等.脫機(jī)手寫體漢子識(shí)別綜述[J].電子學(xué)報(bào),2010(2):406-407.
[2]陳軍勝.組合結(jié)構(gòu)特征的自由手寫體數(shù)字識(shí)別算法研究[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(5):179.
[3]雙小川,張克.基于統(tǒng)計(jì)和結(jié)構(gòu)特征的手寫數(shù)字識(shí)別研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2012(33):1534-1537.
[4]孫艷豐,齊光磊,胡永利,等.基于改進(jìn)Fisher準(zhǔn)則的深度卷積神經(jīng)網(wǎng)絡(luò)識(shí)別算法 [J].北京工業(yè)大學(xué)學(xué)報(bào),2015,41: 836-838.
[5]李峰,王正群,徐春林,等.基于馬氏距離的局部邊界Fisher分析降維算法[J].計(jì)算機(jī)應(yīng)用,2013,33(7):1930-1934.
[6]高學(xué),王有旺.基于CNN和隨機(jī)彈性形變的相似手寫漢字識(shí)別[J].華南理工大學(xué)學(xué)報(bào),2014(42):73.
[7]劉桂紅,李丹,孫勁光.結(jié)合Gabor特征和自適應(yīng)加權(quán) Fisher準(zhǔn)則的人臉識(shí)別[J].計(jì)算機(jī)工程與應(yīng)用,2015(10):2-4.
[8]張潤(rùn)蓮,張昭,彭小金,等.基于Fisher分和支持向量機(jī)的特征選擇算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2014(35):4145-4146.
[9]鄭建煒,王萬(wàn)良,姚曉敏,等.張量局部Fisher判別分析的人臉識(shí)別[J].自動(dòng)化學(xué)報(bào),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 稿件編號(hào):201510227
王堂旺(1989—),男,云南昭通人,碩士。研究方向:嵌入式系統(tǒng)。