第十章模式識別

1、第十章第十章 模板匹配與模式識別模板匹配與模式識別10.1 10.1 模板匹配模板匹配 10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 10.4 10.4 結(jié)構(gòu)模式識別法結(jié)構(gòu)模式識別法 10.5 10.5 神經(jīng)網(wǎng)絡識別法神經(jīng)網(wǎng)絡識別法 10.2 10.2 模式識別概念模式識別概念第十章第十章 模板匹配與模式識別模板匹配與模式識別10.1 10.1 模板匹配模板匹配 模板匹配是一種最原始、最基本的模式識別方法。研究某模板匹配是一種最原始、最基本的模式識別方法。研究某特特定對象物的圖案位于圖像的什么地方，進而識別對象物，就是定對象物的圖案位于圖像的什么地方，進而識別對象物，就是一個匹配的問題。一個匹

2、配的問題。通常應用在以下方面： 1. 1. 模板匹配概述模板匹配概述 在幾何變換中，檢測圖像和地圖之間的對應點 不同的光譜或不同的攝影時間所得的圖像之間位置的配準圖像配準) 在立體影象分析中提取左右影象間的對應關(guān)系 運動物體的跟蹤 圖像中對象物位置的檢測等 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.1 10.1 模板匹配模板匹配 如右圖如右圖, ,設檢測對象的模板為設檢測對象的模板為t(xt(x，y)y)，令其中心與圖像令其中心與圖像f(xf(x，y)y)中的一點中的一點(i(i，j)j)重合，檢測重合，檢測t(xt(x，y)y)和圖像重合部分和圖像重合部分之間的相似度，對圖像中

