DIP12 对象识别

1、北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东数字图像处理数字图像处理Digital Image Processing信息与通信工程学院多媒体技术中心信息与通信工程学院多媒体技术中心第十二第十二章章 目标识别目标识别Object Recognition门爱东教授门爱东教授北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BU

2、PT2目标识别目标识别n本章阐述的本章阐述的目标（或模式）识别目标（或模式）识别方法主要分为两大领域：方法主要分为两大领域：决决策理论策理论和和结构判别结构判别。n决策理论方法：决策理论方法：此类方法处理的是使用此类方法处理的是使用定量描绘子定量描绘子来描述的各种模来描述的各种模式，定量描绘子包括长度、面积和纹理等。式，定量描绘子包括长度、面积和纹理等。n结构判别方法结构判别方法：此类方法处理的是由：此类方法处理的是由定性描绘子定性描绘子描述的各种模式，描述的各种模式，如前面讨论过的关系描绘子。如前面讨论过的关系描绘子。n识别的核心问题是识别的核心问题是通过样本模式进行通过样本模式进行 “学习

3、学习” 这一概念。这一概念。这个世界有趣的一面是可以把它看成由各种模式组这个世界有趣的一面是可以把它看成由各种模式组成的，模式本质上是一种排列，它是由元素顺序而不是成的，模式本质上是一种排列，它是由元素顺序而不是这些元素固有性质来表征的。这些元素固有性质来表征的。 - 诺伯特诺伯特 . 维纳维纳北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT3本章内容本章内容 Out

4、linesn模式和模式类模式和模式类n基于决策理论方法的识别基于决策理论方法的识别n结构性方法结构性方法北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT4 模式和模式类模式和模式类n模式模式是是描绘子描绘子的组合。的组合。n前面讨论过的那些描绘子；前面讨论过的那些描绘子；n在在 模式识别的文献中，长使用模式识别的文献中，长使用“特征特征”来表示描绘子。来表示描绘子。n

