手寫口令系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

摘 要：本文主要描述了在android平臺(tái)上對(duì)手寫口令登陸系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)，采用CAPTCHA圖片驗(yàn)證碼提高系統(tǒng)的安全性。

關(guān)鍵詞：Android；手寫口令；CAPTCHA驗(yàn)證碼；支持向量機(jī)

中圖分類號(hào)：TP391.41

目前主要的手勢(shì)識(shí)別技術(shù)有：模板匹配技術(shù)、神經(jīng)網(wǎng)絡(luò)技術(shù)以及統(tǒng)計(jì)分析技術(shù)等。

模板匹配技術(shù)需要預(yù)先儲(chǔ)存手勢(shì)模板，將經(jīng)傳感器輸入的手勢(shì)與模板手勢(shì)進(jìn)行匹配，通過(guò)一定的算法計(jì)算手勢(shì)之間的相似度來(lái)進(jìn)行識(shí)別；神經(jīng)網(wǎng)絡(luò)技術(shù)中廣泛使用的BP神經(jīng)網(wǎng)絡(luò)技術(shù)是一種俺誤差逆?zhèn)鞑ニ惴ㄓ?xùn)練的多層前饋網(wǎng)絡(luò)，能夠?qū)W習(xí)和存儲(chǔ)大量的輸入-輸出模式映射關(guān)系，而無(wú)需事前解釋描述這種映射關(guān)系的數(shù)學(xué)方程。它的學(xué)習(xí)規(guī)則是使用最快速下降法，通過(guò)反向傳播來(lái)不斷調(diào)整網(wǎng)絡(luò)的權(quán)值和閾值，使網(wǎng)絡(luò)的誤差平方和最??；統(tǒng)計(jì)分析技術(shù)，例如：統(tǒng)計(jì)模式識(shí)別，就是用給定的有限數(shù)量的樣本集，在已知研究對(duì)象統(tǒng)計(jì)模型或已知判別函數(shù)類條件下根據(jù)一定的準(zhǔn)則通過(guò)學(xué)習(xí)算法把d維特征空間劃分為c個(gè)區(qū)域，每一個(gè)區(qū)域與每一個(gè)類別對(duì)應(yīng)。模式識(shí)別系統(tǒng)在進(jìn)行工作時(shí)只要判斷被識(shí)別的對(duì)象落在哪一個(gè)區(qū)域，就能確定出它所屬的類別。[1]

隨著互聯(lián)網(wǎng)的普及，各種網(wǎng)絡(luò)服務(wù)日益成為人們?nèi)粘Ｉ畹囊徊糠郑缑赓M(fèi)的電子郵箱服務(wù)、在線投票及推薦系統(tǒng)、網(wǎng)絡(luò)聊天室等等。這些面向人類用戶的服務(wù)時(shí)常被一些惡意計(jì)算機(jī)程序?yàn)E用，它們占用服務(wù)資源，產(chǎn)生大量的網(wǎng)絡(luò)垃圾，影響用戶的網(wǎng)絡(luò)體驗(yàn)，對(duì)網(wǎng)絡(luò)服務(wù)的安全性造成極大威脅。應(yīng)運(yùn)而生的全自動(dòng)開(kāi)放式人機(jī)區(qū)分圖靈測(cè)試CAPTCHA是解決此類網(wǎng)絡(luò)安全問(wèn)題的一種機(jī)制，即通常所說(shuō)的“驗(yàn)證碼”技術(shù)。根據(jù)不同的表現(xiàn)載體和內(nèi)容，CAPTCHA分為文本、圖像和聲音3種類型。[2]

Android手寫口令采用的是模板匹配技術(shù)，為了提高口令識(shí)別的準(zhǔn)確性和系統(tǒng)的安全性，本文采用支持向量機(jī)與模板匹配相結(jié)合的方法以及CAPTCHA圖片驗(yàn)證碼實(shí)現(xiàn)登陸系統(tǒng)。

1 原理

Android 手勢(shì)識(shí)別采用的是模板匹配技術(shù)。[1]主要包括手勢(shì)圖像的獲取，提取后圖像的預(yù)處理（包括灰度化和二值化處理），圖像幾何矩的提取，SVM模型的訓(xùn)練以及最后的匹對(duì)。[3]

1.1 手勢(shì)圖像的獲取

