圖像識別簡介

1、圖 像描 述圖像處理圖像識別圖像理解計算機圖形學 圖像識別圖像識別 運用模式識別的原理對圖像對象進行分類的學問。運用模式識別的原理對圖像對象進行分類的學問。模式識別系統(tǒng)模式識別系統(tǒng)（1）信息的獲取 通過傳感器，將光或聲等信息轉化為電信息。（2）預處理： A、信號增強：去除噪聲，加強有用信息。 信號恢復：對退化現(xiàn)象進行復原。 B、歸一化處理 （例如圖像大小的歸一化； 神經(jīng)網(wǎng)絡輸入數(shù)據(jù)的歸一化）（3）特征提取和特征選擇 A、特征分類：物理特征、結構特征、數(shù)學特征。 B、特征形成：根據(jù)被識別的對象產(chǎn)生出一組基本特征，它可以是計算出來的（當識別對象是波形或數(shù)字圖像時），也可以是用儀表或傳感器測量出來的

2、（當識別對象是事物或某種過程時），這樣產(chǎn)生的特征叫做原始特征。 C、特征提?。涸继卣鞯臄?shù)量可能很大，通過映射（或變換）的方法可以用低維空間表示樣本，這個過程叫做特征提取。映射后的二次特征是原始特征的線性組合（通常是線性組合）。 D、特征選擇：從一組特征中挑選出一些最有效的特征以達到降低特征空間維數(shù)的過程。 例如：一幅96x64的圖象（a）Gabor濾波器編碼；（b）小波變換+神經(jīng)網(wǎng)絡；（c）細節(jié)點 （分叉點、端點）（4）分類器設計 分類器設計的主要功能是通過訓練確定判決規(guī)則，使按此類判決規(guī)則分類時，錯誤率最低或風險最小。（5）分類決策 在特征空間中對被識別對象進行分類。思考題： 水果（如蘋果

3、和桔子） 圖像自動識別系統(tǒng)：選擇那些有效特征，可以把蘋果和桔子有效地區(qū)分開來？3 模式識別的基本問題模式識別的基本問題（1）特征如何提取？-特征產(chǎn)生特征產(chǎn)生（2）最有效的特征是那些特征？-特征選擇特征選擇（3）對特定任務，如何設計分類器？ -分類器設計分類器設計（4）分類器設計后，如何評價分類器？分類錯誤率是多少？ -分類器評價分類器評價模式傳感器 特征產(chǎn)生 特征選擇分類器設計分類器評價設計流程n典型模式識別系統(tǒng)典型模式識別系統(tǒng) n圖像識別系統(tǒng)圖像識別系統(tǒng) 圖像識別概念n人臉識別系統(tǒng)圖像識別圖像識別概述概述n模式模式可以定義為可以定義為物體的描述物體的描述。由于描述這個。由于描述這個詞的意義比

