數(shù)字圖象處理-10課件

數(shù)字圖像處理北京大學計算機研究所陳曉鷗數(shù)字圖像處理北京大學計算機研究所陳曉鷗1第四節(jié)識別與解釋3.4.1圖像分析引言3.4.2圖像分析系統(tǒng)的組成3.4.3模式與模式類3.4.4決策論法3.4.5結構法第四節(jié)識別與解釋3.4.1圖像分析引言23.4.1圖像分析引言圖像分析引言圖像分析的定義圖像分析的目標自動圖像分析系統(tǒng)行為能力的概念化分類自動圖像分析系統(tǒng)的現(xiàn)狀3.4.1圖像分析引言圖像分析引言33.4.1圖像分析引言圖像分析的定義圖像分析是一個： 發(fā)現(xiàn)、辨認和理解模式的過程這些模式都與執(zhí)行和圖像相關的任務有關。圖像分析的目標計算機圖像分析的主要目的之一是，賦予某些具有感覺能力的機器，以類似人的大腦的能力。例如OCR3.4.1圖像分析引言圖像分析的定義43.4.1圖像分析引言自動圖像分析系統(tǒng)行為能力的概念化分類分為三類：獲取、發(fā)現(xiàn)信息：從背景中提取有關信息學習、應用知識：抽象、歸納信息特征的學習過程， 并應用到新的對象中構造、推理知識：從不完整的信息中構造推論出新 的知識，并加以應用3.4.1圖像分析引言自動圖像分析系統(tǒng)行為能力的概念化分類53.4.1圖像分析引言自動圖像分析系統(tǒng)的現(xiàn)狀我們可以設計出這種系統(tǒng)，但仍然缺乏理論依據(jù)。有待人類視覺認識理論的進一步研究我們可以做出在某一應用上超過人的能力的系統(tǒng)，但缺乏擴展性。過分依賴應用3.4.1圖像分析引言自動圖像分析系統(tǒng)的現(xiàn)狀63.4.2圖像分析系統(tǒng)組的成圖像分析技術分類的三種基本范疇低級處理：圖像獲取、預處理，不需要智能中級處理：圖像分割、表示與描述，需要智能高級處理：圖像識別、解釋，缺少理論，為降 低難度，設計得更專用。3.4.2圖像分析系統(tǒng)組的成圖像分析技術分類的三種基本范疇7圖像分析技術分類的三種基本范疇知識庫分割表示與描述識別與解釋預處理圖像獲取低級處理高級處理中級處理結果問題3.4.2圖像分析系統(tǒng)組的成圖像分析技術分類的三種基本范疇知識庫分割表示與描述識別預處理8圖像識別與解釋的基本方法識別的統(tǒng)計分類方法：用向量形式表達模式；分派模式向量到不同的模式類識別的結構方法：用符號匹配，模式被表示為符號形式（如形狀數(shù)、串和樹）圖像解釋的方法：圖像解釋技術是基于謂詞邏輯、語義網(wǎng)絡和特定產(chǎn)品的系統(tǒng)3.4.2圖像分析系統(tǒng)組的成圖像識別與解釋的基本方法3.4.2圖像分析系統(tǒng)組的成93.4.3模式與模式類模式的定義模式類的定義模式識別的定義常用的模式序列模式特征向量模式串模式樹3.4.3模式與模式類模式的定義103.4.3模式與模式類模式的定義模式是：圖像中的一個對象或某些感興趣本質(zhì)的數(shù)量或結構的描述模式是：由一個或多個描述子來組成，換句話說，模式是一個描述子的序列（名詞“特征”經(jīng)常被用來代指描述子）模式是：一組特征或一組描述子3.4.3模式與模式類模式的定義11模式類的定義模式類是具有某些公共特征的模式的系列 模式類用w1,w2,…wM表示，M是類的個數(shù)模式識別的定義根據(jù)圖像中對象的特征組成的模式，確定對象是屬于那一個模式類，即為模式識別3.4.3識別與解釋:模式與模式類模式類的定義3.4.3識別與解釋:模式與模式類12模式與模式類舉例1）汽車的長、寬、高（L,W,H）——模式2）大客車：（L,W,H）大 小轎車：（L,W,H）小 卡車：（L,W,H）卡 從而有模式類（w大,w小,w卡）3）從圖像中發(fā)現(xiàn)一個對象——模式實例。 希望識別出該對象（L1,W1,H1），是大客車、小轎車、還是卡車——模式識別3.4.3識別與解釋:模式與模式類模式與模式類舉例3.4.3識別與解釋:模式與模式類13常用的模式序列三種模式序列:模式特征向量模式串模式樹模式特征向量定義舉例特征的選擇3.4.3模式與模式類常用的模式序列3.4.3模式與模式類14常用的模式序列模式特征向量的定義——描述子構成的向量模式特征向量用粗體小寫字母表示，如x,y形式如下：其中每一個xi代表第i個描述子，n是這種描述子的數(shù)量。模式特征向量被表示為一列或表示成 x=(x1,x2,…,xn)T，其中T指出是轉(zhuǎn)秩x=

