1、1北京航空航天大學(xué)儀器科學(xué)與光電工程學(xué)院School of Instrumentation Science & Optoelectronics Engineering數(shù)字圖像處理Digital Image Processing2第十二章 目標(biāo)識(shí)別312.1 模式和模式類(lèi)4模式是描繪子的組合，如第11章中討論的那些描繪子。在模式識(shí)別中經(jīng)常使用特征來(lái)表示描繪子。模式類(lèi)是指具有某些共同屬性的一族模式。模式類(lèi)用1, 2, , W表示，其中W是模式類(lèi)數(shù)。由機(jī)器完成的模式識(shí)別是對(duì)不同的模式賦予不同類(lèi)別的技術(shù)，這種技術(shù)是自動(dòng)的，并且盡可能地減少人的干預(yù)。 5實(shí)踐中常用的三種模式組合是向量（用于定量描述）、串

2、和樹(shù)（用于結(jié)構(gòu)描述）。模式向量由粗體小寫(xiě)字母表示，如x,y和z，并采取下列形式：其中，每個(gè)分量xi表示第i個(gè)描繪子，n是與該模式有關(guān)的描繪子的總數(shù)。6模式向量以列向量（即n1階矩陣）形式表示。因此，模式向量可以表示為上式所示的形式或用等價(jià)形式x(x1, x2, , xn)T來(lái)表示，其中T表示轉(zhuǎn)置。模式向量x中的各個(gè)分量的性質(zhì)，取決于用于描述該物理模式本身的方法。下面我們使用一個(gè)簡(jiǎn)單的例子來(lái)加以說(shuō)明。這個(gè)例子不僅簡(jiǎn)單，而且給出了分類(lèi)度量的歷史意義。7在一篇經(jīng)典的論文中，F(xiàn)isher1936使用一種后來(lái)被稱為判別分析的技術(shù)，識(shí)別了三種鳶（音： yun）尾花(Iris setosa，Iris vir

3、ginica和Iris versicolor)，方法是測(cè)量花瓣的寬度和長(zhǎng)度。在當(dāng)前術(shù)語(yǔ)中，每種花由兩個(gè)度量來(lái)描述，從而生成了形如 的一個(gè)二維模式，其中x1和x2分別代表花瓣的長(zhǎng)度和寬度。8山鳶尾、維珍尼亞鳶尾、變色鳶尾Iris setosa山鳶尾Iris virginica維珍尼亞鳶尾Iris versicolor變色鳶尾由兩個(gè)度量描述的三種鳶尾花910在這種情形下，表示為w1, w2和w3的3個(gè)模式類(lèi)分別對(duì)應(yīng)于Iris setosa（山鳶尾）， Iris virginica（維珍尼亞鳶尾）和Iris versicolor（變色鳶尾）三種花。由于花瓣在寬度和長(zhǎng)度上的不同，描述這些花的模式向量也

4、會(huì)不同，這種不同不僅體現(xiàn)在不同的類(lèi)之間，也體現(xiàn)在一個(gè)類(lèi)的內(nèi)部。上圖顯示了每種鳶尾屬花的幾個(gè)樣本的長(zhǎng)度和寬度度量。11在選定了一組度量后（本例子中為兩個(gè)度量），模式向量的分量便成為每個(gè)物理樣本的完整描述。這種情形下的每朵花就成為二維歐氏空間中的一個(gè)點(diǎn)。本例中花瓣的長(zhǎng)度和寬度較好地分離了Iris setosa（山鳶尾）與其他兩種花，但I(xiàn)ris virginica （維珍尼亞鳶尾）和Iris versicolor （變色鳶尾）的分離并不成功。這一結(jié)果說(shuō)明了經(jīng)典的特征選擇問(wèn)題，即類(lèi)的可分程度在很大程度上取決于所用的描繪子的選擇。12下圖顯示了模式向量生成的另一個(gè)例子。在該例中，我們關(guān)注的是不同類(lèi)型的噪

