6、点集配准与单目非刚性3D重建方法综述

点集配准与单目非刚性3D重建方法综述

在计算机视觉领域，点集配准和单目非刚性3D重建是两个重要的研究方向。本文将详细介绍点集配准中的局部细化和概率方法，以及单目非刚性3D重建的相关内容。

1. 点集配准中的局部细化和概率方法

1.1 N体模拟加速技术

在N体问题中，若单独考虑每个粒子，需要$O(N^2)$次操作。为降低计算复杂度，实现大规模N体系统的模拟，提出了以下几种方法：
- Ahmad - Cohen（AC）邻域方案 ：为每个粒子采用两个时间尺度，对相邻粒子的力评估比远处粒子更频繁。在较小时间步长下，对远处点的贡献进行近似。不过，该方案虽能加速，但复杂度仍为$O(N^2)$。
- Barnes - Hut八叉树 ：提出一种树状数据结构用于分层计算力和引力势能。其核心思想是根据粒子间的距离对粒子进行聚类，并累积给定点$\vec{r}_i$处的力或引力势能贡献，算法复杂度为$O(N logN)$。
- 快速多极子方法 ：扩展了Barnes - Hut的思想，允许对一组点进行集体贡献。它利用多极展开进行分层空间分解，相邻近场粒子在远场粒子施加的力作用下往往加速相似。该类算法利用了$N×N$相互作用矩阵的秩亏特性，复杂度为$O(N logN)$，乘法常数取决于近似精度。也存在$O(N)$的算法，但会进一步增加乘法常数。

以下是这些方法的复杂度对比表格：
| 方法 | 复杂度 |
| ---- | ---- |
| 单独考虑每个粒子 | $O(N^2)$ |
| Ahmad -