x1x2.xn3.4.3模式與模式類常用的模式序列x=x13.4.3模式與模式類15模式特征向量舉例 假設我們想描述三種蝴蝶花（多毛的、維吉尼亞、多色的）通過測量它們花瓣的寬度和長度。這里涉及一個兩維的模式特征向量：其中x1、x2分別對應花瓣的長和寬三種模式類用w1、w2、w3表示x=x1x23.4.3模式與模式類模式特征向量舉例x=x13.4.3模式與模式類16由于所有的花瓣在寬和長上都有某種程度的變化，所以描述這些花瓣的模式特征向量也將有變化，不僅在不同的類之間，而且也在類的內(nèi)部 在這種情況下每一種花變成二維歐幾里德空間的一個點3.4.3模式與模式類3.4.3模式與模式類173.4.3模式與模式類1234567x1花瓣長0.51.01.52.02.53.0x2花瓣寬多毛的維吉尼亞多色的3.4.3模式與模式類1234567x1花瓣長0.51.18模式特征向量舉例：分析對花瓣長寬的測量，成功地將多毛的蝴蝶花與其它兩種分離，但對于分離維吉尼亞和多色的是失敗的。這個結論說明了分類的特征選擇問題，在這個問題中，類的可區(qū)別性的程度，完全依賴于對模式尺寸測量的選擇3.4.3模式與模式類模式特征向量舉例：分析3.4.3模式與模式類19模式特征的選擇良好的特征應具備四個特點可區(qū)別性：對不同類別對象特征值差異明顯可靠性：對同類對象特征值比較接近獨立性：所用的各特征之間彼此統(tǒng)計獨立數(shù)量少：過多的特征數(shù)，會使系統(tǒng)復雜度提高一般特征向量的選擇方法盡量不選擇帶噪聲和相關度高的特征先選擇一組直覺上合理的特征，然后逐漸減少到最佳3.4.3模式與模式類模式特征的選擇3.4.3模式與模式類20模式串 用于以對象特征的結構或空間關系作為模式的識別模式串舉例：梯狀的模式3.4.3模式與模式類abaaabbb (1)S->aA (2)A->bS(3)A->b模式串3.4.3模式與模式類abaaabbb (1)S-21模式樹以分層目錄結構排序的模式類，一般多采用樹結構模式樹舉例3.4.3模式與模式類圖像城市田園草地森林娛樂區(qū)商業(yè)區(qū)娛樂區(qū)商業(yè)區(qū)城區(qū)內(nèi)城市郊公路模式樹3.4.3模式與模式類圖像城市田園草地森林娛樂區(qū)商業(yè)223.4.4決策論法決策論法分類器的設計和訓練決策論法的基本概念分類器最小距離分類器相關匹配分類器3.4.4決策論法決策論法233.4.4決策論法分類器的設計與訓練分類器一般設計方法分類器對每一模式類，給出一個典型摸板對每一個遇到的待分類對象計算該對象與個典型摸板之間的相似程度相似值是對象的函數(shù)函數(shù)取值的不同，決定對象屬于那一模式類3.4.4決策論法分類器的設計與訓練243.4.4決策論法分類器的設計與訓練分類器一般設計規(guī)則分類器規(guī)則都轉(zhuǎn)換為閾值規(guī)則將測量空間劃分成互不重疊的區(qū)域每一個模式類對應一個區(qū)域（或多個）對象的分類函數(shù)值落在哪個區(qū)域，對象就屬那類某些情況，某些區(qū)域為“無法確定”類3.4.4決策論法分類器的設計與訓練253.4.4決策論法分類器的設計與訓練分類器的訓練決策規(guī)則決定后，需要確定分類器的閾值實現(xiàn)的方法是用一組已知對象訓練分類器訓練對象集由每類已被正確識別的部分對象組成通過對這些對象的度量，定出能夠?qū)Q策面劃分成不同區(qū)域的合理閾值使分類器對訓練對象樣本集分類準確性最高3.4.4決策論法分類器的設計與訓練263.4.4識別與解釋:決策論法決策論法的基本概念決策論識別法的定義設：模式特征向量：x=(x1,x2,…,xn)T，對于：M個模式類w1,w2,…,wM，尋找M個決策函數(shù)d1(x),d2(x),…,dM(x)，具有這樣的特性：如果模式實例x屬于模式類wi,那么： di(x)>dj(x) j=1,2,…,M;j≠i 換句話說，如果一個未知模式對象x屬于第i個模式類，把x代入所有的決策函數(shù)，di(x)的取值最大。3.4.4識別與解釋:決策論法決策論法的基本概念273.4.4識別與解釋:決策論法決策論法的基本概念決策邊界的定義對于模式特征向量x，如果決策函數(shù)值有： di(x)-dj(x)=0此x向量，被稱為wi與wj的決策邊界。通常用一個單一的函數(shù)標識兩個類之間的決策邊界，定義為： dij(x)=di(x)-dj(x)=0 如果dij(x)>0x屬于類wi 如果dij(x)<0x屬于類wj3.4.4識別與解釋:決策論法決策論法的基本概念283.4.4識別與解釋:決策論法分類器最小距離分類器以蝴蝶花的例子為例：（1）為多色（w1）和多毛（w2）的兩種蝴蝶花，確定兩個原形（或稱模板）m1和m2（2）對于一個未知模式向量x，判斷x與m1和m2的距離，如果與m1的距離小于與m2的距離，則x屬于w1，否則屬于w2。3.4.4識別與解釋:決策論法分類器293.4.4識別與解釋:決策論法1234567x1花瓣長0.51.01.52.02.53.0x2花瓣寬多毛的多色的m1m2x3.4.4識別與解釋:決策論法1234567x1花瓣長0303.4.4識別與解釋:決策論法分類器最小距離分類器1）算法思想：對于M個模式類wii=1,2,...,M為每一個模式類確定一個原形模式特征向量mi對于一個未知模式特征向量x，如果x與mi的距離最小，就稱，x屬于wi3.4.4識別與解釋:決策論法分類器313.4.4識別與解釋:決策論法分類器最小距離分類器2）最小距離分類器定義（訓練）：〈1〉計算模式類wj的原形向量： mj=1/Njxj=1,2,…,M xwj其中Nj是屬于模式類wj的模式向量的個數(shù)。通過計算已知屬于wj的模式特征向量的各分量的均值得到原形模式特征向量mj3.4.4識別與解釋:決策論法分類器323.4.4識別與解釋:決策論法分類器最小距離分類器〈2〉計算x與mi的距離dj(x)=||x–mj||j=1,2,…,M 其中||a||=(aTa)1/2是歐幾里德范式（平方和開方）dj(x)=((x–mj)T(x–mj))1/2j=1,2,…,M〈3〉 決策如果，di(x)=min(dj(x))j=1,2,…,M 就說：x屬于wi3.4.4識別與解釋:決策論法分類器333.4.4識別與解釋:決策論法分類器最小距離分類器為便于計算，改寫成求最大的標準形式，決策函數(shù)為：dj(x)=xTmj–1/2mjTmjj=1,2,…,M 如果，di(x)=max(dj(x))j=1,2,…,M 就說：x屬于wi〈4〉用上式得到的類wi和wj之間的決策邊界是： dij(x)=di(x)-dj(x)=xT（mi–mj）–1/2(mi–mj)T(mi–mj)=03.4.4識別與解釋:決策論法分類器343.4.4識別與解釋:決策論法3）舉例：多色的和多毛的蝴蝶花，用w1和w2分別表示，有簡單的原形向量m1=(4.4,1.3)T m2=(1.5,0.3)T決策函數(shù)是：d1(x)=xTm1–1/2m1Tm1=4.3x1+1.3x2–10.1d2(x)=xTm2–1/2m2Tm2=1.5x1+0.3x2–1.17決策邊界的等式：d12(x)=d1(x)–d2(x)=2.8x1–1.0x2–8.9=03.4.4識別與解釋:決策論法3）舉例：353.4.4識別與解釋:決策論法1234567x1花瓣長0.51.01.52.02.53.0x2花瓣寬多毛的多色的3.4.4識別與解釋:決策論法1234567x1花瓣長0363.4.4識別與解釋:決策論法分類器相關匹配分類器(1)相關匹配的基本思想:a.用樣板子圖像直接作為模式特征（不是用描述子）b.通過子圖像與原圖像直接進行相關計算，把相關計算作為決策函數(shù)c.相關計算獲得最大值的位置，就被認為匹配成功3.4.4識別與解釋:決策論法分類器373.4.4識別與解釋:決策論法相關匹配分類器(1)相關匹配基本思想3.4.4識別與解釋:決策論法相關匹配分類器383.4.4識別與解釋:決策論法分類器相關匹配分類器Mx原點Nyf(x,y)(s,t)Jsw(x-s,y-t)Kt3.4.4識別與解釋:決策論法分類器Mx原點Nyf(x,y393.4.4識別與解釋:決策論法分類器相關匹配分類器(2)算法描述決策函數(shù)是相關函數(shù)c(s,t)=∑∑f(x,y)w(x-s,y-t) xy對圖像的每一個點進行相關計算，只計算重疊部分 問題：在邊界處將失去準確性，其誤差與子圖像的尺寸成正比3.4.4識別與解釋:決策論法分類器403.4.4識別與解釋:決策論法相關匹配分類器(3)改進 相關函數(shù)對振幅的變化太敏感，f(x,y)加倍，c(s,t)也加倍。用相關系數(shù)函數(shù)代替相關函數(shù) ∑∑[f(x,y)–f(x,y)][w(x-s,y-t)–w]γ(s,t)=———————————————————— {∑∑[f(x,y)–f(x,y)]2∑∑[w(x-s,y-t)–w]2}1/2 xy xy γ(s,t)的值域為（-1，1）3.4.4識別與解釋:決策論法相關匹配分類器413.4.4識別與解釋:決策論法相關匹配分類器(4)對旋轉(zhuǎn)和比例變化的分析問題： 當被匹配圖像中，對象的尺寸和角度與模式不一致，此方法將失效。改進：尺寸的正則化，解決空間比例的問題。正則化模板與原圖。如果知道原圖像的旋轉(zhuǎn)角度，我們可以通過旋轉(zhuǎn)原圖像，對齊模式解決。結論: 如果被匹配的對象的角度任意，此方法不能用于這種問題。3.4.4識別與解釋:決策論法相關匹配分類器423.4.4識別與解釋:決策論法分類器相關性匹配分類器(5)關于空域計算相關函數(shù)，可以在頻域計算。 f(x,y)w(x,y)f(s,t)w(s,t)但無論在何種情況下，都沒有更有優(yōu)勢的理論根據(jù)。相關系數(shù)方式只能在空域進行。3.4.4識別與解釋:決策論法分類器433.4.4識別與解釋:結構法結構法匹配形狀數(shù)匹配串3.4.4識別與解釋:結構法結構法443.4.4識別與解釋:結構法結構法決策法，通過量化的方法處理模式，最大限度地忽略了模式形狀的內(nèi)在結構關系。 結構法，則力求通過準確地抓住這些不同模式類的內(nèi)在結構關系來進行模式識別。3.4.4識別與解釋:結構法結構法453.4.4識別與解釋:結構法匹配形狀數(shù)(1)匹配形狀數(shù)的基本思想 通過比較兩個對象邊界的形狀數(shù)的相似程度，來匹配對象。例如： 未知模式 原形模式類3.4.4識別與解釋:結構法匹配形狀數(shù)463.4.4識別與解釋:結構法匹配形狀數(shù)(2)基本概念-相似級別 a.兩個區(qū)域邊界的相似級別k的定義： 用相同形狀數(shù)的最大序號表示：即：當考慮用4向鏈碼表示的封閉區(qū)域邊界的形狀數(shù)時，A和B具有相似級別k，當且僅當滿足： s4(A)=s4(B),s6(A)=s6(B), s8(A)=s8(B),…,sk(A)=sk(B), sk+2(A)sk+2(B),sk+4(A)sk+4(B),…， 這里s表示形狀數(shù),下標表示序號。3.4.4識別與解釋:結構法匹配形狀數(shù)473.4.4識別與解釋:結構法匹配形狀數(shù)(2)基本概念-形狀數(shù)的距離b.兩個區(qū)域邊界A和B形狀數(shù)的距離D(A,B)相似級別的倒數(shù)：D(A,B)=1/k 距離滿足如下性質(zhì)：D(A,B)0D(A,B)=0iffA=BD(A,C)max[D(A,B),D(B,C)]3.4.4識別與解釋:結構法匹配形狀數(shù)483.4.4識別與解釋:結構法匹配形狀數(shù)(3)算法思想a.用不同密度的網(wǎng)格劃分邊界區(qū)域，獲得不同序數(shù)的形狀數(shù)。b.如果使用相似級別k，k越大說明越相似。c.如果使用相似距離D，D越小說明越相似d.可以利用相似樹來進行判別3.4.4識別與解釋:結構法匹配形狀數(shù)493.4.4識別與解釋:結構法匹配形狀數(shù)（4）舉例假設我們有一個形狀F，想在另5個形狀（A，B，C，D，E）中找到與其最相似的形狀ABCDEF3.4.4識別與解釋:結構法匹配形狀數(shù)ABCDEF503.4.4識別與解釋:結構法這個問題類似于有五個原型形狀，想找出一個給定的尚不確定的形狀的最佳匹配的問題。這個問題可以利用相似樹和矩陣來可視化468101214ABCDEFABCDEFBCDEFAAAABECFBEDDDCFCFBEABCDEFABEDCF666668810888128883.4.4識別與解釋:結構法這個問題類似513.4.4識別與解釋:結構法串匹配（1）串匹配的基本思想比較兩個邊界串編碼的相似程度，來進行匹配（2）三個基本概念 設:兩個區(qū)域邊界A和B已分別被編碼為串a(chǎn)1a2…an和b1b2…bm。a3a3a3a3a3a3a3a3a2a2a3a33.4.4識別與解釋:結構法串匹配a3a3a3a3a3a3523.4.4識別與解釋:結構法串匹配a.兩個串的匹配數(shù)M:當ak=bk時我們說發(fā)生了一個匹配。令M代表A、B中匹配的總數(shù)。b.不匹配的符號數(shù)量Q： Q=max（|A|，|B|）-M這里|arg|是字符串的長度。當且僅當A和B完全相同時，Q=0。3.4.4識別與解釋:結構法串匹配533.4.4識別與解釋:結構法串匹配c.A和B相似度的簡便衡量R: R=M/Q=M/[max(|A|,|B|)-M]因此， 當A和B完全匹配時，R=；當A和B中任何字符都不匹配時， M=0，R=0。3.4.4識別與解釋:結構法串匹配543.4.4識別與解釋:結構法串匹配（3）算法思想a.由于匹配是逐字符進行的，b.選擇一個好的開始點，可以大大減少計算量。任何將兩個串規(guī)則化為相同字符開頭的方法都是有效的，只要這種方法不是窮舉起點。c.最大的R給出了最好的匹配。3.4.4識別與解釋:結構法串匹配553.4.4識別與解釋:結構法串匹配（4）舉例對象1.a對象2.a3.4.4識別與解釋:結構法串匹配對象1.a對象2.a563.4.4識別與解釋:結構法串匹配 現(xiàn)有兩個模式類：模式類1：有1.b、1.c、1.d、1.e、1.f 5個模板模式類2：有2.b、2.c、2.d、2.e、2.f 5個模板3.4.4識別與解釋:結構法串匹配573.4.4識別與解釋:結構法串匹配 現(xiàn)將對象1.a與模式類1的5個樣例做串匹配，有相似度R值的結果表： 1.b1.c1.d1.e1.f 1.a16.09.65.074.674.673.4.4識別與解釋:結構法串匹配583.4.4識別與解釋:結構法串匹配 現(xiàn)將對象2.a與模式類2的5個樣例做串匹配，有相似度R值的結果表： 2.b2.c2.d2.e2.f 2.a33.54.753.62.832.633.4.4識別與解釋:結構法串匹配593.4.4識別與解釋:結構法將對象1.a與模式類2的5個樣例做串匹配，有R值的結果表： 2.a2.b2.c2.d2.e2.f1.a1.241.181.021.020.93.89將對象2.a與模式類1的5個樣例做串匹配有R值的結果表： 1.a1.b1.c1.d1.e1.f2.a1.241.501.321.471.551.483.4.4識別與解釋:結構法將對象1.a與60請?zhí)釂栒執(zhí)釂?1數(shù)字圖像處理北京大學計算機研究所陳曉鷗數(shù)字圖像處理北京大學計算機研究所陳曉鷗62第四節(jié)識別與解釋3.4.1圖像分析引言3.4.2圖像分析系統(tǒng)的組成3.4.3模式與模式類3.4.4決策論法3.4.5結構法第四節(jié)識別與解釋3.4.1圖像分析引言633.4.1圖像分析引言圖像分析引言圖像分析的定義圖像分析的目標自動圖像分析系統(tǒng)行為能力的概念化分類自動圖像分析系統(tǒng)的現(xiàn)狀3.4.1圖像分析引言圖像分析引言643.4.1圖像分析引言圖像分析的定義圖像分析是一個： 發(fā)現(xiàn)、辨認和理解模式的過程這些模式都與執(zhí)行和圖像相關的任務有關。圖像分析的目標計算機圖像分析的主要目的之一是，賦予某些具有感覺能力的機器，以類似人的大腦的能力。例如OCR3.4.1圖像分析引言圖像分析的定義653.4.1圖像分析引言自動圖像分析系統(tǒng)行為能力的概念化分類分為三類：獲取、發(fā)現(xiàn)信息：從背景中提取有關信息學習、應用知識：抽象、歸納信息特征的學習過程， 并應用到新的對象中構造、推理知識：從不完整的信息中構造推論出新 的知識，并加以應用3.4.1圖像分析引言自動圖像分析系統(tǒng)行為能力的概念化分類663.4.1圖像分析引言自動圖像分析系統(tǒng)的現(xiàn)狀我們可以設計出這種系統(tǒng)，但仍然缺乏理論依據(jù)。有待人類視覺認識理論的進一步研究我們可以做出在某一應用上超過人的能力的系統(tǒng)，但缺乏擴展性。過分依賴應用3.4.1圖像分析引言自動圖像分析系統(tǒng)的現(xiàn)狀673.4.2圖像分析系統(tǒng)組的成圖像分析技術分類的三種基本范疇低級處理：圖像獲取、預處理，不需要智能中級處理：圖像分割、表示與描述，需要智能高級處理：圖像識別、解釋，缺少理論，為降 低難度，設計得更專用。3.4.2圖像分析系統(tǒng)組的成圖像分析技術分類的三種基本范疇68圖像分析技術分類的三種基本范疇知識庫分割表示與描述識別與解釋預處理圖像獲取低級處理高級處理中級處理結果問題3.4.2圖像分析系統(tǒng)組的成圖像分析技術分類的三種基本范疇知識庫分割表示與描述識別預處理69圖像識別與解釋的基本方法識別的統(tǒng)計分類方法：用向量形式表達模式；分派模式向量到不同的模式類識別的結構方法：用符號匹配，模式被表示為符號形式（如形狀數(shù)、串和樹）圖像解釋的方法：圖像解釋技術是基于謂詞邏輯、語義網(wǎng)絡和特定產(chǎn)品的系統(tǒng)3.4.2圖像分析系統(tǒng)組的成圖像識別與解釋的基本方法3.4.2圖像分析系統(tǒng)組的成703.4.3模式與模式類模式的定義模式類的定義模式識別的定義常用的模式序列模式特征向量模式串模式樹3.4.3模式與模式類模式的定義713.4.3模式與模式類模式的定義模式是：圖像中的一個對象或某些感興趣本質(zhì)的數(shù)量或結構的描述模式是：由一個或多個描述子來組成，換句話說，模式是一個描述子的序列（名詞“特征”經(jīng)常被用來代指描述子）模式是：一組特征或一組描述子3.4.3模式與模式類模式的定義72模式類的定義模式類是具有某些公共特征的模式的系列 模式類用w1,w2,…wM表示，M是類的個數(shù)模式識別的定義根據(jù)圖像中對象的特征組成的模式，確定對象是屬于那一個模式類，即為模式識別3.4.3識別與解釋:模式與模式類模式類的定義3.4.3識別與解釋:模式與模式類73模式與模式類舉例1）汽車的長、寬、高（L,W,H）——模式2）大客車：（L,W,H）大 小轎車：（L,W,H）小 卡車：（L,W,H）卡 從而有模式類（w大,w小,w卡）3）從圖像中發(fā)現(xiàn)一個對象——模式實例。 希望識別出該對象（L1,W1,H1），是大客車、小轎車、還是卡車——模式識別3.4.3識別與解釋:模式與模式類模式與模式類舉例3.4.3識別與解釋:模式與模式類74常用的模式序列三種模式序列:模式特征向量模式串模式樹模式特征向量定義舉例特征的選擇3.4.3模式與模式類常用的模式序列3.4.3模式與模式類75常用的模式序列模式特征向量的定義——描述子構成的向量模式特征向量用粗體小寫字母表示，如x,y形式如下：其中每一個xi代表第i個描述子，n是這種描述子的數(shù)量。模式特征向量被表示為一列或表示成 x=(x1,x2,…,xn)T，其中T指出是轉(zhuǎn)秩x=

