北理工贾云德《计算机视觉》chapter13三维场景表示

1第十三章三维场景表示三维场景表示是机器视觉的又一个关键技术．为了理解场景并与场景中的物体交互作用，必须将场景的三维数据进行有效的表示．三维场景表示包含有两个基本问题：场景重建和场景分割．场景重建(reconstruction)是指使用插值或拟合方法从采样点(稠密深度测量值或稀疏深度测量值)计算曲面的连续函数，实际中通常使用许多三角片或小平面片构成的网面来近似表示场景深度测量值；场景分割是将表示场景的网面分割成若干部分，每一部分表示一个物体或一个特定的区域，这样有利于物体识别、曲面精确估计等后处理算法的实现．本章从曲面的几何特征开始，讨论场景曲面重建和分割的一些基本方法．这些方法可以将双目立体测距、主动三角测距、激光雷达测距等成像系统的输出值转换成简单的曲面表示．这些基本方法包括把测量点转变成三角片网面、把距离测量值分割成简单的曲面片、把测量点拟合成一个光滑曲面以及用测量点匹配一个曲面模型等．13．1三维空间曲线讨论三维空间曲线的原因主要有两个，一是一些物体或物体特征可以直接用三维空间曲线表示，二是三维空间曲线表示可以推广到三维空间曲面表示。曲线表示有三种形式：隐式、显式和参数式。在机器视觉领域中，曲线的参数表示比隐式和显式表示更为常用。三维曲线的参数形式为：))(),(),((),,(tztytxzyxpttt01(13．1)上式说明曲线上的一点可由参数t表示的三个函数来定义，曲线的起点为))(),(),((000tztytx，终点为))(),(),((111tztytx。比如，从),,(1111zyxp到),,(2222zyxp的直线段的参数方程为：111121212zyxzzyyxxtzyx（13．2）空间曲线的最通常的表示形式是三次多项式，下面我们将详细讨论．13．1．1三次样条曲线物体表面上的线条可以是直线、弧线或是任意的曲线．曲线上的每一点位置可以表示成参数形式))(),(),((tztytx．一般的三维曲线都可以方便地用样条函数来表示，这和前面讨论的平面曲线表示类似．三次样条函数是一系列首尾相连的表示复杂曲线的三次多项式曲线，每一段三次样条函数的参数表示形式为：zzzzyyyyxxxxdtctbtatzdtctbtatydtctbtatx232323)()()((13．3)其中01t．三次多项式允许曲线通过确定的相切点，三次多项式是对于非平面曲线的最低阶的多项式．将上式的系数表示成如下系数矢量：),,(),,(),,(),,(zyxzyxzyxzyxdddcccbbbaaadcba(13．4)而且))(),(),(()(tztytxtp，则三次多项式曲线可以重写为如下形式：2dcbaptttt23)((13．5)更复杂的曲线可以表示为一系列首尾相连的三次多项式：nnnnnttttttttttttdcbapdcbapdcbap2322223221121311)()()((13．6)其中10t．如果定义第i个三次多项式段在单位区间iti1上，那么整个区间则为0tn．可以认为，这个三次多项式序列是起点为00p，终点为npn的单一参数曲线．这个三次多项式序列叫做一个三次样条函数，它是机器视觉和计算机图形学中表示任意曲线的常用方式．13．1．2三维B样条曲线三维B样条曲线很适合表示由点序列构成的曲线，因此可以将二维B样条的定义扩展到控制点位于三维空间的三维B样条。例如对已知三维点序列nppp,,,10，由等式（7.28）给出第i阶三次多项式，而)(tBi由等式（7.31）给出．三维B样条曲线也不通过控制点．13．2三维空间曲面的表示本节将讨论机器视觉中常用的几种曲面表示．13．2．1多边形网面平面多边形，也叫平面片(planarpatch)，可以组成复杂的网面（polygonmesh），以表示各种物体的形状．图13.1三角形网面和四边形网面示意图。本节将介绍如何用平面片进行物体多边形网面表示．图13.1物体表面的网面表示，(a)三角形网面表示，(b)四边形网面表示第七章讨论了如何用若干个直线段端点（顶点）坐标表来表示一个多直线段，这一方法也可推广到平面多边形，即平面多边形网面也可以用一系列平面多边形顶点坐标表来表示．一个顶点常常是三个或三个以上多边形的公共顶点，因此，一个顶点在表中重复出现多次．为了使多边形网面的每一个顶点在表中仅出现一次，可以使用一种间接的顶点坐标表示方法，即对这些顶点从1到n进行编号，并按这一顺序将每一个顶点的坐标存入表中．每一个多边形可用其顶点编号表表示．不过这种顶点表不能明显地表示相邻表面的边界，对于一3给定顶点，也不能有效地发现所有包含此顶点的表面．这些问题可以用翼边缘数据结构(WingedEdgeDataStructure)来解决．翼边缘数据结构是一种网络数据结构，它具有三种类型数据记录：顶点、边和面．沿着数据结构包含的数据指针可以找到所有元素的邻接关系，而无须搜索整个网面，也无须将每一元素的所有邻接元素都存储起来．在多边形网面中，每一个顶点对应数据结构中的一个顶点记录，每一个面对应一个面记录、每一条边对应一个边记录。这样，可以直接查询一条边对应的两个顶点和两个多边形面，也可以直接查询一个顶点对应的所有多边形面（或边），查询时间正比于该顶点对应的多边形面（或边）的数量．翼边缘数据结构可以有效地表示三角面网面及其它具有多条边的多边形网面，并且不要求各个多边形面的边数相等．由于各顶点坐标包含在顶点记录中，因此，多边形面（或边）的位置可以由顶点的坐标计算出来．每一个面记录指向该面的某一个边记录，每一个顶点记录指向该顶点对应的边记录。因此，边记录包含将多边形面及其顶点连结成多边形网面的指针，并且允许对多边形网面顶点进行快速的扫描．具体地说，每一个边记录包含有两个端点指针，其两侧的两个多边形面指针和4个邻接翼指针，如图13．2所示。其中的面、顶点和边是用指南针的方向表示的，这样做只是为了方便，实际上，多边形网面上的方向与地球方位没有任何关系．每一条翼边允许对其对应的多边形顶点进行扫描，例如，可沿着东北翼边按顺时针方向扫描东多边形面各顶点．图13．2多边形网面翼边示意图确定多边形面是在东面还是西面取决于进入翼边缘数据结构中多边形面的顺序．当扫描一个多边形面时，必须首先检查此面是在边缘的东面还是西面．如果此面在这条边的东面，则沿着东北翼顺时针扫描或沿着东南翼逆时针扫描；如果此面在此边的西面，则沿着西南翼顺时针扫描或沿着西北翼逆时针扫描．顺时针、逆时针方向是以观察者为中心的．顺时针方向是这样确定的：左手大拇指指向此平面的法线方向，左手的其它手指方向就是沿此面的顺时针方向；右手大拇指指向此面的法线方向，右手的其它手指方向就是沿此面的逆时针方向．如果多边形网面表示一个物体完整表面，则所有面的法线都向外．如果此多边形网面表示一个曲面，则所有法线都指向此曲面的同一边．如果此曲面是图形曲面，则法线指向图形空间坐标的正坐标轴方向，例如，如果多边形网面为图形表面),(yxfz，则此表面法线指向正z轴．在多边形网面上增加一个多边形面的方法见算法13．1，沿某一方向扫描多边形面各顶点（或边）的方法见算法13．2．在算法13．1中，假定顶点是沿着平面顺时针方向排列的．适当改进算法13．2，可用于搜索一个给定顶点对应的所有边(或面)．4算法13．1翼边缘数据结构上增加一个多边形面的算法输入是一个按顺时针方向排列的多边形面的顶点表，包括顶点个数和顶点坐标．1．对于顶点表中的每一个顶点，如果没有出现在数据结构中，则可增加该顶点记录．2．对于每一对相邻的顶点(包括起点和终点)，如果其对应的边没有出现在此数据结构中，则可增加该边记录．3．对于多边形的每一个边记录，增加翼边，以便顺时针或逆时针扫描该多边形面．4．产生一个多边形面记录，并增加指针指向其中一个边缘．算法13．2沿着多边形面顺时针跟踪边缘输入是一个指向面记录的指针和一个调用待访问边的进程．1．从面记录中取出第一条边，使之成为当前边．2．处理当前边，即对被访问的每一条边完成所有的操作，如，沿着多边形面顺时针方向编辑顶点表，沿扫描方向记录边缘端点（顶点）．3．如果正在扫描当前边的西侧面，则下一条边将是西南翼．4．如果正在扫描当前边的东侧面，则下一条边将是东南翼．5．如果当前边是第一条边，则扫描结束．6．否则，回到第2步．13．2．2曲面片曲面上的各部分可以用一个双多项式表示．例如，平面可以表示为：yaxaaz210(13．7)曲面片可以用更高阶的多项式来表示．双线性曲面片（线性是指任何平行于坐标轴的截面的截线是一直线）：xyayaxaaz3210(13．8)双二次曲面片：25243210yaxaxyayaxaaz(13．9)双三次曲面片：3928273625243210yaxyayxaxayaxaxyayaxaaz(13．10)双四次曲面片41431322123114103928273625243210yaxyayxayxaxayaxyayxaxayaxaxyayaxaaz(13．11)在机器视觉中，上述双多项式经常被用来表示曲面片．多项式曲面片非常适合于局部表面的表示，例如一个点的邻域，但整个表面的表示不是很方便，而且不能表示非图形曲面．更复杂的曲面可以用三次样条函数来表示，这将在下一节讨论．13．2．3张量积曲面13．1．1节介绍了如何用参数形式将一个复杂曲线表示成一个三次多项式，此方法可以推广到复杂曲面的参数表示．一个三次多项式参数方程的矩阵形式为：51)(233210uuuuaaaap(13．12)其中，每一个系数都是一个三元矢量．张量积曲面是由两条曲线合成的，其参数形式如下：11),(233210321023vvvuuuvubbbbaaaap(13．13)其中，ia是三元行矢量，jb是三元列矢量，ia，jb的积是每一个坐标系数的双积．此系数曲面可以写为：MVUvuT),(p(13．14)其中，123uuuU123vvvVM是44矩阵，其元素是参数曲面的每一个坐标系数的矢量．在这种表示中，我们可以看到张量积曲面确实是两曲线的积：一条曲线以u为坐标，另一条以v为坐标．任何平行于坐标轴的平面和张量积三次多项式曲面的交线都是三次多项式曲线．换句话说，如果其中一坐标是常数，那么结果就是一条以其它两个坐标为参数的三次多项式曲线．13．2．4超二次曲面超二次曲面（superquadrics）由二次方程添加参数生成，这样可以通过调整参数很方便地改变物体的形状。增加的参数数目等同于物体的维数，比如，曲线是一个参数，曲面是两个参数。（1）超椭圆在超椭圆相应的方程中，允许x和y项的指数是变量，这样可以得到椭圆的笛卡儿表示式。笛卡儿超椭圆方程的表示形式之一是：1)()(22sysxryrx(12.15)其中s参数是任何实数。当1s时，可以得到一般椭圆表示式。相对于方程(12.15)，超椭圆参数参数方程可以表示成：sysxryrxsincos(12.16)图13.3表示了运用不同的参数s值产生的超椭圆面形状。6图13.3不同参数值s对应的超椭圆图形)(yxrr（2）超椭圆球超椭圆球面的笛卡儿表达式是由椭圆球面方程增加二个指数参数而得：1)()()(11222222szsssysxrzryrx(12.17)当121ss时，得到一般的椭球面。对超椭球面的方程（12.17），我们可以得到相应的参数表示式：12121sinsincoscoscosszssyssxrzryrx2/2/（12.1