第五章形状分析与描述

1、第五章形状分析与描述 形状是由组成物体的轮廓线或物体表面的所有点相对位置决 定。这说明我们只能通过物体的轮廓线或外表面才可知道其形状， 而外轮廓和外表面是能为视觉所感知的。利用边缘检测和图象分 割，能够提取关于景物的重要的形状信息。 计算机视觉的另一主要难题是形状的表示。只有通过表示， 才能对感兴趣的景物形状进行学习、匹配、重构与利用。 把边缘连接起来就成为轮廓。轮廓可以是断开的，也可以是 封闭的。封闭轮廓对应于区域的边界，而区域内的象素可以通过 填充算法来填满。断开的轮廓可能是区域边界的一部分，也可能 是图象线条特征。区域之间的对比度太弱或边缘检测阈值设置太 高都有可能产生间断的轮廓。 轮廓

2、可以用边缘序列表或曲线来表示。曲线通常称为轮廓的 数学模型。曲线表示包括线段、二次曲线、三次样条曲线等。 第五章形状分析与描述 轮廓表示的评价标准：轮廓表示的评价标准： l简单：轮廓应该是一种简洁的表示。 l精确：轮廓应能精确地逼近图象特征。 l有效：轮廓应适合于后处理阶段的计算。 决定轮廓表示精确性的主要因素有以下三个方面：决定轮廓表示精确性的主要因素有以下三个方面： （1）用于轮廓建模的曲线形式； （2）曲线拟合算法的性能； （3）边缘位置估计的精度。 轮廓的最简单表示形式是边缘有序表。这种表示的精度就是 边缘估计的精度，但其表示的紧凑性是最差的，后处理也不方便， 因此不是一种高效的图象分

3、析方法。 用适当的曲线模型来拟合边缘会提高精确度，因为曲线模型 拟合边缘时往往具有均值化效应，因此可以减少边缘位置误差。 曲线模型也会提高轮廓表示的经济性，为后处理提供了一种更简 单、更紧凑的表示。 第五章形状分析与描述 已知一组控制点，曲线拟合常采用内插曲线或逼近曲线来实 现。 内插：内插：指使得拟合曲线通过所有的控制点。 逼近：逼近：指使拟合曲线非常接近这些控制点，而无需一定通过 这些控制点。 平面曲线函数可表示为三种形式： （1）显式 ； （2）隐式： ； （3）参数式： ，其中u是某一参数； 函数的显式表示很少用在计算机视觉中，主要原因是平面上 的曲线可能卷曲，致使一个x值可能对应曲线

