DIP12 對象識(shí)別

1、北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東數(shù)字圖像處理數(shù)字圖像處理Digital Image Processing信息與通信工程學(xué)院多媒體技術(shù)中心信息與通信工程學(xué)院多媒體技術(shù)中心第十二第十二章章 目標(biāo)識(shí)別目標(biāo)識(shí)別Object Recognition門愛東教授門愛東教授北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BU

2、PT2目標(biāo)識(shí)別目標(biāo)識(shí)別n本章闡述的本章闡述的目標(biāo)（或模式）識(shí)別目標(biāo)（或模式）識(shí)別方法主要分為兩大領(lǐng)域：方法主要分為兩大領(lǐng)域：決決策理論策理論和和結(jié)構(gòu)判別結(jié)構(gòu)判別。n決策理論方法：決策理論方法：此類方法處理的是使用此類方法處理的是使用定量描繪子定量描繪子來描述的各種模來描述的各種模式，定量描繪子包括長度、面積和紋理等。式，定量描繪子包括長度、面積和紋理等。n結(jié)構(gòu)判別方法結(jié)構(gòu)判別方法：此類方法處理的是由：此類方法處理的是由定性描繪子定性描繪子描述的各種模式，描述的各種模式，如前面討論過的關(guān)系描繪子。如前面討論過的關(guān)系描繪子。n識(shí)別的核心問題是識(shí)別的核心問題是通過樣本模式進(jìn)行通過樣本模式進(jìn)行 “學(xué)習(xí)

3、學(xué)習(xí)” 這一概念。這一概念。這個(gè)世界有趣的一面是可以把它看成由各種模式組這個(gè)世界有趣的一面是可以把它看成由各種模式組成的，模式本質(zhì)上是一種排列，它是由元素順序而不是成的，模式本質(zhì)上是一種排列，它是由元素順序而不是這些元素固有性質(zhì)來表征的。這些元素固有性質(zhì)來表征的。 - 諾伯特諾伯特 . 維納維納北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT3本章內(nèi)容本章內(nèi)容 Out

4、linesn模式和模式類模式和模式類n基于決策理論方法的識(shí)別基于決策理論方法的識(shí)別n結(jié)構(gòu)性方法結(jié)構(gòu)性方法北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT4 模式和模式類模式和模式類n模式模式是是描繪子描繪子的組合。的組合。n前面討論過的那些描繪子；前面討論過的那些描繪子；n在在 模式識(shí)別的文獻(xiàn)中，長使用模式識(shí)別的文獻(xiàn)中，長使用“特征特征”來表示描繪子。來表示描繪子。n

