第10章 模式识别的理论与方法

数字图像处理学第10章模式识别的理论和方法（第二讲）,4.最小距离分类器线性分类器中重要的一类是用输入模式与特征空间中作为模板的点之间的距离作为分类的准则。假设有m类，给出m个参考向量与模式类相联系。,对于的最小距离分类就是把输入的新模式X分为类，其分类准则就是X与参考模式原型之间的距离，与哪一个最近就属于哪一类。X与之间的距离可表示为：,(1013),由此可设定最小距离判别函数,为：,(1014),由上边的判别函数可知，在分类中，如果，则。由式(1014)可见是一个线性函数，因此，最小距离分类器也是一个线性分类器。在最小距离分类中，在决策边界上的点与相邻两类都是等距离的，这种方法就难于解决，此时必须寻找新的特征，重新分类。,这种分类还可以用决策区域来表示。例如，有二类问题，其模板分别为，当距离或者,则，并可用决策区域表示，如图104所示。将模板作连线，再作平分线，平分线左边为区域，平分线右边为区域，为决策区域，中间为决策面。在这种分类中，两类情况界面为线，决策区为两平面。对于三类情况，界面为超平面，决策区为半空间。,5.最近邻域分类法,最近邻域分类法是图像识别中应用较多的一种方法。在最小距离分类法中，取一个最标准的向量作为代表。将这类问题稍微扩张一下，一类不能只取一个代表，把最小距离的概念从一个点和一个点间的距离扩充到一个点和一组点之间的距离。这就是最近邻域分类法的基本思路。,设分别是与类相对应的参考向量的m个集合，在中的向量为，即，也就是,(1015),输入特征向量X与之间的距离用下式表示,(1016),这就是说，X和之间的距离是X和中每一个向量的距离中的最小者。,如果X与之间的距离由式(1013)确定，则其判别函数为,(1017),设,(1018)则,(1019),其中是特征的线性组合，决策边界将是分段线性的。如图105所示，有一个两类判别问题，类的代表为，类的代表为。如果有一个模式送入识别系统，首先要计算它与每个点的距离，然后找最短距离。这种方法的概念简单，分段线性边界可以代表很复杂的曲线，也可能本来是非线性边界，现在可用分段线性来近似代替。,6.非线性判别函数线性判别函数很简单，但也有缺点。它对于较复杂的分类往往不能胜任。在较复杂的分类问题中就要提高判别函数的次数，因此根据问题的复杂性，可将判别函数从线性推广到非线性。非线性判别函数可写成下式形式。,（1020）,式(1020)是一个二次型判别函数。通常二次型判别函数的决策边界是一个超二次曲面。,分段线性判别函数是一种特殊的非线性判别函数，它所确定的决策面是由若干超平面段组成。由于其基本组成仍然是超平面，与一般的超曲面相比仍然很简单。又由于它是由多个超平面组成的，它可以逼近各种形状的超曲面，具有很强的适应能力。一般情况下，分段线性判别函数比一般线性判别函数错误率要小，但又比非线性判别函数简单。,一般情况，如果对类再取个代表点，也就是把属于类的样本区域再分为个子区域，即，这里表示第i类的第l子区域。用表示该子区域中样本的均值向量，并以它作为该子区域的代表点，可定义判别函数如下：,（1041）如果则归到类，这样的分类器也叫分段线性分类器。,现在我们把每一类别分为若干个子类，也就是（1042）对每一类定义一个线性判别函数，即（1043）式中和分别是子类的权向量及阈值。,类的线性判别函数为（1044）,对于c类问题可以定义c个判别函数，。决策规则为：则判决（1045）由上边所述，对于任意样本向量，一定有某个子类的判别函数比其他各子类的判别函数值大。如果具有最大值的判别函数，则把子类归到子类所属的类。这样的决策面就是分段线性的，其决策面方程由各子类的判别函数确定。,10.2.2统计分类法,前边谈到的分类方法是在没有噪声干扰的情况下进行的，此时测得的特征确能代表模式。如果在抽取特征时有噪声，那么可能抽取的特征代表不了模式，这时就要用统计分类法。,用统计方法对图像进行特征抽取、学习和分类是研究图像识别的主要方法之一，而统计方法的最基本内容之一是贝叶斯(Bayes)分析，其中包括贝叶斯决策方法，贝叶斯分类器，贝叶斯估计理论，贝叶斯学习，贝叶斯距离等等。,1.贝叶斯公式,在古典概率中就已有为大家所熟悉的贝叶斯定理。,(1021),式中是n个互不相容的事件，是事件的先验概率，是A在已发生条件下的条件概率。贝叶斯定理说明在给定了随机事件的各先验概率及条件概率时，可计算出事件A出现时事件出现的后验概率。,贝叶斯公式常用于分类问题和参数估值问题中。假如设X表示事物的状态或特征的随机变量，它可以代表图像的灰度或形状等；设代表事物类别的离散随机变量。对事物（比如是图像的亮度或形状）进行分类就可以用如下公式,(1022),式中称为的先验概率，它表示事件属于的预先粗略了解；表示事件属于类而具有X状态的条件概率；叫做X条件下的后验概率，它表示对事件X的状态作观察后判断属于类的可能性。,由式(1022)可见，只要类别的先验概率及X的条件概率已知，就可以得到类别的后验概率。再加上最小误差概率或最小风险法则，就可以进行统计判决分类。,在参数估值问题中，贝叶斯公式中的二个变量常常为连续随机变量，如果写作变量X及参数，则有如下之公式形式,(1023),通过上式，由参数的先验分布及预先设定的条件分布，即可求得参数的后验分布。贝叶斯公式是参数估值的有力工具。,2贝叶斯分类法假设有两类，每类用两种统计参数代表，即,如果用贝叶斯规则的话，结果是,(1025),显然，,在这里起到了判别函数的作用。,在应用中，为方便起见，常取,的对数形式，即,(1026),也就是,(1027),或者,(1029),在两类问题中，分界面为,(1028),假如一个模式遵循正态分布，它的均值为，协方差矩阵是，设m=2，可得到其决策分界面如下：,因为：,是正态分布，所以,(1030),则有,则有,在这种情况下，决策边界成为线性的。所以，求两类分类问题时，如果每类都是正态分布，但有不同的协方差矩阵，分界是二次函数，如果N很大，求相当麻烦。,问题在于选择适当的决策，以使平均风险取极小，或者使条件平均风险的极大值取极小。这种使平均风险取极小的最优决策规则称为贝叶斯规则。,如果是在使平均损失极小的意义上的最优决策，则,223贝叶斯分类器,多类贝叶斯分类器如图106所示。其中与的乘积就是第i类判别函数。如果，对于一切的情况下，则分类器就把给定的一个特性量归于类。,二类贝叶斯分类器如图107所示。在这类范畴的问题中，有时不制定二个判别函数D1(X)和，而是定义一个判别函数,(1042),若，则决策，否则决策。,2.3特征的抽取与选择,在模式识别中，确定判据是重要的。但是问题的另一面，即如何抽取特征也是相当重要的。如果特征找不对，分类就不可能准确。这好比医生看病，如果只注意病人穿什么衣服，头发的长短，就不会正确诊断。当然，特征是很多的，如果把所有的特征不分主次全都罗列出来，N会很大，这也会给正确判断带来麻烦。,例如，如图108所示。有两类模式，用两个特征来表达。在上的投影为ab、cd，在上的投影为ef、gh。那么，由图可见，ac这一段肯定是属于的，bd肯定是属于的，但是cd段就难以分出属于哪一类。,一种设想是把坐标轴作一个旋转，变成y1y2，此时不再去测量x1x2，而是去测量y1y2。如图109所示。由图可见，这时检测y1当然也分不清，可是检测y2就可以分得很清。这说明当作一变换后，y2是一个很好的特征。,特征提取的方法是很多的。从一个模式中提取什么特征，将因不同的模式而异，并且与识别的目的、方法等有直接关系。常用的方法有离散直角坐标系中的弗里曼链码法。它可以方便地描述在离散直角坐标系中的曲线。,图1010(a)是在8邻接定义下的弗里曼链码。位于坐标系内的任一条曲线便可用一个数字序列来表示。图10.10(b)示出了一条曲线，若从a点出发可编出其链码如下：100123110777645421。,在提取边缘细条的过程中，会出现断线，因此，断线的接续是特征提取中的一个处理步骤。最基本的方法是利用膨胀和收缩技术。所谓膨胀是以二值图像内为1的像素为中心，强制性的把与其4邻接或8邻接的相邻像素都变成1。如图1011所示。,收缩方法是把值为0的像素作为中心，强制性地把与其4邻接或8邻接的相邻像素变成0。这样连续膨胀n次，再连续收缩n次，就可以把断线长度为2n以内的线接续起来。,接续断线的另一种方法是山脊线寻迹法。具体做法是使用某种方法已找出直到点为止的一段山脊线，接着判断点，等点是否也位于该山脊线的延长线上。,判断的标准就是看这些点的微分值是否足够大，这些点周围的灰度变化斜率最大的方向是与线的延长线方向垂直。这些点与周围延长线方向成直角方向上的点相比灰度值是否为极大值等等。这种方法碰到折点及分枝点比较难于判断。,在特征提取中，关于线的检测及表达方法有最小二乘法曲线拟合法，霍夫变换法等等。在进行线提取时，往往不是简单地用一些直线段把检测出来的点连接起来就行了，而是希望用某个数学方程式所描述的曲线去逼近检测出来的点列。这种用数学方程式去近似图像中各种线条的方法称为曲线拟合。,最简单的曲线拟合是用直线方程去近似所给出的点列，这种方程有y=g(x)之形式。在拟合处理中自然需要一定的标准去评价该方程与点列的近似程度，常用的评价标准是观察直线方程所代表的直线与点列之间的距离大小。,式(1043)是以直线方程与各点之差的绝对值的和为最小作为评价标准；式(1044)是以差的平方和最小作为评价标准，通常称为最小二乘法判决函数；式(1045)是以差值中的最大值是否小于某一标准进行评价。,霍夫变换也广泛用于线检测，它的概念已在第八章中作了介绍，在此不再赘述。除此之外，用于线检测的特征提取方法还有很多，如用曲率作为曲线的特征，曲线分割，距离变换、骨格化及细化等均是在特征提取处理中常用的方法。,在上图所说明的特征提取的例子中，用坐标旋转的方法得到了既少又好的特征。空间坐标的旋转就是特征空间的线性变换。空间怎样变换才能找到较好的特征呢？其普遍的方法是把每一类的协方差矩阵变成对角形矩阵，在变换后的矩阵中取其特征向量及与其相对应的特征值，然后，把特征向量按其特征值的大小排列起来。,特征值大的那个特征向量就是最好的特征。另外，在变换后的空间中，如果有m个彼此关联的特征，可采用前n个最大特征值对应的特征向量作为特征，这样既可保证均方误差最小，又可大大减少特征的数目。,另外一个途径是寻找一种变换，使同一类向量靠得更近些，以便把它聚合到一起去。在这种思想指导下，可以找每一类点与点之间的距离，使它最小化。这样作是应用特征值最小的那些特征向量。,假定有两类模式，测量两种特征都是正态分布，均值是和。这两个分布离得越远越容易识别。所谓离得远不一定是均值