Point Cloud

Introduction

  • Intro: 点云是一种用于表示三维空间中对象或场景的数据结构。在原始的实现中，它其实是一个包含多个三维坐标点的集合(这些点是通过对实际场景或物体的表面进行离散采样而得到的)。
  • Def: 点云是场景表面在给定坐标系下的离散表示
  • Properties:
    • 高度灵活性Flexibility: 可用于表示各种类型的三维形状
    • 数据密度可变性: 可sparse, 可dense
    • 附加信息丰富性: 除了坐标外，可含其他属性信息。比如在重建中，点云一般还携带着color/intensity value, time, etc的信息。

Package Requirement

  • open3d in Python

    • One thing need to focus is that your open3d version should be correct, otherwise it will lead to dependency problems. You can deal with this by lowing the open3d version. For example, my Python verision is 3.9.12 and my open3d version is 0.15.1. Finally, it can work.
    1
    pip install open3d==0.15.1

Point Cloud Registration

  • Intro: 点云配准指的是输入两个有限点云 PsP_s , PtP_t , 输出一个变换 TT 使得 T(Ps)T(P_s) 与 PtP_t 的重合度尽可能更高。对于我们要研究的问题来说，在本文中 TT 被定为Rigid，即刚性的。一般来说点云配准可分为两步，即粗配准和精配准 (这一概念在Nerf中也有体现，即分层体素渲染(hierarchy volume rendering)先进行一遍随机采样来获得初始的分布，再在得到的分布上进行fine采样，最终不仅加快了采样效率还提高了performance)

ICP(Iterative Closest Point)

  • Overview
    icp_pseudocode
  • Target: F(R,t)=R∗,t∗=argminR,t1∣Ps∣∑i=1∣Ps∣∥pti−(R∗psi+t)∥2F(R, t)= R^*, t^* = argmin_{R, t}\frac{1}{|P_s|} \sum_{i = 1}^{|P_s|} \| p_t^i - (R*p_s^i + t) \|^2
  • Main Component
    • Find the nearest point (using last iteration transformation)
      • Use KD-TREE to accelerate the finding process, which is alike the partition search.
      • Set the threshold to accelerate the finding process (Approximately finding)
    • Find the better transformation (using the current iteration nearest point pairs)
      • 拥有闭式解 (closed-form solution)
        • 定义 3*3 matrix H=∑i=1∣Ps∣psi^pti^TH = \sum_{i = 1}^{|P_s|}\hat{p_s^i}\hat{p_t^i}^T, and H=UΣVTH = U\Sigma V^T
        • R∗=VUTR^* = VU^T
        • t∗=ps^−R∗pt^t^* = \hat{p_s} - R*\hat{p_t}
      • Step 1: 计算最优位移 t∗t^*
        • ∂F∂t=∑i=1∣Ps∣2∗(R∗psi+t−pti)=2∣Ps∣t+2R∗∑i=1∣Ps∣psi−2∗∑i=1∣Ps∣pti=2∣Ps∣t+2R∗∣Ps∣pt^−2∗∣Ps∣ps^\frac{\partial F}{\partial t} = \sum_{i = 1}^{|P_s|} 2 * (R*p_s^i + t - p_t^i) \\ = 2|P_s|t + 2R * \sum_{i = 1}^{|P_s|} p_s^i - 2 * \sum_{i = 1}^{|P_s|} p_t^i \\ = 2|P_s|t + 2R *|P_s| \hat{p_t} - 2 *|P_s| \hat{p_s}
        • 令导数等于0
        • t=ps^−R∗pt^t = \hat{p_s} - R*\hat{p_t}
      • Step 2: 计算最优旋转 R∗R^*
        • First: Standardlized: 将坐标系移至点云的中心，该步旨在化简最小二乘Loss function因为 tt 的取值在给定 点云是确定的
        • Second: 因为旋转矩阵 RR 是正交矩阵所以满足 RT∗R=IR^T * R = I
          • F=∑i=1∣Ps∣∥pti^−R∗psi^∥2=(pti^−R∗psi^)T(pti^−R∗psi^)=(pti^T−psi^T∗RT)(pti^−R∗psi^)=∥pti∥2+∥psi∥2−2∗pti^T∗R∗psi^F = \sum_{i = 1}^{|P_s|} \| \hat{p_t^i} - R*\hat{p_s^i} \|^2 \\ = (\hat{p_t^i} - R*\hat{p_s^i})^T(\hat{p_t^i} - R*\hat{p_s^i}) \\ = (\hat{p_t^i}^T - \hat{p_s^i}^T*R^T)(\hat{p_t^i} - R*\hat{p_s^i}) \\ =\|p_t^i \|^2 + \|p_s^i \|^2 - 2* \hat{p_t^i}^T * R * \hat{p_s^i}
        • Third: 因此我们的Loss function 可以进一步化简, 并且由于trace的性质我们有
          • R∗=argmaxR (∑i=1∣Ps∣pti^T∗R∗psi^)=argmaxR trace(PtTRPs)R^* = argmax_R \ (\sum_{i = 1}^{|P_s|} \hat{p_t^i}^T * R * \hat{p_s^i})\\ = argmax_R \ trace(P_t^TRP_s)
        • Fourth: 由于trace的性质我们有
          • R∗=argmaxR trace(RPsPtT)=argmaxR trace(RH)=argmaxR trace(RUΣVT)=argmaxR trace(ΣVTRU)R^* = argmax_R \ trace(RP_sP_t^T) \\ = argmax_R \ trace(RH) \\ = argmax_R \ trace(RU\Sigma V^T) = argmax_R \ trace(\Sigma V^TRU)
        • Fifth, let M=VTRUM = V^TRU, 我们由奇异值非负数且正交矩阵得性质，可得当 MM 为单位阵trace最大
          • R∗R^*最后要检查 R∗R^* 是否为一个旋转矩阵, 即 ∣R∗∣=1|R^*| = 1 其行列式要大于0。若行列式小于0等于-1, 那么其代表为一个reflection。因此我们要多加入一个约束条件，最终有

          • R∗=V[10001000det(VUT)]UTR^* = V\left[\begin{matrix}1 &0 &0 \\0&1&0 \\0&0&det(VU^T)\end{matrix}\right]U^T

    • Iteration:
      • Break condition:
        • Rk,tkR_k, t_k变化很小
        • loss变化很小
        • 达到设置的迭代次数上限
  • Implementation
    • 注意超参数的设定，在此处应注意的是会引入subset_size这一参数。因此前后配准的两个点云大小并不相同，所以我们每次会挑选一个子集来进行局部配准！！！
    • 注意引入KD-TREE来加速你的寻近邻的过程

ICP with RANSAC

  • RANSAC (Random sample oonsensus) Intro: 通过割舍一些过远的点来得到更好的拟合效果。

    • Step 1: 先随机采样抽取 num_samples 数量个点，然后对模型进行拟合
    • Step 2: 接着根据设置的 Sigma 阈值，来找出拟合曲线周围在阈值范围内的点，并且进行统计
    • Step 3: 判断当前个数与已知的最大个数作比较，若更大，则保留；若更小，则不保留
    • Step 4：迭代结束后，输出当前最优的拟合模型

  • Implementation

    • 注意超参数的选取，尤其是RANSAC的超参数，你需要找到一个合适的num_samples，并且在Sigma的设置中，你需要进行权衡取舍。这样最终你才能得到一个较好的T。