按：目前“大数据”、“3D数字化”、“人工智能AI”、“深度学习”、“AR/VR”是数字智能领域的热点研究方向 ，层出不穷的新概念让一般人看的眼花缭乱。

其实，“万变不离其宗”！本【3D智能十八篇】系列共分十八篇，作者吴怀宇（中科院博士、北大博士后）为中国3D科技产业联盟副理事长。每一篇都力求仅以一页纸的篇幅，来系统完整地介绍十八个主要方向 ，深入浅出。以下内容摘自吴怀宇博士2017年新出版的《3D打印：三维智能数字化创造》（第3版）一书，完整内容及详细目录详见链接：点击查看完整目录列表（含购书链接）

往期回看（点击查看）：

【3D智能十八篇之一】形状分析：优化3D打印形状的表现力

【3D智能十八篇之二】立体视觉重建：将照片转成3D数字模型

【3D智能十八篇之三】众里寻她千百度：海量3D模型的形状检索

【3D智能十八篇之四】3D降维攻击：上帝如何优雅地拍扁你！参数化

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

【立体视觉重建：将照片转成3D数字模型】

我们之前提到过，为了实现3D打印的定制化，很多情况下需要用到计算机视觉技术。比如要为自己量脚定制一双鞋，用户拿手机对着自己的脚拍下多个角度的照片，单击上传按钮，云端的智能计算服务就可以自动把3D脚型重建出来，然后设计出匹配的鞋子并将其3D打印出来。下面我们就以立体视觉重建为例，介绍一下计算机视觉技术。

摄像机定标

假设你现在已经拍摄了脚的多张各个角度的2D照片，那么如何将这些照片转化成一个3D数字化形状呢？首先第一步，你要对摄像机进行定标，比如确定摄像机的焦距、摆放位置和角度等。

我们先来看看摄像机的成像模型[1]。摄像机的成像模型一般采用针孔模型（Pin-Hole Model），与我们中学时学的小孔成像是一个原理，如图6-21所示。

图6-21  两千多年前，墨子和学生进行了世界上第一个小孔成像实验 （图片来源：大科技）

提示：
  其实两千多年前我国古代的大思想家墨子就和学生进行了世界上第一个小孔成像实验，并记录到“景到（即，倒），在午（即，交叉）有端（即，小孔），与景长，说在端”。因此墨子被西方称为“摄影光学理论和实践的开创者，探索光影成像的第一人”。

如图6-22左边所示，为了把成像模型解释清楚，我们来仔细看看摄像机的成像几何关系。同时我们把成像平面放到了小孔的前面，这样成像就是正立着的而不像上图那样倒立了。

图6-22  左：针孔成像模型；右：图像坐标系

◆ O点称为摄像机的光心，由点O与Xc、Yc、Zc轴组成的直角坐标系称为摄像机坐标系。

◆ I是成像平面（图像平面），我们把镜头对焦后，物体就成像在这个平面。图像平面构成了一个图像坐标系，横坐标为x，纵坐标为y。

◆ Xc轴和Yc轴与图像的x轴与y轴平行，Zc轴为摄像机的光轴，它与图像平面垂直。光轴与图像平面的交点，即为图像坐标系的原点Oxy。

◆ OOxy的长度为摄像机焦距f。

一下子冒出这么多术语，我们中场休息一下，给出本节的第1个公式来醒醒脑子。我们先仔细研究一下图像坐标系。如图6-22右边所示，图像坐标系以Oxy为原点，由x、y轴组成，单位是mm。然而，在实际的相机中，并不是以物理单位（如mm）来表示某个成像点的位置的，而是用像素的索引。比如一台相机的像素是1600×1200，说明图像传感器（也就是以前的胶片）横向有1600个捕捉点，纵向有1200个，合计192万个。对于某个成像点，实际上都是这样表示的：横坐标第u个点，纵坐标第v个点（而不是横坐标x mm，纵坐标y mm）。假设Oxy在u、v坐标系中的坐标为()，每一个像素在x轴与y轴方向上的物理尺寸为宽dx mm，高dy mm，则图像中任意一个像素的索引坐标与物理坐标满足下面的换算关系：

