基于改進的加權向量機的假幣識別算法

林樹青 李蓉

摘 要： 支持向量機在處理樣本類別不平衡時，對樣本數(shù)量少的類別，其分類誤差大，針對這一問題提出了一種多核心的加權向量機。將紙幣的RGB色彩空間轉換到YIQ色彩空間，使用直方圖對樣本進行特征的提取。在特征空間使用邊界區(qū)間處理分類問題，加入最小化小樣本誤識率的機制，使用一種改進的加權支持向量機來識別樣本。對樣本的不同區(qū)域使用不同的核函數(shù)。實驗表明本算法可行、可靠。

關鍵詞： 多核學習； 加權支持向量機； 紙幣識別； 懲罰因子； 加權值

中圖分類號：TP391 文獻標志碼：A 文章編號：1006-8228（2013）02-34-04

Recognition of counterfeit money based on improved weighted support vector machines

Lin Shuqing， Li Rong

（ZengCheng college of South China Normal University， Guangzhou， Guangdong 511363， China）

Abstract： To deal with the unbalanced problem in classification， a multi-kernel Support Vector Machines is presented in this paper. RGB color space of note is transformed to the YIQ color space and the characteristics are extracted by using histogram. The classification problem is dealt with by using the boundary interval in eigen-space， and an improved weighted support vector machines are added to minimize the false alarm rate of the small sample. The different kernel functions are used in different regions of the sample. Simulation results show that this algorithm is feasible and reliable.

Key words： multi-kernel learning； weighted support vector machines； recognition of the paper money； penalty factors； weighted value

0 引言

紙幣的防偽技術是世界各國金融系統(tǒng)所面臨的十分重要又棘手問題。目前主要依靠全息磁性安全線磁碼、紫外光、紅外投射檢偽。但在高端產品中僅靠以上技術識偽是不夠的，特別是現(xiàn)在很多是使用清分機對高仿紙幣的識別。因此國外很多學者不斷地研究探索智能識別系統(tǒng)，如Takeda等人利用神經網絡系統(tǒng)去分析、識別紙幣的特征信號[1，2]；Omatu等人利用遺傳算法分析、識別紙幣的特征信號[3]；He等人將紙幣切割成m×n個等分區(qū)域，使用GA算法進行識別[4]；近年來Jae-Kang等人[5]和Ahmadi等人[6]也進行了相應的研究。

本文使用多核心加權向量機來識別紙幣，將紙幣圖像分割成m×n個區(qū)域，然后使用改進的加權向量機進行識別。對每個區(qū)域構建多核心的核矩陣。實驗結果證明該算法的計算精確度高，魯棒性好。

1 特征提取

假鈔與真鈔的顏色對假幣識別用處不大，針對假鈔與真鈔在色度分布上的差異，我們將RGB色彩空間轉換到YIQ色彩空間。其關系方程式為：

⑴

其中Y分量代表圖像的亮度信息，即圖像的灰度值（Gray value），人民幣圖像的每一個像素以一個位元組表示其Y值。

為了降低輸入樣本的維度，我們把樣本圖像轉換成直方圖。以百元人民幣為例。假幣使用編號HD90系列。由于取整張鈔票圖像來識別容易損失個別區(qū)域的不同圖像特征所反映在色度分布上的信息，于是我們將鈔票分割成m×n個區(qū)域，如圖1所示。

圖1 分割成3×2方式的百元真幣

再將每個區(qū)域轉換成Y值的直方圖作為特征。結果一張鈔票圖像分為m×n個256維度的樣本。分割后真、假人民幣的直方圖分別如圖2、圖3所示。

（a） （b）

（c） （d）

（e） （f）

圖2 切割成3×2方式百元真人民幣直方圖

（a） （b）

（c） （d）

（e） （f）

圖3 切割成3×2方式的百元假人民幣直方圖

2 加權支持向量機

2.1 C-SVM模型

C-SVM原始問題的數(shù)學描述為：

⑵

ω是超平面的法向量，b是超平面偏值，C是懲罰參數(shù)，為松弛變量。xi∈Xl為訓練點，yi∈{-1，1}為每個訓練點的正確分類。當訓練集為非線性時，通過一個非線性映射φ（xi）把訓練數(shù)據(jù)xi映射到一個高維線性特征空間。

利用Lagrange優(yōu)化方法可得到其對偶問題：

⑶

⑷

ai為拉格朗日乘子。最優(yōu)化求解ai中，只有ai≠0所對應的訓練樣本稱為支持向量。ai=C所對應的xi稱為邊界支持向量，實際上是錯分的訓練樣本點。分類函數(shù)為：

⑸

用NBSV+、NBSV-分別表示正類的邊界支持向量數(shù)、負類的邊界支持向量數(shù)，用NSV+、NSV-分別表示正類總的支持向量數(shù)、負類總的支持向量數(shù)，用l+、l-分別表示正、負類別樣本數(shù)目。

由約束式⑷通過變換[7]可得到：

⑹

其中：。

