数字图像处理学：第10章 模式识别的理论与方法（第10-2讲）.ppt

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