數(shù)字圖像識別與解釋ppt課件

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

2、解釋識別與解釋3.4.1 識別與解釋:圖像分析引言 圖像分析的定義 圖像分析是一個發(fā)現(xiàn)、辨認(rèn)和理解模式的過程，這些模式都與執(zhí)行與圖像相關(guān)的任務(wù)有關(guān)。 圖像分析的目標(biāo) 計算機(jī)圖像分析的主要目的之一是，賦予某些具有感覺能力的機(jī)器，以類似人的大腦的能力。例如OCR第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.1 識別與解釋:圖像分析引言 自動圖像分析系統(tǒng)行為能力的概念化分類 獲取、發(fā)現(xiàn)信息：從背景中提取有關(guān)信息 學(xué)習(xí)、應(yīng)用知識：籠統(tǒng)、歸納信息特征的學(xué)習(xí)過程，并應(yīng)用到新的對象中。 構(gòu)造、推理知識：從不完整的信息中構(gòu)造推論出新的知識，并加以應(yīng)用。第三章第三章 數(shù)字圖像

3、分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.1 識別與解釋:圖像分析引言 自動圖像分析系統(tǒng)的現(xiàn)狀 我們可以設(shè)計出這種系統(tǒng)，但仍然缺乏理論依據(jù)。有待人類視覺認(rèn)識理論的進(jìn)一步研究。 我們可以做出在某一應(yīng)用上超過人的能力的系統(tǒng)，但缺乏擴(kuò)展性。過分依賴應(yīng)用。第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.2 識別與解釋:圖像分析系統(tǒng)組的成 圖像分析技術(shù)分類的三種基本范疇 低級處理：圖像獲取、預(yù)處理，不需要智能 中級處理：圖像分割、表示與描述，需要智能 高級處理：圖像識別、解釋，缺少理論，為降低難度，設(shè)計得更專用。第三章第三章 數(shù)字圖像分析數(shù)字圖像分析

4、第四節(jié)第四節(jié) 識別與解釋識別與解釋 圖像分析技術(shù)分類的三種基本范疇知識庫知識庫分割分割表示與描述表示與描述識別識別與與解釋解釋預(yù)處理預(yù)處理圖像獲取圖像獲取低級處理高級處理中級處理結(jié)果問題3.4.2 識別與解釋:圖像分析系統(tǒng)組的成第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋 圖像識別與解釋的基本方法 識別的統(tǒng)計分類方法：用向量形式表達(dá)模式；分派模式向量到不同的模式類。 識別的結(jié)構(gòu)方法：用符號匹配，模式被表示為符號形式如形狀數(shù)、串和樹） 圖像解釋的方法：圖像解釋技術(shù)是基于謂詞邏輯、語義網(wǎng)絡(luò)和特定產(chǎn)品的系統(tǒng)。3.4.2 識別與解釋:圖像分析系統(tǒng)組的成第三章第三章 數(shù)字圖

5、像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.3 識別與解釋:模式與模式類 模式與模式類 模式的定義 模式類的定義 模式識別的定義 常用的模式序列 模式向量 模式串 模式樹第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.3 識別與解釋:模式與模式類 模式的定義 模式是圖像中的一個對象或某些感興趣本質(zhì)的數(shù)量或結(jié)構(gòu)的描述 模式是由一個或多個描述子來組成，換句話說，模式是一個描述子的序列名詞“特征經(jīng)常被用來代指描述子） 模式是一組特征或一組描述子第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋 模式類的定義 模式類是具有某些

6、公共特征的模式的系列 模式類用w1,w2,wM表示，M是類的個數(shù) 模式識別的定義 根據(jù)圖像中對象的特征組成的模式，確定對象是屬于那一個模式類，即為模式識別 模式與模式類舉例 已知汽車的長、寬、高x1,x2,x3）,希望識別出，大客車、小轎車、卡車w1,w2,w3）3.4.3 識別與解釋:模式與模式類第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋 常用的模式序列 模式向量、模式串、模式樹 模式向量 模式向量用粗體的小寫字母表示，如x,y形式如下： 其中每一個xi代表第i個描述子，n是這種描述子的數(shù)量。模式向量被表示為一列或表示成 x = (x1, x2, , xn)T

7、， 其中T指出是轉(zhuǎn)秩x = x1x2.xn3.4.3 識別與解釋:模式與模式類第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋模式向量舉例 假設(shè)我們想描述三種蝴蝶花多毛的、維吉尼亞、多色的通過測量它們花瓣的寬度和長度。這里涉及一個兩維的模式向量： 其中x1、x2分別對應(yīng)花瓣的長和寬 三種模式類用w1、w2、w3表示x = x1x23.4.3 識別與解釋:模式與模式類第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋 由于所有的花瓣在寬和長上都有某種程度的變化，所以描述這些花瓣的模式向量也將有變化，不僅在不同的類之間，而且也在類的內(nèi)部在這種情況下

