3.3識(shí)別與解釋.ppt

1、圖像分析技術(shù)分類的三種基本范疇,知識(shí)庫(kù),分割,表示與描述,識(shí)別 與 解釋,預(yù)處理,圖像獲取,低級(jí)處理,高級(jí)處理,中級(jí)處理,結(jié)果,問(wèn)題,3.圖像處理與分析,3.3 識(shí)別與解釋,3.3.1 模式與模式類 3.3.2 統(tǒng)計(jì)模式識(shí)別 3.3.3 神經(jīng)網(wǎng)絡(luò)與支持向量機(jī) 3.3.4 結(jié)構(gòu)模式識(shí)別,圖像識(shí)別與解釋的基本方法 統(tǒng)計(jì)模式識(shí)別：用向量形式表達(dá)模式；分派模式向量到不同的模式類 結(jié)構(gòu)模式識(shí)別：用符號(hào)匹配，模式被表示為符號(hào)形式（如形狀數(shù)、串和樹(shù)） 圖像解釋的方法：圖像解釋技術(shù)是基于謂詞邏輯、語(yǔ)義網(wǎng)絡(luò)和特定產(chǎn)品的系統(tǒng),3.3 識(shí)別與解釋,3.3.1 模式與模式類,1.模式的定義 2.模式類的定義 3.模式

2、識(shí)別的定義 4.常用的模式序列 模式特征向量 模式串 模式樹(shù),3.3.1 模式與模式類,1.模式的定義 模式是：圖像中的一個(gè)對(duì)象或某些感興趣本質(zhì)的數(shù)量或結(jié)構(gòu)的描述 模式是：由一個(gè)或多個(gè)描述子來(lái)組成，換句話說(shuō)，模式是一個(gè)描述子的序列（名詞“特征”經(jīng)常被用來(lái)代指描述子） 模式是：一組特征或一組描述子,2.模式類的定義 模式類是具有某些公共特征的模式的系列 模式類用w1,w2,wM表示，M是類的個(gè)數(shù) 3.模式識(shí)別的定義 根據(jù)圖像中對(duì)象的特征組成的模式，確定對(duì)象是屬于那一個(gè)模式類，即為模式識(shí)別,3.3.1 模式與模式類,模式與模式類舉例 1）汽車的長(zhǎng)、寬、高（L,W,H）模式 2）大客車： （L,W,

3、H）大 小轎車： （L,W,H）小 卡 車： （L,W,H）卡 從而有模式類（w大, w小, w卡） 3）從圖像中發(fā)現(xiàn)一個(gè)對(duì)象模式實(shí)例。 希望識(shí)別出該對(duì)象（L1,W1,H1），是大客車、小轎車、還是卡車模式識(shí)別,3.3.1 模式與模式類,4.常用的模式序列 三種模式序列: 1)模式特征向量 2)模式串 3)模式樹(shù) 1)模式特征向量 定義 舉例 特征的選擇,3.3.1 模式與模式類,常用的模式序列 1)模式特征向量的定義描述子構(gòu)成的向量 模式特征向量用粗體小寫字母表示，如x,y形式如下： 其中每一個(gè)xi代表第i個(gè)描述子，n是這種描述子的數(shù)量。模式特征向量被表示為一列或表示成 x = (x1, x

4、2, , xn)T， 其中T指出是轉(zhuǎn)秩,3.3.1 模式與模式類,模式特征向量舉例 假設(shè)我們想描述三種蝴蝶花（多毛的、維吉尼亞、多色的）通過(guò)測(cè)量它們花瓣的寬度和長(zhǎng)度。這里涉及一個(gè)兩維的模式特征向量： 其中x1、x2分別對(duì)應(yīng)花瓣的長(zhǎng)和寬 三種模式類用w1、w2、w3表示,x =,x1 x2,3.3.1 模式與模式類,由于所有的花瓣在寬和長(zhǎng)上都有某種程度的變化，所以描述這些花瓣的模式特征向量也將有變化，不僅在不同的類之間，而且也在類的內(nèi)部 在這種情況下每一種花變成二維歐幾里德空間的一個(gè)點(diǎn),3.3.1 模式與模式類,3.3.1 模式與模式類,模式特征向量舉例：分析 對(duì)花瓣長(zhǎng)寬的測(cè)量，成功地將多毛的蝴

