🔥 三维视觉任务中常见的形状表示方法

和传统的二维计算机视觉任务不同，三维计算机视觉任务中的形状表示方法 (Shape Representation) 多种多样，难说孰优孰劣。但针对不同课题的场景，一些表示方法会显著比其它表示方法更加合适。了解这些几何形状的表示方法是从事相关研究的基础。

以下的分类方法只是我在 GAP Lab@CUHK-Shenzhen 从事相关研究时的理解，受限于自己所接触课题的广度与深度，如有理解不足之处还望大家不吝赐教。

我个人倾向以计算机推断形状的方式将三维形状的表示方法分为「显式表示 (Explicit Representation)」和「隐式表示 (Implicit Representation)」两种。当然也会有人从用途的角度出发^[1]分为「光栅形式 (Rasterized Forms)」和「几何形式 (Geometric Forms)」，我个人认为一些用于光栅化的形状表示方法也常用于几何领域的研究（如体素适用于碰撞检测），因此觉得这种分类方法不够严谨。

显式表示这一说法更多是相对于 2018 年前后不断涌现的隐式表示而产生的（也可能是只存在于我们实验室的分类思路）。显式表示法往往直接记录了形状的几何信息，而隐式表示往往需要计算机进一步的推断才能获得形状的几何信息。对于这两种表示法的特点，一言蔽之，显式表示法一般是离散/粗糙的，而隐式表示法一般是连续/精细的。

⚠️ 注：「粗糙」和「精细」是从分辨率的角度提出的概念，请区分「精细」和「精确」——比方说，一个 32×32×32 分辨率光栅化的圆柱体^[2] 会比一个 64×64×64 分辨率光栅化的三棱锥更「精确」地描述车轮的形状，但后者更加「精细」一些。

TODO: 这里补个图说明「精细」和「精确」的区别。

显式表示 (Explicit Representation)

基于点的表示法 (Point-based)

点云 (Point Cloud)

点云是欧氏空间里一组点的集合。用数学语言，记一个点云 $V$ ^[3] 为：
$$
V={(x_{i}, y_{i}, z_{i})}_{i=1}^{N}
$$
其中，$N$ 是点的个数，目前在单视角三维重建任务中一般取值 1,024 或 2,048，在其它任务（如场景重建）可能会有更大的取值。其中 $V$ 的一个元素 $(x_i, y_i, z_i)$ 对应了一个点 $v_i$ 在欧氏空间的坐标 (Coordinate)，$x_i$、$y_i$、$z_i$ 的可行域是连续的。

点云之所以被广泛使用，是因为它是 Kinect、激光雷达 等设备直接采集到的原始数据形式 (Raw Data)。正因如此，这一方法在大多数场景中只存储了被扫描物体表面的点，并没有关于物体内部的信息。

TODO: 这里补一个图解释什么叫 “只存储了被扫描物体表面的点”。

要注意的是，点云中的点是「无序 (Unordered)」的。这一特点也是因其获取方式造成的：针对同一个物体，你用同一台 Kinect 沿不同方向扫描所得到的的数据是不一样的^[4]，但它们都反映了相同的物体。

TODO: 这里补一个图解释说明这段内容。

如何判断两个点云是否代表同一个物体，或者更广泛的，如何衡量两个点云的相似性也是 三维视觉/三维几何 中的一个课题。有时同一物体扫描出的两个点云可能连点的个数都不同，有时两个形状相似的点云只是朝向 (Orientation) 或大小 (Scale) 不一致。在进行基于点云形式的深度学习任务前，比如在训练模型前，需要先对数据进行对齐处理 (Alignment)。

幸运的是，针对上述问题，学术界都已经提出了一些相对简单有效^[5] 的解决方法：针对对齐问题，传统方法有 迭代最近点算法 (Iterative Closest Point Algorithm, ICP Algorithm) 等，机器学习领域也有估算相机参数的网络；针对衡量点云相似性的问题，目前常用的方法有 倒角距离(Chamfer Distance, CD)、推土机距离 (Earth Mover’s Distance, EMD) 和 F-Score。

由于点云是大量传感器、深度设备在真实应用场景里采集到的直接数据形式，再加上点云比较轻量^[6]，点云被广泛应用于诸如 物体分类、场景分割、动作捕捉 等对时效要求比较高的任务中。

然而点云有一个与生俱来的不足：它不包含面的信息。哪怕我们知道点云中的点都在形状的表面上，我们却无法判断哪两个点是处于原物体同一平面上的。由于扫描时不可避免的误差，点云中还可能包含一部分噪声点。

