3D模型的可视化

Matlab的三维显示系统

在得到了三维重建的ply模型后，为了便于在PC端显示，我们在matlab下设计了一个显示GUI界面，该界面可以很好的显示ply模型的点云坐标点以及所带的颜色特征。同时为了便于观察设计了四个方向的旋转按钮可以更直观的观察3维信息，主界面如下：

在这里我们可以选择打开一个3维模型，同时为了使得在matlab下显示速度加快，我们设置一个采样步长可以稀疏显示模型的点集，并设置步长显示在界面上。然后开始显示。

以重建生成的狮子头模型，显示的完成结果如下：

为了在不同视角下观看，可以点击自动的动态观看模式，此时三维模型会自动旋转。同时也可以收手动选择观看角度，一个角度如下：

安卓端三维显示系统

Android 3D Rendering
本次实验要实现的功能是对某一物体多张图片进行3D重新建模。建模部分产生的结果是一个ply文件。安卓端需要在通过对这个ply文件进行解析，然后在手机端屏幕上进行展示。

Android系统使用 OpenGL 的标准接口来支持3D图形功能，android 3D 图形系统也分为 java 框架和本地代码两部分。本地代码主要实现的 OpenGL 接口的库，在 Java 框架层，javax.microedition.khronos.opengles 是 java 标准的 OpenGL 包，android.opengl包提供了 OpenGL 系统和 Android GUI 系统之间的联系。

因此，系统需要先对ply文件进行解析。解析过程分为两个部分。首先是对头部的解析，读取到该文件的中的空间属性个数，颜色属性个数以及面属性个数。然后根据各属性的个数开辟相应数量的空间。第二部分是读取ply文件的数值部分，把相应的数值读取到相应的数组中，这样就完成对ply文件的数据解析。

然后是数据展示部分。在 Android 中我们使用 GLSurfaceView 来显示 OpenGL 视图，该类位于 android.opengl 包里面。它提供了一个专门用于渲染3D 的接口 Renderer.主要需要要实现他的两个方法，onCreated，onDrawFrame。第一个方法是用来在图像初始化的时候使用的，第二个方法用来对图像进项旋转的。通过nio的buffer来保存第一个部分读取到的数据，然后调用GLES20里面的原生方法来使用这些数据对图像进行初始化。旋转的时候，通过记录下旋转矩阵通过旋转矩阵对图像进行重构，达到旋转展示的效果。

同时，为了方便操作，增加了一个reset按钮，当该按钮被点击的时候，重新调用图形的oncreated方法实现图像的重新展示。下面是一个正方体的效果展示。

很遗憾由于最终CMVS生成的.ply文件没有面信息，我们没有在安卓端成功显示自己重建的结果，只能在PC端显示。

基于Bundler、CMVS的3D重建

本周我们调研各种重建方法，尝试各种一直算法。尝试进行3D重建。最终我们选择用Bundler+CMVS的方法。这两个方法已经被实现为两个软件，我们主要仔细研究学习了两个算法的原理，并且调试炮筒代码，将两个软件封装在一起，组成一个可以通过一行运行的软件，方便地进行3D场景重建。

这里对整个过程做一个总结。

概览

从多幅图片进行场景重建（3D Scene Reconstruction and Rendering from Multiple Iamges），就是从一系列2D图片中，创建3D模型。它是从3D场景中获取2D图像的逆过程。深度信息的缺失构成此时面临的最大问题。也就是说对于一个2D图像上的点，你只能确定他是出现在一条空间上的一条直线（视线）上的，并不能确定它在这条直线的哪个位置。这个时候用到的技术称为三角测量法（Triangulation）.也就是说，当你有两张图片，那么一个点的空间位置可以由两张图片中该点所在的投影射线的交点确定。那么做Triangulation的关键确定两张图片或者说两个视图的相对位置以及它们之中相互对应的点。

流程