首先要定義一個(gè)手勢(shì)并獲取其特征數(shù)據(jù)，再將其數(shù)據(jù)存儲(chǔ)起來(lái)等待比對(duì)。要在屏幕上畫(huà)出一個(gè)圖形，并獲取該圖形數(shù)據(jù)，將圖形數(shù)據(jù)轉(zhuǎn)化為特征值數(shù)據(jù)，并為圖形數(shù)據(jù)定義出一個(gè)系統(tǒng)名稱標(biāo)識(shí)存儲(chǔ)到指定的“手勢(shì)倉(cāng)庫(kù)”中。[4]

簡(jiǎn)單的手勢(shì)能夠通過(guò)有方向和大小向量來(lái)構(gòu)造。輸入手勢(shì)的每一個(gè)點(diǎn)代表觸屏設(shè)備識(shí)別到的觸屏點(diǎn)，并根據(jù)錄入的順序依次儲(chǔ)存在點(diǎn)數(shù)組里。隨后對(duì)手勢(shì)點(diǎn)數(shù)組進(jìn)行遍歷，求出相鄰點(diǎn)的方向，方向由前面的點(diǎn)指向后面的點(diǎn)，將方向值轉(zhuǎn)換為與圖1最相近的方向值，并存為方向數(shù)組。 對(duì)方向數(shù)組中連續(xù)的相同方向上點(diǎn)進(jìn)行合并，計(jì)算連續(xù)方向點(diǎn)的距離同時(shí)將距離過(guò)短的向量作為噪點(diǎn)去除。[1]

圖1

1.2 SVM 模型的訓(xùn)練以及最后的匹對(duì)

漢字識(shí)別一直是模式識(shí)別最重要的研究領(lǐng)域之一。經(jīng)過(guò)多年的研究，已經(jīng)取得了大量成果。但是，無(wú)約束的非特定人手寫漢字識(shí)別仍然被認(rèn)為是文字識(shí)別領(lǐng)域最困難的問(wèn)題之一，其原因可以歸結(jié)為：（1）漢字規(guī)模大（2）相似漢字較多，且有些相似字差別極其細(xì)微（3）存在大量的不規(guī)則書(shū)寫變形。由于（2）、（3）的存在，導(dǎo)致手寫漢字，特別是相似字在特征空間中的距離變小，使得普通的距離分類器的推廣能力變?nèi)酢Ｒ虼?，如何補(bǔ)償手寫漢字的書(shū)寫變形，提高分類器的泛化和推廣能力，就成為漢字識(shí)別研究的關(guān)鍵問(wèn)題之一。

支持向量機(jī)是ATTBell實(shí)驗(yàn)室的V.Vapnik等人根據(jù)統(tǒng)計(jì)學(xué)習(xí)理論提出的一種新的機(jī)器學(xué)習(xí)方法，已經(jīng)在模式識(shí)別、回歸分析和特征選擇等方面得到了較好的效果。支持向量機(jī)可以看作一種新的訓(xùn)練多項(xiàng)式、徑向基分類器或神經(jīng)網(wǎng)絡(luò)分類器的方法。根據(jù)結(jié)構(gòu)風(fēng)險(xiǎn)最小化準(zhǔn)則，在使訓(xùn)練樣本分類誤差極小化的前提下，盡量提高分類器的泛化推廣能力。從實(shí)施的角度，訓(xùn)練支持向量機(jī)等價(jià)于解一個(gè)線性約束的二次規(guī)劃問(wèn)題，使得分隔特征空間中兩類模式點(diǎn)的兩個(gè)超平面之間距離最大，而且它能保證得到的解為全局最優(yōu)點(diǎn)，使得基于支持向量機(jī)的手寫漢字分類器能夠吸收書(shū)寫的變形，從而具有較好的泛化和推廣能力。[5]

支持向量機(jī)可以有效提高手寫口令識(shí)別的準(zhǔn)確度，以下為分類器的具體實(shí)現(xiàn)：

1.2.1 計(jì)算特征手勢(shì)

設(shè)手勢(shì)圖像f（x，y）為二維n×m灰度圖像，用nm維向量R表示。手勢(shì)圖像訓(xùn)練集為{Ri|i=1，2，…，p}，其中p為訓(xùn)練集中圖像總數(shù)。這p幅圖像的平均向量為：

_ p

R=1/p∑Ri

i=1

對(duì)訓(xùn)練樣本規(guī)范化，即每個(gè)手勢(shì)Ri與平均手勢(shì)R的差值向量：