5、模式類模式類是指具有某些共同屬性的是指具有某些共同屬性的一族模式一族模式，一般用，一般用 1、2、.W 表示，其中表示，其中 W 是模式類的數(shù)量。是模式類的數(shù)量。n實(shí)踐中，常用的三種實(shí)踐中，常用的三種模式組合模式組合是模式是模式向量向量（用于定量描（用于定量描述）、述）、字符串字符串和和樹樹（用于結(jié)構(gòu)描述）。（用于結(jié)構(gòu)描述）。n模式向量用粗體小寫字母表示，比如模式向量用粗體小寫字母表示，比如 x x, y y 和和 z z，并采用，并采用如下的列向量如下的列向量 (即即 n1 階矩陣）的形式表示：階矩陣）的形式表示： 其中，每個(gè)分量其中，每個(gè)分量 xi 表示第表示第 i 個(gè)描繪子；個(gè)描繪子；n

6、 是與該模式有關(guān)的描繪是與該模式有關(guān)的描繪子的總數(shù)；子的總數(shù)；T 表示轉(zhuǎn)置。表示轉(zhuǎn)置。 12,.Tnx xx x x北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT5 模式和模式類模式和模式類n模式向量模式向量 x x 中中各個(gè)分量的性質(zhì)各個(gè)分量的性質(zhì)取決于用于描述該物理模式取決于用于描述該物理模式自身的方法。下面用一個(gè)簡單的例子來說明并給出分類度量自身的方法。下面用

7、一個(gè)簡單的例子來說明并給出分類度量的歷史意義。的歷史意義。n在在 Fisher1936 發(fā)表的經(jīng)典論文中，提出了后來被稱為發(fā)表的經(jīng)典論文中，提出了后來被稱為判別判別分析分析的算法，它通過測量花瓣的的算法，它通過測量花瓣的寬度寬度和和長度，長度，識(shí)別了三種鳶識(shí)別了三種鳶(yuan) 尾花尾花 (Iris Setosa, Iris Virginica 和和 Iris Versicolor)。n每種花由兩個(gè)度量描述，這生成了如下的二維模式向量：每種花由兩個(gè)度量描述，這生成了如下的二維模式向量：nx1 和和 x2 分別代表花瓣的長度和寬度分別代表花瓣的長度和寬度n在此，表示為在此，表示為 1、2、3

8、的的 3 個(gè)模式類分別對應(yīng)個(gè)模式類分別對應(yīng)山鳶尾山鳶尾 (Iris setosa)、維吉尼亞鳶尾、維吉尼亞鳶尾 (Iris virginica) 和變色鳶尾和變色鳶尾 (Iris versicolor) 三三種花。種花。12xx x x北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT6模式和模式類模式和模式類用兩個(gè)度量描述的三種鳶尾花用兩個(gè)度量描述的三種鳶尾花n本例中

9、，本例中，花瓣長度和寬度能較花瓣長度和寬度能較好地把好地把Setosa與其它兩種花區(qū)與其它兩種花區(qū)分開來分開來，但對，但對Virginica和和Versi color 的分離效果不佳。的分離效果不佳。n這一結(jié)果說明了這一結(jié)果說明了經(jīng)典的特征選經(jīng)典的特征選擇問題擇問題，即類的可分程度在很，即類的可分程度在很大程度上取決于所用描繪子的大程度上取決于所用描繪子的選擇。后面對此進(jìn)行更多的闡選擇。后面對此進(jìn)行更多的闡述。述。n由于花瓣在寬度和長度上的不同，描述這些花的模式向量也由于花瓣在寬度和長度上的不同，描述這些花的模式向量也會(huì)不同會(huì)不同，這種不同不僅存在于不同種類的花瓣之間，在同一，這種不同不僅存在

10、于不同種類的花瓣之間，在同一種類的花瓣間也存在。種類的花瓣間也存在。n在選定了一組度量后（本例中為長度和寬度），模式向量的在選定了一組度量后（本例中為長度和寬度），模式向量的分量便成為每個(gè)物理樣本的完整描述。因此，每朵花就由二分量便成為每個(gè)物理樣本的完整描述。因此，每朵花就由二維歐氏空間中的一個(gè)點(diǎn)代表。維歐氏空間中的一個(gè)點(diǎn)代表。北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre,

11、BUPT7模式和模式類模式和模式類一個(gè)噪聲目標(biāo)及其對應(yīng)的信號一個(gè)噪聲目標(biāo)及其對應(yīng)的信號n下圖顯示了另一個(gè)生成模式向量的例子下圖顯示了另一個(gè)生成模式向量的例子。在該例中，關(guān)注的。在該例中，關(guān)注的是不同類型的噪聲波形，其中一個(gè)樣本示于圖是不同類型的噪聲波形，其中一個(gè)樣本示于圖 (a) 中。如果中。如果選擇用噪聲信號代表每個(gè)目標(biāo)，會(huì)得到圖選擇用噪聲信號代表每個(gè)目標(biāo)，會(huì)得到圖 (b) 所示的一維信所示的一維信號。號。n假設(shè)用取樣后的幅度值來描述每個(gè)信號假設(shè)用取樣后的幅度值來描述每個(gè)信號，即以指定的角度間，即以指定的角度間隔值隔值 對信號進(jìn)行取樣，然后通過令對信號進(jìn)行取樣，然后通過令 x1= r(1)，

12、 x2= r(2),., xn = r(n)，可構(gòu)成模式向量。，可構(gòu)成模式向量。n這些向量成為這些向量成為 n 維歐幾里得空間中的點(diǎn)，并且模式類可以想維歐幾里得空間中的點(diǎn)，并且模式類可以想象成象成 n 維空間中的維空間中的“云團(tuán)云團(tuán)”。(a)(b)北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT8模式和模式類模式和模式類n實(shí)際上，實(shí)際上，還有很多其它方法生成模式向量還

13、有很多其它方法生成模式向量，本章中將介紹，本章中將介紹其中的一些方法。其中的一些方法。n例如，計(jì)算給定信號的前例如，計(jì)算給定信號的前 n 個(gè)統(tǒng)計(jì)矩，代替前述的信號幅度，作為個(gè)統(tǒng)計(jì)矩，代替前述的信號幅度，作為描繪子來生成每個(gè)模式向量的分量。描繪子來生成每個(gè)模式向量的分量。n應(yīng)記住的應(yīng)記住的關(guān)鍵概念關(guān)鍵概念是：模式向量中每個(gè)分量描繪子的選擇，是：模式向量中每個(gè)分量描繪子的選擇，描繪子對基于模式向量方法的目標(biāo)識(shí)別的最終性能有很大描繪子對基于模式向量方法的目標(biāo)識(shí)別的最終性能有很大影響。影響。n上述描述的用于生成模式向量的技術(shù)，可得到由定量信息上述描述的用于生成模式向量的技術(shù)，可得到由定量信息表征的模式

14、類。表征的模式類。n在某些應(yīng)用中，模式特性可由在某些應(yīng)用中，模式特性可由結(jié)構(gòu)關(guān)系結(jié)構(gòu)關(guān)系很好地描述很好地描述。n例如，指紋識(shí)別基于痕跡特性的相互關(guān)系（稱為例如，指紋識(shí)別基于痕跡特性的相互關(guān)系（稱為細(xì)節(jié)細(xì)節(jié)），與它們的），與它們的相對大小和位置一起，這些特性是描述指紋脊線特性的主要分量，相對大小和位置一起，這些特性是描述指紋脊線特性的主要分量，如指紋的斷點(diǎn)、分支、合并和不連續(xù)線段。如指紋的斷點(diǎn)、分支、合并和不連續(xù)線段。n這類識(shí)別問題常用結(jié)構(gòu)方法解決這類識(shí)別問題常用結(jié)構(gòu)方法解決，因?yàn)檫@類問題不僅定量度量每種，因?yàn)檫@類問題不僅定量度量每種特性，而且這些特性間的空間關(guān)系決定了類別的成員。特性，而且這些

15、特性間的空間關(guān)系決定了類別的成員。北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT9模式和模式類模式和模式類n結(jié)構(gòu)描繪子組合的模式舉例結(jié)構(gòu)描繪子組合的模式舉例n下圖下圖 (a) 顯示了一個(gè)簡單的階梯模式，如上例噪聲所示，可以對該顯示了一個(gè)簡單的階梯模式，如上例噪聲所示，可以對該模式進(jìn)行角度取樣，并表示為一個(gè)向量模式。然而，用這種向量模模式進(jìn)行角度取樣，并表示為一個(gè)向量

16、模式。然而，用這種向量模式方法將無法表示由兩個(gè)簡單的主要元素式方法將無法表示由兩個(gè)簡單的主要元素 a、b 重復(fù)而組成的基本重復(fù)而組成的基本階梯結(jié)構(gòu)。階梯結(jié)構(gòu)。n一種更好的一種更好的描述方法描述方法是定義元素是定義元素 a 和和 b，并將模式定義為圖，并將模式定義為圖 (b) 所所示的示的字符串字符串 w=.abababab.。n生成方法：以首尾相連的方式定義連接性，且只允許符號交替。生成方法：以首尾相連的方式定義連接性，且只允許符號交替。n這種結(jié)構(gòu)組成適用于任何長度的階梯，但排除了由基元這種結(jié)構(gòu)組成適用于任何長度的階梯，但排除了由基元 a 和和 b 的其它組的其它組合生成其它類型的結(jié)果。合生成

17、其它類型的結(jié)果。n串描述適于生成其結(jié)構(gòu)是基于串描述適于生成其結(jié)構(gòu)是基于基元的較簡單的連接基元的較簡單的連接，并且通，并且通常是和邊界形狀有關(guān)系的目標(biāo)常是和邊界形狀有關(guān)系的目標(biāo)模式和其它實(shí)體模式。模式和其它實(shí)體模式。北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT10模式和模式類模式和模式類n對許多應(yīng)用來說，對許多應(yīng)用來說，更有效的方法是樹形描述更有效的方法是樹形描述。