5、蝶花與其它兩種分離，但對(duì)于分離維吉尼亞和多色的是失敗的。 這個(gè)結(jié)論說(shuō)明了分類的特征選擇問(wèn)題，在這個(gè)問(wèn)題中，類的可區(qū)別性的程度，完全依賴于對(duì)模式尺寸測(cè)量的選擇,3.3.1 模式與模式類,模式特征的選擇 良好的特征應(yīng)具備四個(gè)特點(diǎn) 可區(qū)別性：對(duì)不同類別對(duì)象特征值差異明顯 可靠性 ：對(duì)同類對(duì)象特征值比較接近 獨(dú)立性 ：所用的各特征之間彼此統(tǒng)計(jì)獨(dú)立 數(shù)量少 ：過(guò)多的特征數(shù)，會(huì)使系統(tǒng)復(fù)雜度提高 一般特征向量的選擇方法 盡量不選擇帶噪聲和相關(guān)度高的特征 先選擇一組直覺(jué)上合理的特征，然后逐漸減少到最佳,3.3.1 模式與模式類,2)模式串 用于以對(duì)象特征的結(jié)構(gòu)或空間關(guān)系作為模式的識(shí)別 模式串舉例：梯狀的模式,

6、3.3.1 模式與模式類,a,b,(1) S-aA (2) A-bS (3) A-b,3)模式樹(shù) 以分層目錄結(jié)構(gòu)排序的模式類，一般多采用樹(shù)結(jié)構(gòu) 模式樹(shù)舉例,3.3.1 模式與模式類,圖像,3.3.2 統(tǒng)計(jì)模式識(shí)別,1.分類器的設(shè)計(jì)和訓(xùn)練 2.決策論法的基本概念 3.分類器 最小距離分類器 相關(guān)匹配分類器,3.3.2統(tǒng)計(jì)模式識(shí)別,1.分類器的設(shè)計(jì)與訓(xùn)練 分類器一般設(shè)計(jì)方法 分類器對(duì)每一模式類，給出一個(gè)典型模板 對(duì)每一個(gè)遇到的待分類對(duì)象,計(jì)算該對(duì)象與個(gè)典型模板之間的相似程度 相似值是對(duì)象的函數(shù) 函數(shù)取值的不同，決定對(duì)象屬于那一模式類,3.3.2統(tǒng)計(jì)模式識(shí)別,-分類器一般設(shè)計(jì)規(guī)則 分類器規(guī)則都轉(zhuǎn)換為

7、閾值規(guī)則 將測(cè)量空間劃分成互不重疊的區(qū)域 每一個(gè)模式類對(duì)應(yīng)一個(gè)區(qū)域（或多個(gè)） 對(duì)象的分類函數(shù)值落在哪個(gè)區(qū)域，對(duì)象就屬那類 某些情況，某些區(qū)域?yàn)椤盁o(wú)法確定”類,3.3.2統(tǒng)計(jì)模式識(shí)別,-分類器的訓(xùn)練 決策規(guī)則決定后，需要確定分類器的閾值 實(shí)現(xiàn)的方法是用一組已知對(duì)象訓(xùn)練分類器 訓(xùn)練對(duì)象集由每類已被正確識(shí)別的部分對(duì)象組成 通過(guò)對(duì)這些對(duì)象的度量，定出能夠?qū)Q策面劃分成不同區(qū)域的合理閾值 使分類器對(duì)訓(xùn)練對(duì)象樣本集分類準(zhǔn)確性最高,3.3.2統(tǒng)計(jì)模式識(shí)別,2.統(tǒng)計(jì)模式識(shí)別的基本概念 統(tǒng)計(jì)模式識(shí)別的定義 設(shè)：模式特征向量：x = (x1, x2, ,xn)T， 對(duì)于：M個(gè)模式類 w1,w2,wM， 尋找M個(gè)決

