东海大学资讯工程与科学系.doc

東海大學資訊工程與科學系畢業專題成果競賽基於Gabor變換與Support Vector Machines 分析實現筆跡辨識Implementation of handwriting recognition based on Gabor transform and Support Vector Machines analysis專 題 實 驗 報 告 書 學生:魏琳君 張家慈 劉嘉文 指導老師: 劉榮春中華民國 九十九 年 一 月 六 日目錄目錄2第一章 3 1.1摘要3 1.2前言與文獻回顧3第二章設計原理分析4 (一) Gabor函數 4 1.11gabor前言4 1.2濾波器設計4 1.3取樣設定4 1.4變調與多工4 1.5Gabor其他項目的運用 5 1.5.1 訊號鑑別5 1.5.2語音5 1.5.3生醫工程5 1.6Gabor介紹 5 1.7Gabor文獻探討 6 1.8影像處理/特徵抽取 7 1.9Gabor優點 8 (二) SVM 8 2.1方法介紹 8 2.2支撐向量機法 9 2.2.1支撐向量機之概述 9 2.2.2支撐向量機 10 2.3最大邊際分類器 10 2.4線性不可分割問題 13 2.5核心函數 15 2.6支撐向量機之應用 16第三章軟硬體說明 17第四章團隊分工合作方式 18第五章成果與討論 19第六章結論 27第七章參考文獻 27第一章1.1摘要 支撐向機(Support Vector Machines; SVM)在分問題上已被廣泛應用，然而面對大且複雜的資特徵，SVM 最大的問題，就是正確下和計算時間緩慢。我們可以將問題分為人在處問題的步驟之一，藉由分，可以將特徵型相似的問題歸在一起，使問題簡單化，有決策進。而現實社會中，隨著各種資的複雜及資的增加，越越多以統計學習架構為基礎的方法斷延伸，支撐向機法(Support Vector Machines)為其中一種機器學習模式。支撐向機法是一種較新的分方法，實務上，其應用的域也迅速增加，譬如醫學疾病症影像的分判或者問題結構的分等等。分析支撐向機法對於非線性資的分確程，能建構出先期檢測盜簽進詐欺的可能性，達到預測盜領詐欺為，進一步協助銀行公司行號建賠決策，以達到低盜簽詐欺犯罪率。1.2前言與文獻回顧在這資訊爆炸的時代，大量資料的產生，成為現在人們必面對的問題，故資料分析與分類是相當熱門的議題。所謂分類正確率是指分類器將一未知資料物件作正確地分類的比率；操作即時性是指分類器在操作分類時所花費的時間要儘可能地符合即時系統的要求，也就是要在儘可能短的時間內將資料物件正確地分類。由以上說明可以得知，分類正確率及操作即時性就是用來評估一個分類器優劣的最主要因素。第二章設計原理分析(一) Gabor函數1.1gabor前言與文字相關的筆跡鑑別往往指簽名鑑別。 然而某些人可以對一個簽名模仿的非常像，以至於從表面上根本無法鑑別真偽。所以現在與字跡相關的字跡鑑別往往通過一種手寫設備（手寫板之類），這種設備除了可以採集到書寫的文字字型外，還可以採集到筆跡的速度、加速度、書寫時間等，如果將這些因素融入簽名鑑別後，識別率應當是非常高的。畢竟筆跡容易模仿，但書寫的速度、加速度等很難模仿。隨著科技技術的不斷演進，各種數位影像工具越來越普遍，多媒體影像資料也不斷地增加，如何利用影像去偵測瑕疵以致於去分辨真假是很重要的，若完全以人眼去判斷事物的真假或是瑕疵，常常因為眼睛的主觀或是疲勞而造成錯誤，因此檢測圖像真假瑕疵而使用gabor濾波器進行比對，正確率也比人眼判斷來的高出很很多。1.2濾波器設計濾波器的目的就是要移除我們不要的部份，並保留我們要的部份。在沒有應用時頻分佈之前，我們只能分別在時域跟頻域上面來做過濾的動作。只能分別在時域或頻域上過濾的方式，並不適合處理每一種訊號。如果訊號在時域上或在頻域上有重疊的話，這時候使用時頻分佈函數來做分析過濾，並搭配線性完整轉換的操作，就可以做出更有效且靈活的濾波器。而在濾波器設計的應用中，時頻分佈通常處理的訊號是由很多個項所組成的，因此若用韋格納分佈來做分析的話，將會產生cross-term的問題。或許加伯轉換、加伯-韋格納分佈函數，亦或Cohens class 分佈函數會是比較好的選擇。1.3取樣設定由 Nyquist-Shannon取樣定理且 經過一番推導，我們大致上可以說一個訊號經過取樣後而不產生失真（aliasing）的最低取樣點數，會和這訊號在時頻平面上圖形的面積相等（事實上，沒有一個訊號在時頻平面上的面積有限的，因此我們省略了一些精確度）。使用時頻分析後，所需取樣的點數會比之前少了許多，因此加快了我們的運算。當我們使用韋格納分佈函數時，可能會產生cross-term；另一方面，若使用加伯轉換做分析的話，又可能會因為清晰度不佳而讓所需要取樣的面積又變大了。因此，選用哪 個函數要是訊號的情形而定，如果訊號是單一項組成的，那麼就使用韋格納分佈函數；然而，如果訊號是由多項組成的，則用加伯轉換、加伯-韋格納分佈函數，或是Cohens class 分佈函數。1.4調變與多工傳統上，調變（modulation）與 多工（multiplexing） 都只有分別在時域及頻域上下功夫，也就是盡量塞滿時域及頻域上的空間，這都是一維的操作。如果我們利用時頻分佈函數，就可以將調變與多工的觸角延伸至二維 的時頻平面上，所要做的就是塞滿整個時頻平面，做最有效的利用。但是使用韋格納分佈來分析會有嚴重的cross-term問題，這非常不利於調變與多工的作業，因此不能選擇它來做這種應用。1.5. Gabor其他項目的運用1.5.1 訊號鑑別以下兩個訊號無法經由單純的傅立葉分析分辨出來，它們的頻譜都長得一樣。 不過幸虧有時頻分佈函數，我們可以看出隨時間改變之頻率的起落，進而鑑別訊號。這個想法也可以應用至模式識別。1.5.2 語音語音訊號的特性就是它的頻率隨著時間變化的非常劇烈。因為語音訊號所涵蓋的資訊非常的多，所以相對的計算時間會是很重要的考量。很顯然，用運算複雜度較低的加伯轉換會是較好的選擇。1.5.3 生醫工程例如。我們可以用時頻分佈函數來分析肌電圖1.6Gabor介紹Gabor波器有著選擇頻及選擇方向的特性並且在空間域及頻域有著最佳的分辨。因此使用Gabor波器是有於去除需要的雜訊及保準確的ridge/valley結構。平對稱的Gabor波器產生如下：其中u0表示頻，x及y為沿著X軸及Y軸的高斯波封的空間常。Gabor波器的modulation transfer function (MTF)表示如下：其中及。Figure 3表示平對稱的Gabor波器及它的MTF。 Figure 3. An evensymmetric Gabor filter: (a) Gabor filter tuned to 60 cycles/width and orientation; (b) corresponding MTF. 01.7Gabor文獻探討在量子機制中，海森堡測不準原理指出一個質點的動量以及位置無法同時被準確地測量出來。因為海森堡測不準原理的影響，在1946年，丹尼斯加伯（Dennis Gabor）這位在1971諾貝爾物理獎得主首次發現在信號處理的過程中，時頻分析的重要性，隨後他便提出了windowed Fourier transform 去找出聲波頻率的確切位置。根據海森堡測不準原理，一個訊號的能量散佈以及它的傅立葉轉換不能同時被測量出來。Gabor發現到一個由同一族群的波形所構成的訊號對於時間和頻率有非常好的集中性，而Gabor稱這些基本的波形為時頻原子（time-frequency atoms），它在時頻平面上有最小的分佈。事實上，Gabor用公式表示出如何將一個訊號分解成簡單的波形，他這個開創性的想法變成現今時頻分析的標準模型。為了要同時將時間和頻率的局部性，只用一個轉換方程式求出，Gabor引用了Gabor transform(或是windowed Forier transform)，他的主要想法是使用一個局部時間的窗函數（window function），ga(t b)去找出傅立葉轉換中的局部資訊 ，而參數a代表window的寬度，參數b被用來轉化window為了要包含全部的時間區域。這個想法是用window局部地找出傅立葉轉換的性質。事實上，Gabor用 當作是window function，這裡，而Gabor transform 用 來表示，定義為這裡 ，在實際上的應用f和g代表訊號是有限能量的。在量子系統中，代表的是f的標準相干狀態，相干狀態首次被Gabor所提出在量子光學部份，而Gabor transform的反變換為賈柏轉換法（Gabor transform）是由一個繁複的非線性方程式所構成，在轉換式裡包含三個參數，頻率（frequency），相角（orientation），及帶寬（bandwidth），將轉換法定義如下：， 為一複數，可寫為包含實部：虛部：接著以賈柏函數G ,（x,y）對影像 f（x,y）做旋積，其表示法如下:G(x,y)實部部份：G(x,y)虛部部份：其中 k 決定Gabor filter之視窗大小為MM， M = 2k+1。1.8影像處理/特徵抽取：使用gabor濾波器濾除了影像中不必要的訊號，只保留字跡的文理特徵，並把特徵區域強化，更加明顯的顯示出來。 1.9 Gabor優點：1) 濾波器能被設計成在顯示好的空間區域頻率的描述，而且有較高的選擇性。 2) 在空間域和頻率域中有最佳局部化的功能。以()()二圖為例，將字跡特別圈出的部份強化Gabor的方程式在此，定義如下：而所代表的是一個頻率的值，方程式如下：在上個方程式(3)中，方程式(2)中，將是被定義如下：有兩個變數和，代表角度的變換。 k 決定Gabor filter之視窗大小為MM， M = 2k+1。(二) SVM2.1.方法介紹：何謂SVM (Support Vector Machine)SVM, Support Vector Machine , 簡而言之它是個起源跟類神經網路有點像的東西，不過現今最常拿來就是做分類(classification)。也就是說，如果我有一堆已經分好類的東西（可是分類的依據是未知的！），那當收到新的東西時， SVM可以預測(predict) 新的資料要分到哪一堆去。 2.2.支撐向機法（Support Vector Machine）支撐向機法(Support Vector Machine；SVM)是學者Vapnik 和Cortes在1995所提出，以統計學習為基礎，建構分(Classification)和迴歸(Regression)的演算法。由於SVM 對於資分的正確比其他分演算法的好，因此近在處資分問題上有很廣泛的應用。2.2.1.支撐向機之概述SVM 是一個在高維特徵空間的線性學習系統，而其演算法是從最佳及統計學習而得的。在分的概中，SVM 的主要概是建構一個最佳的超平面作為分決策的界面，透過此介面能有效分Positive example和Negative example。從SVM簡單的型看，如圖2.1，代表為正（Positive example），代表為負（Negative example）。在子中，我們可以直接以線性超平面去分割這些資，但是在現實生活中，大部分的資型態所待解決的問題，多於非線性的問題，無法以簡單線性去分割，如圖2.2，面對非線性資結構，SVM 往往能顯現其優越的分效果。對於分問題，SVM 之方法是透過資的學習，建構出一條最佳線性決策函及找出最接近此函的點，稱為支撐向(Support Vector)，在難以線性分割的資中，藉由建構出一條最佳線性決策函(Linear Decision Function)，轉換到特徵空間，讓原本線性可分割的資變為線性可分割，之後在特徵空間中，使得資可被分為，如圖2.3 所示。之後可用此線性決策函及支援向分模式預測新的未知資，以進分。2.2.2 支撐向機對於二別分問題，SVM 主要是透過資的學習，建構出一條最佳超平面進分。假設給定一組訓資：S=(x1,y1),(x1,y1)其中xiRn且yi -1,1，i=1,l，我們考慮超平面(Hyperplane) 函f : XRn Ry = f(x)= wx+b (0.1)其中向w Rn 為權重向(Weight Vector)，bR為偏差值(Bias)。根據(0.1)式，決策函可表示為sgn(f(x) 。輸入資x經函計算後，當sgn(f(x)=1，則可將此資判定成正集，當sgn(f(x)= 1，則判定成負集。以下將介紹SVM 基本，包括最大邊際分器、線性可分割問題、核心函和介紹SVM 的實際應用。2.3 最大邊際分器(The Maximal Margin Classifier)SVM 最簡單的模式：最大邊際分器(The Maximal Margin Classifier)，最大邊際分器只作用在資為線性可分割時，因此對於現實生活較適用，但最大邊際分器是最容解的演算法，而且也是形成複雜支撐向機的基礎。對於二別問題，假設存在(w,b)，訓資集合S 滿足等式 則資集合S 稱為線性可分割，(0.2)也可表示成yi(wxi+b) 1, i=1,., l。對於線性可分割的資集合，可建構出一條最佳超平面，使得別訓資與超平面間的距達最大，如圖2-2：別資與超平面間的最近距，我們稱為邊際(margin)，以 表示， 的公式如下： 其中 x+與 x分別代表正集與負集的資。所以建構最佳超平面即為找邊際= 1/|w|2 的最大化。因此最佳超平面可用下最佳化問題求得：minimisew,bwwsubject to yi(wxi+b) 1 i=1,l最佳化問題可藉由氏函(Lagrangian Function) 轉變成氏對偶問題(Lagrangian Dual Problem)，以求得各及目標函之最佳解。氏函為：則可以得到： 由(0.5)可知，最佳超平面中氏乘i會滿足：所求出的 可代入權重向量w* yiai*xi，可推得最大邊際= 1/|w|2而偏差值b*用原先最小化問題的限制式求得：由Kuhn-Tucker 定可知，SVM 最佳化問題的解a*、w*、b*必會滿足下面條件：ai*yi(w*xi+b*)-1=0,i=1,l此條件稱 Kuhn-Tucker Complementarity Conditions，表示當輸入資xi所對應的ai*0，則 yi(w*xi+b*)=1，代表資料x最接近最佳超平面，稱為支撐向，簡寫成SV。而其他資所對應的ai*= 0。根據上述最佳化問題所求出的解，最佳超平面f (x) =w* x + b*可改寫為：由上式可知，建構最佳超平面為資和所有支撐向的內積(Inner Product)，而決策函也可改成sgn(f(x;a*,b*)。2.4 線性可分割問題(Linearly Non-separable Case)當訓資集合S 為線性可分割，如圖2-3，則導入寬鬆變(Slack Variables) 0，等式(0.2)修正為：yi(w*xi+ b ) 1-i i=1,l當資料xi滿足(0.2)時，則對應到上式之i 0，也就是，當訓資在分發生錯誤時，i就會大於，因此在求最佳超平面時，希望邊際愈大愈好且i愈小愈好。用此概，線性可分割之最佳超平面可用下最佳化問題求得：其中C 為常，代表發生錯誤的成本。當C 越大表示錯誤發生時對目標函的影響越大，反之影響越小，當C 時，線性可分割問題會退化(Degeneration)成線性可分割問題。似於線性可分割的方法，最佳化問題可轉換成氏對偶問題：而對於最佳化問題的解也會滿足 Kuhn-Tucker Complementarity Conditions：當資料xi所對應的ai*0稱為支撐向，但對於線性可分割問題，支撐向有種，一種是當0 ai* n，使得輸入空間中的資轉換到特徵空間：F = (x) | x X RN讓原本線性可分割資，在高維的特徵空間中能建構出最佳超平面進分。因此在特徵空間中，最佳超平面可用下最佳化問題求得：對於所有xi，xjX Rn，我們定義核心函：K(xi，xj)=(xi)(xj)考慮一矩陣K=( K(xi，xj)=1) ，其中K(xi，xj) 為對稱的(Symmetric)核心函，由Mercers 定可知，矩陣K 為半正定(Positive Semi-definite)矩陣。而(0.6)式可改寫成：由上式可知，將原始資轉換到特徵空間最後會影響結果的是K(xi，xj) ，所以並需要知道(x)為何種函。學者 B Riberio整許多其他學者所提出的核心函，其中最常的核心函有下三種：1) Polynomial Kernel with Degree dK(xi，xj)（xi，xj+）d2) Radial Basis Function (RBF)K(xi，xj)exp(-|xi-xj|d)3) Multi-Layer Perceptron (Sigmoid)K(xi，xj)=tanh(xixj-)最後，由上述可知，最佳超平面可改寫成：而決策函為sgn(f(x) 。2.6 支撐向機法之應用支撐向機法對於樣本分能相當錯，也廣泛應用於文件分、影像辨、手寫字辨及生化科技方面域：1) 文件分(Text Categorization)文件分就是以內容為分基礎，將原始文件分到預先定義好的別中。文件分可應用在同域，如電子郵件過、網頁搜尋、辦公室自動化和以主題排序文件的功能等。一個文件可被指派到只一個別中，而且在一個別中，是屬於多別問題，而是屬於一二元別問題，SVM 就是有效的分工具之一。2) 影像辨(Image Recognition)近位影像在網上或專門資庫中可隨意取得，且很容產生影像資。影像的自動分在許多域中是重要的工作之一，如資擷取、網資過、醫藥應用、光學影像中物體偵測等。影像分著重於從高維下擷取影像特徵，而傳統的分方法對於高維的影像擷取效果較差，但SVM 可以避免此問題。3) 手寫字辨(Hand-written Digit Recognition)最先應用在 SVM 上的實際問題就是手寫字辨，由學者Vapnik 和其工作團隊所研究，主要動機在於美國郵局部門(USPS)要自動化排序手寫郵遞區號。而實驗結果發現，同的核心函對於手寫字辨問題有相同的效果，而且效果比其他分演算法(如決策樹、層經網等)的好。4) 生物資訊(Bioinformatics)蛋白質是由一的胺基酸所組成，在生物資訊學中，存在千種同的蛋白質。而主要問題之一就是：要以胺基酸序為基礎，預測蛋白質的結構與特徵，也就是尋找新蛋白質和已知蛋白質性質間的相關性，當具有同質性(Homology)的蛋白質會被指派在同一，因此透過SVM，可以解決生物資訊上的分問題。三、軟硬體系統說明轉成黑白二值可以更精確的抓到字跡，當開始掃瞄簽名時不會有其他的顏色干擾，只會有單純的黑白兩色作判斷。而傾斜校正是因為可能在簽名的時候，不會正常水平的簽名，有可能斜的簽名，這時就需要去作調整。對紋理圖像進行Gabor變換，Gabor變換屬於加窗傅立葉變換，Gabor函數可以在頻域不同尺度、不同方向上提取相關的特徵。另外Gabor函數與人眼的生物作用相仿，所以經常用作紋理識別上，並取得了較好的效果。利用SVM進行分類，首先對Gabor變換結果進行處理，生成符合SVM處理規範的文本格式。使用SVM分類可以執行libsvm-2.9tools目錄下的easy.py程序，該程序提供了一套默認的、精度較高的SVM分類算法。該實驗在以下的環境中執行：CPU: Genuine Intel(R) CPU T2050 1.60GHzRAM: DDR II 800 2GBOS: Microsoft Windows XP SP3SVM tool: LibSVM 2.9 四、團隊分工合作方式一開始指導教授給的資料中有關於SVM分析的相關資料，不過是做關於網路攻擊的分析。接下來開始思考有什麼也可以利用SVM來分析，結果想到現在網路金融的興盛之下，突顯了安全性的問題，如果能在交易過程中加入簽名的話，安全性必然能大大的提高。所以該如何分析字跡的符合率就成了這次專題的目標。但是該如何擷取資料就是一個相當重要的問題，如果單純抓取RGB值勢必會破壞或者是在有多筆劃的字跡中，會變得難以分辨。之後找到Gabor函數，可以很快速明確抓出特徵圖，不會因為額外的動作而無法辨識出來。所以就朝三個方向研究，第一是Gabor函數是如何操作，原理是什麼，這部份是由魏琳君負責。第二是如何使用SVM的工具，讀的格式是如何產生、如何去分析，這部份由張家慈負責。第三是實作程式範例，從讀入圖片加以Gabor函數轉換、並以SVM來作分析，這部份由劉嘉文負責。五、成果與討論如果只是單純的掃描出有簽名的RGB值，再下去依照相對位置判斷，如此一來準確率會變得相當低。所以使用了Gabor變換後，就會有明顯的特徵圖顯示出來，以下是取出特徵圖的案例。範例一這是原始簽名圖新增額外筆劃-1新增額外筆劃-2破壞簽名圖-1（破壞接近50）破壞簽名圖-2（破壞25）非本人簽名圖-1非本人簽名圖-2使用