基于数学形态学的图像处理一.doc

基础知识 交通图像理解涉及到很多研究领域，如数字图像处理、计算机视觉、计算机科学、模式识别，模糊算法和人工智能等等。这里系统地介绍交通图像理解领域研究的一些预备知识和若干关键技术112-121。本章的结构安排如下:第一节介绍数字图像的数据表达形式；第二节介绍基本的数字图象处理的基础知识;第三节介绍遗传算法基础知识。1数字图像的数据表达 数据和算法是任何程序的两个最主要的组成部分，而数据的组织结构将对算法的简化和使用带来重大影响I20，因此，在本节中，将介绍本文所用到的描述图像的各种数据结构，如矩阵、链表以及金字塔结构等等。二维空间数组 二维数组是表达图像中区域的一种方便、简单、直观的方法。图像矩阵中的任意一个整数对应该象素点的灰度，或者对应该象素点颜色中的某一属性。任意象素点信息可以很轻易的通过该象素点坐标(x，y)从矩阵中获取相应的图像信息。通常该矩阵有三种表现形式：二值图像、灰度图像和彩色图像。 链码是一种重要的目标描述方法，经常用于模式识别中。链码属于一种线性结构，因此该数据结构不能描述象素点邻域间的空间特征。最常使用的链码结构有两种:Freeman码。它经常被用于表述目标边界或单象素点宽度的曲线，由参考点坐标和一组符号序列组成。参考点坐标描述了目标的位置信息；而符号序列描述了边界信息点间的相对位置信息，如图2-1所示。行程编码经常被用来描述图像矩阵中的特征串信息，该编码只记录目标区域象素点信息，每一行形成一个子链，每一个子链的第一个整数代表该行的坐标，而后续的整数对序列则是描述目标区域出现的“开始”“结束”点信息，如图2-2所示。 图2-2行程编码(11133)(214)(423)分层数据结构一金字塔形结构 众所周知，计算机视觉的数据计算是非常耗时的。可以解决上述问题的有效手段之一是使用并行计算机，不幸的是，许多计算机视觉计算问题很难分成多处理器计算。而解决上述问题的另一种有效途径，是使用分层数据结构，利用算法形成一种数据处理策略，从而减少数据处理的数量，加速数据处理的速度。其中，金字塔形结构是最简单的分层数据结构，它是由一系列图像Ml，Ml-1，M。组成。M。是原始图像，位于金字塔的底层，图像Mi是图像Mi-1经一定的数据提取算法获取的更高一层数据图像，图像尺寸相应减少n倍，最终形成一个金字塔形状。可以采用先粗后精的数据处理策略，将极大的提高数据处理速度。2 .2数字图像处理的基础知识直方图 一幅图像的直方图，表示该图像中各种不同灰度级象素出现的相对频率，是一个1-D的离散函数(设图像的灰度总级数为L):式中gk为图像f(i，j)的第k级灰度值，nk是f(i，j)中具有灰度值为gk的象素的个数，N是图像象素总数。因为p(gk)给出了对gk出现概率的一个估计，所以直方图提供了原图的某种灰度值的分布情况，也可以说给出了一幅图所有灰度值的一种整体描述。象素邻域定义 对一个坐标为(i，j)的象素p，它可以有两个水平和两个垂直的近邻象素。它们的坐标分别是(i+l，j)，(i-l，j)，(i，j+l)，(i，j-1)。这些近邻象素组成象素p的4-邻域，记为N4(p)，见图(a)。象素p与其4-邻域近邻象素的距离为一个单位距离。 象素p的四个对角近邻象素的坐标是(i+l，j+l)，(i+1，j-1)，(i-1，j+1)，(i-1，j-l)。见图(b)。这些象素点再加上p的4-邻域象素合起来组成p的8一邻域，记为N8(p)，见图(c)。 图2-3象素的邻域连通性和通路 象素间的连通性是确定图像中目标的边界信息和区域信息的重要概念。连通性是建立在连接和连通的概念之上的，连接属于连通的一种特例。要确定两个象素是否连接需要在某种意义上确定它们是否接触(例如它们是否为4一近邻象素)以及它们的灰度值是否满足某个特定的相似准则(例如它们灰度值相等)。举例来说，在一幅只有灰度0和1的二值图中，两个4一近邻象素.只有在它们具有相同灰度值时才可以说是互相连接的。定义以下两种连接情况(其中V表示定义连接的灰度值集合): (1)4一连接：两个象素p和r在V中取值且r在N4(p)中，则它们为4一连接;(2)8一连接：两个象素p和r在v中取值且r在N8(P)中，则它们为8一连接: 从具有坐标(x，y)的象素p到具有坐标(s，t)的象素q的通路是由一系列具有坐标(x。，y。)，(x1，y1)，(xn，yn)的独立象素组成的。这里(x。，y。)=(x，y)，(xn，yn) =(s，t)，(xi，yi)与(xi-1，yi-1)相毗邻，其中1=i=0 (D(p，q)=0当且仅当p=q);D(P，q)=D(q，p);D(p，r)=D(p，q)+D(q，r)。 点p和q之间的欧氏距离(也是模为2，即L2的距离)定义为: DE(p，q)=(x-s)2+(y-t)21/2 (2-2) 根据这个距离量度，与(x，y)的欧氏距离小于或等于某个值d的象素都包括在以(x，y)为中心以d为半径的圆中。 点p和q之间的D4距离，即城区距离(也是模为l，即Ll的距离)定义为: D4(p，q)=|x-s|+|y-t| (2-3) 根据这个距离定义，与(x，y)的城区距离小于或等于某个值的象素组成以(x，y)为中心的菱形。对象素(x，y)与它D4=1的象素就是(x，y)的4-近邻象素。 点p和q之间的D8距离，即棋盘距离(也是模为，即L的距离)定义为: D8(p，q)=max(|x-s|+|y-t|) (2-4) （ ，？） 根据这个距离量度，与(x，y)的棋盘距离小于或等于某个值的象素组成以(x，y)为中心的正方形。对象素(x，y)，与它D8=1的象素就是(x，y)的8一近邻象素。滤波 由于交通图像通常采集于自然条件，不可避免的存在噪声，跟据噪声的特点以及对滤波的要求，可以选择不同的滤波方式。通常使用的滤波方式如下: 邻域平均法：邻域平均法是一种简单的空域处理方法。它是将象素点(m，n)及其邻域的灰度值与某一加权函数相乘后求和，所得的值作为该点的滤波值。式中，H(r，s)为加权函数，习惯上称为掩码，如:中值滤波法：中值滤波法通常使用一个窗口W在图像上扫描，将窗口内包含的图像象素按灰度排列，取其中间值作为窗口中心象素的灰度，用公式表示: g(m，n)=Medf(m-r，n-s)，(r，s)W (2一7)高斯滤波：高斯滤波属于一种低通滤波器，主要用于滤除噪声、平滑图像的，形式如下:匹配 匹配是根据已知目标特征(如形状、大小、面积等)，在另一图像中搜寻相应的特征的算法。通常有关系结构匹配，模板匹配等。这里重点介绍模板匹配算法。 模板匹配：模板匹配是利用预知的目标特征，产生匹配模板，并在待匹配图像中搜寻目标，当相关函数有了极值时，就可以判定为目标。设模板叠放在图像上，自上而下，自左而右平移，可用下式作为相关函数:(m，n)为其覆盖下的那一块子图左上角的坐标，(i，j)为象素点在模板内的横纵坐标，P(i，j)为模板象素点的灰度值，Sm，n(i，j)为图像相应点的灰度，W，H为模板的长宽尺寸。将上式归一化后变为:根据Cauchy-Schwarz不等式可知:0R(m，n) 1。当且仅当Sm，n(i，j)与模板P(i，j)完全相同时，R(m，n)=1为最大，说明(m，n)是在完全无噪声干扰的情况下精确的匹配。特征抽取 图像特征是用于区分一个图像内部的最基本属性，它们可以是原图像中人类视觉可以鉴别的自然特征，也可以通过对图像进行测量和处理后人为定义的某些特征或参数，它们被称为人工特征。抽取图像特征在图像处理中占有重要的地位。不仅图像分割技术要依据图像边缘特征或组织特征，而且在图像描述和分类中，也离不开对图像特征的正确选择和抽取。作为图像特征，一般应具有如下特点:l、可区分性;2、可靠性:3、独立性;4、数量少。常用的统计特征有:式中L为灰度级总数，P(b)为图像的概率密度。目标描述 在各种图像识别问题中，常常都要涉及对目标大小进行描述，以下将介绍一些通用的描述方法。 面积：目标的面积可以简单地定义为目标边界所包围的象素点数。它反映了目标的大小或者质量。 长度和宽度：目标的长度和宽度可以用在水平和垂直方向上最大的象素点数来度量。 周长：目标的边界象素点总长度。 矩形度：可以用目标面积A0和包围它的最小矩形面积Ar之比，R= A0/Ar作为目标矩形度的一种度量参数。它的大小能够反映目标和矩形接近的程度。 投影比：包围目标之最小矩形的宽度W与长度L之比。该参数可将细长目标和近似圆形或方形目标区分开来。 圆度：目标周长的平方和其面积之比，c=P2/A称为目标的圆度。数学形态学 数学形态学是一种应用于图像处理和模式识别领域的新的方法。它的基本思想是用具有一定形态的结构元素去度量和提取图像中的对应形状以达到对图像进行分析和识别的目的。数学形态学的数学基础和所用语言是集合论。数学形态学的应用可以简化图像数据，保持它们基本的形状特性，并除去不相干的结构。另一方面，数学形态学的算法具有天然的并行实现的结构。 数学形态学的基本运算有四个：膨胀、腐蚀、开启和闭合。现简单介绍如下: 如用A表示图像集合，B表示结构元素，形态学运算就是用B对A进行操作。 A被B膨胀，记为A B，为膨胀算子，膨胀的定义为该式表明的膨胀过程是B首先做关于原点的映射，然后平移x。A被B的膨胀是B被所有x平移后与A至少有一个非零公共元素。 A被B腐蚀，记为AB，为腐蚀算子，腐蚀的定义为也就是说，A被B的腐蚀的结果为所有使B被x平移后包含于A的点x的集合。换句话说，用B来腐蚀A得到的集合是B完全包括在A中时B的原点位置的集合。 膨胀和腐蚀并不互为逆运算，所以它们可以级连结合使用。例如，利用同一个结构元素B，先对图像腐蚀然后膨胀其结果，或先对图像膨胀然后瘸蚀其结果，前一种运算称为开启运算，后一种运算称为闭合运算。它们也是数学形态学中的重要运算。 开启的运算符为o，A用B来开启写作AoB，其定义为: 闭合的运算符为，A用B来闭合写作AB，其定义为: 开启和闭合两种运算都可以去除比结构元素小的特定图像细节，同时保证不产生全局的几何失真。开启运算可以把比结构元素小的椒盐噪声滤除，切断细长搭接而起到分离作用。闭合运算可使比结构元素小的缺口或孔填补上，搭接短的间断而起到连通作用。2.3遗传算法 遗传算法是基于进化论中自然选择机制的、并行的、统计的随机化搜索方法。借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。这一点体现了自然界中“物竞天择、适者生存”的进化过程。按照达尔文的自然选择理论，生物进化取决于个体间的生存竞争，对环境适应度高的个体继续生存，适应度低的个体被淘汰。人类的进化可以通过种群和物种的物理过程，包括复制，变异，竞争和选择得到全面的解释。个体的生物性特征通过遗传物质得到控制，通过复制和交叉得到交换和保持，通过变异引入新的变化。遗传物质的主要载体是染色体。染色体由多个基因组成，遗传算法正是通过对染色体中的基因进行操作来完成信息的存储、交换和特性的控制、改良。遗传算法常用算子 1、选择算子：选择算子从群体中按某一概率成对选择个体，任意个体xi被选择的概率Pi与其适应度值成正比。轮盘赌模型是最通常的实现方法。 2、交叉算子：交叉算子将被选中的两个个体的基因链按概率Pc进行交叉，从而生成两个新的个体，交叉位置是随机的。其中Pc是一个系统参数。 3、变异算子：变异算子将新个体的基因链的各位按概率Pm进行变异，而对二值基因链(0，1)编码来说，即是取反。 尽管算子只有三个，但算法的实现却多种多样，而且许多新的算子正在不断地提出，以改进遗传算法的某些性能。系统参数(个体数n，基因链长度l，交叉概率Pc，变异概率Pm等)对算法的收敛速度及结果有很大的影响，应根据具体情况，选择合适的参数值。典型的遗传算法基本流程1、染色体编码:它定义问题的解空间到染色体编码空间的映射。2、初始化种群:在一定的限制条件下初始化种群，该种群是解空间的一个子空间;3、设计适应度函数:将种群中的每个染色体解码成适于计算适应度函数的形式，并计算其数值;4、设计算子:确定种群中每个染色体的繁殖概率值，并通过专门的遗传算子实现种群的世代更替;5、判断停止:如果进化生成到一个合适的解，或者计算时间达到限定的上界(繁殖到限定的次数)，或者种群中所有个体的适应度不再变化，则算法停止，否则返回步骤3。 因为遗传算法具有全局搜索能力，很多研究者也将遗传算法引入到数字图像处理中，来帮助确定阈值，以及图像处理中的参数优化等问题，取得了很好的效果。遗传算法的应用关键遗传算法在应用中最关键的问题有如下3个 1.串的编码方式。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度