数字图像处理学：第8章 图像分析（第8－1）.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数字图像处理学,第,8,章,图像分析,（第一讲）,对图像进行增强、恢复、编码等处理时，输入是图像，所要求的输出是一幅近似于输入的图像，这是此类处理的一个特点。图像处理的另一个主要分支是图像分析或景物分析。这类处理的输入仍然是图像，但是所要求的输出是已知图像或景物的描述。这类处理基本上用于自身图像分析和模式识别一类的领域。,1,）输入是文字组成的二值图像，输出是读出该段文字；,2,）输入是血球照片，输出是血球数量；,3,）输入是细胞图像，输出是细胞类型；,4,）输入是遥感照片，输出是地貌、植被描述等。,这些都是图像分析的典型例子。,描述一般是针对图像或景物中的特定区域或目标。为了描述，首先要进行分割，有些分割运算可直接用于整个图像，而有些分割算法只适用于已被局部分割的图像。例如，分割染色体的处理，可先用设置门限的方法把染色体和背景分割开来，然后可采用尺寸大小、形状等准则进一步将其分割成单个染色体。,值得注意的一点是，没有唯一的、标准的分割方法，因此，也就没有规定成功分割的准则。,本章只讨论一些最基本的分割、描述方法。,8.1,分割,(segmentation),分割的目的是把图像空间分成一些有意义的区域。例如一幅航空照片，可民分割成工业区、住宅区、湖泊、森林等等。可以以逐个像素为基础去研究图像分割，也可以利用在规定领域中的某些图像信息去分割。,分割的依据可建立在相似性和非连续性两个基本概念之上,。,7.1.1,灰度阈值法分割,7.1.2,样板匹配,7.1.3,区域生长,7.1.4,区域聚合,假如有如下形状的直方图,图,71,图像,f,(,x,y,),的直方图,由直方图可以知道图像,f,(,x,y,),的大部分像素灰度值较低，其余像素较均匀地分布在其他灰度级上。由此可以推断这幅图像是由有灰度级的物体叠加在一个暗背景上形成的。,可以设一个阈值,T,，把直方图分成两个部分，如图所示。,T,的选择要本着如下原则,:,B,1,应尽可能包含与背景相关连的灰度级，而,B,2,则应包含物体的所有灰度级。,当扫描这幅图像时，从,B,1,到,B,2,之间的灰度变化就指示出有边界存在。当然，为了找出水平方向和垂直方向上的边界，要进行两次扫描。也就是说，首先确定一个门限,T,，然后执行下列步骤：,第一，对,f,(,x,y,),的每一行进行检测，产生的图像的灰度将遵循如下规则,(8,1),式中,L,E,是指定的边缘灰度级，,L,B,是背景灰度级。,第二，对,f,(,x,y,),的每一列进行检测，产生的图像的灰度将遵循下述规则,(8,2),为了得到边缘图像，可采用下述关系,（,8,3,）,为了提高边缘抽取能力，一种方法是把图像变成二值图像。例如，图像,f,(,x,y,),的灰度级范围是,(,Z,l,Z,h,),，设,T,是,Z,l,和,Z,h,之间的一个数，那么,f,t,(,x,y,),可由式,(7,4),表示,(8,4),另一方法是把规定的灰度级范围变换为，而把范围以外的灰度级变换为,0,，例如,(8,5),(8,6),那么，在分割中如何设置最佳阈值呢？,假设一幅图像是由背景和物体组成。其中，物体像素的灰度级具有正态概率密度,p,(,z,),，其均值为 ，方差为 ；而背景像素的灰度级也具有正态概率密度,q,(,z,),，其均值为 ，方 差为 。,物体占图像总面积的比为 ，背景占总面积的比为 ，所以这幅图像总的灰度级概率密度为,(8,7),假设对图像设置一阈值 ，并且把小于 的全部点称为目标物体点，而把大于等于 的所有点称为背景点。,把背景错归为物体点的概率为 ，,把物体点错归为背景点的概率为 ，,则有,(8,8),(8,9),总的错分概率为,(8,10),要求得式,(7,10),的最小阈值，可将上式对,t,微分，并令其结果为,0,，则得到,(8,11),因为,(8,12),(8,13),代入式,(8,11),，并取对数,（,8,14),或者,（,8,15),由这个二次方程可以求解出,t,值。如果 ，那么,(8,16),这就是最佳门限,对于复杂图像，在许多情况下对整幅图像用单一阈值不能给出良好的分割结果。例如，图像是在光亮背景上的暗物体，但由于照射光的不均匀，虽然物体与背景始终有反差，但在图像的某一部分物体和背景两者都比另一部分亮。,因此，在图像的一部分能把物体和背景精确地分开的阈值，对另一部分来说，可能把太多的背景也当作物体分割下来了。,克服这一缺点有如下一些方法：,如果已知在图像上的位置函数描述不均匀照射，就可以设法利用灰度级校正技术进行校正，然后采用单一阈值来分割；,另外一种方法是把图像分成小块，并对每一块设置局部阈值。但是，如果某块图像只含物体或只含背景，那么对这块图像就找不到阈值。这时，可以由附近的像块求得的局部阈值用内插法给此像块指定一个阈值。,7.1.1,灰度阈值法分割,7.1.2,样板匹配,7.1.3,区域生长,7.1.4,区域聚合,在数字图像处理中，样板是为了检测某些不变区域特性而设计的阵列。样板可根据检测目的不同而分为点样板、线样板、梯度样板、正交样板等等。,点样板的例子如图,8,2,所示。下面用一幅具有恒定强度背景的图像来讨论。,-1,-1,-1,-1,8,-1,-1,-1,-1,图,8,2,点样板,假定小 块 之 间 的 距 离 大 于,，这里 、分别是在,x,和,y,方向的取样距离，用点样板的检测步骤如下：,1,）、点样板,样板中心（标号为,8,）沿着图像从一个像素移到另一个像素，在每一个位置上，把处在样板内的图像的每一点的值乘以样板的相应方格中指示的数字，然后把结果相加。如果在样板区域内所有图像的像素有同样的值，则其和为零。另一方面，如果样板中心位于一个小块的点上，则其和不为零。,如果小块在偏离样板中心的位置上，其和也不为零，但其响应幅度比起这个小块位于样板中心的情况时要小一些，这时，可以采用阈值法清除这类较弱的响应，如果其幅度值超过阈值，就意味着小块被检测出来了；如果低于阈值则忽略掉。,例如，设 代表,3,3,模板的权，并使 为模板内各像素的灰度值。从上述方法来看，应求两个矢量的积，即：,(8,24),式中,(8,25),(,8,26),设置一阈值,T,，如果,(,8,27),我们认为小块已检测出来了。这个步骤可很容易地推广到,n,n,大小的样板，不过此时要处理,n,2,维矢量。,线检测样板如图,7,3,所示。其中，样板,(a),沿一幅图像移动，它将对水平取向的线（一个像素宽度）有最强的响应。对于恒定背景，当线通过样板中间一行时出现最大响应；样板,(b),对,45,方向的那些线具有最好响应；样板,(c),对垂直线有最大响应；样板,(d),则对,-45,方向的那些线有最好的响应。,图,7,3,线样板,设 是图,7,3,中四个样板的权值组成的九维矢量。与点样板的操作步骤一样，在图像中的任一点上，线样板的各个响应为 ，这 里,i,=1,、,2,、,3,、,4,。,此处,X,是样板面积内九个像素形成的矢量。给定一个特定的,X,，希望能确定在讨论问题的区域与四个线样板中的哪一个有最相近的匹配。如果第,i,个样板响应最大，则可以断定,X,和第,i,个样板最相近。,换言之，如果对所有的 值，除 外，有：,(8,28),就 可 以 说 和 第 个 样 板 最 接近。如果 ，,=2,、,3,、,4,，可以断定 代表的区域有水平线的性质。,对于边缘检测来说也同样遵循上述原理。通常采用的方法是执行某种形式的二维导数。类似于离散梯度计算，考虑,大小的模板，如图,7,4,所示。,图,8,4 3 3,样板,考虑,的图像区域，及 分别用下式表示,(8,29),(8,30),采用绝对值的一种定义为,在,e,点的梯度为,(8,31),(8,32),梯度模板如图,8,5,所示。,图,8,5,梯度样板,把图,7,5,的区域与式,(8,29),比较，可以看出,G,x,为第一行和第三行的差，其中最靠近,e,的元素（,b,和,h,）,的加权等于角偶上权值的两倍，因此，,G,x,代表在,x,方向上导数的估值。式,(8,31),和式,(8,32),可用图,8,5,中两个样板来实现。,边缘检测也可以表示成矢量，其形式与线样板检测相同。如果,X,代表所讨论的图像区域，则：,(8,33),(8,34),这里 ，是图,7,5,中的两个样板矢量。分别代表它们的转置。,这样，梯度公式,(8,31),和式,(8,32),变为式,(8,35),和式,(8,36),的形式。,(8,35),(8,36),检测点、线和边缘的矢量公式可应用于,1977,年费雷和陈提出的一种检测技术。他们提出的检测方法是这样实现的，假定有两个只有三个元素的样板，此时，则有两个矢量,W,1,和,W,2,，它们都是三维的。又假定,W,1,和,W,2,都是正交的和归一 化 的，因 此，它 们 都 有 单 位 幅 值。,和 项分别等于在相应矢量,W,1,和,W,2,上,X,的投影。对于,W,1,来说,(8,37),这里 是两个矢量间的夹角。,因为 ，因此有,(8,38),这就是,X,在,W,1,上的投影，这种情况如图,8,6,所示。对,W,2,来说，亦然。,图,8,6 X,向单位矢量,W,1,的投影,现在假 定 有 三 个 正 交 的 单 位 矢,量,W,1,、,W,2,、,W,3,分别与三个三点样板相对 应，那么乘积 代表在三个矢量,W,1,、,W,2,、,W,3,上的投影。其几何关系 如 图,7,7,所示。,图,77,X,向 确定的子空间的投影,假定样板和是检测线的，而是检测点的，,X,代表的这个区域是更象一条线呢还是更象一个点呢？为了回答这一问题，把,X,投影到,W,1,、,W,2,、,W,3,的子空间上去，,X,和子空间的夹角可以说明,X,更接近于线还是更接近于点。,这可以从图,8,7,的几何关系上看出来。,X,在,由,W,1,和,W,2,所确定的平面上投影的幅度可由式,(8,35),表示，而,X,的幅度由下式表示：,(8,39),X,和其投影间的夹角为：,(8,40,),同理，向,W,3,子空间上投影的夹角可由下式表示：,(8,41),那么，如果,，就说明,X,所代表的区域更接近于线特性而不是点特性。,如果考虑,3,3,的模板，则问题就成为维的，但前边讨论的概念仍然适用。这里，需要个维正交矢量形成一个完整的基。这个模板如图,8,8,所示。,其中前四个模板,(a),、,(b),、,(c),、,(d),适合于边缘检测；,(e),、,(f),、,(g),、,(h),四块模板适合于检测线；最后一块模板,(i),则正比于一幅图像中模板所在区域的像素平均值。,图,8,8,正交模板,图,8,8,正交模板,如果由,X,代表的,3,3,区域，并假定 矢,W,i,量，,i,=1,2,3,，,9,是归一化的，则有：,(8,42),(8,43),式中 分别是,X,向边缘、线和平均子空间投影的幅度。,(8,44),同样道理，有,(8,45),(8,46),式中 是 与它在边缘、线和平均子空间投影之间的夹角。,(8,47),采用这种检测方法可扩展到其它基与维数，只要基本矢量是正交的就可以。,7.1.1,灰度阈值法分割,7.1.2,样板匹配,7.1.3,区域生长,7.1.4,区域聚合,分割的目的是要把一幅图像划分成一些区域，对于这个问题的最直接的方法是把一幅图像分成满足某种判据的区域，也就是说，把点组成区域。为了实现分组，,其次要确定一个区域与其他区域相区别的特征，,最后还要产生有意义分割的相似性判据。,、,首先要确定区域的数目，,为了实现分组，,1),、首先要确定区域的数目,2),、其次要确定一个，区域与其他区域相区别的特征，,3,）、最后还要产生有意义分割的相似性判据。,分割区域的一种方法叫区域生长或区域生成。假定区域的数目以及在每个区域中单个点的位置已知，则可推导一种算法。从一个已知点开始，加上与已知点相似的邻近点形成一个区域。,这个相似性准则可以是灰度级、彩色、组织、梯度或其他特性。相似性的测度可以由所确定的阈值来判定。,它的方法是从满足检测准则的点开始，在各个方向上生长区域。当其邻近点满足检测准则就并入小块区域中，当新的点被合并后再用新的区域重复这一过程，直到没有可接受的邻近点时，生成过程终止。,图,7,9,示出了一个简单的例子。这个例子的相似性准则是邻近点的灰度级与物体的平均灰度级的差小于。图中被接受的点和起始点均用一短线标出，其中,(a),是输入图像；,(b),是第一步接受的邻近点；,(c),是第二步接受的邻近点；,(d),是从开始生成的结果。,图,8,9,区域生长简例,5,5,8,6,4,8,9,7,2,2,8,3,3,3,3,3,8,8,相似性准则是邻近点的灰度级与物体的平均灰度级的差小于,8,5,5,8,6,4,8,9,7,2,2,8,3,3,3,3,3,8,8,第二步：,8,7,5,5,8,6,4,8,9,7,2,2,8,3,3,3,3,3,6,另一种区域生长：,7,8,7.1.1,灰度阈值法分割,7.1.2,样板匹配,7.1.3,区域生长,7.1.4,区域聚合,区域聚合可直接用于图像分割。它要求聚合中的各个点必须在平面上相邻接而且特性相似。区域聚合的步骤是首先检查图像的测度集，以确定在测度空间中聚合的位置和数目，然后把这些聚合的定义用于图像，以得到区域聚合。一般区域聚合技术可以说明如下：,首先可以在图片上定义某个等价关系。,例如，最简单的等价关系可定义为,：,如果 ，,就说明 与 等价。,任何在点的格子上的等价关系又可划分为等价类。例如,p,(,i,j,),的取值范围为,0,到,63,，就可以产生,64,个等价类的模板。如果关系满足，它的值等于，否则为。,模板的图像是两两不相交的，那么,64,个模板就会充满整个格子。这些等价的类又可以进一步分为最大连接的子集，把这个叫做连接分量。,连接性可以用点,(,i,j,),的邻点来定义。如连接邻点，连接邻点等等。连接邻点是四个非对角线上的个邻点，连接则是环绕的个邻点。,假如,R,是属于格子的子集，在,R,中存在一个点序列，第一个点是,p,1,，末一个点是,p,2,，属于格子的子集,R,的两个点,p,1,和,p,2,是被连接起来的，这样，相继的各点是连接相邻的。,通过这样的连接关系可以定义一个属于,R,的子集，这个子集形成一个区域。在这个区域中，任何点都与,R,有关。利用等价模板可分成最大的连接区域。然后，这些最大的连结区域又可以象搭积木一样形成有意义的分割。,年布赖斯和芬尼玛提出一种分割方法。这个方法如图,7,10,所示。图中,(a),是具有灰度级的,3,3,的,G,阵列，图,(b),是对,S,的分割结果。,其中图像格子为,G,，它是大格子,S,的子格子。,G,为,n,m,的格子，,S,是,(,2,n,+1,),(,2,m,+1),的大格子。在大格子中，,G,(,i,j,),点位于,S,的,(2,i,+1,2,j,+1),点上。,G,中的点与,S,中的点相对应，其中每一下标都是奇数，其余的点用来代表区域的边界。,以这种形式表现的区域，产生一种寻找最大连结区域的方法。,G,中的点与它上边和右边的点相比较，灰度级相同就合并，灰度级不同就插入边界线。把图像中的每个点都考虑了之后，整个图像就被分割成区域了。,在这个例子中，由于采用了连接等价关系，因此，由图,710,可见，在对角线方向上的等灰度级产生了隔开的区域。,图,8,10,布赖斯和芬尼玛分割方法,7.2,描绘,当一幅图像被分割或确定之后，通常希望用一系列符号或某种规则来具体的描述该图像的特征，以便在进一步的识别、分析或分类中有利于区分不同性质的图像。同时，也可以减少图像区域中的原始数据量。,一般把表征图像特征的一系列符号叫做,描绘子,。,对这些描绘子的基本要求是它们对图像的大小、旋转、平移等变化不敏感。也就是说，只要图像内容不变，仅仅产生几何变化，描绘图像的描绘子将是唯一的。,7.2.1,区域描绘,7.2.2,关系描绘,7.2.3,相似性描绘,7.2.4,霍夫变换,傅立叶描绘子,当一个区域边界上的点已被确定时，可以从这些点中提取信息。这些信息就可以用来鉴别不同区域的形状。假如一个区域上有,M,个点可利用，可以把这个区域看作是在复平面内，纵坐标为虚轴，横坐标为实轴。如图,7,11,所示。,图,7,11,在复平面上区域边界的表示,在边界上要分析每一个点的坐标,(,x,y,),可以用一复数来表示，即：,x,+,j y,。从边界上任一点开始，沿此边界跟踪一周就可以得到一个复数序列。这个复数序列叫做傅立叶描绘子（,FD,）。,因为,DFT,是可逆的线性变换，因此，在这个过程中没有信息的增益或损失。对于形状的这种频域表示作些简单的处理就可以避免对于位置、大小及方向的依赖性。当给定了任意的,FD,，用若干步骤可以使之归一化，从而不必考虑其原始形状的大小、位置及方向。,关于归一化问题可直接从,DFT,的性质中得出结论。例如，要改变轮廓大小，只要把,FD,分量乘一个常数就行了。由于傅立叶变换是线性的，它的反变换也会被乘以同样的常数。,又如，把轮廓旋转一个角度，只要把每一个坐标乘以 就可以使其旋转,角。由,DFT,的性质，在空域旋转了,角度，那么在频域中也会旋转,角度。关于轮廓起始点的移动，由,DFT,的周期性可以看到，在空域中有限的数字序列实际上代表周期函数的一个周期。,DFT,的系数就是这个周期函数的傅立叶表示式的系数。当轮廓的起点在空域中移动时，就相当于 在 频 域 中 把 第,K,次 频 率 系 数 乘以 ，这里,T,是周期的一部分，这部分即为起始点移动的部分。实际上这就是傅立叶变换的平移性质所导致的结果。当,T,从,0,2,变化时，则起点将把整个轮廓点经历一次。,给定一任意轮廓的,FD,后，归一化就可以执行一系列步骤，使轮廓有一个标准的大小、方向和起点。,在实际执行上还要考虑到如下一些问题：,1),、如果取样不均匀将会给问题带来困难，因此，在理论上采用均匀间隔取样；,2),、其次是,FFT,的算法要求阵列长度为的整数次幂，这样在采用,FFT,之前，应调整表达式的长度。为作到这一点，首先计算出轮廓的周长，然后用所希望的长度（当然应是的整数次幂）去除，然后从一个起始点去追踪，所希望的的幂次可以是大于序列长度的最小的的幂次。,实际上，输入到形状分析运算中的将是从取样图片中取出的轮廓。这个轮廓的周长近似等于轮廓的实际周长。如果原始图像的取样密度足够高的话，那么序列将是轮廓的很好的近似。,例如，图,7,12,所示的等边直角三角形，如果用个取向的链码来追迹则会比较粗糙，如果用个取向的链码来追迹，就得到精确得多的结果。由图,7,12,可见，追踪后的轮廓长度是直角边长度的倍。如图,7,13,所示，用个方向来追踪，其结果更接近实际轮廓的长度。,在归一化中，为了克服噪声和量化误差带来的扰动，应选择最大幅度系数做为归一化系数。,图,8,14,是飞机侧影的描绘结果。这些结果是如下得到的：计算边界的,NFD,（,应用,512,点）；保留最低频率的,32,个点而把其他的点位置,0,；求修改了的,512,阵列的傅立叶反变换，得到原始数据的近似。,图,8,14,采用傅立叶描绘子得到的外形,矩描绘子,采用傅立叶描绘子是以边界上的集合点（可用的）为基础。有时，一个区域以内部点的形式给出，那么，可用另外一种描绘子来描述。它对于图像的变换、旋转和大小变化都是恒定的，这就是矩描绘子。,设,f,(,x,y,),是一个二维函数，可用下式来表示,(,p,+,q,),阶矩,(8,48),式中,p,q,=0,1,2,。,中心矩由下式表示,(8,49),式中,对于数字图像来说，式,(8,49),可表示为下式,(8,50),如下,(8,51),(8,52),(8,53),如果假定所给图像,f,(,x,y,),在每一点,(,x,y,),处的灰度级是在,(,x,y,),点的,“,质量,”,，那么就可以定义,f,(,x,y,),的重心点 ，,其中,:,(8,54),(8,55),因此有,(8,56),由上边各式可得到三阶中心矩如下：,(7,57),(8,58),(8,59),(8,60),(8,61),(8,62),(8,63),(8,64),概括起来有如下一些结果：,定义归一化中心矩为：,(8,65),(8,66),利用第二阶和第三阶矩可导出七个不变矩组：,(8,67),Hu1962,已经证明了这个矩组对于平移、旋转和大小比例变化都是不变的，因此用它们可以描绘一幅给定的图像。,图像的矩不变量,。,不变量 原值 一半尺寸 映像 旋转,2,度 旋转,45,度,1,6.249 6.226 6.919 6.253 6.318,2,17.180 16.954 19.955 17.270 16.803,3,22.655 23.531 26.689 22.836 19.724,4,22.919 24.236 26.901 23.130 20.437,5,45.749 48.349 53.724 46.136 40.525,6,31.830 32.916 37.134 32.068 29.315,7,45.569 48.343 53.590 46.017 40.470,拓扑描绘子,拓扑学是研究图形性质的理论。拓扑特性可用于描绘图像平面区域。有些图形只要不撕裂或连结，其拓扑性质并不受形变的影响。,图,7,15,是带有两个孔的图形，如果把区域中孔洞数做为拓扑描绘子，显然这个性质不受伸长或旋转变换的影响，但是，如果撕裂或折叠时孔洞数就要变化了。,图,8,15,有两个孔的图形,图,8,16,有三个连结部分的图形,区域描绘的另一种有用的拓扑特性是连接部分的个数。一个集合的连接部分就是它的最大子集，在这个子集中的任何两点都可以用一条完全在子集中的曲线加以连接。图,8,16,所示的图形就有三个连接部分。,如果一幅图像的孔洞数为,H,，,连接部分为,C,，,则欧拉数的定义如下式所示。,欧拉数：,E,C,H,(8,68),也是拓扑特性之一。,如图,8,17(a),所示图形有一个连接部分和一个孔，所以它的欧拉数为,0,；而图,(b),有一个连接部分和二个孔，所以它的欧拉数为,-1,。,由直线表示的区域，按照欧拉数有一个简单的描述。如图,8,18,所示的多角网络，把这样的网络内部区域分成面和孔。如果设顶点数为,W,，,边缘数为,Q,，,面数为,F,，,将得到下列关系，这个关系称为欧拉公式。,(8,69,）即：,在图,7,18,的多角网络中，有个顶点、条边、个面、,1,个连接区、,3,个孔、因此，由式（,7,69,）可得到,:,7-11+2=1-3=-2,。,拓扑的概念通常在图像中确定特征区域很有用。,7.2.1,区域描绘,7.2.2,关系描绘,7.2.3,相似性描绘,7.2.4,霍夫变换,如果图像已经被分割为区域或部分，则图像描绘的下一步任务就是如何把这些元素组织成为有意义的关系结构。结构描绘一般是以文法概念为基础的。,例如，从一幅图像中已分割出图,7,19,所示的阶梯形结构，要用某种方法来描绘它，首先要定义一些基本元素，然后再定义一个重写规则就可以描绘出此阶梯形结构。图中,(a),是阶梯结构；,(b),是基本元素；,(c),是编码结构。,图,8,19,阶梯形结构之描绘,在描绘过程中规定基本元素为,a,和,b,，重写规则如下：,这里,S,和,A,是变量，元素,a,和,b,是常量。第一个规则说明,S,可以用基本元素,a,和变量,A,来代替，变量,A,可以用,b,和,S,来代替，也可以用,b,来代替。,如果用,bS,来代替,A,，则可以重复第一个规则的步骤。如果用,b,来代替，则步骤终止。这里假定都用,S,为起始点，第一个元素后面总是,b,。由上例可见只需三条重写规则就可以产生无穷多的相似结构。,串文法和语言,图,7,19,说明的编码结构是由符号的连接串组成的。这种符号串可以引用形式语言的概念来处理。,形式语言起源于,1950,年。诺姆、乔姆斯基用数学模型研究了文法，其目的是研究一种计算机文法，然后用这个文法去研究自然语言，以便计算机在翻译和解答问题的过程中解释自然语言。关于形式语言的研究和应用已渗透到编译设计、计算机语言、自动机理论及模式识别和图像处理领域中了。,首先，介绍一些最基本的定义,：,定义,:,V,为任何有限的符号集合；,在,V,范围内的一个句子、一串字符或字都是由集合中的符号组成的任何有限长度的串。,例 如，给 定,V,=0,1,，则,0,1,00,01,11,000,001,都是有效的句子。,定义,:,没有符号的句子为空句子，用,来代表。,用 代表由,V,中的符号组成的所有句 子集合，其中包括空句子。,代表 的句子集合。,例如，字母,语言是在字母范围内句子的任意集合。,形式语言理论主要研究文法及其性质。,串文法（或叫简单文法）是四元的，即,:,其中：,V,N,为非终端符集合（变量）；,V,T,为终端符的集合（常量）；,P,为产生式或重写规则集合；,S,为起始符或根符号。,假定,S,属于集合,V,N,，并且,V,N,和,V,T,是不相交的集合，字母,V,是,V,N,和,V,T,的合集。,由形式串文法,G,产生的语言记作,L,(,G,),，,这个语言就代表了一个模式。,由字符产生的语言,L,(,G,),满足两个条件：,每一串只由终端符组成,;,每一串都由,S,开始并用由,P,决定的产生式来生成。,例如，有文法,如果把第一个产生式用,m,-1,次，然后再用第二个产生式，由此可产生下列语言：,显然，这个文法产生的语言看作仅仅由这种形式的串组成，特定的串长取决于,m,。,m,可以是任意整数，可以把,L,(,G,),表达为下面的形式：,这个简单的文法可以用来产生无限多串组成的语言。,文法的类型,在讨论文法类型之前，为了便于叙述，规定所使用的符号如下：,非终端符,V,N,用大写英文字母表示，,如,:,S,A,B,C,；,终端符,V,T,用小写英文字母表示，,如,:a,，,b,，,c,，,；,终端字符串用英文字母表后边的 小 写 字 母 来 表 示，如,v,w,x,y,；,终端和非终端的混合字符串用小写的希腊字母来表示，如 。,我们把产生式的一般形式为 的文法叫短语结构文法，一般根据加于产生式的约束条件而把文法分成如下几类：,（）无约束文法,这种文法的产生式为 ：，其中箭头的左右端可以是任意形式的链。,（）上下文有关的文法,这种文法的 产 生 式 为,P,：，其,中 ，这种文法规定只 有当 出现在 和 串的前后关系,中时，才允许用串 来代替非终端符,。,此文法的产生式为 ：，其中 ，。这个文法并不考虑出现 的上下文就可以用串 去代替,变量。,（）上下文无关的文法,（）正则文法,这种文法也称为有限状态文法。它的产生式为,P,：,A,或,A,，这里,A,，,B,，,A,、,B,、均是单个符号。还可以选择另外一种产生式，即,P,：,A,和,A,。当然二种产生式中只能选一种，而不可同时选用。,上述四类文法有时依次称为型，型，型和型文法。,由它们产生的语言分别称为类型语言，类型语言，类型语言及类型语言。,由上述分类可以看出，所有的正则文法都是上下文无关的，所有上下文无关的文法都是上下文有关的，所有上下文有关的文法都是无约束的。对上述四类文法下面分别举例说明。,例：无约束文法,所以有,例：上下文有关的文法,所以,例：上下文无关的文法,所以,例：正则文法,所以,位置算子的运用,前述的字符串是一维结构，而图像是二维结构，因此，在用字符串来描绘图像时就需要建立一种相应的方法，把二维的位置关系缩减为一维形式。,串文法在图像描绘中大多数是从物体中抽取的联接线段为基础的。这种方法如图,7,20,所示。这是用有特定方向和长度的线段把结果编码。,图,7,20,用有方向的线段描绘区域边界,另外一种方法如图,7,21,所示。利用有向线段并用已定义的一些运算来描绘图像的某些部分。图中（,a,）,是用有向线段来表示某些区域，图（,b,）,是定义的某些运算。下面用一个具体例子来说明这些概念。,图,7,21,另一种描绘方法,例：图片描绘语言,这里（）表示与基本单元 方向相反的像元，而 的方向如 中所定义的那样。应用产生式产生一个像元 ，其后，跟随一个尚未定义的变量 。,但是，,A,1,分量所表示的结构的尾在这点上将和,d,的头相连，这是由规定的算法“”所决定的。变量,A,1,又 可分解为,C,+,A,2,，当然,A,2,尚未定义。,同样,A,2,又可分解为,d,*,A,3,。应用前三条产生式得到的结果如图,822,中,(a),，,(b),，,(c),所示。算子“”定义为尾到尾、头到头的连接方式。使用全部产生式所得到的最后结果示于图,722(f),中。,这种文法只能产生一个结构。如果在产生式的规则中引入递归规则（变量有代替自己的能力），则这种,PDL,文法所产生的结构可扩展到各种结果。,图,8,22 PDL,结构组成步骤,例：利用例的条件，定义下列产生式规则,如果顺次应用这些产生式就会产生图,722,中,(f),的结果。,例：染色体特征的描绘,描绘染色体的文法所用的基本像元如图,7,23(a),所示。这些基本像元是对染色体沿边界顺时针方向循迹而检测出来的。典型的半中期和末期染色体的形状如图,8,23(b),所示，描绘文法如下：,其中算子,“,”,用来描绘在按顺时针方向追迹边界时在产生式中各项的可连接性。在这个文法中，,S,和,T,均为起始符，,S,可产生相应于半中期染色体的结构，可以产生相应于末期染色体的结构。,图,8,23,用边界轨迹描述染色体,高维文法,串文法适用于那些图像元素的连接可以用从头到尾或用其他连续形式的图像元素的描绘。在这里我们考虑一种更普遍的文法描绘途径，它有能力描绘更高级的图像元素。,高维文法之一是所谓树文法。树文法中所定义的树是一个或一个以上的节点的集合。其中有一个唯一的指定的节点为根；剩下的节点划分为,m,个不相交的集合，这些集合为 ，把 叫做 的子树；树尖是树的根干部节点的集合，取从左到右的次序。图,7,24,是一树图，其中是根,(root),，,为树尖。,（）树文法,图,8,24,树图,一般来讲，在树图中有两类重要信息。,一是关于节点的信息；,（节点是用一组字描述并存储）,另一个便是节点与其邻点的有关信息。,（节点与邻点的有关信息是以对其邻点的指示符的集合的形式存储。）,第一类信息用于识别模式的像元，,第二类信息定义像元和其他子结构间的物理关系。,例如，把图,7,25,所示的关系用图,(b),所示的树来表示。图,7,25,（,b,）,中，表示根，在中包含着,a,和,c,两部分，因此，从根放射出两个分支。第二级，,a,中包含,b,，,c,中包含,d,和,e,，在,e,中又包含,f,。,这样就构成了一个树图，其 中,b,，,d,，,f,是树的叶子。,图,8,25,用树来表示简单的组合区域,树文法为五元式，即,其中：,V,N,为非终端符；,V,T,为终端符；,S,为起始符；,P,为产生式集合；,r,为秩函数，它指出一个节点直接下降的数目。,图,8,26,图形的树表示,例：利用树文法把图,826(a),的电路结构表示成树的形式。这个树图是把,L-C,网络的最左边的节点定义为根。其树文法如下（电路中的,L,用,l,，,C,用,c,）：,在这种情况下，秩函数,利用三条产生式并利用,A,上定义的递归性就能产,生无限数量的结构。,8.2.1,区域描绘,8.2.2,关系描绘,8.2.3,相似性描绘,8.2.4,霍夫变换,图像描绘的另外一种途径可借助于与已知描绘子的相似程度来进行，这种方法可以在任何复杂的程度上建立相应的相似性测度。它可以比较两个简单的像素，也可以比较两个或两个以上的景物。,1,、距离测度,前面研究过的某些方法可以用来做为两幅图像区域之间进行比较的准则。例如，以矩做为描绘子，假如两个区域的矩分别为,X,1,和,X,2,。把它们写成向量式如下：,（,8,70,）,此时，,X,1,和,X,2,之间的距离可定义如下：,（,8,71,）,采用距离这一测度可以测量两个描绘子之间的相似性。如果已知描绘子用,X,1,X,2,X,3,X,L,表示，未知描绘子用,X,表示，可以计算,X,与已知描绘子的距离,D,(,X,X,i,),，如果,（,8,72,）,就可以判定,X,更接近第,i,个描绘子。式中,j,=1,2,3,.,L,，并且。这个方法原则上可,用于各种描绘子，只要它们能够用一矢量来,表示就可以。,2,、相关性,当给定一幅大小为,M,N,的数字图像,f,(,x,y,),，要确定它是否包含一个区域，该区域与某个大小为,J,K,中的某个区域,w,(,x,y,),相类似，其中,J,M,K,N,。解决这样问题常用的方法之一是求,f,(,x,y,),和,w,(,x,y,),之间的相关性。两个函数之间的相关的定义由下式表示：,（,8,73,）,其中,具体检测步骤如下：,对于,f,(,x,y,),中的任意值,w,(,x,y,),用式,(873),可求得一个,R,值，在,m,n,变化时，,w,(,x,y,),沿着图像移动，这时可得到,R,(,m,n,),。求出,R,(,m,n,),的最大值就说明,f,(,x,y,),和,w,(,x,y,),在此处最相似。但是在,m,n,接近边缘时，其精度较差。这个误差量正比于,w,(,x,y,),的大小。上述步骤可由图,830,加以形象地说明。,这里提到的相关检测法与前述的样板匹配法颇为相似。在这个意义下，样板就是,w,(,x,y,),。相关检测法与样板匹配法的主要区别是,w,(,x,y,),一般是一幅子图像。适合于图像特性的更复杂的相关定义可由下式表示,(8,74),相关性的计算可通过,FFT,算法在频域进行，这样比直接在空域计算更有效。,式中引入了归一化因子。归一化因子的计算是在,w,(,x,y,),被划定的整个面积上进行的，因此它是作为位移函数而变化的。,3,、结构相似性,一般来讲，结构相似性的描绘比起距离测度与相关性更难于公式化，因此，应用起来也就有更高的难度。可以用作相似测度的典型的结构描绘子是线段的长度、线段之间的角度、亮度特性、区域的面积、在一幅图像中一个区域相对于另外一个区域的位置等等。,例如，对一幅图像可用出现于图像中的物体以及这些物体间的关系来描述图像，用于描述的一部分性质可能是下列的一种或几种。,（）亮度：黑、灰、白、亮、暗、均匀、有阴影,等等；,（）颜色：红、橙、黄、绿、青等等；,（）结构：平滑、粒状、斑驳的、有条纹的等,等；,（）大小：长度、面积、体积、高度、宽度、深,度、大小、高、矮、宽、窄等等；,（）取向：水平、垂直、倾斜；,（）形状：实心的、中空的、密集的、参差不齐,的、伸长的等等；,上述的几种只反映了一个侧面，但是，就是这些，如果要从一幅图像中将它们抽取出来也是相当难办的。,基于结构分量之间关系的相似性测度，可以用某些文法将其公式化。假定有两类物体，可以分别用两种文法,G,1,和,G,2,来产生它们。给定一个特定的物体，如果它能用,G,1,来产生而不能用,G,2,来产生，那么就可以说这个物体更接近第一类。,如果用两种文法都能产生，就不能分辨给定的物体了。所以，这种方法可以把文法近似于给定结构的紧密程度作为相似性的测度。,7.2.1,区域描绘,7.2.2,关系描绘,7.2.3,相似性描绘,7.2.4,霍夫变换,霍夫变换是一种线描述方法。它可以将笛卡尔坐标空间的线变换为极坐标空间中的点。图,7,31,是,x,y,坐标系中的一条直线。如果用,代表直线距原点的法线距离，,为该法线与,x,轴的夹角，则可用如下参数方程来表示该直线。,这一直线的霍夫变换,:,（,8,75,）,在极坐标域中便是如图所示的一个点。,图,7,31 Hough,变换的原理,图,8,31 Hough,变换的原理,由图,7,31(b),所示的一个点。由图,8,31(c),、,(d),、,(e),、,(f),所示，在,(,x,y,),坐标系中通过公共点的一簇直线，映射