数字图像分析第7章

1、l讨论对物体形状和结构的分析。讨论对物体形状和结构的分析。l处理对象是二值图象所表示的物体区域或边界处理对象是二值图象所表示的物体区域或边界。它往往是图像分割后得到的区域它往往是图像分割后得到的区域，并且通，并且通常使常使用一种更适合于计算机进一步处理的形式，对用一种更适合于计算机进一步处理的形式，对被 分 割 的 像 素 集 进 行 表 示 和 描 述 。被 分 割 的 像 素 集 进 行 表 示 和 描 述 。l结构分析研究对此对象提取形状特征，给出这结构分析研究对此对象提取形状特征，给出这类结构特征的定量描述方法类结构特征的定量描述方法。分析形状，根据形状识别物体是视觉系统的分析形状，根

2、据形状识别物体是视觉系统的重要功能之一。重要功能之一。l空间域空间域 (7.2，7.4)度量：面积，周长，扁度，紧凑度，度量：面积，周长，扁度，紧凑度，编码与方法：链码，形态方法，编码与方法：链码，形态方法，l频率域频率域 (7.3)傅立叶描述子傅立叶描述子涉及图象边界和区域的转换涉及图象边界和区域的转换 (7.1)l7.1.1 投影投影l7.1.2 边界跟踪边界跟踪l7.1.3 区域填充区域填充l1、种子点填充法、种子点填充法l2、奇偶校验填充、奇偶校验填充l7.1.4 区域标号算法区域标号算法投影是降低维数投影是降低维数的一种处理。的一种处理。投影投影“值值”可以可以作为一种特征。作为一种

3、特征。投影及其重构技投影及其重构技术还是计算机断术还是计算机断层成象的基础。层成象的基础。l关于数字边界关于数字边界l内边界内边界 和和外边界外边界l4-连通边界连通边界 和和 8-连通边界连通边界1111111111111111111111111111111l1、区域用、区域用1表示，背景用表示，背景用0表示。表示。l2、找到当前区域点、找到当前区域点c的一个背景邻点的一个背景邻点b，将，将b点的值点的值从从0变成变成2，同时变当前点，同时变当前点c的值为的值为3，并将当前点放，并将当前点放入表中。入表中。l3、从、从b开始，按顺时针方向访问当前点开始，按顺时针方向访问当前点c的邻点，的邻点

4、，直到找到值为直到找到值为1、3或或4的点，记该点为的点，记该点为d 。然后分两。然后分两种情况处理种情况处理:l(1) 若若d=4，c=3且当前点且当前点c的一个邻点是的一个邻点是2，则变，则变2为为0，变，变3为为4，并终止算法。，并终止算法。l(2) 否则令否则令c=4，并置并置c于表中。于表中。令令d为当前点为当前点c，并找到该并找到该点背景邻点点背景邻点b，同时置前一个同时置前一个b点为点为0。l4、重复操作、重复操作2直至终止。值为直至终止。值为4的点组成边界点集。的点组成边界点集。30002000430011100111000000400000004400113201110000

5、0010000000110011100111000000200200003100111001110000005000000044001140011320000060000000440011400134000200700000004400114003440020008000000044023140044400000090000000440041400444000000考虑还有什么获取边界的方法？考虑还有什么获取边界的方法？l1、种子点填充法、种子点填充法1）种子点向四邻点扩充的算法）种子点向四邻点扩充的算法2）扫描式种子点填充法）扫描式种子点填充法l2、奇偶校验填充、奇偶校验填充步骤：步骤：(1

6、) 从种子点开始将从种子点开始将四邻点四邻点中非中非边界点扩充为新的种子点边界点扩充为新的种子点(2) 重复处理新种子点，直到区重复处理新种子点，直到区域被填满，不再有新的种子域被填满，不再有新的种子点可以增加为止点可以增加为止 1 1 1 1 # # 1 1 1 1 # # # # 1 1 1 1 1 1 1 1 步骤：步骤：(1)从种子点开始扫描，遇到边界从种子点开始扫描，遇到边界后扫下一行。向下扫完所有行后扫下一行。向下扫完所有行后再向上扫描后再向上扫描 (或反之或反之)。(2) 每扫一行，检查前一行是否是每扫一行，检查前一行是否是这样的邻点，它既非边界点，这样的邻点，它既非边界点，又不

