轮廓表示--精确表示轮廓的影响因素.ppt

2019年8月25感谢你的观看1第7章轮廓表示2019年8月25感谢你的观看2把边缘连接起来就成为轮廓(contour)．轮廓可以是断开的，也可以是封闭的.轮廓可以用边缘有序表或曲线来表示。曲线通常称为轮廓的数学模型．曲线表示包括线段、二次曲线、三次样条曲线等．轮廓表示的评价标准：效率：轮廓应该是一种简单和紧凑的表示．精确：轮廓应能精确地逼近图像特征．有效：轮廓应适合于后续应用阶段的计算．2019年8月25感谢你的观看3精确表示轮廓的影响因素：•用于轮廓建模的曲线形式；•曲线拟合算法的性能；•边缘位置估计的精确度。2019年8月25感谢你的观看4定义：•边缘表是边缘点或边缘段的有序集合,轮廓的最简单表示形式。•轮廓是边缘表或用于表示边缘表的曲线。•边界是包围一个区域的封闭轮廓。轮廓曲线拟合通常采用内插曲线或逼近曲线来实现．已知一组称为控制点的坐标点，内插是指一条曲线拟合这组控制点，使得曲线通过所有的控制点；逼近是指一条曲线拟合这组这组控制点，使得这条曲线非常接近这些控制点而无需一定通过这些点．2019年8月25感谢你的观看5设Pi=(xi,yi)是边缘表中第i个边缘坐标．(1)k斜率是在边缘表相距k个边缘点的两个边缘点之间的（角）方向向量．(2)左k斜率是Pi指向Pi–k的方向，(3)右k斜率是Pi指向Pi+k方向．(4)k曲率是左右k斜率之差值。7.1数字曲线及其表示2019年8月25感谢你的观看6niiiiiyyxxS221212121yyxxDnn(6)轮廓端点之间的距离为(5)数字曲线的长度可以近似为像素之间的线段和：2019年8月25感谢你的观看7数字曲线表示1－链码定义：链码是沿着轮廓记录边缘表的一种表示方法．链码规定了边缘表中每一个边缘点的轮廓方向，其中方向被量化为四个或八个方向中的一个．　　)90(1)180(2　　　)0(0　　　　　)270(3　)90(2)135(3　　)45(1)180(4　　　)0(0)225(5　　　)315(7　　　)270(62019年8月25感谢你的观看8曲线的链码是：6022222021013444444454577012其差分链码是：220000627712100000017120111　)90(2)135(3　　)45(1)180(4　　　)0(0)225(5　　　)315(7　　　)270(62019年8月25感谢你的观看9曲线的链码是：024444424323566666676711234其差分链码是：22000062771210000017130111　)90(2)135(3　　)45(1)180(4　　　)0(0)225(5　　　)315(7　　　)270(62019年8月25感谢你的观看10链码的特殊性质:•一个物体很容易实现45角旋转．如果一个物体旋转Nx45°，可由原链码值加上N后再模8得到．N逆时针为正，顺时针为负。•链码的微分，也称差分码，由原码的一阶差分求得．链码差分是关于旋转不变的边界描述方法．链码的问题：表示某一点正切方向的集合是有限的（４－邻接链码有4个，8－邻接链码有8个）。2019年8月25感谢你的观看11用任意的正切方向来表示轮廓可以克服链码的只能用有限个正切方向来表示轮廓的局限性．假定从边缘表开始，计算正切和弧长s，画出正切同弧长的关系图，称作s图．数字曲线表示2－K斜率2019年8月25感谢你的观看1290450-45-90一个轮廓及其s图．对于封闭轮廓，s图是一个周期曲线．2019年8月25感谢你的观看13三种常用的曲线模型拟合边缘点的方法：(1)直线段(LineSegment)(2)圆锥曲线段(ConicSection)(3)三次样条曲线段(CubicSpline)．用曲线模型拟合边缘点应考虑如下两个问题：(1)用什么方法进行边缘点的曲线模型拟合？(2)如何测量拟合的逼近程度？7.2曲线拟合2019年8月25感谢你的观看14设di是拟合曲线和候选点之间的误差．•最大绝对误差(MaximumAbsoluteError,MAE):测量最坏情况下边缘点偏离曲线的距离，MAEdiimax•均方差(MeanSquaredError,MSE):给出边缘点偏离拟合曲线的总的测度，MSEndiin121常用的误差测量方法2019年8月25感谢你的观看15Sdiimax•规范化最大误差(NormalizedMaximumError,NME):最大绝对误差与曲线长度S之比，2019年8月25感谢你的观看16•误差符号变化数:用来表示轮廓边缘模型的曲线适合程度的测度．符号变化是一种评价拟合好坏的很有用的参数．比如，用直线段逼近边缘表，并检测符号变化数．如果符号变化一次，则说明边缘点可以由直线段来逼近；符号变化两次，说明边缘可以由二次曲线逼近；符号变化三次，说明边缘模型是三次曲线，依此类推．如果符号变化数量很大，则意味着曲线复杂度增加一点将不能显著地改善拟合效果．一种好的拟合所对应的符号变化具有随机模式．相同符号连续出现多次说明存在拟合系统误差，这种误差可能是由于错误的曲线模型引起的．•曲线长度与端点距离之比:曲线复杂程度的测度．2019年8月25感谢你的观看17多直线段是指端点连结端点的直线段序列，直线段序列的连接点称为顶点．最大规范误差常常作为线段拟合边缘列表好坏的量度.Didi||max7.2.1多直线段表示2019年8月25感谢你的观看18自顶而下的分裂算法(top-downsplitting)：将整条曲线作为初始曲线，通过反复增加顶点数来进行直线段拟合曲线．ABCABCAB方法1:直线段分裂方法2019年8月25感谢你的观看19线段合并(merging)是指用一条直线段尽量多地拟合边缘表中的边缘点．当边缘点离直线段太远而无法用该直线段拟合时，则开始新的直线段拟合．合并方法也称为自底而上(bottom-upmerging)的多线段拟合方法．方法2:直线段合并方法确定边缘点离直线段的距离有许多种方法．一种方法是使用序贯最小二乘法，完成直线段到边缘点的最小二乘法拟合，并在每次处理新的边缘点时递增地更新线段参数．拟合算法将计算直线段模型和边缘点之间的偏查平方．当偏差超过某一阈值时，引进一个顶点，并将上一个线段的端点作为新的起点开始新的直线段拟合．2019年8月25感谢你的观看20误差带算法是另一种确定顶点位置的方法，主要工作是计算两条平行且离中心线距离为ε的直线段．ε值表示离中心直线的绝对偏离值．只要新的边缘在误差带内，就可以用当前拟合直线表示该边缘．当新的边缘增加到线段内时，线段的参数要重新计算．逼近直线段不必与误差带边保持平行．位于线段端点的顶点是下一线段的起点．2019年8月25感谢你的观看21自顶而下的迭代分解方法和自底而上的合并方法组合起来，形成合并和分裂算法．单独使用分裂或合并算法时，成功率往往不是很高，改进的方法是交叉使用分裂和合并算法．分解过程以后，如果新的线段以很小的规范误差拟合边缘，则允许用单一直线段代替邻接线段．请注意，由于多直线段总是比单直线段的拟合误差小，因此很有必要使用规范化误差．在线段合并后，新的线段可能在不同点处分裂．这样，分裂和合并交替作用直到没有线段被合并和分裂为止．方法3:分裂和合并2019年8月25感谢你的观看22(a)原始边缘点集．(b)自底而上的边缘合并方法产生的坏角点估计．(c)漏掉的真实角点位置由分裂和合并过程来修补2019年8月25感谢你的观看23算法7.1一种有效的多线段拟合算法从边缘表中的前k个边缘构成的子表开始；用直线段拟合子表中第一和最后一个边缘之间的边缘点；如果某点的规范化最大误差太大，则将子表缩到最大误差对应的边缘点处，回到步骤；这样一直进行下去，就可以得到第一条拟合直线段，这实际上是分裂算法．置当前新线段为旧线段，向前移动边缘窗口使得k个边缘在子表中，返回步骤。用分裂算法求取第二条拟合直线段．比较当前直线段和原直线段的方向，如果它们具有相似方向，则将这两条直线段合并,这是合并算法；2019年8月25感谢你的观看24有三种类型的锥形曲线：双曲线，抛物线和椭圆，其中圆是椭圆的一种特殊情况．在几何上，锥形曲线定义为锥体与平面的相交曲线.7.2.2锥形曲线(二次曲线)0222),(22cgyexbyhxyaxyxf圆锥曲线表示如下：2019年8月25感谢你的观看25用直线段拟合一个圆弧可能需要许多个直线段才能满足拟合误差．如果将这些直线段用一个圆弧段来拟合，则仅需要一条圆弧段即可．因此可见，圆弧段拟合比直线段能拟合得更紧凑。圆弧段拟合是在多边形的顶点上进行的。()()xxyyr02022(1)圆弧段2019年8月25感谢你的观看261.将顶点窗口初始化为仅包含前两个直线段的三个顶点;2.计算两个直线段对应的轮廓长度与两个端点之间距离的比值．如果这一比值很大，则保留第一个直线段不动，将窗口向前移动一个顶点，然后重复这一步;3.用一个圆来拟合这三个顶点;4.计算规范化最大误差和符号变化数;5.若规范化最大误差太大或符号数太小，则保留第一个直线段不动，将窗口向前移动一个顶点，返回步骤2;6.如果圆弧段拟合成功，则尽力让该圆弧段合并下一个直线段．重复这一过程，直到没有直线段被合并为止;7.圆弧段拟合结束后，移动顶点窗口到下一个多直线段顶点，返回步骤2．算法7．2用圆弧段代替直线段算法2019年8月25感谢你的观看27圆锥曲线可以拟合轮廓多直线段上的三个顶点．将圆锥曲线段连接在一起的点称为结点．圆锥样条曲线是圆锥曲线的一个序列，它们的端点和端点连接在一起，在结点处具有相等的正切，以便使两个邻接曲线段之间平滑过渡．(2)圆锥曲线2019年8月25感谢你的观看28圆锥样条中的每一个圆锥曲线由两个端点、两个正切和第三点确定．结点位于多线段顶点之间：1)1(iiiiiVvVvK其中iv取0和1之间的数值2)1(11iiiiiiKKVZ第三点定义为：直线段若0)1(1iv角点若0,1)2(1iivviK2019年8月25感谢你的观看297．3样条曲线早期绘图员在制图时，使用一种富有弹性的细长条，称为样条。用压铁将样条固定在若干样点上，然后沿样条可以画出很光滑的曲线，人们将该曲线称为样条曲线．从数学上讲，样条曲线是用分段多项式表示的一个函数，在其连接点处具有连续的一阶和二阶导数．样条曲线有着许多应用．在数据分析中，当没有合适的函数模型时，可以选用样条函数拟合数据点．在计算机图形和计算机辅助设计中，样条函数用来表示自由曲线．在机器视觉中，若没有表示曲线的合适模型时，样条函数可以提供曲线的通用表示形式．2019年8月25感谢你的观看30几何等效和参数等效是两个不同的概念．两条曲线在几何上等效，是指它们连接相同的点集，即它们在空间上对应着相同的形状（或点集）．如果两条曲线的方程一样，则两条曲线在参数上等效．显然，参数等效性比几何等效性更稳定．两条曲线可以是几何上等效但可以具有不同的参数表示式，这是机器视觉中曲线拟合的一个重要概念．比如，机器视觉系统可以产生基于三次样条曲线的表示，其在几何上非常接近于物体轮廓的真实表示，但在参数意义上，表示可能完全不同．在物体识别应用方面和工业零件图像与其模型匹配应用中，通过比较三次样条曲线的参数形式实现匹配几乎是不可能的，在这种情况下，比较必须基于几何等效性．2019年8月25感谢你的观看31比分段线性插值更光滑xyxi-1xiab在数学上，光滑程度的定量描述是：函数(曲线)的k阶导数存在且连续，则称该曲线具有k阶光滑性。光滑性的阶次越高，则越光滑。是否存在较低次的分段多项式达到较高阶光滑性的方法？三次样条插值就是一个很好的例子。三次样条插值2019年8月25感谢你的观看32},1],,[),({)(1nixxxxsxSiii),1()(23nid