圖像匹配與識別

1、本章指導(dǎo)：了解圖像匹配與識別技術(shù)(模式識別)的基本概念以及常用圖像匹配與識別方法。第11章 圖像匹配與識別（模式識別） 2022-5-92第第11章章 圖像匹配與識別圖像匹配與識別 11.1 模式與模式識別 11.2 基于匹配的識別技術(shù) 11.3 統(tǒng)計(jì)模式識別 11.4 句法模式識別 11.5 模糊模式識別方法11.6 人工神經(jīng)網(wǎng)絡(luò)識別法 11.7 統(tǒng)計(jì)學(xué)習(xí)理論和支持向量機(jī)識別方法11.8 小結(jié)2022-5-9311.1模式與模式識別 模式的概念u 模式識別(pattern recognition)作為一門學(xué)科有其系統(tǒng)的理論基礎(chǔ)和技術(shù)方法。u 模式識別屬于圖像分析的范疇，它所得到的結(jié)果是一幅有

2、明確意義的數(shù)值或符號構(gòu)成的圖像或圖形文件，而不再是一幅具有隨機(jī)分布性質(zhì)的圖像 。u 模式識別的目的:u對圖像中的物體進(jìn)行分類;u找出圖像中有哪些物體。2022-5-94舉例l 在人們的日常生活和工作中，模式識別是普遍存在和經(jīng)常進(jìn)行的過程。例如，醫(yī)師為一個患者看病，首先要測量這個患者的體溫和血壓，化驗(yàn)血沉，詢問臨床表現(xiàn)然后通過綜合分析，抓住主要病癥，最后醫(yī)師運(yùn)用自己的知識，根據(jù)主要病癥，為這個患者作出正確的診斷。上述醫(yī)師為患者診斷的過程就是模式識別的一個完整過程。l 在模式識別技術(shù)中，經(jīng)常使用的術(shù)語有樣本、模式、特征和類型等。l 醫(yī)院里有許多患者，每個患者都是一個樣本。請醫(yī)生給出診斷的某一個患者

3、，就是來自許多患者中的單一樣本。l 患者的體溫、血壓等測量值，就是這個樣本的諸測量值。樣本諸測量值的綜合，在模式識中被稱為模式。l 具有某種模式的樣本，有時稱為模式樣本。獲得某個樣本諸測量值的過程稱為模式采集?；颊叩闹饕“Y可以稱為樣本的特征。模式樣本諸測量值經(jīng)過綜合分析找出主要病癥這個過程在模式識別技術(shù)中稱為特征提取和特征選擇。醫(yī)帥運(yùn)用自己的知識作出診斷，在模式識別中稱為分類判決。醫(yī)師的知識是判決的準(zhǔn)則，或者稱為判決規(guī)則。判決結(jié)果把患者區(qū)分成某種疾病的患者，這就是把樣本(患者)區(qū)分成相應(yīng)的類型(疾病)。2022-5-95模式u模式就是存在于時間和空間中，可以區(qū)別它們是否相同或相似的可觀察的事

4、物。u模式所指的不是事物本身，而是從事物中獲取的信息。u模式往往表現(xiàn)為具有時間和空間分布的信息。 l模式的直觀特性:l可觀察性l可區(qū)分性l相似性2022-5-96模式識別系統(tǒng) u模式識別技術(shù)起源于人類自身對事物的認(rèn)知分析過程，是依據(jù)一定的量度或觀測基礎(chǔ)把待識別模式劃分到各自的模式類中去的過程。u模式類是指模式所屬的類別或同一類中模式的總體。l 模式識別 直觀，無所不在，“人以類聚，物以群分”l 周圍物體的認(rèn)知：桌子、椅子l 人的識別：張三、李四l 聲音的辨別：汽車、火車，狗叫、人語l 氣味的分辨：炸帶魚、紅燒肉l 人和動物的模式識別能力是極其平常的，但對計(jì)算機(jī)來說卻是非常困難的。u 2022-