8、策函數(shù)d1(x), d2(x), , dM(x)，具有這 樣的特性：如果模式實(shí)例x屬于模式類wi,那么： di(x) dj(x) j = 1, 2, , M; j i換句話說(shuō)，如果一個(gè)未知模式對(duì)象x屬于第i個(gè)模式類， 把x代入所有的決策函數(shù)，di(x)的取值最大。,3.3.2統(tǒng)計(jì)模式識(shí)別,-決策邊界的定義 對(duì)于模式特征向量x，如果決策函數(shù)值有： di(x) - dj(x) = 0 此x向量，被稱為wi與wj的決策邊界。 通常用一個(gè)單一的函數(shù)標(biāo)識(shí)兩個(gè)類之間的決策 邊界，定義為：dij(x) = di(x) - dj(x) = 0 如果 dij(x) 0 x 屬于類wi 如果 dij(x) 0 x

9、 屬于類wj,3.3.2統(tǒng)計(jì)模式識(shí)別,3. 分類器 最小距離分類器 以蝴蝶花的例子為例： （1）為多色（w1）和多毛（w2 ）的兩種蝴蝶花，確定兩個(gè)原形（或稱模板）m1和m2 （2）對(duì)于一個(gè)未知模式向量x，判斷x與m1和m2的距離，如果與m1的距離小于與m2的距離，則x屬于w1，否則屬于w2 。,3.3.2統(tǒng)計(jì)模式識(shí)別,1,2,3,4,5,6,7,x1 花瓣長(zhǎng),0.5,1.0,1.5,2.0,2.5,3.0,x2 花瓣寬,多毛的,多色的,m1,m2,3.3.2統(tǒng)計(jì)模式識(shí)別,-最小距離分類器 1）算法思想： 對(duì)于M個(gè)模式類 wi i = 1,2,.,M 為每一個(gè)模式類確定一個(gè)原形模式特征向量mi

10、 對(duì)于一個(gè)未知模式特征向量x，如果x與mi的距離最小，就稱，x屬于wi,3.3.2統(tǒng)計(jì)模式識(shí)別,-最小距離分類器 2）最小距離分類器定義（訓(xùn)練）： 1計(jì)算模式類wj的原形向量： mj = 1/Nj x j = 1,2, , M xwj 其中Nj是屬于模式類wj的模式向量的個(gè)數(shù)。 通過(guò)計(jì)算已知屬于wj的模式特征向量的各分量的 均值得到原形模式特征向量mj,3.3.2統(tǒng)計(jì)模式識(shí)別,2計(jì)算x 與 mi的距離 dj(x) = | x mj | j = 1, 2, , M 其中 | a | = (aTa)1/2是歐幾里德范式（平方和開(kāi)方） dj(x) = (x mj )T (x mj ) 1/2 j =

