第八章圖像識(shí)別

1、1第八章 圖像識(shí)別 信息與通信工程學(xué)院 張洪剛2模式識(shí)別和模式的概念感知：從環(huán)境獲取信息感知：從環(huán)境獲取信息3計(jì)算機(jī)模式識(shí)別u模式識(shí)別：使計(jì)算機(jī)模仿人的感知能力，從感知數(shù)據(jù)中提取信息（判別物體和行為）的過程。數(shù)據(jù)獲取模式分割模式識(shí)別姚明姚明ROCKETS11概念4模式識(shí)別的意義數(shù)字化感知數(shù)據(jù)：來源豐富、數(shù)量巨大概念5模式識(shí)別的難點(diǎn)感知數(shù)據(jù)：非結(jié)構(gòu)化（像素、聲波等）概念6模式與模式類u樣本樣本(sample, object)：一類事物的一個(gè)具體體現(xiàn)，對(duì)具體的個(gè)別事物進(jìn)行觀測(cè)所得到的某種形式的信號(hào)。u模式模式(pattern)：表示一類事物，如印刷體A與手寫體A屬同一模式。B與A則屬于不同模式。u

2、樣本是具體的事物，而模式是對(duì)同一類事物概念性的概括。u模式類與模式聯(lián)合使用時(shí)，模式表示具體的事物，而模式類則是對(duì)這一類事物的概念性描述。u模式識(shí)別是從樣本到類別的映射。概念模式確定性和隨機(jī)性以人臉為例l確定性結(jié)構(gòu)關(guān)系：眼睛、鼻子、嘴器官形狀：眼睛形狀、鼻子形狀、嘴形狀膚色：色調(diào)l隨機(jī)性結(jié)構(gòu)關(guān)系：距離、角度器官形狀：大小、形狀參數(shù)不同膚色：不同膚色，不同飽和度和光潔度7定義：模式類l模式(x) : 具有某些量化測(cè)量值或者特征l模式類 (vi)：A collection of “similar” (not necessarily identical) objectsInter-class vari

3、abilityIntra-class variabilityl模式類的統(tǒng)計(jì)特性相似性-先驗(yàn)概率 ：P (vi)類條件概率密度：p (x|vi)8The letter “T” in different typefacesCharacters that look similar9模式識(shí)別的基本問題模式識(shí)別的基本問題（1）特征如何提??？-特征產(chǎn)生特征產(chǎn)生（2）最有效的特征是那些特征？-特征選擇特征選擇（3）對(duì)特定任務(wù)，如何設(shè)計(jì)分類器？ -分類器設(shè)計(jì)分類器設(shè)計(jì)（4）分類器設(shè)計(jì)后，如何評(píng)價(jià)分類器？分類錯(cuò)誤率是多少？ -分類器評(píng)價(jià)分類器評(píng)價(jià)10模式識(shí)別方法的分類模式識(shí)別方法的分類（1）監(jiān)督與非監(jiān)督模式識(shí)別

4、 A、監(jiān)督模式識(shí)別 利用先驗(yàn)知識(shí)和訓(xùn)練樣本來設(shè)計(jì)分類器。 B、非監(jiān)督模式識(shí)別 利用特征向量的相似性來自動(dòng)進(jìn)行分類。11l有監(jiān)督學(xué)習(xí)（supervised learning)：用已知類別的樣本訓(xùn)練分類器，以求對(duì)訓(xùn)練集數(shù)據(jù)達(dá)到某種最優(yōu)，并能推廣到對(duì)新數(shù)據(jù)的分類。l非監(jiān)督學(xué)習(xí)（unsupervised learning) ：樣本數(shù)據(jù)類別未知，需要根據(jù)樣本間的相似性對(duì)樣本集進(jìn)行分類(聚類，clustering)12模式分類 vs. 模式聚類Classification (known categories) Clustering (creation of new categories)Category

5、“A”Category “B”Classification (Recognition) (Supervised Classification) Clustering(Unsupervised Classification)模式識(shí)別方法13參數(shù)估計(jì)近鄰法直接計(jì)算判別函數(shù)非參數(shù)方法有監(jiān)督學(xué)習(xí)最小距離分層聚類無監(jiān)督學(xué)習(xí)靜態(tài)模式（不相關(guān)）HMM時(shí)序模式（相關(guān)的靜態(tài)模式）統(tǒng)計(jì)模式識(shí)別模板匹配結(jié)構(gòu)模式識(shí)別人工神經(jīng)網(wǎng)絡(luò)句法模式識(shí)別統(tǒng)計(jì)學(xué)習(xí)理論和支持向量機(jī)模糊模式識(shí)別14模板匹配Template MatchingTemplateInput scene15結(jié)構(gòu)模式識(shí)別l用簡(jiǎn)單的基元(primitives)和結(jié)構(gòu)