上面的这个方程组，分成了单独两个公式来写，让人感觉关联不够紧密（“本是一家人却说两家话”），因为实际上是要同时满足的，因此我们把两行合并成一个公式来写：

（3）

上面的形式被称作为矩阵形式。形象地说，矩阵（Matrix，没错，电影《黑客帝国》的英文片名就是这个单词）就是将多个有关联的元素用个大括号括在一起成为一个整体，以便直接对整体进行运算以分析出各个元素之间的内在关系。一个m×n的矩阵是一个由m行n列元素排列成的矩形阵列；当m=1或n=1时，则特称为向量。上式左边是个3×1的向量，右边表示了一个3×3矩阵和一个3×1向量之间的相乘。改成矩阵写法之后，将两个公式浓缩成了一个公式，整体感是不是提升了很多？从上面也可以看出，与普通代数（传统代数）不同，矩阵代数这种超凡代数描述的是多维而不仅是一维的代数；普通（一维）代数的乘法与乘子顺序无关，，而矩阵代数通常情况下，即一般不满足交换律；此外普通代数只有0没有逆（倒数），而矩阵代数中，很多矩阵都没有逆。

提示：
  有的读者可能会问，上面的矩阵为什么有3行呢？之前的公式不是只有2个吗？好问题！这是我偷偷塞了点料，把之前的坐标(u,v)和(x,y)都转成齐次坐标(u,v,1)和(x,y,1)了。齐次坐标（Homogeneous Coordinate）的好处是：即使乘个系数k()，仍对应于原来的同一个点，也即(u,v,1)与(k×u,k×v,k)对应于同一个点。同时，还便于几何变换（旋转、缩放、平移），只需用一个大一号的矩阵即可将变换矩阵的乘法（旋转、缩放）和加法（平移）合并到一块。此外，齐次坐标还可表示不同的无穷远点。

好，我们接着进行术语教学。之前我们定义了摄像机坐标系，但由于摄像机可安放在环境中的任何位置，所以我们还要定义一个世界坐标系来描述摄像机在环境中的位置，由Xw、Yw、Zw轴组成。摄像机坐标系与世界坐标系之间的关系可以用旋转矩阵R与平移向量t来描述，即：

（4）

矩阵和向量用黑斜体表示，其中R为3×3的矩阵； t为3×1的向量； Mb为4×4的矩阵，其也被称为摄像机外部参数矩阵。

提示：
  你在高中学习的初等数学是研究常量、研究静态的数学；而在大学里学的高等数学是研究变量、研究运动的数学。下面我们再解释一下空间、向量、矩阵[68] 、行列式的关系。

空间（Space）是高等数学的基础概念，是指某种元素（函数、图形、向量、状态等）的一个集合，在这个集合中建立了元素间的一种或几种数学结构（通俗来讲，“集合”中各个元素之间没什么联系，而“空间”则通过其中的数学结构建立了元素间的关系）。粗略地说，初级的空间可一步步可往上“升级”成结构更高级的空间。线性空间（又名向量空间，Vector Space）其实还是比较初级的，如果在里面定义了范数（“长度”），就成了赋范（Normed）线性空间。赋范线性空间满足完备性，就成了巴那赫（Banach）空间；若定义了角度，则为内积（Inner Product）空间。内积空间若同时满足完备性，就得到希尔伯特（Hilbert）空间（见下面的6.4.2节）。

在线性空间中选定基（坐标系）之后，向量刻画对象，矩阵刻画对象的运动，也即用矩阵与向量的乘法来施加运动。矩阵的本质是运动（变换）的描述，比如在一个线性空间中，只要我们选定一组基，那么对于任何一个线性变换，都能够用一个确定的矩阵来加以描述。此外，相似矩阵实际上描述的是同一个线性变换，因此相似矩阵的特征值（Eigenvalue）相同。