5、模式类模式类是指具有某些共同属性的是指具有某些共同属性的一族模式一族模式，一般用，一般用 1、2、.W 表示，其中表示，其中 W 是模式类的数量。是模式类的数量。n实践中，常用的三种实践中，常用的三种模式组合模式组合是模式是模式向量向量（用于定量描（用于定量描述）、述）、字符串字符串和和树树（用于结构描述）。（用于结构描述）。n模式向量用粗体小写字母表示，比如模式向量用粗体小写字母表示，比如 x x, y y 和和 z z，并采用，并采用如下的列向量如下的列向量 (即即 n1 阶矩阵）的形式表示：阶矩阵）的形式表示： 其中，每个分量其中，每个分量 xi 表示第表示第 i 个描绘子；个描绘子；n

6、 是与该模式有关的描绘是与该模式有关的描绘子的总数；子的总数；T 表示转置。表示转置。 12,.Tnx xx x x北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT5 模式和模式类模式和模式类n模式向量模式向量 x x 中中各个分量的性质各个分量的性质取决于用于描述该物理模式取决于用于描述该物理模式自身的方法。下面用一个简单的例子来说明并给出分类度量自身的方法。下面用

7、一个简单的例子来说明并给出分类度量的历史意义。的历史意义。n在在 Fisher1936 发表的经典论文中，提出了后来被称为发表的经典论文中，提出了后来被称为判别判别分析分析的算法，它通过测量花瓣的的算法，它通过测量花瓣的宽度宽度和和长度，长度，识别了三种鸢识别了三种鸢(yuan) 尾花尾花 (Iris Setosa, Iris Virginica 和和 Iris Versicolor)。n每种花由两个度量描述，这生成了如下的二维模式向量：每种花由两个度量描述，这生成了如下的二维模式向量：nx1 和和 x2 分别代表花瓣的长度和宽度分别代表花瓣的长度和宽度n在此，表示为在此，表示为 1、2、3

8、的的 3 个模式类分别对应个模式类分别对应山鸢尾山鸢尾 (Iris setosa)、维吉尼亚鸢尾、维吉尼亚鸢尾 (Iris virginica) 和变色鸢尾和变色鸢尾 (Iris versicolor) 三三种花。种花。12xx x x北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT6模式和模式类模式和模式类用两个度量描述的三种鸢尾花用两个度量描述的三种鸢尾花n本例中

9、，本例中，花瓣长度和宽度能较花瓣长度和宽度能较好地把好地把Setosa与其它两种花区与其它两种花区分开来分开来，但对，但对Virginica和和Versi color 的分离效果不佳。的分离效果不佳。n这一结果说明了这一结果说明了经典的特征选经典的特征选择问题择问题，即类的可分程度在很，即类的可分程度在很大程度上取决于所用描绘子的大程度上取决于所用描绘子的选择。后面对此进行更多的阐选择。后面对此进行更多的阐述。述。n由于花瓣在宽度和长度上的不同，描述这些花的模式向量也由于花瓣在宽度和长度上的不同，描述这些花的模式向量也会不同会不同，这种不同不仅存在于不同种类的花瓣之间，在同一，这种不同不仅存在

10、于不同种类的花瓣之间，在同一种类的花瓣间也存在。种类的花瓣间也存在。n在选定了一组度量后（本例中为长度和宽度），模式向量的在选定了一组度量后（本例中为长度和宽度），模式向量的分量便成为每个物理样本的完整描述。因此，每朵花就由二分量便成为每个物理样本的完整描述。因此，每朵花就由二维欧氏空间中的一个点代表。维欧氏空间中的一个点代表。北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre,

11、BUPT7模式和模式类模式和模式类一个噪声目标及其对应的信号一个噪声目标及其对应的信号n下图显示了另一个生成模式向量的例子下图显示了另一个生成模式向量的例子。在该例中，关注的。在该例中，关注的是不同类型的噪声波形，其中一个样本示于图是不同类型的噪声波形，其中一个样本示于图 (a) 中。如果中。如果选择用噪声信号代表每个目标，会得到图选择用噪声信号代表每个目标，会得到图 (b) 所示的一维信所示的一维信号。号。n假设用取样后的幅度值来描述每个信号假设用取样后的幅度值来描述每个信号，即以指定的角度间，即以指定的角度间隔值隔值 对信号进行取样，然后通过令对信号进行取样，然后通过令 x1= r(1)，

12、 x2= r(2),., xn = r(n)，可构成模式向量。，可构成模式向量。n这些向量成为这些向量成为 n 维欧几里得空间中的点，并且模式类可以想维欧几里得空间中的点，并且模式类可以想象成象成 n 维空间中的维空间中的“云团云团”。(a)(b)北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT8模式和模式类模式和模式类n实际上，实际上，还有很多其它方法生成模式向量还

13、有很多其它方法生成模式向量，本章中将介绍，本章中将介绍其中的一些方法。其中的一些方法。n例如，计算给定信号的前例如，计算给定信号的前 n 个统计矩，代替前述的信号幅度，作为个统计矩，代替前述的信号幅度，作为描绘子来生成每个模式向量的分量。描绘子来生成每个模式向量的分量。n应记住的应记住的关键概念关键概念是：模式向量中每个分量描绘子的选择，是：模式向量中每个分量描绘子的选择，描绘子对基于模式向量方法的目标识别的最终性能有很大描绘子对基于模式向量方法的目标识别的最终性能有很大影响。影响。n上述描述的用于生成模式向量的技术，可得到由定量信息上述描述的用于生成模式向量的技术，可得到由定量信息表征的模式

14、类。表征的模式类。n在某些应用中，模式特性可由在某些应用中，模式特性可由结构关系结构关系很好地描述很好地描述。n例如，指纹识别基于痕迹特性的相互关系（称为例如，指纹识别基于痕迹特性的相互关系（称为细节细节），与它们的），与它们的相对大小和位置一起，这些特性是描述指纹脊线特性的主要分量，相对大小和位置一起，这些特性是描述指纹脊线特性的主要分量，如指纹的断点、分支、合并和不连续线段。如指纹的断点、分支、合并和不连续线段。n这类识别问题常用结构方法解决这类识别问题常用结构方法解决，因为这类问题不仅定量度量每种，因为这类问题不仅定量度量每种特性，而且这些特性间的空间关系决定了类别的成员。特性，而且这些

15、特性间的空间关系决定了类别的成员。北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT9模式和模式类模式和模式类n结构描绘子组合的模式举例结构描绘子组合的模式举例n下图下图 (a) 显示了一个简单的阶梯模式，如上例噪声所示，可以对该显示了一个简单的阶梯模式，如上例噪声所示，可以对该模式进行角度取样，并表示为一个向量模式。然而，用这种向量模模式进行角度取样，并表示为一个向量

16、模式。然而，用这种向量模式方法将无法表示由两个简单的主要元素式方法将无法表示由两个简单的主要元素 a、b 重复而组成的基本重复而组成的基本阶梯结构。阶梯结构。n一种更好的一种更好的描述方法描述方法是定义元素是定义元素 a 和和 b，并将模式定义为图，并将模式定义为图 (b) 所所示的示的字符串字符串 w=.abababab.。n生成方法：以首尾相连的方式定义连接性，且只允许符号交替。生成方法：以首尾相连的方式定义连接性，且只允许符号交替。n这种结构组成适用于任何长度的阶梯，但排除了由基元这种结构组成适用于任何长度的阶梯，但排除了由基元 a 和和 b 的其它组的其它组合生成其它类型的结果。合生成

17、其它类型的结果。n串描述适于生成其结构是基于串描述适于生成其结构是基于基元的较简单的连接基元的较简单的连接，并且通，并且通常是和边界形状有关系的目标常是和边界形状有关系的目标模式和其它实体模式。模式和其它实体模式。北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT10模式和模式类模式和模式类n对许多应用来说，对许多应用来说，更有效的方法是树形描述更有效的方法是树形描述。

18、n基本上，多数层次排序方式都会导致树形结构基本上，多数层次排序方式都会导致树形结构。n例如，下图显示了一幅建筑物稠密的市区和周围居民区的卫星图像。例如，下图显示了一幅建筑物稠密的市区和周围居民区的卫星图像。有稠密建筑物的城市中心区及周围居民区的卫星照片有稠密建筑物的城市中心区及周围居民区的卫星照片北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT11模式和模式类模式和模

19、式类n下图中下图中 (从上到下从上到下) 显示的树形表示是显示的树形表示是通过使用结构关系通过使用结构关系“由由.组成组成” 得到的。得到的。n树的根节点代表整幅图像，使用符号树的根节点代表整幅图像，使用符号 $ 表示整个图像区域；表示整个图像区域；n下一级的节点表示该图像由城区和居民区组成；下一级的节点表示该图像由城区和居民区组成；n居民区依次由住宅、商业区和高速公路构成；居民区依次由住宅、商业区和高速公路构成；n再下一级描述住宅和告诉公路；再下一级描述住宅和告诉公路；n可以继续按此细分，直至达到图像不同区域的解析能力极限为止。可以继续按此细分，直至达到图像不同区域的解析能力极限为止。北京邮

20、电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT12本章内容本章内容n模式和模式类模式和模式类n基于决策理论方法的模式识别基于决策理论方法的模式识别n匹配匹配n最佳统计分类器最佳统计分类器n神经网络神经网络n结构性方法结构性方法北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processin

21、g 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT13基于决策理论方法的模式识别基于决策理论方法的模式识别n决策理论模式识别方法决策理论模式识别方法是以决策（或判别）函数为基础的。是以决策（或判别）函数为基础的。n令令 x = (x1, x2, xn)T 表示一个表示一个 n 维模式向量。对于维模式向量。对于 W 个模式个模式类类 1、2、.、W，决策理论模式识别的，决策理论模式识别的基本问题基本问题是依据是依据如下属性找到如下属性找到 W 个个决策决策(判别判别)函数函数 d1(x)、d2(x)、dW(x) ，如

22、果模式如果模式 x 属于类属于类 i ，则，则 n上式表示：将上式表示：将 x 代入所有决策函数后，如果代入所有决策函数后，如果 di(x) 得到最大值，则称得到最大值，则称未知的模式未知的模式 x 属于第属于第 i 个模式类，该关系可以任意求解。个模式类，该关系可以任意求解。n从类从类 j 中分离出类中分离出类 i 的决策边界的决策边界，由满足，由满足 di(x)=dj(x) 的的 x 值给出，或等价地由值给出，或等价地由 di(x)-dj(x)=0 式中的式中的 x 值给出。值给出。n通常是使用单一函数通常是使用单一函数 dij(x) = di(x) - dj(x) = 0 来识别两个类之

23、间的决策来识别两个类之间的决策（判别）边界（判别）边界。因此，对于模式类。因此，对于模式类 i ，有，有 dij(x) 0，而模式类，而模式类 j ，有有 dij(x) 3 时，是时，是一个超一个超平面平面。 12TTjjjjdxx mm m Wj,2, 1基于决策理论方法的识别基于决策理论方法的识别-匹配匹配-最小距离分类器最小距离分类器 102ijijTTijijijdxdxdxxmmmmmm 北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, M

24、ultimedia Telecommunication Centre, BUPT16n左图显示了从前述的鸢尾花中提左图显示了从前述的鸢尾花中提取的两个模式类。取的两个模式类。n两个模式类两个模式类 Iris Versicolor 和和Iris Setosa 分别表示为分别表示为 1 和和 2，样，样本均值向量为本均值向量为 m1=(4.3, 1.3)T 和和 m2=(1.5, 0.3)T。 n相应的相应的决策函数决策函数是：是：n由此得出由此得出边界方程边界方程为：为：n左图显示了该边界的图形左图显示了该边界的图形（注意（注意轴的比例不同）。轴的比例不同）。n最小距离分类器的举例最小距离分类器

25、的举例 111112124.31.310.1TTdxx mm mxx 122222121.50.31.17TTdxx mm mxx 基于决策理论方法的识别基于决策理论方法的识别-匹配匹配-最小距离分类器最小距离分类器 1212122.81.08.90dxdxdxxx 任何来自类任何来自类 1 的的模式向量代入边界模式向量代入边界方程，都会得到方程，都会得到 d12(x) 0。相反，任。相反，任何来自类何来自类 2 的的模式向量代入边界方模式向量代入边界方程，都会得到程，都会得到 d12(x) 0。根据根据 d12(x) 的符号将足以确定未知模式的归属。的符号将足以确定未知模式的归属。12北京邮

26、电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT17n实际上，当每个类均值之间的距离与每个类的分散度或随机实际上，当每个类均值之间的距离与每个类的分散度或随机性相比较大时，性相比较大时，最小距离分类器工作得很好最小距离分类器工作得很好。n后面将证明：当每个类的均值分布在后面将证明：当每个类的均值分布在 n 维模式空间中呈现为维模式空间中呈现为一种球形的一种球形的“超云团超云

27、团”形式时，最小距离分类器会得到形式时，最小距离分类器会得到最佳最佳性能性能（在最小化错误分类的平均损失方面）。（在最小化错误分类的平均损失方面）。n实际中，很少同时出现较大的均值分离和相对较小的散布，实际中，很少同时出现较大的均值分离和相对较小的散布，除非系统设计人员能控制输入的性质。除非系统设计人员能控制输入的性质。基于决策理论方法的识别基于决策理论方法的识别-匹配匹配-最小距离分类器最小距离分类器n一个很好的例子就是设计用于读取固定格式一个很好的例子就是设计用于读取固定格式字符的系统；字符的系统；n例如，例如，美国银行家协会美国银行家协会 E-13B 字符集，由字符集，由 14 个字符组

28、成个字符组成。n这些字符被特意设计在这些字符被特意设计在 97 的网格中以便于的网格中以便于读取，并常用含有精细磁性材料的墨水印刷。读取，并常用含有精细磁性材料的墨水印刷。n在读取这些字符之前，对油墨施加一个磁场来在读取这些字符之前，对油墨施加一个磁场来加重每个字符，以便简化检测，即人工地突出加重每个字符，以便简化检测，即人工地突出每个字符的关键特征，解决了分割问题。每个字符的关键特征，解决了分割问题。北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong,

29、 Multimedia Telecommunication Centre, BUPT18n美国银行家协会美国银行家协会 E-13B 字符集字符集n通常使用单缝读取头水平扫描字符，读取头与字符相比要窄一些、通常使用单缝读取头水平扫描字符，读取头与字符相比要窄一些、长一些。长一些。n当读取头横向移动一个字符时，会产生一个一维电信号，该电信号当读取头横向移动一个字符时，会产生一个一维电信号，该电信号与读取头下方字符面积的增大率或减少率成正比。与读取头下方字符面积的增大率或减少率成正比。n例如，观察图中与字符例如，观察图中与字符 “0” 的波形。的波形。n当读取头从左向右移动时，当读取头从左向右移动时

30、，扫描到扫描到 0 左边的竖杠左边的竖杠，读取头看到的字符面，读取头看到的字符面积开始增大，从而产生一个正导数（正变化率）。当读取头开始远离积开始增大，从而产生一个正导数（正变化率）。当读取头开始远离 0 基于决策理论方法的识别基于决策理论方法的识别-匹配匹配-最小距离分类器最小距离分类器 左边的竖杠时，读取头下方的面积开始减少，从而产左边的竖杠时，读取头下方的面积开始减少，从而产生一个负导数；生一个负导数；n当读取头位于当读取头位于 0 的的中间区域中间区域时，扫过的面积几乎不变，时，扫过的面积几乎不变，从而产生零导数；从而产生零导数；n当读取头扫到当读取头扫到 0 的的右边竖杠右边竖杠时，

31、重复一次左边的波形时，重复一次左边的波形（模式）；（模式）；nE-13B 的设计确保了每个字符的波形是完全不同的，也的设计确保了每个字符的波形是完全不同的，也确保了每个波形的峰值和零值大致出现在背景网格的垂确保了每个波形的峰值和零值大致出现在背景网格的垂直线上。直线上。北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT19nE-13B 字符集具有的性质：字符集具有的性质

32、：仅在仅在这些点处对波形取样，就可得到这些点处对波形取样，就可得到实现正确分类所需的足够信息。实现正确分类所需的足够信息。n针对这一应用，设计一个最小针对这一应用，设计一个最小距离分类器是相当简单的。距离分类器是相当简单的。n只需要存储每个波形的样本值，只需要存储每个波形的样本值，然后将每组样本表示为一个原型然后将每组样本表示为一个原型向量向量 mj，j=1,2,14.n当对一个未知字符进行分类时，当对一个未知字符进行分类时，使用刚才的方式扫描它，将波形使用刚才的方式扫描它，将波形的网格样本表示为一个向量的网格样本表示为一个向量 x，然后计算然后计算 dj(x)，依据其最高值选，依据其最高值选

33、择原型向量的类。择原型向量的类。n使用一组电阻组成的模拟电路可使用一组电阻组成的模拟电路可实现高速分类。实现高速分类。基于决策理论方法的识别基于决策理论方法的识别-匹配匹配-最小距离分类器最小距离分类器北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT20基于决策理论方法的识别基于决策理论方法的识别-匹配匹配-相关匹配相关匹配n前面介绍过图像相关的基本概念，并广泛应用于

34、空间滤波。前面介绍过图像相关的基本概念，并广泛应用于空间滤波。n大小大小 mn 的模板的模板 w(x, y) 与图像与图像 f(x, y) 的的相关相关定义为：定义为： 其中，其中，求和的上下限取求和的上下限取 w 和和 f 的共同范围的共同范围，假设，假设 f 范围大于范围大于 w。n相关定理相关定理 其中，其中， 表示空间相关，表示空间相关，F* 是是 F 的复共轭；的复共轭；n上式的反变换得到一个二维循环相关，并且上式的反变换得到一个二维循环相关，并且注意填充问题注意填充问题；n相关可以通过相关可以通过 FFT 算法在频域中完成算法在频域中完成，当应考虑模板当应考虑模板 w 的大小的大小

35、n若若 f 和和 w 大小相同，大小相同，FFT 比在空间域中直接计算相关更有效；比在空间域中直接计算相关更有效；n当当 w 比比 f 小得多时（约小得多时（约 1313 Campbell 1969），直接计算相关比），直接计算相关比 FFT 更有效。更有效。n上式公式对上式公式对 f 和和 w 的尺度变化很敏感。的尺度变化很敏感。 ,stc x yw x y fxs yt , )( , )*( , )( , )f x yw x yFu v W u v（北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Proces