6、關(guān)系來描述復(fù)雜對(duì)象YNMLTXZSceneObjectBackgroundDELTXYZMNDE16句法模式識(shí)別l定義：描述待處理模式的結(jié)構(gòu)信息，并用形式語言中的文法定義模式結(jié)構(gòu)，并通過句法分析進(jìn)行分類對(duì)象被描述為以基元為基本單位（符號(hào)化）的文法源自語言學(xué)，但不限于語言學(xué)應(yīng)用l基本概念基元：預(yù)定義的不再包含細(xì)節(jié)結(jié)構(gòu)信息的子結(jié)構(gòu)文法：對(duì)模式的描述（基元為字符）字符串句法：對(duì)字符串進(jìn)行判別，是否文法描述的“語言”17句法模式識(shí)別系統(tǒng)框架預(yù)處理基元分割或分解句法分析基元和關(guān)系選擇文法結(jié)構(gòu)及推理測(cè)試模式訓(xùn)練模式分類學(xué)習(xí)過程錯(cuò)誤率檢測(cè)基元及關(guān)系識(shí)別18人工神經(jīng)網(wǎng)絡(luò)l計(jì)算“仿生”智能計(jì)算機(jī) 大規(guī)模并行分布

7、式的計(jì)算學(xué)習(xí)，泛化和自適應(yīng)容錯(cuò)，非確定，不精確的分類19模糊模式識(shí)別l1965年Zadeh提出模糊集理論是對(duì)傳統(tǒng)集合理論的一種推廣l傳統(tǒng)：屬于或者不屬于l模糊：以一定的程度屬于模糊邏輯：相對(duì)傳統(tǒng)二值邏輯“是或不是”模糊數(shù)學(xué)：研究模糊集和模糊邏輯模糊系統(tǒng)：應(yīng)用角度20模糊模式識(shí)別方法l隸屬度函數(shù)對(duì)象x屬于集合A的程度的函數(shù)，值域0, 1l模糊模式識(shí)別方法將模糊技術(shù)引入傳統(tǒng)模式識(shí)別方法中l(wèi)模糊特征l模糊分類：模糊子集代替確定子集l模糊評(píng)價(jià)21統(tǒng)計(jì)模式識(shí)別l模式識(shí)別最初從統(tǒng)計(jì)理論發(fā)展而來l基本思想：模式被描述為一組測(cè)量值組成的隨機(jī)特征向量，用概率統(tǒng)計(jì)理論對(duì)其進(jìn)行建模，用統(tǒng)計(jì)決策理論劃分特征空間來進(jìn)行