3、所有的點都之間的相似度，對圖像中所有的點都進行這樣的操作，根據(jù)相似度為最大進行這樣的操作，根據(jù)相似度為最大或者超過某或者超過某閾值來確定對象物是否閾值來確定對象物是否存在，并求得對象物所在的位置，即存在，并求得對象物所在的位置，即是模板匹配匹配的基本原理。是模板匹配匹配的基本原理。 2. 2. 模板匹配方法（原理）模板匹配方法（原理） 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.1 10.1 模板匹配模板匹配 2. 2. 模板匹配方法（原理）模板匹配方法（原理） 1 1） 模板匹配模板匹配非相似度度量方法非相似度度量方法) 11 .10(maxtfssdxdytf) 21 .10(

4、) 31 .10()(2dxdytfs式中計算的是模板和圖像重合部分的非相似度，該值越小，表示匹配程度越好。 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.1 10.1 模板匹配模板匹配 2. 2. 模板匹配方法（原理）模板匹配方法（原理） 2 2） 模板匹配模板匹配相似度度量方法相似度度量方法式中，分別表示f(x+u,y+v)，t(x,y)在S內(nèi)的均值，得到的是模板和圖像重合部分相似度，該值越大，表示匹配程度越好。 sdxdyvyuxfyxtvum),(),(),()51 .10(),(),(),(2sdxdyvyuxfvumvum)61 .10(),(),(),()(),(),(

5、22sssdxdytyxtdxdyfvyuxfdxdytyxtfvyuxfvum（10.1-4）第十章第十章 模板匹配與模式識別模板匹配與模式識別10.1 10.1 模板匹配模板匹配 3. 3. 高速模板匹配高速模板匹配 序貫相似性檢測法序貫相似性檢測法SSDASSDA 模板匹配中使用的模板相當大模板匹配中使用的模板相當大(8(88 832323232左右左右) ) ，為提高匹配速度，為提高匹配速度，BarneaBarnea等人提出了序貫相似性檢測法等人提出了序貫相似性檢測法SSDASSDA法法(Sequential Similiarity (Sequential Similiarity De

6、tectionDetection Algorithm)Algorithm) 。 )71 .10(),() 1, 1(),(11nkmtlktvlukfvumSSDA用下式計算圖像f(x，y)在點(u，v)的非相似度m(u,v)作為匹配尺度。式中(u，v)表示的不是模板中心坐標，而是它左上角坐標。模板的大小為 mn。 若在(u，v)處圖像中有和模板一致的圖案時，則m(u,v)值很小，相反則大。 如果在模板內(nèi)的各像素與圖像重合部分對應象素的灰度差的絕對值依次增加下去，其和就會急劇地增大。因此，在做加法的過程中，如果灰度差的絕對值部分和超過了某一閾值時，就認為這位置上不存在和模板致的圖案，從而轉(zhuǎn)移到

7、下一個位置上計算m(u，v) 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.1 10.1 模板匹配模板匹配 3. 3. 高速模板匹配高速模板匹配 粗檢索細檢索兩階段匹配法粗檢索細檢索兩階段匹配法 粗檢索每隔若干個像素把模板和圖像重疊，并計算匹配的尺度，從而每隔若干個像素把模板和圖像重疊，并計算匹配的尺度，從而求出對象物大致存在的范圍求出對象物大致存在的范圍 細檢索這粗檢索檢出范圍內(nèi)，讓模板每隔這粗檢索檢出范圍內(nèi)，讓模板每隔個像素移動一次，根據(jù)求個像素移動一次，根據(jù)求出的匹配尺度確定對象物所在的位置出的匹配尺度確定對象物所在的位置 計算時間縮短，匹配速度就提高了。但是用這種方法具有計算

8、時間縮短，匹配速度就提高了。但是用這種方法具有漏掉圖漏掉圖像中最適當位置的危險性像中最適當位置的危險性 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.1 10.1 模板匹配模板匹配 4. 4. 模板匹配改進模板匹配改進 基于圖案輪廓的特征匹配方法基于圖案輪廓的特征匹配方法 模板匹配的缺陷在一般的圖像中有較強自相關(guān)性，因此，進行模板匹配計算的在一般的圖像中有較強自相關(guān)性，因此，進行模板匹配計算的相似度就在以對象物存在的地方為中心形成平緩的峰。這樣，相似度就在以對象物存在的地方為中心形成平緩的峰。這樣，即使從圖像中對象物的真實位置稍微離開一點，也表現(xiàn)出相當即使從圖像中對象物的真實位置稍微

9、離開一點，也表現(xiàn)出相當高的相似度，即高的相似度，即模板匹配結(jié)果過于平緩模板匹配結(jié)果過于平緩 改進 基于圖案輪廓的特征匹配 用各種模板進行匹配，從而求出最用各種模板進行匹配，從而求出最致的模板及其位置致的模板及其位置 在對象形狀復雜時，把對象分割成幾個分圖案，把各分圖案作為在對象形狀復雜時，把對象分割成幾個分圖案，把各分圖案作為模板進行匹配，研究分圖案之間位置關(guān)系，從而求得對象的位置模板進行匹配，研究分圖案之間位置關(guān)系，從而求得對象的位置 圖案輪廓的匹配與一般的匹配相比較，表現(xiàn)出更尖銳的相似度分布圖案輪廓的匹配與一般的匹配相比較，表現(xiàn)出更尖銳的相似度分布 10.2 圖像（模式）識別概念圖像（模式

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

11、識別的理論和方法論和方法 10.2 圖像（模式）識別概念圖像（模式）識別概念第十章第十章 模板匹配與模式識別模板匹配與模式識別l典型模式識別系統(tǒng)典型模式識別系統(tǒng) l圖像識別系統(tǒng)圖像識別系統(tǒng) 10.2 圖像（模式）識別概念圖像（模式）識別概念第十章第十章 模板匹配與模式識別模板匹配與模式識別l人臉識別系統(tǒng)10.2 圖像（模式）識別概念圖像（模式）識別概念第十章第十章 模板匹配與模式識別模板匹配與模式識別l模式模式可以定義為可以定義為物體的描述物體的描述。由于描述這個詞。由于描述這個詞的意義比較廣泛，有人把它推廣到圖像數(shù)據(jù)本的意義比較廣泛，有人把它推廣到圖像數(shù)據(jù)本身，因為圖像數(shù)據(jù)也是相應事物的一種

12、描述，身，因為圖像數(shù)據(jù)也是相應事物的一種描述，只不過這樣的描述不夠抽象和簡要而已。圖像只不過這樣的描述不夠抽象和簡要而已。圖像的各種特征和描述的提取方法。我們將的各種特征和描述的提取方法。我們將模式解模式解釋為物體的較抽象的特征和描述。釋為物體的較抽象的特征和描述。 10.2 圖像（模式）識別概念圖像（模式）識別概念第十章第十章 模板匹配與模式識別模板匹配與模式識別l模式可以是以模式可以是以矢量矢量 柵格形式柵格形式表示的表示的數(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)

13、結(jié)構(gòu)等。等。l對于上述三種類型的模式，必須分別使用不同對于上述三種類型的模式，必須分別使用不同的識別和推理方法：的識別和推理方法：統(tǒng)計模式識別，句法模式統(tǒng)計模式識別，句法模式識別識別和和人工智能方法人工智能方法。 10.2 圖像（模式）識別概念圖像（模式）識別概念第十章第十章 模板匹配與模式識別模板匹配與模式識別l統(tǒng)計模式識別統(tǒng)計模式識別基本原理是：有相似性的樣本在模式空間中互相接基本原理是：有相似性的樣本在模式空間中互相接近，并形成近，并形成“集團集團”，即，即“物以類聚物以類聚”。主要方法有：決策函數(shù)法，主要方法有：決策函數(shù)法， k近鄰分類法，支持向近鄰分類法，支持向量機，特征分析法，主因

14、子分析法等量機，特征分析法，主因子分析法等10.2 圖像（模式）識別概念圖像（模式）識別概念第十章第十章 模板匹配與模式識別模板匹配與模式識別l句法（或結(jié)構(gòu)）模式識別 基于形式語言理論的概念為基礎(chǔ)。模式按其結(jié)構(gòu)分解為子模式或模式基元，模式基元的連接關(guān)系以文法形式進行描述。一個場景的示意圖 場景結(jié)構(gòu)的分析 10.2 圖像（模式）識別概念圖像（模式）識別概念第十章第十章 模板匹配與模式識別模板匹配與模式識別l模糊模式識別模糊模式識別模糊集理論，模糊集理論，Zadeh，1965模糊集理論在模式識別中的應用模糊集理論在模式識別中的應用l神經(jīng)網(wǎng)絡模式識別神經(jīng)網(wǎng)絡模式識別特點：具有信息分布式存儲、大規(guī)模自

15、適應并行處理、高度的特點：具有信息分布式存儲、大規(guī)模自適應并行處理、高度的容錯性以及學習能力容錯性以及學習能力缺點：缺點：實際應用中仍有許多因素需要憑經(jīng)驗確定，比如如何選實際應用中仍有許多因素需要憑經(jīng)驗確定，比如如何選擇網(wǎng)絡節(jié)點數(shù)、初始權(quán)值和學習步長等；局部極小點問題、過擇網(wǎng)絡節(jié)點數(shù)、初始權(quán)值和學習步長等；局部極小點問題、過學習與欠學習問題等學習與欠學習問題等 10.2 圖像（模式）識別概念圖像（模式）識別概念第十章第十章 模板匹配與模式識別模板匹配與模式識別l特征選擇特征選擇 所要提取的應當是具有可所要提取的應當是具有可區(qū)別性、可靠性、區(qū)別性、可靠性、獨立性好獨立性好的的少量少量特征特征。因

16、此特征選擇可以看作是一個因此特征選擇可以看作是一個( (從最差的從最差的開始開始) )不斷刪除無用的特征和組合有關(guān)聯(lián)的特不斷刪除無用的特征和組合有關(guān)聯(lián)的特征的過程，直到特征的數(shù)目減少到易于駕馭的征的過程，直到特征的數(shù)目減少到易于駕馭的程度，同時分類器的性能仍能滿足要求為止。程度，同時分類器的性能仍能滿足要求為止。 l每類的每一個特征均值：每類的每一個特征均值： 假設訓練樣本中有個不同類別的樣本。令表示假設訓練樣本中有個不同類別的樣本。令表示第類的樣本數(shù)，第類中第個樣本的兩個特征分第類的樣本數(shù)，第類中第個樣本的兩個特征分別記為和。別記為和。每類的每一個特征均值：每類的每一個特征均值：和和注意：僅

17、是兩個值基于訓練樣本的估計值，而不是真實注意：僅是兩個值基于訓練樣本的估計值，而不是真實的類均值。的類均值。MjNjjiijxijyjNiijjxjxN11jNiijjyjyN1110.2 圖像（模式）識別概念圖像（模式）識別概念第十章第十章 模板匹配與模式識別模板匹配與模式識別l特征方差特征方差第類的特征和特征的方差估值分第類的特征和特征的方差估值分別為：別為： 和和 在理想情況下同一類別中所有對象的特在理想情況下同一類別中所有對象的特征值應該很相近。征值應該很相近。 jxyjNixjijjxjxN122)(1jNiyjijjyjyN122)(110.2 圖像（模式）識別概念圖像（模式）識別

18、概念第十章第十章 模板匹配與模式識別模板匹配與模式識別l特征相關(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，則說明這兩個特，則說明這兩個特征可以組合在一個特征或干脆舍棄其中一個。征可以組合在一個特征或干脆舍棄其中一個。jxyyjxjNiy

19、jijxjijjxyjjyxN)(11 1, 110.2 圖像（模式）識別概念圖像（模式）識別概念第十章第十章 模板匹配與模式識別模板匹配與模式識別l類間距離類間距離一個特征區(qū)分兩類能力的一個指標是類間距離，即類一個特征區(qū)分兩類能力的一個指標是類間距離，即類均值間的方差歸一化間距。顯然，均值間的方差歸一化間距。顯然，類間距離大的特征是類間距離大的特征是好特征好特征。對特征來說，第類與第類之間的類間距為：對特征來說，第類與第類之間的類間距為：xjk22xkxjxkxjxjkD10.2 圖像（模式）識別概念圖像（模式）識別概念第十章第十章 模板匹配與模式識別模板匹配與模式識別基本概念基本概念這里我

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

21、12,Tnnx xxRxx12,ic u類別與類別空間：c個類別（類別數(shù)已知）第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 u把樣本x x分到哪一類分到哪一類最合理最合理？解決該問？解決該問題的題的理論基礎(chǔ)之一是統(tǒng)計決策理論u決策：是從樣本空間S，到?jīng)Q策空間的一個映射，表示為 D D: S - : S - 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 假設我們要把一個樣本集合假設我們要把一個樣本集合 分成分成M M類類 ；如上所述，該樣本集合可以表示為如上所述，該樣本集合可以表示為N N維特征空

22、間維特征空間 中的一個點集，它的分類問題表述為將該特征中的一個點集，它的分類問題表述為將該特征空間劃分為空間劃分為M M個子空間，每一子空間為一類，子個子空間，每一子空間為一類，子空間中的樣本點屬于相應類別。空間中的樣本點屬于相應類別。這樣，這樣，分類問題的關(guān)鍵就在于如何找到一個正分類問題的關(guān)鍵就在于如何找到一個正確子空間劃分，確子空間劃分，即劃分子空間的界面。即劃分子空間的界面。 ,.,21xxM,.,21x第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 下圖為二維特征空間，三類問題。下圖為二維特征空間，三類問題。 第十章第十章 模板匹配與模式

23、識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 u決策區(qū)域與決策面第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 數(shù)學上，統(tǒng)計模式識別問題可以歸結(jié)為：對一數(shù)學上，統(tǒng)計模式識別問題可以歸結(jié)為：對一組給定的樣本集合，找出其最佳的分類判決函組給定的樣本集合，找出其最佳的分類判決函數(shù)數(shù) ，并作判決：并作判決：若對所有的若對所有的 均有：均有： 則作判決：則作判決： MiDi,.,2 , 1, Mjij,.,2 , 1,)()(xDxDjii

24、x第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 因為處理的是分類問題，因此最佳的意義因為處理的是分類問題，因此最佳的意義是分類誤差最小。是分類誤差最小。 由于求解最佳判決函數(shù)的出發(fā)點和途徑不同由于求解最佳判決函數(shù)的出發(fā)點和途徑不同，因此產(chǎn)生了各種不同的分類方法：，因此產(chǎn)生了各種不同的分類方法： 判別函數(shù)方法判別函數(shù)方法貝葉斯分類器貝葉斯分類器：判別函數(shù)表示為似然比，也稱：判別函數(shù)表示為似然比，也稱為為最大似然率分類器或最小損失分類器最大似然率分類器或最小損失分類器集群分類方法集群分類方法：它幾乎不需要有關(guān)待分樣本的：它幾乎不需要有關(guān)待分樣本的先

25、驗知識。先驗知識。 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 u分類器是某種由硬件或軟件組成的“機器”：計算c個判別函數(shù)gi(x)最大值選擇ARGMAXg1.g2gc.x1x2xna(x)第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 基本過程基本過程統(tǒng)計模式識別統(tǒng)計模式識別是研究每是研究每個模式的各種測量數(shù)據(jù)的統(tǒng)計特性，按照統(tǒng)個模式的各種測量數(shù)據(jù)的統(tǒng)計特性，按照統(tǒng)計決策理論來進行分類計決策理論來進

26、行分類 統(tǒng)計模式識別過程統(tǒng)計模式識別過程分為識別和分類兩部分，核心內(nèi)容為分為識別和分類兩部分，核心內(nèi)容為特征處理特征處理與與分類分類 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 特征處理特征處理 包括特征選擇和特征變換：包括特征選擇和特征變換： 特征選擇方法特征選擇特征選擇指的是從原有的指的是從原有的m m個測量值集合中，按某一準則選擇出一個測量值集合中，按某一準則選擇出一個個n n維維(n(nm)m)的子集作為分類特征的子集作為分類特征 窮舉法窮舉法從從m m個原始的測量值中選出個原始的測量值中選出n n個特征，個特征，共有共有C Cm m

27、n n種可能的選擇。種可能的選擇。對每一種選法用己知類別屬性的樣本進行試分類，測出其正確分對每一種選法用己知類別屬性的樣本進行試分類，測出其正確分類率，分類誤差最小的一組特征便是最好的選擇類率，分類誤差最小的一組特征便是最好的選擇 優(yōu)點是不僅能提供最優(yōu)的特征子集，而且可以全面了解所有特征對各類別之間的可分性信息。但是，計算量太大，特別在特征維數(shù)高時，計算更繁 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 最大最小類對距離法最大最小類對距離法 首先在首先在K K個類別中選出最難分離的一對類別，個類別中選出最難分離的一對類別，然后選擇不同的特征子集

28、，計算這一對類別的可分性，然后選擇不同的特征子集，計算這一對類別的可分性，具有最大可分性的特征子集就是該方法所選擇的最佳具有最大可分性的特征子集就是該方法所選擇的最佳特征子集特征子集 特征選擇方法不改變原始測量值的物理意義，因此它不會影響分類器設計者對所用待征的認識，有利于分類器的設計，便于分類結(jié)果的進一步分析 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 特征變換特征變換特征變換是將原有的是將原有的m m個測量值集合通過某種變換，然后產(chǎn)生個測量值集合通過某種變換，然后產(chǎn)生n n個個(n(nm)m)特征用于分類。特征變換又分為兩種情況：特征用于

29、分類。特征變換又分為兩種情況： 一種，從減少特征之間相關(guān)性和濃縮信息量的角度出發(fā)，根據(jù)原一種，從減少特征之間相關(guān)性和濃縮信息量的角度出發(fā)，根據(jù)原始數(shù)據(jù)的統(tǒng)計特性，用數(shù)學的處理方法使得用盡量少的特征來最始數(shù)據(jù)的統(tǒng)計特性，用數(shù)學的處理方法使得用盡量少的特征來最大限度地包含所有原始數(shù)據(jù)的信息。這種方法不涉及具體模式類大限度地包含所有原始數(shù)據(jù)的信息。這種方法不涉及具體模式類別的分布情況，因此，對于沒有類別先驗知識的情況，這是別的分布情況，因此，對于沒有類別先驗知識的情況，這是種種有效的特征變換方式。主分量變換就屬于這一類型有效的特征變換方式。主分量變換就屬于這一類型 另一類，根據(jù)對測量值所反映的物理現(xiàn)

30、象與待分類別之間關(guān)系的另一類，根據(jù)對測量值所反映的物理現(xiàn)象與待分類別之間關(guān)系的認識，通過數(shù)學運算來產(chǎn)生認識，通過數(shù)學運算來產(chǎn)生組新的特征，使得待分類別之間的組新的特征，使得待分類別之間的差異在這組特征中更明顯，從而有利于改善分類效果差異在這組特征中更明顯，從而有利于改善分類效果 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 . . 統(tǒng)計分類方法統(tǒng)計分類方法 v 監(jiān)督分類監(jiān)督分類方法監(jiān)督分類方法就是根據(jù)預先已知類別名的訓練樣本，求出各類在就是根據(jù)預先已知類別名的訓練樣本，求出各類在特征空間的分布，然后利用它對未知數(shù)據(jù)進行分類的方法特征空間的分布，

31、然后利用它對未知數(shù)據(jù)進行分類的方法 換句話說，監(jiān)督分類法就是根據(jù)訓練樣本把特征空間分割成換句話說，監(jiān)督分類法就是根據(jù)訓練樣本把特征空間分割成對應于各類的區(qū)域?qū)诟黝惖膮^(qū)域 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 監(jiān)督分類過程1)1)根據(jù)類別名預先給定的訓練樣本，根據(jù)各類特征矢量分布確定根據(jù)類別名預先給定的訓練樣本，根據(jù)各類特征矢量分布確定判別函數(shù)判別函數(shù)g g1 1ggc c(c(c為類別數(shù)為類別數(shù)) )。這一過程稱為學習。這一過程稱為學習 2)2)對于待分類的特征矢量（或稱模式）對于待分類的特征矢量（或稱模式）X=(xX=(x1,1,

32、x x2,2,x,xn n) )，計算各判，計算各判別函數(shù)的值別函數(shù)的值g g1 1（X X）ggc c(X)(X) 3)3)在在g g1 1(X)g(X)gc c(X)(X)中選擇最大者，把模式中選擇最大者，把模式X X分類到這一類中分類到這一類中 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 常用判別函數(shù)1)1)距離判別函數(shù)距離判別函數(shù) 2/112)(niiiyxniiiyx1|/YXYX歐幾里德距離L距離相似度第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 常用判別函數(shù)1)1)距離判別函數(shù)距