5、5-97l 圖像分析技術(shù)分類的三種基本范疇知識庫知識庫分割分割表示與描述表示與描述識別識別與與解釋解釋預(yù)處理預(yù)處理圖像獲取圖像獲取低級處理高級處理中級處理結(jié)果問題圖像分析系統(tǒng)的組成2022-5-98圖像分析技術(shù)l圖像分析技術(shù)分類的三種基本范疇l低級處理：圖像獲取、預(yù)處理，不需要智能l中級處理：圖像分割、表示與描述，需要智能l高級處理：圖像識別、解釋，缺少理論，為降低難度，設(shè)計(jì)得更專用。2022-5-99u模式識別系統(tǒng)的基本構(gòu)成信息獲取或模式采集數(shù)據(jù)預(yù)處理特征提取和選擇分類器設(shè)計(jì)分類決策訓(xùn)練過程輸出結(jié)果模式識別步驟：圖像分割（物體分離）：檢測出各個物體，并把它們的圖像和其余景物分離;特征抽?。簩?/p>

6、物體進(jìn)行度量。通過計(jì)算對物體的一些重要特性進(jìn)行量化表示;分類：確定每個物體應(yīng)該歸屬的類別.2022-5-910 1.信息獲取部分（或模式采集） 為了使計(jì)算機(jī)能夠?qū)Ω鞣N現(xiàn)象進(jìn)行分類識別，首先利用各種輸入設(shè)備將要識別對象的信息輸入計(jì)算機(jī)。 通過測量、采樣和量化，可以用矩陣或者向量來表示待識別對象的信息。這就是信息獲取的過程。 模式識別系統(tǒng) 獲取的信息，如：二維圖像：文字、指紋、地圖、照片等一維波形：腦電圖、心電圖、季節(jié)震動波形等物理參量和邏輯值：體溫、化驗(yàn)數(shù)據(jù)、參量正常與否的描述2022-5-911模式識別系統(tǒng)l2.預(yù)處理部分 l 預(yù)處理的目的就是去除噪聲，加強(qiáng)有用的信息，并對輸入測量儀器或其他因

7、素所造成的退化現(xiàn)象進(jìn)行復(fù)原。 l 對于數(shù)字圖像來說，預(yù)處理就是應(yīng)用前面講到的圖像復(fù)原、增強(qiáng)和變換等技術(shù)對圖像進(jìn)行處理，提高圖像的視覺效果，優(yōu)化各種統(tǒng)計(jì)指標(biāo)，為特征提取提供高質(zhì)量的圖像。2022-5-912 3.特征提取和選擇 由于待識別對象的數(shù)據(jù)量可能是相當(dāng)大的，為了有效的實(shí)現(xiàn)分類識別，就要對原始數(shù)據(jù)進(jìn)行某種變換，得到最能反映分類本質(zhì)的特征。這就是特征提取和選擇的過程。l 特征提取實(shí)現(xiàn)由模式空間向特征空間的轉(zhuǎn)變，成功地壓縮維數(shù)。 模式識別系統(tǒng)測量空間：原始數(shù)據(jù)組成的空間特征空間：分類識別賴以進(jìn)行的空間模式表示：維數(shù)較高的測量空間-維數(shù)較低的特征空間2022-5-913模式識別系統(tǒng)4.決策分類決

8、策分類就是利用特征空間中獲得的信息，對計(jì)算機(jī)進(jìn)行訓(xùn)練，從而制定判別標(biāo)準(zhǔn)，用某種方法把待識別對象歸為某一類別的過程。 基本做法：在樣本訓(xùn)練集基礎(chǔ)上確定某個判決規(guī)則，使得按這種規(guī)則對被識別對象進(jìn)行分類所造成的錯誤識別率最小或引起的損失最小2022-5-914模式識別系統(tǒng)l 5.分類器的訓(xùn)練/學(xué)習(xí)l 為了能使分類器有效地進(jìn)行分類判決，還必須首先對分類器進(jìn)行訓(xùn)練，即分類器首先要進(jìn)行學(xué)習(xí)。l 研究機(jī)器的自動識別，對分類器進(jìn)行訓(xùn)練，使它學(xué)會識別，具有自動識別的能力，就尤為重要。l 一個孩子認(rèn)字尚需一個反復(fù)學(xué)習(xí)過程，何況一部機(jī)器要掌握某種判決規(guī)則，學(xué)習(xí)過程更不可缺少。l 這種過程往往要多次反復(fù)，不斷地糾正錯