x1x2.xn3.4.3模式與模式類常用的模式序列x=x13.4.3模式與模式類76模式特征向量舉例 假設我們想描述三種蝴蝶花（多毛的、維吉尼亞、多色的）通過測量它們花瓣的寬度和長度。這里涉及一個兩維的模式特征向量：其中x1、x2分別對應花瓣的長和寬三種模式類用w1、w2、w3表示x=x1x23.4.3模式與模式類模式特征向量舉例x=x13.4.3模式與模式類77由于所有的花瓣在寬和長上都有某種程度的變化，所以描述這些花瓣的模式特征向量也將有變化，不僅在不同的類之間，而且也在類的內(nèi)部 在這種情況下每一種花變成二維歐幾里德空間的一個點3.4.3模式與模式類3.4.3模式與模式類783.4.3模式與模式類1234567x1花瓣長0.51.01.52.02.53.0x2花瓣寬多毛的維吉尼亞多色的3.4.3模式與模式類1234567x1花瓣長0.51.79模式特征向量舉例：分析對花瓣長寬的測量，成功地將多毛的蝴蝶花與其它兩種分離，但對于分離維吉尼亞和多色的是失敗的。這個結論說明了分類的特征選擇問題，在這個問題中，類的可區(qū)別性的程度，完全依賴于對模式尺寸測量的選擇3.4.3模式與模式類模式特征向量舉例：分析3.4.3模式與模式類80模式特征的選擇良好的特征應具備四個特點可區(qū)別性：對不同類別對象特征值差異明顯可靠性：對同類對象特征值比較接近獨立性：所用的各特征之間彼此統(tǒng)計獨立數(shù)量少：過多的特征數(shù)，會使系統(tǒng)復雜度提高一般特征向量的選擇方法盡量不選擇帶噪聲和相關度高的特征先選擇一組直覺上合理的特征，然后逐漸減少到最佳3.4.3模式與模式類模式特征的選擇3.4.3模式與模式類81模式串 用于以對象特征的結構或空間關系作為模式的識別模式串舉例：梯狀的模式3.4.3模式與模式類abaaabbb (1)S->aA (2)A->bS(3)A->b模式串3.4.3模式與模式類abaaabbb (1)S-82模式樹以分層目錄結構排序的模式類，一般多采用樹結構模式樹舉例3.4.3模式與模式類圖像城市田園草地森林娛樂區(qū)商業(yè)區(qū)娛樂區(qū)商業(yè)區(qū)城區(qū)內(nèi)城市郊公路模式樹3.4.3模式與模式類圖像城市田園草地森林娛樂區(qū)商業(yè)833.4.4決策論法決策論法分類器的設計和訓練決策論法的基本概念分類器最小距離分類器相關匹配分類器3.4.4決策論法決策論法843.4.4決策論法分類器的設計與訓練分類器一般設計方法分類器對每一模式類，給出一個典型摸板對每一個遇到的待分類對象計算該對象與個典型摸板之間的相似程度相似值是對象的函數(shù)函數(shù)取值的不同，決定對象屬于那一模式類3.4.4決策論法分類器的設計與訓練853.4.4決策論法分類器的設計與訓練分類器一般設計規(guī)則分類器規(guī)則都轉(zhuǎn)換為閾值規(guī)則將測量空間劃分成互不重疊的區(qū)域每一個模式類對應一個區(qū)域（或多個）對象的分類函數(shù)值落在哪個區(qū)域，對象就屬那類某些情況，某些區(qū)域為“無法確定”類3.4.4決策論法分類器的設計與訓練863.4.4決策論法分類器的設計與訓練分類器的訓練決策規(guī)則決定后，需要確定分類器的閾值實現(xiàn)的方法是用一組已知對象訓練分類器訓練對象集由每類已被正確識別的部分對象組成通過對這些對象的度量，定出能夠?qū)Q策面劃分成不同區(qū)域的合理閾值使分類器對訓練對象樣本集分類準確性最高3.4.4決策論法分類器的設計與訓練873.4.4識別與解釋:決策論法決策論法的基本概念決策論識別法的定義設：模式特征向量：x=(x1,x2,…,xn)T，對于：M個模式類w1,w2,…,wM，尋找M個決策函數(shù)d1(x),d2(x),…,dM(x)，具有這樣的特性：如果模式實例x屬于模式類wi,那么： di(x)>dj(x) j=1,2,…,M;j≠i 換句話說，如果一個未知模式對象x屬于第i個模式類，把x代入所有的決策函數(shù)，di(x)的取值最大。3.4.4識別與解釋:決策論法決策論法的基本概念883.4.4識別與解釋:決策論法決策論法的基本概念決策邊界的定義對于模式特征向量x，如果決策函數(shù)值有： di(x)-dj(x)=0此x向量，被稱為wi與wj的決策邊界。通常用一個單一的函數(shù)標識兩個類之間的決策邊界，定義為： dij(x)=di(x)-dj(x)=0 如果dij(x)>0x屬于類wi 如果dij(x)<0x屬于類wj3.4.4識別與解釋:決策論法決策論法的基本概念893.4.4識別與解釋:決策論法分類器最小距離分類器以蝴蝶花的例子為例：（1）為多色（w1）和多毛（w2）的兩種蝴蝶花，確定兩個原形（或稱模板）m1和m2（2）對于一個未知模式向量x，判斷x與m1和m2的距離，如果與m1的距離小于與m2的距離，則x屬于w1，否則屬于w2。3.4.4識別與解釋:決策論法分類器903.4.4識別與解釋:決策論法1234567x1花瓣長0.51.01.52.02.53.0x2花瓣寬多毛的多色的m1m2x3.4.4識別與解釋:決策論法1234567x1花瓣長0913.4.4識別與解釋:決策論法分類器最小距離分類器1）算法思想：對于M個模式類wii=1,2,...,M為每一個模式類確定一個原形模式特征向量mi對于一個未知模式特征向量x，如果x與mi的距離最小，就稱，x屬于wi3.4.4識別與解釋:決策論法分類器923.4.4識別與解釋:決策論法分類器最小距離分類器2）最小距離分類器定義（訓練）：〈1〉計算模式類wj的原形向量： mj=1/Njxj=1,2,…,M xwj其中Nj是屬于模式類wj的模式向量的個數(shù)。通過計算已知屬于wj的模式特征向量的各分量的均值得到原形模式特征向量mj3.4.4識別與解釋:決策論法分類器933.4.4識別與解釋:決策論法分類器最小距離分類器〈2〉計算x與mi的距離dj(x)=||x–mj||j=1,2,…,M 其中||a||=(aTa)1/2是歐幾里德范式（平方和開方）dj(x)=((x–mj)T(x–mj))1/2j=1,2,…,M〈3〉 決策如果，di(x)=min(dj(x))j=1,2,…,M 就說：x屬于wi3.4.4識別與解釋:決策論法分類器943.4.4識別與解釋:決策論法分類器最小距離分類器為便于計算，改寫成求最大的標準形式，決策函數(shù)為：dj(x)=xTmj–1/2mjTmjj=1,2,…,M 如果，di(x)=max(dj(x))j=1,2,…,M 就說：x屬于wi〈4〉用上式得到的類wi和wj之間的決策邊界是： dij(x)=di(x)-dj(x)=xT（mi–mj）–1/2(mi–mj)T(mi–mj)=03.4.4識別與解釋:決策論法分類器953.4.4識別與解釋:決策論法3）舉例：多色的和多毛的蝴蝶花，用w1和w2分別表示，有簡單的原形向量m1=(4.4,1.3)T m2=(1.5,0.3)T決策函數(shù)是：d1(x)=xTm1–1/2m1Tm1=4.3x1+1.3x2–10.1d2(x)=xTm2–1/2m2Tm2=1.5x1+0.3x2–1.17決策邊界的等式：d12(x)=d1(x)–d2(x)=2.8x1–1.0x2–8.9=03.4.4識別與解釋:決策論法3）舉例：963.4.4識別與解釋:決策論法1234567x1花瓣長0.51.01.52.02.53.0x2花瓣寬多毛的多色的3.4.4識別與解釋:決策論法1234567x1花瓣長0973.4.4識別與解釋:決策論法分類器相關匹配分類器(1)相關匹配的基本思想:a.用樣板子圖像直接作為模式特征（不是用描述子）b.通過子圖像與原圖像直接進行相關計算，把相關計算作為決策函數(shù)c.相關計算獲得最大值的位置，就被認為匹配成功3.4.4識別與解釋:決策論法分類器983.4.4識別與解釋:決策論法相關匹配分類器(1)相關匹配基本思想3.4.4識別與解釋:決策論法相關匹配分類器993.4.4識別與解釋:決策論法分類器相關匹配分類器Mx原點Nyf(x,y)(s,t)Jsw(x-s,y-t)Kt3.4.4識別與解釋:決策論法分類器Mx原點Nyf(x,y1003.4.4識別與解釋:決策論法分類器相關匹配分類器(2)算法描述決策函數(shù)是相關函數(shù)c(s,t)=∑∑f(x,y)w(x-s,y-t) xy對圖像的每一個點進行相關計算，只計算重疊部分 問題：在邊界處將失去準確性，其誤差與子圖像的尺寸成正比3.4.4識別與解釋:決策論法分類器1013.4.4識別與解釋:決策論法相關匹配分類器(3)改進 相關函數(shù)對振幅的變化太敏感，f(x,y)加倍，c(s,t)也加倍。用相關系數(shù)函數(shù)代替相關函數(shù) ∑∑[f(x,y)–f(x,y)][w(x-s,y-t)–w]γ(s,t)=———————————————————— {∑∑[f(x,y)–f(x,y)]2∑∑[w(x-s,y-t)–w]2}1/2 xy xy γ(s,t)的值域為（-1，1）3.4.4識別與解釋:決策論法相關匹配分類器1023.4.4識別與解釋:決策論法相關匹配分類器(4)對旋轉(zhuǎn)和比例變化的分析問題： 當被匹配圖像中，對象的尺寸和角度與模式不一致，此方法將失效。改進：尺寸的正則化，解決空間比例的問題。正則化模板與原圖。如果知道原圖像的旋轉(zhuǎn)角度，我們可以通過旋轉(zhuǎn)原圖像，對齊模式解決。結論: 如果被匹配的對象的角度任意，此方法不能用于這種問題。3.4.4識別與解釋:決策論法相關匹配分類器1033.4.4識別與解釋:決策論法分類器相關性匹配分類器(5)關于空域計算相關函數(shù)，可以在頻域計算。 f(x,y)w(x,y)f(s,t)w(s,t)但無論在何種情況下，都沒有更有優(yōu)勢的理論根據(jù)。相關系數(shù)方式只能在空域進行。3.4.4識別與解釋:決策論法分類器1043.4.4識別與解釋:結構法結構法匹配形狀數(shù)匹配串3.4.4識別與解釋:結構法結構法1053.4.4識別與解釋:結構法結構法決策法，通過量化的方法處理模式，最大限度地忽略了模式形狀的內(nèi)在結構關系。 結構法，則力求通過準確地抓住這些不同模式類的內(nèi)在結構關系來進行模式識別。3.4.4識別與解釋:結構法結構法1063.4.4識別與解釋:結構法匹配形狀數(shù)(1)匹配形狀數(shù)的基本思想 通過比較兩個對象邊界的形狀數(shù)的相似程度，來匹配對象。例如： 未知模式 原形模式類3.4.4識別與解釋:結構法匹配形狀數(shù)1073.4.4識別與解釋:結構法匹配形狀數(shù)(2)基本概念-相似級別 a.兩個區(qū)域邊界的相似級別k的定義： 用相同形狀數(shù)的最大序號表示：即：當考慮用4向鏈碼表示的封閉區(qū)域邊界的形狀數(shù)時，A和B具有相似級別k，當且僅當滿足： s4(A)=s4(B),s6(A)=s6(B), s8(A)=s8(B),…,sk(A)=sk(B), sk+2(A)sk+2(B),sk+4(A)sk+4(B),…， 這里s表示形狀數(shù),下標表示序號。3.4.4識別與解釋:結構法匹配形狀數(shù)1083.4.4識別與解釋:結構法匹配形狀數(shù)(2)基本概念-形狀數(shù)的距離b.兩個區(qū)域邊界A和B形狀數(shù)的距離D(A,B)相似級別的倒數(shù)：D(A,B)=1/k 距離滿足如下性質(zhì)：D(A,B)0D(A,B)=0iffA=BD(A,C)max[D(A,B),D(B,C)]3.4.4識別與解釋:結構法匹配形狀數(shù)1093.4.4識別與解釋:結構法匹配形狀數(shù)(3)算法思想a.用不同密度的網(wǎng)格劃分邊界區(qū)域，獲得不同序數(shù)的形狀數(shù)。b.如果使用相似級別k，k越大說明越相似。c.如果使用相似距離D，D越小說明越相似d.可以利用相似樹來進行判別3.4.4識別與解釋:結構法匹配形狀數(shù)1103.4.4識別與解釋:結構法匹配形狀數(shù)（4）舉例假設我們有一個形狀F，想在另5個形狀（A，B，C，D，E）中找到與其最相似的