18、n基本上，多數(shù)層次排序方式都會(huì)導(dǎo)致樹形結(jié)構(gòu)基本上，多數(shù)層次排序方式都會(huì)導(dǎo)致樹形結(jié)構(gòu)。n例如，下圖顯示了一幅建筑物稠密的市區(qū)和周圍居民區(qū)的衛(wèi)星圖像。例如，下圖顯示了一幅建筑物稠密的市區(qū)和周圍居民區(qū)的衛(wèi)星圖像。有稠密建筑物的城市中心區(qū)及周圍居民區(qū)的衛(wèi)星照片有稠密建筑物的城市中心區(qū)及周圍居民區(qū)的衛(wèi)星照片北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT11模式和模式類模式和模

19、式類n下圖中下圖中 (從上到下從上到下) 顯示的樹形表示是顯示的樹形表示是通過使用結(jié)構(gòu)關(guān)系通過使用結(jié)構(gòu)關(guān)系“由由.組成組成” 得到的。得到的。n樹的根節(jié)點(diǎn)代表整幅圖像，使用符號樹的根節(jié)點(diǎn)代表整幅圖像，使用符號 $ 表示整個(gè)圖像區(qū)域；表示整個(gè)圖像區(qū)域；n下一級的節(jié)點(diǎn)表示該圖像由城區(qū)和居民區(qū)組成；下一級的節(jié)點(diǎn)表示該圖像由城區(qū)和居民區(qū)組成；n居民區(qū)依次由住宅、商業(yè)區(qū)和高速公路構(gòu)成；居民區(qū)依次由住宅、商業(yè)區(qū)和高速公路構(gòu)成；n再下一級描述住宅和告訴公路；再下一級描述住宅和告訴公路；n可以繼續(xù)按此細(xì)分，直至達(dá)到圖像不同區(qū)域的解析能力極限為止?？梢岳^續(xù)按此細(xì)分，直至達(dá)到圖像不同區(qū)域的解析能力極限為止。北京郵

20、電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT12本章內(nèi)容本章內(nèi)容n模式和模式類模式和模式類n基于決策理論方法的模式識(shí)別基于決策理論方法的模式識(shí)別n匹配匹配n最佳統(tǒng)計(jì)分類器最佳統(tǒng)計(jì)分類器n神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)n結(jié)構(gòu)性方法結(jié)構(gòu)性方法北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processin

21、g 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT13基于決策理論方法的模式識(shí)別基于決策理論方法的模式識(shí)別n決策理論模式識(shí)別方法決策理論模式識(shí)別方法是以決策（或判別）函數(shù)為基礎(chǔ)的。是以決策（或判別）函數(shù)為基礎(chǔ)的。n令令 x = (x1, x2, xn)T 表示一個(gè)表示一個(gè) n 維模式向量。對于維模式向量。對于 W 個(gè)模式個(gè)模式類類 1、2、.、W，決策理論模式識(shí)別的，決策理論模式識(shí)別的基本問題基本問題是依據(jù)是依據(jù)如下屬性找到如下屬性找到 W 個(gè)個(gè)決策決策(判別判別)函數(shù)函數(shù) d1(x)、d2(x)、dW(x) ，如

22、果模式如果模式 x 屬于類屬于類 i ，則，則 n上式表示：將上式表示：將 x 代入所有決策函數(shù)后，如果代入所有決策函數(shù)后，如果 di(x) 得到最大值，則稱得到最大值，則稱未知的模式未知的模式 x 屬于第屬于第 i 個(gè)模式類，該關(guān)系可以任意求解。個(gè)模式類，該關(guān)系可以任意求解。n從類從類 j 中分離出類中分離出類 i 的決策邊界的決策邊界，由滿足，由滿足 di(x)=dj(x) 的的 x 值給出，或等價(jià)地由值給出，或等價(jià)地由 di(x)-dj(x)=0 式中的式中的 x 值給出。值給出。n通常是使用單一函數(shù)通常是使用單一函數(shù) dij(x) = di(x) - dj(x) = 0 來識(shí)別兩個(gè)類之

23、間的決策來識(shí)別兩個(gè)類之間的決策（判別）邊界（判別）邊界。因此，對于模式類。因此，對于模式類 i ，有，有 dij(x) 0，而模式類，而模式類 j ，有有 dij(x) 3 時(shí)，是時(shí)，是一個(gè)超一個(gè)超平面平面。 12TTjjjjdxx mm m Wj,2, 1基于決策理論方法的識(shí)別基于決策理論方法的識(shí)別-匹配匹配-最小距離分類器最小距離分類器 102ijijTTijijijdxdxdxxmmmmmm 北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, M

24、ultimedia Telecommunication Centre, BUPT16n左圖顯示了從前述的鳶尾花中提左圖顯示了從前述的鳶尾花中提取的兩個(gè)模式類。取的兩個(gè)模式類。n兩個(gè)模式類兩個(gè)模式類 Iris Versicolor 和和Iris Setosa 分別表示為分別表示為 1 和和 2，樣，樣本均值向量為本均值向量為 m1=(4.3, 1.3)T 和和 m2=(1.5, 0.3)T。 n相應(yīng)的相應(yīng)的決策函數(shù)決策函數(shù)是：是：n由此得出由此得出邊界方程邊界方程為：為：n左圖顯示了該邊界的圖形左圖顯示了該邊界的圖形（注意（注意軸的比例不同）。軸的比例不同）。n最小距離分類器的舉例最小距離分類器

25、的舉例 111112124.31.310.1TTdxx mm mxx 122222121.50.31.17TTdxx mm mxx 基于決策理論方法的識(shí)別基于決策理論方法的識(shí)別-匹配匹配-最小距離分類器最小距離分類器 1212122.81.08.90dxdxdxxx 任何來自類任何來自類 1 的的模式向量代入邊界模式向量代入邊界方程，都會(huì)得到方程，都會(huì)得到 d12(x) 0。相反，任。相反，任何來自類何來自類 2 的的模式向量代入邊界方模式向量代入邊界方程，都會(huì)得到程，都會(huì)得到 d12(x) 0。根據(jù)根據(jù) d12(x) 的符號將足以確定未知模式的歸屬。的符號將足以確定未知模式的歸屬。12北京郵