9、誤，最后才能使機(jī)器自動診斷的錯誤率不超過給定的要求。l 這種輸人、修正，再輸人、再修正，不斷反復(fù)循環(huán)，直到分類錯誤率不大于給定值為止，才完成一個完整的學(xué)習(xí)過程。l 學(xué)習(xí)又可分為兩種，一叫做預(yù)分類的訓(xùn)練試驗(yàn)，即監(jiān)督訓(xùn)練，和未分類的訓(xùn)練試驗(yàn)，即無監(jiān)督訓(xùn)練。 2022-5-915模式識別實(shí)例l在傳送帶上用光學(xué)傳感器件對魚按品種分類鱸魚(Seabass)品種鮭魚(Salmon)2022-5-916模式識別實(shí)例l 識別過程：l 數(shù)據(jù)獲?。杭茉O(shè)一個攝像機(jī)，采集一些樣本圖像，獲取樣本數(shù)據(jù)。l 預(yù)處理：去噪聲，用一個分割操作把魚和魚之間以及魚和背景之間分開l 特征提取和選擇：對單個魚的信息進(jìn)行特征選擇，從而通

10、過測量某些特征來減少信息量l長度l亮度l寬度l魚翅的數(shù)量和形狀l嘴的位置，等等 l 分類決策：把特征送入決策分類器2022-5-917模式分類器的獲取和評測過程l數(shù)據(jù)采集l特征選取l模型選擇l訓(xùn)練和測試l計(jì)算結(jié)果和復(fù)雜度分析，反饋2022-5-918訓(xùn)練和測試l訓(xùn)練集：是一個已知樣本集，在監(jiān)督學(xué)習(xí)方法中，用它來開發(fā)出模式分類器。l測試集：在設(shè)計(jì)識別和分類系統(tǒng)時沒有用過的獨(dú)立樣本集。l系統(tǒng)評價原則：為了更好地對模式識別系統(tǒng)性能進(jìn)行評價，必須使用一組獨(dú)立于訓(xùn)練集的測試集對系統(tǒng)進(jìn)行測試。2022-5-919模式識別方法的分類 統(tǒng)計(jì)模式識別方法 將提取的特征向量定義在一個特征空間中，不同類別的對象都對

11、應(yīng)于空間中的一點(diǎn)，在分類階段，利用統(tǒng)計(jì)決策原理對特征空間進(jìn)行劃分，從而識別不同特征的對象。 2022-5-920模糊模式識別 模糊識別的理論基礎(chǔ)是模糊數(shù)學(xué)(fuzzy math)。它根據(jù)人辨識事物的思維邏輯，吸取人腦的識別特點(diǎn)，將計(jì)算機(jī)中常用的二值邏輯轉(zhuǎn)向連續(xù)邏輯。模糊識別的結(jié)果是用被識別對象隸屬于某一類別的程度，即隸屬度來表示的。 模式識別方法的分類 2022-5-921人工神經(jīng)網(wǎng)絡(luò)模式識別 人工神經(jīng)網(wǎng)絡(luò)研究源于對生物神經(jīng)系統(tǒng)的研究。它將若干個處理單元(即神經(jīng)元)通過一定的互連模型連結(jié)成一個網(wǎng)絡(luò)，這個網(wǎng)絡(luò)通過一定的機(jī)制(如誤差后向傳播)可以模仿人的神經(jīng)系統(tǒng)的動作過程，以達(dá)到識別分類的目的。模

