三维点云表示的距离度量方法及其在计算机视觉中的应用

10478用于学习三维点云表示的点集距离Trung Nguyen1Quang-Hieu Pham3Tam Le4Tung Pham1Nhat Ho5Binh-Son Hua1，21 VinAI Research，越南2VinUniversity，越南3Woven Planet北美，Level 54 RIKEN AIP日本5德克萨斯大学奥斯汀摘要学习3D点云的有效表示需要良好的度量来测量两个3D点集之间的差异，由于它们的不规则性，这是不平凡的大多数以前的作品诉诸于使用倒角差异或地球移动器在本文中，我们进行了系统的研究与广泛的实验距离度量的三维点云。从这项研究中，我们建议使用切片Wasserstein距离及其变体来学习3D点云的表示此外，我们引入了一个新的算法来估计切片Wasserstein距离，保证估计值是足够接近的真实的。实验表明，与Chamfer差异相比，切片Wasserstein距离及其变体允许神 经 网 络 学 习 更 有 效 的 表 示 。 我 们 展 示 了 切 片Wasserstein度量及其变体在3D计算机视觉中的几项任务上的效率，包括训练点云自动编码器，生成建模，迁移学习和点云配准。1. 介绍自现代人工智能的火花迸发以来，点云上的3D深度学习已经成为一种强大的-解决识别问题的有效技术，如对象分类[44，21]，对象检测[43]和语义分割[41]。还研究了使用3D点云的生成建模，并取得了一些有希望的结果[51，46，32，22，47，33]。深度学习方法兴起的另一个3D计算机视觉问题是点云匹配[8，11，10，17]。所有这些问题都有一个共同的任务-即学习3D点云的鲁棒表示。在学习3D点云表示的最重要的步骤之一是选择度量来测量两个点集之间的差异。这种度量有两种常用的选择：倒角散度[ 16 ]地球移动器虽然早期的工作[16，1]已经表明EMD在学习表示方面比Chamfer表现更好，但Chamfer更受欢迎[10，52，18，15，12，19]，因为它的计算成本显着降低。在这篇文章中，我们重新审视了3D点云深度学习中的相似性度量问题我们建议使用切片Wasserstein距离（SWD）[5]，其基于将点云中的点投影到一条线上，及其变体作为监督3D点云自动编码器的有效度量。与倒角发散相比，SWD更适合于点云重建，同时保持计算效率（参见图1）。图1）。我们表明，倒角发散弱于EMD和切片Wasserstein距离（参见。引理1），而EMD和切片Wasserstein距离是等价的。这表明，即使当两个点云在倒角散度上接近时，它们在EMD或切片Wasserstein 距 离 上 也 可 能 不 接 近 。 此 外 ， 切 片Wasserstein距离具有NlogN[5]量级的计算复杂度，这与Chamfer散度的计算复杂度相当，而EMD具有N3[39]量级的复杂度，其中N是3D点云中的点数。最后，在标准 点 云 设 置 下 ， 由 于 点 的 维 数 通 常 为 3 ， 切 片Wasserstein距离中的投影步骤只会导致原始点云的信息的少量损失因此，切片Wasserstein距离在Chamfer散度和EMD上具有为了提高来自SWD的切片的质量，我们还讨论了切片Wasserstein距离的变体，包括最大切片Wasserstein距离[13]和所提出的自适应切片Wasserstein算法。通过对学习3D点云自动编码器进行案例研究，我们提供了关于不同度量的性能的全面基准。这些结果符合我们的理论发展。总之，我们的主要发现是：• 第 一 个 理 论 研 究 倒 角 散 度 ， EMD 和 切 片Wasserstein距离之间的关系，用于点云学习（第4节）。10479∈图1：我们提倡使用切片Wasserstein距离来训练3D点云自动编码器。 在这个例子中，我们尝试通过优化两个不同的损失函数将球体变形为椅子：倒角差异（顶部，红色）和切片Wasserstein距离（底部，蓝色）。所提出的切片Wasserstein距离只需要1000次迭代就能收敛，而Chamfer差异需要50000次迭代。• 一种名为自适应切片Wasserstein的新算法，用于评估切片Wasserstein距离，确保评估值足够接近真实值（第4节）。• 点云学习任务的广泛评估，包括点云重建，迁移学 习 ， 基 于 Cham- fer 差 异 ， EMD ， 切 片Wasserstein距离及其变体的点云配准和生成（第5节）。2. 相关工作设置相似性。 3D点云自动编码器非常有用 在广泛的应用中，例如去噪[19]，3D匹配[55，10，12，31]和生成模型[16，1]。近年来，已经提出了许多自动编码器架构[1，52，10]。 为了训练这些自动编码器，有两种流行的损耗选择：倒角差异（CD）和地球移动器距离（EMD）。倒角差异已广泛用于点云深度学习[16，1，52]。已知倒角差异（CD）不是意味着存在CD几乎等于零的两个不同点云虽然早期的工作[16，1]表明EMD在3D点云重建任务中优于Chamfer，但最近的工作[42]仍然有利于Chamfer差异，因为其计算速度快。瓦瑟斯坦距离。 在2D计算机视觉中，Wasserstein距离家族及其基于切片的版本已经在以前的作品中被考虑[2 ， 20 ， 48 ， 14 ， 13 ， 49 ， 29 ， 23] 。 特 别 地 ，Arjovsky et al.[2]提出使用Wasserstein作为生成对抗网络（GANs）的损失函数，而Tolstikhin等人。[48]建议将该距离用于自动编码器框架。然而，Wasserstein距离，包括EMD，具有昂贵的计算成本很高，并且可能遭受维数灾难，即，训练模型所需的数据数量将随着维数呈指数增长。为了处理Wasserstein距离的这些问题，一系列工作已经利用切片方法来降低目标概率测量的维度。值得注意的切片距离是切片Wasserstein距离[5]。后来，切片Wasserstein距离的想法已经适应了自动编码器设置[25]和域自适应[30]。Deshpande等[14]提出使用最大切片Wasserstein距离，当我们只选择最佳方向来投影概率测度时，切片Wasserstein距离的一个版本，来制定生成对抗网络的训练损失。与切片Wasserstein距离相比，后续工作[13，49在最近的工作中，Nguyen et al.[37，38]提出了一种概率方法，通过在投影上找到最佳测量来选择多个重要方向。基于切片的距离的另一个方向是通过用非线性投影替换线性投影来捕获概率度量的更复杂的几何结构[24]。然而，据我们所知，这些作品都没有考虑过3D点云的学习问题。记法。 设Sn−1是n维空间空间对于度量空间（Ω，d）和Ω上的两个概率测度μ和ν，设Π（μ，ν）是所有联合分布γ的集合，使得其边际分布分别为μ和ν对于任何θSn−1和任何测度μ，πθ<$μ表示μ通过映射Rθ的前推测度，其中Rθ（x）=θ<$x，对所有x。3. 背景为了研究点云学习的不同指标的性能，我们简要回顾了数学基础。10480ΣΣxy||||{||||}≥{||||}Σ| −|⊂→||||F（ t）−F哪里|P||Q|MCD|P|y∈Q2XpY（tΣγe），Chamfer差异和Wasserstein距离的关系，这是本文的关键组成部分。请注意，在计算机视觉中，Chamfer经常被滥用为距离。严格地说，Chamfer是一个伪距离，而不是距离[16]。因此，在本文中，我们使用术语倒角差异或倒角散度代替。3.1. 倒角偏差在点云深度学习中，倒角差异已被用于许多任务。有一些变种其中FX和FY分别是随机变量X和Y的累积分布函数。当维数大于1时，WD没有闭合形式，这使得计算WD更加困难。3D点云应用中的EMD 对于3D点云的特定设置，还采用EMD来定义两个点云之间的度量[16，1，53]。对于任何两个给定的点云P和Q，在本文中，我们滥用符号表示其测量表示如下：P =1δ Q=1δx∈P y∈Q奈斯对于任何两个点云P、Q，P和Q之间的倒角差异的共同公式由下式给出：δx表示点云P中的点X处的狄拉克δ分布。当P=Q时，地球移动器d CD（P，Q）=1Σmin|| x − y ||2+1Σmin|| x −y||二、2dEMD（P，Q）=minΣ||x − T（x）||.（四）|P| x∈P y∈Q|Q| y∈Q x∈P2（一）T：P→Q2x∈ P以前的作品[52，10，12，3]也使用了一个稍微修改过的倒角发散版本，用一个max函数代替了d（P，Q）= max，1Σmin ||x − y||二、x∈P虽然早期的工作[16，1]表明EMD在3D点云重建任务中优于Chamfer，但与Chamfer发散相比，EMD的计算可能非常昂贵。特别地，已经表明EMD的实际计算效率在数量级最大P，Q3[39]，这可能是昂贵的。有一个最近的工作线使用熵版本的EMD或在gen-1Σmin||x−y||2、.（二）一般的Wasserstein距离[9]来加速计算|Q| y∈Q2x∈ P的EMD。然而，使用熵方法来近似EMD的最佳已知实际复杂度为在这两个定义中，min函数意味着Chamfer差异只关心一个点的最近邻居，而不是那些最近点的分布。因此，只要x和y的支撑接近，则它们之间对应的倒角差异就小，同时它们对应的分布可以不同。在文献[1]中也发现了一种类似的现象，称为倒角盲，指出倒角差异不能区分坏样本和真样本，因为它的区分力较低。3.2. Wasserstein距离设（n，d）是度量空间，μ，ν是n上的概率测度.对于pi，p-Wasserstein距离（WD）由下式给出：阶maxP，Q2[34，35]，这仍然是昂贵的，比倒角发散慢因此，有必要开发3D点云之间的度量，使得其不仅具有与EMD的统计特性等效的统计特性，而且具有类似于倒角散度的计算复杂度的有利的计算复杂度。4. 切片Wasserstein距离及其变体在本节中，我们首先说明倒角散度比第4.1节中的地球移动器距离散度弱 由于地球移动器最后，我们提出了一个新的算法来计算切片-Wp（μ，ν）= infE（μ，ν（X，Y）1d p（X，Y）p.在4.2.2节中，可以保证估计值足够接近真实值的Wasserstein。当p= 1时，Wasserstein距离变为地球移动器距 离（ EM D ） ， 其 中 最 优 联 合 分 布 γ 产 生 映 射 T ：μ ν ， 该 映 射 保 持 任 何 可 测 量 集 B Ω 上 的 测 量值 。在一维情况下，WD =R且d（x，y）=x，y，WD具有以下封闭式公式：4.1. 倒角发散度与地球运动距离的关系在这一节中，我们研究了P=Q时Chamfer和EMD之间的关系。特别地，下面的不等式表明倒角散度弱于Wasserstein距离。W（μ，ν）=. ∫1.-1-1 p01、（3）引理1. 假设|P|为|Q|以及P和Q的支持Σp倒角差异，我们在这里提供完整的-，dt是有界于一个直径为K的凸包，那么我们发现，10481⇒ minx −y ≤ Kx −T（x），y∈Q−O{||| | }{||||}O{||||}Oy∈Q≤2θθSW p（μ，ν）=. ∫W. πθ µ，πθν） dθd CD（P，Q）≤2Kd EMD（P，Q）。（五）证据 假设T是从P到Q的最优方案。然后我们发现minx−y2≤x−T（x）2222y∈ Q因为<$x−T（x）<$2≤K。对x求和，我们得到Σminx − y2≤ K Σx − T（x）2。4.2. 切片Wasserstein距离及其变体为 了 规 避 EMD 的 高 计 算 复 杂 度 ， 设 计 了 切 片Wasserstein距离[5以利用等式（3）中的Wasserstein距离的1D公式。4.2.1切片Wasserstein距离特别地，切片Wasserstein距离的思想是，我们首先将目标概率测度μ和ν投影到单位球面上的一个方向，即θ上，以获得分别由πθ μ和πθ ν表示的两个然后，我们计算两个投影测度π µ和π ν之间的Wasserstein距离。切片Wasserstein距离x∈ Px∈P（SWD）通过取Wasserstein在所有可能的情况下，两个投影测量之间的距离-类似地，我们有Σ∈Qminx∈Px−y2≤倾斜投影方向θ。特别地，对于任何给定的p≥1，KΣy∈Qy−yT¯（y）2其中T¯2是 的 最优方案p阶的切片Wasserstein距离被公式化为从Q到P然后，我们得到所需的不等式。引理1中的不等式意味着最小化Wasserstein距离导致更小的倒角差异，如下所示：ppSn−11.（六）相反的不等式不成立。因此，EMD和Chamfer散度是不等价的，这可能是不期望的。注意，该不等式不能改进到K的更好阶。例如，让我们考虑两点-具有小方差ε2的云，同时两个点云中心之间的距离等于K O（ε）。 则CD的阶数为K2，EMD的阶数为K.引理1示出了倒角散度弱于EMD，EMD进而弱于其他散度，诸如KL、卡方等。[40，第117页]。然而，正如我们之前解释的那样，Cham- fer差异具有弱点，并且其他差异不如EMD有效，因为即使当两个分布彼此接近时，它们也非常松散[2]。因此，Wasserstein/EMD是用于学习两个分布之间的差异的优选尽管如此，计算EMD可能非常昂贵，因为它相当于解决线性规划问题，其具有最佳的实际计算复杂性（maxP3，Q3）[39]。另一方面，倒角发散的计算复杂度可以按比例增加到（maxP，Q）的数量级。因此，由于其有利的计算复杂度，倒角发散在实践中仍然是优选的。考虑到上述观察，理想地，我们希望利用P和Q之间的距离，使得其等同于EMD，并且在maxP，Q方面具有线性计算复杂度，这与Chamfer散度相当。这将我们带到下一节中的切片Wasserstein距离的概念SWp被认为是Wasserstein距离的低成本近似，因为其计算复杂度为（nlogn）的数量级，其中n是离散概率测度μ和ν的最大支持数。当p= 1时，SWp弱等价于一阶WD或等价于EMD [4]。 SW1和EMD之间的等价性以及引理1的结果表明，SW1是比倒角散度更强的度量，同时它具有与点云的点数成线性的吸引人的最佳计算复杂度，这与倒角散度的计算复杂度相当。我们要注意的是，由于点云中的点的维度通常很小（6），即使在我们将点云投影到球体上的某个方向之后，切片Wasser-stein距离仍然能够保留点云的有用信息 由于其有利的计算复杂性，切片Wasserstein距离已用于若干应用中：点云配准[28]，2D图像上的生成模型;例如参见[45，36，14，25，26，49，27]。然而，据我们所知，这个距离尚未用于3D点云的深度学习任务。蒙特卡罗估计在等式（6）中，积分通常难以计算。因此，我们需要近似积分。近似积分的常用方法是应用蒙特卡罗方法。特别地，我们对N个方向θ1，. . .，θ N均匀地从球面Sd−1，其中d是点云中的点的维数，这导致以下近似Σ p10482. Σ。1pΣΣ4N+s≥2NNN ≤..∫e−x/2pNp输出：软我Ni=1我我1p我我pNi=1NN我NNN−1N-≤N+sΣNNi=1切片Wasserstein距离：NSW（μ，ν）Wp πµ，π1好吧 （七）算法1：自适应切片Wasserstein。输入：两个点集，正整数N0，s;n>0;最大投影数M其中切片的数量N被调整以获得最佳性能。由于N在确定切片Wasserstein距离的近似中起着关键作用，因此通常基于概率测度μ和ν的维数来选择它。在我们的3D点云应用中，由于点云中的点的维度通常很小，我们观察到选择投影的数量N高达100已经足以很好地学习3D点云。最大切片Wasserstein距离为了避免在SWD中使用统一切片，另一种方法集中于在区分两个给定分布时仅取最佳切片这导致最大切片Wasserstein距离[13]。样本N0个投影;计算sw：=swN0，sw2：=sw2N0，N：=N0;whilesw2（sw）2>（N−1）2&N Mdo样品的投影计算sws，sw2s;赋值sw：=N×sw+s×sws;赋值sw2：=N×sw2+s×sw2s;赋值N：=N+s;端给定一个预定义的容差ε >0，我们的目标是对于任何p 1，阶的最大切片Wasserstein距离P由下式给出：ks¯N√Nk2s¯2≤100，或N ≤.（十一）MSWp（ µ，ν）：=maxθ∈Sn−1W p. π θ μ，π θ ν）。（八）从等式（9），我们注意到s¯2=2N所以4.2.2一种自适应切片Wasserstein算法N需要选择N使得k2N−1N−12. 重写-2SWD中蒙特卡罗估计的另一个缺点通过等式（9）中的有偏方差，我们得到它没有提供关于如何接近估计的信息1ΣNsw2−（sw N）2。 表示sw2N ：=1ΣNSW2，mate值是真实的。因此，我们介绍了新的自适应切片Wasserstein算法（ASW）。按面值-条件变为2（N−1）2图中，给定N个均匀随机投影{θ}Nsw2N−（sw N）≤2。从球面Sn−1出发，为了表示简单，我们记为sw i=W p π θµ，π θ ν），对所有1≤i≤N。毛皮-这就引出了算法1的构造。在这因此，我们将sw=SWp（μ，ν）表示为我们要计算的SW距离。SW距离的Monte Carlo估计可以写成如下：摆动N：=1Nswi，它是投影的数量N=N0，然后通过估计距离估计器的在线均值和方差，利用额外的s个样本动态地更新N，直到估计的误差满足误差界。我们注意到ASW算法真值开关 同样，有偏和无偏方差估计数分别定义为：N可用于计算SWD的其他变体，例如广义切片Wasserstein距离[24]。s2：=1。sw−swΣ2，s¯2：=Ns2。（九）我们的自适应性的思想是动态地确定的数量，伯的预测N从所观察到的均值和方差的估计。为此，我们利用估计器误差的概率界，并选择N，使得误差界低于某个容限阈值。特别地，应用中心极限定理，我们有P|sw−s w|

下载后可阅读完整内容，剩余1页未读，立即下载