搜索
第七章轮廓表示Chapter7ContourRepresentationComputerVisionDepartmentofComputerScience@BIT轮廓（Contour）•轮廓是物体在场景中的完整边界，是重要的特征和形状表示方法，是计算机视觉和模式识别领域中的基本工具之一，在图像分割、识别、跟踪等方面有广泛应用.•边缘的连接构成轮廓.•轮廓可以是断开的，也可以是封闭的.•主要问题：表示与获取ComputerVisionDepartmentofComputerScience@BIT轮廓表示（ContourRepresentation）•直接表示方法离散（边缘有序表）、连续（曲线）、变形（主动轮廓模型，activecontourmodelorsnake）•间接表示方法傅立叶描述子（Fourierdescriptor）、边界矩(boundarymoment)、简单形状描述子（面积、凸性、主轴方向等等）ComputerVisionDepartmentofComputerScience@BIT轮廓表示•评价标准精确：尽可能逼近原始形状高效：尽可能简单和紧凑有效：适合于后续处理•影响轮廓表示精确性的因素：1.边缘位置估计的精确度2.用于轮廓建模的曲线形式3.曲线拟合算法的性能ComputerVisionDepartmentofComputerScience@BIT7.1数字曲线（边缘有序表）•直接用边缘点序列表示轮廓链码（chaincode）ψ−s图ComputerVisionDepartmentofComputerScience@BIT7.1.1链码•链码是用单位直线段序列表示轮廓曲线的方法．每个直线段是两个相邻边缘点的连线．4-连通关系对应四方向链码；8-连通关系对应八方向链码． )90(1ο)180(2ο )0(0ο )270(3ο )90(2ο)135(3ο )45(1ο)180(4ο )0(0ο)225(5ο )315(7ο )270(6ο(Freeman,1961)ComputerVisionDepartmentofComputerScience@BIT曲线的链码是：6022222021013444444454577012其差分链码是：220000627712100000017120111曲线的链码是：024444424323566666676711234其差分链码是：22000062771210000017130111链码的有关性质•容易实现旋转：如果一个物体旋转，则旋转后的链码可由原码加n，然后模8得到．（八方向链码）•链码的微分，可由原码的一阶差分求得，也称差分码。链码差分具有旋转不变性.•可以由链码直接求出区域的一些性质，如面积和角点等.°45°×45nComputerVisionDepartmentofComputerScience@BIT链码的不足•角度量化，只能表示有限正切方向•表示效率低，不简洁•对噪声敏感通常作为高层分析过程的输入，如用于多直线段近似，计算边界曲率等等.ComputerVisionDepartmentofComputerScience@BIT7.1.2ψ−s图•ψ−s图是边缘正切方向ψ与弧长s的关系图，是形状在ψ−s空间中的紧凑表示．•ψ计算方法-k斜率边缘表上相距k个边缘点的两个边缘点之间的方向向量，称为k斜率•s计算方法-相邻像素之间的线段和()()∑=−−−+−=niiiiiyyxxS22121ComputerVisionDepartmentofComputerScience@BIT90450-45-90一个轮廓及其ψ−s图对于封闭轮廓，ψ−s图是一个周期曲线ψ−s图常用于轮廓分段ComputerVisionDepartmentofComputerScience@BIT7.2曲线拟合•曲线拟合是用曲线表示轮廓边缘的过程，通常对轮廓的曲线形式预先做出假设，如直线、二次曲线、三次样条曲线等等，称为轮廓的曲线模型．•曲线拟合分为内插和逼近两种方式：内插要求曲线通过所有边缘点．逼近要求曲线尽可能接近边缘点，但不要求一定通过边缘点．ComputerVisionDepartmentofComputerScience@BIT曲线拟合•要素(1)曲线模型：直线段(linesegment)，圆锥曲线段(conicsection)，样条曲线段(spline)(2)曲线模型的拟合方法(3)拟合逼近（误差）程度的测量方法ComputerVisionDepartmentofComputerScience@BIT7.2.1几种常用的误差测量方法•昀大绝对误差MAE:边缘点偏离拟合曲线的昀大距离MAEdii=max•均方差MSE:边缘点偏离拟合曲线的平均距离MSEndiin==∑121ComputerVisionDepartmentofComputerScience@BIT7.2.1几种常用的误差测量方法•规范昀大规范误差NME:昀大绝对误差与曲线长度S之比SdNMEiimax=•误差符号变化次数:曲线适合程度的测度•曲线长度与端点距离之比:曲线复杂程度的测度ComputerVisionDepartmentofComputerScience@BIT7.2.2几种常用的曲线模型•多直线段•圆弧段•圆锥曲线段•样条曲线ComputerVisionDepartmentofComputerScience@BIT多直线段•多直线段是端点连结端点的直线段序列，直线段序列的连接点称为顶点。ComputerVisionDepartmentofComputerScience@BIT圆弧段•对于弧形边缘，圆弧段表示比直线段表示更为合适，也更紧凑。因此，在多直线段拟合以后，可以将其中的部分或全部直线段序列用圆弧段代替，实现直线段和圆弧段的混合表示．•圆弧拟合的要点：三点确定一段圆弧．ComputerVisionDepartmentofComputerScience@BIT二次曲线（圆锥截线）•二次曲线的一般表示：0222),(22=+++++=cgyexbyhxyaxyxf•二次曲线都是用平面切割正圆锥面的截线，包括三种类型：双曲线，抛物线和椭圆，圆是椭圆的特殊情况．ComputerVisionDepartmentofComputerScience@BIT圆锥曲线段•圆锥曲线段由两个端点、两个正切和第三点确定．（拟合要点）1)1(++−=iiiiiVvVvK•端点：2)1(11+++−+=iiiiiiKKVZγγiK:01•第三点：=+iv直线段•特殊情况：:011在圆锥曲线序列中有一个角点==+iivv且•提供了直线段、圆弧段以及其他二次曲线段的一般表示，更为方便、有效．ComputerVisionDepartmentofComputerScience@BIT样条曲线•样条曲线是用分段多项式表示的曲线函数，在连接点处具有连续的一阶和二阶导数．•样条曲线提供了灵活的曲线通用表示形式.•在计算机图形学与辅助设计，以及形状分析与建模中有广泛应用．•几何等效：曲线几何形状相同；参数等效：曲线函数一致．参数等效更严格．ComputerVisionDepartmentofComputerScience@BIT三次样条曲线•三次样条是三次多项式曲线（样条段）的序列，可以有效表示复杂曲线，为样条函数的昀常见形式．•三次样条曲线由n个结点所确定的n-1个三次参数曲线段组成，每个曲线段的参数取值范围[0,1]，总的参数取值范围[0,n-1]，结点处 kp 1p Λ1+kp np 0p Λ2pppiiuu()()=+1ComputerVisionDepartmentofComputerScience@BIT三次样条段•每个三次样条段为平面三次参数曲线：]1,0[,))(),(()(332210∈+++==uuuuuyuxuaaaap系数a0,a1,a2和a3是2-D向量•计算三次样条段，需确定四个系数（8个参数）：两个结点提供四个约束结点处的一阶连续性提供两个约束结点处的方向提供一个附加约束结点处的二阶连续性提供两个约束ComputerVisionDepartmentofComputerScience@BIT三次样条段•形成了过约束（约束个数大于参数个数）用结点处二阶不连续性的极小化条件（一个约束）代替二阶连续性条件（两个约束）•极小化所有结点处二阶导数差值的平方和，获得每个结点处的相应约束：χ211==−∑(&&)∆pin∆&&&&()&&()ppp=−−ii110=++++−+−243111(())tttppiiiii是结点i处的正切向量ti•样条拟合的任务是确定结点ComputerVisionDepartmentofComputerScience@BITB-样条曲线•B-样条曲线的基本形式与样条函数一致，但区别在于B-样条曲线不一定通过结点，因此通常称为控制点（或引导结点）.[]1,0•三次B-样条段是四个参数取值范围在之间的三次多项式的线性组合：()()[]1,0)()()(3322110∈+++=+++ttQtQtQtQtiiiii，CCCCrComputerVisionDepartmentofComputerScience@BITB-样条曲线•根据B-样条在各曲线段连接点处的二阶连续性约束以及B-样条对于坐标变换的形状不变性约束，可以求出四个三次多项式:•整个B-样条曲线可以表示为：()()()()()()()332322313061,133361,46361,161ttQttttQtttQttQ=+++−=+−=−=，封闭曲线()()[]2,0,)(4,300−∈′′=−′=′∑∑−==nttQittininiiiCrr()()[]1,0,)(0304,+∈′′=−′=′∑∑=+=nttQittniniiiiCrr，开放曲线231201,,CCCCCC===+++nnnComputerVisionDepartmentofComputerScience@BITB-样条曲线•为B-样条基函数，各基函数形状相同，彼此相差一个平移：()tQi′4,•B-样条曲线拟合的任务是确定控制点．ComputerVisionDepartmentofComputerScience@BIT7.3曲线拟合方法•多直线段拟合•基于多直线段的拟合圆弧、圆锥曲线、三次样条•曲线回归•主曲线ComputerVisionDepartmentofComputerScience@BIT7.3.1多直线段拟合•方法自顶向下的分裂方法（迭代分解）自底向上的合并方法分裂-合并方法•误差测度常采用规范化昀大误差ComputerVisionDepartmentofComputerScience@BIT多直线段分裂方法ABCABCAB•初始用一条直线段表示整条曲线，然后通过反复增加顶点数不断提高拟合精度.分裂时，以距离多直线段昀远的边缘点为新的顶点，将一条对应直线段分裂为两条.ComputerVisionDepartmentofComputerScience@BIT多直线段合并•初始用边缘点前后相连构成的多直线段表示曲线，然后逐步减少顶点个数以提高表示效率．•序贯昀小二乘法：从起始边缘点开始，逐步增加边缘点的个数，并用昀小二乘法实现直线段拟合，直到新增加的边缘点离所拟合的直线段太远时为止，此时以当前边缘点为起点开始新的直线段拟合．ComputerVisionDepartmentofComputerScience@BIT多直线段合并•误差带算法：BCAD计算两条离中心线距离为ϕ且平行于拟合边缘点的直线段，形成一个带状区域．区域内的所有边缘点对应一条直线段，从区域边界处的边缘点开始新的直线段．ComputerVisionDepartmentofComputerScience@BIT多直线段分裂－合并•分裂方法与合并方法的组合，交替进行直线段分裂与合并。先分裂后合并来修补坏顶点的位置ComputerVisionDepartment