模式識別報告

1、一、模式識別概論在信息的處理過程中，首先需要解決的就是信息的分類問題。按 “物以類聚”的自然規(guī)律，將大容量的信息分門別類，各種類別的信 息分別歸集在一起，然后找出它們內(nèi)部的規(guī)律，以及它們相互之間的 規(guī)律，然后按規(guī)律建立模型，進(jìn)行生產(chǎn)過程的操作和控制，這樣才能 達(dá)到事半功倍的效果。對具體的個別事物進(jìn)行觀測所得到的具有時間和空間分布的信 息稱為模式，而把模式所屬的類別或同一類中模式的總體稱為模式類。 人們?yōu)榱苏莆湛陀^事物，按事物相似的程度組成類別。模式識別的作 用和目的就在于對某一具體事物時將其準(zhǔn)確地歸入某一類別。模式識 別系統(tǒng)都由兩個過程所組成，即設(shè)計和實現(xiàn)。設(shè)計是指用一定數(shù)量的 樣本進(jìn)行分類器

2、的設(shè)計。實現(xiàn)是指用所設(shè)計的分類器對待識別的樣本 進(jìn)行分類決策。模式識別系統(tǒng)主要由4個部分組成:數(shù)據(jù)獲取，預(yù)處 理，特征提取和選擇，分類決策。分類決策就是在特征空間中用統(tǒng)計方法把被識別對象歸為某一 類別?；咀鞣ㄊ窃跇颖居?xùn)練集基礎(chǔ)上確定某個判決規(guī)則，使按這種 判決規(guī)則對被識別對象進(jìn)行分類所造成的錯誤識別率最小或引起的 損失最小。二、模式識別的方法模式分類是模式識別的主要內(nèi)容，即將某個模式分到某個模式類中。在這個過程中首先需要建立樣本庫，然后根據(jù)樣本庫建立判別函 數(shù)，這一過程由機(jī)器來實現(xiàn)，成為學(xué)習(xí)過程。然后對一個未知的新對 象分析它的特征，并根據(jù)判別函數(shù)決定它屬于哪一類。模式分類是一 種監(jiān)督學(xué)習(xí)的

3、方法?？捎糜谀Ｊ椒诸惖姆椒ㄓ泻芏?，經(jīng)典的方法有：統(tǒng)計模式識別統(tǒng)計模式識別方法是受數(shù)學(xué)中的決策理論啟發(fā)而產(chǎn)生的一種識 別方法。其基本思想是將特征提取階段得到的特征向量定義在一個特 征空間中，這個空間包含了所有的特征矢量。不同的特征向量，或者 說不同類別的對象，都對應(yīng)于此空間中的一點。在分類階段，則利用 統(tǒng)計決策的原理對特征空間進(jìn)行劃分，從而達(dá)到識別不同特征對象的 目的。統(tǒng)計識別中應(yīng)用的統(tǒng)計決策分類理論相對比較成熟，研究的重 點是特征提取。這類方法中常用的方法有貝葉斯分類、線性分類、非 線性分類和聚類分析。這類方法的優(yōu)點是比較成熟，能考慮干擾噪聲等影響，識別模式 基元能力強(qiáng)。但是該方法對結(jié)構(gòu)復(fù)雜的

4、模式抽取特征困難，不能反映 模式的結(jié)構(gòu)特征，難以描述結(jié)構(gòu)的性質(zhì)。難以從整體角度考慮識別問 題。句法結(jié)構(gòu)模式識別句法識別是對統(tǒng)計識別方法的補(bǔ)充。統(tǒng)計方法用數(shù)值來描述圖像 的特征，句法方法則是用符號來描述圖像特征的。它模仿了語言學(xué) 中句法的層次結(jié)構(gòu)，采用分層描述的方法，把復(fù)雜圖像分解為單層 或多層的簡單子圖像，主要突出了識別對象的結(jié)構(gòu)信息。圖像識別是 從統(tǒng)計方法發(fā)展起來的，而句法方法擴(kuò)大了識別的能力，使其不僅 限于對象物的分類，而且還用于景物的分析與物體結(jié)構(gòu)的識別。這類 方法中常用的方法有自動機(jī)技術(shù)、CYK剖析算法、Early算法和轉(zhuǎn)移圖 法。該類方法識別方便，可以從簡單的基元開始，由簡至繁。能反

