Chapter 11 3D Reconstruction 第十一章 三维重建 Chapter 11 3D Reconstruction

三维重建是人类视觉的主要目的，也是计算机视觉最主要的研究方向. (Marr 1982) 所谓三维重建就是指从单幅图像加景物约束、二幅、二幅以上图像恢复空间点三维坐标的过程。 成像平面 O CV:Reconstruction 2018/12/1

三维重建主要目的：从图像出发，求出所有的Mi 照相机的成像模型： 三维重建主要目的：从图像出发，求出所有的Mi 摄像机标定：从图像出发，求出内参数K 摄像机定位或运动参数求解：从图像出发，求出运动参数 CV:Reconstruction 2018/12/1

三维重建 摄像机标定 摄像机运动参数的确定 R,T x u y v O O’ m I’  o I m’ ' e l 空间物体 世界坐标系 摄像机坐标系 x y v 图像坐标系 O’ 摄像机 o  I’ I M m’ m ' e l w z x y R,T CV:Reconstruction 2018/12/1

三维重建 获取物体(object)或场景(scene)的深度信息 主动传感器(active sensor)->range data 深度测量(measurement) 获取物体(object)或场景(scene)的深度信息 主动传感器(active sensor)->range data 被动传感器(passive sensor)->image 三维建模(modeling) 形成物体(object)或场景(scene)的三维表示 三维场景 场景 点云 深度测量 三维建模 point cloud CV:Reconstruction 2018/12/1

三维场景重建 表面重建 通过几何单元拼接拟合物体表面来描述物体的三 维结构 体重建 直接将体像素以一定的颜色和透明度投影到显示 平面 基于深度图的表面重建 基于三维密度图的表面重建 体重建 直接将体像素以一定的颜色和透明度投影到显示 平面 CV:Reconstruction 2018/12/1

1.表面重建 多边形网面 曲面片 张量积曲面 超二次曲面 CV:Reconstruction 2018/12/1

1.1多边形网面 用平面多边形（也称平面片，planar patch)组成多边形网面模型（polygon mesh model），表示物体三维形状． CV:Reconstruction 2018/12/1

三角形网面和四边形网面示意图 CV:Reconstruction 2018/12/1

多边形网面数据结构 顶点坐标表示 各个平面表示为顶点三维坐标的集合 问题：顶点重复出现． 顶点序列表示 顶点按序编号，平面中顶点用编号表示 问题：边重复出现，且不能明显表示相邻平面 的边界． CV:Reconstruction 2018/12/1

多边形表表示 CV:Reconstruction 2018/12/1

多边形网面表例 CV:Reconstruction 2018/12/1

用双多项式表示曲面 平面：z=a0+a1x+a2y 1.2 曲面片 双线性曲面片：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 +a10x4+a11x3y+a12x2y2+a13xy3+a14y4 CV:Reconstruction 2018/12/1

1.3 张量积曲面 复杂曲面的参数多项式 张量积曲面由两条曲线合成，可以认为是两曲 线的积：一条曲线以u为坐标，另一条以v为坐 标．任何平行于坐标轴的平面和张量积三次多项式 曲面的交线都是三次多项式曲线． 2018/12/1 CV:Reconstruction

1.4 超二次曲面 具有参数的二次多项式，通过调整参数可以改变物 体的形状 例：超椭球 2018/12/1 CV:Reconstruction

2.基于深度图的表面拟合 根据深度测量值获得连续表面 1. 表面插值(interpolation) 通过所有测量点 2. 表面逼近(approximation) 不一定包含，但尽可能接近测量点 回归(regression) CV:Reconstruction 2018/12/1

2.1 三角形面插值 对于图像中一点（i,j），计算其图像平 面坐标： 2.获得深度图中包含该点的三个非共线的点 3.计算三点所对应的平面 2018/12/1 CV:Reconstruction

Delaunay triangulation 实数域上的三角剖分 定义1 ：假设V是二维实数域上的有限点集，边e是由点集中的点作为 端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分 T=(V,E)是一个平面图G，该平面图满足条件： 1.除了端点，平面图中的边不包含点集中的任何点。 2.没有相交边。 3.平面图中所有的面都是三角面，且所有三角面的合集就是点集V的 凸包 Delaunay边 定义2：假设E中的一条边e（两个端点为a,b），e若满足下列条件， 则称之为Delaunay边： 存在一个圆经过a,b两点，圆内不含点集V中任何的点，这一特性又称 空圆特性。 Delaunay三角剖分 定义3：如果点集V的一个三角剖分T只包含Delaunay边，那么该三 角剖分称为Delaunay三角剖分。 CV:Reconstruction 2018/12/1

