模式識別的理論與方法

1、第十章模式識別的理論與方法n 第十章模式識別的理論與方法Ø 模式識別概述Ø 基本概念模式與模式類Ø 統(tǒng)計模式識別決策論法Ø 句法模式識別結(jié)構(gòu)法Ø 模式識別的應用實例2第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心模式識別概述n 圖像模式識別概述Ø 圖像分析的重要目的ü 圖像分割得到目標ü 紋理分析得到表示紋理的特征ü 圖形描述得到特定目標圖像的抽象化描述ü 圖像的模式識別進一步明確目標的性質(zhì)與特征Ø 圖像識別（模式識別）：對待研究的對象，根據(jù)其某些特征，進行識別并分類Ø

2、; 文字識別是迄今為止人類最熟悉、應用最識別領域的圖像Ø 目前在鑒別、手語識別、面容識別、表情識別等方面正在取得進展Ø 進一步的發(fā)展結(jié)合人工智能，向更高級的識別水平發(fā)展3第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心模式識別概述4第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心模式識別系統(tǒng)模式識別概述n 模式識別流程結(jié)果5第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心特征提取預處理數(shù)據(jù)獲取模式識別概述n 圖像模式識別的現(xiàn)狀Ø 模式識別（pattern cogniton，亦可譯為模式辨認、圖像識別、圖形識別、型式識別）是近30年來得到迅速發(fā)展的

3、一門新興邊緣學科。關于什么是模式或者所能辨認的模式，迄今還沒有一個確切而嚴格的定義。(KanalL.)曾經(jīng)說過這樣一段話：ü “關于什么是模式識別和所能辨認的模式，至 今還沒有人能象香農(nóng)(Shannon)對信息一詞做出定義那祥，給出一個確切的定義。如果一旦出現(xiàn)了這樣一個定義并被證實能夠推動理論的發(fā)展，標志著人類智力的一大進展。雖然如此，目前的局面并不影響模式識 別在各領域中的廣泛應用?！?#216; 我們可以設計出自動圖像識別系統(tǒng)，但仍然缺乏理論依據(jù)。有待人類視覺認識理論的進一步研究。Ø 我們可以做出在某一應用上超過人的能力的系統(tǒng)，但缺乏擴展性。過分依賴具體應用。6第十章

4、模式識別的理論與方法對地觀測與數(shù)字地球科學中心模式識別概述n 圖像模式識別的基礎理論與方法Ø 決策理論是圖像識別的理論基礎Ø 特征和分類是圖像識別的關鍵Ø 圖像識別的基本方式ü 從待分類的圖像中提取能夠代表或排除某些類別的特征ü 根據(jù)特征將圖像目標分到相應的類別中Ø 分類器的兩個基本過程ü 學習過程：首先分離具有典型性的特征，根據(jù)這些特征對每個類別建立的描述，建立特征相應的特征空間ü 測試過程：根據(jù)輸入樣本和特征空間的劃分，對全體圖像進行分類Ø 圖像的分割與識別實際上是一項非常的工作，很難說清楚為什么圖像

5、應該是這樣而不是那樣7第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心模式識別概述n 圖像模式識別的基本方法Ø 識別的統(tǒng)計分類方法：對待分類圖像進行大量統(tǒng)計分析的基礎上，找出規(guī)律性，抽取反映目標特征的統(tǒng)計進行識別。Ø 識別的句法結(jié)構(gòu)方法：通過對圖像結(jié)構(gòu)的分析，一幅 圖像可模仿語言構(gòu)造，用一些語句來表達。通過符號匹配、語法分析等，實現(xiàn)圖像中目標的識別Ø 宏觀比較：統(tǒng)計識別方法很少利用圖像本身的結(jié)構(gòu)關系；句法結(jié)構(gòu)方法未考慮圖像獲取過程中的噪聲干擾n 現(xiàn)代方法研究Ø 模糊模式識別、神經(jīng)網(wǎng)絡模式識別、8第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心