_

Ai=Ri-R i=1，2，…，p

其中列向量Ai表示一個(gè)訓(xùn)練樣本。

訓(xùn)練圖像由協(xié)方差矩陣可表示為：

C=AAT

其中訓(xùn)練樣本nm×p維矩陣A=[A1，A2，…，Ap]

特征手勢(shì)由協(xié)方差矩陣C的正交特征向量組成。對(duì)于nm維手勢(shì)圖像，協(xié)方差矩陣C的大小為nm×nm，對(duì)它求解特征值和特征向量是很困難的，由此引入奇異值分解定理來(lái)解決維數(shù)過(guò)高的問(wèn)題。

1.2.2 奇異值分解定理

由奇異值分解定理可以得到一個(gè)推論：

U=A∨∧1/2

由協(xié)方差矩陣C=AAT，構(gòu)造矩陣：L=ATA∈Rp×p，容易求出其特征值及相應(yīng)的正交歸一特征向量vi（i=1，2，…，p）。由以上述推論可知，C的正交歸一特征向量ui為：

ui=1/Avi i=1，2，…，p

這就是圖像的特征向量，它是計(jì)算p×p低維矩陣L的特征值和特征向量而間接求出來(lái)的。實(shí)際上l（l﹤p）個(gè)特征值足夠用于手勢(shì)識(shí)別。因此僅取L的前l(fā)個(gè)最大特征值的特征向量計(jì)算特征手勢(shì)。

1.2.3 特征向量的選取

以上總共得到了p（訓(xùn)練樣本數(shù)目）個(gè)特征向量。雖然p 比nm小很多。但通常情況下，p 仍然會(huì)太大。根據(jù)應(yīng)用的要求，并不是所有的ui都有很大的保留意義。

考慮到使用K-L變換作為對(duì)手勢(shì)圖像的壓縮手段，可以選取最大的前l(fā)個(gè)特征向量，使得：

l p

∑λi/∑λi≥α

i=1 i=1

在實(shí)際中，可以選擇α=0.90，或者自定義的其他值。這說(shuō)明樣本集在前l(fā)個(gè)軸上的能量占到整個(gè)能量的90%以上。

1.2.4 基于特征手勢(shì)的手勢(shì)識(shí)別

接下來(lái)對(duì)特征手勢(shì)進(jìn)行手勢(shì)劃分，通過(guò)訓(xùn)練集優(yōu)化得到最優(yōu)解。已知訓(xùn)練集

T={（x1，y1），（x2，y2），…，（xl，yl）∈（X，Y）l，其中xi∈X =R0，yi∈Y∈{-1，1}，i=1，2，…，l。

然后，選擇核函數(shù)K（xi，xj）和懲罰參數(shù)C，構(gòu)造并求解最優(yōu)化問(wèn)題：

l l l

min 1/2∑∑yiyjαiαjK（xi，xj）- ∑αj

α i=1 j=1 j=1

l

s.t. ∑yiαi=0

i=1

0≤αi≤C，i=1，2，…，l

得最優(yōu)解α*=（α1*，α2*，…，αl*）T。

l l

計(jì)算W*=∑yiαi*xi，b*可通過(guò)滿足yj（∑αi*yiK（xi，xj）+b*）-1=0的樣本（支

i=1 i=1

持向量）求得。

解決上述問(wèn)題后可得最優(yōu)分類面函數(shù)：

l

f（x）=sgn{（W*·X）+b*}=sgn{∑yjαj*K（xi，xj）+b}

i=1

該方法能夠保證特征子集的劃分的識(shí)別效果等價(jià)于對(duì)整個(gè)樣本集。通過(guò)最優(yōu)分類面函數(shù)進(jìn)行適當(dāng)函數(shù)子集的選擇，使判別函數(shù)的識(shí)別率達(dá)到最優(yōu)，得到一個(gè)具有推廣泛化能力和最優(yōu)分類能力學(xué)習(xí)機(jī)。[3]

DTW 算法是語(yǔ)音訊號(hào)處理上經(jīng)常被使用的一種相似度估量方式，其主要的思想便是希望提供一種在時(shí)間軸上富有更大彈性的相似度對(duì)比方法。使做匹配的數(shù)據(jù)能透過(guò)在時(shí)間軸上的扭曲（ 即伸展或壓縮），找到最小誤差的非線性對(duì)應(yīng)。因?yàn)槭謩?shì)輸入在時(shí)間軸上的連續(xù)性，使得基于向量的數(shù)據(jù)很適合用該算法。DTW算法的實(shí)質(zhì)就是運(yùn)用動(dòng)態(tài)規(guī)劃的思想，利用局部最佳化的處理來(lái)尋找一條路徑使得兩個(gè)特征矢量之間的累積失真量最小，距離值的計(jì)算方法可以用歐式距離或其它距離算法實(shí)現(xiàn)，本文采用支持向量機(jī)的方法進(jìn)行分類。最后根據(jù)計(jì)算得到相似度最高的手勢(shì)即為最匹配手勢(shì)。隨后選擇路徑起點(diǎn)，利用局部路徑約束使其朝規(guī)定方向動(dòng)態(tài)規(guī)劃，累加計(jì)算距離。[1]

