第10章 模板匹配與模式識(shí)別

第10章模板匹配和模式識(shí)別技術(shù)1基本概念：模式模式識(shí)別模式：存在于時(shí)間和空間中可觀察的物體相同或相似性；它指的不是事物本身，而是從事物獲得的信息，因此表現(xiàn)為具有時(shí)間和空間分布的信息。模式的直觀特性:

可觀察性可區(qū)分性相似性模式識(shí)別是人和動(dòng)物的一種特性：周?chē)矬w的認(rèn)知：桌子、椅子人的識(shí)別：張三、李四聲音的辨別：汽車(chē)、火車(chē)，狗叫、人語(yǔ)氣味的分辨：炸帶魚(yú)、紅燒肉模式識(shí)別:又稱(chēng)作模式分類(lèi)，就是確認(rèn)一個(gè)事物是什么，或者不是什么，其本質(zhì)是事物的分類(lèi)。從處理問(wèn)題的性質(zhì)和解決問(wèn)題的方法等角度，模式識(shí)別分為有監(jiān)督的分類(lèi)和非監(jiān)督的分類(lèi)兩種。模式識(shí)別的研究目的：利用計(jì)算機(jī)對(duì)物理對(duì)象進(jìn)行分類(lèi)，在錯(cuò)誤概率最小的條件下，使識(shí)別的結(jié)果盡量與客觀物體相符合。如下所表示：Y=F(X)X的定義域取自特征集Y的值域?yàn)轭?lèi)別的標(biāo)號(hào)集F是模式識(shí)別的判別方法模式識(shí)別簡(jiǎn)史1929年G.Tauschek發(fā)明閱讀機(jī),能夠閱讀0-9的數(shù)字。30年代Fisher提出統(tǒng)計(jì)分類(lèi)理論,奠定了統(tǒng)計(jì)模式識(shí)別的基礎(chǔ)。50年代傅京蓀提出句法結(jié)構(gòu)模式識(shí)別。60年代L.A.Zadeh提出了模糊集理論，模糊模式識(shí)別方法得以發(fā)展和應(yīng)用。80年代以Hopfield網(wǎng)、BP網(wǎng)為代表的神經(jīng)網(wǎng)絡(luò)模型導(dǎo)致人工神經(jīng)元網(wǎng)絡(luò)復(fù)活，并在模式識(shí)別得到較廣泛的應(yīng)用。90年代小樣本學(xué)習(xí)理論，支持向量機(jī)也受到了很大的重視。模式識(shí)別系統(tǒng)的目標(biāo)：在特征空間和解釋空間之間找到一種映射關(guān)系，這種映射也稱(chēng)之為假說(shuō)。特征空間：從模式得到的對(duì)分類(lèi)有用的度量、屬性或基元構(gòu)成的空間。解釋空間：模式識(shí)別的依據(jù)是相似性可以識(shí)別從未見(jiàn)過(guò)的事物；可以識(shí)別變形的事物；根據(jù)事物的特征來(lái)識(shí)別它識(shí)別時(shí)抓住分類(lèi)的主要特征，而忽略其他細(xì)節(jié)差異（只考慮相似不考慮相同）模式識(shí)別的基本過(guò)程：學(xué)習(xí)、分類(lèi)（1）學(xué)習(xí)過(guò)程讀取樣本特征建立分類(lèi)規(guī)則進(jìn)行分類(lèi)檢驗(yàn)（2）分類(lèi)過(guò)程讀取事物信息選取特征按規(guī)則分類(lèi)對(duì)分類(lèi)結(jié)果進(jìn)行評(píng)估模式識(shí)別的方法（1）模版匹配（2）統(tǒng)計(jì)方法（3）結(jié)構(gòu)方法（句法方法）（4）模糊模式識(shí)別（5）神經(jīng)網(wǎng)絡(luò)2模板匹配模板匹配：當(dāng)對(duì)象圖案以圖象的形式表現(xiàn)時(shí)，根據(jù)該圖案與一幅圖象的各個(gè)部分相似度判斷其是否存在，并求得對(duì)象物在圖象中位置操作。ab模板匹配過(guò)程：建立模板：對(duì)每個(gè)類(lèi)別建立一個(gè)或多個(gè)模版，模板比較：輸入樣本和數(shù)據(jù)庫(kù)中每個(gè)類(lèi)別的模版進(jìn)行比較，判斷是否有相似的對(duì)象模板匹配的用途：幾何變換中檢測(cè)圖象和地圖之間對(duì)應(yīng)點(diǎn)；不同光譜或者不同攝影時(shí)間所得的圖象之間的位置配準(zhǔn)；運(yùn)動(dòng)物體的跟蹤；圖象中對(duì)象物位置的檢測(cè)模板匹配方法圖象f(x,y)模板t(x,y)設(shè)檢測(cè)模板為，令其中心與圖象中一象素重合，檢測(cè)和圖象重合部分的相似度，對(duì)圖象所有的象素都進(jìn)行這樣的操作，根據(jù)相似度為最大或者超過(guò)某一個(gè)閾值來(lái)確定對(duì)象物是否存在。非相似度計(jì)算的是模板與圖象重合部分的非相似度，該值越小，則匹配程度越好。采用形式：非相似度、相似度相似度：計(jì)算的是模板與圖象重合部分的相似度，該值越大，表示匹配程度越好模板匹配算法的改進(jìn)高速模板匹配算法在模板匹配中應(yīng)用的模板大，因此導(dǎo)致計(jì)算量比較大于是Barnea等人提出了序貫相似性檢測(cè)算法-SSDA法計(jì)算圖象f(x,y)在像素(u,v)的非相似度m(u,v)作為匹配的尺度。式中的(u,v)表示的不是模板與圖像重合部分的中心坐標(biāo)，而是重合部分的左上角坐標(biāo)，模板大小為m*n