33、離判別函數(shù) 利用距離判別函數(shù)的最近鄰域分類 分別使用與類別的平均值和與逐個訓練樣本的距離分類的結(jié)果，前者邊界為直線后者為曲線 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 常用判別函數(shù)2)2)線性函數(shù)線性函數(shù) g(X)=aX+b 將將m m類問題分解成（類問題分解成（m-1)m-1)個個2 2類識別問題。方法是先把特征空間分類識別問題。方法是先把特征空間分為為1 1類和其他類，如此進行下去即可類和其他類，如此進行下去即可 其中線性判別函數(shù)的系數(shù)可通過樣本試驗來確定其中線性判別函數(shù)的系數(shù)可通過樣本試驗來確定 第十章第十章 模板匹配與模式識別模板匹

34、配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 常用判別函數(shù)3)3)基于統(tǒng)計決策理論的最大似然分類法基于統(tǒng)計決策理論的最大似然分類法 式中式中P( P( i i) )表示類別表示類別 i i的模式以多大的概率被觀測到的情況，稱為先的模式以多大的概率被觀測到的情況，稱為先驗概率。驗概率。p(X| p(X| i i) )表示條件概率密度函數(shù)，表示條件概率密度函數(shù)，p( p( i i|X)|X)表示在觀測模式表示在觀測模式X X的時候，這個模式屬于類別的時候，這個模式屬于類別i i的確定度（似然度）。這一方法叫作的確定度（似然度）。這一方法叫作最大似然法最大似然法。 第十章第十章 模板匹配