5、聲波形，其中一個(gè)樣本示于下圖(a)。如果我們選擇用其信號(hào)的標(biāo)記圖（見(jiàn)11.1.5節(jié)）來(lái)表示每個(gè)目標(biāo)，則會(huì)得到圖(b)所示形式的一維信號(hào)。一個(gè)帶有噪聲的目標(biāo)及其相應(yīng)的信號(hào)1314假設(shè)我們用其取樣后的幅度值來(lái)描述每個(gè)信號(hào)；也就是說(shuō)，我們以指定的間隔值q對(duì)信號(hào)進(jìn)行取樣（表示為q1, q 2, , qn）。然后，我們通過(guò)令x1r(q1), x2r(q2), xnr(qn)，可構(gòu)成模式向量。這些向量成為n維歐氏空間中的點(diǎn)，并且模式類(lèi)可以想象為n維空間中的“云團(tuán)”。 15替代直接使用信號(hào)的幅度，我們可以計(jì)算一個(gè)給定信號(hào)的前n個(gè)統(tǒng)計(jì)矩（見(jiàn)11.2.4節(jié)），并使用這些描繪子作為每個(gè)模式向量的分量。事實(shí)上，生成

6、模式向量的其他方法還有許多種。目前，應(yīng)記住的關(guān)鍵概念是模式向量中每個(gè)分量的描繪子的選擇，描述子對(duì)基于模式向量方法的目標(biāo)識(shí)別的最終性能會(huì)有深刻的影響。16剛才描述的用于生成模式向量的技術(shù)，可得到由定量信息表征的模式類(lèi)。在某些應(yīng)用中，模式特性可由結(jié)構(gòu)關(guān)系來(lái)很好地描述。例如，指紋識(shí)別基于痕跡特性的相互關(guān)系，這種相互關(guān)系稱為細(xì)節(jié)。與它們的相對(duì)尺寸和位置一起，這些特性是描述指紋脊線特性的主要分量，如指紋的斷點(diǎn)、分支、合并和不連續(xù)線段。17這類(lèi)識(shí)別問(wèn)題通常用結(jié)構(gòu)的方法會(huì)得到很好解決，因?yàn)檫@種問(wèn)題不僅定量度量每種特性，而且這些特性間的空間關(guān)系決定了類(lèi)別的成員。這里，我們從模式描繪子的意義上，再次對(duì)其進(jìn)行簡(jiǎn)單

7、介紹。18下圖(a)顯示了一個(gè)簡(jiǎn)單的階梯模式。該模式可以如上圖中的方法被取樣并表示為一個(gè)模式向量。然而，如果采用這種描述方法，那么由兩個(gè)簡(jiǎn)單的主要元素重復(fù)而組成的基本結(jié)構(gòu)將會(huì)丟失。一種更有意義的描述方法是定義元素a和b，并將該模式定義為如下圖(b)所示的串wabababab。19在這種描述中，該特殊模式類(lèi)的結(jié)構(gòu)是按如下方式得到的：以首尾相連的方式定義連接性，且只允許符號(hào)交替。這種結(jié)構(gòu)組成適用于任何長(zhǎng)度的階梯，但排除了由基元a和b的其他組合生成其他類(lèi)型的結(jié)果。20(a) 階梯結(jié)構(gòu)；(b) 使用基元a和b對(duì)結(jié)構(gòu)編碼，生成串描述ababab21建筑物密集的城市中心區(qū)（華盛頓特區(qū)）和周?chē)用駞^(qū)的衛(wèi)星圖

8、像22樹(shù)形描述串描述適于生成其結(jié)構(gòu)是基于基元的較簡(jiǎn)單的連接，并且通常是和邊界形狀有關(guān)系的目標(biāo)模式和其他實(shí)體模式。對(duì)許多應(yīng)用來(lái)說(shuō)，一種更有效的方法是使用樹(shù)形描述?；旧希鄶?shù)層次排序方案都會(huì)導(dǎo)致樹(shù)結(jié)構(gòu)。23例如，下圖顯示了建筑物密集的市區(qū)和周?chē)用駞^(qū)的一幅衛(wèi)星圖像。我們使用符號(hào)$來(lái)定義整個(gè)圖像區(qū)域。下圖中（從上到下）顯示的樹(shù)形表示是通過(guò)使用結(jié)構(gòu)關(guān)系“由組成”得到的。因此，樹(shù)的根表示整幅圖像。24下一層表示該圖像由市區(qū)和居民區(qū)構(gòu)成。居民區(qū)依次由住宅、高速公路和購(gòu)物中心構(gòu)成。再下一層描述住宅和高速公路。我們可以繼續(xù)按這樣的方式細(xì)分，直到達(dá)到我們?cè)趫D像上解析不同區(qū)域的能力的極限為止。25建筑物密集的城

