摘 要:本文主要描述了在android平臺上對手寫口令登陸系統(tǒng)的設計與實現,采用CAPTCHA圖片驗證碼提高系統(tǒng)的安全性。
關鍵詞:Android;手寫口令;CAPTCHA驗證碼;支持向量機
中圖分類號:TP391.41
目前主要的手勢識別技術有:模板匹配技術、神經網絡技術以及統(tǒng)計分析技術等。
模板匹配技術需要預先儲存手勢模板,將經傳感器輸入的手勢與模板手勢進行匹配,通過一定的算法計算手勢之間的相似度來進行識別;神經網絡技術中廣泛使用的BP神經網絡技術是一種俺誤差逆?zhèn)鞑ニ惴ㄓ柧毜亩鄬忧梆伨W絡,能夠學習和存儲大量的輸入-輸出模式映射關系,而無需事前解釋描述這種映射關系的數學方程。它的學習規(guī)則是使用最快速下降法,通過反向傳播來不斷調整網絡的權值和閾值,使網絡的誤差平方和最小;統(tǒng)計分析技術,例如:統(tǒng)計模式識別,就是用給定的有限數量的樣本集,在已知研究對象統(tǒng)計模型或已知判別函數類條件下根據一定的準則通過學習算法把d維特征空間劃分為c個區(qū)域,每一個區(qū)域與每一個類別對應。模式識別系統(tǒng)在進行工作時只要判斷被識別的對象落在哪一個區(qū)域,就能確定出它所屬的類別。[1]
隨著互聯網的普及,各種網絡服務日益成為人們日常生活的一部分,如免費的電子郵箱服務、在線投票及推薦系統(tǒng)、網絡聊天室等等。這些面向人類用戶的服務時常被一些惡意計算機程序濫用,它們占用服務資源,產生大量的網絡垃圾,影響用戶的網絡體驗,對網絡服務的安全性造成極大威脅。應運而生的全自動開放式人機區(qū)分圖靈測試CAPTCHA是解決此類網絡安全問題的一種機制,即通常所說的“驗證碼”技術。根據不同的表現載體和內容,CAPTCHA分為文本、圖像和聲音3種類型。[2]
Android手寫口令采用的是模板匹配技術,為了提高口令識別的準確性和系統(tǒng)的安全性,本文采用支持向量機與模板匹配相結合的方法以及CAPTCHA圖片驗證碼實現登陸系統(tǒng)。
1 原理
Android 手勢識別采用的是模板匹配技術。[1]主要包括手勢圖像的獲取,提取后圖像的預處理(包括灰度化和二值化處理),圖像幾何矩的提取,SVM模型的訓練以及最后的匹對。[3]
1.1 手勢圖像的獲取
首先要定義一個手勢并獲取其特征數據,再將其數據存儲起來等待比對。要在屏幕上畫出一個圖形,并獲取該圖形數據,將圖形數據轉化為特征值數據,并為圖形數據定義出一個系統(tǒng)名稱標識存儲到指定的“手勢倉庫”中。[4]
簡單的手勢能夠通過有方向和大小向量來構造。輸入手勢的每一個點代表觸屏設備識別到的觸屏點,并根據錄入的順序依次儲存在點數組里。隨后對手勢點數組進行遍歷,求出相鄰點的方向,方向由前面的點指向后面的點,將方向值轉換為與圖1最相近的方向值,并存為方向數組。 對方向數組中連續(xù)的相同方向上點進行合并,計算連續(xù)方向點的距離同時將距離過短的向量作為噪點去除。[1]
圖1
1.2 SVM 模型的訓練以及最后的匹對
漢字識別一直是模式識別最重要的研究領域之一。經過多年的研究,已經取得了大量成果。但是,無約束的非特定人手寫漢字識別仍然被認為是文字識別領域最困難的問題之一,其原因可以歸結為:(1)漢字規(guī)模大(2)相似漢字較多,且有些相似字差別極其細微(3)存在大量的不規(guī)則書寫變形。由于(2)、(3)的存在,導致手寫漢字,特別是相似字在特征空間中的距離變小,使得普通的距離分類器的推廣能力變弱。因此,如何補償手寫漢字的書寫變形,提高分類器的泛化和推廣能力,就成為漢字識別研究的關鍵問題之一。
支持向量機是ATTBell實驗室的V.Vapnik等人根據統(tǒng)計學習理論提出的一種新的機器學習方法,已經在模式識別、回歸分析和特征選擇等方面得到了較好的效果。支持向量機可以看作一種新的訓練多項式、徑向基分類器或神經網絡分類器的方法。根據結構風險最小化準則,在使訓練樣本分類誤差極小化的前提下,盡量提高分類器的泛化推廣能力。從實施的角度,訓練支持向量機等價于解一個線性約束的二次規(guī)劃問題,使得分隔特征空間中兩類模式點的兩個超平面之間距離最大,而且它能保證得到的解為全局最優(yōu)點,使得基于支持向量機的手寫漢字分類器能夠吸收書寫的變形,從而具有較好的泛化和推廣能力。[5]
支持向量機可以有效提高手寫口令識別的準確度,以下為分類器的具體實現:
1.2.1 計算特征手勢
設手勢圖像f(x,y)為二維n×m灰度圖像,用nm維向量R表示。手勢圖像訓練集為{Ri|i=1,2,…,p},其中p為訓練集中圖像總數。這p幅圖像的平均向量為:
_ p
R=1/p∑Ri
i=1
對訓練樣本規(guī)范化,即每個手勢Ri與平均手勢R的差值向量:
_
Ai=Ri-R i=1,2,…,p
其中列向量Ai表示一個訓練樣本。
訓練圖像由協(xié)方差矩陣可表示為:
C=AAT
其中訓練樣本nm×p維矩陣A=[A1,A2,…,Ap]
特征手勢由協(xié)方差矩陣C的正交特征向量組成。對于nm維手勢圖像,協(xié)方差矩陣C的大小為nm×nm,對它求解特征值和特征向量是很困難的,由此引入奇異值分解定理來解決維數過高的問題。
1.2.2 奇異值分解定理
由奇異值分解定理可以得到一個推論:
U=A∨∧1/2
由協(xié)方差矩陣C=AAT,構造矩陣:L=ATA∈Rp×p,容易求出其特征值及相應的正交歸一特征向量vi(i=1,2,…,p)。由以上述推論可知,C的正交歸一特征向量ui為:
ui=1/Avi i=1,2,…,p
這就是圖像的特征向量,它是計算p×p低維矩陣L的特征值和特征向量而間接求出來的。實際上l(l﹤p)個特征值足夠用于手勢識別。因此僅取L的前l(fā)個最大特征值的特征向量計算特征手勢。
1.2.3 特征向量的選取
以上總共得到了p(訓練樣本數目)個特征向量。雖然p 比nm小很多。但通常情況下,p 仍然會太大。根據應用的要求,并不是所有的ui都有很大的保留意義。
考慮到使用K-L變換作為對手勢圖像的壓縮手段,可以選取最大的前l(fā)個特征向量,使得:
l p
∑λi/∑λi≥α
i=1 i=1
在實際中,可以選擇α=0.90,或者自定義的其他值。這說明樣本集在前l(fā)個軸上的能量占到整個能量的90%以上。
1.2.4 基于特征手勢的手勢識別
接下來對特征手勢進行手勢劃分,通過訓練集優(yōu)化得到最優(yōu)解。已知訓練集
T={(x1,y1),(x2,y2),…,(xl,yl)∈(X,Y)l,其中xi∈X =R0,yi∈Y∈{-1,1},i=1,2,…,l。
然后,選擇核函數K(xi,xj)和懲罰參數C,構造并求解最優(yōu)化問題:
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
計算W*=∑yiαi*xi,b*可通過滿足yj(∑αi*yiK(xi,xj)+b*)-1=0的樣本(支
i=1 i=1
持向量)求得。
解決上述問題后可得最優(yōu)分類面函數:
l
f(x)=sgn{(W*·X)+b*}=sgn{∑yjαj*K(xi,xj)+b}
i=1
該方法能夠保證特征子集的劃分的識別效果等價于對整個樣本集。通過最優(yōu)分類面函數進行適當函數子集的選擇,使判別函數的識別率達到最優(yōu),得到一個具有推廣泛化能力和最優(yōu)分類能力學習機。[3]
DTW 算法是語音訊號處理上經常被使用的一種相似度估量方式,其主要的思想便是希望提供一種在時間軸上富有更大彈性的相似度對比方法。使做匹配的數據能透過在時間軸上的扭曲( 即伸展或壓縮),找到最小誤差的非線性對應。因為手勢輸入在時間軸上的連續(xù)性,使得基于向量的數據很適合用該算法。DTW算法的實質就是運用動態(tài)規(guī)劃的思想,利用局部最佳化的處理來尋找一條路徑使得兩個特征矢量之間的累積失真量最小,距離值的計算方法可以用歐式距離或其它距離算法實現,本文采用支持向量機的方法進行分類。最后根據計算得到相似度最高的手勢即為最匹配手勢。隨后選擇路徑起點,利用局部路徑約束使其朝規(guī)定方向動態(tài)規(guī)劃,累加計算距離。[1]
2 手寫口令系統(tǒng)的設計與實現
2.1 手寫口令系統(tǒng)的設計
手寫口令如果與sdcard文件中的手勢近似,則實現對驗證碼模塊中下拉列表控件的監(jiān)聽。頁面隨機顯示一幅圖片,在下拉列表中選擇提供的選項,如果與圖片內容相符,則跳轉到下一頁,即登陸成功。
2.2 手寫口令系統(tǒng)的實現
2.2.1 手寫口令技術
(1)創(chuàng)建手勢
找到Gestures Builder的源碼,將其導入到workspace中,并運行文件。需要注意的是,一定確保SD卡的存在,因為軟件生成的文件是保存在SD卡上的。
單擊“Add gesture”按鈕,可以進入創(chuàng)建頁面,創(chuàng)建需要的手勢。在黑白區(qū)域畫出你需要使用的手勢,然后寫上名字單擊“Done”按鈕就完成了一個手勢的創(chuàng)建。
(2)創(chuàng)建應用
創(chuàng)建好的手勢被保存在“/sdcard/gestures”里面,首先把這個文件復制到我們的應用“/res/raw”下,我們就可以在工程里面使用這些手勢了。創(chuàng)建一個我們的應用,首先我們要在Layout里面創(chuàng)建GestureOverlayView,它是一個透明的View,是為了用戶在上面畫出手勢而產生的,并且它可以疊在其他View上面。首先要加載我們的手勢文件,得到我們前面在布局文件中寫入的android.gesture.GestureOverlayView控件,用來得到用戶畫出的手勢。進行手勢識別,得到最配對的,獲取手勢的名字,并打印。
(3)手勢應用
運行程序,在空白處畫出手勢,這里畫出的手勢要盡量和之前的相類似,這樣Android才能更為準確的識別。當我們在屏幕上畫出個“L”時,如果我畫出的手勢與我之前的手勢文件中的手勢比對有相同的,那么就會給出提示,打印出我創(chuàng)建時該手勢的名字。[6
2.2.2 頁面跳轉技術
當選項與圖片內容相符時,運用頁面跳轉技術實現登陸頁面的跳轉,頁面跳轉的部分代碼如下:
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文件中添加代碼,從而實現頁面的跳轉。[8]
3 實驗結果及分析
手寫口令如果與sdcard文件中的手勢近似,則通過口令認證,頁面隨機顯示一幅圖片(圖2),在Spinner控件中對ImageButton控件隨機顯示的圖片內容進行選擇,如果選擇的選項與圖片內容相符,則跳轉到下一頁,即登陸成功。實現效果如圖(圖3):
圖2 圖3
4 總結
本文主要描述了在android平臺上對手寫口令登陸系統(tǒng)的設計與實現,采用CAPCHA圖片驗證碼提高系統(tǒng)的安全性。支持向量機核函數的選擇對分類器的識別性能也有影響,如何利用關于漢字的先驗知識,選擇和設計合適的核函數,還有待進一步的研究。[5]如何設計出更好的分類器從而有效提高手寫口令識別的準確性以及系統(tǒng)的安全性將是進一步要開展的工作。當前對SVM的研究方興未艾,訓練算法的研究方向主要是確定不同的優(yōu)化目標,根據KKT 約束優(yōu)化條件尋找大規(guī)模訓練樣本下的實用算法;應用方向主要是為模式識別時的多類問題尋找好的算法和解決訓練樣本規(guī)模和訓練速度之間的矛盾、解決支持向量樹木和分類速度之間的矛盾。在此基礎上進行進一步的機理分析和試驗分析,探索和拓寬SVM新的應用領域,使其成為更有發(fā)展前途的新技術。[9]
參考文獻:
[1]馬建平,潘俊卿,陳渤.Android智能手機自適應手勢識別方法[J].小型微型計算機系統(tǒng),2013(07).
[2]李秋潔,茅耀斌,王執(zhí)銓.CAPTCHA技術研究綜述[J].計算機研究與發(fā)展,2012(03).
[3]石曼銀.一種基于SVM 向量機的手勢識別算法[J].電子測試,2013(16).
[4]張晗,褚治廣.基于Android 平臺的手勢識別技術設計與應用[J].遼寧工業(yè)大學學報(自然科學版),2013(04).
[5]高學,金連文,尹俊勛,黃建成.一種基于支持向量機的手寫漢字識別方法[J].電子學報,2002(05).
[6]王家林.大話企業(yè)級Android應用開發(fā)實戰(zhàn)[M].北京:電子工業(yè)出版社.
[7]楊豐盛.Android應用開發(fā)揭秘[M].北京:機械工業(yè)出版社.
[8]百度經驗>游戲/數碼>電腦>電腦軟件[OL].http://jingyan.baidu.com/article/851fbc370dfc603e1e15ab48.html.
[9]馬義德,齊春亮,杜鴻飛.支持向量機的研究現狀與進展[OL].中國科技論文在線,2005(03):94.
作者簡介:王淞(1988.11-),山東威海人,碩士研究生,研究方向:計算機圖形學。
作者單位:北京交通大學 計算機與信息技術學院,北京 100044