26、電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT17n實(shí)際上，當(dāng)每個(gè)類均值之間的距離與每個(gè)類的分散度或隨機(jī)實(shí)際上，當(dāng)每個(gè)類均值之間的距離與每個(gè)類的分散度或隨機(jī)性相比較大時(shí)，性相比較大時(shí)，最小距離分類器工作得很好最小距離分類器工作得很好。n后面將證明：當(dāng)每個(gè)類的均值分布在后面將證明：當(dāng)每個(gè)類的均值分布在 n 維模式空間中呈現(xiàn)為維模式空間中呈現(xiàn)為一種球形的一種球形的“超云團(tuán)超云

27、團(tuán)”形式時(shí)，最小距離分類器會(huì)得到形式時(shí)，最小距離分類器會(huì)得到最佳最佳性能性能（在最小化錯(cuò)誤分類的平均損失方面）。（在最小化錯(cuò)誤分類的平均損失方面）。n實(shí)際中，很少同時(shí)出現(xiàn)較大的均值分離和相對較小的散布，實(shí)際中，很少同時(shí)出現(xiàn)較大的均值分離和相對較小的散布，除非系統(tǒng)設(shè)計(jì)人員能控制輸入的性質(zhì)。除非系統(tǒng)設(shè)計(jì)人員能控制輸入的性質(zhì)。基于決策理論方法的識(shí)別基于決策理論方法的識(shí)別-匹配匹配-最小距離分類器最小距離分類器n一個(gè)很好的例子就是設(shè)計(jì)用于讀取固定格式一個(gè)很好的例子就是設(shè)計(jì)用于讀取固定格式字符的系統(tǒng)；字符的系統(tǒng)；n例如，例如，美國銀行家協(xié)會(huì)美國銀行家協(xié)會(huì) E-13B 字符集，由字符集，由 14 個(gè)字符組

28、成個(gè)字符組成。n這些字符被特意設(shè)計(jì)在這些字符被特意設(shè)計(jì)在 97 的網(wǎng)格中以便于的網(wǎng)格中以便于讀取，并常用含有精細(xì)磁性材料的墨水印刷。讀取，并常用含有精細(xì)磁性材料的墨水印刷。n在讀取這些字符之前，對油墨施加一個(gè)磁場來在讀取這些字符之前，對油墨施加一個(gè)磁場來加重每個(gè)字符，以便簡化檢測，即人工地突出加重每個(gè)字符，以便簡化檢測，即人工地突出每個(gè)字符的關(guān)鍵特征，解決了分割問題。每個(gè)字符的關(guān)鍵特征，解決了分割問題。北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong,

29、 Multimedia Telecommunication Centre, BUPT18n美國銀行家協(xié)會(huì)美國銀行家協(xié)會(huì) E-13B 字符集字符集n通常使用單縫讀取頭水平掃描字符，讀取頭與字符相比要窄一些、通常使用單縫讀取頭水平掃描字符，讀取頭與字符相比要窄一些、長一些。長一些。n當(dāng)讀取頭橫向移動(dòng)一個(gè)字符時(shí)，會(huì)產(chǎn)生一個(gè)一維電信號，該電信號當(dāng)讀取頭橫向移動(dòng)一個(gè)字符時(shí)，會(huì)產(chǎn)生一個(gè)一維電信號，該電信號與讀取頭下方字符面積的增大率或減少率成正比。與讀取頭下方字符面積的增大率或減少率成正比。n例如，觀察圖中與字符例如，觀察圖中與字符 “0” 的波形。的波形。n當(dāng)讀取頭從左向右移動(dòng)時(shí)，當(dāng)讀取頭從左向右移動(dòng)時(shí)

30、，掃描到掃描到 0 左邊的豎杠左邊的豎杠，讀取頭看到的字符面，讀取頭看到的字符面積開始增大，從而產(chǎn)生一個(gè)正導(dǎo)數(shù)（正變化率）。當(dāng)讀取頭開始遠(yuǎn)離積開始增大，從而產(chǎn)生一個(gè)正導(dǎo)數(shù)（正變化率）。當(dāng)讀取頭開始遠(yuǎn)離 0 基于決策理論方法的識(shí)別基于決策理論方法的識(shí)別-匹配匹配-最小距離分類器最小距離分類器 左邊的豎杠時(shí)，讀取頭下方的面積開始減少，從而產(chǎn)左邊的豎杠時(shí)，讀取頭下方的面積開始減少，從而產(chǎn)生一個(gè)負(fù)導(dǎo)數(shù)；生一個(gè)負(fù)導(dǎo)數(shù)；n當(dāng)讀取頭位于當(dāng)讀取頭位于 0 的的中間區(qū)域中間區(qū)域時(shí)，掃過的面積幾乎不變，時(shí)，掃過的面積幾乎不變，從而產(chǎn)生零導(dǎo)數(shù)；從而產(chǎn)生零導(dǎo)數(shù)；n當(dāng)讀取頭掃到當(dāng)讀取頭掃到 0 的的右邊豎杠右邊豎杠時(shí)，

31、重復(fù)一次左邊的波形時(shí)，重復(fù)一次左邊的波形（模式）；（模式）；nE-13B 的設(shè)計(jì)確保了每個(gè)字符的波形是完全不同的，也的設(shè)計(jì)確保了每個(gè)字符的波形是完全不同的，也確保了每個(gè)波形的峰值和零值大致出現(xiàn)在背景網(wǎng)格的垂確保了每個(gè)波形的峰值和零值大致出現(xiàn)在背景網(wǎng)格的垂直線上。直線上。北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT19nE-13B 字符集具有的性質(zhì)：字符集具有的性質(zhì)