36、sing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT21n为了克服相关函数对为了克服相关函数对 f 和和 w 的尺度变化敏感的缺点，作为替的尺度变化敏感的缺点，作为替代，使用如下定义的代，使用如下定义的归一化相关系数归一化相关系数：n其中，求和的上下限取其中，求和的上下限取 w 和和 f 的共同范围，的共同范围， 是模板的平均值（只求是模板的平均值（只求一次），一次）， 是是 f 中与模板中与模板 w 重合区域的平均值。重合区域的平均值。n(x, y) 的值域为的值域为 -1, 1，因而，因而 f 与与 w 的

37、幅度变化是归一化的。的幅度变化是归一化的。n当归一化的当归一化的 w 与与 f 中对应的归一化区域相同时，中对应的归一化区域相同时， (x, y) 出现最大值出现最大值，这说明了最大相关（即可能的这说明了最大相关（即可能的最好匹配最好匹配）。）。n当两个归一化的当两个归一化的 w 与与 f 具有最小相似性时，具有最小相似性时，(x, y) 出现最小值。出现最小值。n相关系数不能用傅里叶变换来计算相关系数不能用傅里叶变换来计算，因为该式中存在非线性项（除法，因为该式中存在非线性项（除法和平方）。和平方）。n注意：注意：灰度变化的归一化相关是容易的，但对尺寸和旋转的归一化相灰度变化的归一化相关是容

