圖像識別與模式識別

1、圖 像描 述圖像處理圖像識別圖像理解計算機圖形學圖像（模式）識別概念n模式識別：對表征事物或現(xiàn)象的各種形式的（數(shù)值的，文字的和邏輯關(guān)系的）信息進行處理和分析，以對事物或現(xiàn)象進行描述、辨認、分類和解釋的過程，是信息科學和人工智能的重要組成部分。n什么是模式 （Pattern）？ “模式”是一個客觀事物的描述，是指建立一個可用于仿效的完善的標本。n 圖像識別與模式識別n模式識別的研究內(nèi)容 1）研究生物體（包括人）是如何感知對象的，屬于認知科學的范疇 2）在給定的任務下，如何用計算機實現(xiàn)模式識別的理論和方法 n典型模式識別系統(tǒng)典型模式識別系統(tǒng) n圖像識別系統(tǒng)圖像識別系統(tǒng) n人臉識別系統(tǒng)8 8圖像識別

2、圖像識別8.1 8.1 概述概述n模式模式可以定義為可以定義為物體的描述物體的描述。由于描述這個。由于描述這個詞的意義比較廣泛，有人把它推廣到圖像數(shù)詞的意義比較廣泛，有人把它推廣到圖像數(shù)據(jù)本身，因為圖像數(shù)據(jù)也是相應事物的一種據(jù)本身，因為圖像數(shù)據(jù)也是相應事物的一種描述，只不過這樣的描述不夠抽象和簡要而描述，只不過這樣的描述不夠抽象和簡要而已。前章中我們已經(jīng)討論過圖像的各種特征已。前章中我們已經(jīng)討論過圖像的各種特征和描述的提取方法。因此，我們將和描述的提取方法。因此，我們將模式解釋模式解釋為物體的較抽象的特征和描述。為物體的較抽象的特征和描述。 n模式可以是以模式可以是以矢量形式矢量形式表示的表示

3、的數(shù)字特征數(shù)字特征；也可以是以也可以是以句法結(jié)構(gòu)句法結(jié)構(gòu)表示的表示的字符串或圖字符串或圖；還可以是以還可以是以關(guān)系結(jié)構(gòu)關(guān)系結(jié)構(gòu)表示的表示的語義網(wǎng)絡或框語義網(wǎng)絡或框架結(jié)構(gòu)架結(jié)構(gòu)等。等。n對于上述三種類型的模式，必須分別使用不對于上述三種類型的模式，必須分別使用不同的識別和推理方法：同的識別和推理方法：統(tǒng)計模式識別，句法統(tǒng)計模式識別，句法模式識別模式識別和和人工智能方法人工智能方法。 n統(tǒng)計模式識別基本原理是：有相似性的樣本在模式空間中互相接近，并形成“集團”，即“物以類聚”。主要方法有：決策函數(shù)法， k近鄰分類法，支持向量機，特征分析法，主因子分析法等參考書籍：統(tǒng)計模式識別(Andrew R.W

4、ebb) Jain A K, Duin R P W, Jianchang Mao. Statistical pattern recognition: a review. Pattern Analysis and Machine Intelligence, 2000. 22(1) : 437. n句法（或結(jié)構(gòu)）模式識別 基于形式語言理論的概念為基礎。模式按其結(jié)構(gòu)分解為子模式或模式基元，模式基元的連接關(guān)系以文法形式進行描述。一個場景的示意圖 場景結(jié)構(gòu)的分析 n模糊模式識別模糊集理論，Zadeh，1965模糊集理論在模式識別中的應用n神經(jīng)網(wǎng)絡模式識別特點：具有信息分布式存儲、大規(guī)模自適應并行處理、高