8、每一種花變成二維歐幾里德空間的一個點(diǎn)3.4.3 識別與解釋:模式與模式類第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.3 識別與解釋:模式與模式類1234567x1 花瓣長0.51.01.52.02.53.0 x2 花瓣寬多毛的維吉尼亞多色的第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋對結(jié)果的分析 對花瓣長寬的測量，成功地將多毛的蝴蝶花與其它兩種分離，但對于分離維吉尼亞和多色的是失敗的。 這個結(jié)論說明了分類的特性選擇問題，在這個問題中，類的可分離性的程度，完全依賴于對模式尺寸測量的選擇3.4.3 識別與解釋:模式與模式類第三章第

9、三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋模式串 用于以對象特征的結(jié)構(gòu)或空間關(guān)系作為模式的識別模式串舉例：梯狀的模式3.4.3 識別與解釋:模式與模式類abaaabbb(1) S-aA(2) A-bS (3) A-b第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋模式樹 以分層目錄結(jié)構(gòu)排序的模式類，一般多采用樹結(jié)構(gòu)模式樹舉例3.4.3 識別與解釋:模式與模式類圖像圖像城市城市田園田園城區(qū)城區(qū)內(nèi)城內(nèi)城市郊市郊公路公路 草地草地森林森林娛樂區(qū)娛樂區(qū) 商業(yè)區(qū)商業(yè)區(qū)娛樂區(qū)娛樂區(qū) 商業(yè)區(qū)商業(yè)區(qū)第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解

10、釋識別與解釋3.4.4 識別與解釋:決策論法 決策論法 決策論法的基本概念 匹配 最小距離分類器 相關(guān)匹配第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:決策論法 決策論法的基本概念 決策論識別法的定義 設(shè)：模式向量：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)

11、的數(shù)值最大。第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:決策論法 決策論法的基本概念 決策邊界的定義 對于模式x，如果決策函數(shù)值有： di(x) - dj(x) = 0 此x值，被稱為wi與wj的決策邊界。 通常用一個單一的函數(shù)標(biāo)識兩個類之間的決策 邊境，定義為：dij(x) = di(x) - dj(x) = 0 假設(shè) dij(x) 0 x 屬于類wi 假設(shè) dij(x) 0 x 屬于類wj第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:決策論法 匹配 最小距離分類器 以蝴蝶花的例子為例：

12、 1為多色w1和多毛w2 ）的兩種蝴蝶花，確定兩個原形或稱模板m1和m2 2對于一個未知模式向量x，判斷x與m1和m2的距離，如果與m1的距離小于與m2的距離，則x屬于w1，否則屬于w2 。第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:決策論法1234567x1 花瓣長花瓣長0.51.01.52.02.53.0 x2 花瓣寬花瓣寬多毛的多毛的多色的多色的m1m2x第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:決策論法 匹配 最小距離分類器 1算法思想： 對于M個模式類 wj j = 1,2,

13、.,M 為每一個模式類確定一個原形模式向量mj 對于一個未知模式向量x，如果x與mi的距離最小，就稱，x屬于wi。第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:決策論法 匹配 最小距離分類器 2最小距離分類器定義： 1計算模式類wj的原形向量：mj = 1/Nj x j = 1,2, , M xwj 其中Nj是屬于模式類wj的模式向量的個數(shù)。 通過計算已知屬于wj的模式向量的各分量的 均值得到原形模式向量mj第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:決策論法 匹配 最小距離分類器 2計算