6、模式識別概述n 統(tǒng)計模式識別方法Ø 基本原理有相似性的樣本在模式空間中互相接近，并形成“n 特征與適用于：”，即“物以類聚”Ø 圖像目標特征提取過程中的不精確性誤差的存在Ø 同一類目標圖像存在多種表述的可能性表述的隨機性Ø 利用統(tǒng)計概念，如何使對已知類別的正確識別，在某種意義下使得錯誤識別的可能性達到最小9第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心模式識別概述n 句法模式識別方法Ø 基本原理基于形式語言的理論與概念，模式按其結(jié)構(gòu)分解為子模式或模式基元，模式基元的連接關系以文法形式進行描述n 特征與適用于：Ø 圖像中存在結(jié)構(gòu)

7、信息，且識別的目的不僅需判別圖像屬于哪一類，還需描寫圖像的形態(tài)時某些識別目標，復雜圖像可視為一些相對較簡單的子圖像組成，而這些子圖像又可由一些更為簡單的子圖像來表示，最終分解為一系列簡單的圖像基元¾10第十章 ¾模圖式識像別基的理元論之與間方法按一對組地成觀測目與數(shù)標字地圖球像科學中心規(guī)基本概念模式與模式類n 基本概念模式與模式類¾模式的定義¾模式類的定義¾模式識別的定義¾常用的模式序列9模式9模式串9模式樹11第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心基本概念模式與模式類n 模式的定義Ø 樣本(sample,

8、object)：一類事物的一個具體體現(xiàn)，對具體的個別事物進行觀測所得到的某種形式的信號或表達Ø 模式(pattern)：表示一類事物，表示對該類事務特征或?qū)傩缘某橄蟮拿枋?；如印刷體A 與手寫體A屬同一模式，B與A則屬于不同模式Ø 樣本是具體的事物，而模式是對同一類事物概念性的概括12第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心基本概念模式與模式類n 模式的定義Ø 模式是圖像中的一個對象或某些感區(qū)域的特征或結(jié)構(gòu)的描述物體抽象特征的描述Ø 模式是由一個或多個描述子來組成Ø 模式是一個描述子的序列（名詞“特征”經(jīng)常被用來代指描述子）

9、6; 模式是一組特征或一組描述子13第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心基本概念模式與模式類n 模式類的定義Ø 模式所屬的類別或同一類中模式的總體稱為模式類，其中個別具體的模式常常稱為樣本Ø 模式類是具有某些公共特征的模式的系列Ø 模式類與模式使用時，模式表示具體的事物，而模式類則是對這一類事物的概念性描述n 模式識別的定義Ø 根據(jù)圖像中對象的特征組成的模式，確定對象是屬于那一個模式類，即為模式識別Ø 模式識別是從樣本到類別的14第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心基本概念模式與模式類n 模式與模式類舉例&#

10、216; 已知汽車的長、寬、高（x1,x2,x3），希望識別出： 大客車、小轎車、卡車（w1,w2,w3）9汽車的長、寬、高（L,W,H）模式大客車：(L,W,H)大；小轎車：(L,W,H)小；卡 車：(L,W,H)卡從而有模式類（w大, w小, w卡）Ø 定義了不同汽車的載重量，希望識別出大客車、小轎車、卡車（w1,w2,w3）9汽車的載重量M模式大客車：M大；小轎車：M??；卡車：M卡從而有模式類（w大, w小, w卡）第十章 模式識別的理論與方法15對地觀測與數(shù)字地球科學中心基本概念模式與模式類n 常用的模式序列模式Ø 模式、模式串、模式樹用粗體的小寫字母表示，如x,y

11、形式如下：x1 x29模式.xnx =其中每一個x 代表第i個描述子，n是這種描述子的數(shù)量。模式被表示為一列或表示成x = (x1, x2, , xn)T16第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心基本概念模式與模式類Ø 模式舉例假設我們想描述三種蝴蝶花（多毛的、多色的）通過測量它們花瓣的寬度和長度。這里涉及一個兩維的模式：x1 x2x =其中x1、x2分別對應花瓣的長和寬三種模式類用w1、w2、w3表示17第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心基本概念模式與模式類由于所有的花瓣在寬和長上都有某種程度的變化，所以描述這些花瓣的模式也將有變化，不僅在不同的