3D重建的大体过程为：特征提取与匹配、相机姿态和位置的估计、稀疏\稠密3D重建。大体过程如图１。

特征提取与匹配

图２显示的是特征匹配的过程。从各张图片中找出特征点（利用SIFT等算法），进行匹配，然后找到图片之间的集合约束关系，构建出一个几何图。

相机姿态和位置的估计

图３表示的是计算本质矩阵（Essential Matrix）的过程，具体过程是求解一个线性方程组。

图４表示的是根据由前量幅图像重建的三维点（x）和第三幅图像中的对应点利用校准法计算第三个相机矩阵（Pi）的过程。

稀疏重建

稀疏重建需要结合上述相机的姿态和位置估计。具体来讲，首先需要通过求解初始图片对儿的线性方程组来估计本质矩阵，对相机矩阵做一个不太精确的估计，然后每加入一张图片估计一个新的相机矩阵，然后通过光束平差法（Bundle Adjustment）进行三维点位置的精确计算。重复这一过程知道没有新的相机矩阵呗计算出来。流程图如图５所示
【光束平差法（Bundle Adjustment）：由于计算投影重建的时候有许多对应点可用，需要采用非线性最小二乘(Levenberg-Marquardt)求解，以最小化二次投影误差。针对这个问题的非线性最小二乘法来自于摄影测量中的光束平差法。】

我们采用的同样是这个流程。该流程建立在小孔成像模型的基础上，需要估计的具体参数有焦距（focal length）,径向畸变（k1, k2），旋转矩阵(R)和平移矩阵（T）。从三维空间点到相机点的映射可以表示为：

P = R * X + t       (conversion from world to camera coordinates)
p = -P / P.z        (perspective division)
p' = f * r(p) * p   (conversion to pixel coordinates)

其中P.z是P的第三个轴，r(p)为

r(p) = 1.0 + k1 * ||p||^2 + k2 * ||p||^4.

因此根据上式，得到相机的朝向为:

