北理工贾云德《计算机视觉》chapter07轮廓表示

1第七章轮廓表示把边缘连接起来就成为轮廓(contour)．轮廓可以是断开的，也可以是封闭的．封闭轮廓对应于区域的边界，而区域内的像素可以通过填充算法来填满．断开的轮廓可能是区域边界的一部分，也可能是图像线条特征，如手写体笔画、图画中的线条等．区域之间的对比度太弱或边缘检测阈值设置太高都有可能产生间断的轮廓．轮廓可以用边缘序列表或曲线来表示．曲线通常称为轮廓的数学模型．曲线表示包括线段、二次曲线、三次样条曲线等．下面是几种轮廓表示的评价标准：高效：轮廓应该是一种简单和紧凑的表示．精确：轮廓应能精确地逼近图像特征．有效：轮廓应适合于后处理阶段的计算．轮廓表示的精确性由以下三个方面因素决定：①用于轮廓建模的曲线形式；②曲线拟合算法的性能；③边缘位置估计的精确度．轮廓的最简单表示形式是边缘有序表．这种表示的精确度就是边缘估计的精确度，但其表示的紧凑性是最差的，因此不是一种有效的后续图像分析表示方法．用适当的曲线模型来拟合边缘会提高精确度，这是因为曲线模型拟合边缘时往往具有均值化效应，因而可以减少边缘位置误差．曲线模型也会提高轮廓表示的经济性，为后处理提供了一种更适合、更紧凑的表示，例如，一条直线上的边缘集用一直线来拟合是表示这些边缘的最简单和最有效的方法，这一表示也简化了后续处理（如确定线的长度和方向）；另外，由于估计直线与真实直线的均值方差小于真实直线与任何其它边缘之间的均值方差，因此可以说这种表示也增加了精确度．轮廓曲线拟合通常采用内插曲线或逼近曲线来实现．已知一组称为控制点的坐标点，内插是指一条曲线拟合这组控制点，使得曲线通过所有的控制点；逼近是指一条曲线拟合这组这组控制点，使得这条曲线非常接近这些控制点而无需一定通过这些点．在下面几节中，假定由边缘检测器得到的边缘十分准确，并使用内插值方法进行边缘曲线拟合．定义7．1边缘表是边缘点或边缘段的有序集合．定义7．2轮廓是边缘表或用于表示边缘表的曲线．定义7．3边界是包围一个区域的封闭轮廓．在无特别说明的情况下，边缘通常是指边缘点．对大多数曲线拟合算法来说，只需要边缘的位置信息。在很少的几种情况下，即需要边缘位置信息，也需要方向角信息，此时的边缘是指边缘段．平面曲线函数可以表示为三种形式：显式)(xfy,隐式),(yxf，或参数式))(),((uyux,其中u是某一参数．函数的显式表示很少用在机器视觉中，主要原因是yx平面上的曲线可能卷曲，使得一个x值可能对应曲线上多个y值．7．1数字曲线及其表示本节将讨论一组计算曲线几何元素的算法，几何元素包括轮廓长度、正切方向角和曲率等．由于邻接像素之间的量化增量是45，因此，精确计算斜率和曲率是很困难的．2估计正切方向角的基本思路是使用边缘表中非邻接的边缘点，这就允许存在一个较大的可能正切方向角集合．设),(iiiyxp是边缘表中第i个边缘坐标．k斜率是在边缘表相距k个边缘点的两个边缘点之间的方向向量．左k斜率是pik指向pi的方向，右k斜率是pi指向pik方向．k曲率是左右k斜率之差值．假定在边缘表中有n个边缘),(,),,(),,(2211nnyxyxyx．数字曲线的长度可以近似为像素之间的线段和：niiiiiyyxxS22121(7．1)轮廓端点之间的距离为：2121yyxxDnn(7．2)7．1．1链码链码是沿着轮廓记录边缘表的一种表示方法．链码规定了边缘表中每一个边缘点所对应的轮廓方向，其中的轮廓方向被量化为４－邻接链码或８－邻接链码中的一个，如图7．1所示．图7．2所示的是一条曲线及其８－邻接链码的表示，8－邻接链码从边缘表中第一个边缘开始，沿着轮廓按逆时针方向行走，行走方向用八链码中的一个表示．（a）（b）图7．1连接边缘点方向的链码示意图，（a）４－邻接链码，(b)8－邻接链码链码有一些很特殊的的性质．一个物体很容易实现45角旋转．如果一个物体旋转n45，旋转后的物体链码可由原链码加上n倍的模8得到．链码的微分，也称差分码，可由原码的一阶差分求得．链码差分是关于旋转不变的边界描述方法．比如，图７．２曲线的链码是：6022222021013444444454577012其差分链码是：220000627712100000017120111图７．３是图７．２曲线逆时针旋转90后得到的，曲线的链码是：024444424323566666676711234其差分链码是：22000062771210000017130111由此可见，一条曲线旋转到不同的位置将对应不同的的链码，但其差分链码不变，即差分链码关于曲线旋转是不变的．区域的一些其它性质，如面积和角点，也可以由链码直接求得．这种表示的局限性是表示某一点正切方向的集合是有限的（４－邻接链码有4个，8－邻接链码有8个），这一局限性可以通过下面几节介绍的曲线表示方法来克服．3图7．2一条曲线及其８－邻接链码表示图7．３一条曲线及其８－邻接链码表示7．1．2斜率表示法用任意的正切方向来表示轮廓可以克服链码的只能用有限个正切方向来表示轮廓的局限性．假定从边缘表开始，使用上面给出的公式计算正切和弧长，可以画出正切同弧长s的关系图，称作s图．s图是轮廓形状在s空间的表示，是一种轮廓形状的紧凑描述．图７．４所示的是包含有直线段和圆弧段的轮廓在s空间中的表示，它是一个直线段序列．对于封闭轮廓，s图是一个周期曲线．在s图中，水平方向的直线段对应轮廓中的直线段，这是由于直线段对应的斜率是恒定值。其它方向的直线段对应圆弧段，非直线段部分对应曲线基元．如果把s图分割成直线段，也就把轮廓分割成直线段和圆弧段．许多研究人员采用这一方法来分割轮廓，由此产生了轮廓分段方法的多种形式．490450-45-90图7．4轮廓的斜率表示7．2曲线拟合本章将讨论三种常用的曲线模型拟合边缘点的方法：直线段(LineSegment)，圆锥曲线段(ConicSection)和三次样条曲线段(CubicSpline)．一般来说，在用曲线模型拟合边缘点之前应考虑如下两个问题：用什么方法进行边缘点的曲线模型拟合？如何测量拟合的逼近程度？下面几节将讨论曲线模型拟合边缘点方法，其中假设边缘位置足够精确，不会对拟合结果产生影响．设di是边缘点到一条拟合曲线的距离，该距离值有正负符号，在曲线同一侧的边缘具有相同的正符号或负符号．目前有许多种测量曲线与候选边缘点的拟合效果方法，每一种都取决于拟合曲线和候选点之间的误差．下面是一些常用的方法．(1)最大绝对误差测量最坏情况下边缘点偏离曲线的距离：||maxiidMAE(7．3)(2)均方差给出边缘点偏离拟合曲线的总的测度：MSEndiin121(7．4)(3)最大规范（normal）误差最大绝对误差与曲线长度S之比：Sdii||max(7．5)(4)误差符号变化次数这里的误差就是指di，即边缘点偏离拟合曲线的距离。误差符号变化次数可用来表示轮廓边缘模型的曲线适合程度的测度．(5)曲线长度与端点距离之比曲线复杂程度的测度．符号变化是一种评价拟合好坏的很有用的参数．比如，用直线段逼近边缘表，并检测符号变化数．如果符号变化一次，则说明边缘点可以由直线段来逼近；符号变化两次，5说明边缘可以由二次曲线逼近；符号变化三次，说明边缘模型是三次曲线，依此类推．如果符号变化数量很大，则意味着曲线复杂度增加一点将不能显著地改善拟合效果．一种好的拟合所对应的符号变化具有随机模式．相同符号连续出现多次说明存在拟合系统误差，这种误差可能是由于错误的曲线模型引起的．曲线拟合模型的选择取决于应用场合．如果场景是由直线段组成，则使用直线段（或多线段）模型比较合适．直线段模型也可作为其它拟合模型的初始拟合模型．圆弧段是估计曲率的最有用的一种表示，因为曲线可以分割成具有分段恒定曲率线段．圆锥曲线段是一种表示直线段和圆弧段序列以及椭圆和高次弧段序列的有效方法．三次样条曲线适合于平滑曲线模型，因为三次样条曲线并不要求正切向量和曲率的估计值一定是分段恒定的．7．2．1多直线段多直线段是指端点连结端点的直线段序列，直线段序列的连接点称为顶点．多直线段适合具有线段序列的边缘列表的拟合．多线段算法的输入值是边缘点有序表{(,),(,),,(,)}xyxyxynn1122．边缘点坐标可以计算到子像素精度．由于线段的两个端点对应两个边缘点，即线段拟合在这两个边缘点之间进行，因此仅需要精确计算对应端点的两个边缘点的坐标．拟合边缘表并把第一和最后一个边缘点(,)xy11和(,)xykk连接起来的直线线公式如下：yyxxyyxxkk11(7．6)上式可以改写为由端点表示的隐式函数：0CByAx(7．7)其中，1111)()(yxyxCxxByyAkkkk而22BAD是边缘点(,)xy11和(,)xykk之间的距离．任意一点),(iiyx，设CByAxrii，则r的符号可以用来计算符号变化次数C．点),(iiyx与上述直线段的距离为：DCByAxdiii(7．8)最大规范误差为：Ddiimax(7．9)最大规范误差常常作为线段拟合边缘列表好坏的量度．需要指出的是上面的公式都是在点向直线段的垂直投影落在线段内这个假设下进行的．对于其它情况，则应修正公式，以便计算点到最近的线段端点的距离．下面介绍两种拟合多线段的方法：自顶而下的分裂和自底而上的合并．(1)多直线段分裂自顶而下的分裂算法(top-downsplitting)是将整条曲线作为初始曲线，通过反复增加顶点数来进行直线段拟合曲线．考虑图7．5所示的边缘点曲线（可以认为是由离散边缘点构成），将第一个和最后一个边缘点连成的直线作为曲线的初始拟合，用AB标记．在边缘表中计算最大规范误差，如果该误差值高于某一阈值，则在离直线段最远的边缘点上设置一个顶点，用C来标记．这样，将形成两个拟合直线段AC和CB，边缘表也分6割成对应于两个新直线段的两个子边缘表．在每一个子边缘表中，重复上面所述的分裂算法，形成两个新的直线段及对应的两个更小的子边缘表．这样的分裂过程可以一直进行下去，直到所有的直线段对应的最大规范误差均低于某一阈值为止．多线段分裂也称为迭代分解．(2)线段合并线段合并(merging)是指用一条直线段尽量多地拟合边缘表中的边缘点．当边缘点离直线段太远而无法用该直线段拟合时，则开始新的直线段拟合．合并方法也称为自底而上(bottom-upmerging)的多线段拟合方法．确定边缘点离直线段的距离有许多种方法．一种方法是使用序贯最小二乘法，完成直线段到边缘点的最小二乘法拟合，并在每次处理新的边缘点时递增地更新线段参数．拟合算法将计算直线段模型和边缘点之间的残差平方．当误差超过某一阈值时，引进一个顶点，并将上一个线段的端点作为新的起点开始新的直线段拟合．误差带算法是另一种确定顶点位置的方法，如图7．6所示，主要工作是计算两条离中心线距离为且平行于拟合边缘点的直线段．值表示离有差拟合直线的绝对偏离值．只要新的边缘在误差带内，就把这些边缘增加到当前线段内．当新的边缘增加到线段内时，线段的参数要重新计算．逼近直线段没有与误差带边保持平行．位于线段端点的顶点是下一线段的起点．这一方法常常产生大量的线段．由于算法须行进到边缘直到误差带表示的边界才产生角点，因此，不能精确估计角点位置和角度．ABCABCAB图7．5多直线段分裂方法7图7．6拟合直线段的误差带方法图(3)分裂和合并自顶而下的迭代分解方法和自底而上的合并方法组合起来，形成合并和分裂算法．单独使用分裂或合并算法时，成功率往往不是很高，改进的方法是交叉使用分裂和合并算法．分解过程以后，如果新的线段以很小的规范误差拟合边缘，则允许用单一直线段代替邻接线段．请注意，由于多直线段总是比单直线段的拟合误差小，因此很有必要使用规范误差．在线段合并后，新的线段可能在不同点处分裂．这样，分裂和合并交替作用直到没有线段被合并和分裂为止．图7．7所示的是先分裂后合并来修补坏顶点位置的示意图．一种有效的分裂和合并算法