TODO: 这里补个图说明没有面的信息会带来哪些直观的影响。

网格 (Mesh)

为了弥补点云表示法缺失面信息的不足，我们将形状表面的点用线连接起来，标记其中存在面 (Face) 的部分，便得到了网格。用数学语言，一个网格 $M$ ^[7] 可以表示为：

$$
M=(V, F)
$$

其中 $V$ 的定义与前面点云中 $V$ 的定义相同，$F$ 是一个记录了点云中面的集合：

$$
F={(v_{p}^i, v_{q}^i, …, v_{k}^i)}_{i=1}^{S}
$$

这个表示法中的 $S$ 表示网格中面的个数，上标 $i$ 表示存储在数据文件中的第 $i$ 个面。$(v_p^i, v_q^i, …, v_k^i)$ 代表围成第 $i$ 个面的几个顶点。

TODO: 这里补个图说明点云和网格的差别，最好带上文件 sample。

由于欧氏空间中 3 个点可以确定一个平面，因此 $F$ 中的一个元素长度至少为 3，但网格的广义定义并没有要求 $F$ 中的每个元素一样长。当然，任何一个多边形都可以分割成几个三角形^[8]，如果我们对一个网格中所有的面都分割成三角形，那么 $F$ 中的每个元素长度将严格等于 3，这个过程称为 三角化或三角剖分 (Triangulation)，所得到的网格有个特殊的名字叫 三角形网格 (Triangle Mesh)。

注意在三维视觉任务中网格一般不会记为 $M=(V, E)$^[9]，这是因为哪怕几个点连接成了一个封闭图形，也不足以说明这个封闭图形是原形状上的一个面。

TODO: 这里补个图说明为什么 M=(V, E) 来表示是不够的。

其实这种形式可以看作是一个无向图结构 (Undirected Graph)，我曾有段时间想将图神经网络中的方法应用到欧氏空间的网格上，但没有什么突破，这里就不展开了。

和点云类似，网格也被大量运用在实际场景，尤其是电影、游戏行业中。比如最近 Unreal Engine 5 也提到了他们可以实现一个包含 160 亿多边形的场景渲染，这是个不小的成就。然而，这些运用领域中的网格往往是由人手工设计的，目前由计算机生成的网格仍难以解决拓扑结构的问题。

在单视角三维重建课题，使用网格作为直接输出的代表作是 Pixel2Mesh。下图展示了 Pixel2Mesh 的模型结构。不用担心，在这篇博文中我们不会深究这个模型的结构和方法，只需了解这个模型通过某些方式将一个 椭球型的网格^[10] “捏” 成了目标输出的形状^[11] 即可。Pixel2Mesh 这么做的一个动机是它可以保证最终输出是封闭的 (Watertight)：因为起始的椭球型网格是封闭的，而 “捏” 这一操作只是移动网格上点的空间位置，所以最终输出和起始网格一样是封闭的。

然而，这一思路带来的另一个问题是它不能生成其它亏格的形状。换句话说，你要生成的形状其拓扑结构从一开始就是固定的，如果你打算用 Pixel2Mesh 的去生成一个甜甜圈，那么这是不可能的——甜甜圈^[13]中间有个洞而椭球形网格^[14]则没有。

除了「对封闭网格进行变换」这一思路外，为了解决网格对复杂拓扑形状应对能力差的问题，AtlasNet^[15] 提出可以用一组平面网格去拟合复杂的形状：你可以想象我们在用几张纸贴在所要拟合的物体上，只不过这几张纸其实是几块平面网格而已。很容易想到的是，这样的生成方式并不能保证最后的结果是封闭的，而且可能还会有严重的重影 (Overlap)。

TODO: 这里补个图说明什么叫重影。

目前来看，还没有特别好的网格自动生成方式能很好地同时兼顾形状封闭性和拓扑结构泛化能力。

TODO: 这一部分找个地方把 Mesh 含面方便渲染的特点补上。

基于体素的表示法 (Voxel-based)

我们知道在二维的照片里，每一个存储了颜色的单元叫 像素 (Pixel)，那么在三维的立体里一个最小单位是什么呢？我们把它称为 体素 (Voxel)。正如最开始的像素只用「0」和「1」来表示「黑」与「白」一样，我们用「0」来表示一个单位空间里没有实体，而用「1」来表示这个单位空间里有实体。

TODO: 这里补个图形象说明 Voxel-based 是什么样的。