7、是已被填充过的点。又不是已被填充过的点。如果有，取这些点中的某一点如果有，取这些点中的某一点作为新的种子点。记在表中，作为新的种子点。记在表中，待以后作为新的扫描的起点。待以后作为新的扫描的起点。(3) 如步骤如步骤(1)、(2) ，直到处理完，直到处理完所有的种子点。所有的种子点。eoeo1) 求边界点集求边界点集:2) 由边界点集生成一填充起始点表。由边界点集生成一填充起始点表。 (1) 跟踪边界点，找到跟踪边界点，找到y的局部极值点处。的局部极值点处。 若局部极值点是一个孤立的极值点，则在边界点中再若局部极值点是一个孤立的极值点，则在边界点中再一次加入该极值点的坐标。一次加入该极值点的坐

8、标。 若有一系列若有一系列x值连续的极值点，则保留首尾两个，把值连续的极值点，则保留首尾两个，把中间诸点从边界点集中删除。中间诸点从边界点集中删除。 (2) 把所有边界点先对把所有边界点先对y排序，然后在同一排序，然后在同一y值中对值中对x排序，排序，形式成一个二维表列。形式成一个二维表列。3) 按照上述二维表填充，逐行取出表中边界点坐标，以按照上述二维表填充，逐行取出表中边界点坐标，以每对坐标的前一点为起点，后一点为终点，以划线每对坐标的前一点为起点，后一点为终点，以划线方式填充区域。方式填充区域。,.,2 , 1),(niyxiieoeo1 1 1 11 1 1 11 1 111 11 1

9、 11 1 11 1 1 1 1 1 11 1 11 1 1 1 11 1 1 1 1 1 11 1 1 11、算法开始，令标号、算法开始，令标号L=1；2、自左向右、自上向下地扫描图象，对于值为、自左向右、自上向下地扫描图象，对于值为1的的点，做下述操作：点，做下述操作：1) 若若f(i-1,j)=0，f(i,j-1)=1，则令当前点，则令当前点 (i,j) 的标号的标号与点与点 (i,j-1) 的标号相同，即：的标号相同，即：L(i,j)=L(i,j-1)。2) 若若f(i-1,j)=1，f(i,j-1)=0，则令，则令L(i,j)=L(i-1,j)。3) 若若f(i-1,j)=f(i,j

10、-1)=1，且两点标号相同，且两点标号相同， 即即L(i-1,j)=L(i,j-1)。则令。则令L(i,j)=L(i-1,j)。4) 若若f(i-1,j)=f(i,j-1)=0，则认为当前点为一新区域的，则认为当前点为一新区域的起点，故赋予它一个新的标号：起点，故赋予它一个新的标号：L=L+1，L(i,j)=L。5) 若当前点的两直接邻点都已赋标号，但标号不同，若当前点的两直接邻点都已赋标号，但标号不同，即即 f(i-1,j)=f(i,j-1)=1，但，但L(i-1,j)L(i,j-1)，则令当，则令当前点的标号等于其中任一标号，并且记下这一事前点的标号等于其中任一标号，并且记下这一事实：点实

11、：点(i,j-1)的标号的标号L(i-1,j)必须等于点必须等于点(i,j-1)的标的标号号L(i, j-1)。i,ji-1,ji,j-10L #L0 #LL#00# L1L2 #3、扫描完一幅图象之后，根据记录中的应相等的标号对，、扫描完一幅图象之后，根据记录中的应相等的标号对，重新整理各标号数值，得出最后的标好号的区域图象。重新整理各标号数值，得出最后的标好号的区域图象。改为改为 223改为改为 345记录表1 1 1 11 1 1 11 1 12 23 32 2 23 3 32 2 2 2 2 2 24 4 42 2 2 2 25 5 5 5 5 5 55 5 5 5l7.2.1 链码链

12、码1、链码的构成、链码的构成2、由链码表示的形状的数字度量、由链码表示的形状的数字度量l7.2.2 多边形近似多边形近似 1、线性扫描多项式近似、线性扫描多项式近似2、多边形近似的分裂算法、多边形近似的分裂算法3、分合多边形近似、分合多边形近似l7.2.3 区域形状的数字度量区域形状的数字度量方向链方向链8向链码向链码 4向链码向链码标识码标识码起始，结束起始，结束 坐标，序号坐标，序号yx04050010405004770022000333550400065273141)曲线长度曲线长度2)区域的宽度区域的宽度 高度高度3)区域的面积区域的面积4)两点间距离两点间距离)2(oennTL)mi