5、映 模式的結(jié)構(gòu)特征，能描述模式的性質(zhì)。對圖形的畸變抗干擾能力較強(qiáng)。 但是該方法當(dāng)存在干擾和噪聲時，抽取特征基元困難，且易失誤。模糊模式識別模糊模式識別的理論基礎(chǔ)是模糊數(shù)學(xué)。它根據(jù)人辨識事物的思維 邏輯，吸取人腦的識別特點，將計算機(jī)中常用的二值邏輯轉(zhuǎn)向連續(xù)邏 輯。模糊識別的結(jié)果是用被識別對象隸屬于某一類別的程度即隸屬度 來表示的，一個對象可以在某種程度上屬于某一類別，而在另一種程 度上屬于另一類別。一般常規(guī)識別方法則要求一個對象只能屬于某一 類別?；谀：碚摰淖R別方法有:最大隸屬原則識別法、擇近原 則識別法和模糊聚類法。該方法由于隸屬度函數(shù)作為樣本與模板間相似程度的度量，能反 映整體的與主體

6、的特征，從而允許樣本有相當(dāng)程度的干擾與畸變。但 是該方法準(zhǔn)確合理的隸屬度函數(shù)往往難以建立，故限制了它的應(yīng)用。（1）貝葉斯分類貝葉斯判別的核心問題是：樣本為特征向量X時，它屬于哪一類 可能性有多大。如能確定屬于各個類別的百分比（概率），分類決策就 有了依據(jù)。貝葉斯分類有最大后驗概率判決準(zhǔn)則和最小風(fēng)險貝葉斯判 決準(zhǔn)則。最大后驗概率判決準(zhǔn)則如果P（31|x）P（32|x）,則判決X屬于3 1；如果P（1|x）P（2|x）,則判決X屬于32；如果P（31|x）二P（32|x）,則判決x屬于31或?qū)儆?/這種決策稱為最大后驗概率判決準(zhǔn)則，也稱為貝葉斯（Bayes）判 決準(zhǔn)則。假設(shè)已知P（3j）和p（x|

7、3（i=1, 2,，m）,最大后驗概 率判決準(zhǔn)則就是把樣本x歸入后驗概率最大的類別中，也就是P( I x) = max P(w I x)jie1,2,m則 xE3.。由于已知P（i ）和p（x|3因此需要找到P（3x ）與它們之間 的關(guān)系。假設(shè)特征變量為X,由Bayes公式p (x I )P 皿)iip (x)若 p（x I ）P0 ） = max p（xI ）P（ ），則 xE3 ；J Jie1,2, m在最大后驗概率判決準(zhǔn)則中，xE3.的決策區(qū)域為=x I 心)也,i = 1,2,.,m,i 豐 j p (x I 巴)P ( ?J最大后驗概率判決準(zhǔn)則的一個優(yōu)良性質(zhì)就是使平均錯誤概率達(dá)到 最

8、小。因此，最大后驗概率判決準(zhǔn)則又稱為最小錯誤概率判決準(zhǔn)則。最小風(fēng)險貝葉斯判決準(zhǔn)則基于最小風(fēng)險的貝葉斯決策的基本思路是給每一種決策規(guī)定一 個損失值（或代價），將其作為因錯誤決策而導(dǎo)致的損失的度量。決策ai：將樣本x的類別判為第j類。損失函數(shù)X(aj,wi):對真實類別為第i類的樣本采取決策氣 所帶來的損失。條件風(fēng)險當(dāng)樣本x的真實類別未知時，決策*的條件風(fēng)險是對x為所有可 能的真實類別條件下將樣本判為第j類的代價求平均，即R (a I x) = 人(a 0 ) P 皿 I x)i=1最小風(fēng)險貝葉斯判決準(zhǔn)則:R (a I x) = min R (a I x)則判決xGw,其中r(a Ix) = 人(

9、a ,)P(Ix)。Ji=1J線性分類線性判別函數(shù)的形式如下:g (x) = wT x + w0即 g (x) = w T x + w = wx + w X HF w X + W = 0。 其中 w = (w , w，w )t ,0112 2d d 012dx =(氣,., Xd)T。其幾何意義為d維歐幾里德空間中的一個超平面。線性分類器設(shè)計的關(guān)鍵在于確定權(quán)向量w和閾值權(quán)w0。對于兩類分類問題，線性判決函數(shù)的幾何意義在于利用一個超平面實現(xiàn)對特征空間Rd的劃分。即w t (x - x ) = 0其中w指向R1, R1中的點在H的正側(cè)。R2中的點在H的負(fù)側(cè)。如下圖所示:R1，- w . X1-x2