32、：僅在僅在這些點(diǎn)處對波形取樣，就可得到這些點(diǎn)處對波形取樣，就可得到實(shí)現(xiàn)正確分類所需的足夠信息。實(shí)現(xiàn)正確分類所需的足夠信息。n針對這一應(yīng)用，設(shè)計(jì)一個(gè)最小針對這一應(yīng)用，設(shè)計(jì)一個(gè)最小距離分類器是相當(dāng)簡單的。距離分類器是相當(dāng)簡單的。n只需要存儲(chǔ)每個(gè)波形的樣本值，只需要存儲(chǔ)每個(gè)波形的樣本值，然后將每組樣本表示為一個(gè)原型然后將每組樣本表示為一個(gè)原型向量向量 mj，j=1,2,14.n當(dāng)對一個(gè)未知字符進(jìn)行分類時(shí)，當(dāng)對一個(gè)未知字符進(jìn)行分類時(shí)，使用剛才的方式掃描它，將波形使用剛才的方式掃描它，將波形的網(wǎng)格樣本表示為一個(gè)向量的網(wǎng)格樣本表示為一個(gè)向量 x，然后計(jì)算然后計(jì)算 dj(x)，依據(jù)其最高值選，依據(jù)其最高值選

33、擇原型向量的類。擇原型向量的類。n使用一組電阻組成的模擬電路可使用一組電阻組成的模擬電路可實(shí)現(xiàn)高速分類。實(shí)現(xiàn)高速分類?；跊Q策理論方法的識(shí)別基于決策理論方法的識(shí)別-匹配匹配-最小距離分類器最小距離分類器北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT20基于決策理論方法的識(shí)別基于決策理論方法的識(shí)別-匹配匹配-相關(guān)匹配相關(guān)匹配n前面介紹過圖像相關(guān)的基本概念，并廣泛應(yīng)用于

34、空間濾波。前面介紹過圖像相關(guān)的基本概念，并廣泛應(yīng)用于空間濾波。n大小大小 mn 的模板的模板 w(x, y) 與圖像與圖像 f(x, y) 的的相關(guān)相關(guān)定義為：定義為： 其中，其中，求和的上下限取求和的上下限取 w 和和 f 的共同范圍的共同范圍，假設(shè)，假設(shè) f 范圍大于范圍大于 w。n相關(guān)定理相關(guān)定理 其中，其中， 表示空間相關(guān)，表示空間相關(guān)，F(xiàn)* 是是 F 的復(fù)共軛；的復(fù)共軛；n上式的反變換得到一個(gè)二維循環(huán)相關(guān)，并且上式的反變換得到一個(gè)二維循環(huán)相關(guān)，并且注意填充問題注意填充問題；n相關(guān)可以通過相關(guān)可以通過 FFT 算法在頻域中完成算法在頻域中完成，當(dāng)應(yīng)考慮模板當(dāng)應(yīng)考慮模板 w 的大小的大小

35、n若若 f 和和 w 大小相同，大小相同，F(xiàn)FT 比在空間域中直接計(jì)算相關(guān)更有效；比在空間域中直接計(jì)算相關(guān)更有效；n當(dāng)當(dāng) w 比比 f 小得多時(shí)（約小得多時(shí)（約 1313 Campbell 1969），直接計(jì)算相關(guān)比），直接計(jì)算相關(guān)比 FFT 更有效。更有效。n上式公式對上式公式對 f 和和 w 的尺度變化很敏感。的尺度變化很敏感。 ,stc x yw x y fxs yt , )( , )*( , )( , )f x yw x yFu v W u v（北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Proces

36、sing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT21n為了克服相關(guān)函數(shù)對為了克服相關(guān)函數(shù)對 f 和和 w 的尺度變化敏感的缺點(diǎn)，作為替的尺度變化敏感的缺點(diǎn)，作為替代，使用如下定義的代，使用如下定義的歸一化相關(guān)系數(shù)歸一化相關(guān)系數(shù)：n其中，求和的上下限取其中，求和的上下限取 w 和和 f 的共同范圍，的共同范圍， 是模板的平均值（只求是模板的平均值（只求一次），一次）， 是是 f 中與模板中與模板 w 重合區(qū)域的平均值。重合區(qū)域的平均值。n(x, y) 的值域?yàn)榈闹涤驗(yàn)?-1, 1，因而，因而 f 與與 w 的

37、幅度變化是歸一化的。的幅度變化是歸一化的。n當(dāng)歸一化的當(dāng)歸一化的 w 與與 f 中對應(yīng)的歸一化區(qū)域相同時(shí)，中對應(yīng)的歸一化區(qū)域相同時(shí)， (x, y) 出現(xiàn)最大值出現(xiàn)最大值，這說明了最大相關(guān)（即可能的這說明了最大相關(guān)（即可能的最好匹配最好匹配）。）。n當(dāng)兩個(gè)歸一化的當(dāng)兩個(gè)歸一化的 w 與與 f 具有最小相似性時(shí)，具有最小相似性時(shí)，(x, y) 出現(xiàn)最小值。出現(xiàn)最小值。n相關(guān)系數(shù)不能用傅里葉變換來計(jì)算相關(guān)系數(shù)不能用傅里葉變換來計(jì)算，因?yàn)樵撌街写嬖诜蔷€性項(xiàng)（除法，因?yàn)樵撌街写嬖诜蔷€性項(xiàng)（除法和平方）。和平方）。n注意：注意：灰度變化的歸一化相關(guān)是容易的，但對尺寸和旋轉(zhuǎn)的歸一化相灰度變化的歸一化相關(guān)是容

38、易的，但對尺寸和旋轉(zhuǎn)的歸一化相關(guān)是復(fù)雜的。關(guān)是復(fù)雜的。 1/222,xystxyststw s twf xs y tfx yw s twf xs y tf 基于決策理論方法的識(shí)別基于決策理論方法的識(shí)別-匹配匹配-相關(guān)匹配相關(guān)匹配xyf北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT22n左圖說明了上述處理的步驟。這里假設(shè)左圖說明了上述處理的步驟。這里假設(shè) f 原原點(diǎn)在