12、類之間，而且也在類的內(nèi)部在這種情況下每一種花變成二維空間的一個點18第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心基本概念模式與模式類x2 花瓣寬3.02.52.01.51.00.5多毛的多色的x1 花瓣長123456719第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心基本概念模式與模式類Ø 對結(jié)果的分析對花瓣長寬的測量， 它兩種分離，但對于分離的。地將多毛的蝴蝶花與其和多色的是失敗這個結(jié)論說明了分類的特性選擇問題，在這個問題中，類的可分離性的程度，完全依賴于對模式尺寸測量的選擇20第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心基本概念模式與模式類Ø

13、 模式串以對象特征的結(jié)構(gòu)或空間關系作為模式時，形成模式串Ø 模式串舉例：梯狀的模式a(1) S->aA(2) A->bS(3) A->bbaababb21第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心基本概念模式與模式類¾模式樹以分層目錄結(jié)構(gòu)排序的模式類，一般多采用樹結(jié)構(gòu)¾模式樹舉例圖像城市田園城區(qū)內(nèi)城市郊公路草地森林區(qū) 商業(yè)區(qū)區(qū) 商業(yè)區(qū)22第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 統(tǒng)計模式識別決策論法¾統(tǒng)計模式識別基本概念與過程¾決策論法的基本概念¾最小距離分類器¾相關