9、市中心區(qū)（華盛頓特區(qū)）和周?chē)用駞^(qū)的衛(wèi)星圖像的樹(shù)形描述2612.2 基于決策理論方法的識(shí)別27決策理論方法識(shí)別是以使用決策（或判別）函數(shù)為基礎(chǔ)的。令x(x1,x2,xn)T表示一個(gè)n維模式向量。對(duì)于W個(gè)模式類(lèi)1,2,W，決策理論模式識(shí)別的基本問(wèn)題是依據(jù)如下屬性來(lái)找到W個(gè)決策函數(shù)d1(x), d2(x), dW(x)：如果模式x屬于類(lèi)i，則：28換句話說(shuō)，將x代入所有決策函數(shù)后，如果di(x)得到最大值，則稱未知模式x屬于第i個(gè)模式類(lèi)。從類(lèi)j中分離出類(lèi)i的決策邊界，由滿足di(x)dj(x)的x值給出，或等價(jià)地由di(x)dj(x)0的x值給出。通常使用單一函數(shù)dij(x)di(x)dj(x)0

10、來(lái)識(shí)別兩類(lèi)之間的決策邊界。因此，對(duì)于模式類(lèi)i有dij(x)0，而對(duì)于模式類(lèi)j有dij(x)0。2912.2.1 匹配本節(jié)的主要目的是探討尋找滿足下式的決策函數(shù)的各種方法?；谄ヅ涞淖R(shí)別技術(shù)通過(guò)一個(gè)原型模式向量來(lái)表示每個(gè)類(lèi)。根據(jù)一種預(yù)先定義的度量，將一個(gè)未知模式賦予最接近的類(lèi)。30最簡(jiǎn)單的方法是最小距離分類(lèi)器，如其名稱所示，最小距離分類(lèi)器計(jì)算該未知模式與每個(gè)原型向量間的（歐氏）距離。它選擇最小距離來(lái)決策。我們還將探討一種基于相關(guān)的方法，該方法可根據(jù)圖像用公式來(lái)直接表達(dá)，因此相當(dāng)直觀。31最小距離分類(lèi)器假設(shè)我們把每個(gè)模式類(lèi)的原型定義為該類(lèi)模式的平均向量：其中，Nj是來(lái)自j類(lèi)模式向量的數(shù)量，求和操作

11、是對(duì)所有這些向量執(zhí)行的。如以前那樣，W是模式類(lèi)的數(shù)量。如前所述，求未知模式向量x的類(lèi)成員的一種方法是，將它賦給其最接近的原型類(lèi)。32使用歐氏距離求接近程度可將該問(wèn)題簡(jiǎn)化為計(jì)算如下距離度量：Dj(x) j1,2,W其中， (aTa)1/2是歐幾里得范數(shù)。若Di(x)是最小距離，則把x賦給類(lèi)i。也就是說(shuō)，最小距離意味著該式表示最好的匹配?？梢宰C明，選擇最小距離等同于計(jì)算函數(shù)： j1,2,W 33并在di(x)獲得最大數(shù)值時(shí)，將x劃歸類(lèi)i。該式與 中 定義的決策函數(shù)的概念是一致的。由式di(x)dj(x)0和式 ，對(duì)于一個(gè)最小距離分類(lèi)器，類(lèi)i和類(lèi)j之間的決策邊界為：dij(x)di(x)dj(x)3

12、4由上式給出的決策面是連接mi和mj的線段的垂直等分線。對(duì)于由x(x1,x2,xn)T表示的一個(gè)n維模式向量，當(dāng)n2時(shí)，垂直等分線是一條直線；n3時(shí)，它是一個(gè)平面；n3時(shí)，稱其為一個(gè)超平面。 35最小距離分類(lèi)器的說(shuō)明下圖顯示了鳶尾屬植物例子中提取的兩個(gè)模式類(lèi)。兩個(gè)模式類(lèi)Iris versicolor（變色鳶尾）和Iris setosa（山鳶尾）分別表示為1和2，其樣本均值向量為m1(4.3, 1.3)T和m2(1.5, 0.3)T。由式 可知，決策函數(shù)為：36由dij(x)di(x)dj(x) 可知邊界方程為： d12(x)d1(x)d2(x)2.8x11.0 x28.90下圖顯示了該邊界的圖