n阶矩阵的行列式也有着明确的几何意义：为n个组成向量按照平行四边形法则所张成的一个n维立方体的体积（如果是2维，则为面积）。向量的线性相关性实际上表示了这些向量所张成的广义平行四边形面积（体积）为0，例如此时的向量共线（n=2情况下）或共面（n=3情况下）。反之，若线性无关，则体积（行列式）不为0。此外，我们也不难看出，行列式不为0的矩阵，是可逆的（非奇异），即可将一组线性无关的向量变换成另一组也保持无关性的向量。

如果一个n阶矩阵虽不能保持n个向量的线性无关性，但它能保持r <n个向量的线性无关性，r就被称作矩阵的秩 （Rank），表示了能保持非0体积的几何体的最大维数。

外围的知识都介绍完了，好，我们现在正式开始介绍针孔模型。如图6-22左边所示，空间上任何一点P在图像上的投影位置p为光心O与P点的连线OP与图像平面的交点，这种关系也被称为中心射影或透视投影。由几何比例关系可轻易得出（先看下面公式的左边）：

（5）

其中(x,y)为p的图像坐标，(Xc,Yc,Zc)为空间点P在摄像机坐标系下的坐标。同样，上式的箭头右边为左边的矩阵形式，左右两边是等价的。

我们将公式（3）和公式（4）代入公式（5），就可以得到P点在世界坐标系下的坐标(Xw,Yw,Zw)与其在图像平面的投影点p的坐标(u,v)的关系：

其中，，；M=MaMb为3×4矩阵，称为投影矩阵；Ma完全由、、、决定的摄像机内部结构（如焦距、光心）有关，称为摄像机内部参数；Mb完全由摄像机相对于世界坐标系的方位（如摆放位置和拍摄角度）决定，称为摄像机外部参数。确定某一摄像机的内部和外部参数，就被称为摄像机定标/标定（Calibration）。注意，很多情况下的摄像机定标仅指确定摄像机的内部参数。

由上式可以看出，如果已知摄像机的内参数Ma和外参数Mb（即定标好了），两者直接一相乘就可得到投影矩阵M。投影矩阵M有什么作用呢？对任意空间点P，如果已知它的世界坐标系坐标，根据M，就可求出它的图像点p的位置(u,v)。

【单台摄像机的定标】

下面介绍一下摄像机定标的过程，如图6-23左边所示，我们在摄像机前放一个标定块。所谓标定块，就是每个特征点的空间位置都被事先测定的基准块，比如两个点的距离都被精确做成了1.0000 cm（精确到小数点后若干位）。用相机拍摄标定块的图像，就可以根据特征点的图像坐标(u,v)与真实三维空间坐标(Xw,Yw,Zw)之间的关系，来计算摄像机的内外参数了。我们需要6个或以上特征点，就可求解出投影矩阵M。但在实际应用中，我们通常使用了几十个特征点以减少可能的误差。此外，我们常用图6-23右边的平面标定块来进行标定[71]，标定时先平放着拍一张正面照片，然后再用个小物件轮流把每边往空间上翘起来一点（即改变标定板的空间位置姿态），依次拍摄3幅以上照片即可。（不要小看了小小的标定板，比如一块选材做工精良的大理石标定板定价需要几千元，以保证工业级高精度、完全平面、不变形。选购时，比如要实现±10 mm的3D重建精度，可选择1 mm精度的标定板。）

图6-23  上：三维标定块；下：二维标定板

提示：
  如果在定标时，环境不允许放置标定块或标定板，或者经常需要改变摄像机的内参数（如调焦），这时就只能通过自标定（Self-Calibration）技术来获取摄像机内参数，能利用到的信息只有图像的空间对应点，并用数学上的绝对二次曲线（AC，Absolute Conic）作为虚拟标定物。绝对二次曲线是在射影空间中无穷远平面上、全部由虚点构成的一条二次曲线，它的重要特性是它在图像平面的成像（IAC）不随摄像机的位置姿态变化，即投影成像只与摄像机的内参数有关。自标定至少需要拍摄3幅图像。另外对于平面场景的自标定，可通过提取平行线段进行求解。由于自标定求解的非线性，所以一般适用于精度要求不高的场合。