14、匹配分析¾¾特征的抽取與選擇23第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 統(tǒng)計模式識別基本概念Ø 假定我們所處理的模式每一個樣本都表示為N維特征矢量N )¢x = (Ø 將樣本表示為N維特征矢量空間中的一個點，在特征空間中研究不同樣本歸屬不同類別的問題Ø 假設我們要把一個樣本集合分成M類：xr , xr , w ,w,.,w1212MØ 在N如何找到一個正確的子空間劃分Ø 對樣本x進行分類統(tǒng)計決策理論24第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 統(tǒng)計模式識別基

15、本過程Ø 分析階段（學習階段）9確定需分類的目標與類別9對每一種類別，選定一組目標樣本9對樣本數(shù)據(jù)進行分析（訓練、學習），形成不同類別目標的特征Ø 識別階段，每個一個模式9對待分類圖像進行必要的預處理與特征提取9按照上述各類別的特征，對提取的特征進行判決分類（匹配），確定其歸屬的類別25第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 統(tǒng)計模式識別基本過程26第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 統(tǒng)計圖像識別基本過程識別分析27第十章模式識別的理論與方法對地觀測與數(shù)字地球科學中心改進規(guī)則誤差檢測規(guī)則學習特征選擇特征提取預處

16、理訓練樣本圖像輸入分類特征選擇特征提取預處理圖像輸入統(tǒng)計模式識別n 決策論法的基本概念¾決策論識別法的定義：x = (x1, x2, ,xn)T，設：模式對于：M個模式類 w1，w2，wM，尋找M個決策函數(shù)d1(x)，d2(x)，dM(x)，具有這樣的特性：如果模式x屬于模式類wi，那么：di(x) > dj(x)j = 1, 2, , M; j i換句話說，如果一個未知模式x屬于第i個模式類，把x代入所有的決策函數(shù)，di(x)的數(shù)值最大。28第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 決策論法的基本概念Ø 決策邊界的定義9對于模式x，如果決

17、策函數(shù)值有：di(x) - dj(x) = 0此x值，被稱為wi與wj的決策邊界。9通常用一個單一的函數(shù)標識兩個類之間的決策邊界， 定義為：dij(x) = di(x) - dj(x) = 0如果 dij(x) > 0 x 屬于類wi 如果 dij(x) < 0 x 屬于類wj29第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 最小距離分類器以蝴蝶花的例子為例：1為多色（w ）和多毛（w2 ）的兩種蝴蝶花，（或稱模板）m1和m2確定兩個2對于一個未知模式x，x與m1和m2的距離，如果與m1 的距離小于與m2 的距離，則x屬于w1，否則屬于w2 。30第十章 模

18、式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別x2 花瓣寬3.02.52.01.51.00.5m1m2多毛的多色的xx1 花瓣長123456731第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 最小距離分類器1）算法思想：9對于M個模式類 wjj = 1,2,.,Mmj為每一個模式類確定一個模式x，如果x與mj 的距離最9對于一個未知模式小，就稱x屬于wj。32第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 最小距離分類器2）最小距離分類器定義：1計算模式類wj的：mj = 1/Nj å xj = 1,2, , MxÎw

19、j其中Nj是屬于模式類wj的模式通過計算已知屬于wj的模式的個數(shù)。的各分量的均值，得到模式mj2計算x 與 mj的距離dj(x) = | x mj |其中 | a | = (aTa)1/2是j = 1, 2, , M范式（平方和開方）33第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 最小距離分類器3 決策如果，di(x) = min(dj(x)就說：x 屬于wij = 1, 2, , M改寫最大的標準形式，決策函數(shù)為：dj(x) = xTmj 1/2mjmjT如果，di(x) = max(dj(x)就說：x 屬于wij = 1,2, , Mj = 1, 2, , M4類

20、wi和wj之間的決策邊界是：dij(x) = di(x) - dj(x)= xT(mi mj) 1/2(mi mj)T(mi mj) = 034第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別3）舉例：多色的和多毛的蝴蝶花，用w1和w2分別表示，有簡單的m1 = (4.4, 1.3)T決策函數(shù)是：m2 = (1.5, 0.3)Td1(x) = xTm1 1/2m1m1 = 4.3x1 + 1.3x2 10.1Td2(x) = xTm2 1/2m2m2 = 1.5x1 + 0.3x2 1.17T決策邊界的等式：d12(x) = d1(x) d2(x) = 2.8x1 1.0x2

21、 8.9 = 035第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別x2 花瓣寬3.02.52.01.51.00.5m1m2多毛的多色的決策邊界2.8x1 +1.0x2x- 8.9 = 0-+5x1 花瓣長12346736第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 相關匹配(1) 相關匹配的基本思想:a. 用樣板子圖像直接作為模式（不是用描述子）b. 通過子圖像與原圖像直接進行相關計算，把相關計算結(jié)果作為決策函數(shù)。c.相關計算獲得最大值的位置，就被認為匹配。37第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 相關匹配(1) 相關

22、匹配基本思想38第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別ytn 相關匹配(2) 算法描述決策函數(shù)是相關函數(shù)c(s,t) = f(x,y)w(x-s,y-t)xyN原點Ks對圖像的每一個點進行相關計算，只計算重疊部分。J(s,t)Mxw(x-s,y-t)f(x,y)39第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 相關匹配（3）問題：Ø 在邊界處將失去準確性，其誤差與子圖像的正比成Ø 相關函數(shù)對振幅的變化太敏感，f(x,y)加倍，c(s,t)也加倍。40第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 相關

23、匹配(4) 改進用相關系數(shù)函數(shù)代替相關函數(shù)f(x,y) f(x,y)w(x-s,y-t) w(s,t)=f(x,y)f(x,y)2w(x-s,y-t) w21/2xyxy(s,t)的值域為（-1，1）實例41第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 相關性匹配(5) 對旋轉(zhuǎn)和比例變化的分析9當被匹配圖像中，對象的致，此方法將失效和角度與模式不一9的正則化，解決空間比例的問題9如果知道原圖像的旋轉(zhuǎn)角度，我們可以通過旋轉(zhuǎn)原圖像，對齊模式解決9如果被匹配的對象的角度任意，有結(jié)論：此方法不能用于這種問題42第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別（

24、Bayes）分析Ø 當特征抽取時存在噪聲干擾，則抽取的特征可能代表不了相應的模式，具有某種隨機性Ø 利用訓練樣本產(chǎn)生的不同類別的模式，每個模式難于用一個來表示，只能得到每一類模式的一個概率分布Ø 為對此類特征進行分類，需采用統(tǒng)計意義上最佳的分類方法Ø 統(tǒng)計分類方法的最基本方法之一：分析分類器、貝分析包括：葉斯估計理論、決策方法、距離等¾43第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別（Bayes）分析公式¾設有N個互不相容的率為P(Bi) ；已知僅當其中某些：B1, B2, BN，每個發(fā)生的概件A才發(fā)生。若其中某

25、一發(fā)生Bi發(fā)生，A發(fā)生的可能性以概率P(A/ Bi)描述。A確實已發(fā)生，則對于A反過來，若發(fā)生條件下Bi發(fā)生的概率應給與重新估計，可有公式：P ( B i ) P ( A / B i )/ A ) =P ( BiNåj = 1P ( B) P ( A / B)jj44第十章模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別分析分類法設有M類圖像：B1, B2, BM若已知Bi的先驗概率：和某觀察特征值X的條件概率：則由特征X 所決定的Bi的概率由¾P(Bi) P(X/ Bi)公式?jīng)Q定：P(Bi )P( X / Bi )P(B / X ) =iNå P(Bj

26、 )P( X / B j )j =1分類實質(zhì)：從統(tǒng)計角度，在已知分類模式概率分布的條件下， 模式所應歸屬的類別¾新出現(xiàn)的45第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別分析分類法兩個類別的分類¾如果某觀察特征值X使P(B1/X)>P(B2/X)，則表明在X特征值出現(xiàn)的情況下，類別B1的可能性較高分類法則：P(B1/X) > P(B2/X)，則決策B1若反之，若 P(B1/X) < P(B2/X)，則決策B2公式，不同模式間重要的區(qū)別是其等價決策法則為：項，可有另一若P(X/B1)P(B1) > P(X/B2)P(B2)，則決策B

27、1反之，若 P(X/B1)P(B1) < P(X/B2)P(B2)，則決策B246第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別分析分類法兩個類別的分類（例）分布的兩個模式類1和2，假定每個類中的模式均服從高斯分布，即有¾在三- 1 ( X - M )T C -1 ( X - M )1P ( X / w ) =iiie2i1 / 2( 2p ) n / 2Ci即每一個模式類中變量的密度函數(shù)均由其均值和協(xié)方差矩陣惟一確定Ei ( X - M i )( X - M i ) TMi = Ei Xé3ùC i =- 484- 4ù

28、50;é 8é1ùC = C= ê- 41 ê1 êúú48M1 = 4 ê1úM2 = 4 ê3úêêë- 4úúû12êë1úûêë3úû47第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別分析公式，可得出決策函數(shù)為：由P(wi / X) = P(X / wi )P(wi )為計算方便，采用對數(shù)形式：i = 1,2d

29、i (x) = lnP(wi / X) = ln P(X / wi ) + ln P(wi )進一步假定P(1)=P(2)=1/2 ，可有：i = 1,21d (x) = X T C -1M -M T C -1Mi = 1,2iiii2d1(x) = 4x1 -1.5d2 (x) = -4- 5.53進一步得出兩個類別的決策面為：d1(x) - d2 (x) = 8+ 4 = 0348第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別分析分類法對多類別問題，可有：若 P(Bi/X)>P(Bj/X)對所有j¹i成立，則決策Bi¾¾分類器利用上述

30、函數(shù)分類器如右圖實例49第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 特征的抽取與選擇Ø 合適的特征抽取與選擇是正確分類的基礎Ø 特征的選擇影響到?jīng)Q策方法的采用與實施效果Ø 特征的提取與選擇與模式定義密切相關n 什么是好的特征？Ø 好的特征之間是相互可區(qū)別的Ø 好的特征常常必須由來確定Ø 好的特征有通過統(tǒng)計方法來確定性假設Ø 相似類別目標的特征在特征空間中聚在一起Ø 不相似類別目標的特征在特征空間中可能聚在一起或相互遠離50第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n

31、 特征的抽取與選擇Ø 所要提取的應當是具有可區(qū)別性、可靠性、獨立性好的少量特征Ø 特征選擇可以看作是一個（從的開始）不斷刪除無用的特征和組合有關聯(lián)的特征的過程，直到特征的數(shù)目減少到易于駕馭的程度， 同時分類器的性能仍能滿足要求為止51第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 特征的抽取與選擇多種方式（例）統(tǒng)計模式識別n 特征的抽取與選擇實例Ø 魚群的特征抽取魚的長度x1 魚的面積x2Ø 在（x1 , x2 ）空間形成兩種類別的聚類群53第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 特征的抽取與選擇實例特

32、征選擇存在問題ü 噪聲與生物多樣性使每種魚的特征類散布在一定區(qū)域ü 特征類別的重迭將導致分類誤差¾聚類的距離與密度問題ü ？處如何分類屬于A：與A類十分靠近屬于B：因為B在該特征區(qū)域的密度最高¾54第十章模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 特征的抽取與選擇實例通過特征空間的尺度變換可改變特征的聚合狀況特征空間尺度變換可能帶來的問題¾¾55第十章模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 特征的抽取與選擇實例特征空間尺度變換可能帶來的問題改進方法：使變化量相同¾56第十章模

33、式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 特征的抽取與選擇實例直接由測量特征進行分類，最好結(jié)果將不可避免地存在誤差¾57第十章模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 特征的抽取與選擇實例Ø 通過統(tǒng)計方法改進特征空間類別的確定對每一類別樣本，分別計算其均值和方差，假定其分布為高斯分布58第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 特征的抽取與選擇實例Ø 通過統(tǒng)計方法改進特征空間類別的確定形成二統(tǒng)計特征分布59第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心統(tǒng)計模式識別n 特征的抽取與選擇實例通過

34、統(tǒng)計方法改進特征空間類別的確定通過Mahalanobis距離確定新的特征空間¾¾60第十章模式識別的理論與方法對地觀測與數(shù)字地球科學中心句法模式識別n 句法模式識別Ø 統(tǒng)計模式識別，通過量化的方法處理模式，最大限度地忽略了模式形狀的內(nèi)在結(jié)構(gòu)關系Ø 句法模式識別，則力求通過準確地抓住這些不同模式類的內(nèi)在結(jié)構(gòu)關系來進行模式識別Ø 以形式語言為理論基礎以圖像描述語言形成樣本的字符描述，通過句法分析方法完成識別61第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心句法模式識別n 句法模式識別的有關基本概念Ø 字符集9一個任意的有限符號集合

35、Ø 句子9在某一字符集上的句子是任一有限長度字符串，該字 取自于這一字符集上的字符組成如，給定一字符集0,1，它上面的有效句子集合為：0,1,00,01,10,.。Ø 語言9定義為某一字符集上的任一句子集合，該集合不一定 是有限的62第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心句法模式識別n 句法模式識別的有關基本概念Ø 語法9定義為一個四元組：G = (VN ,VT , P, S )l VN為一非終止符（變量）集合l VT為終止符（常量）集合； VN與VT為互不相交的兩個集合l P為產(chǎn)生式或重寫規(guī)則的集合，即終止符與非終止符之間的關系表達式l S為起始

36、符由語法G產(chǎn)生的語言L(G)是滿足下面兩個條件的句子的集合：1.2.每一字符串中只包含終止符每一字符串可由起始符S出發(fā)，按照P的規(guī)則推導形成63第十章模式識別的理論與方法對地觀測與數(shù)字地球科學中心句法模式識別n 句法模式識別的有關基本概念Ø 定義了字符集、句子、語言，既明確了基本規(guī)則：字符組成句子，句子組成語言Ø 字符按照一定規(guī)則組成句子，進而組成語言語則形成的要素Ø 與任何一種自然語言一樣，語法在形式語言中起中心作用Ø 句法模式識別中的各個環(huán)節(jié)，都是開n 介紹兩種方法Ø 匹配形狀數(shù)Ø 串匹配著語法的研究展64第十章 模式識別的理論與

37、方法對地觀測與數(shù)字地球科學中心句法模式識別n 句法模式識別的有關基本概念Ø 例定義有向線段之間的運算：語法定義：VT= a, b, c, dVN= S, A1 , A2 , A3 , A4G = (VN ,VT , P, S )65第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心句法模式識別n 句法模式識別的有關基本概念Ø 例P： S ® A * AA ® A * c1213A3 ® d + A4A2 ® a + bA4 ® c + (» d )”表示有向線段d 的反向。其中“ » d該語法產(chǎn)生的語

38、言類是：d + c + (» d )*(a + b) * c它可描述的圖形結(jié)構(gòu)為：66第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心句法模式識別n 匹配形狀數(shù)(1) 匹配形狀數(shù)的基本思想形狀數(shù)：描述一個對象的邊界、結(jié)構(gòu)時，所得到表達式或特征數(shù)；可看作為模式串、模式樹的一種通用表述。通過比較兩個對象邊界的形狀數(shù)的相似程度， 來匹配對象。例如：未知模式模式類67第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心句法模式識別n 匹配形狀數(shù)(2) 基本概念a.兩個區(qū)域邊界的相似級別k的定義： 相同形狀數(shù)的最大序號。如：當考慮用4碼表示的封閉區(qū)域邊界的形狀數(shù)時，A和B具有相似級別k

39、，如果滿足s4(A) = s4(B), s6(A) = s6(B), s8(A) = s8(B), sk(A) = sk(B),sk+2(A) ¹ sk+2(B), sk+4(A) ¹ sk+4(B), ，這里s表示形狀數(shù),下標表示序號。68第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心句法模式識別n 匹配形狀數(shù)(2) 基本概念b.兩個區(qū)域邊界A和B形狀數(shù)的距離D(A,B)， 定義為相似級別k的倒數(shù) ：D(A,B) = 1 / k距離滿足如下性質(zhì)：D(A,B) ³ 0D(A,B) = 0 iff A=BD(A,C) £ maxD(A,B),D(B

40、,C)69第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心句法模式識別n 匹配形狀數(shù)(3) 算法思想a. 用不同密度的網(wǎng)格劃分邊界區(qū)域，獲得不同序數(shù)的形狀數(shù)。b. 如果使用相似級別k，k越大說明越相似。c.如果使用相似距離D，D越小說明越相似d 可以利用相似進行判別70第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心句法模式識別n 匹配形狀數(shù)（4）舉例假設我們有一個形狀F，想在另5個形狀（A，B，C，D，E）中找到與其最相似的形狀ABCDE71第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心F句法模式識別這個問題類似于有五個原型形狀，想找出一個給定的尚不確定的形狀的最佳匹配的

41、問題。這個問題可以利用相似進行可視化判別468ABCDEF ABCDEFBCDEFAA AA10DDCFCFBE12BBEE14D實例72第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心CF句法模式識別n 串匹配（1） 串匹配的基本思想比較兩個邊界的串編碼的相似程度，來進行匹配（2） 三個基本概念設: 兩個區(qū)域邊界A和B已分別被編碼為串a(chǎn)1a2an和b1b2bm。73第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心句法模式識別n 串匹配a. 兩個串的匹配數(shù)M:當 ak= bk 時我們說發(fā)生了一個匹配。令M代表A、B中匹配的總數(shù)。b. 不匹配的符號數(shù)量Q：Q = max（|A|，|B|）- M這里|arg|是字符串的長度。當且僅當A和B 完全相同時，Q = 0。74第十章 模式識別的理論與方法對地觀測與數(shù)字地球科學中心句法模式識別串匹配c. A和B相似度的簡便衡量R:R = M/Q = M / max(|A|,|B|) - M因此，當A和B完全匹配時，R = ¥； 當A和B中任何字符都不匹配時，M = 0，R = 0。75第十章模式識別的理論與方法對地觀測與數(shù)字地球科學中心句法模式識別n 串匹配（3）算法思想a. 由于匹配是逐字符進行的，b. 選擇一個好的開始點，可以大大減少計算量。任何將兩個串規(guī)則化為相