北理工贾云德《计算机视觉》第十三章-三维场景表示

第十三章第十三章三维场景表示三维场景表示北京理工大学计算机系为了理解场景并与场景中的物体交互作用，必须将场景的三维数据进行有效的表示．三维场景表示包含有两个基本问题：场景重建和场景分割北京理工大学计算机系场景重建场景重建(reconstruction)是指使用插值或拟合方法从采样点(稠密深度测量值或稀疏深度测量值)计算曲面的连续函数，实际中通常使用许多三角片或小平面片构成的网面来近似表示场景深度测量值；场景分割场景分割是将表示场景的网面分割成若干部分，每一部分表示一个物体或一个特定的区域，这样有利于物体识别、曲面精确估计等后处理算法的实现．北京理工大学计算机系将双目立体测距、主动三角测距、激光雷达测距等成像系统的输出值转换成简单的曲面表示．基本方法基本方法::把测量点转变成三角片网面把距离测量值分割成简单的曲面片把测量点拟合成一个光滑曲面用测量点匹配一个曲面模型...北京理工大学计算机系13.1三维空间曲线曲线表示有三种形式：隐式、显式和参数式在机器视觉领域中常用形式:曲线的参数表示北京理工大学计算机系三维曲线的参数形式为：P=(x,y,z)=(x(t),y(t),z(t))t0≤t≤t1上式说明曲线上的一点可由参数t表示的三个函数来定义，曲线的起点为(x(t0),y(t0),z(t0))终点为(x(t1),y(t1),z(t1))。比如，从p1=(x1,y1,z1)到p2=(x2,y2,z2)的直线段的参数方程为：北京理工大学计算机系13.1.113.1.1三次样条曲线三次样条曲线三维曲线都可以用样条函数来表示，这和前面讨论的平面曲线表示类似．三次样条函数是一系列首尾相连的三次多项式曲线，每一段三次样条函数的参数表示形式为：x(t)=axt3+bxt2+cxt+dxy(t)=ayt3+byt2+cyt+dyz(t)=azt3+bzt2+czt+dz其中0≤t≤1北京理工大学计算机系将上式的系数表示成如下系数矢量：a=(ax,ay,az)b=(bx,by,bz)c=(cx,cy,cz)d=(dx,dy,dz)且：p(t)=(x(t),y(t),z(t))则三次多项式曲线重写为：p(t)=at3+bt2+ct+d北京理工大学计算机系复杂曲线可表示为一系列首尾相连的三次多项式p1(t)=a1t3+b1t2+c1t+d1p2(t)=a2t3+b2t2+c2t+d2.Pn(t)=ant3+bnt2+cnt+dn其中其中00≤≤tt≤≤11．．如果定义第如果定义第ii个三次多项式段在单位区间个三次多项式段在单位区间ii--11≤≤tt≤≤ii上，那么整个序列就定义在区间为上，那么整个序列就定义在区间为00≤≤tt≤≤nn上上..这个三次多项式序列叫做一个三次样条函数这个三次多项式序列叫做一个三次样条函数···北京理工大学计算机系13.213.2三维空间曲面的表示三维空间曲面的表示平面多边形也叫平面片(planarpatch)，可组成复杂的网面（polygonmesh），以表示各种物体的形状．下图是三角形网面和四边形网面示意图北京理工大学计算机系•平面多边形网面表示：(1)一系列平面多边形的顶点坐标表．表示直观；问题：一个顶点在表中重复出现多次．(2)顶点从1到n进行编号表示，顶点在表中仅出现一次，问题：这种顶点表不能明显地表示相邻表面的边界，对于一给定顶点，也不能有效地发现所有包含此顶点的表面．•翼边缘数据结构(WingedEdgeDataStructure)．北京理工大学计算机系翼边缘数据结构是一种网络数据结构，它具有三种类型数据记录：顶点、边和面．沿着数据结构包含的数据指针可以找到所有元素的邻接关系，而无须搜索整个网面，也无须将每一元素的所有邻接元素都存储起来．在多边形网面中，每一个顶点对应数据结构中的一个顶点记录，每一个面对应一个面记录、每一条边对应一个边记录。这样，可以直接查询一条边对应的两个顶点和两个多边形面，也可以直接查询一个顶点对应的所有多边形面（或边），查询时间正比于该顶点对应的多边形面（或边）的数北京理工大学计算机系翼边缘数据结构表示多边形表面翼边缘数据结构表示多边形表面••多边形面（或边）的位置可以由顶点的坐标计算多边形面（或边）的位置可以由顶点的坐标计算出来．出来．••每一个面记录指向该面的某一个边记录，每一个每一个面记录指向该面的某一个边记录，每一个顶点记录指向该顶点对应的边记录。顶点记录指向该顶点对应的边记录。••边记录包含将多边形面及其顶点连结成多边形网边记录包含将多边形面及其顶点连结成多边形网面的指针，并且允许对多边形网面顶点进行快速面的指针，并且允许对多边形网面顶点进行快速的扫描．的扫描．••具体地说，每一个边记录包含有具体地说，每一个边记录包含有两个端点指针两个端点指针，，其两侧的其两侧的两个多边形面指针两个多边形面指针和和四个邻接翼指针四个邻接翼指针北京理工大学计算机系SNEW面、顶点和边是用面、顶点和边是用指南针的方向表示的指南针的方向表示的每一条翼边允许对每一条翼边允许对其对应的多边形顶点其对应的多边形顶点进行扫描进行扫描例如，可沿着东北例如，可沿着东北翼翼(NE)(NE)边按顺时针方边按顺时针方向扫描东向扫描东(E)(E)多边形面多边形面各顶点．各顶点．北京理工大学计算机系确定多边形面是在东面还是西面取决确定多边形面是在东面还是西面取决于进入翼边缘数据结构中多边形面的顺于进入翼边缘数据结构中多边形面的顺序．序．如果多边形网面表示一个物体完整表如果多边形网面表示一个物体完整表面，则所有面的法线都向外．面，则所有面的法线都向外．如果此多边形网面表示一个曲面，则如果此多边形网面表示一个曲面，则所有法线都指向此曲面的同一边．所有法线都指向此曲面的同一边．如果此曲面是图形曲面，则法线指向如果此曲面是图形曲面，则法线指向图形空间坐标的正坐标轴方向图形空间坐标的正坐标轴方向..北京理工大学计算机系算法算法13.113.1在多边形网面上增加一个多边形面假定顶点是沿平面顺时针方向排列。输入是一个按顺时针方向排列的多边形面的顶点表，包括顶点个数和顶点坐标1．对于顶点表中的每一个顶点，如果没有出现在数据结构中，则可增加该顶点记录．2．对于每一对相邻的顶点(包括起点和终点)，若其对应边没有出现在数据结构中，则增加该边记录．3．对于多边形的每一个边记录，增加翼边，以便顺时针或逆时针扫描该多边形面．4．产生一个多边形面记录，并增加指针指向其中一个边缘．算法13.2沿某一方向扫描多边形面各顶点沿某一方向扫描多边形面各顶点//边边1．从面记录中取出第一条边，使之成为当前边．2．处理当前边，即对被访问的每一条边完成所有的操作，如沿着多边形面顺时针方向编辑顶点表，沿扫描方向记录边缘端点（顶点）．3．如在扫描当前边的西侧面，则下一条边是西南翼．4．如在扫描当前边的东侧面，则下一条边是东南翼．5．如当前边是第一条边，则扫描结束．6．否则，回到第2步可用于搜索一个给定顶点对应的所有边(或面)．13.2.213.2.2曲面片曲面片二元多项式可表示曲面二元多项式可表示曲面如：z=a0+a1x+a2y用高阶多项式可表示各种曲面片用高阶多项式可表示各种曲面片双线性曲面片：z=a0+a1x+a2y+a3xy双二次曲面片：z=a0+a1x+a2y+a3xy+a4x2+a5y2双三次曲面片：z=a0+a1x+a2y+a3xy+a4x2+a5y2+a6x3+a7x2y+a8xy2+a9y3双四次曲面片：z=a0+a1x+a2y+a3xy+a4x2+a5y2+a6x3+a7x2y+a8xy2+a9y3+a10x4+a11x3y+a12x2y2+a13xy3+a14y4多项式曲面片非常适合于局部表面的表示，但不能表示非图形曲面．更复杂的曲面可以用三次样条函数来表示13.2.313.2.3张量积曲面张量积曲面一个三次多项式参数方程的矩阵形式为：张量积曲面由两条曲线合成，参数形式:[]⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=1)(233210uuuuaaaap[][]⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=11),(233210321023vvvuuuvubbbbaaaap其中，每一个系数都是一个三元矢量其中，ai是三元行矢量bj是三元列矢量Ai,bj的积是各坐标系数的双积该系数曲面为：P(u,v)=UTMV其中，M是4×4矩阵，其元素是参数曲面的每一个坐标系数的矢量．张量积曲面是两曲线的积：一条曲线以u为坐标，另一条以v为坐标．任何平行于坐标轴的平面和张量积三次多项式曲面的交线都是三次多项式曲线．13.2.413.2.4超二次曲面超二次曲面由二次方程添加参数可生成超二次曲面通过调整参数可以改变物体的形状。增加的参数数目等同于物体的维数（（11）超椭圆）超椭圆在超椭圆方程中，当x和y项的指数视为变量时，笛卡儿超椭圆方程表示：1)()(22=+sysxryrx超椭圆参数方程：θθsysxryrxsincos==πθπ≤≤−不同S值产生超椭圆面:（（22）超椭圆球）超椭圆球超椭圆球面的笛卡儿表达式是由椭圆球面方程增加二个指数参数而得：当s1=s2=1时得椭球一般式：由上式可得参数表示式：1)()()(11222222=+⎥⎥⎦⎤⎢⎢⎣⎡+szsssysxrzryrxϕθϕθϕ12121sinsincoscoscosszssyssxrzryrx===πθππϕπ≤≤−≤≤−2/2/渐变s1和s2值可生成形状渐变的超圆球这些及其它超二次曲面形状的可以生成很复杂的形状，如家具、闪电和其它金属构成。13.313.3曲面插值曲面插值深度图的表示（曲面插值计算）由于原始深度图分布不均匀无法用均匀分布的网面表示，此时就需要曲面插值．通常在对原始图像进行处理（如边界检测和分割）之前，先要对深度图插值运算将其表示成一个均匀变化的网面模式．13.3.113.3.1三角形面插值三角形面插值空间曲面z=f(x,y)深度值zk插值空间不共线的三点可构成一个平面其方程为：z=a0+a1x+a2y该方程的系数可通过已知非共线的空间三点求得。故可以通过已知平面方程对三角小面片进行插值13.3.113.3.1三角形面插值三角形面插值（续）（续）m×n图像各点的坐标(xj,yi)由下式计算：21−−=mjxj21−+−=niyi对于一点(xj,yi)，在深度图中找出在x-y平面上包含该点的三个非共线的点，根据上式求出三角面方程,该点的深度值：ijijyaxaaz210++=13.3.213.3.2二元线性插值二元线性插值二元线性函数可表示为：f(x,y)=a0+a1x+a2y+a3xy1.如果把上式的一个变量设定为常数，则函数对于另一个变量就是线性变化的．2.对于四条边皆平行于坐标轴的任何矩形平面，有唯一的用于矩形顶点插值的二元线性多项式13.3.213.3.2二元线性插值二元线性插值((续续))例如在一个矩形网格的四个顶点中间的一点(x,y)进行插值，并设点(x,y)由四条边都平行于坐标轴的矩形包围．此矩形的顶点坐标是(x0,y0)，(x0,y1),(x1,y0),(x1,y1)，其函数值为z00,z01,z10,z1113.3.213.3.2二元线性插值二元线性插值((续续))二元线性插值的系数是由矩形的4个顶点确定的，把每一个顶点的坐标代入方程，则系数满足如下方程：z00=a0+a1x0+a2y0+a3x0y0z01=a0+a1x0+a2y1+a3x0y1z10=a0+a1x1+a2y0+a3x1y0z11=a0+a1x1+a2y1+a3x1y1联立上述四个方程，得到系数解：13.3.213.3.2二元线性插值二元线性插值((续续))当矩形网格为单位格时，二元线性插值有简单的表示．设要插值的点(x,y)离方格的左上顶点的偏移量为(δx,δy)，则双线性插值公式为：此公式可用于像元之间的插值．13.3.313.3.3鲁棒插值鲁棒插值最小中值二乘法LMS可用于曲面片拟合具有局外点的深度测量值集合．LMS是一种鲁棒回归算法，其溃点值为50％，正好对应于待拟合点集的中值的地方．使