第12章形状分析.ppt

章毓晋 (TH-EE-IE),第12章 形状分析,12.1 关于形状的讨论 12.2 平面形状的分类 12.3 形状特性的描述 12.4 基于技术的描述 12.5 拓扑结构的描述 12.6 分形维数,章毓晋 (TH-EE-IE),12.1 关于形状的讨论,1. 什么是形状 许多人都知道，但没人能全面定义的概念 读书辨字时，主要是形状信息在起作用 但用语言来解释形状是比较难的 几个看起来简单，但很难回答的问题 (1) 什么是形状？ (2) 什么是客观世界中一个物体的形状？ (3) 什么是图象中一个区域的形状？,章毓晋 (TH-EE-IE),1. 什么是形状 字典中关于形状的几个定义： (1) 形状是由轮廓或外形所确定的外观 (2) 形状是具有形体或图案的东西 (3) 形状是伴随模式的 (4) 形状是实际物体或几何图案的一个性 质，该性质依赖于组成该物体或图案 的轮廓或表面的所有点间的相对位置,12.1 关于形状的讨论,章毓晋 (TH-EE-IE),1. 什么是形状 形状的定义： 一个目标的形状就是该目标边界上所有点 组成的模式 形状可定义为“连通的点集合” 一般考虑形状时，均考虑“单个”且“完整” 的目标。“单个”和“完整”均可用连通的数 学概念来描述,12.1 关于形状的讨论,章毓晋 (TH-EE-IE),2. 形状研究的工作内容 (1) 预处理 采集图象，存储图象，消除噪声，分割目标 (2) 形状表达和描述 (3) 形状分类 对给定形状的目标确定它是否属于某个预先定义 的类别（有监督分类 ） 对预先没有分类的形状如何定义或辨识其中的类 别（无监督分类或聚类 ）,12.1 关于形状的讨论,章毓晋 (TH-EE-IE),3. 形状分析的方法 描述常采用的三类方法 特征的方法，形状变换的方法，基于关系的方法 描述符 一个形状性质可用基于不同的理论技术的 描述符来描述 借助同一种理论技术也可以获得不同的描 述符以刻画目标形状的不同性质,12.1 关于形状的讨论,章毓晋 (TH-EE-IE),12.2 平面形状的分类,各阶导数均存在,没有自交叉,章毓晋 (TH-EE-IE),12.2 平面形状的分类,(1) 粗和细形状 粗形状指包括内部的区域 细形状指没有充满的区域 2-D目标的外形（silhouette）,章毓晋 (TH-EE-IE),12.2 平面形状的分类,(2) 参数曲线 点在2-D空间 移动得到的轨迹 位置矢量的集合 参数为t 时的点速度,章毓晋 (TH-EE-IE),12.2 平面形状的分类,(3) 规则曲线 如果一条参数曲线的速度永远不为零，则 称该曲线为规则曲线 规则曲线速度的一个重要性质： 各点的速度矢量都与曲线在该点相切 归一化以使沿曲线的切向矢量为单位大小,章毓晋 (TH-EE-IE),12.3 形状特性的描述,形状和尺寸 任何目标均可用它的形状和尺寸来描述？ 形状性质与尺寸性质不相关？ 描述微结构的形状参数应具有一些共性 12.3.1 形状紧凑性描述 12.3.2 形状复杂性描述,章毓晋 (TH-EE-IE),12.3.1 形状紧凑性描述,对应目标的几何参数，所以均与尺度有关 1. 外观比 外观比（aspect ratio）常用来描述塑性形 变后目标的形状（细长程度） 可借助目标围盒定义 L和W分别是目标围盒的长和宽,章毓晋 (TH-EE-IE),12.3.1 形状紧凑性描述,2、形状因子 基于周长和面积 F 的值当区域为圆时达到最小（1） 没有量纲，所以对尺度变化不敏感 问题：形状不同，形状因子可能相同,章毓晋 (TH-EE-IE),12.3.1 形状紧凑性描述,3、偏心率 利用整个区域的所有象素 描述了区域的紧凑性（伸长情况） 由惯量推出 转动惯量 惯性积,章毓晋 (TH-EE-IE),12.3.1 形状紧凑性描述,3、偏心率 半轴长 E = p / q E 的值当区域为圆时 达到最小（1）,章毓晋 (TH-EE-IE),12.3.1 形状紧凑性描述,4、球状性 原本指3-D目标的表面积和体积的比值 基于区域的内切圆和外接圆（圆心为重心） 区域为圆时 S 值达到最大（1）,章毓晋 (TH-EE-IE),12.3.1 形状紧凑性描述,5、圆形性 利用所有轮廓点 区域趋向圆时 C 值趋于无穷,章毓晋 (TH-EE-IE),12.3.1 形状紧凑性描述,区域描述符示例 几个典型的简单物体,章毓晋 (TH-EE-IE),12.3.1 形状紧凑性描述,几个描述符的比较 外观比： 比较容易计算 但不适合用来描述非规则性 形状因子： 对非规则性比较敏感 对形状伸长度方面不如外观比敏感 球状性： 对伸长度和不规则性都比较敏感,章毓晋 (TH-EE-IE),12.3.2 形状复杂性描述,(1) 细度比例（thinness ratio）：形状因子的倒数， 即4p(A/B2) (2) 面积周长比：A/B (3) 矩形度（rectangularity）：定义为A/AMER，其中 AMER代表围盒面积。 (4) 与边界的平均距离（mean distance to the boundary）：定义为A / (5) 轮廓温度（temperature）：由热力学原理得来， 定义为 其中H为目标凸包的周长。,章毓晋 (TH-EE-IE),12.3.2 形状复杂性描述,饱和度 饱和度在一定意义下反映了目标的紧凑 性（紧致性） 它考虑的是目标在其围盒中的充满程度 具体可用属于 目标的像素数 与整个围盒所 包含的像素数 之比来计算,章毓晋 (TH-EE-IE),12.4 基于技术的描述,相关的描述符 由一种表达技术衍生出来的描述符 由基本描述符推导出来的描述符 12.4.1 基于多边形表达的形状描述 12.4.2 基于曲率的形状描述,章毓晋 (TH-EE-IE),12.4.1 基于多边形表达的形状描述,1. 直接计算的特征 可直接从多边形表达轮廓算出的特征： (1) 角点或顶点的个数 (2) 角度和边的统计量，如均值，中值，方差 (3) 最长边和最短边的长度，它们的长度比和它 们间的角度 (4) 最大内角与所有内角和的比值 (5) 各个内角的绝对差的均值,章毓晋 (TH-EE-IE),12.4.1 基于多边形表达的形状描述,2. 形状数的比较 两个形状 A 和 B 之间的相似度 k 是这两个形状数之间的最大公共形状数 如果 S4(A) = S4(B)，S6(A) = S6(B)，Sk(A) = Sk(B)，Sk+2(A) Sk+2(B)，则 A 和 B 的相似度就是 k 两个形状间的距离：它们相似度的倒数：,章毓晋 (TH-EE-IE),12.4.1 基于多边形表达的形状描述,3. 区域的标记 对区域中所有象素沿不同方向进行投影 点阵表达的字母（多边形逼近后的结果） 垂直投影： 得到相同的结果 水平投影： 得到不同的结果,章毓晋 (TH-EE-IE),12.4.2 基于曲率的形状描述,1. 曲率与几何特征,章毓晋 (TH-EE-IE),12.4.2 基于曲率的形状描述,2. 离散曲率 给定一个离散点集合 P=pii=0, , n，它定义了一条数字曲线，在点 piP处的 k-阶曲率 r k(pi) =1|cos |，其中 = angle(pik, pi, pi+k)是两个线段pi k, pi和pi, pi+k之间的夹角，而k i, , n i。,章毓晋 (TH-EE-IE),12.4.2 基于曲率的形状描述,2. 离散曲率,章毓晋 (TH-EE-IE),12.4.2 基于曲率的形状描述,3. 离散曲率的计算 (1) 先对x(t)和y(t)进行插值再求导数 用有限差分的方法,章毓晋 (TH-EE-IE),12.4.2 基于曲率的形状描述,3. 离散曲率的计算 (2) 根据矢量间的夹角来定义等价的曲率测度,章毓晋 (TH-EE-IE),12.4.2 基于曲率的形状描述,4. 基于曲率的描述符 (1) 曲率的统计值：平均值，方差，熵 (2) 曲率最大、最小点，拐点 (3) 弯曲能 将给定曲线弯曲成所需形状而需要的能量 设曲线长度为L，在其上一点k的曲率为k(t),章毓晋 (TH-EE-IE),12.5 拓扑结构描述,交叉数（crossing number） 考虑象素 p 的8个邻域象素 qi (i = 0, , 7) S4(p)：在p的8-邻域中4-连通组元的数目 连接数（connectivity number） C8(p)：在p的8-邻域中8-连通组元的数目,章毓晋 (TH-EE-IE),12.5 拓扑结构描述,区分4-连通组元 F 中的各个象素 p： (1) 如果 S4(p) = 0，则 p 是一个孤立点 （即F = p） (2) 如果 S4(p) = 1，则 p 或者是一个边界点或 者是一个内部点 (3) 如果 S4(p) = 2，则 p 对保持F的4-连通是必 不可少的一个点 (4) 如果 S4(p) = 3，则 p 是一个分叉点 (5) 如果 S4(p) = 4，则 p 是一个交叉点,章毓晋 (TH-EE-IE),12.5 拓扑结构描述,连通区域图 拓扑结构图 图中的孔数 H = 1 + |A| |V| V代表图结构中的结点集合 A代表图结构中的结点连接弧集合,章毓晋 (TH-EE-IE),12.6 分形维数,1. 两种维数定义 (1) 拓扑维数（topological dimension） 点在集合中位置的自由度的数目，记为dT 点的dT是0，曲线的dT是1，平面的dT是2 (2) Hausdorff 维数（自相似维数） 它被记为d，是实数 在欧氏空间的集合中，总有d dT （不等式成立的为分形集合，d为分形维数）,章毓晋 (TH-EE-IE),12.6 分形维数,2. 盒计数方法 将图象分成尺寸为 L × L的盒 对含有感兴趣目标的盒进行计数，记为N(L) 通过改变L，得到logN(L)对log(L)的曲线 分形维数是 曲线逼近直 线的斜率 的绝对值,N(L) Ld,章毓晋 (TH-EE-IE),12.6 分形维数,Koch Curve,章毓晋 (TH-EE-IE),12.6 分形维数,Koch Curve N(r) rd ：r为半径，N(r)为个数 r = 1/2, N(r) = 1； r = 1/6, N(r) = 4；r = 1/18, N(r) = 16 4 (1/3)d d = log(4) / log(3) 1.26,章毓晋 (TH-EE-IE),12.6 分形维数,3. 盒计数方法的讨论 分形总是对应一定的有限尺度 logN(L)对log(L)曲线的三段区域 无分形的区域(d 1) 分形的区域(d 1) 约为零维数的区域 (d 0),章毓晋 (TH-EE-IE),通信地址：北京清华大学电子工程系 邮政编码：100084 办公地址：清华大学东主楼，9区307室 办公电话：(010)62781430 传真号码：(010)62770317 电子邮件：zhangyjee.tsinghua.edu.cn 个人主页：www.ee.tsinghua.edu.cn/zhangyujin/ 实验室网：image.ee.tsinghua.edu.cn,联 系 信 息,