模式識別導論1

第一章概論

§1-1模式識別的基本概念一.模式識別的基本定義模式(pattern)----存在于時間，空間中可觀察的事物,具有時間或空間分布的信息。模式識別(PatternRecognition)----用計算機實現(xiàn)人對各種事物或現(xiàn)象的分析,描述,判斷,識別。模式識別與圖象識別，圖象處理的關系模式識別是模擬人的某些功能模擬人的視覺:計算機+光學系統(tǒng)模擬人的聽覺:計算機+聲音傳感器模擬人的嗅覺和觸覺:計算機+傳感器2024/11/9二.模式識別的發(fā)展史1929年G.Tauschek發(fā)明閱讀機，能夠閱讀0-9的數(shù)字。30年代Fisher提出統(tǒng)計分類理論,奠定了統(tǒng)計模式識別的基礎。因此，在60～70年代，統(tǒng)計模式識別發(fā)展很快，但由于被識別的模式愈來愈復雜，特征也愈多，就出現(xiàn)“維數(shù)災難”。但由于計算機運算速度的迅猛發(fā)展，這個問題得到一定克服。統(tǒng)計模式識別仍是模式識別的主要理論。50年代NoamChemsky提出形式語言理論,美籍華人付京蓀提出句法結(jié)構(gòu)模式識別。60年代L.A.Zadeh提出了模糊集理論，模糊模式識別理論得到了較廣泛的應用。2024/11/980年代Hopfield提出神經(jīng)元網(wǎng)絡模型理論。近些年人工神經(jīng)元網(wǎng)絡在模式識別和人工智能上得到較廣泛的應用。90年代小樣本學習理論，支持向量機也受到了很大的重視。2024/11/9三.關于模式識別的國內(nèi)、國際學術(shù)組織1973年IEEE發(fā)起了第一次關于模式識別的國際會議“ICPR”，成立了國際模式識別協(xié)會---“IAPR”，每2年召開一次國際學術(shù)會議。1977年IEEE的計算機學會成立了模式分析與機器智能（PAMI）委員會，每2年召開一次模式識別與圖象處理學術(shù)會議。國內(nèi)的組織有電子學會，通信學會，自動化協(xié)會，中文信息學會….。2024/11/9§1-2模式識別系統(tǒng)信息獲?。菏峭ㄟ^傳感器，將光或聲音等信息轉(zhuǎn)化為電信息。信息可以是二維的圖象,如文字，圖象等；也可以是一維的波形，如聲波，心電圖，腦電圖；還可以是物理量與邏輯值。預處理：包括A\D,二值化，圖象的平滑，變換，增強，恢復，濾波等,主要指圖象處理。2024/11/9特征抽取和選擇：在模式識別中，需要進行特征的抽取和選擇。例如，一幅64x64的圖象可以得到4096個數(shù)據(jù)，這種在測量空間的原始數(shù)據(jù)通過變換獲得在特征空間最能反映分類本質(zhì)的特征。這就是特征提取和選擇的過程。分類器設計：分類器設計的主要功能是通過訓練確定判決規(guī)則，使按此類判決規(guī)則分類時，錯誤率最低。把這些判決規(guī)則建成標準庫。分類決策：在特征空間中對被識別對象進行分類。2024/11/9§1-3模式識別的應用字符識別：包括印刷體字符的識別；手寫體字符的識別（脫機），各種OCR設備例如信函分揀、文件處理、卡片輸入、支票查對、自動排板、期刊閱讀、稿件輸入；在線手寫字符的識別（聯(lián)機），各種書寫輸入板。醫(yī)療診斷：心電圖，腦電圖，染色體，癌細胞識別，疾病診斷，例如關幼波肝炎專家系統(tǒng)。遙感：資源衛(wèi)星照片，氣象衛(wèi)星照片處理，數(shù)字化地球，圖象分辨率可以達到1米。指紋識別與臉形識別。檢測污染分析，大氣，水源，環(huán)境監(jiān)測。2024/11/9自動檢測：產(chǎn)品質(zhì)量自動檢測語聲識別，機器翻譯，電話號碼自動查詢，偵聽，機器故障判斷。軍事應用2024/11/9§1-4模式識別的基本問題一.模式(樣本)表示方法向量表示:假設一個樣本有n個變量(特征)Ⅹ=(X1,X2,…,Xn)T矩陣表示:N個樣本，n個變量(特征)2024/11/9幾何表示一維表示

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)T

X2=(x1,x2,x3)T==(1,0,1)T2024/11/9基元（鏈碼）表示：在右側(cè)的圖中八個基元分別表0,1,2,3,4,5,6,7,八個方向和基元線段長度。則右側(cè)樣本可以表示為X1=006666。