10、 /R2匕一一OH:g(x)=0超平面示意圖g(x)是x到超平面距離的一種代數(shù)距離。該距離有符號，當(dāng)符號 為正時，表明x對應(yīng)的點在超平面的正側(cè)，反之在負(fù)側(cè)。對于多類分類問題，利用線性判別函數(shù)設(shè)計多類分類器。可以把 n個類問題化簡為n-1個問題，其中第i個問題可以用線性判別函數(shù) 把屬于七類的點與不屬于wi的點區(qū)分。最麻煩的方法是用c (c-1) /2個線性判別函數(shù)把樣本分為c個類別，每個判別函數(shù)只針對兩個 類進(jìn)行分類。定義c個判別函數(shù)g (x) = WTX + w如果對于一切j。i,存在g,(X) gj(x)，則把x歸于Wi類。如果 g, (X) = gj (X)則拒絕決策。線性判別函數(shù)設(shè)計的一

11、般步驟：選擇樣本集z=x1,x2，,xN。樣本集中的樣本來自兩類且類 別已知。確定一個準(zhǔn)則函數(shù)J,要求滿足以下兩個條件：J是樣本集、w和w的函數(shù)；J的值反映分類器性能，它的極值對應(yīng)于“最好”的決策。用最優(yōu)化技術(shù)求解準(zhǔn)則函數(shù)，得到極值點對應(yīng)的w*和w*。常見的線性判斷準(zhǔn)則有最小距離判別，歐幾里德線性判別，馬氏 距離線性判別，F(xiàn)isher線性判別。Fisher線性判別Fisher線性判決的基本思想是尋找一個最好的投影方向，當(dāng)特征 向量x從d維空間映射到這個方向上時，兩類能最好地分開。即向量 W的方向選擇應(yīng)能使兩類樣本投影的均值之差盡可能大些，而使類內(nèi) 樣本的離散程度盡可能小。這就是Fisher準(zhǔn)則

12、函數(shù)的基本思路。尋 找最好的投影方向，在數(shù)學(xué)上就表現(xiàn)為尋找最好的變換方向w*。Fisher線性判決函數(shù)為J(w)=(PP )2S1 + 52分子反映了映射后兩類中心的距離平方，該值越大,類間可分性越 好；分母反映了兩類的類內(nèi)離散度，其值越小越好；從總體上來講，JF(w)的值越大越好。在這種可分性評價標(biāo)準(zhǔn)下，使JF(w)達(dá)到最大值 的w即為最佳投影方向。將J (w)化成w的顯示格式，故Fisher線性判決函數(shù)化為Fw t S wJ (w) =bFwtS ww求J(w)的極大值點Fw * = S-1(汽p 2)利用w*，將樣本x往該方向上投影，可得y = (w *)t x在投影空間內(nèi)的決策準(zhǔn)則為：

