模式識別導(dǎo)論第一章精簡

1、模式識別導(dǎo)論PATTERN RECOGNITION PRIMER孫玉寶南京信息工程大學(xué)信息與控制學(xué)院 / 手機(jī) 言 課程對象系統(tǒng)專業(yè)本科自動化專業(yè)本科 與模式識別相關(guān)的學(xué)科基礎(chǔ)課程統(tǒng)計學(xué)概率論線性代數(shù)（矩陣計算）形式語言相關(guān)課程機(jī)器學(xué)習(xí)人工智能圖像處理計算機(jī)視覺教學(xué)方法著重講述模式識別的基本概念，基本方法和算法原理。注重理論與實踐緊密結(jié)合實例教學(xué)：通過大量實例講述如何將所學(xué)知識運用到實際應(yīng)用之中避免引用過多的、繁瑣的數(shù)學(xué)推導(dǎo)。 教學(xué)目標(biāo)掌握模式識別的基本概念和方法有效地運用所學(xué)知識和方法解決實際問題為研究新的模式識別的理論和方法打下基礎(chǔ) 題外話基本：完成課程學(xué)習(xí)，通過

2、考試考試，獲得學(xué)分。提高：能夠?qū)⑺鶎W(xué)知識和內(nèi)容用于課題研究，解決實際問題。飛躍：通過模式識別的學(xué)習(xí)，改進(jìn)思維方式，為將來的工作打好基礎(chǔ)，終身受益。參考文獻(xiàn)教材教材齊敏，李大健，郝重陽，模式識別導(dǎo)論，清華大學(xué)出版社，2009.參考著作參考著作R. Duda, P. Hart, D. Stork, Pattern Classification, second edition, 2000（有中譯本）.邊肇祺，模式識別（第二版），清華大學(xué)出版社，2000。蔡元龍，模式識別，西北電訊工程學(xué)院出版社，1986。機(jī)構(gòu)、會議、刊物1973年 IEEE發(fā)起了第一次關(guān)于模式識別的國際會議“ICPR”（此后兩年一次

3、），成立了國際模式識別協(xié)會-“IAPR”1977年IEEE成立PAMI委員會，創(chuàng)立IEEE Trans. on PAMI，并支持ICCV, CVPR兩個會議 其它刊物Pattern Recognition (PR)Pattern Recognition Letters (PRL)Pattern Analysis and Application (PAA)International Journal of Pattern Recognition and Artificial Intelligence (IJPRAI)第一章 模式識別概論什么是模式（Pattern）？什么是模式？具有某種特定性質(zhì)的觀

4、察對象，廣義地說，存在于時間和空間中可觀察的物體，如果我們可以區(qū)別它們是否相同或是否相似，都可以稱之為模式。模式舉例： 一個數(shù)字、 一句話、 一張照片等都是觀察對象，都能成為模式識別中的識別對象。模式類：具有相似特性的模式的集合。 模式與模式類的關(guān)系相當(dāng)于集合論中的元素與集合的 關(guān)系）模式的直觀特性:可觀察性可區(qū)分性相似性模式識別的概念模式識別 直觀，無所不在，“人以類聚，物以群分”周圍物體的認(rèn)知：桌子、椅子人的識別：張三、李四聲音的辨別：汽車、火車，狗叫、人語氣味的分辨：炸帶魚、紅燒肉人和動物的模式識別能力是極其平常的，但對計算機(jī)來說卻是非常困難的。模式識別的概念模式識別(Pattern R

5、ecognition) ： 用計算機(jī)確定一個模式（樣本）的類別屬性（模式類）的過程，即把某一樣本歸屬于多個類型中的某個類型。Pattern recognition is the study of how machines can observe the environment, learn to distinguish patterns of interest from their background, and make sound and reasonable decisions about the categories of the patterns. (Anil K. Jain)模式識

6、別的研究目的：利用計算機(jī)對樣本（模式）進(jìn)行分類，在錯誤概率最小的條件下，使識別的結(jié)果盡量與客觀物體相符合。Y = F(X)X的定義域取自特征集Y的值域為類別的標(biāo)號集F是模式識別的判別方法分類器分類器F樣本（模式）樣本（模式）類別類別 模式識別模式識別是一種智能活動，包括分析和判斷兩個過程。分析分析過程過程：通過學(xué)習(xí)與訓(xùn)練，學(xué)習(xí)與訓(xùn)練，確定用于劃分模式類的特征及其劃分準(zhǔn)則； 判斷過程判斷過程：依據(jù)待識別對象的特征，將其判屬于某一個模式類。 模式識別的研究模式識別與圖像處理、圖像識別的關(guān)系：模式識別是模擬人的某些功能。 模擬人的視覺：計算機(jī)+圖像傳感器 模擬人的聽覺：計算機(jī)+聲音傳感器 模擬人的嗅