4、上多个y值。 )(xfy ),(yxf )(),(uyux 第五章形状分析与描述 下面讨论一组计算曲线几何元素的算法，包括轮廓长度、正 切方向、曲率等。由于相邻象素间的量化增量是45，因此，精确 计算斜率和曲率是很困难的。 估计正切方向的基本思路是使用边缘表中非邻接非邻接的边缘点， 这就允许存在一个较大可能的正切方向集合。 设 是边缘表中第i个边缘坐标。K斜率是在边缘 表中相距K个边缘点的两个边缘点之间的方向矢量。进一步又分 为左K斜率和右K斜率。 K曲率是左、右K斜率之差。 假定边缘表中有n个边缘 。则数字曲线的 长度S及轮廓端点之间的距离D可表示为： ),( iii yxp ),(),(

5、11nn yxyx n i iiii yyxxS 2 2 1 2 1 )()( 2 1 2 1 )()(yyxxD nn 第五章形状分析与描述 一、链码 链码是沿着轮廓记录边缘表的一种表示方法。分为4方向链 码和8方向链码。如用8邻点链码表示一条曲线，即从边缘表中的 第一个边缘点开始，沿着轮廓按逆时针方向行走，行走方向用8个 链码中一个表示。 第五章形状分析与描述 第五章形状分析与描述 将上页图中曲线旋转90后如上图。 曲线的链码是：3566666676711234 其差分链码不变。 二、斜率表示法 第五章形状分析与描述 常用的曲线模型有：直线段、圆锥曲线和三次样条曲线。一 般，拟合之前应考虑

6、如下两个问题： （1）用什么方法进行边缘点曲线模型拟合？ （2）如何测量拟合的逼近程度？ 现假设边缘位置足够精确，不会对拟合结果产生影响。以下 讨论用曲线模型拟合边缘点的方法。 设di是边缘点到一条拟合曲线的距离（含正负号），在曲线 同一侧时具有相同的符号。以下是一些常用的用于衡量曲线拟合 效果的方法。 （1）最大绝对误差（MAE） （2）均方差（MSE） （3）规范化最大误差 （4）误差符号变化次数 （5）曲线长度与端点距离之比 i i dMAE max 第五章形状分析与描述 一、多直线段 多直线段是指端点连接端点的直线段序列，直线段序列的连 接点称为顶点。多线段算法的输入值是边缘点有序表

7、拟合边缘表并把第一个边缘点 和最后一个边缘点 连接起来的直线段公式如下： 上式可改写成： 其中： 而 是边缘点 和 之间的距离。 任给一点 ，设 ，则r的符号可用来 计算符号变化次数。点 与拟合直线段的距离为： 规范化最大误差为： ),( ,),(),( 2211nn yxyxyx ),( 11 yx),( nn yx xx yy xx yy n n 1 1 0CByAx 1 yyA n 1 xxB n 11 yxyxC nn 22 BAD ),( 11 yx),( nn yx ),( ii yxCByAxr ii ),( ii yx D CByAx d ii i D di i max 第五章

8、形状分析与描述 （1）多直线段分裂 自顶向下的分裂算法是将整 条曲线作为初始曲线，通过反复 增加顶点来用直线段拟合曲线。 直到所有的直线段对应的规范化 最大误差均小于某一阈值为止。 该过程也称为迭代分解。 第五章形状分析与描述 （2）线段合并 线段合并是指用一直线段尽量多地拟合边缘表中的边缘点。 当边缘点离直线太远而无法用该直线段拟合时，则开始新的直线 段拟合。（自底而上合并的多线段拟合方法） 第五章形状分析与描述 （3）分裂与合并 将多直线分裂与线段合并方法组合起来，形成合并与分裂算 法。 第五章形状分析与描述 二、二次曲线 二次曲线的一般表示如下： 二次曲线也称为圆锥曲线，包括：圆、椭圆、

9、抛物线、双曲 线。 （1）圆弧段 （2）圆锥曲线 0222),( 22 cgyexbyhxyaxyxf 第五章形状分析与描述 样条样条：富有弹性的细长条。 样条曲线样条曲线：将样条上的若干点固定，沿样条画出的光滑曲线。 在数学意义上，样条曲线是用分段多项式表示的一个函数，在其连 接点处具有连续的一阶和二阶导数。 样条曲线有很多应用。在数学分析中，当没有合适的函数模型时， 可选用样条函数拟合数据点；在计算机图形学和计算机辅助设计中，样 条函数用来表示自由曲线；在计算机视觉中，若没有表示曲线的合适模 型时，样条函数可以提供曲线的通用表示形式通用表示形式。 需指出，几何等效几何等效和参数等效参数等效

10、是两个不同的概念。 几何等效几何等效：是指它们连接相同的点集（即在空间上对应着相同的形状）。 参数等效参数等效：是指两条曲线的方程相同。 显然，参数等效比几何等效更稳定。两条曲线可以是几何上等效但 可具有不同的参数表示式，这是计算机视觉中的一个重要概念。 在计算机视觉的形状表示和物体识别中，常常基于几何等效性。 第五章形状分析与描述 一、三次样条曲线 样条函数最常见的形式是三次样条函数，它是分段三次多项 式的一个序列。直线段、二次曲线序列都是样条函数的特例。三 次样条函数可以用很少的几个样条段表示很复杂的曲线。已广泛 用于图形学及轮廓表示。 三次样条具有足够的自由度来逼近边缘段位置和方向。大多

11、 数边缘检测算子同时提供边缘方向和位置估计。在直线段、二次 曲线拟合中，仅使用了边缘的位置信息。下面介绍一种在三次样 条曲线拟合中如何使用有边缘检测器产生的方向信息的例子。 平面三次曲线方程如下： 或： 参数u取值范围在0和1之间。三次曲线起始点为 ， 终点为 。三次样条是由 构成的一个序列。这一序列定义在连续区间0，1，1，2， 32 32 )( )( uducubauy uducubaux yyyy xxxx 32 uuu)(x(u),y(u)(u)d dc cb ba ap p )0(),0()0(yxp )1 (),1 () 1 (yxp )(,),(),( 110 upupup n

12、第五章形状分析与描述 n-1，n上，并将端点连接起来使得在端点处 。样条 中每一个三次曲线段称为样条段，连接样条段两端的端点称为结 点。设第i个结点连接第i-1样条段和第i样条段，该结点表示为 或 。 与前述曲线拟合算法相同，把边缘点序列分成一个个子序列， 每一子序列的第一个和最后一个边缘点为样条曲线的结点，然后 再用样条段拟合这些结点。由三次曲线方程可知，样条中每一个 三次曲线段都需要确定四个二维矢量共计8个参数，其中，曲线段 的两个端点提供4个约束，结点处的一阶连续性提供2个约束，结 点处的二阶连续性提供两个约束，结点处的方向信息仅提供1个约 束（由于结点由两个样条段共享），这样产生的方程

13、数量为9个， 多于三次样条段所需的8个参数。 )()( 1 upup ii ) 1 ( 1i p)0( i p 第五章形状分析与描述 在结点处光滑连接样条段是非常重要的。在计算 机图形学中，光滑连接是通过增加二阶连续性来实现。 由上述分析知，二阶连续性提供2个约束，从而对样条 段产生过约束。为避免过约束，同时又要使结点处光 滑，可以采用结点处二阶不连续性的极小化条件，也 即将结点处的曲率差值极小化作为一个约束代替二阶 连续性提供的两个约束。（推导略） 同前面介绍的多线段、二次曲线拟合算法一样， 结点必须从边缘表中选出。调节结点的位置和数量可 以改善三次样条对整个边缘点集的拟合效果。 三次样条拟

14、合算法仅需要求解一个小的线性系统 就可得到正切值的符号和量值，因此该算法十分有效。 另外，也可以使用交互式图形界面，在其上可方便地 调节三次样条曲线。 第五章形状分析与描述 二、B样条曲线 B样条曲线是由 结点引导的逐段多项 式曲线，是一种平滑 和内插技术。 第五章形状分析与描述 Hough变换(HT)是一种用于区域边界形状描述的方 法，经典HT常常被用于直线段、圆和椭圆的检测。HT 是于1962年由P. V. C. Hough提出的，后经不断改进。 广义HT可推广至检测任意形状。无论是HT还是广义 HT其基本思想是将图象空间变换到参数空间，用大多 数边界点满足的某种参数形式来描述图象中的曲线

15、 （边界）。由于HT是根据局部度量来计算全面描述参 数，因此对区域边界被噪声干扰或被其它目标遮盖而 引起边界发生某些间断的情况，它具有很好的容错性 和鲁棒性。 第五章形状分析与描述 一、Hough变换的原理 Hough（HT）变换是一种用于区域边界形状描述的重要方法。 采用Hough变换检测任意曲线的原理如下： 假设 为需检测曲线的参数方程。式中 为形状参数，x，y为空间 域的图象点坐标。 对于图象空间的任一点 ，利用上式 可将其变换为参数 空间 中的一条曲线。假定空间域中位于同一曲线上的n 个点，对这n个点逐一进行上述变换，则在参数空间 中对 应地得到n条曲线，由上式知，这n条曲线必定经过同

16、一点 ，找到参数空间的这个点就决定了空间域中的曲线l。 传统的Hough变换将空间域中的每一个轮廓点代入上式，其 计算结果对参数空间中的量化点进行投票，若票数超过某一门限 值，则认为有足够多的图象点位于该参数点所决定的曲线上。即 需要逐点投票、记录，故耗时长，占用存储量也大。为克服这一 缺点，人们在应用中提出了许多改进算法。 ),( 121 yxaaafa nn n aa, 1 ),( 00 yx ),( 1n aa ),( 1n aa ),( 010n aa 第五章形状分析与描述 二、线段检测 直线的方程为： 如下图，按上述思想，一种检测直线的简单方法为：首先把参数 平面离散化，并建立一个参

17、数矩阵 。对于图象空间的每一 个边缘点 ，建立方程 ，并对离散化后的每个a 值，计算出相应的b值，然后，将参数矩阵的元素 的值加1： baxy ),(baP ),( ii yx ii yaxb ),(baP 第五章形状分析与描述 即 重复这一过程，直到扫描完所有的边界点。在过程结束后，参数 矩阵元素 的值表示图象空间中满足方程 的边界 点的个数，如果其大于某一阈值，就表示检测到了相应的直线。 这种在参数空间进行“投票”的方法体现了Hough变换抗干扰的 鲁棒性。 上述参数方程不适合处理垂直直线，因为此时直线的a值趋 于无穷大。为此，需引进直线的极坐标形式： 1),(),(baPbaP ),(b

18、aP baxy 第五章形状分析与描述 空间与 空间的变换),(),(yx y x ),( sincosyx 第五章形状分析与描述 此时的参数空间为 。其检测步骤如下： （1）适当量化参数空间； （2）累加器清零； （3）对每一 投票，相应累加器加1； （4）对投票结果进行阈值化处理。 由上述分析可知，若对参数空间量化过细，则计算量增大； 反之，若量化过粗，则参数空间的集聚效果差，检测精度降低。 因此，在应用Hough变换时，应根据实际选取合适的量化值。 如果图象空间各点的梯度方向已知，在寻求直线边缘时，可 在边缘点梯度方向的一定范围内对精细量化，其它角则粗量化， 这样可提高检测直线方向角的精度

19、，又不致增加计算量。 ),( ),( ii yx 第五章形状分析与描述 第五章形状分析与描述 三、圆检测 对于圆，其参数方程为： 其参数空间为 ，增加到三维。 222 )()(rbyax 222 )()(rbyax ),(rba 第五章形状分析与描述 其算法步骤如下（从灰度图象出发）： （1）应用边缘检测算子提取图象边缘，并按一定的阈值对其进行 二值化处理，生成边缘图象； （2）圆的参数方程 可改写为： 将角度值按参数空间的大小离散化，并求出相应的 值 存入数据表中； （3）对边缘图象中的所有点，当r的取值在 变化时， 求出 值，并将对应的累加器阵列中的单元 加1； （4）对累加阵进行处理，当 时，其参数对应为图象 空间的圆形边界。 显然，上述圆的Hough变换的计算量是非常大的。为降低计 算复杂性，有许多改进算法，如增加边缘方向信息等。 222 )()(rbyax sinryb rcocxa sin,cos maxmin rrr ),(ba),(rba TrbaP),( 第五章形状分析与描述 四、椭圆检测 参数空间变为5维： 五、广义Hough变换与任意形状检测 ),( 00 bayx 第五章形状分析与描述 第五章形状分析与描