《第七章-轮廓表示-机器视觉课件.ppt》由会员分享，可在线阅读，更多相关《第七章-轮廓表示-机器视觉课件.ppt（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第七章 轮廓表示 7 1 数字曲线及其表示 7 2 曲线拟合 7 3 样条曲线 7 4 曲线回归逼近 7 5 Hough 变换 7 6 傅里叶描述子 把边缘连接起来就成为轮廓(contour)轮廓可以用边缘序列表或曲线来表示曲线通常称为轮廓的数学模型曲线表示包括线段、二次曲线、三次样条曲线等 几种轮廓表示的评价标准：高效：轮廓应该是一种简单和紧凑的表示精确：轮廓应能精确地逼近图像特征有效：轮廓应适合于后处理阶段的计算 定义71 边缘表是边缘点或边缘段的有序集合 定义72 轮廓是边缘表或用于表示边缘表的曲线 定义73 边界是包围一个区域的封闭轮廓71 数字曲线及其表示 本节将讨论一组计算曲线几何
2、元素的算法，几何元素包括轮廓长度、正切方向角和曲率等估计正切方向角的基本思路是使用边缘表中非邻接的边缘点，这就允许存在一个较大的可能正切方向角集合设 是边缘表中第i个边缘坐标k斜率是在边缘表相距k个边缘点的两个边缘点之间的方向向量左k斜率是 指向 的方向，右斜率是 指向 方向k曲率是左右k斜率之差值 假定在边缘表中有n个边缘 数字曲线的长度可以近似为像素之间的线段和：轮廓端点之间的距离为：711 链码链码是沿着轮廓记录边缘表的一种表示方法链码规定了边缘表中每一个边缘点所对应的轮廓方向，其中的轮廓方向被量化为邻接链码或邻接链码中的一个，如图71所示图72 所示的是一条曲线及其邻接链码的表示，8邻
3、接链码从边缘表中第一个边缘开始，沿着轮廓按逆时针方向行走，行走方向用八链码中的一个表示（a）邻接链码(b)8邻接链码 图71 连接边缘点方向的链码示意图图7 一条曲线及其邻接链码表示712 斜率表示法假定从边缘表开始，使用上面给出的公式计算正切和弧长，可以画出正切 同弧长s的关系图，称作 图 图是轮廓形状在 空间的表示，是一种轮廓形状的紧凑描述图所示的是包含有直线段和圆弧段的轮廓在 空间中的表示，它是一个直线段序列 图74 轮廓的斜率表示72曲线拟合 本章将讨论三种常用的曲线模型拟合边缘点的方法：直线段(Line Segment)，圆锥曲线段(Conic Section)和三次样条曲线段(Cu
4、bic Spline)目前有许多种测量曲线与候选边缘点的拟合效果方法，每一种都取决于拟合曲线和候选点之间的误差 在用曲线模型拟合边缘点之前应考虑如下两个问题：(1)用什么方法进行边缘点的曲线模型拟合？(2)如何测量拟合的逼近程度？(1)最大绝对误差(maximun absolute error,MAE)测量最坏情况下边缘点偏离曲线的距离：(2)均方差(mean squared error,MSE)给出边缘点偏离拟合曲线的总的测度：拟合边缘表并把第一和最后一个边缘点 和 连接起来的直线线公式如下：上式可以改写为由端点表示的隐式函数：是边缘点 和 之间的距离任意一点，设，则 的符号可以用来计算符号
5、变化次数。点 与上述直线段的距离为：最大规范误差为：下面介绍两种拟合多线段的方法：自顶而下的分裂和自底而上的合并(1)多直线段分裂 自顶而下的分裂算法(top-down splitting)是将整条曲线作为初始曲线，通过反复增加顶点数来进行直线段拟合曲线考虑图75所示的边缘点曲线（可以认为是由离散边缘点构成），将第一个和最后一个边缘点连成的直线作为曲线的初始拟合，用AB标记在边缘表中计算最大规范误差，如果该误差值高于某一阈值，则在离直线段最远的边缘点上设置一个顶点，用C来标记(2)线段合并 线段合并(merging)是指用一条直线段尽量多地拟合边缘表中的边缘点当边缘点离直线段太远而无法用该直线
6、段拟合时，则开始新的直线段拟合误差带算法是另一种确定顶点位置的方法，如图76所示，主要工作是计算两条离中心线距离为 且平行的直线段(3)分裂和合并 自顶而下的迭代分解方法和自底而上的合并方法组合起来，形成合并和分裂算法单独使用分裂或合并算法时，成功率往往不是很高，改进的方法是交叉使用分裂和合并算法图77所示的是先分裂后合并来修补坏顶点位置的示意图 图77(a)原始边缘点集(b)自底而上的边缘合并方法产生的坏角点估计(c)漏掉的真实角点位置由分裂和合并过程来修补722圆锥曲线下面讨论如何用圆锥曲线逼近边缘表圆锥曲线的一般表示如下：(71)圆锥曲线也称二次曲线，因为二次曲线都是用平面切割正圆锥面的
7、截线，如图78所示 图78 圆锥和平面定义的圆锥曲线 由于二次曲线中除了特殊的直线外，最简单的情况时圆弧，因而得到了大量的研究我们将单独讨论圆弧逼近方法(1)圆弧段 用圆弧段拟合多直线段时，圆弧段的两个端点要经过多直线段的某两个顶点，第三个点位于这两个顶点之间。选择第三个点时可能有如下几种情况：1.选用距离连接这两个顶点直线最远的多直线段顶点 2.选用距离连接这两个顶点直线最远的边缘点选用这两个顶点之间所有顶点的中点选用这两个顶点之间所有边缘的中点(2)圆锥曲线 圆锥曲线可以拟合轮廓多直线段上的三个顶点圆锥逼近如图79所示圆锥样条中的每一个圆锥曲线由两个端点、两个正切和第三点确定结点位于多线段
8、顶点之间：(72)其中取0和1之间的数值正切由三个顶点,和 组成的三角形来定义第三点如图710所示，由下面式子计算(73)这里所示的计算圆锥样条算法使用了一个圆锥曲线的导向形式，以表示由三条直线约束的圆锥曲线，如图711所示 图711 圆锥曲线的导向形式7 样条曲线三次样条曲线样条函数最常见的形式是三次样条函数，它是分段三次多项式的一个序列图712样条中的每一个三次曲线段称为样条段，连结样条段的边缘点称为结点 图7.12 个控制点的分段连续三次样条插值曲线 和前面讨论的曲线拟合算法一样，把边缘点序列分成一个个子序列，每一个子序列的第一个和最后一个边缘点为样条曲线的结点，然后再用样条段拟合这些结
9、点 三次样条拟合算法仅仅需要求解一个小的线性系统就可以得到正切值的符号和量值，因此该算法十分有效如果需要的话，可以使用许多交互式图形界面，在其上可以很方便地调节三次样条曲线732 样条曲线 样条曲线是由结点引导的逐段多项式曲线，是一种平滑和内插技术B样条与上述样条曲线不同，它不必通过结点，我们将这种结点称为引导结点样条曲线的三次多项式是最常用的，因为这些样条曲率连续度为最低如图713所示通常，次的样条包含在由控制点确定的多边形内。由于样条的优良特性和对于任何控制点导数的连续性，故在实际中较为常用。图713 样条曲线示意图。（a）直线，(b)二次样条曲线，（3）三次样条曲线角点估计的最佳方法是使
10、用直线段逼近边缘点来求出直线段序列，然后计算直线段之间的交点这一方法补偿了由边缘检测算子对角点的平滑作用而引入的误差，并且比利用局部信息的角点检测算子求出的角点更精确一种较好的探测角点方法是沿着轮廓用一对直线拟合 个边缘点中的一个个连续子表，其中，参数 n 是边缘点数量，用于精确直线拟合；参数m是位于角点周围不予考虑的边缘点的数量，即跨越角点圆弧部分的边缘点设置一个阈值，检测 的幅值是否大于该阈值即可决定角点是否存在73 鲁棒回归法如果误差不服从正态分布，那么最小二乘法就不是最佳拟合方法图714所示的是数据集合包含一些局外点时，使用最小二乘法所遇到的问题的一个例子 图714 使用最小二次回归曲
11、线拟合方法和鲁棒性回归方法对包含有局外点的一组数据进行拟合的差别图715 最小二次方法对局外点敏感度的物理模拟图Jain图715是一个物理模拟图，可以使问题变的更加清楚设想一下你准备求出平面上一组点的质心把具有相同弹簧系数的若干弹簧的一端连接到一个可以自由运动的物体上，另一端分别系在不同的固定点上，物体将会被拉到一个平衡（平均）位置上弹簧将通过弹簧势能方程进行最小二乘法范数运算 75Hough 变换Hough变换-使用表决原理的参数估计技术在Hough变换中，曲线上的每一点可以表决若干参数组合，赢得多数表决的参数就是胜者 考虑一下直线拟合数据的方法直线方程为：(74)上述方程中，x和y是观测值
12、，m和c表示参数如果已知参数值，则该点坐标之间的关系即可确定把上述方程重新表示为：假定m和c是我们感兴趣的变量，而x和y是常数，则上述方程表示的是 空间中的一条直线，斜率和截距由x和y决定点 对应于空间 的直线，如图716(a)所示如果直线上有个n点，那么这些点对应参数空间 上的一个直线族，且所有直线都经过 上的一点，该点的坐标当然反应空间 上的直线参数,如图716(b)所示(75)直线的极坐标方程表示如下：(76)上述方程中，点 被映射到空间 上，如图716（c）所示 Hough变换算法的基本思路：如果我们对求点的最佳直线拟合感兴趣，那么，我们就可以使用上述图像空间到参数空间的映射这种方法称
13、为Hough变换在这种方法中，我们把参数空间表示为一个累加器阵列，表示离散参数值依照变换方程，图像中的每一点可以表决几个参数为了求出表征直线的参数，我们应该探测参数空间的峰值这种一般的想法概括在算法74中算法74 Hough变换算法（1）适当地量化参数空间；（2）假定参数空间的每一个单元都是一个累加器，把累加器初始化为零；（3）对图像空间的每一点，在其所满足的参数方程对应的累加器上加1；（4）累加器阵列的最大值对应模型的参数；利用上述算法的实验结果见图 7.17图7.17Hough变换算法实验结果。（a）合成图像，（b）直角坐标参数空间映射图，（c）极坐标参数空间映射图 算法75 圆拟合算法
14、量化参数空间a和b 置累加器阵列为零 计算梯度值和角 对于中的每一个边缘点，沿着直线（见方程7.53）给累 加器阵列中的所有点一个增量 累加器中局部最大值对应于图像中的圆中心 算法76广义Hough变换算法 在物体上取出一个参考点 沿着物体的边界计算梯度角 对每一个梯度角，存储对于参考点的距离和角度 实际应用例子流量检测参数空间中出现了二个峰值（多数表决点）（121,339,126）和（85,248,93），1=339*427/769=188.235，1=126*180/640=35.438 2=248*427/769=137.706，2=93*180/640=26.156 line 1：li
15、ne 2：76 傅里叶描述子由于沿着封闭轮廓的位置函数是周期性的，因此傅里叶级数可以用来逼近轮廓轮廓逼近的分辨率由傅里叶级数的项数来确定一维序列函数的离散傅里叶变换（DFT）定义为：(77）复数系数 称为边界的傅里叶描述子（78）傅里叶描述子是轮廓表示的简洁表示方法然而，更简洁的表示形式是使用傅里叶序列的低阶项的低分辨率逼近 习题1.什么是轮廓？轮廓与区域有什么关系？一个非封闭轮廓表示 什么？2.请列出选择轮廓表示的判据，并讨论这些因素在物体识别中的含义3.插值和逼近方法有何区别？那一种方法更好？4.为了完成的旋转，可能使用16方向的链码编码你如何来完 成这一编码？为什么8方向链码是最常用的链
16、码？5.逆时针求取图719所示物体的8-方向链码和链码差分，其中的空心圆点是起点图7.19 思考题75的轮廓6.考虑一下782节的角点位置估计方法当两条直线成直 角时，的值是多少？当两条直线成某一角度时，又为何值？（这是用于设置角点探测阈值的公式）7.考虑一下782节的角点位置估计方法假定边缘位置x和y的坐标误差服从方差为的正态分布角点的位置误差分布是什么？角点对应的角度是如何影响该误差的？8.产生一个相对于均匀背景的均匀强度的人工图像请使用第五章任何一种边缘检测器计算边缘，并用多线段拟合边缘请问所求得的顶点与真实角点位置的差距有多大？这种误差是否一定偏向一个方向？9.为什么 图被认为是连续链
17、码？其最吸引人的特点是什么？10.如何使用 图来比较两个物体？11.讨论一下你所使用的不同的逼近算法误差测量请问在逼近算法中，误差算法测量起什么作用？12.为什么说三次样条相对于多线段和圆锥曲线段是一种更有效的表示方法？13.试论述几何等效和参数等效的差别14.为什么在全回归方法中使用最小二次测量方法？试列出它的优点和缺点15.试说明鲁棒性方法是如何克服全回归方法的局限性？为什么鲁棒性方法在逼近算法中用的不是很普遍？16.傅里叶描述子在逼近和表示封闭曲线时的优点和弱点是什么？17.什么是Hough变换？它是否与鲁棒性回归方法有关？为什么？18.你能把Hough变换推广到检测任意物体形状？如何把
18、Hough变换用于探测旋转和尺度变换后的物体？上机作业题 1.编制一个程序求一条给定曲线的链码你能否利用链码来确定角点？如果能，请完成这一算法，并用几幅图像来测试2.编制一个用Hough算法检测图像中的直线算法使用这一算法来求一幅图像中的所有大于规定长度的直线段，设规定的长度为20点3.请产生一幅在均匀背景下的具有均匀灰度的矩形物体图像，使用第五章中任何一种边缘检测方法检测矩形物体的边缘，并用多线段拟合这一边缘请问多线段中的顶点与真实的角点接近的程度如何？这些顶点与真实角点的偏差是否总是在一个方向上？4.请产生一幅四个角点都为圆角的矩形图像，圆角可用四分圆表示首先使用边缘探测和多线段拟合，然后
19、使用本章介绍的圆弧段拟合方法替代多线段拟合，并测量圆弧段端点处的误差误差是否对称？是否角点不均匀使得矩形变的扭曲？5.完成用于直线拟合边缘点集表的最小中值二次回归算法。在边缘点集表中增加假边缘，以模拟成组误差请画出估计线段与真实线段之间的距离相对于假边缘数量的曲线6.考虑一个相对于一个垂直轴对称的物体假定可以得到物体左右两边的两个边缘段表采取一种三次样条拟合边缘的算法以确保这一对称性约束，并把这一算法推广到轴在任意一个位置7.假定可以得到一个相对于某一个轴是对称的物体的轮廓边缘点集表把边缘表处理成一个直线段和圆弧段序列编制一个匹配直线段和圆弧段算法来检测物体是对称的，并估计出对称轴在确定对称轴
20、以后，用这一信息来改善直线段和圆弧段的估计请编制一个细化轮廓表示的算法做迭代算法探测对称轴的实验，用这一信息细化轮廓表示，然后用改进的轮廓表示细化轴位置估计，重复这一过程，直到轴和轮廓表示收敛 习题 什么是轮廓？轮廓与区域有什么关系？一个非封闭轮廓表示什么？请列出选择轮廓表示的判据，并讨论这些因素在物体识别中的含义 插值和逼近方法有何区别？那一种方法更好？为了完成的旋转，可能使用16方向的链码编码你如何来完成这一编码？为什么8方向链码是最常用的链码？逆时针求取图719所示物体的8-方向链码和链码差分，其中的空心圆点是起点 图7.19 思考题75的轮廓 考虑一下782节的角点位置估计方法当两条直
21、线成直角时，的值是多少？当两条直线成某一角度时，又为何值？（这是用于设置角点探测阈值的公式）考虑一下782节的角点位置估计方法假定边缘位置x和y的坐标误差服从方差为的正态分布角点的位置误差分布是什么？角点对应的角度是如何影响该误差的？产生一个相对于均匀背景的均匀强度的人工图像请使用第五章任何一种边缘检测器计算边缘，并用多线段拟合边缘请问所求得的顶点与真实角点位置的差距有多大？这种误差是否一定偏向一个方向？为什么图被认为是连续链码？其最吸引人的特点是什么？如何使用图来比较两个物体？讨论一下你所使用的不同的逼近算法误差测量请问在逼近算法中，误差算法测量起什么作用？为什么说三次样条相对于多线段和圆锥曲线段是一种更有效的表示方法？试论述几何等效和参数等效的差别 为什么在全回归方法中使用最小二次测量方法？试列出它的优点和缺点 试说明鲁棒性方法是如何克服全回归方法的局限性？为什么鲁棒性方法在逼近算法中用的不是很普遍？傅里叶描述子在逼近和表示封闭曲线时的优点和弱点是什么？什么是Hough变换？它是否与鲁棒性回归方法有关？为什么？你能把Hough变换推广到检测任意物体形状？如何把Hough变换用于探测旋转和尺度变换后的物体？