13、若yy0，則xE3，否則xe o20歐幾里德線性判別任意特征向量x和一個代表點之間的歐幾里德平方距離可以用 下面的公式描述d2(x) =11 x- m 11= (x- m )(x- m ) = xv - m x- xm + m mkkkkkk k k選擇d2( x )使得最小化的類wk也就是mk將包含mk的項放到一起我們 得到d2(x) = -2(m x一 0.5m m ) + xx假設(shè)類別數(shù)c=2，那么類之間對應(yīng)的決策邊界為d2(x) = d2(x)即12mx 一 0.5 II m II2 = m x 一 0.5 II m II2n (m 一 m )x 一 0.5(m + m ) = 011

14、221212最后得到一個關(guān)于x的線性等式它表示了一個垂直于(m1 -m2)并且 通過均值點的中心點0.5(m1 + m的超平面。它是一個劃分W1和的的線性 判別。馬氏距離線性判別馬氏距離是歐幾里德距離尺度的一個推廣它非常適合于解決協(xié)方 差不相等以及特征之間相互聯(lián)系的情況假設(shè)所有的類別具有一個相 同的協(xié)方差矩陣C這表明各類特征向量的分布就有一個相似的超橢圓 形狀，根據(jù)歐幾里德平方距離得d2(x) = (x一m )C-1(x一m )再次根據(jù)mk進(jìn)行合并，得到d2(x) = -2(CTm )x - 0.5m CTm + xCtx 決策函數(shù)為：g (x) = W x + w其中， w = C-im ;

15、 w = -0.5m C-im得到一個超平面形式的線性判別函數(shù)它通過連接均值點線段的中 點和前面一節(jié)得到的結(jié)果的唯一不同就是如今劃分類W|和類Wj的超 平面是和向量C-i（m -m ）相互正交。（3）非線性分類線性分類器的分界面是一個超平面。當(dāng)類與類之間不能用任何 一個超平面實現(xiàn)劃分時，類間的分界面應(yīng)是一個超曲面?？紤]到曲線 可以由多個線段近似表達(dá)，曲面可以由多個平面逼近，因此,也可以 用多個超平面近似表達(dá)超曲面，分段線性分類器正是基于這種思路而 設(shè)計的一種分類器。分段線性距離分類器中最小距離分類器，其判決函數(shù)為llx 叩2 llx V2 = x ：1I 2即 |x - vjl2 -| |x

16、- V J|2 0 n x -：1，這時類間的決策面為I 2|x V2 = I|x V 21|2它是兩類均值點連線的垂直平分面。H1H2兩類非線性可分時可用多段超平面分開（4）神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)是由大量的人工神經(jīng)元廣泛互連而成的網(wǎng)絡(luò)。神經(jīng)網(wǎng)絡(luò) 信息處理包括學(xué)習(xí)和執(zhí)行兩個階段。學(xué)習(xí)階段也稱為訓(xùn)練階段：給定訓(xùn)練樣本集，按一定的學(xué)習(xí) 規(guī)則調(diào)整權(quán)系數(shù)，使某種代價函數(shù)達(dá)到最小，也就是使權(quán)系數(shù)收斂 到最優(yōu)值。執(zhí)行階段：利用學(xué)習(xí)階段得到的連接權(quán)系數(shù)，對輸入信息進(jìn)行 處理，并產(chǎn)生相應(yīng)的輸出。BP網(wǎng)絡(luò)是采用誤差反向傳播算法的多層前饋網(wǎng)絡(luò)其學(xué)習(xí)規(guī)則采 用梯度下降算法。在網(wǎng)絡(luò)學(xué)習(xí)過程中，把輸出層節(jié)點的期望輸出（目標(biāo)