35、與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 3)3)基于統(tǒng)計決策理論的最大似然分類法基于統(tǒng)計決策理論的最大似然分類法 理論上為誤差最小的分類法。例如，在一維特征空間的場合，如下圖a所示，用某一值T把特征空間分割成兩個區(qū)域（類別）的時候，產(chǎn)生的誤分類概率可由圖b中劃有斜線的部分的面積來表示。即 dxXpPdxXpPEEPTTE)|()()|()(11222112圖a圖b第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 3)3)基于統(tǒng)計決策理論的最大似然分類法基于統(tǒng)計決策理論的最大似然分類法 為了使用最大似然法，必須預先求

36、出( i)和p(| i)。( i)是類別 i被觀測的概率，所以是可以預測的。另一方面，p(| i)是表示在類別 i的特征矢量分布的函數(shù)，是不易求得的。因此，通常假定它為正態(tài)分布，即： )()(21exp)2()|(12/12/iiTiiiUXUXXp第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 3)3)基于統(tǒng)計決策理論的最大似然分類法基于統(tǒng)計決策理論的最大似然分類法 分布函數(shù)的平均值i和協(xié)方差矩陣i則可從訓練樣本計算。從n個訓練樣本X1,X2,Xn計算平均值U和協(xié)方差矩陣的表達式為：niinX11U1, 2, , nT1212122211121