如果摄像机内参数Ma已知，仅需要确定外参数（R、t），即由N个3D空间点与图像点的对应关系来确定世界坐标系与摄像机坐标系之间的欧氏变换，这个问题被称为PNP问题（Perspective-N-Points）。当N≥6时，可线性唯一确定；但N=3,4,5时，一般情况下也可把解限定在有限的几个候选上。

以上我们假设的都是线性摄像机模型，但如果使用广角镜头（或全向摄像机），在远离图像中心处会有较大的畸变，因此可能还需要进行非线性修正或建模，如对径向畸变、离心修正、薄棱镜畸变等非线性畸变进行修正。

【两台摄像机的定标】

好了，我们刚才对一台摄像机的内外参数进行了标定。然而，对于从2D图像到3D形状的重建，一台摄像机（或仅拍一个角度的照片）是不够的。从图6-22中可以看出，已知图像点p的位置(u,v)，即使知道摄像机的内外参数，空间坐标(Xw,Yw,Zw)也不是能唯一确定的，实际上任何位于射线OP上的空间点的图像点都是p点。怎么办？再加一台摄像机（或者用同一台摄像机拍两次）！用左右两个摄像机进行立体视觉重建。

我们分别对左右两台摄像机单独进行了定标，就得到了它们的内参数。我们在6.3.2节可以知道，在一般的立体视觉方法中，只需知道摄像机的内参数，以及用极线（Epipolar Line）描述的双摄像机相对位置就足够了。

下面我们对极线进行介绍。如图6-24所示，用两个摄像机同时获得两张图像I1与I2。如果p1和p2是空间同一点P在两张图像上的投影点，我们称p2为p1的对应点，反之亦然。我们指出，p1点的对应点p2不需要在I2整幅图像中搜索，它必然只位于I2的某一条直线上，该直线（图中的l2）称为图像I2上对应于p1点的极线。

图6-24  用两台摄像机拍摄空间点

那么如何找到极线呢？其实很简单，它满足一个几何约束。如图6-24所示，O1为左摄像机的光心，O2为右摄像机的光心，两者的连线O1O2经过左右两个图像平面时相交于两个极点e1和e2。可以证明，I1（或I2）图像上的所有极线都相交于同一点e1（或e2），也即极线必然经过e1（或e2）。经推导可知，给定投影矩阵M1与M2，对于左摄影机的一个图像投影点坐标p1，则它的对应点坐标p2所在的极线是完全确定的，满足如下方程：

（6）

其中，；反对称矩阵，其秩为2。注意F是一个仅为3×3的矩阵，具有7个自由度，由投影矩阵M1与M2组合运算得到，这是立体视觉很重要的一个矩阵，称为基本矩阵（Fundamental Matrix）。

通过上式（6）还可以看出，无须费劲地求解出两个摄像机的所有内外参数（即M1和M2），很多应用场合下这是不必要的，因为只需一个基本矩阵F就可以得到立体视觉的极线几何约束关系。为了求解出基本矩阵F，我们至少需要两幅图像中的7或8个对应点。

更广义地，我们介绍图像平面间的单应矩阵（Homography Matrix）H的概念，具有8个自由度（实际上，前面提到的F由平面单应矩阵与极点唯一确定，即）。所谓单应可理解为：空间平面在两个摄像机各自的射影变换（Projective Transformation，也被称为直射变换Collineatory Transformation）下所生成的图像点具有一一对应的关系，即。单应矩阵H的一个典型应用就是对射影变换导致的图像变形进行矫正：我们只需先从变形图像中指定共面的4个点，对其手工矫正后得到4个新的点，于是就可求解出单应矩阵H了，最后对变形图像的所有点应用单应变换H进行自动矫正，整个过程无需求解摄像机的任何参数。