17、輸出）與實際輸出（計算輸出）的均方誤差，逐層向輸入層反向傳播，分 配給各連接節(jié)點，并計算出各連接節(jié)點的參考誤差，在此基礎(chǔ)上調(diào)整 各連接權(quán)值,使得網(wǎng)絡(luò)的期望輸出與實際輸出的均方誤差達(dá)到最小。逐個處理的BP算法訓(xùn)練步驟如下：初始化。根據(jù)實際問題，設(shè)計網(wǎng)絡(luò)連接結(jié)。輸入一個樣本,用現(xiàn)有的權(quán)值計算網(wǎng)絡(luò)中各神經(jīng)元的實際輸出。U E 弋 E）計算局部誤差（i）pk（i=1,2,，l, l+1）,l為隱含層的個數(shù)。計算權(quán)值變化量A W（i）（i=1,2,，l,l+1）,并更新相應(yīng)的權(quán)值。P,k輸入另一樣本，轉(zhuǎn)步驟。把訓(xùn)練集中所有樣本都加到網(wǎng)絡(luò)上， 直到網(wǎng)絡(luò)收斂且均方誤差小于給定的閾值訓(xùn)練結(jié)束。此時，固定權(quán)值，

18、 網(wǎng)絡(luò)就構(gòu)成了一個模式分類器。三、應(yīng)用實例以車牌識別為例，說明模式識別的應(yīng)用。車牌的識別的過程如下圖所示:時集玦實果橫字像數(shù)用車牌分判特征提取數(shù)據(jù)傳送常見的車牌拍攝圖如下所示:該車尸口所在省的簡和 車牌超過了藪字的容量國為福建璀用字毋表示I字狩 使用 白色英文字母中的I和O一般避而不用，以免和數(shù)字中的1和0混淆。車牌大小為440*140mm。漢字字體為黑體，數(shù)字和字母字體為國家公 安部門開發(fā)的特殊字體。車牌識別預(yù)處理字符分割2.字符細(xì)化特征空間向量的選擇由于車牌中字母和數(shù)字都有特定的字體，且作為汽車的“身份證”，車牌制作過程嚴(yán)謹(jǐn)，相同字符形態(tài)區(qū)別不大，他們的差異性和共同點都很明顯。基于上節(jié)描述

19、的設(shè)計準(zhǔn)則，綜合考慮了提取特征的 編程復(fù)雜度和特征對不同字符的區(qū)分度，本系統(tǒng)分別從字符的形態(tài)、 結(jié)構(gòu)、筆畫特點出發(fā)，采用了 4個類別共10個特征值作為判斷的矢 量依據(jù)（特征提取時均以細(xì)化后圖像為基礎(chǔ)）。字符的重心判斷：字符重心位于上方/下方，分別計算字符上下半?yún)^(qū)的像素數(shù)目， 如果其差值在一個固定的小范圍內(nèi)（試驗得出此差值在0-20像素內(nèi) 為最佳），則該特征值記為2,上方偏多記為1，下方偏多記為3；字符重心位于左方/右方，分別計算字符左右半?yún)^(qū)的像素數(shù)目， 如果其差值在一個固定的小范圍內(nèi)（試驗得出此差值在0-20像素內(nèi) 為最佳），則該特征值記為2,左方偏多記為1，右方偏多記為3。特定位置的掃描線特征：圖像垂直1/3處掃描線穿越的線條數(shù)目；圖像垂直1/2處掃描線穿越的線條數(shù)目；圖像垂直2/3處掃描線穿越的線條數(shù)目；圖像水平1/3處掃描線穿越的線條數(shù)目；圖像水平2/3處掃描線穿越的線條數(shù)目；筆畫特征：字符中“豎”的數(shù)目，計算圖像在水平方向上的投影，投影點 的像素數(shù)目累加值超過1/3圖像高度且無超過5像素的中斷，記為 “豎”的數(shù)目加1；字符中“橫”的數(shù)目，計算圖像在垂直方向上的投影，投影點 的像素數(shù)目累加值超過1/3圖像寬度且