37、1.mmmmmm在假設特征矢量為正態(tài)分布的前提下，為了使最大似然法計算簡化，常把似然度函數(shù)P( i)p(X| i)用其對數(shù)logP( i)+logp(X| i)來代替。因為對數(shù)函數(shù)是單調(diào)函數(shù)，所以即使采用對數(shù)似然度函數(shù)，分類結(jié)果也完全不變 如果不對各種類別的特征矢量是否真正的形成正態(tài)分布進行檢查，最大似然分類法多半會產(chǎn)生誤分類，甚至出現(xiàn)不能使用的情況 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.3 10.3 統(tǒng)計模式識別統(tǒng)計模式識別 v 非監(jiān)督分類非監(jiān)督分類非監(jiān)督分類方法是在無法獲得類別先驗知識的情況下，根據(jù)模式方法是在無法獲得類別先驗知識的情況下，根據(jù)模式之間的相似度進行類別劃分

38、，將相似性強的模式歸為同一類別。之間的相似度進行類別劃分，將相似性強的模式歸為同一類別。非監(jiān)督分類方法又稱為非監(jiān)督分類方法又稱為聚類分析聚類分析 對于模式不服從多維正態(tài)分布或者概率密度函數(shù)具有多重模態(tài)對于模式不服從多維正態(tài)分布或者概率密度函數(shù)具有多重模態(tài)( (即不止一個最大值的情況）時，通常就可使用非監(jiān)督分類。即不止一個最大值的情況）時，通常就可使用非監(jiān)督分類。第第七章中介紹的七章中介紹的K K均值聚類均值聚類分析法就是一種非監(jiān)督分類法分析法就是一種非監(jiān)督分類法 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.4 10.4 結(jié)構(gòu)模式識別結(jié)構(gòu)模式識別 1. 1. 基本原理基本原理 結(jié)構(gòu)模

39、式識別結(jié)構(gòu)模式識別是將一個復雜的模式分解成一系列更簡單的模式（子模是將一個復雜的模式分解成一系列更簡單的模式（子模式），對子模式繼續(xù)分解，最后分解成最簡單的子模式（或稱基元），式），對子模式繼續(xù)分解，最后分解成最簡單的子模式（或稱基元），借助于一種形式語言對模式的結(jié)構(gòu)進行描述，從而識別圖像。模式、借助于一種形式語言對模式的結(jié)構(gòu)進行描述，從而識別圖像。模式、子模式、基元類似于英文句子的短語、單詞、字母，這種識別方法類子模式、基元類似于英文句子的短語、單詞、字母，這種識別方法類似語言的句法結(jié)構(gòu)分析，因此又稱為句法模式識別。似語言的句法結(jié)構(gòu)分析，因此又稱為句法模式識別。 第十章第十章 模板匹配與模式

40、識別模板匹配與模式識別10.4 10.4 結(jié)構(gòu)模式識別結(jié)構(gòu)模式識別 1. 1. 基本原理基本原理 句法模式識別系統(tǒng)原理框圖如下圖所示。它由識別和分析兩部分組成句法模式識別系統(tǒng)原理框圖如下圖所示。它由識別和分析兩部分組成 識別部分包括預處理、分割描述、基元提取和結(jié)構(gòu)分析。預處理主要包括編碼、增強等系列操作。結(jié)構(gòu)分析是用學習所得的句法規(guī)則對未知結(jié)構(gòu)信息的圖像所表示的句子進行句法分析。 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.4 10.4 結(jié)構(gòu)模式識別結(jié)構(gòu)模式識別 2. 2. 樹分類法樹分類法 樹分類法樹分類法就是根據(jù)樹型分層理論，將未知數(shù)據(jù)歸屬于某一類的分類方就是根據(jù)樹型分層理論，

41、將未知數(shù)據(jù)歸屬于某一類的分類方法，下圖所示是一個法，下圖所示是一個n n類問題的樹分類器。類問題的樹分類器。 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.4 10.4 結(jié)構(gòu)模式識別結(jié)構(gòu)模式識別 2. 2. 樹分類法樹分類法 分類過程首先，把集合首先，把集合 C C1 1,C,C2 2, ,，C Cn n 用特征用特征f f1 1將其分成兩組將其分成兩組CC1 1,C,C2 2, ,，C Cn1n1 和和CCn1+1n1+1,C,Cn1+2n1+2, ,，C Cn n 然后，用特征然后，用特征f f2 2進一步將進一步將CC1 1,C,C2 2, ,C Cn1n1 分成兩組，用特征分

42、成兩組，用特征f f3 3將將CCn1+1n1+1,C,Cn1+2n1+2, ,C Cn n 分成兩組分成兩組 不斷地進行二分法處理，最終分別達到唯一的種類為止不斷地進行二分法處理，最終分別達到唯一的種類為止 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.4 10.4 結(jié)構(gòu)模式識別結(jié)構(gòu)模式識別 2. 2. 樹分類法樹分類法 樹分類法優(yōu)點在識別多類、多特征圖像時，用樹分類器，每次判定只選用少量的在識別多類、多特征圖像時，用樹分類器，每次判定只選用少量的特征，而不同的特征又可在不同的判定中發(fā)揮作用，維數(shù)的問題就特征，而不同的特征又可在不同的判定中發(fā)揮作用，維數(shù)的問題就顯得不突出了顯得不突

43、出了 樹分類器每次判定比較簡單。盡管判定次數(shù)增多，但判定一個樣本樹分類器每次判定比較簡單。盡管判定次數(shù)增多，但判定一個樣本所屬類別的總計算量并不一定增加所屬類別的總計算量并不一定增加 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.4 10.4 結(jié)構(gòu)模式識別結(jié)構(gòu)模式識別 2. 2. 樹分類法樹分類法 問題注意設計分類器時，必須考慮樹的結(jié)構(gòu)，使之用最少的特征，盡可能少設計分類器時，必須考慮樹的結(jié)構(gòu)，使之用最少的特征，盡可能少的段數(shù)達到最終的判決。對非常容易出現(xiàn)的類別，盡可能縮短判決的段數(shù)達到最終的判決。對非常容易出現(xiàn)的類別，盡可能縮短判決的段數(shù)，而很少出現(xiàn)的類別，判決段數(shù)長些。的段數(shù)，而

44、很少出現(xiàn)的類別，判決段數(shù)長些。 樹分類器雖然判決簡單，容易用機器實現(xiàn)，但是，如果從樹分類器雖然判決簡單，容易用機器實現(xiàn)，但是，如果從“樹根樹根”就產(chǎn)生判決錯誤，以后將無法糾正這個錯誤判決。所以，在靠近樹就產(chǎn)生判決錯誤，以后將無法糾正這個錯誤判決。所以，在靠近樹根處必須選擇抗噪聲的穩(wěn)定可靠的特征。根處必須選擇抗噪聲的穩(wěn)定可靠的特征。 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.5 10.5 人工神經(jīng)網(wǎng)絡識別法人工神經(jīng)網(wǎng)絡識別法 1. 1. 人工神經(jīng)網(wǎng)絡結(jié)構(gòu)人工神經(jīng)網(wǎng)絡結(jié)構(gòu) 常一個網(wǎng)絡分為輸入層、隱含層和輸出層。第一層稱為輸入層。網(wǎng)常一個網(wǎng)絡分為輸入層、隱含層和輸出層。第一層稱為輸入層

45、。網(wǎng)絡中當前層的每個神經(jīng)元獲得輸入信號，而它的輸出則傳向下一層絡中當前層的每個神經(jīng)元獲得輸入信號，而它的輸出則傳向下一層的所有神經(jīng)元。有些網(wǎng)絡則允許同層間的神經(jīng)元之間通信，而反饋的所有神經(jīng)元。有些網(wǎng)絡則允許同層間的神經(jīng)元之間通信，而反饋結(jié)構(gòu)還允許前一層的神經(jīng)元接受后一層的神經(jīng)元的輸出。最后一層結(jié)構(gòu)還允許前一層的神經(jīng)元接受后一層的神經(jīng)元的輸出。最后一層被稱為輸出層，而其它所有的稱為隱含層。被稱為輸出層，而其它所有的稱為隱含層。 輸入1輸入2輸入n輸出輸入層 隱含層 輸出層 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.5 10.5 人工神經(jīng)網(wǎng)絡識別法人工神經(jīng)網(wǎng)絡識別法 2. 2. 神經(jīng)

46、元神經(jīng)元 一個處理單元即一個人工神經(jīng)元，將接受的信息一個處理單元即一個人工神經(jīng)元，將接受的信息x x0 0,x,x1 1, ,x,xn-1n-1，通過，通過用用W W0 0,W,W1 1, ,W,Wn-1n-1表示的權(quán)，以點積的形式作為自己的輸入，如下圖，表示的權(quán)，以點積的形式作為自己的輸入，如下圖，并將輸入與以某種方式設定的域值并將輸入與以某種方式設定的域值作比較，再經(jīng)某種函數(shù)作比較，再經(jīng)某種函數(shù)f f的變換，的變換，便得到該神經(jīng)元的輸出便得到該神經(jīng)元的輸出y y 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.5 10.5 人工神經(jīng)網(wǎng)絡識別法人工神經(jīng)網(wǎng)絡識別法 2. 2. 神經(jīng)元神

47、經(jīng)元 常用非線性變換函數(shù)f二值型閾值邏輯型S型第十章第十章 模板匹配與模式識別模板匹配與模式識別10.5 10.5 人工神經(jīng)網(wǎng)絡識別法人工神經(jīng)網(wǎng)絡識別法 2. 2. 神經(jīng)元神經(jīng)元 神經(jīng)元輸入輸出間關(guān)系神經(jīng)元的輸入與輸出間的關(guān)系由下式給出：神經(jīng)元的輸入與輸出間的關(guān)系由下式給出： )(10iniixWfyxi為第i個輸入元素（通常為n維輸入矢量X的第i個分量）；Wi為從第i個輸入與神經(jīng)元間的互聯(lián)權(quán)重；為神經(jīng)元的內(nèi)部閾值；y為神經(jīng)元的輸出。 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.5 10.5 人工神經(jīng)網(wǎng)絡識別法人工神經(jīng)網(wǎng)絡識別法 2. 2. 神經(jīng)元神經(jīng)元 神經(jīng)元輸入輸出間關(guān)系神經(jīng)元

48、的輸入與輸出間的關(guān)系由下式給出：神經(jīng)元的輸入與輸出間的關(guān)系由下式給出： )(10iniixWfyxi為第i個輸入元素（通常為n維輸入矢量X的第i個分量）；Wi為從第i個輸入與神經(jīng)元間的互聯(lián)權(quán)重；為神經(jīng)元的內(nèi)部閾值；y為神經(jīng)元的輸出。 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.5 10.5 人工神經(jīng)網(wǎng)絡識別法人工神經(jīng)網(wǎng)絡識別法 3. 3. 神經(jīng)網(wǎng)絡用于模式識別的基本原理神經(jīng)網(wǎng)絡用于模式識別的基本原理在模式識別應用中，神經(jīng)網(wǎng)絡的輸入是未知對象的特征向量；在模式識別應用中，神經(jīng)網(wǎng)絡的輸入是未知對象的特征向量； 輸入的信息經(jīng)不同層傳播，使輸出層上產(chǎn)生相應輸出向量，根輸入的信息經(jīng)不同層傳播

49、，使輸出層上產(chǎn)生相應輸出向量，根據(jù)輸出的結(jié)果將該對象劃分到某一類中據(jù)輸出的結(jié)果將該對象劃分到某一類中 當神經(jīng)元的定義和網(wǎng)絡連接結(jié)構(gòu)確定后，神經(jīng)元之間互連的權(quán)重當神經(jīng)元的定義和網(wǎng)絡連接結(jié)構(gòu)確定后，神經(jīng)元之間互連的權(quán)重系數(shù)決定了網(wǎng)絡的行為。在訓練過程中權(quán)重系數(shù)不斷得到調(diào)整，系數(shù)決定了網(wǎng)絡的行為。在訓練過程中權(quán)重系數(shù)不斷得到調(diào)整，當訓練結(jié)束進入實際應用時，權(quán)重系數(shù)保持不變。當訓練結(jié)束進入實際應用時，權(quán)重系數(shù)保持不變。 第十章第十章 模板匹配與模式識別模板匹配與模式識別10.5 10.5 人工神經(jīng)網(wǎng)絡識別法人工神經(jīng)網(wǎng)絡識別法 3. 3. 神經(jīng)網(wǎng)絡用于模式識別的優(yōu)缺點分析神經(jīng)網(wǎng)絡用于模式識別的優(yōu)缺點分析 優(yōu)點o 它要求對問題的了解較少它要求對問題的了解較少 o 可以實現(xiàn)特征空間較復雜的劃