提示：
  空间点P不仅可以通过在左右两张图像上的投影点p1和p2来重建（这称之为双视图几何），类似地，还可通过同时拍3张图像来重建点P，这就被称为三视图几何。其中三焦张量（Trifocal Tensor）等同于双视图几何中基本矩阵的地位，类推还有四视图几何的四焦张量。3视图及以上的几何重建统称为多视图立体重建（MVS，Multi-View Stereo）。

6.3.2  基于立体视觉、SFM和Visual Hull的三维重建

我们先介绍一下3D重建的基本原理。如图6-24所示，如果我们知道了p1点以及它的对应点p2的位置，并对两个摄像机进行了定标（得到两个投影矩阵M1与M2，也即知道了焦距、光心距离等信息），那么很简单，可以用三角测距（见图6-24中灰色的大三角形O1O2P，其所在平面π因为经过了两个光心O1O2故也被称为极平面）的原理来计算空间点P的三维坐标。我们将这个过程称之为基于立体视觉的三维重建。两个摄像机光心的连线O1O2也被称为基线（Baseline），即两个摄像机的光心距离。基线越长，则重建误差越小，但基线长度不可太长，否则不仅会造成点的匹配困难，而且可能由于物体各个部分的相互遮挡，导致两个摄像机无法同时观察到空间点P。当两个摄像机仅存在水平方向上的纯平移运动时，p1与p2的纵坐标相同，p1与p2横坐标之差称为视差（Disparity），这也是我们看3D立体电影觉得真实的原因：左右两只眼睛看物体会有位置上的细微偏移。空间点P离摄像机越远，则视差越小，当无穷远时，O1P与O2P变得平行，视差变成0。

提示：
  让计算机自动建立多幅图像之间的匹配关系（如找到p1点的对应点p2）其实是三维重建最困难的一个问题。图像匹配最常见的做法是基于特征点（如Harris、DoG特征点）的匹配，此外还有基于直线的匹配，以及基于区域的匹配。

【基于立体视觉的直接三维重建】

经典的三维重建方法是根据拍摄的左右两张图片，基于立体视觉直接进行形状重建（Shape from Stereo），一般都利用标定块事先计算出了摄像机的内参数。然后，找出2D图像上的对应点，并通过对应点所求解得到的基本矩阵来计算摄像机的本质矩阵（Essential Matrix，对于摄像机的运动参数恢复起最本质的作用，其只与外参数有关），据此可进一步分解得到摄像机的外参数和投影矩阵。有了投影矩阵就万事大吉了，如图6-24所示，根据三角测距原理，再采用DLT（Direct Linear Transformation，直接线性变换）方法即可恢复空间点的3D高精度坐标。

【基于分层的SFM三维重建 】

然而，很多时候我们拍的多张照片中并没有事先准备标定块，而且我们也并不要求特别高精度的3D重建，这时该怎么办？仔细观察图6-22和图6-25可发现，针孔相机（中心射影）拍摄的2D图像向3D欧氏空间的重建过程，实际上依次经历了从射影、仿射到相似变换的提升过程。实际上，相似变换是仿射变换的特例（子群），而仿射变换又是射影变换的特例（子群）。于是，分层重建（Stratified Reconstruction）作为一种代表性的3D重建策略[17]，把原本多个变量的同时求解分摊到各个层中，这样减轻了非线性优化的难度，还可同时实现摄像机的自标定。针对连续拍摄的多张图像序列，分层重建首先利用图像对应完成射影重建（Projective Reconstruction），再通过确定无穷远平面来完成仿射重建（Affine Reconstruction），最后再通过摄像机定标实现相似重建（Similarity Reconstruction）也即度量重建（Metric Reconstruction）。步骤如下：

图6-25  相似变换是仿射变换的特例，而仿射变换又是射影变换的特例

◆ 首先，仅根据图像的特征对应点我们就可得到射影重建，方法很简单。比如在双视图中，利用对应点求解（见公式（6））出的基本矩阵就完全描述了射影结构关系。注意射影意义下重建的点并不是实际物理点的度量重建，而是相差一个射影变换。