5、度的容錯性以及學習能力缺點：實際應用中仍有許多因素需要憑經(jīng)驗確定，比如如何選擇網(wǎng)絡節(jié)點數(shù)、初始權(quán)值和學習步長等；局部極小點問題、過學習與欠學習問題等 n特征選擇特征選擇 所要提取的應當是具有可所要提取的應當是具有可區(qū)別性、可靠區(qū)別性、可靠性、獨立性好性、獨立性好的的少量少量特征特征。因此特征選擇可以看作是一個因此特征選擇可以看作是一個( (從最差從最差的開始的開始) )不斷刪除無用的特征和組合有關(guān)聯(lián)不斷刪除無用的特征和組合有關(guān)聯(lián)的特征的過程，直到特征的數(shù)目減少到易的特征的過程，直到特征的數(shù)目減少到易于駕馭的程度，同時分類器的性能仍能滿于駕馭的程度，同時分類器的性能仍能滿足要求為止。足要求為止。

6、 n每類的每一個特征均值：每類的每一個特征均值： 假設訓練樣本中有個不同類別的樣本。令假設訓練樣本中有個不同類別的樣本。令表示第類的樣本數(shù)，第類中第個樣本的兩表示第類的樣本數(shù)，第類中第個樣本的兩個特征分別記為和。個特征分別記為和。每類的每一個特征均值：每類的每一個特征均值：和和注意：僅是兩個值基于訓練樣本的估計值，而不是注意：僅是兩個值基于訓練樣本的估計值，而不是真實的類均值。真實的類均值。MjNjjiijxijyjNiijjxjxN11jNiijjyjyN11n特征方差特征方差第類的特征和特征的方差估值第類的特征和特征的方差估值分別為：分別為： 和和 在理想情況下同一類別中所有對象的在理想情

7、況下同一類別中所有對象的特征值應該很相近。特征值應該很相近。 jxyjNixjijjxjxN122)(1jNiyjijjyjyN122)(1n特征相關(guān)系數(shù)特征相關(guān)系數(shù)第類特征和特征的相關(guān)系數(shù)估計為第類特征和特征的相關(guān)系數(shù)估計為 它的取值范圍為。它的取值范圍為。如果如果=0=0，說明這兩特征之間沒有相關(guān)性；接近，說明這兩特征之間沒有相關(guān)性；接近+1+1表示這兩個特征相關(guān)性強；為表示這兩個特征相關(guān)性強；為-1-1表示任一特征都與表示任一特征都與另一特征的負值成正比。另一特征的負值成正比。因此，因此，如果相關(guān)系數(shù)的絕對值接近如果相關(guān)系數(shù)的絕對值接近1 1，則說明這兩，則說明這兩個特征可以組合在一個特

8、征或干脆舍棄其中一個。個特征可以組合在一個特征或干脆舍棄其中一個。jxyyjxjNiyjijxjijjxyjjyxN)(11 1, 1n類間距離類間距離一個特征區(qū)分兩類能力的一個指標是類間距離，一個特征區(qū)分兩類能力的一個指標是類間距離，即類均值間的方差歸一化間距。顯然，即類均值間的方差歸一化間距。顯然，類間距離大類間距離大的特征是好特征的特征是好特征。對特征來說，第類與第類之間的類間距為：對特征來說，第類與第類之間的類間距為：xjk22xkxjxkxjxjkDn降維降維有許多方法可以將兩個特征和合成為有許多方法可以將兩個特征和合成為一個特征，一個簡單的方法是用線性函數(shù)：一個特征，一個簡單的方法

9、是用線性函數(shù)：由于分類器的性能與特征幅值的縮放倍數(shù)由于分類器的性能與特征幅值的縮放倍數(shù)無關(guān)，可以對幅值加以限制，如無關(guān)，可以對幅值加以限制，如因此因此 其中是一個新的變量，它決定和在組其中是一個新的變量，它決定和在組合中的比例。合中的比例。 xyzbyaxz122basincosyxzxy如果訓練樣本集中每一對象都對應于二如果訓練樣本集中每一對象都對應于二維特征空間維特征空間( (即平面即平面) )中的一個點，上中的一個點，上式描述了為所有到在軸式描述了為所有到在軸( (與軸成角與軸成角) )上的投影。顯然應選取使得類間距最大的上的投影。顯然應選取使得類間距最大的或者滿足評價特征質(zhì)量的其它條件

10、的?；蛘邼M足評價特征質(zhì)量的其它條件的。xyzx8.2 8.2 統(tǒng)計模式識別統(tǒng)計模式識別8.2.1 8.2.1 基本概念基本概念這里我們討論數(shù)字特征的識別。其前提這里我們討論數(shù)字特征的識別。其前提是，假定我們所處理的模式每一個樣本都是，假定我們所處理的模式每一個樣本都表示為表示為N N維特征矢量，寫為：維特征矢量，寫為： 顯然，特征矢量顯然，特征矢量 可以表示為可以表示為N N維特維特征矢量空間征矢量空間 中的一個點，這樣統(tǒng)計模中的一個點，這樣統(tǒng)計模式識別的概念及方法就可以在特征空間中式識別的概念及方法就可以在特征空間中予以研究。予以研究。),.,(21Nxxxxxxu模式分類：根據(jù)識別對象的觀

11、測值確定其類別u樣本與樣本空間表示：12,Tnnx xxRxx12,ic u類別與類別空間：c個類別（類別數(shù)已知）u把樣本x x分到哪一類分到哪一類最合理最合理？解決該問？解決該問題的題的理論基礎之一是統(tǒng)計決策理論u決策：是從樣本空間S，到?jīng)Q策空間的一個映射，表示為 D D: S - : S - 假設我們要把一個樣本集合假設我們要把一個樣本集合 分成分成M M類類 ；如上所述，該樣本集合可以表示為如上所述，該樣本集合可以表示為N N維特維特征空間征空間 中的一個點集，它的分類問題中的一個點集，它的分類問題表述為將該特征空間劃分為表述為將該特征空間劃分為M M個子空間，個子空間，每一子空間為一類