R' * [0 0 -1]'  (i.e., the third row of R or third column of R')

相机的位置为：

-R' * t .

上述整个流程通常叫做运动恢复结构（Structure from motion, SfM）。

到目前为止的具体实现

截至目前，我们具体实现了以下几个步骤。然后将这些步骤通通包装在一起，最终在Ubuntu Linux 14.04上运行的命令只有一行，无论是稀疏重建还是稠密重建。

预处理
SIFT特征提取
利用Bundler进行SfM稀疏重建
利用CMVS(Clustering Views for Multi-view Stereo)进行稠密重建

（下截图取自重建两个瓶子的场景的重建）

###预处理
由于后边我们使用了David Lowe的SIFT程序，而它要求输入图片的长宽都不能超过4000，所以我们需要对超出的图片进行缩放。缩放比例可以自己设置。　然后要提取图片的EXIF信息，信息中包含相机的生产商、相机型号和实际焦距(mm为单位)等。需要注意的是，如果使用自己的只能手机进行拍照，必须事先查询相机的型号并找到其ccd传感器的宽度。然后才能计算出以像素为单位的焦距值，这是必要的。具体如何将ccd宽度加入到程序中可以看之后我们写的readme.md。

###特征提取
我们的特征提取采用最初的SIFT算法，由David Lowe提出。直接调用其可执行二进制文件即可。当然也可以采用其他改进后的SIFT算法，但是注意的是如果后面要使用Bundler进行稀疏重建，sift提取的结果数据形式必须和David Lowe的形式完全相同。

###利用Bundler进行SfM稀疏重建
Bundler实现了一整套的SfM流程，包括相机的标定校准和点云的计算。具体原理已经在上边详细介绍过。（加building rome in a day中的描述）这样重建出的结果是稀疏的点云。
feature matching and bundle adjustment

###利用CMVS进行稠密重建
CMVS(Clustering Views for Multi-view Stereo)[http://www.di.ens.fr/cmvs/] 可以将大量的输入图片分解到不同的类，并在每一个类中并行地进行重建。这样得到的每一个类的重建结果是原图的一部分，最后整合在一起。这种分成局部并行重建的方法可以大大提高输入图片较多时的重建速度。

然后就可以利用Meshlab等软件进行显示。
这里边展示我们的几组结果，密码：123456
公开数据：
狮子头稀疏重建

狮子头稠密重建

自行拍摄的数据：
瓶子

大门

整合

Bundler和CMVS都是开源的软件，只需要一次编译过后，调用可执行文件即可。并且我们编写了各种脚本，对输入图片进行了预处理、特征提取等，将中间结果放置到合适的文件夹中供Bundler和CMVS调用，最终暴露给用户的只是两个shell脚本。用户可以通过调用这两个脚本并输入几个命令行参数完成，简单有效。
目录结构为，

运行方法为,

1
2
3
4

＃ sparse reconstruction
./sparse_reconstruction.sh [path to your images] [scaling factor, default value is 1] 
# dense reconstruction
./sparse_reconstruction.sh [path to your images] [scaling factor, default is 1]; ./dense_reconstruction.sh [path to sparse reconstruction folder] [number of photos in each CMVS clusters]

例子

1

./sparse_reconstruction.sh ../data/bottles 0.5; ./dense_reconstruction.sh ./reconstruction 20

需要安装的依赖一定要详细看我们写的readme.md

实验结果表明，采用David Lowe的SIFT提取的特征不够好，除了上述几个成功的数据集外，还有一些雕塑图片得不到良好的重建。说明特征提取的算法比较关键。

重建过程完整视频：

论文阅读：Multi-camera Scene Reconstruction via Graph Cuts

Vladimir Kolmogorov and Ramin Zabih

（１）介绍

文章用graph cut（图割）即能量最小化的方法，解决了多相机场景下的三维重建问题。

能量最小化方法有三个特性：

• 它把输入图像对称
• 它处理的能见度得当
• 它保持空间平滑，同时保持连续性

文章指出，传统的方法（voxel occupancy,体素占有）存在不能保证两幅图片之间的一致性的问题，并介绍了两种算法来保证图片一致性，voxel color和space carving。

（２）问题抽象

设多相机拍摄n幅图像， $ P = P_1\bigcup … \bigcup P_n $，体素$p\in P$；
令标签函数f将体素p映射到与深度相关的标签$l$;
这样3D空间中的一个点就可以用一个\对来表示。
这样的点只有当他们处于同一个label，即$l$相等时他们才有相互联系；

定义需要最小化的能量函数：
$E(f) = E{data}(f) + E{smoothness}(f) + E_{visibility}(f)$

其中$D(p, q)$是体素$p$和体素$q$之间不可见的地方。

$$$$

（３）图割

图割（Graph cuts）是一种十分有用和流行的能量优化算法。

此方法把图像分割问题与图额最小割（min cut）问题相关联。首先用一个无向图$G = $表示要分割的图像，$V$和$E$分别是顶点（vertex）和边（edge）的集合。此处的Graph和普通的Graph稍有不同。普通的图由顶点和边构成，如果边是有方向的则成为有向图，否则为无向图。而且边是有权值的，不同的边可以又不同的权值，分别代表不同的物理意义。而Graph Cuts涉及的图是在普通图的基础上多了２个顶点，这两个定点分别用符号”S“和”T“表示，统称为终端顶点。其它所有的顶点都必须和这２个顶点相连形成边集合中的一部分。所以Graph CUts中有两种顶点，也有两种边。

• 第一种普通顶点对应于图像中的每个像素。每两个邻域顶点（对应于图像中没两个邻域像素）的连接就是一条边。这种边也叫n-links。
• 除图像像素外，还有另外两个终端顶点，叫源点S(source)和汇点T(sink)。每个普通顶点和这两个终端顶点之间都有连接，组成第二种边，称为t-links。

图中每条边都有一个非负的权值we，也可以理解为cost（代价或者费用）。一个cut（割）就是图中边集合E的一个子集C，那这个割的cost（表示为|C|）就是边子集C的所有边的权值的总和。

Graph Cuts中的Cuts是指这样一个边的集合，很显然这些边集合包括了上面2种边，该集合中所有边的断开会导致残留”S”和”T”图的分开，所以就称为“割”。如果一个割，它的边的所有权值之和最小，那么这个就称为最小割，也就是图割的结果。

Graph cut的3x3图像分割示意图：我们取两个种子点（就是人为的指定分别属于目标和背景的两个像素点），然后我们建立一个图，图中边的粗细表示对应权值的大小，然后找到权值和最小的边的组合，也就是（c）中的cut，即完成了图像分割的功能。

本周完成的工作主要是：（１）详细阅读一篇论文，查资料并了解3D场景重建的基本流程；（２）搭建安卓开发环境

论文阅读

3D Reconstruction and Rendering from Image Sequences

R.Koch, J.-F. Evers-Senne, J.-M. Frahm, K.Koeser

(1) 介绍

    文章实现了一个3D场景的表面重建系统，可以合成未知静态场景的新视角视图。整个系统可以大体分为两部分：线下数据采集和线上交互渲染。
    在线下数据采集部分，大体进行两个步骤。第一步为通过SfM(structure from motion)方法估计相机的方位以及标定其内部参数。这样就会得到一个稀疏的3D特征点集。这些特征本身就已经组成了一个对于场景的稀疏3D描述。第二步是优化改善上一步的结果：从上一步中做过标定的图片中估计出稠密深度图（dense depth maps），进而进行3D场景几何物体的refine。总的来说，经过了线下数据采集部分以后，每张图片的标定参数(the associated calibration)、3D拍摄姿态(3D pose)和稠密深度图(dense depth map)会被计算并存储。
    在线上交互渲染部分，使用VDGT(view-dependent geometry and texture models)利用第一部分的结果渲染并呈现出场景在新视角的视图。

(2) 系统框图　

(3) 分块讲解

• 线下数据采集（offline data acquisition）
  大体进行两个步骤。第一步为通过SfM(structure from motion)方法估计相机的方位以及标定其内部参数。这样就会得到一个稀疏的3D特征点集。这些特征本身就已经组成了一个对于场景的稀疏3D描述。具体来讲，先用一个2d feature detector抽取出图像的特征，然后使用KLT-tracker等找到场景的不同视图之间相关的特征。匹配过程使用到RANSAC算法。由于所有2D视图都是一个3D场景在不同角度的投影，所以可以通过同时估计相机姿态和3D特征点来计算所有视线的交叉情况。于是bundle adjustment算法提炼出描述场景结构的3D点坐标、相对运动参数和相机的光学参数，这样就得到了我们想要的相机姿态和3D特征点。
  同一场景的不同角度视图如下图所示：
  
  场景原图和3D标定结果如下图所示：
  
  第二步是优化改善上一步的结果：从上一步中做过标定的图片中估计出稠密深度图（dense depth maps），进而进行3D场景几何物体的refine。具体来讲，需要对每个视图的每个像素点进行深度估计。论文使用到的方法是multi-view stereoscopic depth estimation.
• 线上交互渲染（interactive online rendering）
  在进行线上交互渲染时，用户可以控制一个虚拟的照相机，从新的角度查看场景。新角度的视图通过根据已有视图的标定图和深度图进行插值而得到。这个时候面临的问题有几个：哪些图片对于所求视角最为合适、怎样计算深度的变化以及如何将原图中的文理信息混合进新的视图。当然，如果想实现交互式的效果，处理的帧率要至少达到10fps。
  文章解决这些问题的策略为：
  – 选择最佳的相机视图
  – 融合不同视图的几何物体
  – viewpoint-adaptive mesh generation
  – viewpoint-adaptive texture blending
  具体来讲,是使用了VDGT(Rendering with View dependent Geometry and Texture)的方法。该方法选取与新视角的视点、方向、公共视图内容最相近的几个相机图片，并将他们经过图像扭曲（image warping）拼接到一个表面上。

安卓环境搭建

(1) 软件版本

采用0.86 beta 版本的Android Studio

(2) 安装过程

1) 缓存文件夹配置

Android Studio的缓存路径，这个缓存文件主要是存放一些Android Studio设置和插件和项目的缓存信息的，缓存文件夹如图：

缓存文件夹是默认在磁盘中，随着项目的增多，缓存会越来越大,甚至会达到几G的大小，所以移到非系统盘是必须的，也方便以后重装系统时，没必要的迁移。

找到Android Studio根目录，进入bin,再找到idea.properties,打开并修改它，找到要修改的选项，去掉注释符号。然后修复后面的配置路径，如图

然后就能在安装目录下运行了。

2) 构建工具 Gradle的配置