38、易的，但对尺寸和旋转的归一化相关是复杂的。关是复杂的。 1/222,xystxyststw s twf xs y tfx yw s twf xs y tf 基于决策理论方法的识别基于决策理论方法的识别-匹配匹配-相关匹配相关匹配xyf北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT22n左图说明了上述处理的步骤。这里假设左图说明了上述处理的步骤。这里假设 f 原原点在

39、它的左上角，点在它的左上角，w 原点在它的中心，可原点在它的中心，可以处于图像以处于图像 f 的任何位置的任何位置 (x, y)。n计算完一点计算完一点 (x,y) 的相关值，把模板的中心的相关值，把模板的中心移到一个相邻位置，重复该过程。移到一个相邻位置，重复该过程。通过移通过移动模板的中心，使动模板的中心，使 w 的中心遍历的中心遍历 f 中的每中的每个像素，可得到所有相关系数个像素，可得到所有相关系数 (x, y) 。在。在该过程结束后，该过程结束后，寻找寻找(x, y) 中的最大值，从中的最大值，从而找到最好的匹配位置而找到最好的匹配位置。在。在 (x, y) 中可能中可能在多个位置存

40、在最大值，此时说明在多个位置存在最大值，此时说明 w 和和 f 之间有多个匹配。之间有多个匹配。n当当 w 的中心位于的中心位于 f 的边界上时，围绕的边界上时，围绕 f 的边的边界需要进行填充界需要进行填充（在模板匹配中，当模板（在模板匹配中，当模板的中心越过图像的边界时，相关的值通常的中心越过图像的边界时，相关的值通常并不重要，因此，填充被限制为模板宽度并不重要，因此，填充被限制为模板宽度的一半）。为表示方便，通常只关心奇数的一半）。为表示方便，通常只关心奇数大小的模板。大小的模板。 基于决策理论方法的识别基于决策理论方法的识别-匹配匹配-相关匹配相关匹配模板匹配的机理模板匹配的机理中心在