8、分類。22統(tǒng)計(jì)模式識(shí)別的一般過程預(yù)處理特征提取/選擇分類預(yù)處理特征提取/選擇學(xué)習(xí)分類規(guī)則測(cè)試模式訓(xùn)練模式分類訓(xùn)練錯(cuò)誤率檢測(cè)23統(tǒng)計(jì)模式識(shí)別基本過程l基本系統(tǒng)組成數(shù)據(jù)獲?。簻y(cè)量預(yù)處理：利于特征提取和分類特征提取與選擇l降維l選擇有利于分類的特征，去除不利分類的特征分類決策l錯(cuò)誤率最小l損失最小24統(tǒng)計(jì)模式識(shí)別統(tǒng)計(jì)模式識(shí)別 距離分類法距離分類法 1. 標(biāo)準(zhǔn)模式法標(biāo)準(zhǔn)模式法設(shè)由訓(xùn)練樣例可獲得c個(gè)模式類1, 2, c，且可獲得各個(gè)模式類的標(biāo)準(zhǔn)模式M1, M2, MC。那么，對(duì)于待識(shí)模式X，可通過計(jì)算其與各標(biāo)準(zhǔn)模式的距離d(X, Mi) (i=1,2,c)來決定它的歸屬。具體分類規(guī)則為： d(X, Mj

9、)=min d(X, Mi) Xj i=1,2,c 即與X距離最小的標(biāo)準(zhǔn)模式所屬的模式類即為X的所屬模式類。25m1m2xg(x)=0m1m2x262. 平均距離法平均距離法平均距離法就是將待識(shí)模式X與模式類i (i=1,2,c) 中所有樣例模式的距離平均值作為與X的距離，然后以距離最小的模式類作為X的類屬。分類規(guī)則可描述為： ),(),(ijXdXdjXji其中, ksllkkYXdsXd1),(1),(k=1, 2, , c), sk為模式類k中的樣例模式數(shù)。 273. 3. 最近鄰法最近鄰法最近鄰法是將與待識(shí)模式X距離最近的一個(gè)樣例模式的模式類作為X的類屬。分類規(guī)則可描述為 ),(),(

10、ijXdXdjXji其中,sk為模式類k中的樣例模式數(shù)。 ),(min),(, 2 , 1lslkYXdXdk2829幾何分類法幾何分類法一個(gè)模式類就是相應(yīng)特征空間中的一個(gè)點(diǎn)集。一般來講，在特征空間中一個(gè)模式類的點(diǎn)集總是在某種程度上與另一個(gè)模式類的點(diǎn)集相分離。因此，模式識(shí)別的另一個(gè)思路就是設(shè)法構(gòu)造一些分界面（線），把特征空間Rn分割成若干個(gè)稱為決策區(qū)域的子空間Ri (i=1,2,n)，使得一個(gè)模式類剛好位于一個(gè)決策區(qū)域。這樣，對(duì)于待識(shí)模式X，就可以利用空間中的這些分界面來判定X的類屬。分界面（線）方程gi(X)=0中的函數(shù)gi(X)稱為判別函數(shù)。顯然，構(gòu)造分界面的關(guān)鍵就是構(gòu)造其判別函數(shù)。 分界

11、面（線）可分為平面（直線）和曲面，相應(yīng)的判別函數(shù)為線性函數(shù)和非線性函數(shù)。30對(duì)于二分類問題, 顯然只需一個(gè)分界平面。設(shè)判別函數(shù)為 g(X)=WTX+w0 其中W= (w1, w2, wn)T為X中各分量x1, x2, xn的系數(shù)組成的向量，稱為權(quán)向量；w0為一個(gè)常數(shù)，稱為閾值權(quán)。那么，分界平面方程為 g(X) = WTX+w0= 0 由幾何知識(shí)知,位于這個(gè)分界平面兩邊的點(diǎn)X的判別函數(shù)值g(X)符號(hào)相反。于是, 可有分類規(guī)則: g(X)0 X1 g(X)0 X2 g(X)=0 X屬于X1或X2 ，或者不可判別 31二分類問題的分界面(線)示意 32概率分類法概率分類法基于最小錯(cuò)誤率的貝葉斯決策基

12、于最小錯(cuò)誤率的貝葉斯決策因?yàn)槟Ｊ綄儆谀囊荒Ｊ筋惔嬖诓淮_定性,所以需要用概率來決策, 就是說對(duì)于待識(shí)模式X,如果它屬于哪個(gè)類的概率大則它就屬于哪一類。但如果直接使用各模式類的先驗(yàn)概率P(ci), 則會(huì)因先驗(yàn)概率所提供的信息量太少而導(dǎo)致把所有模式都?xì)w入先驗(yàn)概率最大的模式類的無效分類。因此, 應(yīng)該考慮后驗(yàn)概率P(ci|X), 但通常概率P(ci|X)不易直接求得的。幸好, 概率論中的貝葉斯公式可以幫忙, 事實(shí)上, 由貝葉斯公式 cjjjiiicPcXpcPcXpXcP1)()|()()|()|(圖解p(x|1)p(x|2)p(1|x)p(2|x)類條件概率密度函數(shù)后驗(yàn)概率最小錯(cuò)誤率決策34模式識(shí)別過

13、程示例：Fish Classification預(yù)處理：image enhancement, separating touching/occluding fishes and finding the boundary of the fishExample from: R. Duda, P. Hart, D. Stork, “Pattern Classification”, second edition, 2000.35l先驗(yàn)知識(shí): 鱸魚一般比鮭魚長(zhǎng)l通過長(zhǎng)度L是否超過了臨界值L*來判斷種類l為了確定恰當(dāng)?shù)腖*值，必須先獲得不同類別的魚的若干樣本(“設(shè)計(jì)樣本”或”訓(xùn)練樣本”)進(jìn)行長(zhǎng)度測(cè)量。3637l驗(yàn)證了平均意義上鱸魚要比鮭魚長(zhǎng)的結(jié)論l令人失望的表明: 單一的特征判據(jù)是不足以完美分類的。l繼續(xù)嘗試別的特征，如: 魚的平均光澤度。38392021-7-9l總體代價(jià)函數(shù): 決策理論的中心任務(wù)是要確定一種決策,使該代價(jià)函數(shù)最小。l單一特征的分類效果不能令人滿意，應(yīng)考慮組合運(yùn)用多種特征的方法。l特征組合: 光澤度x1和寬度x2,簡(jiǎn)化為一個(gè)二維的特征向量，或二維空間的一個(gè)點(diǎn)x1,x240412021-7-9出