13、n()max(iixxw)min()max(iiyyhNiiyiixayaS11)21(2122)()(iiyiixaadne 和和 no分别是偶数标号和奇数标号的方向链的个数分别是偶数标号和奇数标号的方向链的个数,坐标坐标 ， x0, y0 是起始点的坐标，是起始点的坐标， aix, aiy 是码的分量。是码的分量。jjyiyay0jjxixax0误误 差差 计计 算算 1)选择一最大误差选择一最大误差e以及初始点以及初始点A，算法的输出是一组顶点。，算法的输出是一组顶点。2)令令B=A+e，C=A-e，扫描至下一点，从该点向，扫描至下一点，从该点向B和和C引直线，引直线，分别标号分别标号L

14、above和和Lbelow。3)逐点扫描，对任意一点（逐点扫描，对任意一点（xi, yi），连接），连接B和（和（xi, yi）成直）成直线线Lb，连接，连接C和（和（xi, yi）成直线）成直线Lc。若。若Lb在在Labove之上，则之上，则以以Lb刷新刷新Labove，若，若Lc在在Lbelow之下，则以之下，则以Lc刷新刷新Lbelow；检；检查查Labove和和Lbelow之夹角，若小于之夹角，若小于0度，则执行第度，则执行第4步，否则步，否则重复第重复第3步。步。4)自自A点作点作Labove和和Lbelow的平行线，与曲线交于离当前点最的平行线，与曲线交于离当前点最近的一点近的一点

15、A。A点即作为输出的顶点，同时作为下一次点即作为输出的顶点，同时作为下一次扫描的初始点，回到第扫描的初始点，回到第2步操作。步操作。5)当所有曲线点全部处理完之后，算法结束。当所有曲线点全部处理完之后，算法结束。l1、选择上限误差、选择上限误差emax，对于边界点集对于边界点集(xi,yi)，i=1,2,N,令令(xN+1,yN+1)=(x1,y1)。l2、定义两个堆栈、定义两个堆栈OPEN和和CLOSED，将点，将点1装入装入OPEN，将点将点N+1装入装入CLOSED。l3、如果在堆栈、如果在堆栈OPEN和和CLOSED中的最后一个元素是中的最后一个元素是i1和和i2，则用一线段连接，则用

16、一线段连接(xi1,yi1)和和(xi2,yi2)。l4、令、令im表示这一线段近似中出现最大误差的点，并用表示这一线段近似中出现最大误差的点，并用em表示该误差。若表示该误差。若ememax，则把，则把im压入堆栈压入堆栈OPEN中，否中，否则从则从OPEN中取出中取出i1并把它装入堆栈并把它装入堆栈CLOSED中。中。l5、若、若OPEN中已空，则算法终止，否则重复操作中已空，则算法终止，否则重复操作3和和4。运算结果装在运算结果装在CLOSED中。中。179514CLOSEOPENi1i2im141114 7141,7714 9141,7,9914 1314,91,779814,9,71

17、,557614,9,7,51154 Emax 则返回，否则则返回，否则合并合并 Si 和和 Si+1， 置置merge为真，以为真，以 Gi 刷新总体误差刷新总体误差E， 进而刷新所有进而刷新所有 Si 。 (3) 若若range为真，执行下述顶点调整操作为真，执行下述顶点调整操作:分别令分别令k=1,2, 对所有对所有i = k，k+2，n-1，作顶点调，作顶点调整：设当前顶点为整：设当前顶点为H(Si) ，与之相邻的顶点分别为，与之相邻的顶点分别为H(Si-1)和和H(Si+1) ，令，令H(Si)的坐标为的坐标为 (xj,yj)，取该点的，取该点的前一点前一点 (xj-1,yj-1) 和

18、后一点和后一点 (xj+1,yj+1) 分别算出以这两分别算出以这两个邻点为顶点时的误差，即在个邻点为顶点时的误差，即在 H(Si-1)，(xj-1,yj-1), H(Si+1) 以及以及 H(Si-1), (xj+1,yj+1), H(Si+1) 近似段上的误近似段上的误差。差。若它们都大于原误差，则不作调整，否则选它们之中若它们都大于原误差，则不作调整，否则选它们之中较小的一个刷新原顶点较小的一个刷新原顶点( xj, yj )。若在所有顶点的操作中，未作任何调整，则置若在所有顶点的操作中，未作任何调整，则置range为假。为假。l1、面积、面积l2、长度和宽度、长度和宽度l3、扁度、扁度