2 手寫口令系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

2.1 手寫口令系統(tǒng)的設(shè)計(jì)

手寫口令如果與sdcard文件中的手勢(shì)近似，則實(shí)現(xiàn)對(duì)驗(yàn)證碼模塊中下拉列表控件的監(jiān)聽(tīng)。頁(yè)面隨機(jī)顯示一幅圖片，在下拉列表中選擇提供的選項(xiàng)，如果與圖片內(nèi)容相符，則跳轉(zhuǎn)到下一頁(yè)，即登陸成功。

2.2 手寫口令系統(tǒng)的實(shí)現(xiàn)

2.2.1 手寫口令技術(shù)

（1）創(chuàng)建手勢(shì)

找到Gestures Builder的源碼，將其導(dǎo)入到workspace中，并運(yùn)行文件。需要注意的是，一定確保SD卡的存在，因?yàn)檐浖傻奈募潜４嬖赟D卡上的。

單擊“Add gesture”按鈕，可以進(jìn)入創(chuàng)建頁(yè)面，創(chuàng)建需要的手勢(shì)。在黑白區(qū)域畫(huà)出你需要使用的手勢(shì)，然后寫上名字單擊“Done”按鈕就完成了一個(gè)手勢(shì)的創(chuàng)建。

（2）創(chuàng)建應(yīng)用

創(chuàng)建好的手勢(shì)被保存在“/sdcard/gestures”里面，首先把這個(gè)文件復(fù)制到我們的應(yīng)用“/res/raw”下，我們就可以在工程里面使用這些手勢(shì)了。創(chuàng)建一個(gè)我們的應(yīng)用，首先我們要在Layout里面創(chuàng)建GestureOverlayView，它是一個(gè)透明的View，是為了用戶在上面畫(huà)出手勢(shì)而產(chǎn)生的，并且它可以疊在其他View上面。首先要加載我們的手勢(shì)文件，得到我們前面在布局文件中寫入的android.gesture.GestureOverlayView控件，用來(lái)得到用戶畫(huà)出的手勢(shì)。進(jìn)行手勢(shì)識(shí)別，得到最配對(duì)的，獲取手勢(shì)的名字，并打印。

（3）手勢(shì)應(yīng)用