14、x 與 mi的距離 dj(x) = | x mj | j = 1, 2, , M 其中 | a | = (aTa)1/2是歐幾里德范式 （平方和開方） 3決策 假設(shè)，di(x) = min(dj(x) j = 1, 2, , M 就說：x 屬于wi第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:決策論法 匹配 最小距離分類器 改寫成求最大的標(biāo)準(zhǔn)形式，決策函數(shù)為： dj(x) = xTmj 1/2mjTmj j = 1,2, , M 假設(shè)，di(x) = max(dj(x) j = 1, 2, , M 就說：x 屬于wi 4類wi和wj之間的決策

15、邊界是：dij(x) = di(x) - dj(x) = xTmi mj） 1/2(mi mj)T(mi mj) = 0第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.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.1（d2(x) = xTm2 1/2m2Tm2 = 1.5x1 + 0.3x2 1.17（決策邊界的等式：（d12(x) = d1(x

16、) d2(x) = 2.8x1 1.0 x2 8.9 = 0第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:決策論法1234567x1 花瓣長花瓣長0.51.01.52.02.53.0 x2 花瓣寬花瓣寬多毛的多毛的多色的多色的第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:決策論法 匹配 相關(guān)匹配 (1) 相關(guān)匹配的基本思想: a. 用樣板子圖像直接作為模式不是用描述子） b. 通過子圖像與原圖像直接進(jìn)行相關(guān)計算，把 相關(guān)計算作為決策函數(shù)。 c. 相關(guān)計算獲得最大值的位置，就被認(rèn)為匹配 勝利。

17、第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:決策論法相關(guān)匹配(1) 相關(guān)匹配基本思想第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:決策論法 匹配 相關(guān)性匹配Mx原點(diǎn)原點(diǎn)Nyf(x,y)(s,t)Jsw(x-s,y-t)Kt第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:決策論法 匹配 相關(guān)匹配 (2) 算法描述 決策函數(shù)是相關(guān)函數(shù) c(s,t) = f(x,y)w(x-s,y-t) x y 對圖像的每一個點(diǎn)進(jìn)行相關(guān)計算，只計算重疊部分。 問

18、題：在邊界處將失去準(zhǔn)確性，其誤差與子圖像的尺寸成正比第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:決策論法相關(guān)性匹配(3) 改良相關(guān)函數(shù)對振幅的變化太敏感，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）第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:決策論法相關(guān)性匹配(4) 對旋轉(zhuǎn)和比例變化的分析當(dāng)被匹配圖

19、像中，對象的尺寸和角度與模式不一致，此方法將失效。尺寸的正則化，解決空間比例的問題。正則化模板與原圖。如果知道原圖像的旋轉(zhuǎn)角度，我們可以通過旋轉(zhuǎn)原圖像，對齊模式解決。如果被匹配的對象的角度任意，有結(jié)論:此方法不能用于這種問題。第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:決策論法 匹配 相關(guān)性匹配 (5) 關(guān)于空域計算 相關(guān)函數(shù)，可以在頻域計算。f(x,y)w(x,y) f(s,t)w(s,t) 但在何種情況下，沒有更有優(yōu)勢的理論根據(jù)。相關(guān)系數(shù)方式只能在空域進(jìn)行。第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4

20、.4 識別與解釋:結(jié)構(gòu)法 結(jié)構(gòu)法 匹配形狀數(shù) 匹配串第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:結(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ù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:結(jié)構(gòu)法 匹配形狀數(shù) (1) 匹配形狀數(shù)的基本思想 通過比較兩個對象邊界的形狀數(shù)的相似程度，來匹配對象。例如：未知模式原形模式類第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋

21、識別與解釋3.4.4 識別與解釋:結(jié)構(gòu)法 匹配形狀數(shù) (2) 基本概念-a a.兩個區(qū)域邊界的相似級別k的定義： 相同形狀數(shù)的最大序號：即： 當(dāng)考慮用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ù),下標(biāo)表示序號。第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:結(jié)構(gòu)法 匹配形狀數(shù) (2) 基本概念-b b.兩個區(qū)域邊界A和

22、B形狀數(shù)的距離D(A,B) 相似級別的倒數(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)第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:結(jié)構(gòu)法 匹配形狀數(shù) (3) 算法思想 a. 用不同密度的網(wǎng)格劃分邊界區(qū)域，獲得不同序數(shù)的形狀數(shù)。 b. 如果使用相似級別k，k越大說明越相似。 c. 如果使用相似距離D，D越小說明越相似 d. 可以利用相似樹來進(jìn)行判別第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4

23、識別與解釋:結(jié)構(gòu)法 匹配形狀數(shù) （4舉例 假設(shè)我們有一個形狀F，想在另5個形狀A(yù)，B，C，D，E中找到與其最相似的形狀A(yù)BCDEF第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:結(jié)構(gòu)法 這個問題類似于有五個原型形狀，想找出這個問題類似于有五個原型形狀，想找出一個給定的尚不確定的形狀的最佳匹配的問題。這一個給定的尚不確定的形狀的最佳匹配的問題。這個問題可以利用相似樹和矩陣來可視化個問題可以利用相似樹和矩陣來可視化468101214ABCDEFABCDEFBCDEFAAAABECFBEDDDCFCF BEA B C D E FABEDCF 6 6

24、6 6 6 8 8 10 8 8 8 12 8 8 8 第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:結(jié)構(gòu)法 串匹配 （1串匹配的基本思想 比較兩個邊界的串編碼的相似程度，來進(jìn)行匹配 （2三個基本概念設(shè): 兩個區(qū)域邊界A和B已分別被編碼 為串a(chǎn)1a2an和b1b2bm。第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:結(jié)構(gòu)法 串匹配 a.兩個串的匹配數(shù)M: 當(dāng) ak= bk 時我們說發(fā)生了一個匹配。令M代表A、B中匹配的總數(shù)。 b.不匹配的符號數(shù)量Q：Q = max（|A|，|B|）- M 這里|arg|是字符串的長度。當(dāng)且僅當(dāng)A和B完全相同時，Q = 0。第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:結(jié)構(gòu)法 串匹配 c. A和B相似度的簡便衡量R: R = M/Q = M / max(|A|,|B|) - M 因此，當(dāng)A和B完全匹配時，R = ； 當(dāng)A和B中任何字符都不匹配時， M = 0，R = 0。第三章第三章 數(shù)字圖像分析數(shù)字圖像分析 第四節(jié)第四節(jié) 識別與解釋識別與解釋3.4.4 識別與解釋:結(jié)構(gòu)法 串匹配 （