图像处理--第8章目标表达与描述

数字图像处理1主讲：杨絮长春理工大学电信学院通信工程系第8章目标表达与描述第8章目标表达与描述§8.1概述与分类2§8.2边界表达§8.3区域表达§8.6关系描述§8.4边界描述§8.5区域描述内容第8章目标表达与描述§8.1概述与分类一、目标：图像中某些感兴趣的区域，称之为目标。二、表达：表达就是直接具体的表示目标。表达侧重于数据结构，分内部表达式和外部表达式。–内部表达式：区域的灰度、颜色、纹理等区域的反射性质；目标内部特性，即组成区域的像素集合；–外部表达式：区域的形状等；目标外部特性，即组成区域边界的像素集合。好的表达方法应具有节省存储空间、易于特征计算等优点；3第8章目标表达与描述4三、描述描述：较抽象地表示目标；应对目标的尺寸、平移、旋转不敏感；分类：边界描述、区域描述、关系描述。描述侧重于区域特性，以及区域间的联系和差别。借助一些称为目标特征的描述符进行，他们代表了目标区域的特性。常见的目标特征：灰度特征，纹理特征和几何形状特征等。内部特征外部特征§8.1概述与分类第8章目标表达与描述§8.2边界表达边界表达就是基于分割得到的一系列沿目标边界的像素点，对边界进行表示；5技术分类(1)参数边界：将目标的轮廓线表示为参数曲线(2)边界点集合：将轮廓线表示为边界点的集合(3)曲线逼近：利用几何基元去近似地逼近第8章目标表达与描述§8.2边界表达§8.2.1链码一、链码：对边界点的一种编码表示方法，逐点进行；特点：利用一系列具有特定长度和方向的相连的直线段表示目标的边界；链码起点用绝对坐标表示；其余点用偏移量表示。6第8章目标表达与描述7若直接对目标边界编码可能出现的问题：(1)码串太长(2)易受噪声干扰，导致链码发生与目标整体形状无关的较大变动§8.2边界表达§8.2.1链码改进：对原边界以较大的网格重新采样，得到的新边界具有较少的边界点，而且其形状受噪声等干扰的影响也较小。第8章目标表达与描述8§8.2边界表达§8.2.1链码4方向链码：0033322211014方向链码：000033333322222211110011第8章目标表达与描述9二、常用链码常用的链码有8方向链码和4方向链码，链码的直线段长度固定，方向有限（4或8）；这种链码中，边界的起点用坐标表示，其余点用接续方向数表示，采用方向数可大大减少数据量；因坐标值(x,y)至少得两个字节，方向数最多一个字节；（0-3用2bits，0-7用3bits）例：§8.2.1链码第8章目标表达与描述使用链码时，起点的选择很关键，因为即使是同一个边界，如果起点不同，链码不同。归一化，使链码构成的自然数最小；例如，右图的原链码为10103322，归一化后的归一化码为01033221，自然数最小；10二、常用链码§8.2.1链码第8章目标表达与描述11目标旋转时，链码会发生变化，可采用旋转归一化解决；一阶差分，求方向变化；链码的一阶差分：相邻2个方向数（按反方向）相减得到，但-1表示为3，例0-1=3；1-2=3；2-3=3；如(2)10103322--原链码33133030--差分码将图左转90度，链码不变。§8.2.1链码10310223(2)10103322331330302103313303010233(3)21210033左转90°第8章目标表达与描述§8.2.2边界段把边界分解成若干段分别表示，可减少边界表达的复杂性；引出的关键问题是如何判断分段点；一、凸包概念包含S的最小凸形称为逼近凸包H，H-S叫做S的凸残差，用D表示；能分开D的各部分的点就是合适的边界分段点。12二、判断方法跟踪H的边界，进入D或从D出去的点，就是1个分段点。第8章目标表达与描述13SS§8.2.2边界段第8章目标表达与描述14§8.2.3标记产生边界标记的方法很多，基本思想都是借助不同的投影技术把2-D的边界用1-D的较易描述的函数形式来表达。可把2-D形状描述的问题转化为对1-D波形进行分析的问题。投影并不是一种能保持信息的变换，将2-D平面上的区域边界变换为1-D的曲线是有可能丢失信息的。第8章目标表达与描述15§8.2.3标记1、标记的方法很多，最简单的是先对给定的物体求重心，然后把边界点与重心的距离作为角度的函数就得到一种标记。这种标记不受目标平移影响，但会随目标旋转或放缩而变化第8章目标表达与描述16§8.2.3标记2、y-s曲线沿边界围绕目标一周，在每个位置作出该点切线，该切线与一个参考方向（如横轴）之间的角度值就给出一种标记第8章目标表达与描述17§8.2.3标记第8章目标表达与描述§8.2.4多边形用多边形近似逼近不规则边界，抗干扰性好，节省数据量；常用方法有：一、基于收缩的最小周长多边形法18第8章目标表达与描述19二、基于聚合（merge）的最小均方误差线段逼近法：沿边界依次连接像素，计算拟合误差；三、基于分裂（split）的最小均方误差线段逼近法：先连接边界上相距最远的二个像素，再分裂边界，计算拟合误差，直至满足条件不再分裂；基于聚合基于分裂§8.2.4多边形第8章目标表达与描述20§8.3区域表达技术分类(1)区域分解：将目标区域分解为一些简单单元(2)围绕区域：用几何基元填充来表达(3)内部特征：由区域内部像素获得的集合第8章目标表达与描述§8.3.1空间占有数组对图像f(x,y)中任一点(x,y)，如果(x,y)在给定的区域内，则f(x,y)=1，否则f(x,y)=0。逐点表达的方法，占用较大空间。图像象素与数组元素是一一对应的。10111111111110000000000000000000000001000011111111100000000000000000(a)(b)21§8.3区域表达第8章目标表达与描述22§8.3.2四叉树利用金字塔式的数据结构，是对空间占有数组的编码。若图像是方形的，且像素点个数是2的整数次幂时，四叉树法最适合。所有结点分为3类:目标结点（白色）背景结点（深色）混合结点（浅色）§8.3区域表达C0级1级2级1245BDEA3678D31245ABE678C0级2级1级白灰黑AC第8章目标表达与描述23§8.3.3骨架利用细化技术得到区域的骨架是常用的方法。中轴变换(Medialaxistransform,MAT)是一种用来确定物体骨架的细化技术。MAT的定义：具有边界B的区域R中，对每个R中的点P，在B中寻找与它最近的点。若对P能找到多于1个这样的点，则称P属于R的中线或骨架。理论上说，每个骨架点保持了它与边界点距离最小的性质。§8.3区域表达第8章目标表达与描述24骨架，实际上就是用一个点与一个点集的最小距离来定义的，即(,)inf(,)|sdpBdpzzB其中距离量度可以是欧氏的、城区的、棋盘的。一般，较细长的物体的骨架能提供较多的形状信息，而较粗短的物体的骨架能提供的信息较少。注意，有时用骨架表示区域受噪声的影响较大。§8.3区域表达§8.3.3骨架第8章目标表达与描述25§8.3区域表达§8.3.3骨架•对每个R中的点P，在B中搜寻与它最近的点。如果对P能找到多于1个这样的点（即有2个或以上的B中的点与P同时最近），就可以认为P属于R的中线或骨架，或者说P是1个骨架点。RBp第8章目标表达与描述26§8.3区域表达§8.3.3骨架人腿骨和分层叠加显示的区域骨架第8章目标表达与描述27§8.3区域表达(1)外接盒：是包含目标区域的最小长方形(2)最小包围长方形：也称围盒。它定义为包含目标区域的（可朝向任何方向）最小长方形(3)凸包：包含目标区域的最小凸多边形§8.3.4围绕区域第8章目标表达与描述§8.4边界描述描述是将图像变成了符号（描述符）；§8.4.1简单描述符一、边界的长度定义：边界点p，1）p属于R区域，2）p的邻域中有像素不属于区域R，p就是边界点；边界点除外的点称为内部点。边界的长度：边界所包围区域的轮廓的周长就是边界的长度；是边界的全局特征；28第8章目标表达与描述二、边界的直径边界上相隔最远的2点之间的距离，是直线线段长度，一般是边界的主轴或长轴。三、曲率斜率的改变率即曲率；描述了边界上各点沿边界方向变化的情况；曲率的符号描述了边界在该点的凹凸性。29§8.4边界描述第8章目标表达与描述§8.4.2形状数形状数是基于链码的一种边界形状描述符。一、形状数的定义形状数：值最小的（链码的）差分码阶：形状数序列的长度，即码的个数。二、计算形状数的步骤计算链码计算差分码循环找出最小值形状数30§8.4边界描述第8章目标表达与描述31计算举例:链码(2)11010030030322322212差分码30313031031330130031形状数00313031303103133013阶20§8.4.2形状数§8.4边界描述起点第8章目标表达与描述§8.5区域描述§8.5.1简单描述符1.区域面积A基本特性，描述区域的大小:A=1；(x,y)∈R；计算区域面积实际上是对区域像素的计数；2.区域重心全局描述符，区域重心坐标计算x’=(1/A)x，(x,y)∈R；y’=(1/A)y，(x,y)∈R；3.区域灰度（密度）灰度的最大值、最小值、中值、平均值、方差以及高阶矩等统计量，都可以作为区域的描述参数。32第8章目标表达与描述§8.5区域描述§8.5.2拓扑描述符（基于拓扑学原理）令区域内的孔数为H，区域内的连通组元个数为C，类似笔划数。设欧拉数E=C-H；则欧拉数可以作为区域的拓扑描述符；例Bird，B的C=1；H=2；E=-1；i的C=2；H=0；E=2；r的C=1；H=0；E=1；d的C=1；H=1；E=0；33第8章目标表达与描述§8.5区域描述§8.5.2拓扑描述符（基于拓扑学原理）全由直线段构成的区域集合可利用欧拉数简便地描述。34一个包含拓扑网络的区域W代表顶点数，Q代表边数，F代表面数，给出欧拉公式：W-Q+F=E=C-H上图中：W=7，Q=11，F=2，C=1，H=3。因此，欧拉数E=-2。第8章目标表达与描述35多边形网的拓扑描述:W-Q+F=E=C-HWQFHW=26;Q=33;F=7;H=3;C=3;E=0§8.5区域描述§8.5.2拓扑描述符第8章目标表达与描述36§8.5区域描述§8.5.2拓扑描述符第8章目标表达与描述37§8.5.3形状描述符1.形状参数F=||B||2/（4A）；式中，A为区域的面积，||B||为区域的周长。形状参数描述了区域的紧凑性，但不能仅靠形状参数区别不同形状的区域：A=5;||B||=12;F1=F2=F3§8.5区域描述第8章目标表达与描述382.偏心率亦称伸长度，描述了区域的紧凑性计算边界长轴（直径）长度与短轴长度的比值，受物体形状和噪声影响大，方法简单；3.球状性S=ri/rc，ri代表区域内切圆的半径，rc代表区域外接圆的半径。当区域为圆的时候，S达到最大值1；当区域为其他形状时则有S1。4.圆形性C=mR/sR，mR表示从区域重心到边界点的平均距离，sR表示从区域重心到边界点的距离的均方差。§8.5.3形状描述符第8章目标表达与描述§8.6关系描述描述边界－边界、边界－区域、区域－区域之间的关系。一、字符串描述符（形式语言）三元组{S，∑，P}；S为开始符；∑为符号集合，如{a,b}；P为规则集合，如{SaA；AbS；Ab}39(1,3)(1,2,1,3)(1,2,1,2,1,3)第8章目标表达与描述40利用有向线段描述复杂结构：a+ba-ba×bab第8章目标表达与描述41二、树结构描述符abcdefR第8章目标表达与描述42习题8.1求出对应链码11076765543322的闭合边界，并画出归一化后的起点。8.2求出链码0101030303323232212111的一阶差分码（旋转归一化码）8.3求右下图的4方向链码和8方向链码。第8章目标表达与描述43习题8.4画出圆和等腰三角形的骨