这个部分是整个配置过程的关键。项目无法编译或者报错的问题通常源于此部分没有执行好

Android Studio 中，有一些概念是和 eclipse 不同的. eclipse 迁移至 Android Studio 时，一些概念的对照情况如下，仅供参考和明确，方便以后的熟练使用.

简单的来说，android Stduio，把一个项目比喻成一个工程的一个个模块，外部的依赖也是一个个模块，这样一个项目的结构就很清晰明了。

• 新建项目

基本步骤省略至下图

离线配置gradle文件，先用系统自带进程管理器杀死android Studio,然后来到C盘，找到C:\Users\xxx.gradle\wrapper\dists ,xxx为当前系统的用户名，进到这个目录,在gradle官网下载，1.12版本的gradle,选择1.12的版本，选择gradle-1.12-all，下载，将下下来的压缩文件放在此目录即可。

Porject Introduction

topic

3D Scene Reconstruction and Rendering from Multiple Images

brief description

3D scene reconstruction is usually a task where multiple images of a scene is taken and a 3D surface of that scene is reconstructed. A system of 3D scene reconstruction should estimates camera pose and 3D scene geometry i.e. depth information. Building such a system mainly requires knowledge of computer graphics and image processing. We three are really looking forward to have a try on such a challenge. Over the next few weeks, we will update our progress in the project on this website.