運(yùn)行程序，在空白處畫(huà)出手勢(shì)，這里畫(huà)出的手勢(shì)要盡量和之前的相類似，這樣Android才能更為準(zhǔn)確的識(shí)別。當(dāng)我們?cè)谄聊簧袭?huà)出個(gè)“L”時(shí)，如果我畫(huà)出的手勢(shì)與我之前的手勢(shì)文件中的手勢(shì)比對(duì)有相同的，那么就會(huì)給出提示，打印出我創(chuàng)建時(shí)該手勢(shì)的名字。[6

2.2.2 頁(yè)面跳轉(zhuǎn)技術(shù)

當(dāng)選項(xiàng)與圖片內(nèi)容相符時(shí)，運(yùn)用頁(yè)面跳轉(zhuǎn)技術(shù)實(shí)現(xiàn)登陸頁(yè)面的跳轉(zhuǎn)，頁(yè)面跳轉(zhuǎn)的部分代碼如下：

m_Spinner.setOnItemSelectedListener（new Spinner.OnItemSelectedListener（）{

public void onItemSelected（AdapterView<？> arg0，View arg1，int arg2，long arg3）{

if（index==arg2）{

m_TextView.setText（\"圖片顯示的是：\"+m_Countries[arg2]）；

arg0.setVisibility（View.VISIBLE）；

Intent intent=new Intent（TwoActivity.this，LoginActivity.class）；

startActivity（intent）；

finish（）；}}}）；[7]

在AndroidManifest文件中添加代碼，從而實(shí)現(xiàn)頁(yè)面的跳轉(zhuǎn)。[8]

3 實(shí)驗(yàn)結(jié)果及分析

手寫口令如果與sdcard文件中的手勢(shì)近似，則通過(guò)口令認(rèn)證，頁(yè)面隨機(jī)顯示一幅圖片（圖2），在Spinner控件中對(duì)ImageButton控件隨機(jī)顯示的圖片內(nèi)容進(jìn)行選擇，如果選擇的選項(xiàng)與圖片內(nèi)容相符，則跳轉(zhuǎn)到下一頁(yè)，即登陸成功。實(shí)現(xiàn)效果如圖（圖3）：

圖2 圖3

4 總結(jié)

本文主要描述了在android平臺(tái)上對(duì)手寫口令登陸系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)，采用CAPCHA圖片驗(yàn)證碼提高系統(tǒng)的安全性。支持向量機(jī)核函數(shù)的選擇對(duì)分類器的識(shí)別性能也有影響，如何利用關(guān)于漢字的先驗(yàn)知識(shí)，選擇和設(shè)計(jì)合適的核函數(shù)，還有待進(jìn)一步的研究。[5]如何設(shè)計(jì)出更好的分類器從而有效提高手寫口令識(shí)別的準(zhǔn)確性以及系統(tǒng)的安全性將是進(jìn)一步要開(kāi)展的工作。當(dāng)前對(duì)SVM的研究方興未艾，訓(xùn)練算法的研究方向主要是確定不同的優(yōu)化目標(biāo)，根據(jù)KKT 約束優(yōu)化條件尋找大規(guī)模訓(xùn)練樣本下的實(shí)用算法；應(yīng)用方向主要是為模式識(shí)別時(shí)的多類問(wèn)題尋找好的算法和解決訓(xùn)練樣本規(guī)模和訓(xùn)練速度之間的矛盾、解決支持向量樹(shù)木和分類速度之間的矛盾。在此基礎(chǔ)上進(jìn)行進(jìn)一步的機(jī)理分析和試驗(yàn)分析，探索和拓寬SVM新的應(yīng)用領(lǐng)域，使其成為更有發(fā)展前途的新技術(shù)。[9]

參考文獻(xiàn)：

[1]馬建平，潘俊卿，陳渤.Android智能手機(jī)自適應(yīng)手勢(shì)識(shí)別方法[J].小型微型計(jì)算機(jī)系統(tǒng)，2013（07）.

[2]李秋潔，茅耀斌，王執(zhí)銓.CAPTCHA技術(shù)研究綜述[J].計(jì)算機(jī)研究與發(fā)展，2012（03）.

[3]石曼銀.一種基于SVM 向量機(jī)的手勢(shì)識(shí)別算法[J].電子測(cè)試，2013（16）.

[4]張晗，褚治廣.基于Android 平臺(tái)的手勢(shì)識(shí)別技術(shù)設(shè)計(jì)與應(yīng)用[J].遼寧工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2013（04）.

[5]高學(xué)，金連文，尹俊勛，黃建成.一種基于支持向量機(jī)的手寫漢字識(shí)別方法[J].電子學(xué)報(bào)，2002（05）.

[6]王家林.大話企業(yè)級(jí)Android應(yīng)用開(kāi)發(fā)實(shí)戰(zhàn)[M].北京：電子工業(yè)出版社.

[7]楊豐盛.Android應(yīng)用開(kāi)發(fā)揭秘[M].北京：機(jī)械工業(yè)出版社.

[8]百度經(jīng)驗(yàn)>游戲/數(shù)碼>電腦>電腦軟件[OL].http：//jingyan.baidu.com/article/851fbc370dfc603e1e15ab48.html.

[9]馬義德，齊春亮，杜鴻飛.支持向量機(jī)的研究現(xiàn)狀與進(jìn)展[OL].中國(guó)科技論文在線，2005（03）：94.

作者簡(jiǎn)介：王淞（1988.11-），山東威海人，碩士研究生，研究方向：計(jì)算機(jī)圖形學(xué)。

作者單位：北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044