這種方法將在句法模式識別中用到。2024/11/9二.模式類的緊致性緊致集：同一類模式類樣本的分布比較集中，沒有或臨界樣本很少，這樣的模式類稱緊致集。臨界點(樣本)：在多類樣本中，某些樣本的值有微小變化時就變成另一類樣本稱為臨界樣本（點）。2024/11/9緊致集的性質(zhì)要求臨界點很少集合內(nèi)的任意兩點的連線,在線上的點屬于同一集合集合內(nèi)的每一個點都有足夠大的鄰域,在鄰域內(nèi)只包含同一集合的點模式識別的要求:滿足緊致集，才能很好的分類；如果不滿足緊致集，就要采取變換的方法,滿足緊致集.2024/11/9三.相似與分類兩個樣本xi，xj之間的相似度量滿足以下要求：應為非負值樣本本身相似性度量應最大度量應滿足對稱性在滿足緊致性的條件下，相似性應該是點間距離的單調(diào)函數(shù)用各種距離表示相似性：絕對值距離已知兩個樣本Xi=(xi1,xi2,xi3,…,xin)T

Xj=(xj1,xj2,xj3,…,xjn)T

2024/11/9歐幾里德距離明考夫斯基距離

其中當q=1時為絕對值距離，當q=2時為歐氏距離2024/11/9切比雪夫距離

q趨向無窮大時是明氏距離的極限情況馬哈拉諾比斯距離

其中xi，xj為特征向量，為協(xié)方差。使用的條件是樣本符合正態(tài)分布2024/11/9夾角余弦

即樣本間夾角小的為一類。例：x1,x2,x3的夾角如圖：因為x1,x2的夾角小，所以x1,x2最相似。x1x2x32024/11/9相關系數(shù)

為xixj的均值

注意：在求相關系數(shù)之前，要將數(shù)據(jù)標準化分類的主觀性和客觀性分類帶有主觀性：目的不同，分類不同。例如：鯨魚，牛，馬從生物學的角度來講都屬于哺乳類，但是從產(chǎn)業(yè)角度來講鯨魚屬于水產(chǎn)業(yè)，牛和馬屬于畜牧業(yè)。分類的客觀性：科學性判斷分類必須有客觀標準，因此分類是追求客觀性的，但主觀性也很難避免，這就是分類的復雜性。2024/11/9四.特征的生成

低層特征：無序尺度：有明確的數(shù)量和數(shù)值。有序尺度：有先后、好壞的次序關系，如酒分為上，中，下三個等級。名義尺度：無數(shù)量、無次序關系，如有紅，黃兩種顏色中層特征：經(jīng)過計算，變換得到的特征高層特征：在中層特征的基礎上有目的的經(jīng)過運算形成例如：椅子的重量=體積*比重其中體積與長，寬，高有關；比重與材料，紋理，顏色有關。這里低、中、高三層特征都有了。2024/11/9五.數(shù)據(jù)的標準化

極差標準化，一批樣本中，每個特征的最大值與最小值之差。

極差

極差標準化

方差標準化

Si

為方差標準化的方法很多，原始數(shù)據(jù)是否應該標準化，應采用什么方法標準化，都要根據(jù)具體情況來定。2024/11/9§1-5模式識別應用舉例

郵政編碼是０～９十個手寫數(shù)字組成，屬于比較簡單的手寫體字符識別。但由于郵政編碼的廣泛書寫者及書寫習慣大不相同，書寫工具不同及書寫時的隨機變化，同一數(shù)字的字形是多種多樣的。在個別情況下，某一數(shù)字的字形變化會逐漸接近別的數(shù)字，如下圖：

不同數(shù)字之間字形的連續(xù)變化2024/11/9

這種由量變到質(zhì)變的過程給識別帶來極大的困難。下面我們簡單介紹一種郵政編碼的識別方法，對模式識別系統(tǒng)有初步了解。

2024/11/9

一.二值化處理

對于字符識別，字符圖象不需要256個灰度級，只要黑白兩級即可。因此圖象的存貯量可以大大壓縮，加快處理速度。二值化的方法是建立直方圖如下。

0IB:背景灰度IW:圖象灰度IT:直方圖谷點IBITIWf(I)灰度

一.二值化處理

對于字符識別，字符圖象不需要256個灰度級，只要黑白兩級即可。因此圖象的存貯量可以大大壓縮，加快處理速度。二值化的方法是建立直方圖如下：

§1-5模式識別應用舉例2024/11/9

若取谷點IT作為閾值，則這樣就可以把一個多灰度級的圖象變成二值圖象。但實際上谷點IT常常是不明顯的，而且是變化的，因此閥值IT的選擇是非常重要的。根據(jù)圖象的復雜程度，我們可以選取固定閥值和自動閥值。固定閥值：取

IT為固定值。手動閥值：用人工調(diào)節(jié)IT的大小。自動閥值：根據(jù)圖象變化，可自動調(diào)整二值化的閥值的大小，使圖象最好。I>ITI

IT2024/11/9