如果圖像和模板在(u,v)處有和模板一致的圖案時(shí)，則m(u,v)的值很小，相反則較大。特別是模板和圖像重疊部分完全不一致的情況下，和就不斷的增大。當(dāng)差的絕對(duì)值部分和超過(guò)某一個(gè)閾值的時(shí)就認(rèn)為在該位置不存在于模板一致的圖案，從而轉(zhuǎn)移到下一個(gè)位置。還有一種方法：粗檢索和細(xì)檢索兩個(gè)階段。模板一次移動(dòng)若干個(gè)像素，計(jì)算匹配尺度，先求出大致的范圍。然后在大致范圍內(nèi)，在每次移動(dòng)一個(gè)像素，求出匹配尺度，確定對(duì)象所在位置。模板的要求：檢測(cè)對(duì)象大小和方向未知的情況下進(jìn)行模板匹配，需要具備各式各樣大小和方向的模板，從而確定對(duì)象及其未知。對(duì)象形狀復(fù)雜時(shí)，需要把對(duì)象分割成幾個(gè)分圖案，把分圖案作為模板進(jìn)行匹配，然后研究分圖案之間的位置關(guān)系，從而獲得圖像中對(duì)象的位置。模版匹配：優(yōu)點(diǎn)：直接、簡(jiǎn)單（早期非智能化方法）缺點(diǎn)：適應(yīng)性差（可采用形變模版）3統(tǒng)計(jì)模式識(shí)別統(tǒng)計(jì)模式識(shí)別是研究每一個(gè)模式的各種測(cè)量統(tǒng)計(jì)數(shù)據(jù)特性，按照統(tǒng)計(jì)決策理論進(jìn)行分類(lèi)。三部分組成：分類(lèi)；特征處理：由已知類(lèi)別的訓(xùn)練樣本求出判別函數(shù)以及判別規(guī)則，進(jìn)而用來(lái)對(duì)未知類(lèi)別的圖像進(jìn)行分類(lèi)。自適應(yīng)學(xué)習(xí)部分：用訓(xùn)練樣本根據(jù)某些規(guī)則求出一些判別規(guī)則之后，再對(duì)這些訓(xùn)練樣本逐個(gè)進(jìn)行檢測(cè)，觀察是否有誤差特征處理：特征提取和特征選擇首先對(duì)識(shí)別對(duì)象的性質(zhì)進(jìn)行測(cè)量；利用測(cè)量值作為分類(lèi)的特征。特征選擇：選擇有區(qū)分性，可靠性，獨(dú)立性好的特征特征選擇的方法：窮舉法：從m個(gè)測(cè)量值里面選取n個(gè)特征，然后對(duì)每一種選法利用已經(jīng)知道類(lèi)別屬性的樣本進(jìn)行試分類(lèi)，獲得其正確率，分類(lèi)誤差最小的一組特征便是最好的選擇。最大最小類(lèi)對(duì)距離法：基本思想：從K個(gè)類(lèi)別中選取最難分離的一對(duì)類(lèi)別，然后選擇不同的特征子集，計(jì)算這一類(lèi)別的可分性，具有最大可分性的特征子集就是該方法所選擇的最佳特征子集。這種方法不改變?cè)加^測(cè)值的物理意義。特征變換就是將m個(gè)測(cè)量值的集合通過(guò)某種變換，產(chǎn)生n個(gè)特征用于分類(lèi)。分兩種情況：從減少原始特征之間相關(guān)性和濃縮性信息量的角度出發(fā)。另一種方法就是根據(jù)觀測(cè)量所反映的物理現(xiàn)象與待分類(lèi)別之間的關(guān)系的認(rèn)識(shí)，通過(guò)數(shù)學(xué)運(yùn)算產(chǎn)生一組新的特征值，使得待分類(lèi)之間的差異在改組特征值里面更加明顯。統(tǒng)計(jì)分類(lèi)法監(jiān)督分類(lèi)就是根據(jù)預(yù)先已知類(lèi)別名的訓(xùn)練樣本，求出各類(lèi)在特征空間的分布，然后利用它對(duì)未知數(shù)據(jù)進(jìn)行分類(lèi)。g1g2gc判別函數(shù)常用的判別函數(shù)距離判別函數(shù)線性判別函數(shù)該方法一般將m類(lèi)問(wèn)題分解成m-1個(gè)兩類(lèi)識(shí)別的問(wèn)題。先把特征空間分為一類(lèi)和其它類(lèi)。線性判別函數(shù)的系數(shù)通過(guò)樣本試驗(yàn)確定。統(tǒng)計(jì)決策理論最大似然法該方法為理論上為誤差最小的分類(lèi)法如在一維數(shù)特征空間場(chǎng)合，如下圖T把特征空間分成兩個(gè)區(qū)域，產(chǎn)生的誤分類(lèi)概率為：這一誤分類(lèi)概率隨T的位置而發(fā)生變化，在位置上確定T時(shí)，PE最小，特征矢量分布函數(shù)使用最大似然法，需要預(yù)先求出非監(jiān)督分類(lèi)無(wú)法獲得先驗(yàn)知識(shí)的情況下根據(jù)模式之間的相似度進(jìn)行分類(lèi)。將相似性強(qiáng)的模式歸為同一類(lèi)別，該方法又稱(chēng)為聚類(lèi)分析其中k均值聚類(lèi)就是一種非監(jiān)督分類(lèi)的方法。例：統(tǒng)計(jì)模式識(shí)別19名男女同學(xué)進(jìn)行體檢，測(cè)量了身高和體重，但事后發(fā)現(xiàn)其中有4人忘記填寫(xiě)性別，試問(wèn)（在最小錯(cuò)誤的條件下）這4人是男是女？體檢數(shù)值如下：實(shí)例：統(tǒng)計(jì)模式識(shí)別待識(shí)別的模式：性別（男或女）測(cè)量的特征：身高和體重訓(xùn)練樣本：15名已知性別的樣本特征目標(biāo)：希望借助于訓(xùn)練樣本的特征建立判別函數(shù)（即數(shù)學(xué)模型）實(shí)例：統(tǒng)計(jì)模式識(shí)別50100150200607080體重kg身高cm實(shí)例：統(tǒng)計(jì)模式識(shí)別從圖中訓(xùn)練樣本的分布情況，找出男、女兩類(lèi)特征各自的聚類(lèi)特點(diǎn)，從而求取一個(gè)判別函數(shù)（直線或曲線）。只要給出待分類(lèi)的模式特征的數(shù)值，看它在特征平面上落在判別函數(shù)的哪一側(cè)，就可以判別是男還是女了。根據(jù)訓(xùn)練樣本，建立決策邊界；統(tǒng)計(jì)決策理論，根據(jù)每一類(lèi)總體的概率分布決定決策邊界優(yōu)點(diǎn)：理論基礎(chǔ)扎實(shí)，算法適用面廣；缺點(diǎn)：算法復(fù)雜、對(duì)于統(tǒng)計(jì)分類(lèi)不明確的問(wèn)題難求解4結(jié)構(gòu)模式識(shí)別法識(shí)別原理：句法：描述語(yǔ)言規(guī)則的一種法則。許多復(fù)雜的模式可以分解為簡(jiǎn)單的子模式，這些子模式組成所謂“基元”，每個(gè)模式都可以由基元根據(jù)一定的關(guān)系來(lái)組成，基元可以認(rèn)為是語(yǔ)言中的字母，每個(gè)模式都可以認(rèn)為是一個(gè)句子，關(guān)系可以認(rèn)為是語(yǔ)法。模式的相似性由句子的相似性來(lái)決定。句子的層狀結(jié)構(gòu)自然句法規(guī)則用語(yǔ)模式識(shí)別：房子和樹(shù)結(jié)構(gòu)模式識(shí)別以形式語(yǔ)言為基礎(chǔ)，將一個(gè)復(fù)雜的模式分解成一系列子模式，對(duì)子模式繼續(xù)分解，最后分解成最簡(jiǎn)單的子模式（基元），然后借助于一種形式語(yǔ)言對(duì)模式的結(jié)構(gòu)進(jìn)行描述，從而識(shí)別對(duì)象。模式，子模式，基元類(lèi)似于短語(yǔ)，單詞，字母。因此該方法類(lèi)似于語(yǔ)言句法結(jié)構(gòu)分析，因此稱(chēng)句法模式識(shí)別。結(jié)構(gòu)模式識(shí)別系統(tǒng)框圖樹(shù)分類(lèi)法樹(shù)分類(lèi)法：根據(jù)樹(shù)型分層理論，將未知數(shù)據(jù)歸屬于某一類(lèi)的分類(lèi)方法，是一種基于二叉樹(shù)的分類(lèi)方法。優(yōu)點(diǎn)：能夠利用少量特征，使不同特征在不同判定中起不同作用；每次判定比較簡(jiǎn)單缺點(diǎn)：容易從樹(shù)根就產(chǎn)生錯(cuò)誤，并且不能夠平等的使用所有的特征注意：在靠近樹(shù)根部必須選擇穩(wěn)定的，抗噪強(qiáng)的特征實(shí)例：句法模式識(shí)別問(wèn)題：如何利用對(duì)圖像的結(jié)構(gòu)信息描述，識(shí)別如下所示圖片：實(shí)例：句法模式識(shí)別（續(xù)）將整個(gè)場(chǎng)景圖像結(jié)構(gòu)分解成一些比較簡(jiǎn)單的子圖像的組合；子圖像又用一些更為簡(jiǎn)單的基本圖像單元來(lái)表示，直至子圖像達(dá)到了我們認(rèn)為的最簡(jiǎn)單的圖像單元（基元）；所有這些基元按一定的結(jié)構(gòu)關(guān)系來(lái)表示，利用多級(jí)樹(shù)結(jié)構(gòu)對(duì)其進(jìn)行描述(這種描述可以采用形式語(yǔ)言理論).實(shí)例：句法模式識(shí)別（續(xù)）多級(jí)樹(shù)描述結(jié)構(gòu)實(shí)例：句法模式識(shí)別（續(xù)）訓(xùn)練過(guò)程：用已知結(jié)構(gòu)信息的圖像作為訓(xùn)練樣本，先識(shí)別出基元（比如場(chǎng)景圖中的X、Y、Z等簡(jiǎn)單平面）和它們之間的連接關(guān)系（例如長(zhǎng)方體E是由X、Y和Z三個(gè)面拼接而成），并用字母符號(hào)代表之；然后用構(gòu)造句子的文法來(lái)描述生成這幅場(chǎng)景的過(guò)程，由此推斷出生成該場(chǎng)景的一種文法。實(shí)例：句法模式識(shí)別（續(xù)）識(shí)別過(guò)程：先對(duì)未知結(jié)構(gòu)信息的圖像進(jìn)行基元提取及其相互結(jié)構(gòu)關(guān)系的識(shí)別；然后用訓(xùn)練過(guò)程獲得的文法做句法分析；如果能被已知結(jié)構(gòu)信息的文法分析