Delaunay triangulation Delaunay三角剖分，由于其独 特性，关于点集的很多种几何 图都和Delaunay三角剖分相关， 如Voronoi图，EMST树， Gabriel图等. Delaunay三角剖分有几个很好 的特性： 1.最大化最小角，“最接近于 规则化的“的三角网. 2.唯一性（任意四点不能共 圆）. Delaunay三角剖分的不足: 在低纬空间下数据量较小时更 有效. 2018/12/1 CV:Reconstruction

2.2 线性插值 用二元线性函数对曲面片建模 f(x,y)=a0+a1x+a2y+a3xy 用矩形四个顶点计算系数，代入获得深度值 2018/12/1 CV:Reconstruction

把每一个顶点的坐标代入 联立上述四个方程，得到系数求解出： CV:Reconstruction 2018/12/1

2.3 鲁棒插值 用最小中值二乘准则和重采样策略实现 最小中值二乘回归 鲁棒回归 取距离当前点最近的n个点 在n个点中任取m个点，共 种组合 对每一个组合，作最小中值二乘回归 取各个组合中对应最小平方中值的解 2018/12/1 CV:Reconstruction

2.4 曲面逼近 由于深度测量值存在误差，因此找一个曲面来逼近 深度数据比曲面插值更重要． 设重建曲面的模型为： 该曲面重建问题实际上成为确定最适合数据的曲面 模型参数的回归问题，回归函数为： CV:Reconstruction 2018/12/1

2.4.1 正则化方法 不适定(ill-posed)问题，因为许多函数可以对该 数据集实现最佳拟合 可以增加一个逼近约束函数，使得所选择的曲面 拟合函数有唯一解． 上面方程的第一个项称为问题约束，第二项是加 权光滑约束项，叫做正则项或稳定函数。 在问题约束上通过增加稳定函数将不适定问题变 为适定问题的过程叫正则化 （regularization）． CV:Reconstruction 2018/12/1

2.4.2 回归样条 用张量积B样条对表面建模 用最小二乘法求解回归问题 CV:Reconstruction 2018/12/1

回归样条 计算方法 1.张量积基函数 每一个测量点对应一个包含16个系数（三次B样条）的方程 用最小二乘法解线性方程组得所有系数 CV:Reconstruction 2018/12/1

3. 基于三维体数据的表面重建 三维规则体数据封装 (1) 内存记录方式 (2) 体数据文件格式 体数据内存记录方式 (1) 内存记录方式 (2) 体数据文件格式 体数据内存记录方式 CV:Reconstruction 2018/12/1

体元模型 (a) 方向无关的三线性插值模型 (b) 方向有关的三线性插值模型 CV:Reconstruction 2018/12/1

等值面是三次曲面 等值面（IsoSurface）定义  1 三线性插值结果  2 等值面定义 CV:Reconstruction 2018/12/1

1） 如立方体顶点的数据值≥等值面的值， 则定义该顶点位于等值面之外，记为“0”； 3.1移动立方体（Marching Cubes）算法 1.MC算法的基本原理 （1）体素中等值面剖分方式的确定 1）  如立方体顶点的数据值≥等值面的值， 则定义该顶点位于等值面之外，记为“0”； 2） 如立方体顶点的数据值＜等值面的值， 则定义该顶点位于等值之内，记为“1”。 8个顶点，每个顶点共有2个状态，因此共256种 组合状态  根据互补对称性, 256变为128  根据旋转对称性， 256变为15 CV:Reconstruction 2018/12/1

CV:Reconstruction 2018/12/1

MC用一个字节的空间构造了一个体元状态表 该状态表的每一位可以表示该体元一个顶点的状态（0或1），也就可以知道当前元素对应属于上面哪一种图中情况，以及等值面与那一边相交。 CV:Reconstruction 2018/12/1

