调研报告
题目基于二维图形的三维构造
学生姓名张鹏宇
指导教师张昊
学院信息科学与工程学院
专业班级电子信息工程
完成时间2016年1月
本科生院制
摘要：
由于计算机和数字化技术的快速发展，传统的二维图像已经无法满足人们的需求。

人们更希望计算机能表达更加真实的三维世界。

因此计算机视觉技术迈入高速发展的时期。

计算机视觉是指用计算机来实现人类的视觉功能，也就是用计算机对二维图像进行三维重构，流行一些的说法就是基于双眼视觉。

关键词：三维重建，算法，CT图像，立体建模，三维分布；
1.三维重建算法的主要分类:
(1)自顶向下法:
将形体分解为由若干个基本形体或体素(正多面体、圆柱、圆锥、球、环等)组合而成。

每种基本形体在三面视图上的投影具有固定的模式,例如圆柱的三视图是两个矩形与一个圆,而球则为三个圆。

找出每个视图中的圆、矩形等元素,再通过检查其坐标值将这些元素相互对应,根据基本形体的投影特性确定出每个部分的形状,最后将它们组装起来,就完成了三维重建。

(类似于映射的关系，word中的三维重建就是这个原理)
(2)自底向上法:
(1)二维点、线的对应与三维点、线的生成。

参与对应的二维点包括曲、直线段的端点与曲线的极值点。

最初的算法首先由二维点对应产生三维点,再由三维点得到三维线段;给出了基于边线分类,从而由视图一步获得三维线段的快速方法。

(2)平面与曲面的获得。

共面但不共线的两条或多条直线段与曲线段都能够唯一确定一个平面。

曲面一般只考虑圆柱面、圆锥面、球面等,其中的每一种都可以用特定的模式来产生。

例如一个球面可以由半径相同、相交但不共面的两个三维圆或圆弧唯一确定。

通常,产生的平面与曲面都被记录成方程的形式。

(3)面环“face一loop求取。

前面获得的平面与曲面需要加上边界条件才能作为形体的表面。

边界可以通过求取落在面上的闭合环,即面环来获得。

面
环分为内环与外环,内环产生于形体上的孔洞。

(4)基元形体的生成与组装。

前面步骤中获得的平面与曲面将空间分割成一些无公共内点的三维封闭子空间,称为基元形体或体环(bdoy一loop)。

基元形体的组合构成重建的候选解集,通过检验是否完全符合视图,判断出正确的重建结果。

2.部分三维重建算法：
（1）运动恢复结构算法（structure from motion，SFM）并不需要知道相机拍摄时的绝对位置，也不需要使用结构光进行标定，只需要所拍摄物体为静态三维物体，并且所拍摄图像基本覆盖了物体。

通过多视角的二维图像的几何关系，先进行运动估算，然后采用光束平差进行运动计算的优化和三维空间点的确定，最后进行点云扩展以获得稠密三维点云。

（2）1987年, Lorensen等提出了MC三维重建算法,这里称为传统MC算法,该算法是面绘制算法中的一种。

（3）FDK算法是Feldkamp等人在1984年提出的锥束CT三维图像重建算法,现已得到广泛的应用,该算法主要分为滤波和反投影两个步骤。

3.算法具体解析：
基于分割的等值面生成算法将分割结果作为MC的输入,利用分割结果构造等值面。

算法步骤如下图所示。

当立方体中的三角面片确定后,与它相临的立方体(前、后、上、下、左、右)中的面片会按照一定的顺序延伸,因此要建立两个查找表:立方体表和邻接立方体表。

立方体表包括立方体的256种构型索引及其所对应的三角剖分形式,邻接立方体表包括每种构型索引及其所对应的相邻立方体的情况。

算法维护一个队列,用来记录处理过的立方体,同时建立一个标志数组,用来记录该立方体是否被处理过(1代表已经处理过, 0代表没有处理过)。

开始时所有的标志数组都标记为0,用户在三维数据集上确定一个种子立方体,种子立方体含有所要抽取等值面的一部分。

先找出一个种子点,加到队列中,并将其标志设为1。

执行从队列中的第一个立方体开始。

从队列中取出一个立方体,每个立方体进行两次判断。

第一次判断是通过分割后的数据集来判断该立方体的构型(该构型在0到255之间),以此来
确定该立方体哪条边上有交点,并将交点及法向量计算出来加入三角片数组。

第二次判断通过邻接立方体表来确定哪个邻域将被继续访问,并将需要处
理的相邻立方体(如果没有被访问过)加到队列中。

执行过程中,该立方体被标记为访问过的。

该算法执行到队列为空为止,这时等值面已经抽取出来。

算法的伪代码如下:
1)输入:分割后的数据(用来进行表面跟踪),
原始三维数据(用来计算法向量)。

2)输出:三维模型,用三角面片表示。

3)辅助数据结构:三角面片结构为
Mesh=x1,y1,z1,x2,y2,z2,x3,y3,z3,
nx1,ny1,nz1,nx2,ny2,nz2,nx3,ny3,nz3.
其中:(xi,yi,zi)(i= 1,2,3)表示三角面片三顶点的坐标,(nxi,nyi,nzi)(i= 1,2,3)表示三角面片每个顶点的法向量。

对于法向量的计算,这里用中心差分法获得体素中心点的梯度值来代替体素的法向量,法向量的计算通过使用原始三维数据集进行:
Gx= g(i+ 1,j,k)- g(i- 1,j,k),
Gy= g(i,j+ 1,k)- g(i,j- 1,k),
Gz= g(i,j,k+ 1)- g(i,j,k- 1),
nu=Gu(Gx)2+(Gy)2+(Gz)2,u= x,y,z.
其中g(i,j,k)表示点(i,j,k)的灰度值。

图像分割是进行三维重建的基础,分割效果直接影响到三维重建的速度和重建后模型的视觉效果基于分割的等值面生成算法,将分割结果作为MC的输入,这样可以根据图像特征选择最恰当的分割方法,可以将各种分割算法集成到三维重构中,,使得分割更为准确,使三维显示效果也更好。

采用种子生长的方式进行立方体检测,减少了无用立方体的检测时间。

采用中点代替插值计算,用整数算法代替浮点运算,使重建速度大为提高。

[参考文献]
[1]朱仁芝,刘磊.关于由二维视图重建三维形体算法的若干问题[J].计算机科学,1998,25(3):95-97.
[2]张艳超,庄载椿,肖宇钊,何勇.基于运动恢复结构算法的油菜NDVI 三维分布,2015,09.
[3]刘少丽,杨向东,陈恳.基于分割MC算法的超声影像三维重建方法.2010.。