19、-长轴与短轴的长度比长轴与短轴的长度比 l4、紧凑度、紧凑度-周长的平方与面积之比周长的平方与面积之比l5 5、球形性、球形性-区域的内切园与外接园的比区域的内切园与外接园的比 l6、园形性园形性-区域的重心到边界的平均距离与区域区域的重心到边界的平均距离与区域的重心到边界的距离的均方差之比的重心到边界的距离的均方差之比 l7 7、矩形度、矩形度-区域面积和区域的最小外接矩形之比区域面积和区域的最小外接矩形之比 l8、欧拉数、欧拉数-连通区域数减去空洞数连通区域数减去空洞数 l矩特征矩特征l综合光密度综合光密度 2550)(zzHIOD二值化二值化边界跟踪边界跟踪重叠分离重叠分离填充标号填充标

20、号统计面积等统计面积等 对于二值图象的边界，边界点没有灰度信息，因此可对于二值图象的边界，边界点没有灰度信息，因此可以把它作为直角坐标下的离散曲线。以把它作为直角坐标下的离散曲线。这样，不管是曲线，还是边界，都可以表示成点集这样，不管是曲线，还是边界，都可以表示成点集(xi,yi)，i=1,2,N 。把把 y 看成是看成是 x 的函数，则又可写成的函数，则又可写成y=f(xi) i =1,2,N这样，用傅氏变换的概念把曲线用一组基函数的加权这样，用傅氏变换的概念把曲线用一组基函数的加权和来近似，导出了区域边界的富利叶级数描述子和来近似，导出了区域边界的富利叶级数描述子。tta)(Llt2)(t

21、aL是角度，是角度，是归一化长度，是归一化长度，是总长度。是总长度。函数函数 对于闭合曲线是周期变化的。对于闭合曲线是周期变化的。?a(t) 3 2 0 1 4 )sincos()(10ntcntbtannn10)cos()(nnnntAta200)(21dtta20cos)(1ntdttabn20sin)(1ntdttacn以一组展开系数以一组展开系数 An 作为其傅氏描述子。作为其傅氏描述子。傅氏描述子是旋转、位移、尺度不变的。傅氏描述子是旋转、位移、尺度不变的。由于傅氏级数的系数基本上是递减的，因此可以取前由于傅氏级数的系数基本上是递减的，因此可以取前面若干项面若干项(值比较大的值比较大

22、的)系数作为区域结构的特征描述系数作为区域结构的特征描述。式中式中:记为记为傅氏级数展开：傅氏级数展开：构造曲线的参数方程：构造曲线的参数方程：iAii10.3470.09820.3715.68731.0014.98940.3843.27950.5754.58860.4231.08470.4220.00480.1284.28390.2404.084100.0814.708复函数参数方程：复函数参数方程：复数型的傅氏级数展开为：复数型的傅氏级数展开为： 其中其中归一化归一化 ，用，用 代替代替 ，则有：，则有： 其中其中)()()(liylxlu)exp()(inlalunnLndlinlluL

23、a0)exp()(1lLl2l)2exp()(LlnialunnLndlLnliluLa0)2exp()(1取前面有限个系数作为该曲线的数字结构度量。取前面有限个系数作为该曲线的数字结构度量。l具有不变性。具有不变性。 不受平移、旋转、缩放的影响。不受平移、旋转、缩放的影响。l少数傅氏描述子能反映边缘的大致情况。少数傅氏描述子能反映边缘的大致情况。 一些低阶系数能够反映大体形状；一些低阶系数能够反映大体形状； 加上更多的高阶系数项可以精确反映形状加上更多的高阶系数项可以精确反映形状特征。特征。研究点以及集合的逻辑运算和几何运算方法和性质。研究点以及集合的逻辑运算和几何运算方法和性质。l7.4.1 图象形态运算基础图象形态运算基础l 逻辑运算：交、并、补，组成复杂的运算。逻辑运算：交、并、补，组成复杂的运算。l 几何运算：点与点，点与集合，几何运算：点与点，点与集合，“结构元素结构元素” 结构和、结构差结构和、结构差 开运算、闭运算开运算、闭运算 形态交离变换形态交离变换(中与丢中与丢) 细化和粗化。细化和粗化。l7.4.2 图象形态运算在结构分