教学课件第8章 图像分析（第8－4讲）（研究生学位课）ppt（全）.ppt

教学课件第8章图像分析（第84讲）（研究生学位课）数字图像处理学数字图像处理学第第8章章 图像分析图像分析（第四讲）（第四讲）阮秋琦教授阮秋琦教授 如果图像已经被分割为区域或部分，则图像描绘的下一步任务就是如何把这些元素组织成为有意义的关系结构。结构描绘一般是以文法概念为基础的。8.2.3 8.2.3 关系描关系描绘绘 例如，从一幅图像中已分割出图840所示的阶梯形结构，要用某种方法来描绘它，首先要定义一些基本元素，然后再定义一个重写规则就可以描绘出此阶梯形结构。图中(a)是阶梯结构；(b)是基本元素；(c)是编码结构。图8-39 阶梯形结构之描绘 在描绘过程中规定基本元素为a和b，重写规则如下：这里S和A是变量，元素a和b是常量。第一个规则说明S可以用基本元素a和变量A来代替，变量A可以用b和S来代替，也可以用b来代替。如果用 bS 来代替 A，则可以重复第一个规则的步骤。如果用 b 来代替，则步骤终止。这里假定都用 S 为起始点，第一个元素后面总是 b。由上例可见只需三条重写规则就可以产生无穷多的相似结构。1.1.串文法和语言串文法和语言 图8-39说明的编码结构是由符号的连接串组成的。这种符号串可以引用形式语言的概念来处理。形式语言起源于1950年。诺姆、乔姆斯基用数学模型研究了文法，其目的是研究一种计算机文法，然后用这个文法去研究自然语言，以便计算机在翻译和解答问题的过程中解释自然语言。关于形式语言的研究和应用已渗透到编译设计、计算机语言、自动机理论及模式识别和图像处理领域中了。首先，介绍一些最基本的定义：定义:V 为任何有限的符号集合；在 V 范围内的一个句子、一串字符或字都是由集合中的符号组成的任何有限长度的串。例 如，给 定 V=0,1，则0,1,00,01,11,000,001,都是有效的句子。定义:没有符号的句子为空句子，用来代表。用 V*代表由 V 中的符号组成的所有句 子集合，其中包括空句子。V+代表 (V*-)的句子集合。形式语言理论主要研究文法及其性质。串文法（或叫简单文法）是四元的，即形式语言理论主要研究文法及其性质。串文法：串文法（或叫简单文法）是四元的，即:其中：V N 为非终端符集合（变量）；VT 为终端符的集合（常量）；P 为产生式或重写规则集合；S 为起始符或根符号。假定 S 属于集合 VN ，并且 VN 和 VT 是不相交的集合，字母 V 是 V N 和 VT 的合集。由形式串文法 G 产生的语言记作 L(G)，这个语言就代表了一个模式。由字符产生的语言 L(G)满足两个条件：每一串只由终端符组成;每一串都由 S 开始并用由 P 决定的产生式来 生成。这个简单的文法可以用来产生无限多串组成的语言。上述四类文法有时依次称为型，型，型和型文法。由它们产生的语言分别称为类型语言，类型语言，类型语言及类型语言。由上述分类可以看出，所有的正则文法都是上下文无关的，所有上下文无关的文法都是上下文有关的，所有上下文有关的文法都是无约束的。对上述四类文法下面分别举例说明。0123四类文法的关系例：无约束文法 3.3.位置算子的运用位置算子的运用 前述的字符串是一维结构，而图像是二维结构，因此，在用字符串来描绘图像时就需要建立一种相应的方法，把二维的位置关系缩减为一维形式。串文法在图像描绘中大多数是从物体中抽取的联接线段为基础的。这种方法如图8-40所示。这是用有特定方向和长度的线段把结果编码。图840 用有方向的线段描绘区域边界 另外一种方法如图8-41所示。利用有向线段并用已定义的一些运算来描绘图像的某些部分。图中（a）是用有向线段来表示某些区域，图（b）是定义的某些运算。下面用一个具体例子来说明这些概念。图8-41 另一种描绘方法 例：图片描绘语言 这里（d ）表示与基本单元 d 方向相反的像元，而 a,b,c,d 的方向如 V T 中所定义的那样。应用产生式产生一个像元 d，其后，跟随一个尚未定义的变量 A1 。但是，A1 分量所表示的结构的尾在这点上将和 d 的头相连，这是由规定的算法“”所决定的。变量 A1 又 可分解为 C+A2 ，当然 A2 尚未定义。同样 A2 又可分解为 d *A3 。应用前三条产生式得到的结果如图8-42中(a)，(b)，(c)所示。算子“”定义为尾到尾、头到头的连接方式。使用全部产生式所得到的最后结果示于图8-42(f)中。这种文法只能产生一个结构。如果在产生式的规则中引入递归规则（变量有代替自己的能力），则这种PDL文法所产生的结构可扩展到各种结果。图8-42 PDL结构组成步骤 例：利用例的条件，定义下列产生式规则：顺次应用这些产生式就会产生图8-42中(f)的结果。例：染色体特征的描绘 描绘染色体的文法所用的基本像元如图843(a)所示。这些基本像元是对染色体沿边界顺时针方向循迹而检测出来的。典型的半中期和末期染色体的形状如图8-43(b)所示，描绘文法如下：其中算子“”用来描绘在按顺时针方向追迹边界时在产生式中各项的可连接性。在这个文法中，S和T均为起始符，S可产生相应于半中期染色体的结构，可以产生相应于末期染色体的结构。图 8-43 用边界轨迹描述染色体 4.4.高维文法高维文法 串文法适用于那些图像元素的连接可以用从头到尾或用其他连续形式的图像元素的描绘。在这里我们考虑一种更普遍的文法描绘途径，它有能力描绘更高级的图像元素。（）树文法（）树文法 高维文法之一是所谓树文法。树文法中所定义高维文法之一是所谓树文法。树文法中所定义的树是一个或的树是一个或一个以上的节点的集合。其中有一个唯一的指定的节点为根；剩下的节点划分为m个不相交的集合，这些集合为 T1,T2,T3,Tm，把 Tm叫做T 的子树；树尖是树的根干部节点的集合，取从左到右的次序。图8-44是一树图，其中是根(root)，x,y 为树尖。图8-44 树图 一般来讲，在树图中有两类重要信息。一是关于节点的信息；（节点是用一组字描述并存储）另一个便是节点与其邻点的有关信息。（节点与邻点的有关信息是以对其邻点的指示符的集合的形式存储。）第一类信息用于识别模式的像元，第二类信息定义像元和其他子结构间的物理关系。例如，把图8-45所示的关系用图(b)所示的树来表示。图8-45（b）中，表示根，在中包含着a和c两部分，因此，从根放射出两个分支。第二级，a中包含b，c中包含d和e，在e中又包含f。这样就构成了一个树图，其 中b，d，f是树的叶子。图8-45 用树来表示简单的组合区域 树文法为五元式，即图 8-46 图形的树表示 例：利用树文法把图8-46(a)的电路结构表示成树的形式。这个树图是把L-C网络的最左边的节点定义为根。其树文法如下（电路中的L用l，C用c）：利用三条产生式并利用A定义的递归性就能产生无限数量的结构。（）（）网文法网文法网是把节点加以标号的无指向图结构。在作图像描绘时，它的表示法比串或树更加简单。图8-47示出了一些简单的网。图8-48 由网文法产生的结构图8-47 简单的网这时可以忽略标号而以其基本图来识别网。这种类型的网文法有时被称为“图文法”。例：考虑上下文有关图文法如下：这个文法产生的图形结构包含有任何数量的串联和并联部分。并联的分段至少被一个串联节隔开，并且所有的结构的起始和终端至少有一个这样的节。两个简单的结果如图8-50所示。图8-49 图文法推导结果例：下面的网文法产生一些简单的几何图形。根据上述规则可做出如下推导：