11、 1, 2, , M 3決策 如果，di(x) = min(dj(x) j = 1, 2, , M 就說(shuō)：x 屬于wi,3.3.2統(tǒng)計(jì)模式識(shí)別,為便于計(jì)算，改寫成求最大的標(biāo)準(zhǔn)形式，決策函數(shù)為： dj(x) = xTmj 1/2mjTmj j = 1,2, , M 如果，di(x) = max(dj(x) j = 1, 2, , 就說(shuō)：x 屬于wi 4用上式得到的類wi和wj之間的決策邊界是： dij(x) = di(x) - dj(x) = xT（mi mj） 1/2(mi mj)T(mi mj) = 0,3.3.2統(tǒng)計(jì)模式識(shí)別,3）舉例： 多色的和多毛的蝴蝶花，用w1和w2分別表示， 有簡(jiǎn)單

12、的原形向量 m1 = (4.4, 1.3)T m2 = (1.5, 0.3)T 決策函數(shù)是： d1(x) = xTm1 1/2m1Tm1 = 4.3x1 + 1.3x2 10.1 d2(x) = xTm2 1/2m2Tm2 = 1.5x1 + 0.3x2 1.17 決策邊界的等式： d12(x) = d1(x) d2(x) = 2.8x1 1.0 x2 8.9 = 0,3.3.2統(tǒng)計(jì)模式識(shí)別,1,2,3,4,5,6,7,x1 花瓣長(zhǎng),0.5,1.0,1.5,2.0,2.5,3.0,x2 花瓣寬,多毛的,多色的,3.3.2統(tǒng)計(jì)模式識(shí)別,分類器 相關(guān)匹配分類器 (1) 相關(guān)匹配的基本思想: a.

13、用樣板子圖像直接作為模式特征（不是用描述子） b. 通過(guò)子圖像與原圖像直接進(jìn)行相關(guān)計(jì)算，把相關(guān)計(jì)算作為決策函數(shù) c. 相關(guān)計(jì)算獲得最大值的位置，就被認(rèn)為匹配成功,3.3.2統(tǒng)計(jì)模式識(shí)別,相關(guān)匹配分類器 (1) 相關(guān)匹配基本思想,3.3.2統(tǒng)計(jì)模式識(shí)別,分類器 相關(guān)匹配分類器,M,x,原點(diǎn),N,y,f(x,y),(s,t),J,s,w(x+s,y+t),K,t,3.3.2統(tǒng)計(jì)模式識(shí)別,分類器 相關(guān)匹配分類器 (2) 算法描述 決策函數(shù)是相關(guān)函數(shù) c(s,t) = f(x,y)w(x+s,y+t) x y 對(duì)圖像的每一個(gè)點(diǎn)進(jìn)行相關(guān)計(jì)算，只計(jì)算重疊部分 問(wèn)題：在邊界處將失去準(zhǔn)確性，其誤差與子圖像的尺

14、寸成正比,3.3.2統(tǒng)計(jì)模式識(shí)別,相關(guān)匹配分類器 (3) 改進(jìn) 相關(guān)函數(shù)對(duì)振幅的變化太敏感，f(x,y)加倍，c(s,t)也加倍。用相關(guān)系數(shù)函數(shù)代替相關(guān)函數(shù) f(x,y) f(x,y)w(x-s,y-t) w (s,t)= f(x,y)f(x,y)2w(x-s,y-t) w21/2 x y x y (s,t)的值域?yàn)椋?1，1）,3.3.2統(tǒng)計(jì)模式識(shí)別,相關(guān)匹配分類器 (4) 對(duì)旋轉(zhuǎn)和比例變化的分析 問(wèn)題： 當(dāng)被匹配圖像中，對(duì)象的尺寸和角度與模式不一致，此方法將失效。 改進(jìn)： 尺寸的正則化，解決空間比例的問(wèn)題。正則化模板與原圖。 如果知道原圖像的旋轉(zhuǎn)角度，我們可以通過(guò)旋轉(zhuǎn)原圖像，對(duì)齊模式解決。

15、 結(jié)論: 如果被匹配的對(duì)象的角度任意，此方法不能用于這種問(wèn)題。,3.3.2統(tǒng)計(jì)模式識(shí)別,分類器 相關(guān)性匹配分類器 (5) 關(guān)于空域計(jì)算 相關(guān)函數(shù)，可以在頻域計(jì)算。 f(x,y)w(x,y) f(s,t)w(s,t) 但無(wú)論在何種情況下，都沒(méi)有更有優(yōu)勢(shì)的理論根據(jù)。相關(guān)系數(shù)方式只能在空域進(jìn)行。,3.3.3神經(jīng)網(wǎng)絡(luò)和支持向量機(jī),（1）感知機(jī) （2）支持向量機(jī),（1）感知機(jī),最基本的感知機(jī)建立能將兩個(gè)線性可分訓(xùn)練集分開(kāi)的線性決策函數(shù),對(duì)模式矢量增加第n + 1個(gè)元素 構(gòu)建一個(gè)擴(kuò)充模式矢量y，讓yi = xi， i = 1, 2, , n，且后面加一個(gè)元素yn+1 = 1 其中y = y1 y2 yn

16、1T是個(gè)擴(kuò)充模式矢量，w = w1 w2 wn wn+1T是個(gè)權(quán)矢量 關(guān)鍵問(wèn)題：用模式矢量的給定訓(xùn)練集確定w,（1）感知機(jī),1）.線性可分類 由兩個(gè)線性可分訓(xùn)練集獲取權(quán)矢量 令w(1)代表一個(gè)任意選定的初始權(quán)矢量 如果 y(k) s1，wT(k)y(k) 0 如果 y(k) s2，wT(k)y(k) 0 否則：,（1）感知機(jī),1）.線性可分類 兩個(gè)訓(xùn)練集，每個(gè)包括兩個(gè)模式 先將模式擴(kuò)充，對(duì)類s1得到訓(xùn)練集0 0 1T, 0 1 1T，對(duì)類s2得到訓(xùn)練集1 0 1T, 1 1 1T,（1）感知機(jī),2）.線性不可分類 最小化實(shí)際響應(yīng)和希望響應(yīng)間的誤差 沿J(w)負(fù)梯度的方向逐步增加w以尋找上述函數(shù)

17、的最小值。最小值應(yīng)在r = wTy時(shí)出現(xiàn) 通用的梯度下降算法可寫成：,（1）感知機(jī),2）.線性不可分類 寫成德?tīng)査―elta）校正算法的形式 權(quán)矢量的誤差 誤差的變化量 改變權(quán)重能將誤差減少a|y(k)|2，下一輪繼續(xù),（1）感知機(jī),（2）支持向量機(jī),1.線性可分類 線性分類器的設(shè)計(jì)目的：要設(shè)計(jì)一個(gè)超平面 滿足條件的超平面 一般不惟一 離開(kāi)兩個(gè)類都比較 遠(yuǎn)的超平面分類的結(jié)果 會(huì)更好些，可能的錯(cuò)誤率 也會(huì)更小一些,1.線性可分類 對(duì)每個(gè)朝向，與兩個(gè)類距離相等的超平面應(yīng)該是與兩個(gè)類都有最大距離的超平面 確定能給出類距離 最大的朝向的超平面 從一個(gè)點(diǎn)到一個(gè)超 平面的距離,（2）支持向量機(jī),1.線性