39、它的左上角，點(diǎn)在它的左上角，w 原點(diǎn)在它的中心，可原點(diǎn)在它的中心，可以處于圖像以處于圖像 f 的任何位置的任何位置 (x, y)。n計(jì)算完一點(diǎn)計(jì)算完一點(diǎn) (x,y) 的相關(guān)值，把模板的中心的相關(guān)值，把模板的中心移到一個(gè)相鄰位置，重復(fù)該過程。移到一個(gè)相鄰位置，重復(fù)該過程。通過移通過移動(dòng)模板的中心，使動(dòng)模板的中心，使 w 的中心遍歷的中心遍歷 f 中的每中的每個(gè)像素，可得到所有相關(guān)系數(shù)個(gè)像素，可得到所有相關(guān)系數(shù) (x, y) 。在。在該過程結(jié)束后，該過程結(jié)束后，尋找尋找(x, y) 中的最大值，從中的最大值，從而找到最好的匹配位置而找到最好的匹配位置。在。在 (x, y) 中可能中可能在多個(gè)位置存

40、在最大值，此時(shí)說明在多個(gè)位置存在最大值，此時(shí)說明 w 和和 f 之間有多個(gè)匹配。之間有多個(gè)匹配。n當(dāng)當(dāng) w 的中心位于的中心位于 f 的邊界上時(shí)，圍繞的邊界上時(shí)，圍繞 f 的邊的邊界需要進(jìn)行填充界需要進(jìn)行填充（在模板匹配中，當(dāng)模板（在模板匹配中，當(dāng)模板的中心越過圖像的邊界時(shí)，相關(guān)的值通常的中心越過圖像的邊界時(shí)，相關(guān)的值通常并不重要，因此，填充被限制為模板寬度并不重要，因此，填充被限制為模板寬度的一半）。為表示方便，通常只關(guān)心奇數(shù)的一半）。為表示方便，通常只關(guān)心奇數(shù)大小的模板。大小的模板。 基于決策理論方法的識(shí)別基于決策理論方法的識(shí)別-匹配匹配-相關(guān)匹配相關(guān)匹配模板匹配的機(jī)理模板匹配的機(jī)理中心在

41、任意位置中心在任意位置 (x, y) 的模板的模板圖像圖像 f原點(diǎn)原點(diǎn)填充填充北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT23n相關(guān)匹配的舉例相關(guān)匹配的舉例n913913 的的Harricane Andrew颶風(fēng)衛(wèi)星圖像，其中風(fēng)眼清晰可見；颶風(fēng)衛(wèi)星圖像，其中風(fēng)眼清晰可見；n3131 大小的大小的颶風(fēng)眼的模板颶風(fēng)眼的模板；n顯示為圖像的相關(guān)系數(shù)（注意最亮點(diǎn)），顯示為

42、圖像的相關(guān)系數(shù)（注意最亮點(diǎn)），由于填充，該圖像的原始由于填充，該圖像的原始大小為大小為 943943 像素，但為顯示，把它裁剪到原始圖像大小。在像素，但為顯示，把它裁剪到原始圖像大小。在該圖像中，灰度與相關(guān)值成正比，并且所有的負(fù)相關(guān)都截為該圖像中，灰度與相關(guān)值成正比，并且所有的負(fù)相關(guān)都截為 0（黑），以簡化該圖像的視覺分析，相關(guān)圖像的最亮點(diǎn)在接近颶風(fēng)（黑），以簡化該圖像的視覺分析，相關(guān)圖像的最亮點(diǎn)在接近颶風(fēng)眼的位置清晰可見；眼的位置清晰可見；a)最大相關(guān)顯示為一個(gè)白點(diǎn)，與颶風(fēng)眼位置緊密對應(yīng)最大相關(guān)顯示為一個(gè)白點(diǎn)，與颶風(fēng)眼位置緊密對應(yīng)（此時(shí)，存在一（此時(shí)，存在一個(gè)最大值為個(gè)最大值為 1 的唯一匹

43、配）。的唯一匹配）?；跊Q策理論方法的識(shí)別基于決策理論方法的識(shí)別-匹配匹配-相關(guān)匹配相關(guān)匹配北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT24基于決策理論方法的識(shí)別基于決策理論方法的識(shí)別-最佳統(tǒng)計(jì)分配器最佳統(tǒng)計(jì)分配器n就像在大多數(shù)處理度量和判讀領(lǐng)域中一樣，就像在大多數(shù)處理度量和判讀領(lǐng)域中一樣，在模式識(shí)別中考在模式識(shí)別中考慮概率統(tǒng)計(jì)問題也十分重要慮概率統(tǒng)計(jì)問題也十分重

44、要。n基于概率統(tǒng)計(jì)理論，推導(dǎo)一種最佳模式識(shí)別方法，使得產(chǎn)生基于概率統(tǒng)計(jì)理論，推導(dǎo)一種最佳模式識(shí)別方法，使得產(chǎn)生的分類錯(cuò)誤的概率在平均意義上最低。的分類錯(cuò)誤的概率在平均意義上最低。n來自來自 i 類的特定模式類的特定模式 x 概率表示為概率表示為 p(i /x）。如果模式分）。如果模式分類器判斷類器判斷 x 來自來自j 類，而實(shí)際上它來自類，而實(shí)際上它來自i 類，那么分類器類，那么分類器出現(xiàn)一次失敗的分類，出現(xiàn)一次失敗的分類，導(dǎo)致一次損失，表示為導(dǎo)致一次損失，表示為 Lij。n因?yàn)槟Ｊ揭驗(yàn)槟Ｊ?x 可能屬于所有可能屬于所有 W 個(gè)類中的任何一個(gè)類，所以，個(gè)類中的任何一個(gè)類，所以，將模式將模式 x

45、 指定為指定為 j 類的類的平均損失平均損失為為 n該公式稱為該公式稱為條件平均風(fēng)險(xiǎn)條件平均風(fēng)險(xiǎn)或或條件平均損失條件平均損失。 1/WjkjkkrxL px 北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT25基于決策理論方法的識(shí)別基于決策理論方法的識(shí)別-最佳統(tǒng)計(jì)分配器最佳統(tǒng)計(jì)分配器-基礎(chǔ)基礎(chǔ)n由概率論可知，有由概率論可知，有 p(A/B) = p(A)p(B/A)

