數(shù)字圖像處理課程北大計(jì)算所124m版第03章數(shù)字圖象分析05m

數(shù)字圖像處理北京大學(xué)計(jì)算機(jī)研究所陳曉鷗第四節(jié)識(shí)別與解釋3.4.1圖像分析引言3.4.2圖像分析系統(tǒng)的組成3.4.3模式與模式類3.4.4決策論法3.4.5結(jié)構(gòu)法3.4.1圖像分析引言圖像分析引言圖像分析的定義圖像分析的目標(biāo)自動(dòng)圖像分析系統(tǒng)行為能力的概念化分類自動(dòng)圖像分析系統(tǒng)的現(xiàn)狀3.4.1圖像分析引言圖像分析的定義圖像分析是一個(gè)：

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

其中每一個(gè)xi代表第i個(gè)描述子，n是這種描述子的數(shù)量。模式特征向量被表示為一列或表示成

x=(x1,x2,…,xn)T，

其中T指出是轉(zhuǎn)秩x=

x1x2.xn3.4.3模式與模式類模式特征向量舉例

假設(shè)我們想描述三種蝴蝶花（多毛的、維吉尼亞、多色的）通過測量它們花瓣的寬度和長度。這里涉及一個(gè)兩維的模式特征向量：其中x1、x2分別對(duì)應(yīng)花瓣的長和寬三種模式類用w1、w2、w3表示x=

x1x23.4.3模式與模式類

由于所有的花瓣在寬和長上都有某種程度的變化，所以描述這些花瓣的模式特征向量也將有變化，不僅在不同的類之間，而且也在類的內(nèi)部 在這種情況下每一種花變成二維歐幾里德空間的一個(gè)點(diǎn)3.4.3模式與模式類3.4.3模式與模式類1234567x1花瓣長0.51.01.52.02.53.0x2花瓣寬多毛的維吉尼亞多色的模式特征向量舉例：分析

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

(1)S->aA (2)A->bS(3)A->b模式樹

以分層目錄結(jié)構(gòu)排序的模式類，一般多采用樹結(jié)構(gòu)模式樹舉例3.4.3模式與模式類圖像城市田園草地森林娛樂區(qū)商業(yè)區(qū)娛樂區(qū)商業(yè)區(qū)城區(qū)內(nèi)城市郊公路3.4.4決策論法決策論法分類器的設(shè)計(jì)和訓(xùn)練決策論法的基本概念分類器最小距離分類器相關(guān)匹配分類器3.4.4決策論法分類器的設(shè)計(jì)與訓(xùn)練分類器一般設(shè)計(jì)方法分類器對(duì)每一模式類，給出一個(gè)典型摸板對(duì)每一個(gè)遇到的待分類對(duì)象計(jì)算該對(duì)象與個(gè)典型摸板之間的相似程度相似值是對(duì)象的函數(shù)函數(shù)取值的不同，決定對(duì)象屬于那一模式類3.4.4決策論法分類器的設(shè)計(jì)與訓(xùn)練分類器一般設(shè)計(jì)規(guī)則分類器規(guī)則都轉(zhuǎn)換為閾值規(guī)則將測量空間劃分成互不重疊的區(qū)域每一個(gè)模式類對(duì)應(yīng)一個(gè)區(qū)域（或多個(gè)）對(duì)象的分類函數(shù)值落在哪個(gè)區(qū)域，對(duì)象就屬那類某些情況，某些區(qū)域?yàn)椤盁o法確定”類3.4.4決策論法分類器的設(shè)計(jì)與訓(xùn)練分類器的訓(xùn)練決策規(guī)則決定后，需要確定分類器的閾值實(shí)現(xiàn)的方法是用一組已知對(duì)象訓(xùn)練分類器訓(xùn)練對(duì)象集由每類已被正確識(shí)別的部分對(duì)象組成通過對(duì)這些對(duì)象的度量，定出能夠?qū)Q策面劃分成不同區(qū)域的合理閾值使分類器對(duì)訓(xùn)練對(duì)象樣本集分類準(zhǔn)確性最高3.4.4識(shí)別與解釋:決策論法決策論法的基本概念決策論識(shí)別法的定義設(shè)：模式特征向量：x=(x1,x2,…,xn)T，對(duì)于：M個(gè)模式類