41、任意位置中心在任意位置 (x, y) 的模板的模板图像图像 f原点原点填充填充北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT23n相关匹配的举例相关匹配的举例n913913 的的Harricane Andrew飓风卫星图像，其中风眼清晰可见；飓风卫星图像，其中风眼清晰可见；n3131 大小的大小的飓风眼的模板飓风眼的模板；n显示为图像的相关系数（注意最亮点），显示为

42、图像的相关系数（注意最亮点），由于填充，该图像的原始由于填充，该图像的原始大小为大小为 943943 像素，但为显示，把它裁剪到原始图像大小。在像素，但为显示，把它裁剪到原始图像大小。在该图像中，灰度与相关值成正比，并且所有的负相关都截为该图像中，灰度与相关值成正比，并且所有的负相关都截为 0（黑），以简化该图像的视觉分析，相关图像的最亮点在接近飓风（黑），以简化该图像的视觉分析，相关图像的最亮点在接近飓风眼的位置清晰可见；眼的位置清晰可见；a)最大相关显示为一个白点，与飓风眼位置紧密对应最大相关显示为一个白点，与飓风眼位置紧密对应（此时，存在一（此时，存在一个最大值为个最大值为 1 的唯一匹

43、配）。的唯一匹配）。基于决策理论方法的识别基于决策理论方法的识别-匹配匹配-相关匹配相关匹配北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT24基于决策理论方法的识别基于决策理论方法的识别-最佳统计分配器最佳统计分配器n就像在大多数处理度量和判读领域中一样，就像在大多数处理度量和判读领域中一样，在模式识别中考在模式识别中考虑概率统计问题也十分重要虑概率统计问题也十分重