12、式識別方法的分類 2022-5-922 句法結(jié)構(gòu)模式識別 著眼于對待識別對象的結(jié)構(gòu)特征的描述。將一個識別對象看成是一個語言結(jié)構(gòu)，例如一個句子是由單詞和標(biāo)點(diǎn)符號按照一定的語法規(guī)則生成的，同樣， 一幅圖像是由點(diǎn)、線、面等基本元素按照一定的規(guī)則構(gòu)成的。 模式識別方法的分類 2022-5-923模式識別的應(yīng)用l 模式識別已經(jīng)在天氣預(yù)報(bào)、衛(wèi)星航空圖片解釋、工業(yè)產(chǎn)品檢測、字符識別、語音識別、指紋識別、醫(yī)學(xué)圖像分析等許多方面得到了成功的應(yīng)用。 l 分為以下幾個方面：l 字符識別l如清華的尚書OCR識別軟件；l郵局信函自動分揀機(jī)l 生物特征識別l指紋識別,人像識別等l 遙感應(yīng)用l衛(wèi)星云圖, 地面導(dǎo)彈、飛機(jī)場等

13、設(shè)施的衛(wèi)星圖像識別處理l 醫(yī)學(xué)診斷l(xiāng)CT等圖像的識別處理2022-5-92411.2 基于匹配的識別技術(shù)全局模板匹配l 為了從圖像中確定出是否存在某一目標(biāo)，可把某目標(biāo)從標(biāo)準(zhǔn)圖像中預(yù)先分割出來作為全局描述的模板，然后在另一幅圖像中搜索是否有這種模板目標(biāo)。 l 設(shè)全圖像f(x,y)大小為MN，若目標(biāo)模板是JK大小的w(x,y)，常用相關(guān)度量R(x，y)來表示它們之間的相關(guān)性：式中，m=0,1,2,M-1;n=0,1,2,N-1。2022-5-925全局模板匹配進(jìn)一步，規(guī)格化相關(guān)度： 2022-5-926 上式中設(shè)樣板所框出范圍都是j,k從到J,K計(jì)算，而(m,n)則為f(x,y)的MN小區(qū)中任一點(diǎn)

14、，式中f1 (x,y)是f(x,y)在(m,n)點(diǎn)框出JK大小的f(x,y)區(qū)，當(dāng)m,n改變時，可搜索到一個R(m,n)最大值即為樣板配準(zhǔn)或匹配的位置。 若圖像和目標(biāo)樣板用f和w1向量表示，則相關(guān)計(jì)算為： 式中w1為w(j-m,k-n)形成的向量。 模板匹配與空間濾波非常相似。即，模板匹配表示把w(x,y)當(dāng)作加權(quán)矩陣對f(x,y)進(jìn)行空間濾波。2022-5-927yMxJ(m,n) w(x,y)K在點(diǎn)(m,n)處的全局樣本相關(guān) 例 通過相關(guān)系數(shù)進(jìn)行目標(biāo)匹配l圖a是f(x,y),圖b是w(x,y),圖c是相關(guān)系數(shù)r(x,y).在 f和w之間找到最佳匹配的地方,相關(guān)系數(shù)r(x,y)的值最大(更亮

15、).2022-5-9282022-5-929模板向量匹配u 若用向量描述模板，則相關(guān)匹配可以用求向量差的方法求相關(guān)，如用相似度作為模板與圖像某子區(qū)的匹配量度。u 把圖像被JK框出部分用向量表示，模板也用向量表示，這時兩個向量相似度可用兩個向量的向量差向量差為相似度的一種度量，差值D(m,n) jknkmjwkjfnmD2),(),(),(D(m,n)是被搜索到的圖像場f(j,k)和樣板w差。規(guī)定一個最小向量差的閾值，若 D(m,n)， 則說明在(m,n)位置上匹配，向量僅為JK維。2022-5-930特征匹配 若圖像待識別部分和樣板都用特征向量表示，則向量的維數(shù)大為減少。例如用不變矩描述時，則

16、f(j,k)和w(j,k)特征向量只有7維( 參見，即l x=(x11,x12,x13,x14,x15,x16,x17)l w=(w11,w12,w13,w14,w15,w16,w17) X和W向量差可用差向量的范數(shù)來表示： DJ(x,w)=|x-w|2=(x-w)T(x-w) 若圖像中已分割出個目標(biāo)物，求其中是否有目標(biāo)物，則只需求出個l Dj(x,w)=|w-xj|2 j=1,2,L 選出其中最小的一個j，即為與w相似的圖像。2022-5-93111.3 統(tǒng)計(jì)模式識別u統(tǒng)計(jì)模式識別主要是根據(jù)模式統(tǒng)計(jì)特性，采用一系列自動處理技術(shù)對給定模式進(jìn)行大量統(tǒng)計(jì)分析，抓取反映模式本質(zhì)的特征而進(jìn)行賦值和分類

17、識別處理。 u 統(tǒng)計(jì)識別認(rèn)為圖像可能包含有一個或若干個不同的物體，對于每一個物體都應(yīng)當(dāng)屬于若干事先定義的模式類之一。 2022-5-932 統(tǒng)計(jì)模式識別的過程 統(tǒng)計(jì)模式識別方法最終都要?dú)w結(jié)為分類的問題。如果從某個模式中共抽取N個模式符圖像，可以分為m個模式類，那么就可以對N進(jìn)行分類，進(jìn)而決定出未知圖像屬于這m個模式類中的哪一種。對模式的分類主要建立在統(tǒng)計(jì)決策理論之上的，而決策理論方法又要用到?jīng)Q策函數(shù)。通?？梢园炎R別模式當(dāng)作是對一個n維模式矢量進(jìn)行分類，即： 其中xi為描述模式表達(dá)方式的第i個描述符。 Tnxxxx212022-5-933 上式代表了一個n維模式矢量，對于給定的m個模式類1，2，