46、/ p(B)，則上式變，則上式變?yōu)椋簽椋?11/WjkjkkkrxL p xPp x 其中，其中，p(x /k）是來自）是來自 k 類的模式的概率密度函數(shù)，類的模式的概率密度函數(shù)， P(k) 是是 k 類出現(xiàn)的概率。類出現(xiàn)的概率。n由于由于 1/p(x) 是正的，并且對所有的是正的，并且對所有的 rj(x) 都為正，故可以從上式中省都為正，故可以從上式中省略掉此項(xiàng)，而不影響略掉此項(xiàng)，而不影響 rj(x) 的相對大小排序，的相對大小排序，平均損失簡化為平均損失簡化為：n假設(shè)分類器有假設(shè)分類器有 W 個(gè)可能的類，任何給定的未知模式可從這個(gè)可能的類，任何給定的未知模式可從這些類中選擇。如果分類器對每

47、個(gè)模式些類中選擇。如果分類器對每個(gè)模式 x 計(jì)算計(jì)算r(x)，并且把該，并且把該模式所具有的最低損失賦給相應(yīng)的類，則對所有判決來講，模式所具有的最低損失賦給相應(yīng)的類，則對所有判決來講，總體平均損失將是最低的?？傮w平均損失將是最低的。這種總體平均損失最佳的分類這種總體平均損失最佳的分類器稱為器稱為貝葉斯分類器貝葉斯分類器。 1/WjkjkkkrxL p xP 北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommuni

48、cation Centre, BUPT26基于決策理論方法的識(shí)別基于決策理論方法的識(shí)別-最佳統(tǒng)計(jì)分配器最佳統(tǒng)計(jì)分配器-基礎(chǔ)基礎(chǔ)n如果如果 ri(x) 0 時(shí)時(shí)，輸出為，輸出為 +1，模式，模式 x 識(shí)別為屬于識(shí)別為屬于 1 類；類；n當(dāng)當(dāng) d(x) 0 時(shí)時(shí)，輸出為，輸出為 -1，模式，模式 x 識(shí)別為屬于識(shí)別為屬于 2 類；這與前面介紹類；這與前面介紹的單個(gè)決策函數(shù)是一致的。的單個(gè)決策函數(shù)是一致的。n當(dāng)當(dāng) d(x) = 0 時(shí)時(shí)，模式，模式 x 位于分割兩個(gè)模式類的決策面上，處于不能位于分割兩個(gè)模式類的決策面上，處于不能確定的狀態(tài)，需要給出決策邊界條件。確定的狀態(tài)，需要給出決策邊界條件。n令

49、上式令上式 d(x) 等于等于 0，給出決策邊界：，給出決策邊界：11( )niinid xw xw 11( )0niinid xw xw 北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT45決策理論模式識(shí)別決策理論模式識(shí)別-神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)-兩個(gè)模式類的感知器兩個(gè)模式類的感知器n上式是在上式是在 n 維模式空間中的一個(gè)超平面方程。維模式空間中的一個(gè)超平面方程。在幾何

50、上，前在幾何上，前 n 個(gè)系數(shù)確定超平面的方向，最個(gè)系數(shù)確定超平面的方向，最后一個(gè)系數(shù)后一個(gè)系數(shù) wn+1 與從原點(diǎn)到超平面的垂直距與從原點(diǎn)到超平面的垂直距離成正比。當(dāng)離成正比。當(dāng) wn+1 =0，則超平面經(jīng)過模式空，則超平面經(jīng)過模式空間的原點(diǎn)；類似地，如果間的原點(diǎn)；類似地，如果 wj =0，則超平面平，則超平面平行于行于 xj 軸。軸。n上圖中的閾值單元輸出取決于上圖中的閾值單元輸出取決于 d(x) 的符號，把的符號，把 wn+1 項(xiàng)移到項(xiàng)移到等式右邊，此時(shí)系統(tǒng)的輸出為：等式右邊，此時(shí)系統(tǒng)的輸出為：n該實(shí)現(xiàn)等同于右圖所示，唯一不同是閾值函數(shù)被量該實(shí)現(xiàn)等同于右圖所示，唯一不同是閾值函數(shù)被量 -

51、 wn+1 所取代，且所取代，且沒有了常量單位輸入。沒有了常量單位輸入。11111, 1, niininiiniw xwOw xw 北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT46決策理論模式識(shí)別決策理論模式識(shí)別-神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)-兩個(gè)模式類的感知器兩個(gè)模式類的感知器n另一個(gè)常用的公式是擴(kuò)充這些模式向量另一個(gè)常用的公式是擴(kuò)充這些模式向量，方法是附加一個(gè)額，方法是附

52、加一個(gè)額外的第外的第 (n+1) 個(gè)元素，不管類成員是什么，該元素總等于個(gè)元素，不管類成員是什么，該元素總等于 1。即擴(kuò)充后的模式向量即擴(kuò)充后的模式向量 y 是從模式向量是從模式向量 x 創(chuàng)建的，令創(chuàng)建的，令 yi = xi，i=1,2,n，并附加一個(gè)額外的元素，并附加一個(gè)額外的元素 yn+1 = 1。則響應(yīng)變?yōu)椋骸t響應(yīng)變?yōu)椋簄其中其中 y = (y1,y2,yn,1)T 是一個(gè)擴(kuò)充的模式向量；是一個(gè)擴(kuò)充的模式向量； w = (w1,w2,wn+1)T 是加權(quán)向量；是加權(quán)向量；n通常是更為方便的表達(dá)式。通常是更為方便的表達(dá)式。n不管采用哪個(gè)公式表示，不管采用哪個(gè)公式表示，關(guān)鍵問題關(guān)鍵問題是使

53、用來自兩個(gè)類的一個(gè)是使用來自兩個(gè)類的一個(gè)給定模式向量給定模式向量訓(xùn)練集找到訓(xùn)練集找到 w。11( )nTiiid xw yw y 北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT47神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)-訓(xùn)練算法訓(xùn)練算法-線性可分的類線性可分的類n線性可分的類：線性可分的類：用于求兩個(gè)線性可分訓(xùn)練集的權(quán)重向量解用于求兩個(gè)線性可分訓(xùn)練集的權(quán)重向量解的一種簡單的一種簡單迭代算