7、覺和觸覺：計算機(jī)+嗅覺/觸覺傳感器 模式識別技術(shù)當(dāng)前主要是對視覺和聽覺能力的模擬。模擬人的視覺能力就是用計算機(jī)來做圖像識別和理解工作；模擬人的聽覺就是用計算機(jī)來做語音（或者各種聲音）識別和理解方面的工作。模式識別的研究模式識別簡史1929年 G. Tauschek發(fā)明閱讀機(jī) ，能夠閱讀0-9的數(shù)字。30年代 Fisher提出統(tǒng)計分類理論，奠定了統(tǒng)計模式識別的基礎(chǔ)。50年代 Noam Chemsky 提出形式語言理論傅京蓀 提出句法結(jié)構(gòu)模式識別。60年代 L.A.Zadeh提出了模糊集理論，模糊模式識別方法得以發(fā)展和應(yīng)用。80年代以Hopfield網(wǎng)、BP網(wǎng)為代表的神經(jīng)網(wǎng)絡(luò)模型導(dǎo)致人工神經(jīng)元網(wǎng)絡(luò)

8、復(fù)活，并在模式識別得到較廣泛的應(yīng)用。90年代小樣本學(xué)習(xí)理論，支持向量機(jī)也受到了很大的重視。當(dāng)前稀疏與低秩表示理論，深度學(xué)習(xí)模式識別的應(yīng)用（舉例）生物學(xué)自動細(xì)胞學(xué)、染色體特性研究、遺傳研究天文學(xué)天文望遠(yuǎn)鏡圖像分析、自動光譜學(xué)經(jīng)濟(jì)學(xué)股票交易預(yù)測、企業(yè)行為分析醫(yī)學(xué)心電圖分析、腦電圖分析、醫(yī)學(xué)圖像分析模式識別的應(yīng)用（舉例）工程產(chǎn)品缺陷檢測、特征識別、語音識別、自動導(dǎo)航系統(tǒng)、污染分析軍事航空攝像分析、雷達(dá)和聲納信號檢測和分類、自動目標(biāo)識別安全指紋識別、人臉識別、監(jiān)視和報警系統(tǒng)模式識別方法模式識別系統(tǒng)的目標(biāo)：在特征空間和類別空間之間找到一種映射關(guān)系，這種映射也稱之為分類器。特征空間：從模式得到的對分類有用

9、的度量、屬性或基元構(gòu)成的空間。類別空間：將c個類別表示為其中 為所屬類別的集合，稱為類別空間。 分類器分類器F樣本（模式）樣本（模式）類別類別模式識別方法：監(jiān)督學(xué)習(xí)監(jiān)督學(xué)習(xí)依靠已知所屬類別的的訓(xùn)練樣本集，按它們特征向量的分布來確定判別函數(shù)，在判別函數(shù)確定之后能用它對未知的模式進(jìn)行分類；對分類的模式要有足夠的先驗知識，通常需要采集足夠數(shù)量的具有典型性的樣本進(jìn)行訓(xùn)練。 訓(xùn)練樣本訓(xùn)練樣本（模式（模式+類別）類別）分類器分類器F學(xué)習(xí)訓(xùn)練學(xué)習(xí)訓(xùn)練 測試樣本測試樣本 （未知類別）（未知類別）分類決策分類決策類別類別監(jiān)督學(xué)習(xí)模式監(jiān)督學(xué)習(xí)模式樣本集樣本集模式識別方法：非監(jiān)督學(xué)習(xí)非監(jiān)督學(xué)習(xí)在沒有先驗知識的情況下

10、，基于“物以類聚”的觀點，在學(xué)習(xí)過程中根據(jù)樣本的相似性對被識別的樣品進(jìn)行識別分類和歸類，稱為聚類分析。這種方法試圖找到一種只以特征空間中的樣本相似關(guān)系為基礎(chǔ)的識別方法。 樣本樣本 （類別未知）（類別未知）聚類分析聚類分析類別類別模式分類的主要方法模板匹配數(shù)據(jù)聚類統(tǒng)計分類結(jié)構(gòu)模式識別神經(jīng)網(wǎng)絡(luò)模板匹配法該方法的基本思想如下：(1)首先對每個類別建立一個或多個模板；(2)輸入樣本和數(shù)據(jù)庫中每個類別的模板進(jìn)行比較，求相關(guān)或距離；(3)根據(jù)相關(guān)性或距離大小進(jìn)行決策。 優(yōu)點：直接、簡單缺點：適應(yīng)性差數(shù)據(jù)聚類目標(biāo)：用某種相似性度量的方法將原始數(shù)據(jù)組織成有意義的和有用的各種數(shù)據(jù)集。是一種非監(jiān)督學(xué)習(xí)的方法，解決