MC算法的基本原理 （2）求等值面与体元边界的交点 假定密度数据在体元边界成线性变化，因此 可以利用线性插值算法求解 （3）三角片各顶点法向量计算 先求出体元各顶点的梯度，然后通过体元边 界两端点处梯度的线性插值求出三角面片各顶点 的梯度，也就是法向量。 （4）将各三角面片顶点的坐标值和法向量送给三 维显示模块处理，绘制面片。 CV:Reconstruction 2018/12/1

MC算法的重建结果 256×256×109MRI表皮重建 （b）128×128×93CT颅骨重建 （c）128×128×93CT表皮重建 三角面片：187559 顶点：94015 三角面片：137799 顶点：69331 三角面片：696889 顶点：347322 MC算法重建的表面模型 CV:Reconstruction 2018/12/1

MC方法的局限性 (b) 连接方式二义性的三维表示 (a)连接方式二义性的二维表示 MC方法的二义性 拓扑不一致造成孔隙 CV:Reconstruction 2018/12/1

3.2 移动四面体（Marching Tetrahedra）算法 MT算法的基本原理 立方体的四面体剖分 四面体中的等值面 CV:Reconstruction 2018/12/1

MT算法的重建结果 (a) 128×128×113CT颅骨重建 (c) 128×128×113CT表皮重建 （b）104×185×220CT脚骨骼重建 三角面片：331290 顶点：165808 三角面片：423998 顶点：211905 三角面片：365858 顶点：183056 　MT算法重建的表面模型 CV:Reconstruction 2018/12/1

3.3 三维模型的网格简化与模型的剖切  （1）抽样（Sampling）  （2）自适应细分(Adaptive subdivision) 基于边收缩的网格简化算法  网格简化算法简述  （1）抽样（Sampling）  （2）自适应细分(Adaptive subdivision)  （3）删除 (Decimation)  （4）顶点合并 （Vertex merging） CV:Reconstruction 2018/12/1

Hoppe采用显式能量函数E（M）来度量简化网格 与原始网格的逼近度［Hoppe96］：  基于边收缩的网格简化算法 Hoppe采用显式能量函数E（M）来度量简化网格 与原始网格的逼近度［Hoppe96］： 其中Edist(M)为M的距离能量，它定义为点集到网格的距 离平方： Espring(M)为弹性能量，这相当于在的每条边上均放置一 条弹性系数为k的弹簧，即： Escalar(M)度量M的标量属性的精度，而Edisc(M)则度量了 M上视觉不连续的特征线（如边界线、侧影轮廓线等） 的几何精度。 CV:Reconstruction 2018/12/1

边收缩过程示意图 (a)收缩前 (b)收缩后 边收缩过程 CV:Reconstruction 2018/12/1

 网格简化结果 MT重建结果 简化50％　　　　 简化90％　　　　简化90％表面绘制 CV:Reconstruction 2018/12/1

MC重建结果　　　　　简化50％　　　　　简化85％　　　 简化85％表面绘制 CV:Reconstruction 2018/12/1

开窗操作一般是用立方体或棱柱对重建模型 进行切割，模型处于剖切体之内的部分被切割 掉，之外的部分被保留下来。 3.4 医学影像应用——手术开窗操作 开窗操作一般是用立方体或棱柱对重建模型 进行切割，模型处于剖切体之内的部分被切割 掉，之外的部分被保留下来。 CV:Reconstruction 2018/12/1

手术开窗操作实验结果 　　(a)剖切　　　　　　　　　　 (b)开窗　　　　　 (c)开窗 　模型的剖切与开窗 CV:Reconstruction 2018/12/1

4. 体重建 是直接将体像素以一定的颜色和透明度投影到显示 平面的方法，称为体重建。 体重建通过计算所有体素对光线的作用得到二维投 影图像，依赖于景物的复杂程度和物体形状的复杂 程度，也不需要对切片的边界轮廓进行提取，避免 了重建过程中所造成的伪像痕迹，其计算过程不依 赖于视点，处理三维采样信号方便，便于显示物体 的内部结构。 三维体重建所需数据量大，运算速度较慢。 CV:Reconstruction 2018/12/1

三维体重建 使用imread( )函数读入现有的 n 幅图像 使用cat( )函数创建三维矩阵D 使用reducevolume( )函数减少 数据量， 使用isosurface( )函数计算数 据集在显示平面累计投影 使用patch( )函数对碎片进行 构造，并对图像的颜色，光线 进行定义， 设置图像的颜色、阴影及显示 效果 2018/12/1 CV:Reconstruction