從上式可看出，如果兩類別樣本數(shù)目不等，即l+≠l-，則對于樣本數(shù)目大的類別，其錯誤分類率小，對樣本數(shù)目小的類別，其錯誤分類率大。事實上我們在人民幣識別時真鈔的數(shù)量遠遠大于假鈔數(shù)量。因此，我們對C-SVM加以改進，使樣本數(shù)目小的類別，其錯誤分類率小。

2.2 改進的加權支持向量機

對于相同樣本，一種情況是將其中一張真鈔誤識為假鈔，其余都正確，另一種將其中一張假鈔誤識為真鈔，其余識別都正確，雖兩種情況的識別率相同，但造成的結果完全不同。

在一般情況下，學習機對所有的訓練樣本是一視同仁的，最佳的超平面與正類別及負類別具有相同大小的邊界。我們重點考慮的不是把真鈔誤識為假鈔，而是把假鈔誤識為真鈔的問題。希望能將假鈔被誤識為真鈔的可能性降至最小。

先把訓練樣本的真鈔標識為正類別，假鈔標識為負類別。通過調高假鈔被分類錯誤是的懲罰值，讓最佳的超平面往正的類別靠近，希望負類別的區(qū)間大于正類別的區(qū)間，降低假鈔被誤判為真鈔的機率。提出了一種改進的加權向量機：

⑺

其中：c為常數(shù)，l+為真鈔的數(shù)量，l-為假鈔的數(shù)量，βi為對各樣本的加權，滿足0≤βi≤1，對要舍去的樣本點，其權值取接近為零的數(shù)，而最重要的樣本點，其權值取為1，這樣就可以克服算法對各類別樣本數(shù)不均衡引起的缺陷。φ（xi）為樣本的特征映射函數(shù)。

在假鈔識別時l+>l-（遠遠大于），所以負類別的懲罰參數(shù)大于正類別。當正負類別的樣本數(shù)差異越大時，樣本數(shù)少的類別會受到更大的懲罰值。

其對偶問題如下：

⑻

寫成矩陣的表示方式：

⑼

其中，，

G（K）=diag（y）Kdiag（y）是一個半正定矩陣。分類判別函數(shù)為：

（10）

使用與C-SVM算法相同的分析方法，可得到下式：

（11）

在假幣識別時，設真幣（正類）βi=β+，假幣（負類）βi=β-。則上面不等式可寫成：

（12）

我們希望能將假鈔被誤識為真鈔的可能性降至最小，也就是要求將樣本數(shù)目小的類別的錯誤分類率降至最低。因此我們令：，即：

（13）

這種方法以犧牲總樣本的精度為代價來提高小樣本類的精度。在人民幣識別中，實際上當使用驗鈔機檢驗錢時通常驗鈔機檢測出問題鈔票之后會由人工再進行檢查。所以對最終的結果影響不大。

圖4顯示了當正類別樣本與負類別樣本的數(shù)量比例為6：1時決策邊界的變化，由于我們的方法強調負類別樣本的懲罰值，使得負類別仍然可以保持較大的區(qū)間而不容易受到正類別樣本數(shù)量增加的影響。但必須犧牲的是，正類別樣本被錯誤分類的數(shù)量也可能會增加。

圖4 本文算法與C-SVM在樣本數(shù)量不同時決

3 核函數(shù)的選取

應用SVM過程中所面臨的一個問題是如何確定其分類訓練參數(shù)。使用不同類型的核函數(shù)、不同的核函數(shù)參數(shù)、不同的誤差參數(shù)都會影響到最終的識別結果。核函數(shù)類型的選取目前仍然依賴經驗。本文采用了一種多核方法[8，9]。

使用樣本來訓練多核支持向量機，鈔票圖像分割成m×n區(qū)域，每個區(qū)域的特征用來訓練出一組核矩陣，其中每組核矩陣為M核矩陣的線性組合，個別的核矩陣是由對應區(qū)域的圖像特征經過不同的核心函數(shù)的內積構成。形式如下：

（14）

s.t. trace（K）=c=M×l， Ki?0， μj≥0

μ1，…，μM×m×n為每塊的權重，l為樣本數(shù)量。在半定規(guī)劃搜索最佳的μ1，…，μM×m×n組合，μ值越高的區(qū)域表示其用來識別真假的鑒別能力越高。因我們不知道哪個區(qū)域的鑒別能力較高，而不同區(qū)域的圖像特征分布情況也不一樣。所以每個區(qū)域塊給出M個核心函數(shù)。核心函數(shù)使用RBF函數(shù)，表達式為k（xi，x）=。

4 實驗結果與分析

為了驗證本算法的可行性及優(yōu)越性，我們選用2005年版的百元幣，假幣選用市面上仿真度高的HD90系列。其中訓練樣本為400張真幣及10張假幣。實驗中取C=1。為了數(shù)據(jù)的準確性，我們對每組實驗進行10次，結果取平均數(shù)，F(xiàn)P為把假鈔識別為真鈔的數(shù)量，F(xiàn)N為把真鈔識別為假幣的數(shù)量。

我們定義識別率為：

（15）

