《模式識別緒論》PPT課件.ppt

,模式識別,2012年2月22日,自動化學院袁立,1,出勤：10%實驗：4學時，兩個實驗，10考試：80，開卷,課程要求,11:02,2,教材：張學工等編，模式識別清華大學出版社，2010年，第3版,參考書：RuchardO.Duda等模式分類（PatternClassification）機械工業(yè)出版社，2004年,課程要求,11:02,3,模式與模式識別的概念模式識別的主要方法監(jiān)督模式識別與非監(jiān)督模式識別模式識別系統(tǒng)的典型構成模式識別系統(tǒng)應用舉例,第一章緒論,4,一、模式識別,1.1模式與模式識別的概念,直觀，無所不在兒童認數字：數字符號的識別讀書看報：文字識別汽車、火車，狗叫、人語：聲音識別人群中尋找一個人：根據面像、形體或其他特征進行識別人類的模式識別能力是極其平常的，時刻在完成某種模式識別的任務。隨著社會活動以及生產科研的發(fā)展，需要識別的對象種類越來越多，內容越來越復雜和深入，要求越來越高。為了減輕工作強度，希望計算機代替人來完成識別工作；有些場合環(huán)境惡劣、存在危險或人類不能接近，需要借助機器、運用分析算法進行識別。,11:02,5,第一章緒論,11:02,6,1.模式識別(PatternRecognition):使計算機模仿人的感知能力，從感知數據中提取信息（判別物體和行為）的過程。模式識別作為一門學科，是研究用機器完成自動識別事物的工作；研究內容：使計算機做以前只能由人類才能做的事，具備人所具有的、對各種事物或現象進行分析、描述與判斷的部分能力。模式識別學科形成于5060年代，與眾多學科有聯(lián)系，尤其與人工智能和圖像處理關系密切。,1.1模式與模式識別的概念,2.模式與模式類：模式：需要識別且可測量的對象的描述。這些對象與實際的應用有關，如：字符識別的模式每個字符圖像人臉識別的模式每幅人臉圖像模式類：當用一定的度量來衡量兩個模式，而找不出它們之間的差別時，它們在這種度量條件下屬于同一等價類，就說它們是同一模式類。例如：數字識別有10個類別，每個數字就是一個類。不同模式類之間是可以區(qū)分的，應有明確界限。,11:02,7,1.1模式與模式識別的概念,3.識別最基本的方法：計算計算機根據已研制的識別算法，把輸入的未知模式劃入正確類別中，從而實現自動分類。識別算法中的關鍵環(huán)節(jié)就是要對待識別事物與標準“模板”的相似程度進行計算。,特征向量表示法：將對事物進行度量的指標排成向量的形式。一維表示X1=1.5X2=3二維表示X1=(x1,x2)T=(1,2)TX2=(x1,x2)T=(2,1)T三維表示X1=(x1,x2,x3)T=(1,1,0)TX2=(x1,x2,x3)T=(1,0,1)T蘋果（重量，直徑，顏色）,4.模式描述方法,圖像的向量表示方法：在計算機里分析的稱為數字圖像，它由排列整齊的二維網格組成，分為若干行與若干列，相當于一個二維數組，或稱矩陣。我們稱每個元素為像素。,左圖為57的數字圖像；一個數字就用57共35個網格是黑是白來表示；如令是黑為“1”，是白為“0”，那么一個數字就可用35維的二進制向量表示。這就是典型的特征向量表示法,1.1模式與模式識別的概念,結構表示法：由事物的組成成分與相互關系表示在右側的圖中八個基元分別表示0，1，2，3，4，5，6，7，八個方向和基元線段長度。則右側樣本可以表示為X1=006666這種方法將在句法模式識別中用到。,二、模式識別簡史1929年G.Tauschek發(fā)明閱讀機，能夠閱讀0-9的數字。30年代Fisher提出統(tǒng)計分類理論，奠定了統(tǒng)計模式識別的基礎。統(tǒng)計模式識別是模式識別的主要理論。50年代NoamChemsky提出形式語言理論傅京蓀提出句法結構模式識別。60年代L.A.Zadeh提出了模糊集理論，模糊模式識別方法得以發(fā)展和應用。80年代以Hopfield網、BP網為代表的神經網絡模型導致人工神經元網絡復活，并在模式識別得到較廣泛的應用。90年代小樣本學習理論，支持向量機受到了很大的重視。2000年，流形學習（manifoldlearning）：流形學習就是從高維采樣數據中恢復低維流形結構，即找到高維空間中的低維流形，并求出相應的嵌入映射，以實現維數約簡或者數據可視化.2005年，稀疏表示（sparserepresentation）：近年來有關生理學的研究成果表明：人類的視覺系統(tǒng)具有對圖像的稀疏表示特性,神經元對于輸入圖像的激活機制具有高度的稀疏性.,1.1模式與模式識別的概念,三.關于模式識別的國內、國際學術組織,1973年IEEE發(fā)起了第一次關于模式識別的國際會議“ICPR”，成立了國際模式識別協(xié)會-“IAPR”，每2年召開一次國際學術會議。1977年IEEE的計算機學會成立了模式分析與機器智能（PAMI）委員會，每2年召開一次模式識別與圖象處理學術會議。國內組織：中國自動化學會：模式識別與機器智能(PRMI)專業(yè)委員會，1981年成立，IAPR成員組織；人工智能與模式識別專業(yè)委員會；中國人工智能學會國內學術機構：中科院模式識別國家重點實驗室，中科院計算所，微軟研究院，清華大學等。,11:02,10,1.1模式與模式識別的概念,模式識別學科位置,模式識別：計算機科學與電子工程交叉學科中國：“控制科學與工程”一級學科二級學科：控制理論與控制工程、模式識別與智能系統(tǒng)、系統(tǒng)工程等西方：沒有自動控制系自動控制：電子工程系、機械工程系模式識別：電子工程系、計算機科學系,四、模式識別的應用多媒體數據檢索（文檔、圖像、視頻、音樂檢索）字符識別（印刷體字符的識別；手寫體字符的識別（脫機/聯(lián)機），信函分揀、支票查對、自動排板、稿件輸入等）醫(yī)療診斷（心電圖，腦電圖，染色體，癌細胞識別，疾病診斷等）工程（產品缺陷檢測、自動導航系統(tǒng)、污染分析）軍事（航空攝像分析、雷達和聲納信號檢測和分類、自動目標識別等）安全監(jiān)控（基于生物特征的身份識別、視頻監(jiān)控、交通監(jiān)控、音視頻監(jiān)聽）,1.1模式與模式識別的概念,現有生物特征識別類型,11:02,12,1.1模式與模式識別的概念,1.2模式識別的主要方法,基于知識的方法(Knowledge-based)AI、專家系統(tǒng)(ExpertSystems)句法（結構）模式識別(SyntaxPRorStructuralPR)（基于結構性描述）基于數據的方法(Data-based)統(tǒng)計模式識別方法（StatisticalPR）（基于特征向量表示方法）人工神經網絡(ANN)支持向量機(SVM),統(tǒng)計模式識別方法：在確定了描述樣本所采用的特征之后，收集一定數量的已知樣本，用這些樣本作為訓練集來訓練一定的模式識別機器，使之在訓練后能夠對未知樣本進行分類。這是基于數據的機器學習中研究最多的一個方向。,統(tǒng)計模式識別用函數表示：Y=F(X)X的定義域取自特征集Y的值域為類別的標號集F是模式識別的判別方法有監(jiān)督模式識別分類（classification）給出若干已知答案的樣本（訓練樣本trainingsamples）由機器從這些樣本中進行學習（訓練training/learning）學習的目的在于從這些樣本中總結規(guī)律，使之能夠對新的樣本進行判斷無監(jiān)督模式識別聚類（clustering）所面對的只有未知答案的樣本由機器從這些樣本中進行學習（自學習）學習的目的在于從這些樣本中發(fā)現規(guī)律，這種規(guī)律應該是某種固有的關系，或者依據這種規(guī)律對對象的分類有某種功用,1.3監(jiān)督模式識別與非監(jiān)督模式識別,1.模式識別系統(tǒng)：執(zhí)行模式識別的計算機系統(tǒng)。,1.4模式識別系統(tǒng)的典型構成,2.模式識別系統(tǒng)組成：信息獲取與預處理，特征提取與選擇、分類或聚類、后處理等四個部分。,第一章緒論,1.4模式識別系統(tǒng)的典型構成,1.4模式識別系統(tǒng)的典型構成,1.4模式識別系統(tǒng)的典型構成,監(jiān)督模式識別系統(tǒng)組成：數據獲取，預處理，特征提取選擇、分類器設計以及分類決策五部分。,訓練過程：對作為訓練樣本的量測數據進行特征選擇與提取，得到它們在特征空間的分布，依據這些分布決定分類器的具體參數，也就是設計分類器的過程。識別過程：分類決策的過程，則是在特征空間中用統(tǒng)計方法把被識別對象歸為某一類別。,3.監(jiān)督模式識別系統(tǒng)構成及功能,（1）信息獲?。河貌煌问降膫鞲衅鳂嫵桑瑢崿F信息獲取與信息在不同媒體之間的轉換，非電信號轉換成電信號。,用話筒將聲音信號轉換成電信號，表現出電壓(電流)隨時間變化的復雜波形。景物信息在攝像機靶面成像并轉換成二維的象素矩陣，每個像素(矩陣元素)的電信號與物體表面反射的光強或顏色信息呈現函數關系,一般輸入對象的信息有三種類型：二維圖象，如文字、指紋、地圖、照片等一維波形，如腦電圖、心電圖、機械震動波形等物理參量和邏輯值，如疾病診斷中病人體溫，各種化驗數據；或對癥狀有無描述，如疼與不疼（0/1）,1.4模式識別系統(tǒng)的典型構成,（2）預處理去除所獲取信息中的噪聲，增強有用的信息，及一切必要的使信息純化的處理過程。預處理這個環(huán)節(jié)內容很廣泛，與要解決的具體問題有關，例如，從圖象中將汽車車牌的號碼識別出來，就需要先將車牌從圖像中找出來，再對車牌進行劃分，將每個數字分別劃分開。做到這一步以后，才能對每個數字進行識別。以上工作都應該在預處理階段完成。,（3）特征選擇和提取功能：對所獲取的信息實現從測量空間到特征空間的轉換。將所獲取的原始量測數據轉換成能反映事物本質，并將其最有效分類的特征表示。輸入：原始的量測數據(經過必要的預處理)，例如由聲波變換成的電信號，表現為電壓電流幅度隨時間的變化，二維圖像每個像素所具有的灰度值等。輸出：將原始量測數據轉換成有效方式表示的信息，從而使分類器能根據這些信息決定樣本的類別。,1.4模式識別系統(tǒng)的典型構成,特征選擇和提取:選擇什么樣的方法來描述事物，從而可以有效、牢靠地把事物正確地區(qū)分開。,如令是黑為“1”，是白為“0”，那么一個數字就可用35維的二進制向量表示。這就是典型的特征向量表示法。,另一種方法則是將數字用筆劃表示，也就是將它分成一橫加上一斜杠表示。這種表示方法屬于結構表示法范疇。這種方法沒有前一種方法的缺點，但提取這種結構信息也不是一件容易方便的事。,缺點：這種表示與網格的尺寸有關，與字的筆劃粗細有關，更主要的是字在網格中的不同位置與轉向有關。這個字在網格中略為偏一點，其特征向量表示就會有很大的不一樣。這就說明了這種表示的穩(wěn)定性差。,例：印刷體數字大多通過掃描儀輸入，或從圖像中獲取。這樣，一個數字往往用一個NM的數組表示。如果N5，M7，則一個數字就用57共35個網格是黑是白來表示。,1.4模式識別系統(tǒng)的典型構成,（4）分類器設計與分類決策分類器設計：將該特征空間劃分成由各類占據的子空間，確定相應的決策分界和判決規(guī)則，使按此類判決規(guī)則分類時，錯誤率最低。把這些判決規(guī)則建成標準庫。分類決策：分類器在分界形式及其具體參數都確定后，用相應的決策分界對待分類樣本進行分類決策的過程。,1.4模式識別系統(tǒng)的典型構成,1.5模式識別系統(tǒng)實例,19名男女同學進行體檢，測量了身高和體重，但事后發(fā)現其中有4人忘記填寫性別，試問（在最小錯誤的條件下）這4人是男是女？體檢數值如下：,11:02,24,待識別的模式：性別（男或女）測量的特征：身高和體重訓練樣本：15名已知性別的樣本特征,模式識別系統(tǒng)實例（一）,目標：希望借助于訓練樣本的特征建立判別函數（即數學模型）由訓練樣本得到的特征空間分布圖：,11:02,25,從圖中訓練樣本的分布情況，找出男、女兩類特征各自的聚類特點，從而求取一個判別函數（直線或曲線）。只要給出待分類的模式特征的數值，看它在特征平面上落在判別函數的哪一側，就可以判別是男還是女了。,1.5模式識別系統(tǒng)實例,11:02,26,魚類罐頭加工廠：將傳送帶上的魚按品種自動分類，即把不同的魚分開。魚的分類：鮭魚（salmon）,鱸魚（seabass）,模式識別系統(tǒng)實例（二）,數據采集：用光學感知手段，定時拍攝魚的數字圖像，將其傳入計算機。預處理：增強圖像中感興趣的部分，抑制圖像中的噪聲，將不同的魚、魚與背景分離開來。特征提?。╢eatureextraction）：待分對象鮭魚和鱸魚確實存在一些差異，比如長度、寬度、光澤和形狀等。利用類別之間的這些差異來分類。,1.5模式識別系統(tǒng)實例,11:02,27,模式識別系統(tǒng)實例（二）,特征提取（featureextraction）：待分對象鮭魚和鱸魚確實存在一些差異，比如長度、寬度、光澤和形狀等。利用類別之間的這些差異來分類。特征：從模式中提取的、對分類有用的特征。特征選擇是模式識別的核心問題之一。分類判別（classification）單一特征先驗知識：鱸魚一般比鮭魚長。因此可以選擇長度為分類特征；長度l超過預定閾值l*時判定為鱸魚，否則判定為鮭魚。如何獲得長度閾值l*呢？（預定）,1.5模式識別系統(tǒng)實例,11:02,28,模式識別系統(tǒng)實例（二）,利用特征直方圖獲得長度閾值l*,直方圖表明：無論怎樣確定長度閾值l*，都不能將兩類魚截然分開，分類錯誤比較嚴重。通常，單一特征不足以很好分類。,1.5模式識別系統(tǒng)實例,11:02,29,模式識別系統(tǒng)實例（二）,嘗試利用其他特征：魚的光澤度，用x表示。,1.5模式識別系統(tǒng)實例,11:02,30,模式識別系統(tǒng)實例（二）,利用多個特征進行分類形成特征空間：以每個特征為坐標軸形成的空間。特征的個數，就是特征空間的維數。特征向量：特征空間中的一個點。X=(x1,x2)T表示一條魚，x1代表長度，x2代表光澤度。分類器設計：要找到一個判定邊界,兩類問題判定線判定線把特征空間分為兩個區(qū)域，識別時特征向量落在那個區(qū)域就判定為相應類別。其總分類錯誤比單一特征分類器好一些，但仍存在一些錯誤的分類。,1.5模式識別系統(tǒng)實例,11:02,31,模式識別系統(tǒng)實例（二）,分類器的推廣能力：即分類器對未知模式的正確分類的能力復雜的分類算法導致復雜的判定邊界。判決曲線被過分調諧到這些訓練樣本上，雖然所有訓練樣本都被正確分類，但其推廣能力卻很差。比如：圖中的?新模式更像鮭魚，卻被分到鱸魚類了。,1.5模式識別系統(tǒng)實例,11:02,32,模式識別系統(tǒng)實例（二）,簡化分類器設計方案分類器設計無需上面那樣復雜，即便對訓練樣本不能完美識別，只要對新模式有足夠的推廣能力就可以接受。分類器如何自動產生比較簡單的判決邊界，使其比上面的直線和復雜邊界更優(yōu)秀？如何預測分類器對新模式的推廣能力？這些都是模式識別要研究的問題。,1.5模式識別系統(tǒng)實例,模式識別系統(tǒng)舉例（三）：汽車車牌識別,應用領域：自動收費站，十字路口的違章車輛監(jiān)視等。,主要步驟：（1）圖像獲?。?）車牌的提取和定位（3）字符識別部分,1.5模式識別系統(tǒng)實例,1.5模式識別系統(tǒng)實例,11:02,35,1.5模式識別系統(tǒng)實例,車牌定位模塊目的：從整幅圖像中定位出車牌的精確位置。利用的信息：是車牌部分的紋理分布，主要利用的是水平和豎直兩個方向上的邊緣。在車牌部分，邊緣分布比較密集，可以利用這一點提取出候選的車牌區(qū)域，在圖中用方框標出。粗略定位的結果往往不是很準，我們還可以利用顏色的連續(xù)性信息對定位的結果進行修正。之后輸出的就是候選的車牌位置，這些位置中，只有一個是真正的車牌。而究竟哪一個是對的，要到字符識別階段才能有結果。,11:02,36,1.5模式識別系統(tǒng)實例,字符識別模塊目的：輸入包括每一個候選車牌區(qū)域，而通過它們的輸出評價，來把不合適的偽車牌區(qū)域去掉，只把最正確車牌的結果作為最終結果輸出出來。第一部分：字符分割，要把車牌中的一個個字符逐一切分開，這樣才能在下一步的識別中對每一個字符分別處理。分割方法：利用灰度圖像往水平方向的投影。在有數字或字符的部分，這個投影值應該比較大，而在字符之間的間隙處，投影的累計值就幾乎為零了。確定是否車牌：如果劃分結果比較合理，劃分出的每個字符的寬度都差不多，那么說明這個區(qū)域比較像車牌。如果字體太寬，說明是其它的字符。,11:02,37,1.5模式識別系統(tǒng)實例,模板匹配：是把樣本字符與輸入的待識別字符作匹配，如果兩個字符很像(在某種距離度量下距離很小)，說明匹配成功，把這個模板的對應字符作為輸出結果。特征提?。菏菍颖竞痛郎y圖像都先提取一些明顯的特征，例如對“5”和“9”考慮其右上角是否封口，這樣作的好處是可以用維數較低的向量來描述圖像，而且這些特征都是有代表性，可以用來區(qū)分不同樣本的。,11:02,38,第二部分：字符識別，方法很多：神經元網絡，PCA，特征提取及匹配等，模板匹配和特征提取是比較常用的方法。,1.5模式識別系統(tǒng)實例,字符識別模塊的訓練和識別過程,11:02,39,車牌定位模塊的訓練和識別,1.5模式識別系統(tǒng)實例,11:02,40,其它應用舉例：人臉檢測與跟蹤人臉識別視頻監(jiān)控異常行為分析智能交通,1.5模式識別系統(tǒng)實例,智能視覺物聯(lián)網（SmartVisualInternetofThings，SVIOT）,物聯(lián)網是指通過各種信息傳感設備，如射頻識別（RFID）、紅外感應器、藥理傳感器、聲音傳感器、圖像視頻傳感器等，實時采集其聲、光、熱、電、力學、化學、生物、位置等各種需要的信息，與互聯(lián)網結合形成的一個巨大網絡。其目的是實現物與物、物與人，所有的物品與網絡的連接，方便識別、管理和控制?！爸悄芤曈X物聯(lián)網”涉及物聯(lián)網的視覺感知部分，利用各類圖像獲取傳感器，包括監(jiān)控攝像機、手機、數碼相機，獲取人、車、物圖像或視頻，并采用智能分析技術對視覺信息進行處理，為后續(xù)利用提供支撐。智能視覺物聯(lián)網它是未來物聯(lián)網中重要組成部分，對視覺感知范圍內的人、車或其他物件等目標賦以“身份”標簽并識別目標的實際“身份”，并利用網絡化特點對大范圍中的目標標簽進行關聯(lián)，有效地分析目標標簽物體的實時狀態(tài)，感知各類異常事件，就異常事件的發(fā)生向相關受體提出自動警示。,11:02,41,1.5模式識別系統(tǒng)實例,11:02,42,學習機器的學習過程：使用一批包括各類別的訓練樣本勾畫出各種事物在特征空間分布的規(guī)律性確定使用分類的具體數學公式及其參數,1.6模式識別的若干問題,第一章緒論,分類器設計：求優(yōu)化解的過程模式識別中的學習與訓練是從訓練樣本提供的數據中找出某種數學式子的最優(yōu)解，這個最優(yōu)解使分類器得到一組參數，按這種參數設計的分類器使人們設計的某種準則達到極值。分類器參數的選擇或學習過程得到的結果取決于設計者選擇什么樣的準則函數。不同準則函數的最優(yōu)解對應不同的學習結果，得到性能不同的分類器。,例：兩類訓練樣本分布圖中兩類訓練樣本的分布體現出近似圓形的分布。因此如能把這兩個圓形區(qū)域確定下來，將它們的邊界用某種數學式子近似，那么落在某一個圓形內的樣本就可以用這種數學式子來判斷。當不一定非要精確地表達不同類樣本分布地聚集區(qū)時。用一條直線(線性方程)也許可以達到同樣的目的。滿足直線的方程是一個線性方程，寫成f(x1,x2)=ax1+bx2+c=0，而不在該直線上的點則用f(x1,x2)是否大于零或小于零來分辨。,1.3模式識別的若干問題,一般來說，決定使用什么樣的分類函數往往是人為決定的。對一個實際分類問題，快速計算、快速分類是十分重要的。,兩類樣本在二維特征空間中有相互穿插很難用簡單的分界線將它們完全分開。直線作為分界線線性分類器對圖中所示的樣本分布情況，無論直線參數如何設計，總會有錯分類發(fā)生。如果以錯分類最小為原則分類，則圖中A直線可能是最佳的分界線，它使錯分類的樣本數量為最小。,2.模式的緊致性分類器設計難易程度與模式在特征空間的分布方式有密切關系。,1.3模式識別的若干問題,(a)(b)(c),例：(a)、(b)與(c)分別表示了兩類在空間分布的三種狀況。其中(a)中兩類樣本存在各自明確的區(qū)域，它們之間的分界線(或面，超曲面)具有簡單的形式，因而也較易區(qū)分，(b)中兩類雖有各自不同的區(qū)域，但分界面的形式比較復雜，因而設計分類器的難度要大得多，如果遇到(c)類的情況則無法將它們正確分類。,緊致集：同一類模式類樣本的分布比較集中，沒有或臨界樣本很少，這樣的模式類稱緊致集。性質：(1)臨界點的數量與總的點數相比很少。(2)集合中任意兩個內點可以用光滑線連接，在該連線上的點也屬于這個集合。(3)每個內點都有一個足夠大的鄰域，在該鄰域中只包含同一集合中的點。,特征提?。焊纳茢祿木o致性,1.3模式識別的若干問題,許多問題在量測空間表示時往往不滿足緊致性。但是如果它們的確是可分的話，這就意味著可以通過一種變換，使它們在相應的特征空間中界線分明，也就是具有了緊致性。模式識別系統(tǒng)設計的任務就是要尋找這樣一種變換，即選擇一種特征空間，使不同類別的樣本能正確地分開。因此在討論模式識別的問題時，通常假設同一類的各個模式在該空間中組成一個緊致集。至于如何找到這種變換還沒有一種統(tǒng)一的有效的理論與方法。,3.距離和相似性度量在特征空間中用特征向量描述樣本的屬性，把相似性度量用距離量表示。給定一個輸入樣本集合，用D維空間中的一個點表示某個樣本，可以選擇某個隨距離增加而下降的函數f作為兩個樣本和之間相似性度量,1.3模式識別的若干問題,歐式距離的減函數,絕對值偏差的減函數,偏差的夾角,