course requirements

3D reconstruction from multiple images is the creation of three-dimensional models from a set of images. It is the reverse process of obtaining 2D images from 3D scenes.
The essence of an image is a projection from a 3D scene onto a 2D plane, during which process the depth is lost. The 3D point corresponding to a specific image point is constrained to be on the line of sight. From a single image, it is impossible to determine which point on this line corresponds to the image point. If two images are available, then the position of a 3D point can be found as the intersection of the two projection rays. This process is referred to as triangulation. The key for thsi process is the relations between multiple views which convey the information that corresponding sets of points must contain some structure and that this structure is related to the poses and the calibration of the camera.

BONUS (Reslizing each of the following tasks you can gain up to 10% mor scores of your project score, i.e. your final project score = basic project score * 110%)

1. Rendoring 3D scene on mobile devices(+10%)
2. Result evaluation on public datasets(+10%): Multi-View Stereo Dataset: http://vision.middlebury.edu/mview/

video demo (from the web):

Group Members

• 杨子枢：2463454532@qq.com
• 龚逸凌：476174713@qq.com
• 王敬靖：413226895@qq.com
• 陈俊：1924153192@qq.com

Current Plan for Next Week

1. Read papers and learn basics about 3D scene reconstruction; dicussions will be held.
2. Learn Android programming
3. Confirm duties and responsibilities, i.e. division of labor

References

[1] Multi-camera scene reconstruction via graph cuts, ECCV 2002
[2] 3D Reconstruction and Rendering from Image Sequences
[3] Scene Reconstruction and Visualization from Internet Photo Collections, 2008