其中：TP（truce positive）為真鈔被識別為真鈔的數(shù)量、TN（true negative）為假鈔被識為假鈔的數(shù)量、l+為真鈔的數(shù)量，l-為假鈔的數(shù)量。

表1是使用5個RBF核心的結果，σ-2分別為0.01，0.05，0.1，0.5，1。從表1可發(fā)現(xiàn)3×2的分割方式的效果比其他方式好，可以用來識別假幣。這時百元紙幣的核心函數(shù)的權重分布為μ1=0，μ2=0.020，μ3=0.119，μ4=0.304，μ5=0.105，μ6=0.452。

表1 切割方式與5個RBF核心結果

[分割方式＼&標準svm＼&本文算法＼&準確率＼&FP;＼&FN;＼&時間＼&準確率＼&FP;＼&FN;＼&時間＼&2×2＼&100＼&0＼&0＼&12.045＼&100＼&0＼&0＼&10.815＼&2×3＼&82.258＼&0＼&54.5＼&13.4344＼&82.652＼&0＼&54.2＼&12.622＼&2×4＼&85.862＼&0＼&36.8＼&19.998＼&86.564＼&0＼&42.6＼&18.986＼&2×8＼&92.576＼&1＼&36.6＼&26.6684＼&93.546＼&0＼&19.5＼&25.856＼&3×2＼&98.624＼&0＼&8.6＼&12.04＼&100＼&0＼&5.4＼&11.028＼&3×3＼&97.546＼&0＼&26.4＼&20.3744＼&98.542＼&0＼&36.5＼&19.562＼&3×4＼&90.526＼&0＼&21.3＼&23.548＼&89.523＼&0＼&36.4＼&22.536＼&3×8＼&86.356＼&2＼&20.9＼&28.3804＼&96.387＼&0＼&27.2＼&27.568＼&4×2＼&93.656＼&0＼&18.5＼&19.794＼&95.684＼&0＼&18.1＼&18.782＼&4×3＼&90.582＼&0＼&19.2＼&24.6444＼&93.567＼&0＼&16.5＼&23.832＼&4×4＼&88.567＼&0＼&20.2＼&26.664＼&86.579＼&0＼&15.2＼&25.652＼&4×8＼&90.846＼&3＼&20.4＼&54.2014＼&83.872＼&1＼&14.6＼&53.389＼&8×2＼&98.108＼&0＼&23.5＼&27.177＼&87.265＼&0＼&15.3＼&26.165＼&8×3＼&89.258＼&0＼&16.2＼&30.3304＼&90.256＼&0＼&12.2＼&29.518＼&8×8＼&92.457＼&5＼&18.2＼&133.836＼&93.584＼&4＼&13.4＼&132.824＼&]

5 結束語

紙幣的鑒別真?zhèn)蔚倪^程實質上就是一個模式識別的過程，把這種模式識別的技術應用到驗鈔系統(tǒng)中，實驗證明在一定程度上提高了鑒偽的準確性。我們的目的是在軟件方面，通過研究建立—個鈔票實時處理系統(tǒng)，由軟件算法中的相應結論改善硬件設備的構造，接下來的工作是研究怎樣與硬件設備結合使用。

參考文獻：

[1] F.Takeda， T.Nishikage， and S.Omatu，Banknote recognition bymeans of optimized masks， neural network and genetic algorithms[J].engineering Applications of Artificial Intelligence，1999.12（2）：175-184

[2] F. Takeda， S. Omatu， A neuro-money recognition using optimized masks by GA[J]. Lecture Notes in Computer Science，1995.1011：190-201

[3] F.Omatu，S.Systems，Man and CybernetiCS， A neuro—papercurrency recognition method USing optimized masks by genetiC algorithm Takeda[J].IEEE International Conference on，1995.5：4367-437l

[4] C.He， M.Girolami， and G.Ross， Employing Optimized Combinations of One-Class Classifiers for Automated Currency Validation[J].Pattern Recognition，2004.37（6）： 1085-1096

[5] L.Jae-Kang， K.Il-Hwan， New recognition algorithm for various

kinds of Euro banknotes[C] //proceedings of the 29th Annual Conference of the IEEE Industrial Electronics Society， USA，2003.3：2266-2270

[6] A.Ahmadi， S.Omatu， M.Yoshioka， Implementing a reliableneuron-classifier for paper currency using PCA algorithm[C] //Proceedings of the 41st SICE Annual Conference of the Society of Instrument and Control Engineers， Japan，2002.4：2466-2468

[7] 劉爽，賈傳熒，陳鵬.一種自動選擇參數(shù)的加權支持向量機算法[J].計算機工程與應用，2006.42（2）：64-66

[8] R. Tomioka， T. Suzuki， M. Sugiyama， Optimization algorithms forsparse regularization and multiple kernel learning and their applications to CV/PR[C] //IEICE Technical Report， Japanese，2009：43-48

[9] Mingqing Hu， Yiqiang Chen， James Tin-Yau， Building sparsemultiple-kernel SVM classifiers[J].IEEE Transactions on Neural Networks，2009.20（5）：827-839