资源描述
第 7 章,轮廓表示,1,轮廓：把边缘连接起来就成为轮廓(contour)轮廓可以是断开的，也可以是封闭的. 轮廓可以用边缘有序表或曲线来表示。曲线通常称为轮廓的数学模型曲线表示包括线段、二次曲线、三次样条曲线等,2,轮廓表示的评价标准： 效率：轮廓应该是一种简单和紧凑的表示 精确：轮廓应能精确地逼近图像特征 有效：轮廓应适合于后续应用阶段的计算,3,精确表示轮廓的影响因素： 用于轮廓建模的曲线形式； 曲线拟合算法的性能； 边缘位置估计的精确度。,4,轮廓曲线拟合通常采用内插曲线或逼近曲线来实现已知一组称为控制点的坐标点，内插是指一条曲线拟合这组控制点，使得曲线通过所有的控制点；逼近是指一条曲线拟合这组这组控制点，使得这条曲线非常接近这些控制点而无需一定通过这些点,5,定义： 边缘表是边缘点或边缘段的有序集合,轮廓的最简单表示形式。 轮廓是边缘表或用于表示边缘表的曲线。 边界是包围一个区域的封闭轮廓。,6,设Pi=(xi,yi)是边缘表中第i个边缘坐标 (1)k斜率是在边缘表相距k个边缘点的两个边缘点之间的（角）方向向量 (2)左k斜率是Pi指向Pik的方向， (3)右k斜率是Pi指向Pi+k方向 (4)k曲率是左右k斜率之差值。,7.1 数字曲线及其表示,7,(6)轮廓端点之间的距离为,(5)数字曲线的长度可以近似为像素之间的线段和：,8,数字曲线表示1链码,链码：是沿着轮廓记录边缘表的一种表示方法链码规定了边缘表中每一个边缘点的轮廓方向，其中方向被量化为四个或八个方向中的一个,9,曲线的链码是： 6022222021013444444454577012 其差分链码是： 220000627712100000017120111,10,曲线的链码是： 024444424323566666676711234 其差分链码是： 22000062771210000017130111,11,链码的特殊性质: 一个物体很容易实现45 角旋转如果一个物体旋转Nx45，可由原链码值加上N后再模8得到N逆时针为正，顺时针为负。 链码的微分，也称差分码，由原码的一阶差分求得链码差分是关于旋转不变的边界描述方法 链码的问题： 表示某一点正切方向的集合是有限的（邻接链码有4个，8邻接链码有8个）。,12,用任意的正切方向来表示轮廓可以克服链码的只能用有限个正切方向来表示轮廓的局限性假定从边缘表开始，计算正切和弧长的投影s ，画出正切同弧长的投影的关系图，称作s图,数字曲线表示2K斜率,13,一个轮廓及其s图对于封闭轮廓，s图是一个周期曲线,轮廓,s,14,三种常用的曲线模型拟合边缘点的方法： (1)直线段(Line Segment) (2)圆锥曲线段(Conic Section) (3)三次样条曲线段(Cubic Spline) 用曲线模型拟合边缘点应考虑如下两个问题： (1) 用什么算法进行边缘点的曲线模型拟合？ (2) 如何测量拟合的逼近程度？,7.2 曲线拟合,15,设di是拟合曲线和候选点之间的误差 （1）最大绝对误差(Maximum Absolute Error,MAE): 测量最坏情况下边缘点偏离曲线的距离。,（2）均方差(Mean Squared Error,MSE): 给出边缘点偏离拟合曲线的总的测度。,常用的误差测量方法,16,（3）规范化最大误差(Normalized Maximum Error, NME): 最大绝对误差与曲线长度S之比。,17,（5）误差符号变化数: 用来表示轮廓边缘模型的曲线适合程度的测度,（4）曲线长度与端点距离之比: 曲线复杂程度的测度。,18,多直线段是指端点连结端点的直线段序列，直线段序列的连接点称为顶点最大规范误差常常作为线段拟合边缘列表好坏的量度.,7.2.1 多直线段表示,19,自顶而下的分裂算法(top-down splitting)： 将整条曲线作为初始曲线，通过反复增加顶点数来进行直线段拟合曲线,方法1:直线段分裂方法,20,线段合并(merging)是指用一条直线段尽量多地拟合边缘表中的边缘点当边缘点离直线段太远而无法用该直线段拟合时，则开始新的直线段拟合合并方法也称为自底而上(bottom-up merging)的多线段拟合方法,方法2:直线段合并方法,21,确定边缘点离直线段的距离有许多种方法 一种方法是使用序贯最小二乘法，完成直线段到边缘点的最小二乘法拟合，并在每次处理新的边缘点时递增地更新线段参数拟合算法将计算直线段模型和边缘点之间的偏查平方当偏差超过某一阈值时，引进一个顶点，并将上一个线段的端点作为新的起点开始新的直线段拟合,22,误差带算法是另一种确定顶点位置的方法，主要工作是计算两条平行且离中心线距离为的直线段值表示离中心直线的绝对偏离值只要新的边缘在误差带内，就可以用当前拟合直线表示该边缘当新的边缘增加到线段内时，线段的参数要重新计算逼近直线段不必与误差带边保持平行位于线段端点的顶点是下一线段的起点,23,自顶而下的迭代分解方法和自底而上的合并方法组合起来，形成合并和分裂算法 单独使用分裂或合并算法时，成功率往往不是很高，改进的方法是交叉使用分裂和合并算法分解过程以后，如果新的线段以很小的规范误差拟合边缘，则允许用单一直线段代替邻接线段请注意，由于多直线段总是比单直线段的拟合误差小，因此很有必要使用规范化误差在线段合并后，新的线段可能在不同点处分裂这样，分裂和合并交替作用直到没有线段被合并和分裂为止,方法3:分裂和合并,24,(a)原始边缘点集 (b)自底而上的边缘合并方法产生的坏角点估计 (c) 漏掉的真实角点位置由分裂和合并过程来修补,25,算法7.1 一种有效的多线段拟合算法, 从边缘表中的前k个边缘构成的子表开始； 用直线段拟合子表中第一和最后一个边缘之间的边缘点； 如果某点的规范化最大误差太大，则将子表缩到最大误差 对应的边缘点处，回到步骤 ；这样一直进行下去，就 可以得到第一条拟合直线段，这实际上是分裂算法 置当前新线段为旧线段，向前移动边缘窗口使得k个边缘 在子表中，返回步骤 。用分裂算法求取第二条拟合直线 段 比较当前直线段和原直线段的方向，如果它们具有相似方 向，则将这两条直线段合并,这是合并算法；,26,有三种类型的锥形曲线：双曲线，抛物线和椭圆，其中圆是椭圆的一种特殊情况在几何上，锥形曲线定义为锥体与平面的相交曲线.,7.2.2 锥形曲线(二次曲线),圆锥曲线表示如下：,27,用直线段拟合一个圆弧可能需要许多个直线段才能满足拟合误差如果将这些直线段用一个圆弧段来拟合，则仅需要一条圆弧段即可因此可见，圆弧段拟合比直线段能拟合得更紧凑。圆弧段拟合是在多边形的顶点上进行的。,（1）圆弧段,28,1.将顶点窗口初始化为仅包含前两个直线段的三个顶点; 2.计算两个直线段对应的轮廓长度与两个端点之间距离的 比值如果这一比值很大，则保留第一个直线段不动， 将窗口向前移动一个顶点，然后重复这一步; 3.用一个圆来拟合这三个顶点; 4.计算规范化最大误差和符号变化数; 5.若规范化最大误差太大或符号数太小，则保留第一个直 线段不动，将窗口向前移动一个顶点，返回步骤2; 6.如果圆弧段拟合成功，则尽力让该圆弧段合并下一个直 线段重复这一过程，直到没有直线段被合并为止; 7.圆弧段拟合结束后，移动顶点窗口到下一个多直线段顶 点，返回步骤2,算法72 用圆弧段代替直线段算法,29,圆锥曲线可以拟合轮廓多直线段上的三个顶点将圆锥曲线段连接在一起的点称为结点圆锥样条曲线是圆锥曲线的一个序列，它们的端点和端点连接在一起，在结点处具有相等的正切，以便使两个邻接曲线段之间平滑过渡,(2) 圆锥曲线,30,圆锥样条中的每一个圆锥曲线由两个端点、两个正切和第三点确定结点位于多线段顶点之间：,第三点定义为：,31,7.3 样条曲线,早期绘图员在制图时，使用一种富有弹性的细长条，称为样条。用压铁将样条固定在若干样点上，然后沿样条可以画出很光滑的曲线，人们将该曲线称为样条曲线从数学上讲，样条曲线是用分段多项式表示的一个函数，在其连接点处具有连续的一阶和二阶导数 样条曲线有着许多应用在数据分析中，当没有合适的函数模型时，可以选用样条函数拟合数据点在计算机图形和计算机辅助设计中，样条函数用来表示自由曲线在机器视觉中，若没有表示曲线的合适模型时，样条函数可以提供曲线的通用表示形式,举MS WORD里的样条曲线的例子！,32,几何等效和参数等效的概念: 两条曲线在几何上等效，是指它们连接相同的点集，即它们在空间上对应着相同的形状（或点集）如果两条曲线的方程一样，则两条曲线在参数上等效,33,显然，参数等效性比几何等效性更稳定两条曲线可以是几何上等效但可以具有不同的参数表示式，这是机器视觉中曲线拟合的一个重要概念比如，机器视觉系统可以产生基于三次样条曲线的表示，其在几何上非常接近于物体轮廓的真实表示，但在参数意义上，表示可能完全不同在物体识别应用方面和工业零件图像与其模型匹配应用中，通过比较三次样条曲线的参数形式实现匹配几乎是不可能的，在这种情况下，比较必须基于几何等效性,34,在数学上，光滑程度的定量描述是：函数(曲线)的k阶导数存在且连续，则称该曲线具有k阶光滑性。光滑性的阶次越高，则越光滑。是否存在较低次的分段多项式达到较高阶光滑性的方法？三次样条曲线就是一个很好的例子。,7.3.1 三次样条曲线,35,三次样条是三次曲线的一个序列 样条中的每一个三次曲线称为样条段 连结样条段的边缘点称为结点,36,三次样条曲线是一个三次多项式函数的集合：,要确定这个三次样条曲线，就要确定 等4n个参数。,37,边界条件:,以上总共4n个方程！,38,7.3.2 B样条曲线,式中B0,B1,B2,B3为参数 的三次多项式，如何确定上式四个多项式所对应的16个参数 ?,B样条曲线是由结点引导的逐段多项式曲线，是一种平滑和内插技术B样条与上述三次样条曲线不同，它不必通过结点，我们将这种结点称为引导结点,已知引导结点序列为P0,P1,Pn，则三次B样条多项式为：,39,7.3.2 B样条曲线,相邻曲线段Pi(t),Pi+1(t)端点以及一阶二阶导数必须连续的条件提供15个等式:,五个等式,五个等式,40,41,B样条曲线示意图 （a）直线 (b) 二次B样条曲线 （c）三次B样条曲线,通常，m次的样条包含在由m+1控制点确定的多边形内。,42,7.4 曲线回归逼近,直线段、圆弧段、圆锥曲线和三次样条拟合边缘点的方法属于一般回归问题，主要用于端点之间的曲线拟合这些算法都假定边缘的位置可以精确计算，甚至可能使用子像素计算方法这种回归算法没有使用端点之间的边缘点信息，因此曲线的拟合精度主要取决于端点的位置精度本节讨论的曲线回归逼近方法将使用所有边缘点信息,43,一般曲线拟合问题是一个曲线的回归问题, 曲线用p个参数的隐函数表示：,在无噪声情况下，通过p次观测产生的p个方程来求解p个未知曲线参数不幸的是在大多数场合，由于噪声的原因，这一直接方法不是很有效实际的应用常常需要使用边缘表中所有信息来获取这些参数的最佳估计,曲线拟合（预估）问题就是指这种曲线模型拟合一个边缘点集：,44,（1）全回归方法（最小二乘法）,对数据点与回归模型之间垂直距离平方和进行极小化.,最小二次回归方法在计算机视觉中主要用于曲线拟合当误差服从正态分布时，最小二次方法是最合适的拟合方法,45,为观测值,例子：（直线）,直线的极坐标形式：,46,对于正态分布的点集，最小二乘法可以得到最佳估计，但对于不服从正态分布的局外点很敏感。,全回归方法的缺点,47,（2）鲁棒回归法,设Z是n个数据点的集合，将Z集合中任意m个点的坐标设置成任意值（局外点），构成一个含有m个任意点的集合Z,已知回归预估器:,由局外点引起的偏差：,48,溃点定义:,溃点定义：溃点是指局外点占整个数据的一个最大比例值，当局外点数不超过这个值时，无论局外点如何不正确，都不会使预估算法产生任意的错误估计.,此处课本有误！,49,设置溃点的基本思想是定量分析局外点的数量在数据点数量n中所占比例增加时对值的影响程度当增加到一定数量时，无界，这就是溃点当低于溃点时，回归估计器可以完全拒绝局外点，或使得局外点对预估结果影响很小当高于溃点时，局外点可以驱使预估器产生任意的解案，答案将取决于局外点而不是合法数据换句话说，预估器所提供的结果是不可预估的,50,最小中值二乘回归方法被证明是解决大量局外点回归问题的非常简单、有效的方法容错高达百分之五十的局外点，也就意味着数据点集中，有一半的数据可以取任意值而不会严重地影响回归结果 在最小中值二次回归方法中，模型参数 的估计 由极小化残差平方的中值求得:,最小中值二乘回归方法,51,假定有n个数据和p个参数的线性模型 在n各个数据点集中，随机地选择p个点; 用模型拟合p个点; 计算残差平方的中值; 拟合过程重复进行直到得到足够小的残差平 方中值.,算法7.3 最小中值二乘回归方法,52,Hough变换是基于表决原理的参数估计方法 在图像处理领域，是一种重要的形状检测技术. 基本思想： 图像中每一点对参数组合进行表决，赢得多数票的参数组合为胜者（结果）,7.5 Hough 发音hok变换,53,以检测直线为例：,以(x, y)为自变量，(m, c)为因变量 每个点(x,y)对应于空间(m,c)上的一条直线,y,x,c,m,54,直线方程表示存在的问题：垂直时斜率（m）趋于无穷大！ 极坐标表示：,空间与 空间的变换,y,x,55,图7.16 Hough变换示意图。 左边:为图像空间 右边:为Hough变换空间 (a)一条直线对应一个点 (b) 一条直线上的多个点对应多条交于一点的直线 (c) 一条直线上的多个点对应多条交于一点的正弦曲线,56,如果我们对求点的最佳直线拟合感兴趣，那么，我们就可以使用上述图像空间到参数空间的映射这种方法称为Hough变换在这种方法中，我们把参数空间表示为一个累加器阵列，表示离散参数值依照变换方程，图像中的每一点可以表决几个参数为了求出表征直线的参数，我们应该探测参数空间的峰值这种一般的想法概括在算法7.4中,57,适当地量化参数空间 假定参数空间的每一个单元都是一个累加器， 把累加器初始化为零 对图像空间的每一点，在其所满足的参数方程对应 的累加器上加1 累加器阵列的最大值对应模型的参数,算法7.4 Hough变换算法,58,59,60,61,Hough变换的演示程序：hough_transform.exe,62,由于沿着封闭轮廓的位置函数是周期性的，因此傅里叶级数可以用来逼近轮廓轮廓逼近的分辨率由傅里叶级数的项数来确定假定物体的边界表示为一个坐标的序列u(n)=x(n),y(n)，其中n=0,1,2,N-1用复数来表示每一个坐标对，即u(n)=x(n)+jy(n) .注意，对于封闭边界，这一序列是周期的，其周期是N，这样，边界就可以在一维空间表示,7.6 傅立叶描述子（Fourier descriptor）,63,用傅立叶级数表示边缘，傅立叶级数的系数称为傅立叶描述子,采用前个系数逼近,64,
展开阅读全文