計(jì)算機(jī)視覺教程CCV12

1、第12章景物識別12.1 統(tǒng)計(jì)模式分類12.2 感知機(jī)12.3 支持向量機(jī)12.4 結(jié)構(gòu)模式識別12.1 統(tǒng)計(jì)模式分類12.1.1 模式分類原理12.1.2 最小距離分類器12.1.3 最優(yōu)統(tǒng)計(jì)分類器12.1.1 模式分類原理一個(gè)n維的模式矢量可寫成如果一個(gè)模式x屬于類si，那么有對一個(gè)未知模式x來說，如果將它代入所有決策函數(shù)算得di(x)值最大，則x屬于第i類。如果對x的值，有di(x) = dj(x)，則得到將類i與類j分開的決策邊界12.1.2 最小距離分類器每個(gè)模式類用一個(gè)均值矢量表示計(jì)算并且在dj(x)給出最大值時(shí)將x賦給類sj類si和sj之間的決策邊界12.1.3 最優(yōu)統(tǒng)計(jì)分類器1

2、.最優(yōu)統(tǒng)計(jì)分類原理在平均意義上產(chǎn)生最小可能分類誤差條件平均風(fēng)險(xiǎn)損失貝葉斯分類器12.1.3 最優(yōu)統(tǒng)計(jì)分類器1.最優(yōu)統(tǒng)計(jì)分類原理損失函數(shù)貝葉斯分類器在滿足下面的條件時(shí)將x賦給類si對0-1損失函數(shù)，貝葉斯分類器相當(dāng)于實(shí)現(xiàn)了如下的判決函數(shù)12.1.3 最優(yōu)統(tǒng)計(jì)分類器2.用于高斯模式類的貝葉斯分類器貝葉斯決策函數(shù)對類sj的貝葉斯決策函數(shù)是dj(x) = p(x | sj)P(sj)采用自然對數(shù)形式來表達(dá)決策函數(shù)12.1.3 最優(yōu)統(tǒng)計(jì)分類器例12.1.2模式在3-D空間的分布12.2 感知機(jī)兩個(gè)模式類的感知機(jī)模型12.2 感知機(jī)感知機(jī)的決策邊界系統(tǒng)的輸出12.2 感知機(jī)1.線性可分類由兩個(gè)線性可分訓(xùn)練

3、集獲取權(quán)矢量的迭代算法校正增量c設(shè)為正的如果機(jī)器正確地劃分了模式，給它的獎(jiǎng)勵(lì)就是不改變w；但如果機(jī)器錯(cuò)誤地劃分了模式，給它的懲罰就是改變w。根據(jù)感知機(jī)訓(xùn)練定理12.2 感知機(jī)2.線性不可分類準(zhǔn)則函數(shù)梯度下降算法12.2 感知機(jī)2.線性不可分類如將權(quán)矢量的變化，即德爾塔寫成如下的形式德爾塔（Delta）校正算法當(dāng)模式y(tǒng)(k)出現(xiàn)時(shí)，權(quán)矢量w(k)的誤差為12.3 支持向量機(jī)1.線性可分類設(shè)計(jì)目的就是要獲得一個(gè)超平面其中，w = w1, w2, , wlT為權(quán)向量，w0為閾值12.3 支持向量機(jī)1.線性可分類朝向A為所求，而朝向B給出了一個(gè)其他朝向從一個(gè)點(diǎn)到一個(gè)超平面的距離12.3 支持向量機(jī)1.

4、線性可分類用拉格朗日乘數(shù)法來解最優(yōu)解的向量參數(shù)w是Ns個(gè)（Ns N）與li 0相關(guān)的特征向量的線性組合這些向量就稱為支持向量，而最優(yōu)的超平面分類器就稱為支持向量機(jī)12.3 支持向量機(jī)2.線性不可分類(1)向量落在分類帶之外且被正確地分了類(2)向量落在分類帶之內(nèi)且被正確地分了類(3)向量被錯(cuò)誤地分了類12.3 支持向量機(jī)2.線性不可分類此時(shí)的目標(biāo)是在保持具有ri 0的點(diǎn)數(shù)盡可能小的條件下，使最近點(diǎn)到超平面的距離盡可能小。此時(shí)要最小化的代價(jià)函數(shù)為12.4 結(jié)構(gòu)模式識別12.4.1 字符串結(jié)構(gòu)識別12.4.2 樹結(jié)構(gòu)識別12.4.1 字符串結(jié)構(gòu)識別1.字符串文法文法是一組句法規(guī)則，它們能控制字符集

5、中符號產(chǎn)生句子的過程由一個(gè)文法G所產(chǎn)生的一組句子稱為語言，并記為L(G)。所以句子是符號的串，這些串代表了模 式，而語言對應(yīng)模式類12.4.1 字符串結(jié)構(gòu)識別1.字符串文法例12.4.1字符串結(jié)構(gòu)示例考慮文法G = (N, T, P, S)，其中N = A, B, C，T = a, b, c，P = S aA, A bA, A bB, B c12.4.1 字符串結(jié)構(gòu)識別2.語義應(yīng)用句法確定目標(biāo)結(jié)構(gòu)，語義主要與其正確性有關(guān)12.4.1 字符串結(jié)構(gòu)識別3.用自動(dòng)機(jī)作為字符串識別器如何識別一個(gè)模式是否屬于由文法G產(chǎn)生的語言L(G)。結(jié)構(gòu)識別法的基本概念可借助稱為自動(dòng)機(jī) （計(jì)算機(jī)器）的數(shù)學(xué)模型來解釋有

6、限自動(dòng)機(jī)是由規(guī)則語法產(chǎn)生的語言識別器，可定義為一個(gè)五元組12.4.1 字符串結(jié)構(gòu)識別3.用自動(dòng)機(jī)作為字符串識別器Q = q0, q1, q2，T = a, b，F(xiàn) = q0。映射規(guī)則是d (q0, a) = q2，d (q0, b) = q1，d (q1, a) = q2，d (q1, b) = q0，d (q2, a) = q0，d (q2, b) = q1能識別字符串a(chǎn)bbabb，但不能識別字符串a(chǎn)abab12.4.2 樹結(jié)構(gòu)識別1.樹文法樹文法是由如下五元組所定義擴(kuò)展樹文法X1, X2, , Xn 為非終結(jié)符號，k 是一個(gè)終結(jié)符 號，r(k) = n12.4.2 樹結(jié)構(gòu)識別1.樹文法在這個(gè)樹文法中，N = X1, X2, X3, S，S = a, b, c, d, e，其中終結(jié)符號表示圖12.4.4(b)所示的基元12.4.2 樹結(jié)構(gòu)識別2.樹自動(dòng)機(jī)一個(gè)從樹葉向樹根掃描的樹自動(dòng)機(jī)其中，Q為一組狀態(tài)有限集；F為一組終結(jié)狀態(tài)集，且是Q的一個(gè)子集；fk是Qm Q中的關(guān)系，其中m為k的秩，Qm代表Q的自身m次笛卡爾乘積，即Qm = Q Q Q Q12.4.2 樹結(jié)構(gòu)識別2.樹自動(dòng)機(jī)教程作者（章毓晉）聯(lián)系信息 通信地址：北京清華大學(xué)電子工