54、法迭代算法：n對于兩個(gè)分別屬于對于兩個(gè)分別屬于 1 和和 2 的擴(kuò)充模式向量的訓(xùn)練集，令的擴(kuò)充模式向量的訓(xùn)練集，令 w(1) 表示任意選擇的一個(gè)初始加權(quán)向量。表示任意選擇的一個(gè)初始加權(quán)向量。n第第 k 步迭代中步迭代中n若若 y(k) 1，并且，并且 wT(k)y(k) 0，則使用下式代替，則使用下式代替 w(k)：n若若 y(k) 2，并且，并且 wT(k)y(k) 0，則：，則：n否則，令否則，令 w(k) 不變：不變：(1)( )( )w kw kcy k (1)( )( )w kw kcy k (1)( )w kw k c 是一個(gè)正的修正增量，若是一個(gè)正的修正增量，若是一個(gè)常量，該算法

55、有時(shí)稱是一個(gè)常量，該算法有時(shí)稱為為固定增量校正準(zhǔn)則固定增量校正準(zhǔn)則。當(dāng)兩個(gè)類的整個(gè)訓(xùn)練集循環(huán)通過機(jī)器而當(dāng)兩個(gè)類的整個(gè)訓(xùn)練集循環(huán)通過機(jī)器而不出現(xiàn)任何錯(cuò)誤時(shí)，該算法收斂。如果不出現(xiàn)任何錯(cuò)誤時(shí)，該算法收斂。如果模式的兩個(gè)訓(xùn)練集是線性可分的，那么模式的兩個(gè)訓(xùn)練集是線性可分的，那么固定增量校正準(zhǔn)則會(huì)在有限步內(nèi)收斂。固定增量校正準(zhǔn)則會(huì)在有限步內(nèi)收斂。北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Cen

56、tre, BUPT48神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)-訓(xùn)練算法訓(xùn)練算法-線性可分的類線性可分的類n感知機(jī)算法舉例感知機(jī)算法舉例n下圖下圖 (a) 所示的兩個(gè)訓(xùn)練集，每個(gè)訓(xùn)練集由兩個(gè)模式組成，兩個(gè)訓(xùn)所示的兩個(gè)訓(xùn)練集，每個(gè)訓(xùn)練集由兩個(gè)模式組成，兩個(gè)訓(xùn)練集是線性可分的，故可以采用上述算法。練集是線性可分的，故可以采用上述算法。n在應(yīng)用算法之前，進(jìn)行模式擴(kuò)充，對在應(yīng)用算法之前，進(jìn)行模式擴(kuò)充，對 1 類生成訓(xùn)練集類生成訓(xùn)練集 (0,0,1)T, (0,1,1)T，對，對 2 類生成訓(xùn)練集類生成訓(xùn)練集 (1,0,1)T, (1,1,1)T，令，令 c=1，w(1)=0，并按如下步驟順序提交這些模式：并按如下步驟順序提交

57、這些模式：北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT49神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)-訓(xùn)練算法訓(xùn)練算法-線性可分的類線性可分的類n感知機(jī)算法舉例感知機(jī)算法舉例n從中看到，由于錯(cuò)誤分類，在第從中看到，由于錯(cuò)誤分類，在第 1 步和第步和第 3 步進(jìn)行了權(quán)重向量的修步進(jìn)行了權(quán)重向量的修正；正；n由于僅當(dāng)算法由于僅當(dāng)算法對所有訓(xùn)練模式完全無誤迭代時(shí)，才能得到一個(gè)解對所有訓(xùn)練模式完全

58、無誤迭代時(shí)，才能得到一個(gè)解，因此，需要再次提交訓(xùn)練集，學(xué)習(xí)過程繼續(xù)下去：令因此，需要再次提交訓(xùn)練集，學(xué)習(xí)過程繼續(xù)下去：令 y(5)=y(1)，y(6)=y(2)，y(7)=y(3)，y(8)=y(4)，并以同樣的方式進(jìn)行。，并以同樣的方式進(jìn)行。n當(dāng)當(dāng) k=14 時(shí)收斂，得到權(quán)重向量為時(shí)收斂，得到權(quán)重向量為 w = (-2, 0, 1)T，相應(yīng)的決策函數(shù)，相應(yīng)的決策函數(shù)為為 d(y) = - 2y1 + 1。n通過令通過令 xi=yi，返回原始模式空間，得返回原始模式空間，得 d(x) = -2x1+1。當(dāng)集合等于。當(dāng)集合等于 0，它變成了下圖它變成了下圖 (b) 所示的所示的決策邊界方程決策邊

59、界方程。北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東北京郵電大學(xué)信息與通信工程學(xué)院多媒體技術(shù)中心門愛東 Digital Image Processing 對象識(shí)別對象識(shí)別, Men Aidong, Multimedia Telecommunication Centre, BUPT50神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)-訓(xùn)練算法訓(xùn)練算法-不可分的類不可分的類n不可分的類不可分的類n實(shí)際中，線性可分模式類是個(gè)例外，通常情況并非如此。上世紀(jì)六實(shí)際中，線性可分模式類是個(gè)例外，通常情況并非如此。上世紀(jì)六七十年代后，大多數(shù)研究轉(zhuǎn)向了不可分的模式類。隨著神經(jīng)網(wǎng)絡(luò)訓(xùn)七十年代后，大多數(shù)研究轉(zhuǎn)向了不可分的模式類。隨著神經(jīng)網(wǎng)絡(luò)

60、訓(xùn)練取得的進(jìn)展，許多不分開模式類處理方法已成為歷史，但早期的練取得的進(jìn)展，許多不分開模式類處理方法已成為歷史，但早期的德爾塔德爾塔 Delta 規(guī)則還在繼續(xù)使用。規(guī)則還在繼續(xù)使用。nDelta 規(guī)則規(guī)則n原始的原始的 Delta 規(guī)則稱為規(guī)則稱為感知訓(xùn)練的感知訓(xùn)練的 Widrow-Hoff 或最小均方或最小均方 (LMS) delta 規(guī)則規(guī)則，它使得在任何訓(xùn)練步驟中實(shí)際響應(yīng)和期望響應(yīng)之間的誤，它使得在任何訓(xùn)練步驟中實(shí)際響應(yīng)和期望響應(yīng)之間的誤差最小。差最小。n考慮考慮準(zhǔn)則函數(shù)準(zhǔn)則函數(shù)為為n其中，其中，r 是期望響應(yīng)，即當(dāng)擴(kuò)充后的訓(xùn)練模式向量是期望響應(yīng)，即當(dāng)擴(kuò)充后的訓(xùn)練模式向量 y 屬于類屬于類