1、主主 讲讲 人:人:原原 飞飞机器视觉机器视觉/空间测量组空间测量组基于图像的三维重建基于图像的三维重建一、一、应用背景应用背景二、二、研究现状研究现状三、三、重建流程重建流程1-1 制造业与逆向工程制造业与逆向工程 1-2 影视与娱乐影视与娱乐数字化三维模型,能够给电影和视频游戏提供丰富素材。数字化三维模型,能够给电影和视频游戏提供丰富素材。22届国际体博会上,由届国际体博会上,由深圳泰山在线科技公司深圳泰山在线科技公司研发的首款三维体感互研发的首款三维体感互动游戏动游戏i-dong地鼠地鼠 1997年,年,Paul Debevec利用图像重建技术,成功利用图像重建技术,成功地出品了电影短片
2、地出品了电影短片the Campanile。1-3 文化遗产的保存文化遗产的保存对文物进行三维重建操作,以便获取文物精准的几何对文物进行三维重建操作,以便获取文物精准的几何和色彩信息。和色彩信息。河南省新乡河南省新乡市辉县村舍市辉县村舍重建图重建图龙形纹理门框的局部重建图龙形纹理门框的局部重建图新疆米兰古城三维重建图新疆米兰古城三维重建图2-1 国外研究现状国外研究现状 Paul E.Debevec参数几何体表示初始模型参数几何体表示初始模型 Steven M.Seitz颜色不变量、顺序可见性规颜色不变量、顺序可见性规 则重建场景模型则重建场景模型 Roberto cipolla三维重建系统三
3、维重建系统PhotoBuilder2-2 国内研究现状国内研究现状 北京交通大学北京交通大学 袁保宗袁保宗 提出了提出了,由真实世界到计算机,由真实世界到计算机虚拟世界的转换问题。虚拟世界的转换问题。浙江大学浙江大学 刘刚刘刚 设计了,一个能绘制出几何模型和表设计了,一个能绘制出几何模型和表面纹理的真实场景交互建模系统。面纹理的真实场景交互建模系统。中科院自动化研究所中科院自动化研究所,开发的,开发的CVSuite,能利用立能利用立体视觉进行三维重建。体视觉进行三维重建。上海交大上海交大 马利庄马利庄 提出了一种基于构建提出了一种基于构建Visual Hull,求,求取物体形状及表面反射属性的
4、方法。取物体形状及表面反射属性的方法。2-3 重建软件重建软件 3DmeNow Canoma PhotoModeler和和PhotoModeler Scanner ImageModeler三维重建的四种主要方式:三维重建的四种主要方式:1 基于图像基于图像 2 使用探针或激光读数器逐点获取数据使用探针或激光读数器逐点获取数据 3 三维物体的断层扫面三维物体的断层扫面 4 光学三维扫描仪光学三维扫描仪 基于图像的重建方式,应用范围广泛,精基于图像的重建方式,应用范围广泛,精度比较低。度比较低。使用探针或激光读数器逐点获取数据,进行整体使用探针或激光读数器逐点获取数据,进行整体三角化,此类方法测量
5、精确,但速度很慢,难以在三角化,此类方法测量精确,但速度很慢,难以在短时间内获得大量数据。短时间内获得大量数据。根据三维物体的断层扫面,得到二维图像轮根据三维物体的断层扫面,得到二维图像轮廓,进行相邻轮廓的连接和三角化,得到物廓,进行相邻轮廓的连接和三角化,得到物体表面形状。体表面形状。应用硬件光学三维扫描仪获得物体的点云数据,应用硬件光学三维扫描仪获得物体的点云数据,进行重建获得物体的整体表面信息。进行重建获得物体的整体表面信息。基于图像重建流程基于图像重建流程纹理贴图纹理贴图图像匹配图像匹配1摄像机标定摄像机标定图像校正图像校正匹配匹配2,计算视差计算视差点云对齐,点云对齐,拼接拼接曲面重
6、构曲面重构空间点的获取空间点的获取黄色:任意位置黄色:任意位置绿色:平行位置绿色:平行位置图像校正图像校正 图像校正的目的图像校正的目的图像校正图像校正极线不平行极线不平行极线交于极点极线交于极点极线平行极线平行极点无穷远极点无穷远相机任意位置相机任意位置图像未校正图像未校正相机平行相机平行校正图像校正图像需计算极线方程需计算极线方程影响运行效率影响运行效率不需进行极线不需进行极线提高效率提高效率111pU p222pU p1p 图像校正的原理图像校正的原理 图像校正的过程,就是对里两幅图像分别进行二维的变换。将这种变换记为U1和U2,则图像点的变换可以看成其中,为p1变换后的坐标,为p2变换
7、后的坐标。2p(1a)(1b)图像校正图像校正 为了使极线变成一组平行直线,需要将极点放为了使极线变成一组平行直线,需要将极点放到无穷远处。设该无穷远极点为到无穷远处。设该无穷远极点为 则经过校正后的图像对的基础矩阵则经过校正后的图像对的基础矩阵 可以表示可以表示为为(000)Te F000 001010XFe(2)图像校正图像校正210TpF p 22110TTp UFU p 2121 TTXFUFUUeU则由式(1a)可以得到如下等式将式(1a)和式(1b)代入得由式(2)可得图像校正图像校正只要知道了基础矩阵F,就可以从上式中分解出变换矩阵 和 ,从而实现图像的校正。1U2U图像校正图像
8、校正2121 TTXFUFUUeU 设设 为为1123121233121TTTuaaaUUubbbucc1U将将U分解为如下形式:分解为如下形式:1000101pabUcc透视变换透视变换图像校正图像校正srpUU U U23 23 1113 123 230001rb bcbc bUb bcb bcb123010001ssssU相似变换相似变换错切变换错切变换 图像校正过程图像校正过程图像校正图像校正透视变换透视变换错切变换错切变换相似变换相似变换极线和图像坐极线和图像坐标系的横轴平标系的横轴平行行极点被移到了极点被移到了无穷远点无穷远点极线束变成了极线束变成了一组平行直线一组平行直线使得水平
9、方向使得水平方向的图像畸变最的图像畸变最小化小化 基于窗口的灰度匹配基于窗口的灰度匹配 基于窗口的稀疏点匹配基于窗口的稀疏点匹配 基于窗口的稠密点匹配基于窗口的稠密点匹配 匹配匹配 计算视差计算视差cos21dxx12345678 1 2 3 4 p 5 6 7 8基于窗口的灰度匹配原基于窗口的灰度匹配原则则1212|Tv vvv=匹配匹配 计算视差计算视差左图中所有匹配点左图中所有匹配点最大视差为最大视差为a最小视差为最小视差为b匹配点匹配点p的视差为的视差为d视差图中视差图中p点的灰度值为点的灰度值为 255*|d-b|/|a-b|匹配匹配 计算视差计算视差匹配匹配 计算视差计算视差3-4
10、 空间点的获取空间点的获取图像经过校正后可以看成是两台光轴互相平行的摄像图像经过校正后可以看成是两台光轴互相平行的摄像机的成像机的成像(1)TPXYZ(1)TPX b YZ212(1)Tpuv111(1)Tpuv经过校正后图像上的俩个对应点经过校正后图像上的俩个对应点空间点空间点P在摄像机在摄像机C1和和C2坐坐标系下的坐标,标系下的坐标,b为基线为基线图像点和三维空间点的映射关系可以得到:图像点和三维空间点的映射关系可以得到:1u bxd1vbydbfzd 3-5 点云拼接点云拼接 三维坐标变换三维坐标变换 拼接原理拼接原理 拼接步骤拼接步骤 拼接实例拼接实例点云拼接点云拼接点云拼接点云拼接
11、 三维坐标变换三维坐标变换 11121314212223243132333441424344aaaaaaaaAaaaaaaaa111213212223313233aaaRaaaaaa414243Taaa点云拼接点云拼接表示三维图像的坐标变换产生比例、旋转、错切等几何变换产生平移变换 拼接原理点云拼接点云拼接点云拼接点云拼接 P1中提取一个子中提取一个子集集|,1,2,.,iiim mP iN在数据点集在数据点集P2 中有一子集中有一子集与与P1中点一一对应中点一一对应|,1,2,.,iiimmP iN通过这俩个子集求解通过这俩个子集求解R和和T222 2o x y z1 11 1o x y z
12、实现P1与与 P2的拼接的拼接2222o x y z121112132412221222324232313233243TTTxxaaaxayR yTaaayazzaaaza1 11 1o x y z三维坐标系 和 之间的位置对应关系可以用下式表示,即:如果知道了R和T 的值,就可以将坐标系进行旋转和平移,转化为 坐标系。这样就能将各块测量的数据转换到同一个坐标系,实现拼接任务了。1 11 1o x y z2222o x y z点云拼接点云拼接 拼接步骤:拼接步骤:多视角点云数据的拼接方法可以分为两多视角点云数据的拼接方法可以分为两步。步。1 首先利用离散的特征进行匹配的方法实现首先利用离散的特
13、征进行匹配的方法实现粗配准粗配准 2 再使用迭代最近点算法再使用迭代最近点算法(ICP)算法进行精算法进行精确配准确配准点云拼接点云拼接 注意:注意:当零件的表面没有明显的特征的时候,当零件的表面没有明显的特征的时候,可以通过人为的方式在物体的表面附加特可以通过人为的方式在物体的表面附加特征来处理,常用的是粘贴标记点或者辅助征来处理,常用的是粘贴标记点或者辅助圆球的做法。圆球的做法。点云拼接点云拼接 拼接实例拼接实例 对同一个待测物体从不同的两个方位进行拍对同一个待测物体从不同的两个方位进行拍摄,其中图摄,其中图(a)的右半部分和图的右半部分和图(b)的左半部分事实的左半部分事实上是待测物体上
14、的同一个部分。上是待测物体上的同一个部分。图图(a)中的参考点中的参考点 4、5、6、7 分别对应图分别对应图(b)中中的的 2、1、4、3 点点将这些相同点一一对应起来将这些相同点一一对应起来根据它们的坐标解出根据它们的坐标解出R和和T拼接两部分得到的数据点云,形成一段完拼接两部分得到的数据点云,形成一段完整的物体表面轮廓。整的物体表面轮廓。点云拼接点云拼接点云拼接点云拼接散乱点集的曲面三角剖分散乱点集的曲面三角剖分空间直接剖分逐点插入法分治算法三角网格生长法约束delaunay三角剖分Delaunay三角剖分最小权三角剖分Hoppe算法Choi算法Voronoi图算法-shape算法 平面
15、投影法三角剖分曲面重构曲面重构Delaunay三角剖分三角剖分一、定义一、定义二、性质二、性质三、算法分类三、算法分类曲面重构曲面重构定义定义 三角剖分:假设三角剖分:假设V是二维实数域上的有限点集,是二维实数域上的有限点集,边边e是由点集中的点作为端点构成的封闭线段是由点集中的点作为端点构成的封闭线段,E为为e的集合。那么该点集的集合。那么该点集V的一个三角剖分的一个三角剖分T=(V,E)是一个平面图是一个平面图G,该平面图满足条件:,该平面图满足条件:1.除了端点,平面图中的边不包含点集中的任除了端点,平面图中的边不包含点集中的任何点。何点。2.没有相交边。没有相交边。3.平面图中所有的面
16、都是平面图中所有的面都是三角面,且所有三角面的合集是散点集三角面,且所有三角面的合集是散点集V的凸的凸包。包。曲面重构曲面重构Delaunay三角剖分三角剖分Delaunay边:假设边:假设E中的一条边中的一条边e(两个端点(两个端点为为a,b),),e若满足下列条件,则称之为若满足下列条件,则称之为Delaunay边:存在一个圆经过边:存在一个圆经过a,b两点,圆内两点,圆内(注意是圆内,注意是圆内,圆上最多三点共圆圆上最多三点共圆)不含点集不含点集V中任何其他的点,中任何其他的点,这一特性又称空圆特性。这一特性又称空圆特性。Delaunay三角剖分:如果点集三角剖分:如果点集V的一个三角剖
17、的一个三角剖分分T只包含只包含Delaunay边,那么该三角剖分称为边,那么该三角剖分称为Delaunay三角剖分。三角剖分。曲面重构曲面重构Delaunay三角剖分两个重三角剖分两个重要的性质要的性质:1、空圆特性:、空圆特性:Delaunay三角网三角网是唯一的(任意四点不能共圆),是唯一的(任意四点不能共圆),在在Delaunay三角形网中任一三角形三角形网中任一三角形的外接圆范围内不会有其它点存在。的外接圆范围内不会有其它点存在。2、最大化最小角特性:在散点集、最大化最小角特性:在散点集可能形成的三角剖分中,可能形成的三角剖分中,Delaunay三角剖分所形成的三角形的最小角三角剖分所
18、形成的三角形的最小角最大。最大。曲面重构曲面重构 算法分类:算法分类:分治算法分治算法逐点插入法逐点插入法三角网格生长法三角网格生长法曲面重构曲面重构 1 分治算法分治算法首先把点集分治算法分治算法首先把点集V以横坐标为主,纵以横坐标为主,纵坐标为辅按升序排序,然后递归地执行以下步骤:坐标为辅按升序排序,然后递归地执行以下步骤:(1)把点集)把点集V分为近似相等的两个子集分为近似相等的两个子集VL和和VR。(2)在)在VL和和VR中生成三角剖分;中生成三角剖分;(3)用局部优化算法优化所生成的三角剖分,使之)用局部优化算法优化所生成的三角剖分,使之成为成为Delaunay三角剖分;三角剖分;(
19、4)找出连接)找出连接VL和和VR中两个凸包的底线和顶线;中两个凸包的底线和顶线;(5)由底线至顶线合并)由底线至顶线合并VL和和VR中两个三角剖分。中两个三角剖分。不同的实现方法可有不同的点集划分法、子三角剖分不同的实现方法可有不同的点集划分法、子三角剖分生成法及合并法。代表算法有生成法及合并法。代表算法有Lewjo和和Robinson算法、算法、Lee和和Schachter算法、算法、Dwyer算法、算法、Dewall算法等算法。算法等算法。曲面重构曲面重构 2 逐点插入法逐点插入算法的基本步骤是:逐点插入法逐点插入算法的基本步骤是:(1)定义一个包含所有数据点的初始多边形;)定义一个包含
20、所有数据点的初始多边形;(2)在初始多边形中建立初始三角剖分,然后迭代以)在初始多边形中建立初始三角剖分,然后迭代以下步骤,直至所有数据点都被处理:下步骤,直至所有数据点都被处理:1)插入一个数据点)插入一个数据点P,在三角剖分中找出包含,在三角剖分中找出包含P的三的三角形角形t,把,把P与与t的三个顶点相连,生成三个新的三角形;的三个顶点相连,生成三个新的三角形;2)然后优化三角剖分。)然后优化三角剖分。各种实现方法的差别在于其初始多边形的不同以及建各种实现方法的差别在于其初始多边形的不同以及建立初始三角剖分的方法不同。代表算法有立初始三角剖分的方法不同。代表算法有Lawson算法、算法、L
21、ee和和Schachter算法、算法、MaCullagh和和Ross算法、算法、Bowyer算算法、法、Waston算法、算法、Sloan算法。算法。曲面重构曲面重构 3 三角网格生长法生长算法的基本步骤是:三角网格生长法生长算法的基本步骤是:(1)以一点为起始点;)以一点为起始点;(2)找出与起始点最近的数据点相互连接形成)找出与起始点最近的数据点相互连接形成Delaunay三角剖分的一条边作为基线,按三角剖分的一条边作为基线,按Delaunay三角剖三角剖分的判别法则(即最小内角最大准则和空外接圆准则),分的判别法则(即最小内角最大准则和空外接圆准则),找出与基线构成找出与基线构成Dela
22、unay三角形的第三点;三角形的第三点;(3)基线的两个端点与第三点相连,成为新的基线;)基线的两个端点与第三点相连,成为新的基线;(4)迭代以上两步直至所有基线都被处理。)迭代以上两步直至所有基线都被处理。各种不同的实现方法多在搜寻各种不同的实现方法多在搜寻“第三点第三点”上寻求突破。上寻求突破。代表算法有代表算法有Gree和和Sibson算法、算法、Brass和和Reif算法、算法、Mirante和和Weigarten算法。算法。曲面重构曲面重构曲面重构曲面重构6 曲面重构曲面重构曲面重构曲面重构 3-7 纹理映射纹理映射 主要的映射方法:主要的映射方法:纹理映射纹理映射 凹凸映射凹凸映射
23、 环境映射环境映射纹理映射纹理映射图10-16 纹理映射中纹理空间、物体空间和象素空间的变换纹理空间(s,t)数组坐标物体空间(u,v)表面参数象素空间(x,y)象素坐标纹理和表面变换观察和投影变换纹理映射纹理映射象素区物体表面纹理模式图10-17 由象素空间向纹理空间的映射观察投影变换的逆变换纹理映射变换的逆变换纹理映射纹理映射二维纹理映射二维纹理映射 在纹理映射中需要用到的坐标:在纹理映射中需要用到的坐标:屏幕坐标最终生成的图像显示在这个坐标中世界坐标需要把纹理映射到位于这个坐标中几何对象的表面上纹理坐标使用这个坐标表示纹理空间中的一个位置 参数坐标 使用这个坐标定义曲面纹理映射纹理映射
24、纹理映射的方法纹理映射的方法 方法一:把像素中心逆向投影到纹理坐标空间,方法一:把像素中心逆向投影到纹理坐标空间,从而得到某个纹理坐标对应的纹理值从而得到某个纹理坐标对应的纹理值 方法二:使用两步映射。方法二:使用两步映射。第一步映射是把纹理映射到一个简单的三维中第一步映射是把纹理映射到一个简单的三维中 间间 表面上,如球面、圆柱面或立方体表面。表面上,如球面、圆柱面或立方体表面。第二步映射再把带有纹理映射的中间表面映射第二步映射再把带有纹理映射的中间表面映射到需要绘制的对象表面上。到需要绘制的对象表面上。纹理映射纹理映射纹理映射纹理映射纹理映射纹理映射tts把纹理映射到圆柱面纹理映射纹理映射
25、 方法一方法一 1 取中间对象表面上某点的纹理值取中间对象表面上某点的纹理值 2 沿着该点的法向量方向画条直线直到沿着该点的法向量方向画条直线直到与绘制的对象相交。与绘制的对象相交。3 然后把中间对象表面上的纹理值作为然后把中间对象表面上的纹理值作为该交点的纹理值。该交点的纹理值。纹理映射纹理映射 方法二方法二 1 从要绘制的对象表面从要绘制的对象表面上的某点出发,并沿该上的某点出发,并沿该点的法向量方向画条直点的法向量方向画条直线。线。2 计算直线与中间对象计算直线与中间对象的交点。的交点。3 从这个交点可以得到从这个交点可以得到对象表面的纹理值。对象表面的纹理值。纹理映射纹理映射 方法三方法三 已知绘制对象的中心已知绘制对象的中心 1 从该中心位置到对象表从该中心位置到对象表面上某一点画一条直面上某一点画一条直 2 计算该直线与中间对象计算该直线与中间对象表面的交点。表面的交点。3 把直线与中间对象表面把直线与中间对象表面交点处的纹理值赋给绘制对交点处的纹理值赋给绘制对象表面相应的点。象表面相应的点。纹理映射纹理映射 谢谢!谢谢!