用数学的语言来表示，一个由体素堆积起来的 立体 (Volume，暂译名) $V_o$ 可以定义为一个三维矩阵： $$ V_o = b_{i,j,k}, \\ where \ b_{i,j,k} \in \{0,1\} \\ and \ i,j,k \in \mathbb{Z}, \ such \ that\ \ 0 \le i,j,k \le N $$ 其中 $b_{i,j,k}$ 只能取值为「0」或「1」；$N$ 是一个整数，代表任一轴有 $N$ 个体素^[16]，反映了这个立体的分辨率。这里需要注意的是，与点云/网格中表示空间位置信息的 $x_i, y_i, z_i$ 不同，$i,j,k$ 只是立体中晶格 (Cell) 的索引 (Index)，取值是离散的。

用体素来表示物体形状一个显而易见的优点是它保证了物体形状是封闭的。

在不考虑压缩的情况下，Python 3.7 中 True 和False 各占用 8 个字节 (Byte)，那么一个 $128 \times 128 \times 128$ 的立体在 Python 3.7 中需要占用 $(128 \times 8)^3 = 1,073,741,824$ 字节，合计 1 GB 内存。这还只是表示形状的数据的大小，如果还要基于此进行诸如卷积等操作，那么所占用的内存将会更大。Numpy、Tensorflow、PyTorch、MXNet 都对矩阵运算进行了大量优化，但时至今日，处理 $128^3$ 以上的立体仍是一个挑战。

其它表示法

RGBD Image

在原有的 RGB 图片上加上了表示深度 (Depth) 的通道，形成了类似 2.5D 的效果。

Multi-view Image

本质上只是把多个角度的图片拼接在了一起，本身不包含形状的几何信息。

隐式表示 (Implicit Representation)

在正式介绍隐式表示法前，我们先来看看前面提到的显式表示法。

形状空间分布 (Occupancy)

「形状空间分布」是我暂定的译名（基于 Occupancy 含义所给的意译），

有向距离函数 (Signed Distance Function, SDF)

「有向距离函数」也是我暂定的译名（目前还没有看到被广泛使用的译名），在学术圈里往往用英文首字母缩写 SDF 指代。所谓「有向距离函数」，是指

总结

用一张表总结一下上述形状表示方法的特点：

类型	表示方法	优点	缺点
显式表示法	点云	轻量、简单； 接近采集到的原始数据；	容易被噪声影响； 几何信息少，没有面，难以推断拓扑结构；
	网格	轻量； 包含面的信息，利于几何处理和渲染；	主要来源是手工绘制，自动生成出的网格形状拓扑比较差；
	体素	形状封闭； 适合碰撞检测； 容易处理，可以直接拓展二维卷积的定义来处理形状；	存储开销大； 受限于内存大小，分辨率低； 在低分辨率下容易丢失细小结构；
隐式表示法	形状空间分布	形状封闭； 拓扑结构精细；	推断效率低； 目前的模型一般需要较长的训练时间；
	有向距离函数	形状封闭； 拓扑结构精细； 方便插值运算；	推断效率低； 目前的模型一般需要较长的训练时间；

注释

1. Karbo 的博文: 3D 结构重建, 2019 ↩
2. 其实是一种基于体素的表达 ↩
3. 取自 Vertices 的首字母 ↩
4. 至少点的存储顺序不同 ↩
5. 但我认为仍不够完美优雅 ↩
6. 只存储了每个点的坐标 ↩
7. 取自 Mesh 的首字母 ↩
8. 一个 N 边形可以分割成 N-2 个三角形 ↩
9. E 是一个存储点与点连接关系的集合，$(v_i, v_j) \in E$ ↩
10. 对应图中 Ellipsoid Mesh ↩
11. 对应图中 2466 vertices 的客机形状 ↩
12. Wang, N., Zhang, Y., Li, Z., Fu, Y., Liu, W., & Jiang, Y. G. (2018). Pixel2mesh: Generating 3d mesh models from single rgb images. In Proceedings of the European Conference on Computer Vision (ECCV) (pp. 52-67). ↩
13. 亏格为 1 ↩
14. 亏格为 0 ↩
15. Groueix, T., Fisher, M., Kim, V. G., Russell, B. C., & Aubry, M. (2018). A papier-mâché approach to learning 3d surface generation. In Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR) (pp. 216-224). ↩
16. 这里只讨论正方体立体 ↩
17. 当然 Numpy、Tensorflow、PyTorch、MXNet 都对此进行了优化 ↩