第八章圖像識別

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

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

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

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

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

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

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

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

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

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

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

12、于最小錯誤率的貝葉斯決策因為模式屬于哪一模式類存在不確定性,所以需要用概率來決策, 就是說對于待識模式X,如果它屬于哪個類的概率大則它就屬于哪一類。但如果直接使用各模式類的先驗概率P(ci), 則會因先驗概率所提供的信息量太少而導致把所有模式都歸入先驗概率最大的模式類的無效分類。因此, 應該考慮后驗概率P(ci|X), 但通常概率P(ci|X)不易直接求得的。幸好, 概率論中的貝葉斯公式可以幫忙, 事實上, 由貝葉斯公式 cjjjiiicPcXpcPcXpXcP1)()|()()|()|(圖解p(x|1)p(x|2)p(1|x)p(2|x)類條件概率密度函數(shù)后驗概率最小錯誤率決策34模式識別過

13、程示例：Fish Classification預處理：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先驗知識: 鱸魚一般比鮭魚長l通過長度L是否超過了臨界值L*來判斷種類l為了確定恰當?shù)腖*值，必須先獲得不同類別的魚的若干樣本(“設計樣本”或”訓練樣本”)進行長度測量。3637l驗證了平均意義上鱸魚要比鮭魚長的結(jié)論l令人失望的表明: 單一的特征判據(jù)是不足以完美分類的。l繼續(xù)嘗試別的特征，如: 魚的平均光澤度。38392021-7-9l總體代價函數(shù): 決策理論的中心任務是要確定一種決策,使該代價函數(shù)最小。l單一特征的分類效果不能令人滿意，應考慮組合運用多種特征的方法。l特征組合: 光澤度x1和寬度x2,簡化為一個二維的特征向量，或二維空間的一個點x1,x240412021-7-9出