11、方案是數(shù)據(jù)驅(qū)動的。統(tǒng)計分類基于概率統(tǒng)計模型得到各類別的特征向量的分布，以取得分類的方法。特征向量分布的獲得是基于一個類別已知的訓(xùn)練樣本集。根據(jù)訓(xùn)練樣本，建立決策邊界 統(tǒng)計決策理論根據(jù)每一類總體的概率分布決定 決策邊界 判別分析方法給出帶參數(shù)的決策邊界，根據(jù)某 種準(zhǔn)則，由訓(xùn)練樣本決定“最優(yōu)”的參數(shù)是一種監(jiān)督分類的方法，分類器是概念驅(qū)動的。結(jié)構(gòu)模式識別該方法通過考慮識別對象的各部分之間的聯(lián)系來達(dá)到識別分類的目的。識別采用結(jié)構(gòu)匹配的形式，通過計算一個匹配程度值（matching score）來評估一個未知的對象或未知對象某些部分與某種典型模式的關(guān)系如何。當(dāng)成功地制定出了一組可以描述對象部分之間關(guān)系的

12、規(guī)則后，可以應(yīng)用一種特殊的結(jié)構(gòu)模式識別方法 句法模式識別，來檢查一個模式基元的序列是否遵守某種規(guī)則，即句法規(guī)則或語法。神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)是受人腦組織的生理學(xué)啟發(fā)而創(chuàng)立的。由一系列互相聯(lián)系的、相同的單元（神經(jīng)元）組成。相互間的聯(lián)系可以在不同的神經(jīng)元之間傳遞增強(qiáng)或抑制信號。增強(qiáng)或抑制是通過調(diào)整神經(jīng)元相互間聯(lián)系的權(quán)重系數(shù)來（weight）實現(xiàn)。神經(jīng)網(wǎng)絡(luò)可以實現(xiàn)監(jiān)督和非監(jiān)督學(xué)習(xí)條件下的分類。模式識別系統(tǒng)模式識別系統(tǒng)的基本構(gòu)成數(shù)據(jù)獲取特征提取和選擇預(yù)處理分類決策（測試判別）（測試判別）分類器設(shè)計（學(xué)習(xí)與訓(xùn)練）（學(xué)習(xí)與訓(xùn)練）學(xué)習(xí)訓(xùn)練過程：從訓(xùn)練樣本學(xué)習(xí)確定用于劃分模式類的特征及其表 達(dá)方法； 判斷判別過程：

13、依據(jù)待識別對象的特征，將其判屬于某一個模式類。 模式識別系統(tǒng)組成單元數(shù)據(jù)獲取：對于機(jī)器識別來說, 由于計算機(jī)只能處理數(shù)字信號, 計算機(jī)獲取模式信息意味著實現(xiàn)觀察對象的數(shù)字化表達(dá)。信息獲取是通過傳感器，將光或聲音等信息轉(zhuǎn)化為電信息，用計算機(jī)可以運算的符號來表示所研究的對象二維圖像：文字、指紋、地圖、照片等一維波形：腦電圖、心電圖、季節(jié)震動波形等物理參量和邏輯值：體溫、化驗數(shù)據(jù)、參量正常與否的描述模式識別系統(tǒng)組成單元預(yù)處理單元：去噪聲，提取有用信息，并對輸入測量儀器或其它因素所造成的退化現(xiàn)象進(jìn)行復(fù)原。對于圖像信息，采用數(shù)字圖像處理技術(shù)作為其預(yù)處理技術(shù)，主要有二值化、圖像平滑、變換、增強(qiáng)、恢復(fù)、濾波

14、、幾何校正等。模式識別系統(tǒng)組成單元特征提取和選擇：對原始數(shù)據(jù)進(jìn)行變換，得到最能反映分類本質(zhì)的特征。如，一幅6464的灰度圖像可以得到4096個數(shù)據(jù)，這種在測量空間的原始數(shù)據(jù)通過變換獲得在特征空間最能反映分類本質(zhì)的特征。這就是特征提取和選擇的過程。模式識別系統(tǒng)組成單元特征是用于描述模式性質(zhì)(特性)的一種定量的概念, 通過對模式的分析得到一組特征, 稱這個過程為特征形成。特征一般通過向量進(jìn)行表示 當(dāng)將特征表達(dá)為數(shù)值時, 一個模式的 d 個特征值就構(gòu)成了一個特征向量特征向量, 記為x x, 即12( ,)dx xxx其中, x x 的每個分量 xi (i=1, 2, , d) 對應(yīng)一個特征。 模式識