18、3，m，識別過程就是要確定此n維模式矢量是否屬于模式類i，以及模式矢量中的每一個x可以劃歸到哪一個i模式類。該問題也可以轉(zhuǎn)化為對決策函數(shù)d1(x),d2(x),dm(x)的確定，如果模式x屬于模式類i，就有 di(x)dj(x),j=1,2,m,i j 從另一個角度考慮：如果將未知模式代入所有的決策函數(shù)，得到第i個決策函數(shù)的計(jì)算結(jié)果最大，那么就可以將這個未知模式劃歸到第i個模式類。 關(guān)鍵問題是找到合適的決策判別函數(shù)。這個過程叫學(xué)習(xí)或訓(xùn)練。 2022-5-934實(shí)例：統(tǒng)計(jì)模式識別l19名男女同學(xué)進(jìn)行體檢，測量了身高和體重，但事后發(fā)現(xiàn)其中有4人忘記填寫性別，試問（在最小錯誤的條件下）這4人是男是女

19、？體檢數(shù)值如下：2022-5-935實(shí)例：統(tǒng)計(jì)模式識別l待識別的模式：性別（男或女）l測量的特征：身高和體重l訓(xùn)練樣本：15名已知性別的樣本特征l目標(biāo)：希望借助于訓(xùn)練樣本的特征建立判別函數(shù)（即數(shù)學(xué)模型）2022-5-936實(shí)例：統(tǒng)計(jì)模式識別l由訓(xùn)練樣本得到的特征空間分布圖2022-5-937實(shí)例：統(tǒng)計(jì)模式識別l從圖中訓(xùn)練樣本的分布情況，找出男、女兩類特征各自的聚類特點(diǎn)，從而求取一個判別函數(shù)（直線或曲線）。l只要給出待分類的模式特征的數(shù)值，看它在特征平面上落在判別函數(shù)的哪一側(cè)，就可以判別是男還是女了。2022-5-93811.4 句法模式識別u 所謂句法，是描述語法規(guī)則的一種法則。u一個完整的句

