试图从这样的点云或点云中挑选物体的常规技术可以以速度或准确度来实现，但不能两者都这样。

研究人员表示，通过他们的新技术，机器人可以在接收到视觉数据的几秒钟内准确地挑出一个物体，如小动物，这些物体在密集的点云中被遮挡。该团队表示，该技术可用于改善机器感知必须既快速又准确的一系列情况，包括工厂和家中的无人驾驶汽车和机器人助手。

“这项工作令人惊讶的是，如果我要求你在这个数千点的云中找到一只小兔子，你就无法做到这一点，”航空航天助理教授兼麻省理工学院实验室成员LucaCarlone说。信息和决策系统(LIDS)。“但我们的算法能够通过所有这些混乱看到对象。因此，我们在本地化对象方面达到了超人的水平。“

Carlone和研究生HengYang将于本月晚些时候在德国的机器人：科学与系统会议上介绍该技术的细节。

“不知不觉失败”

机器人当前通过比较模板对象(对象(例如兔子)的3D点表示)与可能包含该对象的现实世界的点云表示来尝试识别点云中的对象。模板图像包括“特征”或点集合，其指示该对象的特征曲率或角度，例如兔子的耳朵或尾巴。现有算法首先从现实点云中提取相似的特征，然后尝试匹配这些特征和模板的特征，并最终旋转并将特征与模板对齐，以确定点云是否包含相关对象。

但是，流入机器人传感器的点云数据总是包含错误，以错误位置或间隔不正确的点的形式，这可能会极大地混淆特征提取和匹配过程。因此，机器人可以产生大量错误的关联，或者研究人员称之为点云之间的“异常值”，最终错误识别对象或完全错过它们。

Carlone说，一旦匹配功能，最先进的算法能够从好的东西中筛选出坏的关联，但是它们是在“指数时间”这样做的，这意味着即使是一堆处理繁重的计算机，也可以通过密集筛选用现有算法点云数据，无法在合理的时间内解决问题。这些技术虽然准确，但对于分析包含密集点云的较大的真实数据集是不切实际的。

其他可以快速识别特征和关联的算法匆忙地进行，在过程中产生大量异常值或误检，而不会意识到这些错误。

“如果这是在自动驾驶汽车或任何安全关键应用上运行，那就太可怕了，”Carlone说。“在不知道你失败的情况下失败是算法可以做的最糟糕的事情。”

轻松的景色

Yang和Carlone设计了一种技术，可以在“多项式时间”中修剪异常值，这意味着它可以快速完成，即使对于日益密集的点云也是如此。因此，该技术可以快速准确地识别隐藏在杂乱场景中的对象。

研究人员首先使用传统技术从点云中提取模板对象的特征。然后，他们开发了一个三步过程，使点云中的对象的大小，位置和方向与模板对象相匹配，同时识别不良特征关联的好处。

该团队开发了一种“自适应投票方案”算法来修剪异常值并匹配对象的大小和位置。对于大小，算法在模板和点云特征之间建立关联，然后比较模板中的特征与点云中的相应特征之间的相对距离。例如，如果点云中两个要素之间的距离是模板中对应点的五倍，则该算法会对对象比模板对象大五倍的假设进行“投票”。

该算法为每个特征关联执行此操作。然后，算法选择那些具有最多投票的大小假设下的关联，并将这些关联标识为正确的关联，同时修剪掉其他关联。通过这种方式，该技术同时揭示了正确的关联以及由这些关联表示的对象的相对大小。相同的过程用于确定对象的位置。

研究人员开发了一种单独的旋转算法，可以在三维空间中找到模板对象的方向。

要做到这一点是一个非常棘手的计算任务。想象一下拿着一个杯子并试图倾斜它，以匹配可能是同一个杯子的模糊图像。你可以倾斜任何角度的杯子，每个角度都有一定的可能性匹配模糊的图像。

现有技术通过将对象的每个可能的倾斜或旋转视为“成本”来处理该问题-成本越低，该旋转在特征之间创建精确匹配的可能性越大。每个旋转和相关的成本在各种地形图中表示，由多个山丘和山谷组成，较低的海拔与较低的成本相关联。

但是Carlone说这很容易混淆算法，特别是如果有多个山谷并且没有可辨别的最低点代表对象的特定旋转与点云中的对象之间的真实，精确匹配。相反，该团队开发了一种“凸松弛”算法，简化了地形图，其中一个谷表示最佳旋转。以这种方式，该算法能够快速识别定义点云中对象的方向的旋转。

通过他们的方法，团队能够快速准确地识别隐藏在密度增加的点云中的三个不同的物体-兔子，龙和佛陀。他们还能够识别真实场景中的物体，包括起居室，其中算法很快就能够发现麦片盒和棒球帽。

Carlone表示，由于该方法能够在“多项式时间”内工作，因此可以轻松扩展以分析更密集的点云，例如，类似于无人驾驶汽车的传感器数据的复杂性。“导航，协同制造，家用机器人，搜索和救援以及自动驾驶汽车是我们希望产生影响的地方，”Carlone说。