光学和算法是3D结构光的核心能力，性能优越的3D结构光摄像头必须是光学系统和深度算法的完美融合，两者高度耦合且技术上不可分割。
本篇文章分为两个章节：第一章前言回顾3D成像（双目、主动式双目、结构光）的发展历史与渊源；第二章重点介绍主动式双目系统与散斑结构光系统的算法细节与难点挑战。
第一章
前言
双目成像技术自诞生以来，经历了半个多世纪的发展。最初的双目成像系统源自于对人眼双目的仿生：
图1 双目成像系统示意图[11]
通过上图可以明显看出，物体的空间位置移动（尤其是光轴方向的前后移动）会带来左右视图上投影点的像素位移，按照上图中的三角原理，Z轴移动量的大小可以通过投影点的像素位移来衡量，顺着这个思路，行业内发展出了双目立体匹配技术，就是目前常说的双目系统。
但是双目系统有一个非常突出的缺点：即左右视图上同名点（对应物理空间位置同一点）的匹配问题，在物体表面纹理（或者周期性纹理）特征不明显的情况下，这种匹配将变得非常困难，典型的一个示例如下：
图2 低纹理表面双目成像匹配困难 [11]
主动式双目是对于双目系统的增强，本质上还是双目系统，其特点是在双目系统的基础上增加了一个主动式光源（或者类似的主动式增加纹理的装置）。为了继续简化系统，同时兼顾主动式双目系统能够解决低纹理表面匹配问题的特点，行业内发展出了结构光系统：将双目中一个相机换成一个投影仪，用于向物体表面投射特殊的纹理图案。
图3 结构光方案投射特殊纹理示意图 [11]
结构光方案集之前方案优点于一身，由于光路可逆性原理，使用投影仪代替相机不仅符合双目三角法基本物理原理，而且可以向物体表面投射特殊图案，避免了低纹理表面的匹配困难问题。目前来说，结构光系统技术方案一般可通过投射的图案来进行区分：
条纹结构光：早期的结构光技术，由于条纹的周期性，必须使用多组不同周期或者不同相位的条纹图案进行编码，否则会出现误匹配，但是使用多组条纹图案会造成实时性较差，动态场景受影响尤其明显，所以目前常见于静态模型扫描[1]；
散斑结构光：近期发展起来的一种结构光技术，早期也有人称之为“One snapshot”技术，通过单张图案即可完成深度恢复，要求图案必须局部随机，该技术在动态场景下识别较好，典型产品就是Prime Sense、Kinect-V1 [2]。
第二章
双目算法与结构光算法
不论是双目算法还是结构光算法，从上述历史发展来看，其基本物理原理都是双目三角法，所以算法核心在于图像匹配，通过图像匹配技术寻找像素视差，从而最终得到Z轴深度值。两种算法的不同之处在于：双目算法通过左右视图进行图像匹配得到视差，结构光算法通过单一视图和投影图案进行图像匹配（一般这张投影图案被称为参考图）。
以目前最常见的散斑结构光为例，结构光算法整体流程如下图所示：
图 4 单目结构光算法流程
在工程实现时，需要根据实现平台（CPU/FPGA/ASIC）的特点，对每个模块作出调整，平衡算力、存储、时延、分辨率、帧率和传输带宽等诸多因素，使整体性能达到最优的效果。接下来算法详述我们先从双目算法讲起，再扩展到结构光算法。
一、最简单的双目测距系统
首先从最简单的双目测距系统说起，如下图所示：
图5 正面平行双目系统
假定左右两个摄像头参数完全一致，基线（两个光心的连线）与两个成像面平行，且左右摄像头每个对应的像素行对齐（row-aligned），我们称这样的双目系统为正面平行系统（frontal parallel）。
根据相似三角形，可以得到：
这就是基本的双目三角法原理，从上面的公式可知，视差（disparity）与距离（distance）Z成反比，如下图所示：
图6 视差与距离之间的对应图[12]
从上面的公式可以看出，如果要计算空间点P的深度Z，必须要知道：
相机焦距f，左右相机基线b——这些参数可以通过相机标定得到；
视差d——即左相机成像面上的每个像素点和右相机成像面上的对应点的关系，这就是双目算法的核心：匹配
回顾以上，我们得到结论：理想的正面平行双目系统，需要通过相机标定得到相机内外参才能计算深度。但是现实世界中的双目摄像头无法达到理想环境，所以需要采用某种算法，对实际的双目成像系统进行补偿、矫正，譬如将采集到的左右图变形（warp），使之行对齐。为了实现这一点，需要引入极几何（epipolar geometry）的概念。
二、极线约束
图7 极平面和极线[12]
如上图所示，是两个相机的光心，P是三维空间中的任意一点，和两个相机的光心形成了三维空间中的一个平面，称为极平面（epipolar plane）。极平面和两个相机的像平面分别相交于两条直线，这两条直线称为极线(epipolar line)。与两个相机的像平面的交点，称为极点（epipole）。P在相机的像平面中的成像点是，在相机的像平面中的成像点是。
我们的目标是：对于左图的，寻找它在右图中的匹配点，然后利用三角测距原理确定P在三维空间中的位置。为了能够减小的搜索范围，我们引入极线约束（epipolar constraint）的概念——对于任意一个三维空间点P，已知它在左图的成像点，那么对应右图的匹配点一定位于相对于的极线上，这就将搜索范围从一个二维的区间压缩到了一个一维的线段，大大降低了计算量，如下图所示。显然，成像面上的所有极线都相交于极点，比如图7中右图上的所有极线都相交于。
图8 匹配点与极线约束[11]
在极线约束下虽然匹配范围缩小到了一个一维的线段，但是实际计算起来还是不方便。而且即使找到匹配点，将视差转化为深度也比较繁琐。这种情况下，双目系统的标定（calibration）就非常重要了，通过标定得到内外参矩阵，使用相机内外参对左右视图进行矫正（rectification），使得左右视图的极线重合，如下图所示，这样匹配搜索只需要在水平方向进行即可。需要注意的是，双目系统的内外参不仅仅会影响深度绝对精度，还会影响双目系统的极线矫正。
图9 双目系统的矫正[11]
什么是极线矫正呢？简单的讲，就是我们通过标定得到的内外参，计算出两个单应性矩阵（homography），分别对左右视图进行变形（warp），使得左右视图的极点都被挪到了无穷远处，并且极线行对齐（row-alignment），这样就可以直接使用理想正面平行双目系统计算深度信息。
三、匹配计算
如上述，双目算法的核心在于匹配，这点对于结构光算法也是一样。深度计算的过程是得出所拍摄到的范围内每一个点的深度值，对于双目系统而言，就是检测每一个点在左图相对于右图的同名点，寻找同名点的方法就是匹配：通过对左图当前点提取特征并与右图一定范围内的所有点进行匹配（matching），左右图上同名点的像素差异就是视差。
视差计算方法按照匹配算法大体可以分为三类：局部匹配算法（Block Matching）、全局匹配算法（Global Matching）、半全局匹配算法（Semi-Global Matching）[3][4][13]。
局部匹配算法：利用邻近局部区域的纹理约束信息（同名点的纹理信息一致），具有算法简单、运算速度快的优点。但是该方法通常只能获得在某个区域内的最优视差，无法在整个图像范围内进行视差的优化，对于遮挡和弱纹理等也比较敏感，容易造成误匹配。一般会增加后处理算法对原始视差图进行优化；
全局匹配算法：利用图像的全局约束信息，该算法首先要定义一个能量函数，该能量函数表征左图和变换后右图的相似性，然后使用有效的计算方法来寻找全局最小能量，相对应的变换函数就是全局视差，优点是对图像的模糊不敏感，能够给出两幅图像重叠区域中绝大部分像素的视差值，但计算代价很高，不适合在工程实践中应用；
半全局匹配算法：综合了局部匹配和全局匹配的优势，通过Block Matching的方法计算代价空间（Cost Volume），然后在每一行上寻找最佳视差路径，该视差路径可以使整行匹配代价最低（路径规划使用动态规划算法（Dynamic Programming）），这种算法的优势是匹配精度高，而且计算量远远小于全局匹配，可使用在GPU、高端FPGA平台上，一般的CPU平台仍不太适合部署。
在实际工程应用中，绝大多数的匹配计算可以概括为下面4个步骤：
图10 视差计算流程[13]
局部匹配算法会依次执行上面前3步，通常在第3步采用一个简单的赢者通吃（Winner Takes All，WTA）策略 [5]，获得视差值；全局算法往往会跳过“代价聚合”这一步，直接到第3步。
匹配代价（matching cost）计算是双目算法中最核心的模块，它的优劣直接关系到深度计算的精度和质量[6]。那么它如何计算呢？我们要引入一个名词——特征（feature），画面中不同像素点的特征不同，我们可以通过特征来寻找左右视图的同名点。
这里介绍一种在双目算法和散斑结构光算法中都非常常用的特征：像素的灰度值，对应的匹配代价就是SAD：待匹配像素邻域内所有像素的AD之和（灰度值差的绝对值 (Absolute Differences，AD)）。
图11 匹配代价计算[11]
如上图所示，我们会在搜索范围（水平极线）上计算像素的匹配代价（SAD）。
图12 WTA获得视差[11]
如图12所示，我们会在视差搜索范围内比较得到的每个代价值，然后选取最小的代价值对应的视差作为该像素的视差结果。
但是这种视差计算仅仅考虑了孤立的局部信息，没有充分考虑领域的视差信息，在正常的物理环境下，相邻点的视差是连续的，匹配代价也应该是连续的，顺着这个思路，就发展出了代价聚合（Cost Aggregation）[7]：
Cost Aggregation=Cost(data)+Cost(smooth)
Cost(smooth)来自于领域点的视差传递，通过这种方法，可以有效提升视差计算的准确度，下面是一张对比图：
图13 代价聚合前后对比[11]
最后再简单介绍一下视差细化。通常情况下，我们在经过上面介绍的3步（匹配代价计算代价聚合视差计算）后得到的视差是像素级的精度，但是有些应用我们希望能达到亚像素级精度 [8][9]，这样我们就需要对得到的视差做细化（refinement），最常见的细化操作就是二次插值。
图14 亚像素插值[11]
如图14所示，我们最初得到的最小代价对应的视差是13，利用相邻的3个点做二次曲线拟合，然后取二次曲线最小值对应的视差（12.8）作为最终的视差结果。通过视差细化我们可以得到亚像素精度的深度图，但是有一点需要注意的是：亚像素毕竟是一种插值方法，通过算法对亚像素视差位置进行预测，不同的场景适合的亚像素插值方法是不同的。举个例子，对于高纹理区域，二次曲线拟合比较适用，但是低纹理区域，二次曲线拟合的结果并不好。
四、散斑结构光算法
前面的章节我们介绍了双目立体匹配的算法框架，下面以散斑结构光[10]为例，分析结构光算法与双目算法的区别与联系。
仍以正面平行双目系统为例：假设其中左相机被替换为投影仪，该投影仪投射出一副图案，如果我们在距离D1和D2分别放一块幕布，右相机去拍摄幕布上的图案，由于上面所说的极线约束，右相机拍摄到的两幅图案只是在行方向上的偏移关系，图案本身结构不会发生任何变化。这就引出了散斑结构光的一条重要原理：对于理想散斑结构光系统而言，散斑图案在不同距离上是整体移动的，散斑大小和分布模式不会随距离变化而变化。
顺着这个原理，我们就可以非常容易设计出一套散斑结构光系统：使用幕布（或者白墙）在某个距离下获取一张参考图像，其他距离的图像和这张图像都是行方向的平移关系，散斑结构光算法计算的本质就是计算物体散斑图和参考散斑图的行方向平移关系，从而得到视差，最终计算出每个点的深度值。
为了详细解释这个平移不变性，图15是一个典型的散斑结构光成像系统的原理图，图中I是激光散斑发射器，假设它投影的两条射线IG 和IH 为投影散斑的两个斑点，它在反射面1 和反射面2 上的两个斑点之间的距离分别为EF 和GH，EF 在成像面上对应的斑点像的距离为AB，GH 在成像面上的对应的斑点像的距离为CD。假定反射面1和反射面2与相机的垂直距离分别为L1和L2，相机焦距为f，基线MI为b。
图15 散斑成像示意图
因为△ABM与△EFM相似，所以 ;因为△CDM与△GHM相似，所以; 因为△IEF与△IGH相似，所以 ；综上可得 AB=CD。
也就是说，虽然深度越大，散斑之间的距离越大，但是距离越大，成像透镜对其缩小的倍数也越大，相互抵消，从而导致散斑之间的距离在成像面上的成像与深度无关。同理，可以证明，散斑的大小也不会随着深度的变化而在成像面上发生变化。所以散斑间的距离，斑点大小以及散斑分布模式在不同深度的反射面上成像是基本相同的。散斑图中物体深度发生变化时，只有物体上的散斑图整体移动，所以我们可以使用匹配的方法将物体散斑图与参考散斑图进行匹配。
图16 散斑图
左右图分别是在不同距离下拍摄的平面散斑图
如图16所示，可以很容易看出，散斑整体发生了偏移，与上面的理论分析一致。
总体来看，散斑结构光算法与双目算法非常类似，其核心都在于匹配。
上述的所有推导，都是基于理想平行双目系统，实际环境中，不会存在这样的理想系统，那么我们如何仿照双目算法的处理方式，对散斑结构光系统进行矫正。
核心还是在于标定，我们需要对散斑发射装置（譬如投影仪）和相机进行位置关系标定，通过标定出来的系统参数，同样可以对散斑结构光系统做极线矫正，这点对于实际散斑结构光相机非常重要。
另外，散斑结构光系统对于散斑模式是有随机性要求的。随机性需求的核心是为了解决匹配过程中的误匹配问题，所以这种随机只要求在搜索范围内随机即可，3D结构光都是采用VCSEL随机点阵的散斑发射器+DOE复制的方案，来减少无匹配发生的概率。
滑动查看参考文献
苏显渝, 张启灿, & 陈文静. (2014). 结构光三维成像技术. 中国激光, 41(2), 0209001.
蔡赞赞. (2018). 结构光技术解析及应用. 中国新通信, (11), 87.
赵晨园, 李文新, & 张庆熙. (2020). 双目视觉的立体匹配算法研究进展. 计算机科学与探索, 1-13.
笪健, 屈惠明, 陶天阳, 陈钱, & 左超. (2016). 结合极线约束和散斑相关的实时三维测量方法. 光学学报, 36(10), 1012003.
赵亮亮. (2007). 双目立体视觉中的图像匹配技术研究 (Doctoral dissertation, 南京航空航天大学).
Lazzaro, J., Ryckebusch, S., Mahowald, M. A., & Mead, C. A. (1989). Winner-take-all networks of O (n) complexity. In Advances in neural information processing systems (pp. 703-711).
黄子月. (2018). 双目视觉局部代价聚合匹配算法研究 (Master's thesis, 燕山大学).
潘兵, 谢惠民, 续伯钦, & 戴福隆. (1900). 数字图像相关中的亚像素位移定位算法进展. 力学进展, 35(3), 345-352.
刘卫光, 崔江涛, & 周利华. (2005). 插值和相位相关的图像亚像素配准方法. 计算机辅助设计与图形学学报, 17(6), 1273-1277.
张绍阳, 侯旭阳, 崔华, & 高小梅. (2016). 利用激光散斑获取深度图. 中国光学, 9(6), 633-641.
Stefano Mattoccia. (January 12, 2013). Stereo Vision: Algorithms and Applications.
Adrian Kaehler & Gary Bradski.(2016.12.09). Learning OpenCV 3 Computer Vision in C++ with the OpenCV Library.
Daniel Scharstein & Richard Szeliski(2002). A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms.