20、子一定是主語+謂語或主語+謂語+賓語(或表語)的基本結(jié)構(gòu)構(gòu)成。一種特定的語言，一定類型的句子之間是有一定的結(jié)構(gòu)順序的。 u特點(diǎn)：u 無規(guī)則的任意組合，必然達(dá)不到正確的思想交流。u形容詞、副詞、冠詞等可以與名詞、動詞構(gòu)成“短語”，豐富句子要表達(dá)的思想內(nèi)容。u而這些短語的構(gòu)成也是有特定規(guī)律的。 2022-5-939 句子的層狀結(jié)構(gòu) 2022-5-940 自然句法規(guī)則的思想可以移植到圖像的模式識別中。盡管自然界的景物組合是千變?nèi)f化的，但仔細(xì)分析可以看出：某一對象的結(jié)構(gòu)，也存在一些不變的規(guī)則。 一座房子由內(nèi)屋頂和墻面構(gòu)成。組成屋頂?shù)膸缀螆D形，可以是三角形、四邊形、圓形等，組成墻平面的幾何圖形也是由矩形

21、、平行四邊形(透視效果)等構(gòu)成，至少某一個墻面應(yīng)該有門，而窗的高度不低于門等等。進(jìn)一步，還可以提出一些用來刻畫構(gòu)成一所房子的規(guī)則，如屋頂一定在墻面之上，且由墻面支撐。一所房子這些規(guī)則就像構(gòu)成一個句子的句法規(guī)則一樣，是不能改變的。2022-5-941 如果將描述房子的規(guī)則(它構(gòu)成一個房子的模式)存于計(jì)算機(jī)，要在一張風(fēng)景照片上去識別有無房子，那么就可按照片上所有景物的外形匹配是否符合房子的模式(房子構(gòu)成規(guī)則)。符合房子模式的就輸出為“有房子”，否則，輸出“無房子”。 句法模式識別是將一個復(fù)雜的模式分解成一系列更簡單的模式(子模式)，對子模式繼續(xù)分解，最后分解成最簡單的子模式(或稱基元)，借助于一種

22、形式語言對模式的結(jié)構(gòu)進(jìn)行描述，從而識別圖像。 模式、子模式、基元類似于英文句子的短語、單詞、字母，這種識別方法類似語言的句法結(jié)構(gòu)分析。因此稱為句法模式識別。 2022-5-942 句法模式識別系統(tǒng)框圖 2022-5-943實(shí)例：句法模式識別l問題：如何利用對圖像的結(jié)構(gòu)信息描述，識別如下所示圖片：2022-5-944實(shí)例：句法模式識別l將整個場景圖像結(jié)構(gòu)分解成一些比較簡單的子圖像的組合；l子圖像又用一些更為簡單的基本圖像單元來表示，直至子圖像達(dá)到了我們認(rèn)為的最簡單的圖像單元（基元）；l所有這些基元按一定的結(jié)構(gòu)關(guān)系來表示，利用多級樹結(jié)構(gòu)對其進(jìn)行描述（這種描述可以采用形式語言理論）。2022-5-9

23、45實(shí)例：句法模式識別l多級樹描述結(jié)構(gòu)2022-5-946實(shí)例：句法模式識別l訓(xùn)練過程：l用已知結(jié)構(gòu)信息的圖像作為訓(xùn)練樣本，先識別出基元（比如場景圖中的X、Y、Z等簡單平面）和它們之間的連接關(guān)系（例如長方體E是由X、Y和Z三個面拼接而成），并用字母符號代表之；l然后用構(gòu)造句子的文法來描述生成這幅場景的過程，由此推斷出生成該場景的一種文法。2022-5-947實(shí)例：句法模式識別l識別過程：l先對未知結(jié)構(gòu)信息的圖像進(jìn)行基元提取及其相互結(jié)構(gòu)關(guān)系的識別；l然后用訓(xùn)練過程獲得的文法做句法分析；l如果能被已知結(jié)構(gòu)信息的文法分析出來，則該幅未知圖像與訓(xùn)練樣本具有相同的結(jié)構(gòu)（識別成功），否則就不是這種結(jié)構(gòu)（識別失敗）。2022-5-94811.5 模糊模式識別方法u 問題：u “張三是個學(xué)生嗎？”-回答是精確的u “張三性格穩(wěn)重嗎？”-回答無法精確u 常規(guī)