閥值IT的數(shù)學表示為：

IT=T[（X，Y），N（X，Y），g（X，Y）]其中(X，Y)為象素坐標，N（X，Y）為象素周圍局部灰度特征，g(X，Y)為灰度。整體閥值選擇：IT=T[g（X，Y）]，只由直方圖谷點象素的灰度決定閥值，效果較差。局部閥值選擇：IT=T[g（X，Y），N（X，Y）]這種方法主要根據(jù)一點與其周圍各點的平均關系來定閥值，所以只適合于噪聲變化平緩的圖象。動態(tài)閥值選擇：IT=T[（X，Y），N（X，Y），g（X，Y）]該方法的要點是通過對象素的灰度的反復調(diào)整，修改直方圖，使谷點清晰或單峰變雙峰。2024/11/9二.平滑處理對于二值化后的圖象，由于噪聲的干擾，會存在一些黑白的孤立點和邊緣上的凹凸點。1.除孤立點外，用九點窗掃描，用邏輯式：若周圍8個點為“0”,掃描點為“1”則把掃描點由“1”

→“0”。若周圍8個點為“1”,掃描點為“0”則把掃描點由“0”→“1”。

abcdefghi2024/11/92.除邊緣凹凸點：除凸點的四種情況邏輯式

:

中心點由“1”→“0”

00

01

00

010000

00

10

00000010

2024/11/9補凹點：四種情況

1

10

1

101

1

1

01

1

1

101

2024/11/9三.細化處理

因為各種字符筆畫粗細不同為抽取特征方便和減小信息量，希望把筆畫寬度減小到一個象素的寬度，這樣字符筆畫就變成一個骨架，消除了筆畫粗細對識別的影響。細化的方法很多，我們介紹的方法是逐漸去掉文字的邊緣點。方法：用3X3輔助矩陣去順序掃描文字點陣的每個點，應用細化邏輯來判斷所掃描的每個點應除掉還是保留。

2024/11/9細化邏輯設計規(guī)則:（1）按上-下-左-右順序去掉邊緣點第一次掃描只去掉上邊緣點第二次掃描只去掉下邊緣點第三次掃描只去掉左邊緣點第四次掃描只去掉右邊緣點

上邊緣點下邊緣點左邊緣點右邊緣點

0

1

1

0

01

10

2024/11/9（2）不能使筆畫斷線，應保留連點（3）保留端點

0

1

1

1

0

1

010

1

0

111

0

1

0

1

0

10000100100100100000000110000001100000000101000000100010010100001000100002024/11/9（4）保留節(jié)點（三叉點，四叉點）

010111

0

01

11001

0

111010

10011

100101110101010101012024/11/9（5）保留左右角點

（6）保留上下角點

00011010000001100110011000000101100

0000101100000100110110100001100100002024/11/9根據(jù)以上規(guī)則，可以編制軟件程序也可以設計硬件邏輯電路，經(jīng)多次掃描細化就只剩下字符骨架了。如圖1-4所示。

圖1-4文字經(jīng)過平滑和細化變化情況2024/11/9四.跟蹤和抽取特征

1.跟蹤規(guī)則

（1）跟蹤從任一端點開始每個端點只抽一次特征（2）按逆時針方向（）沿骨架移動一周，直到重新回到原端點。（3）跟蹤方向的先后順序由下列辦法確定。上次跟蹤方向，檢查下次跟蹤方向的先后次序

2024/11/9例如。上次跟蹤方向是f7，下次跟蹤次序為：

D6D5D8D7D1D300000111111f6

f5f8

f7

f1

f3

d5d4d3d6d9d2d7d8d1f1

f2

f3

f4

f5

f6

f7

f82024/11/92.抽特征：每跟蹤一步就要抽取方向特征，凹凸特征和分支特征。下面對這三種特征詳細討論。（1）方向特征：按f1→f8共8個跟蹤方向可獲得8個方向特征。（2）線特征：包括凹凸平三種特征方向增量Δf定義如下：x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

Δf=0

Δf=+1Δf=+2Δf=-1Δf=-22024/11/9凹凸平定義狀態(tài)圖：凹：Δf=-2連續(xù)兩個Δf=-1凸：Δf=+2連續(xù)兩個Δf=+1平：Δf=0+1，+2[凸]+2[凸]0[平]0+—0[平]+1[平]0[平]+1[平]+2[凸]-1[平]-2[凹]-1[平]-2[凹]-1，-2[凹]2024/11/9（3）分支特征（點特征）

包括端點，三叉點，四叉點，連點

X=1時，d9

為端點

X=2時，d9

為三叉點

X=3時，d9

為四叉點

X=4時，d9

為連點

101011101三叉點規(guī)定8＋1＝12024/11/9例如：d1=d2=d3=d5=d7=d9=12024/11/9四.分類判決

采用序貫分類方法：跟蹤一步抽取方向特征，點特征，