18、可分類 對(duì)每個(gè)類si，記其標(biāo)號(hào)為ti，其中t1 = 1，t2 = 1?，F(xiàn)在問(wèn)題變?yōu)椋河?jì)算超平面的w和w0，在滿足下列條件 的情況下最小化 用拉格朗日乘數(shù)法來(lái)解,（2）支持向量機(jī),1.線性可分類 結(jié)果為 最優(yōu)解的向量參數(shù)w是Ns個(gè)（Ns N）與li 0相關(guān)的特征向量的線性組合（支持向量） 支持向量機(jī)：最優(yōu)的超平面分類器,（2）支持向量機(jī),2.線性不可分類 訓(xùn)練特征向量可以分成以下三類： (1)向量落在分類帶之外且被正確地分了類 (2)向量落在分類帶之內(nèi)且被正確地分了類 (3)向量被錯(cuò)誤地分了類,（2）支持向量機(jī),3.3.4 結(jié)構(gòu)模式識(shí)別,1.匹配形狀數(shù) 2.匹配串,3.3.4結(jié)構(gòu)模式識(shí)別,統(tǒng)計(jì)模

19、式識(shí)別，通過(guò)量化的方法處理模式，最大限度地忽略了模式形狀的內(nèi)在結(jié)構(gòu)關(guān)系。 結(jié)構(gòu)模式識(shí)別，則力求通過(guò)準(zhǔn)確地抓住這些不同模式類的內(nèi)在結(jié)構(gòu)關(guān)系來(lái)進(jìn)行模式識(shí)別。,3.3.4結(jié)構(gòu)模式識(shí)別,1. 匹配形狀數(shù) (1) 匹配形狀數(shù)的基本思想 通過(guò)比較兩個(gè)對(duì)象邊界的形狀數(shù)的相似程度，來(lái)匹配對(duì)象。例如： 未知模式原形模式類,3.3.4結(jié)構(gòu)模式識(shí)別,匹配形狀數(shù) (2) 基本概念-相似級(jí)別 a.兩個(gè)區(qū)域邊界的相似級(jí)別k的定義： 用相同形狀數(shù)的最大序號(hào)表示：即： 當(dāng)考慮用4向鏈碼表示的封閉區(qū)域邊界的形狀數(shù)時(shí)，A和B具有相似級(jí)別k，當(dāng)且僅當(dāng)滿足： s4(A) = s4(B), s6(A) = s6(B), s8(A) =