◆ 仿射重建是分层重建算法中至关重要的环节。可通过模约束（其至少需要3个视图）确定无穷远平面（如求解出它的法向量），之后就可计算无穷远平面的平面单应（Homography，可理解为射影变换）矩阵，将重建结果从射影重建提升（Upgrade）到仿射重建。

◆ 通过求解IAC（参见6.3.1节的自标定）来计算出摄像机内参数，这样便可获得度量重建，其与真实大小物体的欧氏重建（Euclidean Reconstruction）只相差一个相似变换（均匀大小缩放）。

当然，分层重建并不意味着每层都必须经历，我们还可以选择跳层。比如利用（对偶）绝对二次曲面的成像（DIAC，是绝对二次曲线的像IAC的对偶），就可将三维重建直接从射影空间提升到度量空间。为了求解的稳定，可对摄像机内参数做一些合乎事实的约束限制，比如光心位于图像中心、畸变参数为零、纵横比dx/dy为1等。

我们往往拿着相机围绕固定物体转360°拍各个视角的多张照片，这时需要同时求解运动过程中的摄像机结构参数（包括不断变化的内外参数）以及固定物体的3D坐标，这被称为SFM（Structure from Motion，基于运动的重建）。由于双视图相机模型的参数求解存在一定的不确定性，所以SFM可采用更稳定可靠的多视图模型（比如用3张视图作为一组重建）。此外在求解时，为减少3D空间点重投影到图像平面的评估误差，需要把摄像机参数和3D空间点的位置都作为变量绑定在一起进行反复迭代优化，称之为捆绑调整（Bundle Adjustment），正所谓“东北乱炖一锅香”。

由于特征点匹配算法只能得到少数稀疏（Sparse）特征点的匹配对应，这样只能重建出物体的大致3D轮廓。所以还需要在此基础上对点（或面片）进行扩散，并根据极几何约束、视差梯度约束、颜色灰度一致性、错点剔除，以获得稠密（Dense）匹配重建或准稠密（Quasi-Dense）匹配重建。目前多视角立体重建的代表方法是先用Bundler软件包得到摄像机的内参数，然后再用PMVS（Patch based Multi-View Stereophesis）软件包获得稠密的3D点云。

当然，对于3D照相馆的室内影棚环境，我们完全可以事先对多个同步拍摄的摄像机用标定块进行标定，得到摄像机的参数，这样大大降低整个重建系统的难度。

【基于Visual Hull的三维重建】

上面介绍的基于立体视觉的三维重建方法，首先需要在多视图中找出特征点匹配，然后根据摄像机的参数来得到空间点的3D位置，最后才将3D点云拼接对齐并重建成3D网格面片。除此之外，还有一些方法直接采用多边形网格逼近物体表面，比如Visual Hull（可视外壳）方法。Visual Hull是一种基于侧影轮廓的重建技术（Structure from Silhouette），原理非常简单，类似于拿光刀把3D模型不断地逼近、切割出来。如图6-26所示，每个视点连接各自视图下的物体侧影轮廓，形成了一个视线锥体。然后，所有视点的轮廓锥体进行相交操作，所共同围成的空间包络就是可视外壳（图中的红色部分）。对于一个物体来说，其三维模型必定落在可视外壳中。注意，图中给出的只是一个2D示例，仅对3D物体的某个2D平面切层进行了重建，即假设图中的那条龙只是个平放着的2D图案。

图6-26  上：Visual Hull（可视外壳）的重建原理；下：两个重建实例（图片来源：UIUC）

Visual Hull简单快速，但也有明显的缺点，这就是精度不高。首先在原理上，有限个锥体相交得到的空间包络本身就不是原始形状的精确拟合，即会存在冗余体。当然，如果你拍摄更多视角的照片可明显改善。其次，对于那些非穿透的内凹部分也无法精确重建出来，比如深陷的眼窝就很难从轮廓中精细勾画出来。为了改进Visual Hull的重建效果，我们可以结合前面介绍的立体匹配重建方法，利用极几何约束、可见性分析、灰度梯度一致性、特征匹配等约束来获得一些精确的3D特征点，并以此驱动初始的Visual Hull不断收敛逼近到物体表面。