第八章 高層理解--目標(biāo)識別

.,ZhangXingming,TheInstituteofComputerScienceandEngineering,Chapter8ObjectRecognition,.,8.1知識表示,描述和特征描述：物體的標(biāo)量特性，稱為特征;特征矢量:幾個描述組合起來;例如,.,2結(jié)構(gòu)描述基元:形成物體的基本單元，由他們的類型信息表示;結(jié)構(gòu)描述:基元和它們之間的關(guān)系生成，通過符號構(gòu)成的鏈、樹和圖來描述;語法:字生成器的數(shù)學(xué)模型;語言:字的集合;,a,a,b,b,c,c,abcabc,.,謂詞邏輯它為從舊知識中通過演繹得到新知識提供了一種數(shù)學(xué)形式;處理對象是邏輯變量和量詞和邏輯運算符。產(chǎn)生式規(guī)則If條件X處理then采取動作Y;,.,模糊邏輯克服數(shù)值和精確知識表示的明顯局限;可以用模糊規(guī)則表示知識:ifXisAthenYisB;6語義網(wǎng)絡(luò)為一個有向圖,她的節(jié)點表示物體，弧表示物體之間的關(guān)系;,.,框架,.,8.2圖象識別系統(tǒng)的基本原理,模式是對某些感興趣客體的定量或結(jié)構(gòu)描述。模式類就是具有某些共同特性的模式的集合。模式識別就是研究一種自動技術(shù)，依靠這種技術(shù)，機器將自動（或盡可能少的人工干預(yù)）把待識模式分配到各自的模式類中去。這就需要把人們的知識和經(jīng)驗教給機器，為機器制定一些規(guī)則和方法，并且讓機器能夠完成自動識別的任務(wù)，這就是模式識別的研究目標(biāo)。,.,.,1、預(yù)處理它主要完成模式的采集、模數(shù)轉(zhuǎn)換、濾波、消除模糊、減少噪聲、糾正幾何失真等預(yù)處理操作。因此也要求相應(yīng)的設(shè)備來實現(xiàn)。,.,2、特征或基元提取特征提取實現(xiàn)由模式空間向特征空間的轉(zhuǎn)換，有效地壓縮維數(shù)。一般地說，它該是在一定分類準(zhǔn)則下的最佳或次最佳變換器。模式識別中，分類器的分類規(guī)則固然重要，但是，如果所基于的模式特征沒有包含足夠的待識客體的信息或未能提取反映客體特征的信息，那么，識別的結(jié)果將面目全非。所以說，在設(shè)計分類器之前，能夠快速、有效地進(jìn)行特征提取是模式識別的關(guān)鍵。不幸的是，直到目前為止還沒有形成特征提取的一般理論，隨著識別任務(wù)的不同，特征提取的方法也不一樣。此外，如果待識別的模式樣本本身攜帶反映不同模式本質(zhì)特性的特征，則特征提取也不一定需要。,.,歸納起來，一般常用的方法主要包括：傅立葉分析(FourierTransformation)；梅林變換(MeilinTransformation)；小波變換(WaveletTransformation)；矢量量化(VectorQuantization)；神經(jīng)網(wǎng)絡(luò)(NeuralNetwork)；高階矩(HigherMoment)；,.,3、分類訓(xùn)練為了能使分類器有效地進(jìn)行分類判決，還必須對分類器進(jìn)行訓(xùn)練（學(xué)習(xí)）。分類器的訓(xùn)練學(xué)習(xí)是模式識別的一個重要概念。由于我們研究機器的自動識別，對分類器進(jìn)行訓(xùn)練，使它學(xué)會識別，具有自動識別的能力，尤為重要。眾所周知，一個孩子認(rèn)字尚需一個反復(fù)學(xué)習(xí)過程，何況一部機器要掌握某種判決規(guī)則，學(xué)習(xí)過程更必不可少。當(dāng)然，對于不同的分類方法，其學(xué)習(xí)規(guī)則也不一樣。,.,4、分類在完成訓(xùn)練的基礎(chǔ)上，分類器根據(jù)已經(jīng)確定的判決規(guī)則，對未知類別屬性的樣本執(zhí)行判決過程，就是說，分類器具有了自動識別的能力。這是模式識別“出成果”的階段，直接以其分類結(jié)果表明本次識別的結(jié)束。顯然，這是舉足輕重的階段，弄得不好，會使前幾階段的工作付諸東流。,.,8.3統(tǒng)計模式識別,在經(jīng)典模式識別中，根據(jù)用來解決模式識別問題的數(shù)學(xué)技巧，可以將它分成兩種一般的方法，統(tǒng)計模式識別和句法模式識別。原則上講，聚類分析屬統(tǒng)計模式識別的范疇，但其無監(jiān)督訓(xùn)練的特點，所以將它單獨列出。在經(jīng)典模式識別中，統(tǒng)計模式識別在模式識別技術(shù)的發(fā)展中一直起著顯著的作用，統(tǒng)計決策論和有關(guān)領(lǐng)域已成為一個固定的領(lǐng)域，其中實質(zhì)性的理論進(jìn)展和創(chuàng)造不斷發(fā)生，這些發(fā)展強有力地沖擊于模式識別的應(yīng)用。按確定論和隨機論來分，可分為幾何分類法和概率分類法。,.,1、幾何分類法1)模板匹配法它是模式識別中的一個最原始、最基本的方法，它將待識模式分別與各標(biāo)準(zhǔn)模板進(jìn)行匹配，若某一模板與待識模式的絕大多數(shù)單元均相匹配，則稱該模板與待識模式“匹配得好”，反之則稱“匹配得不好”，并取匹配最好的作為識別結(jié)果。,.,2）距離分類法距離是一種重要的相似性度量，通常認(rèn)為空間中兩點距離越近，表示實際上兩樣本越相似。大約有十余種作為相似性度量的距離函數(shù)，其中使用最廣泛的是歐氏距離。它是使用最為廣泛的方法，常用的有平均樣本法、平均距離法、最近鄰法和近鄰法。,.,最近鄰分離器,.,K近鄰分離器,.,3）線性判別函數(shù)和上述的方法不同，判決函數(shù)法是以判決邊界的函數(shù)形式的假定為其特性的，而上述的方法都是以所考慮的分布的假定為其特性的。假如我們有理由相信一個線性判決邊界取成：是合適的話，那么剩下的問題就是要確定它的權(quán)系數(shù)。權(quán)系數(shù)可通過感知器算法或最小平方誤差算法來實現(xiàn)。但作為一條規(guī)則，應(yīng)用此方法必須注意兩點；第一就是方法的可適性問題，第二就是應(yīng)用判決函數(shù)后的誤差準(zhǔn)則。,.,4）非線性判別函數(shù)線性判決函數(shù)的特點是簡單易行，實際應(yīng)用中許多問題往往是非線性的，一種處理的辦法將非線性函數(shù)轉(zhuǎn)換為線性判決函數(shù)，所以又稱為廣義線性判決函數(shù)。另一種方法借助電場的概念，引入非線性的勢函數(shù)，它經(jīng)過訓(xùn)練后即可用來解決模式的分類問題。,.,2概率分類法,幾何分類法是以模式類幾何可分為前提條件的，在某些分類問題中這種條件能得到滿足，但這種條件并不經(jīng)常能得到滿足，模式的分布常常不是幾何可分的，即在同一區(qū)域中可能出現(xiàn)不同的模式，這時，必須借助概率統(tǒng)計這一數(shù)學(xué)工具。可以說，概率分類法的基石是貝葉斯決策理論。,.,設(shè)有R類樣本，分別為w1,w2,wR,若每類的先驗概率為P(wii),i=1,2,3,R,對于一隨機矢量，每類的條件概率為（又稱類概率密度）P(X/Wii)，則根據(jù)Bayes公式，后驗概率為：從后驗概率出發(fā)，有Bayes法則：,.,以貝葉斯法則為基礎(chǔ)，在考慮錯誤判決和判決風(fēng)險的情況下，就可以得到最小錯誤率判決、最小風(fēng)險判決和最大似然判決等規(guī)則。當(dāng)然，如果先驗概率和損失函數(shù)沒有提供，或沒有全部被提供，上述最基本的貝葉斯分類方法就發(fā)生了困難。為此，可應(yīng)用聶曼皮爾遜判決規(guī)則和最小最大判決規(guī)則。上述方法都可統(tǒng)稱為貝葉斯分類器。分類器訓(xùn)練的主要任務(wù)是完全確定類概率密度函數(shù)。如果訓(xùn)練樣本的類別屬性是已知的，則稱為有監(jiān)督訓(xùn)練，否則稱為無監(jiān)督訓(xùn)練。對于有監(jiān)督訓(xùn)練的情況，當(dāng)已知類概率密度的函數(shù)形式時，就要選用參數(shù)估計方法，否則就要選用非參數(shù)估計的方法。常用的參數(shù)估計方法有最大似然估計、貝葉斯估計和貝葉斯學(xué)習(xí)。非參數(shù)估計的任務(wù)就是利用已知的訓(xùn)練樣本集來估計概率分布密度，常用的方法有Parzen窗法、Kn近鄰法和正交級數(shù)展開逼近法。對于無監(jiān)督訓(xùn)練，也有相應(yīng)的參數(shù)估計方法，此處就不詳述。,.,（1）分類器學(xué)習(xí)定義:從樣本集合中設(shè)置分類器參數(shù)的方法;訓(xùn)練集:模式和帶有類別信息的集合;分類器設(shè)置應(yīng)該是最優(yōu)或次優(yōu)的，能夠識別那些它沒有“見過”的對象；訓(xùn)練集的大小一般逐步增加幾次，直到可以取得正確的分類器設(shè)置。,.,（2）基本性質(zhì)學(xué)習(xí):系統(tǒng)優(yōu)化的過程；學(xué)習(xí)目標(biāo)：使優(yōu)化準(zhǔn)則最?。挥?xùn)練集合有限，學(xué)習(xí)過程應(yīng)該具有歸納的特點；學(xué)習(xí)無法一步完成，是一個循序漸進(jìn)的過程物體描述實際上是在允許分類錯誤率、分類時間和分類器構(gòu)造復(fù)雜度之間的折中。,.,（3）分類器學(xué)習(xí),兩個常用方法：概率密度估計和直接損失最小化概率密度估計若概率密度的形式未知，則必須估計概率密度，若已知，則必須估計參數(shù)。,.,(a)已知，未知(b)未知，已知,.,(c)和均未知,.,算法學(xué)習(xí):計算平均向量和協(xié)方差;計算概率密度;計算先驗概率;分類:,.,3聚類分析,硬C均值聚類算法HCM：設(shè)為一模式集，C為聚類的類別數(shù)（2c0,thestateisacceptedwithprobability:,.,3algorithm:Letxbeavectorofoptimizationparameters;computethevalueoftheobjectiveunctionJ(x);Repeatstep3and4ntimes;Perturbtheparametervectorxslightly,creatingthevectorxnew,andcomputethenewJ(x);Generatearandomnumberr(0,1),fromaunifo