20、 s8(B), sk(A) = sk(B), sk+2(A) sk+2(B), sk+4(A) sk+4(B), ， 這里s表示形狀數(shù),下標(biāo)表示序號(hào)。,3.3.4結(jié)構(gòu)模式識(shí)別,匹配形狀數(shù) (2) 基本概念-形狀數(shù)的距離 b.兩個(gè)區(qū)域邊界A和B形狀數(shù)的距離D(A,B) 相似級(jí)別的倒數(shù) ：D(A,B) = 1 / k 距離滿足如下性質(zhì)： D(A,B) 0 D(A,B) = 0 iff A=B D(A,C) maxD(A,B),D(B,C),3.3.4結(jié)構(gòu)模式識(shí)別,匹配形狀數(shù) (3) 算法思想 a. 用不同密度的網(wǎng)格劃分邊界區(qū)域，獲得不同序數(shù)的形狀數(shù)。 b. 如果使用相似級(jí)別k，k越大說(shuō)明越相似。

21、c. 如果使用相似距離D，D越小說(shuō)明越相似 d. 可以利用相似樹(shù)來(lái)進(jìn)行判別,3.3.4結(jié)構(gòu)模式識(shí)別,匹配形狀數(shù) （4）舉例 假設(shè)我們有一個(gè)形狀F，想在另5個(gè)形狀（A，B，C，D，E）中找到與其最相似的形狀,A,B,C,D,E,F,3.3.4結(jié)構(gòu)模式識(shí)別,這個(gè)問(wèn)題類似于有五個(gè)原型形狀，想找出一個(gè)給定的尚不確定的形狀的最佳匹配的問(wèn)題。這個(gè)問(wèn)題可以利用相似樹(shù)和矩陣來(lái)可視化,4,6,8,10,12,14,ABCDEF,ABCDEF,BCDEF,A,A,A,A,BE,CF,B,E,D,D,D,CF,C,F,B,E,A B C D E F,A,B,E,D,C,F, 6 6 6 6 6, 8 8 10 8, 8 8 12, 8 8, 8,3.3.4結(jié)構(gòu)模式識(shí)別,2.串匹配 （1）串匹配的基本思想 比較兩個(gè)邊界串編碼的相似程度，來(lái)進(jìn)行匹配 （2）三個(gè)基本概念 設(shè): 兩個(gè)區(qū)域邊界A和B已分別被編碼 為串a(chǎn)1a2an和b1b2bm。,a3a3a3a3a3a3a3a3,a2a2a3a3,3.3.4結(jié)構(gòu)模式識(shí)別,串匹配 a.兩個(gè)串的匹配數(shù)M: 當(dāng) ak= bk 時(shí)我們說(shuō)發(fā)生了一個(gè)匹配。令M代表A、B中匹配的總數(shù)。 b.不匹配的符號(hào)數(shù)量Q： Q = max（|A|，|B|）- M 這里|arg|是字符串的長(zhǎng)度。當(dāng)且僅當(dāng)A和B完全相同時(shí)，Q = 0。,3.