12、，子空間中的樣本點屬每一子空間為一類，子空間中的樣本點屬于相應類別。于相應類別。這樣，這樣，分類問題的關(guān)鍵就在于如何找到一分類問題的關(guān)鍵就在于如何找到一個正確子空間劃分，個正確子空間劃分，即劃分子空間的界面。即劃分子空間的界面。 ,.,21xxM,.,21x下圖為二維特征空間，三類問題。下圖為二維特征空間，三類問題。 u決策區(qū)域與決策面數(shù)學上，統(tǒng)計模式識別問題可以歸結(jié)為：對一數(shù)學上，統(tǒng)計模式識別問題可以歸結(jié)為：對一組給定的樣本集合，找出其最佳的分類判決函組給定的樣本集合，找出其最佳的分類判決函數(shù)數(shù) ，并作判決：并作判決：若對所有的若對所有的 均有：均有： 則作判決：則作判決： MiDi,.,2

13、 , 1, Mjij,.,2 , 1,)()(xDxDjiix因為處理的是分類問題，因此最佳的意義因為處理的是分類問題，因此最佳的意義是分類誤差最小。是分類誤差最小。 由于求解最佳判決函數(shù)的出發(fā)點和途徑不同由于求解最佳判決函數(shù)的出發(fā)點和途徑不同，因此產(chǎn)生了各種不同的分類方法：，因此產(chǎn)生了各種不同的分類方法： 判別函數(shù)方法判別函數(shù)方法貝葉斯分類器貝葉斯分類器：判別函數(shù)表示為似然比，也稱：判別函數(shù)表示為似然比，也稱為為最大似然率分類器或最小損失分類器最大似然率分類器或最小損失分類器集群分類方法集群分類方法：它幾乎不需要有關(guān)待分樣本的：它幾乎不需要有關(guān)待分樣本的先驗知識。先驗知識。 u分類器是某種由

14、硬件或軟件組成的“機器”：計算c個判別函數(shù)gi(x)最大值選擇ARGMAXg1.g2gc.x1x2xna(x)8.2.2 8.2.2 判別函數(shù)方法判別函數(shù)方法在很多分類問題中，往往必須知道待分樣本在很多分類問題中，往往必須知道待分樣本的先驗知識。這里假設我們已經(jīng)知道判別函數(shù)的的先驗知識。這里假設我們已經(jīng)知道判別函數(shù)的形式，剩下的問題是如何求判別函數(shù)的待定參量形式，剩下的問題是如何求判別函數(shù)的待定參量以及進行分類判決。誠然，由分類者隨心所欲地以及進行分類判決。誠然，由分類者隨心所欲地選擇判別函數(shù)的形式，是件快事。但是，類別函選擇判別函數(shù)的形式，是件快事。但是，類別函數(shù)選擇不合適，會導致分類誤差的

15、增加。數(shù)選擇不合適，會導致分類誤差的增加。一、一、 線性判別函數(shù)線性判別函數(shù)線性判別函數(shù)的一般形式為：線性判別函數(shù)的一般形式為： 其中，其中， ， 分別稱為擴充了的特征矢量和權(quán)矢量。分別稱為擴充了的特征矢量和權(quán)矢量。xAaxaxaxaxDtNNNi12211.)(21) 1 ,.,(Nxxxx ),.,(121nNtaaaaA使用線性判別函數(shù)的分類判決有下述兩種情況：使用線性判別函數(shù)的分類判決有下述兩種情況：l 第一種情況第一種情況：每一類可以用一個判決平面與其它所有類隔開，每一類可以用一個判決平面與其它所有類隔開，在這種情況下，有在這種情況下，有M M個判決函數(shù)：個判決函數(shù)： 其它x若xAx

16、Diti00)(l 第二種情況第二種情況：每一類與其它所有各類可以由不同的判決平面每一類與其它所有各類可以由不同的判決平面一一隔開，也就是說，各類是可分段可分的，一一隔開，也就是說，各類是可分段可分的，共有共有 個判決面。個判決面。 判決函數(shù)可以寫成判決函數(shù)可以寫成 若對于所有的若對于所有的 均有：均有： 則作判決：則作判決： 2) 1(MM)()(xDxAxDjiijijMjij,.,2 , 1,0)(xDijix在判決函數(shù)完全獲得定義之后，分類器的設計才在判決函數(shù)完全獲得定義之后，分類器的設計才算結(jié)束，可以用于分類。通常，線性判別函數(shù)中算結(jié)束，可以用于分類。通常，線性判別函數(shù)中的權(quán)系數(shù)的權(quán)

17、系數(shù) 是用訓練或稱學習的方法獲得的。是用訓練或稱學習的方法獲得的。為了討論上的方便，先考慮兩類問題。為了討論上的方便，先考慮兩類問題。 tA所謂訓練，就是給定一組已經(jīng)所謂訓練，就是給定一組已經(jīng)標定好類號的訓練樣本，求出判別函標定好類號的訓練樣本，求出判別函數(shù)中的各參數(shù)。若以數(shù)中的各參數(shù)。若以 表示第一類的表示第一類的訓練樣本，以訓練樣本，以 表示第二類的訓練樣表示第二類的訓練樣本，則對所有訓練樣本，有本，則對所有訓練樣本，有 以及以及 求解這一系列不等式，就可以求解這一系列不等式，就可以解得權(quán)系數(shù)解得權(quán)系數(shù)A。 1Y2Y01YA02YA這顯然是線性判決函數(shù)，前面所述的線性這顯然是線性判決函數(shù)，

18、前面所述的線性判別函數(shù)的各種處理方法也適用于最小距判別函數(shù)的各種處理方法也適用于最小距離分類器。離分類器。 下圖是最近鄰域分類器的一個例子。下圖是最近鄰域分類器的一個例子。當然，判別函數(shù)的形式可以取其它很當然，判別函數(shù)的形式可以取其它很多種形式，例如高次多項式等。多種形式，例如高次多項式等。u以兩類分類問題為例：已知先驗分布P(i)和觀測值的類條件分布p(x|i)，i=1,2問題問題：對某個樣本x，抉擇x 1? x 2？( )(| )iigPxxu該決策使得在觀測值x下的條件錯誤率P(e|x)最小。 Bayes決策理論是最優(yōu)的。u以后驗概率為判決函數(shù)：u決策規(guī)則：argmax(| )iijPx

19、即選擇P(1|x)，P(2|x)中最大值對應的類作為決策結(jié)果后驗概率P (i| x)的計算uBayes公式： 假設已知先驗概率P(i)和觀測值的類條件概率密度函數(shù)p(x|i)，i=1,2。(, )(| )( )() ( |)() ( |)iiiijjjPPpPpPpxxxxxu比較大小不需要計算p(x)：argmax(| )( |) ()argmaax( )rgmax( |) ()iiiiiiiiPpPPppxxxxu對數(shù)域中計算，變乘為加：ln ( | ) ( ) ln ( | ) ln ( )iiiipPpPxx判別函數(shù)中與類別i無關(guān)的項，對于類別的決策沒有影響，可以忽略。Bayes最小錯

20、誤率決策例解u兩類細胞識別問題：正常(1)和異常(2)u根據(jù)已有知識和經(jīng)驗，兩類的先驗概率為：正常(1)： P(1)=0.9異常(2)： P(2)=0.1對某一樣本觀察值x，通過計算或查表得到： p(x|1)=0.2， p(x|2)=0.4u如何對細胞x進行分類？u利用貝葉斯公式計算兩類的后驗概率：11121() ( |)0.90.2(| )0.8 0.4() ( |)jjjPpPPpxxx22221() ( |)0.40.1(| )0.180.1() ( |)jjjPpPPpxxxargmax(| )1iijPx1x決策結(jié)果p(x|1)p(x|2)p

21、(1|x)p(2|x)類條件概率密度函數(shù)后驗概率決策的錯誤率u條件錯誤率：( | )P e x( )( ( | )( | ) ( )P eE P eP epdxxxx（平均）錯誤率是條件錯誤率的數(shù)學期望u（平均）錯誤率u條件錯誤率P(e|x)的計算:以兩類問題為例，當獲得觀測值x后，有兩種決策可能：判定 x1 ，或者x2。u條件錯誤率為：211122(| ) 1(| )( | )(| ) 1(| )1 max (| )iiPPP ePPP xxxxxxxx若決定若決定uBayes最小錯誤率決策使得每個觀測值下的條件錯誤率最小，因而保證了（平均）錯誤率最小。uBayes決策是一致最優(yōu)決策。u設t

22、為兩類的分界面，則在特征向量x是一維時，t為x軸上的一點。形成兩個決策區(qū)域:R1(-，t)和R2(t，+)12122121212122112211( )(,)(,)() (|)() (|)()( |)()( |)()( )()( )RRP eP xRP xRPP xRPP xRPp xdxPp xdxPP ePP en例子012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910http:/ 自動化學院首頁 教學工作 教學下載 課程講義下載 圖象處理 課件與大作

23、業(yè)網(wǎng)址：8.3.1 形式語言的基本概念形式語言的基本概念形式語言最初的設想是實現(xiàn)計算機的形式語言最初的設想是實現(xiàn)計算機的自然語言自然語言(如英語如英語)理解，這一設想雖然理解，這一設想雖然至今尚未全部完成，但是，在形式語言至今尚未全部完成，但是，在形式語言的基礎上，成功地建立起學科分支：編的基礎上，成功地建立起學科分支：編譯器設計、自動機理論、計算機語言以譯器設計、自動機理論、計算機語言以及我們現(xiàn)在討論的句法模式識別。這里及我們現(xiàn)在討論的句法模式識別。這里僅就與句法模式識別有關(guān)的基本概念作僅就與句法模式識別有關(guān)的基本概念作一介紹。一介紹。一、一、 基本定義基本定義字符集字符集是一任意的有限符號

24、集合。在某一是一任意的有限符號集合。在某一字符集上的字符集上的句子句子是任一有限長度字符串，該是任一有限長度字符串，該字符串由取自于這一字符集上的字符組成。字符串由取自于這一字符集上的字符組成。如，給定一字符集如，給定一字符集0,1，它上面的有效句，它上面的有效句子集合為：子集合為：0,1,00,01,10,.。語言語言定義為某一字符集上的任一句子集合，該定義為某一字符集上的任一句子集合，該集合不一定是有限的。集合不一定是有限的。給定了字符集、句子、語言的基本定義之后，給定了字符集、句子、語言的基本定義之后，僅僅明確了下述問題：字符組成句子，句子組僅僅明確了下述問題：字符組成句子，句子組成語言

25、。字符究竟是按照什么規(guī)則組成句子，成語言。字符究竟是按照什么規(guī)則組成句子，進而組成語言？這有待于對語法的研究。與任進而組成語言？這有待于對語法的研究。與任何一種自然語言一樣，語法在形式語言中起中何一種自然語言一樣，語法在形式語言中起中心作用。心作用。句法模式識別中的各個環(huán)節(jié)，都是圍句法模式識別中的各個環(huán)節(jié)，都是圍繞著語法進行研究的繞著語法進行研究的。 8.3.2 高維語法高維語法 經(jīng)典形式語言中定義的語法，原是為自經(jīng)典形式語言中定義的語法，原是為自然語言理解設計的，因此，它只處理字符然語言理解設計的，因此，它只處理字符串組成的語言。字符串是一維級聯(lián)的，難串組成的語言。字符串是一維級聯(lián)的，難以表

26、達結(jié)構(gòu)信息，為了更好地描述物體的以表達結(jié)構(gòu)信息，為了更好地描述物體的各部分空間聯(lián)接關(guān)系，提出了不少高維語各部分空間聯(lián)接關(guān)系，提出了不少高維語法。這里簡單介紹圖像描述語言法。這里簡單介紹圖像描述語言(PDL)和樹和樹語法。語法。一、一、 圖像描述語言圖像描述語言(PDL)圖像描述語言主要用于圖形形狀結(jié)構(gòu)，圖像描述語言主要用于圖形形狀結(jié)構(gòu)，其基元是有向線段，該線段有頭和尾，其基元是有向線段，該線段有頭和尾，線段之間的連接方式與矢量運算相仿。線段之間的連接方式與矢量運算相仿。表示成圖中的加、表示成圖中的加、“x”乘和乘和“*”乘。乘。例子：例子：),(SPVVGTN,4321AAAASVN,dcba

27、VT21AAScAA31baA243AdA)(4dcA其中其中“ ”表示有向線段表示有向線段d的反向。顯然，的反向。顯然，該語法產(chǎn)生的語言是：該語法產(chǎn)生的語言是： 它描述的圖形結(jié)構(gòu)為它描述的圖形結(jié)構(gòu)為d*)(*)(cbadcdP：8.4 8.4 模糊模式識別簡介模糊模式識別簡介 在現(xiàn)實世界中，模糊性和隨機性是兩大不確定在現(xiàn)實世界中，模糊性和隨機性是兩大不確定性。盡管兩者有本質(zhì)的區(qū)別，但是，二者之間卻可性。盡管兩者有本質(zhì)的區(qū)別，但是，二者之間卻可以相互交叉。同一研究對象往往不僅含有模糊性而以相互交叉。同一研究對象往往不僅含有模糊性而且含有隨機性。例如，人們說常且含有隨機性。例如，人們說?！懊魈焓呛锰鞖獾拿魈焓呛锰鞖獾目赡苄杂卸啻罂赡苄杂卸啻蟆?，“他交好運的概率很小他交好運的概率很小”，“他他很少能較早來上班很少能較早來上班”，這里，這里