44、要。n基于概率统计理论，推导一种最佳模式识别方法，使得产生基于概率统计理论，推导一种最佳模式识别方法，使得产生的分类错误的概率在平均意义上最低。的分类错误的概率在平均意义上最低。n来自来自 i 类的特定模式类的特定模式 x 概率表示为概率表示为 p(i /x）。如果模式分）。如果模式分类器判断类器判断 x 来自来自j 类，而实际上它来自类，而实际上它来自i 类，那么分类器类，那么分类器出现一次失败的分类，出现一次失败的分类，导致一次损失，表示为导致一次损失，表示为 Lij。n因为模式因为模式 x 可能属于所有可能属于所有 W 个类中的任何一个类，所以，个类中的任何一个类，所以，将模式将模式 x

45、 指定为指定为 j 类的类的平均损失平均损失为为 n该公式称为该公式称为条件平均风险条件平均风险或或条件平均损失条件平均损失。 1/WjkjkkrxL px 北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT25基于决策理论方法的识别基于决策理论方法的识别-最佳统计分配器最佳统计分配器-基础基础n由概率论可知，有由概率论可知，有 p(A/B) = p(A)p(B/A)

46、/ p(B)，则上式变，则上式变为：为： 11/WjkjkkkrxL p xPp x 其中，其中，p(x /k）是来自）是来自 k 类的模式的概率密度函数，类的模式的概率密度函数， P(k) 是是 k 类出现的概率。类出现的概率。n由于由于 1/p(x) 是正的，并且对所有的是正的，并且对所有的 rj(x) 都为正，故可以从上式中省都为正，故可以从上式中省略掉此项，而不影响略掉此项，而不影响 rj(x) 的相对大小排序，的相对大小排序，平均损失简化为平均损失简化为：n假设分类器有假设分类器有 W 个可能的类，任何给定的未知模式可从这个可能的类，任何给定的未知模式可从这些类中选择。如果分类器对每

47、个模式些类中选择。如果分类器对每个模式 x 计算计算r(x)，并且把该，并且把该模式所具有的最低损失赋给相应的类，则对所有判决来讲，模式所具有的最低损失赋给相应的类，则对所有判决来讲，总体平均损失将是最低的。总体平均损失将是最低的。这种总体平均损失最佳的分类这种总体平均损失最佳的分类器称为器称为贝叶斯分类器贝叶斯分类器。 1/WjkjkkkrxL p xP 北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommuni

48、cation Centre, BUPT26基于决策理论方法的识别基于决策理论方法的识别-最佳统计分配器最佳统计分配器-基础基础n如果如果 ri(x) 0 时时，输出为，输出为 +1，模式，模式 x 识别为属于识别为属于 1 类；类；n当当 d(x) 0 时时，输出为，输出为 -1，模式，模式 x 识别为属于识别为属于 2 类；这与前面介绍类；这与前面介绍的单个决策函数是一致的。的单个决策函数是一致的。n当当 d(x) = 0 时时，模式，模式 x 位于分割两个模式类的决策面上，处于不能位于分割两个模式类的决策面上，处于不能确定的状态，需要给出决策边界条件。确定的状态，需要给出决策边界条件。n令

49、上式令上式 d(x) 等于等于 0，给出决策边界：，给出决策边界：11( )niinid xw xw 11( )0niinid xw xw 北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT45决策理论模式识别决策理论模式识别-神经网络神经网络-两个模式类的感知器两个模式类的感知器n上式是在上式是在 n 维模式空间中的一个超平面方程。维模式空间中的一个超平面方程。在几何

50、上，前在几何上，前 n 个系数确定超平面的方向，最个系数确定超平面的方向，最后一个系数后一个系数 wn+1 与从原点到超平面的垂直距与从原点到超平面的垂直距离成正比。当离成正比。当 wn+1 =0，则超平面经过模式空，则超平面经过模式空间的原点；类似地，如果间的原点；类似地，如果 wj =0，则超平面平，则超平面平行于行于 xj 轴。轴。n上图中的阈值单元输出取决于上图中的阈值单元输出取决于 d(x) 的符号，把的符号，把 wn+1 项移到项移到等式右边，此时系统的输出为：等式右边，此时系统的输出为：n该实现等同于右图所示，唯一不同是阈值函数被量该实现等同于右图所示，唯一不同是阈值函数被量 -

51、 wn+1 所取代，且所取代，且没有了常量单位输入。没有了常量单位输入。11111, 1, niininiiniw xwOw xw 北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT46决策理论模式识别决策理论模式识别-神经网络神经网络-两个模式类的感知器两个模式类的感知器n另一个常用的公式是扩充这些模式向量另一个常用的公式是扩充这些模式向量，方法是附加一个额，方法是附

52、加一个额外的第外的第 (n+1) 个元素，不管类成员是什么，该元素总等于个元素，不管类成员是什么，该元素总等于 1。即扩充后的模式向量即扩充后的模式向量 y 是从模式向量是从模式向量 x 创建的，令创建的，令 yi = xi，i=1,2,n，并附加一个额外的元素，并附加一个额外的元素 yn+1 = 1。则响应变为：。则响应变为：n其中其中 y = (y1,y2,yn,1)T 是一个扩充的模式向量；是一个扩充的模式向量； w = (w1,w2,wn+1)T 是加权向量；是加权向量；n通常是更为方便的表达式。通常是更为方便的表达式。n不管采用哪个公式表示，不管采用哪个公式表示，关键问题关键问题是使

53、用来自两个类的一个是使用来自两个类的一个给定模式向量给定模式向量训练集找到训练集找到 w。11( )nTiiid xw yw y 北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT47神经网络神经网络-训练算法训练算法-线性可分的类线性可分的类n线性可分的类：线性可分的类：用于求两个线性可分训练集的权重向量解用于求两个线性可分训练集的权重向量解的一种简单的一种简单迭代算

54、法迭代算法：n对于两个分别属于对于两个分别属于 1 和和 2 的扩充模式向量的训练集，令的扩充模式向量的训练集，令 w(1) 表示任意选择的一个初始加权向量。表示任意选择的一个初始加权向量。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 是一个正的修正增量，若是一个正的修正增量，若是一个常量，该算法

55、有时称是一个常量，该算法有时称为为固定增量校正准则固定增量校正准则。当两个类的整个训练集循环通过机器而当两个类的整个训练集循环通过机器而不出现任何错误时，该算法收敛。如果不出现任何错误时，该算法收敛。如果模式的两个训练集是线性可分的，那么模式的两个训练集是线性可分的，那么固定增量校正准则会在有限步内收敛。固定增量校正准则会在有限步内收敛。北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Cen

56、tre, BUPT48神经网络神经网络-训练算法训练算法-线性可分的类线性可分的类n感知机算法举例感知机算法举例n下图下图 (a) 所示的两个训练集，每个训练集由两个模式组成，两个训所示的两个训练集，每个训练集由两个模式组成，两个训练集是线性可分的，故可以采用上述算法。练集是线性可分的，故可以采用上述算法。n在应用算法之前，进行模式扩充，对在应用算法之前，进行模式扩充，对 1 类生成训练集类生成训练集 (0,0,1)T, (0,1,1)T，对，对 2 类生成训练集类生成训练集 (1,0,1)T, (1,1,1)T，令，令 c=1，w(1)=0，并按如下步骤顺序提交这些模式：并按如下步骤顺序提交

57、这些模式：北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT49神经网络神经网络-训练算法训练算法-线性可分的类线性可分的类n感知机算法举例感知机算法举例n从中看到，由于错误分类，在第从中看到，由于错误分类，在第 1 步和第步和第 3 步进行了权重向量的修步进行了权重向量的修正；正；n由于仅当算法由于仅当算法对所有训练模式完全无误迭代时，才能得到一个解对所有训练模式完全

58、无误迭代时，才能得到一个解，因此，需要再次提交训练集，学习过程继续下去：令因此，需要再次提交训练集，学习过程继续下去：令 y(5)=y(1)，y(6)=y(2)，y(7)=y(3)，y(8)=y(4)，并以同样的方式进行。，并以同样的方式进行。n当当 k=14 时收敛，得到权重向量为时收敛，得到权重向量为 w = (-2, 0, 1)T，相应的决策函数，相应的决策函数为为 d(y) = - 2y1 + 1。n通过令通过令 xi=yi，返回原始模式空间，得返回原始模式空间，得 d(x) = -2x1+1。当集合等于。当集合等于 0，它变成了下图它变成了下图 (b) 所示的所示的决策边界方程决策边

59、界方程。北京邮电大学信息与通信工程学院多媒体技术中心门爱东北京邮电大学信息与通信工程学院多媒体技术中心门爱东 Digital Image Processing 对象识别对象识别, Men Aidong, Multimedia Telecommunication Centre, BUPT50神经网络神经网络-训练算法训练算法-不可分的类不可分的类n不可分的类不可分的类n实际中，线性可分模式类是个例外，通常情况并非如此。上世纪六实际中，线性可分模式类是个例外，通常情况并非如此。上世纪六七十年代后，大多数研究转向了不可分的模式类。随着神经网络训七十年代后，大多数研究转向了不可分的模式类。随着神经网络

60、训练取得的进展，许多不分开模式类处理方法已成为历史，但早期的练取得的进展，许多不分开模式类处理方法已成为历史，但早期的德尔塔德尔塔 Delta 规则还在继续使用。规则还在继续使用。nDelta 规则规则n原始的原始的 Delta 规则称为规则称为感知训练的感知训练的 Widrow-Hoff 或最小均方或最小均方 (LMS) delta 规则规则，它使得在任何训练步骤中实际响应和期望响应之间的误，它使得在任何训练步骤中实际响应和期望响应之间的误差最小。差最小。n考虑考虑准则函数准则函数为为n其中，其中，r 是期望响应，即当扩充后的训练模式向量是期望响应，即当扩充后的训练模式向量 y 属于类属于类