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

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