13、形。代入來(lái)自類(lèi)1的任何模式向量，都會(huì)得到d12(x)0。相反，代入來(lái)自類(lèi)2的任何模式向量，都會(huì)得到d12(x)0。給定一個(gè)屬于這兩個(gè)類(lèi)之一的未知模式，d12(x)的符號(hào)將足以確定該模式的歸屬。37類(lèi)Iris versicolor（變色鳶尾）和類(lèi)Iris setosa（山鳶尾）的最小距離分類(lèi)器的決策邊界。圖中紅色的小方塊和小圓分別是類(lèi)的均值。38實(shí)際上，就每個(gè)類(lèi)的均值而言，當(dāng)均值間的距離與每個(gè)類(lèi)的分散度或隨機(jī)性相比較大時(shí)，最小距離分類(lèi)器工作得很好。當(dāng)每個(gè)類(lèi)關(guān)于其均值的分布在n維模式空間中表現(xiàn)為一種球形的“超云團(tuán)”形式時(shí)，最小距離分類(lèi)器（在最小化錯(cuò)誤分類(lèi)的平均損失方面）會(huì)產(chǎn)生最佳性能。實(shí)際中，很少

14、同時(shí)出現(xiàn)較大的均值分離和相對(duì)較小的散布，除非系統(tǒng)設(shè)計(jì)人員能控制輸入的性質(zhì)。39美國(guó)銀行家協(xié)會(huì)E138字符集和對(duì)應(yīng)的波形40針對(duì)這一應(yīng)用設(shè)計(jì)一個(gè)最小距離分類(lèi)器相當(dāng)簡(jiǎn)單。我們只需要存儲(chǔ)每個(gè)波形的樣本值，然后將每組樣本表示為一個(gè)原型向量mj, j1, 2, , 14。當(dāng)對(duì)一個(gè)未知字符進(jìn)行分類(lèi)時(shí)，方法是使用單縫讀取頭來(lái)水平掃描字符，將波形的網(wǎng)格樣本表示為一個(gè)向量x。41然后依據(jù)式 得到的最高值選擇原型向量的類(lèi)。該類(lèi)即為該原型向量所屬的類(lèi)。使用由一組電阻器組成的模擬電路可實(shí)現(xiàn)高速分類(lèi)。相關(guān)匹配我們使用如下的歸一化相關(guān)系數(shù)：其中，求和的上下限取w和f的共同范圍， 是模板的平均值（只計(jì)算一次）， 是f中與w

15、重合區(qū)域的平均值。42通常，我們將w稱為模板，而將相關(guān)稱為模板匹配。(x,y)的值域?yàn)?, 1，因而f和w的幅度變化是歸一化的。當(dāng)歸一化的w和f中對(duì)應(yīng)的歸一化區(qū)域相同時(shí)， (x,y)出現(xiàn)最大值。這說(shuō)明了最大相關(guān)（即最好可能的匹配）。當(dāng)兩個(gè)歸一化函數(shù)在式 的意義下表現(xiàn)出最小相似性時(shí)，會(huì)出現(xiàn)最小值。43下圖說(shuō)明了剛才討論的步驟的機(jī)理。如3.4.2節(jié)中解釋的那樣，當(dāng)w的中心位于f的邊界上時(shí)，圍繞f的邊界需要進(jìn)行填充（在模板匹配中，當(dāng)模板的中心越過(guò)圖像的邊界時(shí)，相關(guān)的值通常并不重要，因此填充被限制為模板寬度的一半）。為表示方便，我們通常只關(guān)心奇數(shù)大小的模板。44下圖顯示了一個(gè)大小為mn的模板，其中心位

16、于任意位置(x,y)。在這一點(diǎn)的相關(guān)可以用下式 得到。然后，該模板的中心移到一個(gè)相鄰位置，重復(fù)該過(guò)程。45通過(guò)移動(dòng)該模板的中心（即增大x和y），以便w的中心訪問(wèn)f中的每個(gè)像素，可得到所有的相關(guān)系數(shù)(x,y)。在該過(guò)程的最后，我們尋找(x,y)中的最大值，從而找到出現(xiàn)最好匹配的位置。在(x,y)中可能會(huì)有多個(gè)位置出現(xiàn)最大值，此時(shí)表明w和f之間有多個(gè)匹配。46模板匹配的機(jī)理47舉例 用相關(guān)進(jìn)行匹配下圖(a)顯示了一幅大小為913913的颶風(fēng)衛(wèi)星圖像，其中暴風(fēng)眼清晰可見(jiàn)。作為相關(guān)的一個(gè)例子，我們希望找到下圖(b)中的模板在圖(a)中最好匹配的位置，模板是暴風(fēng)眼的一幅較小的（3131）子圖像。下圖(c)顯示了由歸一化相關(guān)系數(shù)公式計(jì)算的相關(guān)系數(shù)