值图像处理与形状分析.ppt

第七讲二值图像处理与形状分析,刘春国河南理工大学测绘与国土信息工程学院,8.1二值图像的连接性和距离,二值图像的连接性和距离,在二值图像特征分析中最基础概念是二值图像的连接性（连通性）和距离邻域和邻接对于任意像素(i，j)，把像素的集合(j+p，j+q)(p,q是一对适当的整数)叫做像素(i，j)的邻域。直观上看，这是像素(i，j)附近的像素形成的区域。最经常采用的是4-邻域和8-邻域。4-邻域与4-邻接：互为4-邻域的两像素叫4-邻接8-邻域与8-邻接：互为8-邻域的两像素叫8-邻接,二值图像的连接性和距离,像素的连接对于二值图像中具有相同值的两个像素A和B，所有和A、B具有相同值的像素系列p0(=A),p1,p2,pn-1,pn(=B)存在，并且pi-1和pi互为4-/8-邻接，那么像素A和B叫做4-/8-连接，以上的像素序列叫4-/8-路径。如图8.1.3。,二值图像的连接性和距离,连接成分在二值图像中，把互相连接的像素的集合汇集为一组，于是具有若干个0值的像素(0像素)和具有若干个1值的像素(1像素)的组就产生了。把这些组叫做连接成分。,图8.1.4连接性矛盾示意图,图8.1.5连接成分,孔：在0-像素的连接成分中，如果存在和像素外围的1行或1列的0-像素不相连接的成分，称之为孔单重连接成分：不包含孔的1-像素连接成分多重连接成分：包含孔的1-像素连接成分,如果把1-像素看成8-连接，那么0-像素就必须用4-连接。0-像素和1-像素必须采用互反的连接方式,二值图像的连接性和距离,欧拉数在二值图像中，1像素连接成分数C减去孔数H的值叫做这幅图像的欧拉数。若用E表示图像的欧拉数，则E=C-H(8.1-1)对于一个1像素连接成分，1减去这个连接成分中所包含的孔数的差值叫做这个1像素连接成分的欧拉数。显然，二值图像的欧拉数是所有1像素连接成分的欧拉数之和。,二值图像的连接性和距离,像素连接数与背景相连的像素称为境界像素为了记录图形形状，对邻接的境界像素一个接一个地进行跟踪处理，叫境界追踪。进行包括孔的所有的境界线追踪时，通过某个1-像素的次数，叫做该像素的连接数。像素的连接数可以通过考察以该像素为中心的33像素区域获取二值图像上改变一个像素的值后，整个图像的连接性并不改变（各连接成分既不分离、不结合，孔也不产生、不消失），则这个像素是可删除的。像素的可删除性可用像素的连接数来检测。,计算像素p的4-/8-邻接的连接数公式分别为,二值图像的连接性和距离,同一图像的像素，在4-或8-邻接的情况下，该像素的连接数是不同的。像素的连接数作为二值图像局部的特征量是很有用的。按连接数Nc(p)大小可将像素分为以下几种：孤立点：B（p）=1的像素p，在4-/8-邻接的情况下，当其4-/8-邻接的像素全是0时，像素p叫做孤立点。其连接数Nc(p)=0。内部点：B（p）=1的像素p，在4-/8-邻接的情况下，当其4-/8-邻接的像素全是1时，叫做内部点。内部点的连接数Nc(p)=0。边界点:在B（p）=1的像素中，把除了孤立点和内部点以外的点叫做边界点。在边界点上，1Nc(p)4。Nc(p)的像素为可删除点或端点；Nc(p)的像素为连接点；Nc(p)的像素为分支点；Nc(p)的像素为交叉点。背景点：把B（p）=0的像素叫做背景点。,二值图像的连接性和距离,距离对于集合S中的两个元素p和q，当函数D(p,q)满足下式的条件时，把D(p,q)叫做p和q的距离，也称为距离函数。,二值图像的连接性和距离,计算点（i,j）和（h,k）间距离常用的方法有：欧几里德距离de(i,j),(h,k)=(i-h)2+(j-k)2)1/24-邻点距离d4(i,j),(h,k)=|i-h|+|j-k|8-邻点距离d8(i,j),(h,k)=max(|i-h|,|j-k|)8角形距离d0(i,j),(h,k)=max|i-h|,|j-k|,2(|i-h|+|j-k|+1)/3,8.2二值图像连接成分的变形操作,二值图像连接成分的变形操作,1、连接成分的标记为区分二值图像中的连接成分，求得连接成分个数，对属于同一个像素连接成分的所有像素分配相同的编号，对不同的连接成分分配不同的编号的操作，叫做连接成分的标记。,对图像进行TV光栅扫描，发现没有分配标号的1像素，对这个像素分配还没有使用的标号，对位于这个像素8-邻域内的1像素也赋予同一标号，然后对位于其8-邻域内的1像素也赋予同一标号。,8-连接下的连接成分的标记算法,设二值图像为f，标记图像为g，则8-连接下的标记算法的具体步骤：1、设标记r=0，已贴标记数N=0，按照从上到下，从左至右的顺序进行扫描，寻找像素值为1的目标点像素；2、对尚未标记过的目标点像素f(i,j)，根据已扫描过的四个邻接像素，进行如下判断：如果所有的值为0，则r=r+1,g(i,j)=r,N=n+1;如果其标记值相同，即全部为r（r0），则g(i,j)=r；如果其标记值有两种（不可能有三种以上），即四个邻接像素值为r,r1(0rr1)，这时称为标记冲突，令g(i,j)=r，将所有已经标记为r1的像素，改标记为r,同时令N=N-1；,8-连接下的连接成分的标记算法,3、将全部像素都进行第2步的处理，直到所有像素全部处理完毕；4、判断是否满足r=N；如果是，则结束标记过程；如果否，则表明标记是一种非连续编号，需要进行一次映射处理，将所有的不连续编号校正为连续编号，结束标记过程。,基于数学形态学的二值图像操作,2、数学形态学数学形态学的数学基础是集合论，是以形态为基础对图像进行分析的数学工具它的基本思想是用具有一定形态的结构元素，去度量和提取图像中的对应形状。一般认为数学形态学的基本运算有4个：收缩和膨胀、开启和闭合。,二值图像连接成分的变形操作,2、简单的数学形态学知识二值图像形态学的运算对象是集合，一般地设A为图像集合，B为结构元素，数学形态学是B对A的操作，结构元素本身也是图像集合对每个结构元素先要指定一个原点，它是结构元素参与形态学运算的参考点,二值图像连接成分的变形操作,2.1、膨胀和收缩（腐蚀）膨胀就是把连接成分的边界扩大一层的处理。收缩（腐蚀）则是把连接成分的边界点去掉从而缩小一层的处理。若输出图像为g(i,j),则它们的定义式为:,膨胀和腐蚀的反复使用就可检测或清除二值图像中的小成分或孔。,二值图像连接成分的变形操作,2.2、膨胀膨胀的运算符为，A用B来膨胀记作AB,上式表明用B膨胀A的过程是，如果对B平移x，这里A与B交集非空集，这样的点组成的集合就是B对A的结果也即B的原点移动到x位置，如果A与B有任何一点同时为1，则新图像上相应的点为1，如果A与B完全没有相交，则新图像上相应的点为0膨胀的作用是把图像区域周围的背景点合并到图像区域中，其结果是使图像的面积增大相应的点,膨胀运算的一个例子,二值图像连接成分的变形操作,2.3、收缩/腐蚀腐蚀的运算符为，A用B来腐蚀记作AB,上式表明用B腐蚀A的过程是，如果对B平移x，如果B完全包含在A中，则新图像上相应的点为1，否则为0。腐蚀的作用是把消除物体所有边界点。把小于结构元素的物体去除，选取不同大小的结构元素可去掉大小不同且无意义的物体。,腐蚀运算的一个例子,二值图像连接成分的变形操作,2.4、开运算先腐蚀后膨胀的运算称为开运算。它一般的作用是消除细小物体。在纤点处分离物体和平滑物体边界时又不明显改变其面积,2.5、闭运算先膨胀后腐蚀的运算称为闭运算。它一般的作用是填充物体内细小空洞，连接相邻物体，在不明显改变其面积的情况下平滑物体边界,二值图像连接成分的变形操作,3、线图形化：将给定图形变换成线图形3.1距离变换和骨架距离变换是把任意图形变换成线图形的最有效的方法距离变换是求二值图像中各1像素到0像素的最短距离的处理。在经过距离变换得到的图像中，最大值点的集合就形成骨架，即位于图像中心部分的线像素的集合常用于图形压缩、提取图形幅宽和形状特征等,距离变换算法,采用4邻域距离，应用两次逐次图像扫描来进行距离变换设原始图像F=f(i,j)，中间图像S=s(i,j),S的所有元素初始化为0.对于第一次扫描有，,在第二阶段，将光栅扫描顺序颠倒，从最后一行开始，从右向左，逐行向上进行扫描，并进行如下处理结果图像H=h(i,j),H的所有元素初始化为0.对于第二次扫描有，,细线化方法,细线化方法目标是提取二值图像骨架，将线宽变为1个像素。距离骨架和细线化方法的区别是前者不保存拓扑性质，而后者保存通过膨胀处理能从骨架恢复原二值图像，细线化图像不能恢复原二值图像图像细线化的核心是判断像素点能否删除，可以根据像素的连接数和像素间的位置关系确定。,细线化方法,一种8-连接下的图像细线化的具体算法确定待处理像素p0=1，周围像素空间方位关系，进行位置标记pi（i=1,2,3,4,5,6,7,8）。计算的p0连接数Nc(p0)=1;如果满足以下条件：2=N(p0)=6,（N(p0)为p0八近邻像素之和）P1.P3.P7=0，或者Nc(p7)不等于1，避免p0是左或上端点、左上角点的情况P3.P5.P7=0，或者Nc(p5)不等于1，避免p0是右或下端点、右下角点的情况,细线化-Hilditch方法,1、光栅行扫描到某1-值像素，当满足一下6条件时，把B(p0)置换成-1，（1）B(p0)=1（2）p0是边界像素，4邻域有0值像素点（3）不是端点，8邻域的像素和大于等于2（4）不是孤立点（5）连接数为1（6）线宽为2的线段，消除单向条件，邻域8像素B(pi)不存在等于-1的像素,或者若存在，B(pi)=-1，使B(pi)=0，重新计算当前像素的连接数，如连接数不等于1，不能删除。2、对于B(pi,j)=-1的全部像素,置0，返回第一步运行，直到B(pi,j)=-1不存在，结束,二值图像连接成分的变形操作,3.3边界跟踪为了求得区域间的连接关系，沿区域的边界点跟踪像素，称之为边界（或边缘）跟踪。边界跟踪是在图像边缘连接明确的假设下进行的。实际上很多图像的边缘连接并不明显，可以在浓淡图像直接跟踪边缘。直接跟踪浓淡图像边缘的时候，须同时进行边缘检出。,二值图像连接成分的变形操作,3.3边界跟踪算法(1）根据光栅扫描发现像素从0变为1的像素p0时，p0作为边界的起点，存储它的坐标值(i,j);（2）从像素(i,j-1)开始反时针方向在像素(i,j)的8-邻域寻找1像素，当第一次出现的1像素记为pk(k=1)，存储它的坐标值（3）同上，反时针方向从pk-1以前的像素开始在pk的8-邻域内寻找1像素，把最新发现的1像素记为pk+1，存储它的坐标值当pk=p0时而且pk+1=p1时，跟踪结束。在其他情况下，把k+1当k，返回第三步，反复处理,8.3形状特征提取与分析,形状特征提取方法,区域形状特征提取是形状分析的基础通过图像分割获得了组成区域的像素集合（区域内部）或组成区域边界的像素集合（区域外部）。提取目标物的区域内部和区域外部的形状特征区域形状特征的提取有三类方法区域内部（包括空间域和变换域）形状特征提取；区域外部（包括空间域和变换域）形状特征提取；利用图像层次型数据结构，提取形状特征。,区域内部形状特征提取与分析,1、区域内部空间域分析是直接在图像空间域对区域内部提取形状特征，方法有下：1）拓扑描绘子欧拉数是区域拓扑性质之一。在二值图像中，1像素连接成分数C减去孔数H的值叫做这幅图像的欧拉数或示性数。若用E表示图像的欧拉数，则E=C-H,欧拉数维为0和-1的图形,区域内部空间域分析,2）凹凸性连接图形内任意两个像素的线段，如果不通过这个图形以外的像素，则这个图形成为凸的。任何一个图形，把包含它的最小的凸图形称作这个图形的凸闭包。从凸闭包除去原始图形后，所产生的图形的位置和形状是形状特征分析的重要线索。对于凸多边形的凸闭包就是其本身确定了目标凸闭包后，将边界分段下图中D=H-S;当把S的边界分解为边界段时，能分开D的各部分的点就是合适的边界分段点。通过D来确定S的分段点。,区域内部空间域分析,3）区域的测量区域的大小及形状描述量面积：区域内像素的总和周长：常用的有两种：一种计算方法是在区域的边界像素中，设某像素与其上下左右像素间的距离为1，与斜方向像素间的距离为21/2（角点：链码方向发生变化的地方）。周长就是这些像素间距离的总和。另一种计算方法将边界的像素总和作为周长。圆形度：它是测量区域形状的常用的量,此外，常用的特征量还有区域的幅宽、占有率和直径等。,区域内部空间域分析,2、区域内部变换法区域内部变换是形状分析的经典方法，它包括求区域的各阶统计矩、投影和截口等。1)矩法,函数f(x,y)的(p+q)阶原点矩定义式为：,那么大小为nm的数字图像f(i,j)的矩为,0阶矩m00是图像灰度f(i,j)的总和；二值图像的m00表示对象物的面积；如果用m00来规格化1阶矩m10及m01，则得到中心坐标（iG,jG）。,区域内部空间域分析,中心矩定义式为,利用中心矩可以提取区域的一些基本形状特征。例如M20和M02分别表示围绕通过灰度中心的垂直和水平轴线的惯性矩。假如M20M02，则可能所计算的区域为一个水平方向延伸的区域。当M30=0时，区域关于i轴对称。同样，当M03=0时，区域关于j对称。,区域外部形状,3、区域外部形状特征提取与分析区域外部形状是构成区域边界的像素集合。主要的分析方法有方向链码描述和结构分析法1.区域的边界、骨架空间域分析1)方向链码描述边界的方向链码表示既便于有关形状特征的提取，又节省存储空间。从链码可以提取一系列的几何形状特征。如周长、面积某方向的宽度、矩、形心、两点之间的距离等。,区域内部空间域分析,方向链码描述对于离散的数字图像，区域的边界可理解为相邻边界按像素逐段组成。对于图像某像素8-邻域，把该像素与其邻域的各像素连线放线如左图所示并进行编码，用0,1,2,3,4,5,6,7表示8个方向，这种代码称为方向码。其中偶数为水平或垂直方向的链码，码长为1；奇数码为对角线方向的链码，码长为21/2。右图以S为起点的逆时针编码,区域内部空间域分析,3、区域外部形状特征提取与分析2.结构分析法利用二值图像的四叉树表示边界，可以提取如欧拉数、区域面积、矩、形心、周长等区域的形状特征。,区域内部空间域分析,区域外形变换法区域外形变换是指对区域的边界作各种变换，包括区域边界的付立叶描述算子、Hough变换和广义Hough变换、区域边界和骨架的多项式逼近等。这样将区域的边界或骨架转换成向量或数量，并把它们作为区域的形状特征。,