15、別系統(tǒng)組成單元特征提取與選擇是指采用變換 (或映射)實現(xiàn)由模式測量空間向特征空間的轉(zhuǎn)變, 或者將特征空間的維數(shù)從高維變成低維。模式空間模式空間：原始數(shù)據(jù)組成的空間特征空間特征空間：分類識別賴以進(jìn)行的空間特征提取與選擇特征提取與選擇：維數(shù)較高的模式空間-維數(shù)較低的特征空間模式識別系統(tǒng)組成單元分類決策：在特征空間中用模式識別方法把被識別對象歸為某一類別基本做法：在樣本訓(xùn)練集基礎(chǔ)上確定某個判決規(guī)則，使得按這種規(guī)則對被識別對象進(jìn)行分類所造成的錯誤識別率最小或引起的損失最小說明：基于機(jī)器學(xué)習(xí)的模式識別系統(tǒng)通常由兩個過程組成, 即分類器設(shè)計(簡稱設(shè)計)和分類判決(簡稱實現(xiàn))。 一般是用一定數(shù)量的樣本進(jìn)行分

16、類器設(shè)計, 這些樣本的所屬類別已知, 稱為訓(xùn)練樣本。 測試是用所設(shè)計的分類器對待識別模式進(jìn)行分類判決 (或分類決策)。模式識別過程實例在傳送帶上用光學(xué)傳感器件對魚按品種分類鱸魚(Seabass)品種鮭魚(Salmon)識別過程數(shù)據(jù)獲?。杭茉O(shè)一個攝像機(jī)，采集一些樣本圖像，獲取樣本數(shù)據(jù)預(yù)處理：去噪聲，用一個分割操作把魚和魚之間以及魚和背景之間分開識別過程特征提取和選擇：對單個魚的信息進(jìn)行特征選擇，從而通過測量某些特征來減少信息量長度亮度寬度魚翅的數(shù)量和形狀嘴的位置，等等 分類決策：把特征送入決策分類器模式分類器的獲取和評測過程數(shù)據(jù)采集特征選取訓(xùn)練和測試計算結(jié)果和復(fù)雜度分析，反饋訓(xùn)練和測試訓(xùn)練集：是

17、一個已知樣本集，在監(jiān)督學(xué)習(xí)方法中，用它來開發(fā)出模式分類器。測試集：在設(shè)計識別和分類系統(tǒng)時沒有用過的獨立樣本集。系統(tǒng)評價原則：為了更好地對模式識別系統(tǒng)性能進(jìn)行評價，必須使用一組獨立于訓(xùn)練集的測試集對系統(tǒng)進(jìn)行測試。對象空間對象空間模式空間模式空間特征空間特征空間類型空間類型空間各類空間（各類空間（Space)Space)的概念的概念模式采集：模式采集：從客觀世界（對從客觀世界（對象象空間，樣本空間）空間，樣本空間）到模式空間到模式空間的過程稱為模式采集。的過程稱為模式采集。特征提取和特征選擇：特征提取和特征選擇：由模式由模式空間到特征空間的變換和選擇?？臻g到特征空間的變換和選擇。類型判別：類型判別

18、：特征空間到類型空特征空間到類型空間所作的操作。間所作的操作。模模式式識識別別三三大大任任務(wù)務(wù)模式分類器的獲取和評測過程50數(shù)據(jù)采集數(shù)據(jù)采集分類分類識別識別特征提取特征提取與與選擇選擇訓(xùn)練訓(xùn)練樣本樣本改進(jìn)采集改進(jìn)采集提取方法提取方法改進(jìn)特征提改進(jìn)特征提取與選擇取與選擇制定改進(jìn)分制定改進(jìn)分類識別規(guī)則類識別規(guī)則測試測試樣本樣本正確率正確率測試測試51例:汽車車牌識別從攝像頭獲取包含車牌的彩色圖象從攝像頭獲取包含車牌的彩色圖象車牌定位和獲取車牌定位和獲取字符分割和識別字符分割和識別輸入圖象輸入圖象特征提取特征提取粗略定位粗略定位分割字符分割字符確定類型確定類型精細(xì)定位精細(xì)定位識別、輸出識別、輸出52