4、較廣泛，有人把它推廣到圖像數(shù)詞的意義比較廣泛，有人把它推廣到圖像數(shù)據(jù)本身，因為圖像數(shù)據(jù)也是相應事物的一種據(jù)本身，因為圖像數(shù)據(jù)也是相應事物的一種描述，只不過這樣的描述不夠抽象和簡要而描述，只不過這樣的描述不夠抽象和簡要而已。已。基于圖像匹配的圖像識別基于圖像匹配的圖像識別 1 定義定義 根據(jù)已知模式到另一幅圖中尋找相應的模式。2 基于相關的模板匹配基于相關的模板匹配 10210102101010),(),(),(),(),(KkJjKkJjKkJjkjtkyjxfkyjxfkjtyxR3 基于誤差平方和的模板匹配基于誤差平方和的模板匹配 10102),(),(),(JjKkkjtkyjxfyxD

5、4、特征模板匹配、特征模板匹配5、 特征匹配特征匹配 WjmxxDWjxNmjjxjjj, 2 , 1)(, 2 , 11n模式可以是以模式可以是以矢量形式矢量形式表示的表示的數(shù)字特征數(shù)字特征；也可以是以也可以是以句法結構句法結構表示的表示的字符串或圖字符串或圖；還可以是以還可以是以關系結構關系結構表示的表示的語義網(wǎng)絡或框語義網(wǎng)絡或框架結構架結構等。等。n對于上述三種類型的模式，必須分別使用不對于上述三種類型的模式，必須分別使用不同的識別和推理方法：同的識別和推理方法：統(tǒng)計模式識別，句法統(tǒng)計模式識別，句法模式識別模式識別和和人工智能方法人工智能方法。 n統(tǒng)計模式識別基本原理是：有相似性的樣本在

6、模式空間中互相接近，并形成“集團”，即“物以類聚”。主要方法有：決策函數(shù)法， k近鄰分類法，支持向量機，特征分析法，主因子分析法等參考書籍：統(tǒng)計模式識別(Andrew R.Webb) Jain A K, Duin R P W, Jianchang Mao. Statistical pattern recognition: a review. Pattern Analysis and Machine Intelligence, 2000. 22(1) : 437. n句法（或結構）模式識別 基于形式語言理論的概念為基礎。模式按其結構分解為子模式或模式基元，模式基元的連接關系以文法形式進行描述。一

7、個場景的示意圖 場景結構的分析 n模糊模式識別模糊集理論，Zadeh，1965模糊集理論在模式識別中的應用n神經(jīng)網(wǎng)絡模式識別特點：具有信息分布式存儲、大規(guī)模自適應并行處理、高度的容錯性以及學習能力缺點：實際應用中仍有許多因素需要憑經(jīng)驗確定，比如如何選擇網(wǎng)絡節(jié)點數(shù)、初始權值和學習步長等；局部極小點問題、過學習與欠學習問題等 n特征選擇特征選擇 所要提取的應當是具有可所要提取的應當是具有可區(qū)別性、可靠區(qū)別性、可靠性、獨立性好性、獨立性好的的少量少量特征特征。因此特征選擇可以看作是一個因此特征選擇可以看作是一個( (從最差從最差的開始的開始) )不斷刪除無用的特征和組合有關聯(lián)不斷刪除無用的特征和組合

8、有關聯(lián)的特征的過程，直到特征的數(shù)目減少到易的特征的過程，直到特征的數(shù)目減少到易于駕馭的程度，同時分類器的性能仍能滿于駕馭的程度，同時分類器的性能仍能滿足要求為止。足要求為止。 n每類的每一個特征均值：每類的每一個特征均值： 假設訓練樣本中有個不同類別的樣本。令假設訓練樣本中有個不同類別的樣本。令表示第類的樣本數(shù)，第類中第個樣本的兩表示第類的樣本數(shù)，第類中第個樣本的兩個特征分別記為和。個特征分別記為和。每類的每一個特征均值：每類的每一個特征均值：和和注意：僅是兩個值基于訓練樣本的估計值，而不是注意：僅是兩個值基于訓練樣本的估計值，而不是真實的類均值。真實的類均值。MjNjjiijxijyjNii

9、jjxjxN11jNiijjyjyN11n特征方差特征方差第類的特征和特征的方差估值第類的特征和特征的方差估值分別為：分別為： 和和 在理想情況下同一類別中所有對象的在理想情況下同一類別中所有對象的特征值應該很相近。特征值應該很相近。 jxyjNixjijjxjxN122)(1jNiyjijjyjyN122)(1n特征相關系數(shù)特征相關系數(shù)第類特征和特征的相關系數(shù)估計為第類特征和特征的相關系數(shù)估計為 它的取值范圍為。它的取值范圍為。如果如果=0=0，說明這兩特征之間沒有相關性；接近，說明這兩特征之間沒有相關性；接近+1+1表示這兩個特征相關性強；為表示這兩個特征相關性強；為-1-1表示任一特征都

10、與表示任一特征都與另一特征的負值成正比。另一特征的負值成正比。因此，因此，如果相關系數(shù)的絕對值接近如果相關系數(shù)的絕對值接近1 1，則說明這兩，則說明這兩個特征可以組合在一個特征或干脆舍棄其中一個。個特征可以組合在一個特征或干脆舍棄其中一個。jxyyjxjNiyjijxjijjxyjjyxN)(11 1, 1n類間距離類間距離一個特征區(qū)分兩類能力的一個指標是類間距離，一個特征區(qū)分兩類能力的一個指標是類間距離，即類均值間的方差歸一化間距。顯然，即類均值間的方差歸一化間距。顯然，類間距離大類間距離大的特征是好特征的特征是好特征。對特征來說，第類與第類之間的類間距為：對特征來說，第類與第類之間的類間距

11、為：xjk22xkxjxkxjxjkD統(tǒng)計模式識別統(tǒng)計模式識別基本概念基本概念這里我們討論數(shù)字特征的識別。其前提這里我們討論數(shù)字特征的識別。其前提是，假定我們所處理的模式每一個樣本都是，假定我們所處理的模式每一個樣本都表示為表示為N N維特征矢量，寫為：維特征矢量，寫為： 顯然，特征矢量顯然，特征矢量 可以表示為可以表示為N N維特維特征矢量空間征矢量空間 中的一個點，這樣統(tǒng)計模中的一個點，這樣統(tǒng)計模式識別的概念及方法就可以在特征空間中式識別的概念及方法就可以在特征空間中予以研究。予以研究。),.,(21Nxxxxxxu模式分類：根據(jù)識別對象的觀測值確定其類別u樣本與樣本空間表示：12,Tnn

12、x 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個子空間，個子空間，每一子空間為一類，子空間中的樣本點屬每一子空間為一類，子空間中的

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

14、DxDjiix因為處理的是分類問題，因此最佳的意義因為處理的是分類問題，因此最佳的意義是分類誤差最小。是分類誤差最小。 由于求解最佳判決函數(shù)的出發(fā)點和途徑不同由于求解最佳判決函數(shù)的出發(fā)點和途徑不同，因此產(chǎn)生了各種不同的分類方法：，因此產(chǎn)生了各種不同的分類方法： 判別函數(shù)方法判別函數(shù)方法貝葉斯分類器貝葉斯分類器：判別函數(shù)表示為似然比，也稱：判別函數(shù)表示為似然比，也稱為為最大似然率分類器或最小損失分類器最大似然率分類器或最小損失分類器集群分類方法集群分類方法：它幾乎不需要有關待分樣本的：它幾乎不需要有關待分樣本的先驗知識。先驗知識。 u分類器是某種由硬件或軟件組成的“機器”：計算c個判別函數(shù)gi(

15、x)最大值選擇ARGMAXg1.g2gc.x1x2xna(x)判別函數(shù)方法判別函數(shù)方法在很多分類問題中，往往必須知道待分樣本在很多分類問題中，往往必須知道待分樣本的先驗知識。這里假設我們已經(jīng)知道判別函數(shù)的的先驗知識。這里假設我們已經(jīng)知道判別函數(shù)的形式，剩下的問題是如何求判別函數(shù)的待定參量形式，剩下的問題是如何求判別函數(shù)的待定參量以及進行分類判決。誠然，由分類者隨心所欲地以及進行分類判決。誠然，由分類者隨心所欲地選擇判別函數(shù)的形式，是件快事。但是，類別函選擇判別函數(shù)的形式，是件快事。但是，類別函數(shù)選擇不合適，會導致分類誤差的增加。數(shù)選擇不合適，會導致分類誤差的增加。一、一、 線性判別函數(shù)線性判別

16、函數(shù)線性判別函數(shù)的一般形式為：線性判別函數(shù)的一般形式為： 其中，其中， ， 分別稱為擴充了的特征矢量和權矢量。分別稱為擴充了的特征矢量和權矢量。xAaxaxaxaxDtNNNi12211.)(21) 1 ,.,(Nxxxx ),.,(121nNtaaaaA使用線性判別函數(shù)的分類判決有下述兩種情況：使用線性判別函數(shù)的分類判決有下述兩種情況：l 第一種情況第一種情況：每一類可以用一個判決平面與其它所有類隔開，每一類可以用一個判決平面與其它所有類隔開，在這種情況下，有在這種情況下，有M M個判決函數(shù)：個判決函數(shù)： 其它x若xAxDiti00)(l 第二種情況第二種情況：每一類與其它所有各類可以由不同

17、的判決平面每一類與其它所有各類可以由不同的判決平面一一隔開，也就是說，各類是可分段可分的，一一隔開，也就是說，各類是可分段可分的，共有共有 個判決面。個判決面。 判決函數(shù)可以寫成判決函數(shù)可以寫成 若對于所有的若對于所有的 均有：均有： 則作判決：則作判決： 2) 1(MM)()(xDxAxDjiijijMjij,.,2 , 1,0)(xDijix在判決函數(shù)完全獲得定義之后，分類器的設計才在判決函數(shù)完全獲得定義之后，分類器的設計才算結束，可以用于分類。通常，線性判別函數(shù)中算結束，可以用于分類。通常，線性判別函數(shù)中的權系數(shù)的權系數(shù) 是用訓練或稱學習的方法獲得的。是用訓練或稱學習的方法獲得的。為了討

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

19、也適用于最小距離分類器。離分類器。 下圖是最近鄰域分類器的一個例子。下圖是最近鄰域分類器的一個例子。當然，判別函數(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即選擇P(1|x)，P(2|x)中最大值對應的類作為決策結果后驗概率P

20、(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無關的項，對于類別的決策沒有影響，可以忽略。Bayes最小錯誤率決策例解u兩類細胞識別問題：正常(1)和異常(2)u根據(jù)已有知識和經(jīng)

21、驗，兩類的先驗概率為：正常(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.8180.90.20.1 0.4() ( |)jjjPpPPpxxx22221() ( |)0.40.1(| )0.1820.20.90.40.1() ( |)jjjPpPPpxxxargmax(| )1iijPx1x決策結果p(x|1)p(x|2)p(1|x)p(2|x)類條件概率密度函數(shù)后驗概率決策的錯誤率u條件錯誤率

22、：( | )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為兩類的分界面，則在特征向量x是一維時，t為x軸上的一點。形成兩個決策區(qū)

23、域:R1(-，t)和R2(t，+)12122121212122112211( )(,)(,)() (|)() (|)()( |)()( |)()( )()( )RRP eP xRP xRPP xRPP xRPp xdxPp xdxPP ePP en例子012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910形式語言的基本概念形式語言的基本概念形式語言最初的設想是實現(xiàn)計算機的形式語言最初的設想是實現(xiàn)計算機的自然語言自然語言(如英語如英語)理解，這一設想雖然理解，

24、這一設想雖然至今尚未全部完成，但是，在形式語言至今尚未全部完成，但是，在形式語言的基礎上，成功地建立起學科分支：編的基礎上，成功地建立起學科分支：編譯器設計、自動機理論、計算機語言以譯器設計、自動機理論、計算機語言以及我們現(xiàn)在討論的句法模式識別。這里及我們現(xiàn)在討論的句法模式識別。這里僅就與句法模式識別有關的基本概念作僅就與句法模式識別有關的基本概念作一介紹。一介紹。一、一、 基本定義基本定義字符集字符集是一任意的有限符號集合。在某一是一任意的有限符號集合。在某一字符集上的字符集上的句子句子是任一有限長度字符串，該是任一有限長度字符串，該字符串由取自于這一字符集上的字符組成。字符串由取自于這一字

25、符集上的字符組成。如，給定一字符集如，給定一字符集0,1，它上面的有效句，它上面的有效句子集合為：子集合為：0,1,00,01,10,.。語言語言定義為某一字符集上的任一句子集合，該定義為某一字符集上的任一句子集合，該集合不一定是有限的。集合不一定是有限的。給定了字符集、句子、語言的基本定義之后，給定了字符集、句子、語言的基本定義之后，僅僅明確了下述問題：字符組成句子，句子組僅僅明確了下述問題：字符組成句子，句子組成語言。字符究竟是按照什么規(guī)則組成句子，成語言。字符究竟是按照什么規(guī)則組成句子，進而組成語言？這有待于對語法的研究。與任進而組成語言？這有待于對語法的研究。與任何一種自然語言一樣，語

26、法在形式語言中起中何一種自然語言一樣，語法在形式語言中起中心作用。心作用。句法模式識別中的各個環(huán)節(jié)，都是圍句法模式識別中的各個環(huán)節(jié)，都是圍繞著語法進行研究的繞著語法進行研究的。 高維語法高維語法 經(jīng)典形式語言中定義的語法，原是為自經(jīng)典形式語言中定義的語法，原是為自然語言理解設計的，因此，它只處理字符然語言理解設計的，因此，它只處理字符串組成的語言。字符串是一維級聯(lián)的，難串組成的語言。字符串是一維級聯(lián)的，難以表達結構信息，為了更好地描述物體的以表達結構信息，為了更好地描述物體的各部分空間聯(lián)接關系，提出了不少高維語各部分空間聯(lián)接關系，提出了不少高維語法。這里簡單介紹圖像描述語言法。這里簡單介紹圖像

27、描述語言(PDL)和樹和樹語法。語法。一、一、 圖像描述語言圖像描述語言(PDL)圖像描述語言主要用于圖形形狀結構，圖像描述語言主要用于圖形形狀結構，其基元是有向線段，該線段有頭和尾，其基元是有向線段，該線段有頭和尾，線段之間的連接方式與矢量運算相仿。線段之間的連接方式與矢量運算相仿。表示成圖中的加、表示成圖中的加、“x”乘和乘和“*”乘。乘。例子：例子：),(SPVVGTN,4321AAAASVN,dcbaVT21AAScAA31baA243AdA)(4dcA其中其中“ ”表示有向線段表示有向線段d的反向。顯然，的反向。顯然，該語法產(chǎn)生的語言是：該語法產(chǎn)生的語言是： 它描述的圖形結構為它描述的圖形結構為d*)(*)(cbadcdP：模糊模式識別簡介模糊模式識別簡介 在現(xiàn)實世界中，模糊性和隨機性是兩大不確定在現(xiàn)實世界中，模糊性和隨機性是兩大不確定性。盡管兩者有本質(zhì)的區(qū)別，但是，二者之間卻可性。盡管兩者有本質(zhì)的區(qū)別，但是，二者之間卻可