w1,w2,…,wM，尋找M個(gè)決策函數(shù)d1(x),d2(x),…,dM(x)，具有這樣的特性：如果模式實(shí)例x屬于模式類wi,那么：

di(x)>dj(x) j=1,2,…,M;j≠i

換句話說，如果一個(gè)未知模式對(duì)象x屬于第i個(gè)模式類，把x代入所有的決策函數(shù)，di(x)的取值最大。3.4.4識(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)>0x屬于類wi

如果dij(x)<0x屬于類wj3.4.4識(shí)別與解釋:決策論法分類器最小距離分類器以蝴蝶花的例子為例：（1）為多色（w1）和多毛（w2）的兩種蝴蝶花，確定兩個(gè)原形（或稱模板）m1和m2（2）對(duì)于一個(gè)未知模式向量x，判斷x與m1和m2的距離，如果與m1的距離小于與m2的距離，則x屬于w1，否則屬于w2。3.4.4識(shí)別與解釋:決策論法1234567x1花瓣長0.51.01.52.02.53.0x2花瓣寬多毛的多色的m1m2x3.4.4識(shí)別與解釋:決策論法分類器最小距離分類器1）算法思想：對(duì)于M個(gè)模式類wii=1,2,...,M

為每一個(gè)模式類確定一個(gè)原形模式特征向量mi對(duì)于一個(gè)未知模式特征向量x，如果x與mi的距離最小，就稱，x屬于wi3.4.4識(shí)別與解釋:決策論法分類器最小距離分類器2）最小距離分類器定義（訓(xùn)練）：〈1〉計(jì)算模式類wj的原形向量：

mj=1/Nj

x

j=1,2,…,M

xwj

其中Nj是屬于模式類wj的模式向量的個(gè)數(shù)。通過計(jì)算已知屬于wj的模式特征向量的各分量的均值得到原形模式特征向量mj3.4.4識(shí)別與解釋:決策論法分類器最小距離分類器〈2〉計(jì)算x與mi的距離dj(x)=

||x

–mj

||

j=1,2,…,M

其中||a||=(aTa)1/2是歐幾里德范式（平方和開方）dj(x)=

((x

–mj

)T(x

–mj

))1/2

j=1,2,…,M〈3〉 決策如果，di(x)=min(dj(x))

j=1,2,…,M

就說：x屬于wi3.4.4識(shí)別與解釋:決策論法分類器最小距離分類器為便于計(jì)算，改寫成求最大的標(biāo)準(zhǔn)形式，決策函數(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識(shí)別與解釋:決策論法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識(shí)別與解釋:決策論法1234567x1花瓣長0.51.01.52.02.53.0x2花瓣寬多毛的多色的3.4.4識(shí)別與解釋:決策論法分類器相關(guān)匹配分類器(1)相關(guān)匹配的基本思想:a.用樣板子圖像直接作為模式特征（不是用描述子）b.通過子圖像與原圖像直接進(jìn)行相關(guān)計(jì)算，把相關(guān)計(jì)算作為決策函數(shù)c.相關(guān)計(jì)算獲得最大值的位置，就被認(rèn)為匹配成功3.4.4識(shí)別與解釋:決策論法相關(guān)匹配分類器(1)相關(guān)匹配基本思想3.4.4識(shí)別與解釋:決策論法分類器相關(guān)匹配分類器Mx原點(diǎn)Nyf(x,y)(s,t)Jsw(x-s,y-t)Kt3.4.4識(shí)別與解釋:決策論法分類器相關(guān)匹配分類器(2)算法描述決策函數(shù)是相關(guān)函數(shù)c(s,t)=∑∑f(x,y)w(x-s,y-t)

xy

對(duì)圖像的每一個(gè)點(diǎn)進(jìn)行相關(guān)計(jì)算，只計(jì)算重疊部分 問題：在邊界處將失去準(zhǔn)確性，其誤差與子圖像的尺寸成正比3.4.4識(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)]2∑∑[w(x-s,y-t)–w]2}1/2

xy

xy

γ(s,t)的值域?yàn)椋?1，1）3.4.4識(shí)別與解釋:決策論法相關(guān)匹配分類器(4)對(duì)旋轉(zhuǎn)和比例變化的分析問題：

當(dāng)被匹配圖像中，對(duì)象的尺寸和角度與模式不一致，此方法將失效。改進(jìn)：尺寸的正則化，解決空間比例的問題。正則化模板與原圖。如果知道原圖像的旋轉(zhuǎn)角度，我們可以通過旋轉(zhuǎn)原圖像，對(duì)齊模式解決。結(jié)論:

如果被匹配的對(duì)象的角度任意，此方法不能用于這種問題。3.4.4識(shí)別與解釋:決策論法分類器相關(guān)性匹配分類器(5)關(guān)于空域計(jì)算相關(guān)函數(shù)，可以在頻域計(jì)算。

f(x,y)w(x,y)f(s,t)w(s,t)但無論在何種情況下，都沒有更有優(yōu)勢(shì)的理論根據(jù)。相關(guān)系數(shù)方式只能在空域進(jìn)行。3.4.4識(shí)別與解釋:結(jié)構(gòu)法結(jié)構(gòu)法匹配形狀數(shù)匹配串3.4.4識(shí)別與解釋:結(jié)構(gòu)法結(jié)構(gòu)法

決策法，通過量化的方法處理模式，最大限度地忽略了模式形狀的內(nèi)在結(jié)構(gòu)關(guān)系。

結(jié)構(gòu)法，則力求通過準(zhǔn)確地抓住這些不同模式類的內(nèi)在結(jié)構(gòu)關(guān)系來進(jìn)行模式識(shí)別。3.4.4識(shí)別與解釋:結(jié)構(gòu)法匹配形狀數(shù)(1)匹配形狀數(shù)的基本思想 通過比較兩個(gè)對(duì)象邊界的形狀數(shù)的相似程度，來匹配對(duì)象。例如： 未知模式 原形模式類3.4.4識(shí)別與解釋:結(jié)構(gòu)法匹配形狀數(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)=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.4.4識(shí)別與解釋:結(jié)構(gòu)法匹配形狀數(shù)(2)基本概念-形狀數(shù)的距離b.兩個(gè)區(qū)域邊界A和B形狀數(shù)的距離D(A,B)

相似級(jí)別的倒數(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í)別與解釋:結(jié)構(gòu)法匹配形狀數(shù)(3)算法思想a.用不同密度的網(wǎng)格劃分邊界區(qū)域，獲得不同序數(shù)的形狀數(shù)。b.如果使用相似級(jí)別k，k越大說明越相似。c.如果使用相似距離D，D越小說明越相似d.可以利用相似樹來進(jìn)行判別3.4.4識(shí)別與解釋:結(jié)構(gòu)法匹配形狀數(shù)（4）舉例假設(shè)我們有一個(gè)形狀F，想在另5個(gè)形狀（A，B，C，D，E）中找到與其最相似的形狀A(yù)BCDEF3.4.4識(shí)別與解釋:結(jié)構(gòu)法

這個(gè)問題類似于有五個(gè)原型形狀，想找出一個(gè)給定的尚不確定的形狀的最佳匹配的問題。這個(gè)問題可以利用相似樹和矩陣來可視化468101214ABCDEFABCDEFBCDEFAAAABECFBEDDDCFCFBEABCDEFABEDCF666668810888128883.4.4識(shí)別與解釋:結(jié)構(gòu)法串匹配（1）串匹配的基本思想比較兩個(gè)邊界串編碼的相似程度，來進(jìn)行匹配（2）三個(gè)基本概念 設(shè):兩個(gè)區(qū)域邊界A和B已分別被編碼為串a(chǎn)1a2…an和b1b2…bm。a3a3a3a3a3a3a3a3a2a2a3a33.4.4識(shí)別與解釋:結(jié)構(gòu)法串匹配a.兩個(gè)串的匹配數(shù)M:

當(dāng)ak=bk時(shí)我們說發(fā)生了一個(gè)匹配。令M代表A、B中匹配的總數(shù)。b.不匹配的符號(hào)數(shù)量Q：

Q=max（|A|，|B|）-M

這里|arg|是字符串的長度。當(dāng)且僅當(dāng)A和B完全相同時(shí)，Q=0。3.4.4識(shí)別與解釋:結(jié)構(gòu)法串匹配

c.A和B相似度的簡便衡量R:

R=M/Q=M/[max(|A|,|B|)-M]

因此， 當(dāng)A和B完全匹配時(shí)，R=；當(dāng)A和B中任何字符都不匹配時(shí)，

M=0，R=0。3.4.4識(shí)別與解釋:結(jié)構(gòu)法串匹