19、53實例：統(tǒng)計模式識別19名男女同學(xué)進(jìn)行體檢，測量了身高和體重，但事后發(fā)現(xiàn)其中有4人忘記填寫性別，試問（在最小錯誤的條件下）這4人是男是女？體檢數(shù)值如下：實例：統(tǒng)計模式識別（續(xù)）待識別的模式：性別（男或女）測量的特征：身高和體重訓(xùn)練樣本：15名已知性別的樣本特征目標(biāo)：希望借助于訓(xùn)練樣本的特征建立判別函數(shù)（即數(shù)學(xué)模型）實例：統(tǒng)計模式識別（續(xù)）由訓(xùn)練樣本得到的特征空間分布圖實例：統(tǒng)計模式識別（續(xù)）從圖中訓(xùn)練樣本的分布情況，找出男、女兩類特征各自的聚類特點，從而求取一個判別函數(shù)（直線或曲線）。只要給出待分類的模式特征的數(shù)值，看它在特征平面上落在判別函數(shù)的哪一側(cè)，就可以判別是男還是女了。實例：句法模式

20、識別問題：如何利用對圖像的結(jié)構(gòu)信息描述，識別如下所示圖片：實例：句法模式識別（續(xù)）將整個場景圖像結(jié)構(gòu)分解成一些比較簡單的子圖像的組合；子圖像又用一些更為簡單的基本圖像單元來表示，直至子圖像達(dá)到了我們認(rèn)為的最簡單的圖像單元（基元）；所有這些基元按一定的結(jié)構(gòu)關(guān)系來表示，利用多級樹結(jié)構(gòu)對其進(jìn)行描述（這種描述可以采用形式語言理論）。實例：句法模式識別（續(xù)）多級樹描述結(jié)構(gòu)實例：句法模式識別（續(xù)）訓(xùn)練過程：用已知結(jié)構(gòu)信息的圖像作為訓(xùn)練樣本，先識別出基元（比如場景圖中的X、Y、Z等簡單平面）和它們之間的連接關(guān)系（例如長方體E是由X、Y和Z三個面拼接而成），并用字母符號代表之；然后用構(gòu)造句子的文法來描述生成這

21、幅場景的過程，由此推斷出生成該場景的一種文法。實例：句法模式識別（續(xù)）識別過程：先對未知結(jié)構(gòu)信息的圖像進(jìn)行基元提取及其相互結(jié)構(gòu)關(guān)系的識別；然后用訓(xùn)練過程獲得的文法做句法分析；如果能被已知結(jié)構(gòu)信息的文法分析出來，則該幅未知圖像與訓(xùn)練樣本具有相同的結(jié)構(gòu)（識別成功），否則就不是這種結(jié)構(gòu)（識別失敗）。本門課程的主要內(nèi)容第一章 概論第二章 聚類分析第三章 判別函數(shù)第四章 統(tǒng)計判別第五章特征選擇和提取第六章神經(jīng)網(wǎng)絡(luò)第七章句法模式識別第八章模糊模式識別第九章模式識別應(yīng)用相關(guān)數(shù)學(xué)概念隨機(jī)向量及其分布隨機(jī)向量如果一個對象的特征觀察值為x1, x2, , xn，它可構(gòu)成一個n維的特征向量值x，即 x = (x1,

22、 x2, , xn)T 式中， x1, x2, , xn為特征向量x的各個分量。一個特征可以看作n維空間中的向量或點，此空間稱為模式的特征空間Rn。相關(guān)數(shù)學(xué)概念隨機(jī)向量及其分布隨機(jī)向量在模式識別過程中，要對許多具體對象進(jìn)行測量，以獲得許多次觀測值。每次觀測值不一定相同，所以對許多對象而言，各個特征分量都是隨機(jī)變量，即許多對象的特征向量在n維空間中呈隨機(jī)性分布，稱為隨機(jī)向量。相關(guān)數(shù)學(xué)概念隨機(jī)向量及其分布隨機(jī)向量的參數(shù)數(shù)學(xué)期望和方差協(xié)方差協(xié)方差矩陣數(shù)學(xué)期望與方差隨機(jī)變量X的數(shù)學(xué)期望（或稱均值）記作E(X)，它描述了隨機(jī)變量的取值中心。隨機(jī)變量( X - E(X) )2的數(shù)學(xué)期望稱為X的方差，記作2，而稱為X的均方差（標(biāo)準(zhǔn)差）。它們描述了隨機(jī)變量的可能取值與均值的偏差的疏密程度。數(shù)學(xué)期望與方差數(shù)學(xué)期望與