确定物体方向的算法可以帮助机器人进行导航

假设您正在尝试浏览大城市中不熟悉的部分，并且您正在使用特定的摩天大楼群作为参考点。交通和单行道迫使你采取一些奇怪的转弯，有一段时间你会看不到你的地标。当它们重新出现时，为了将它们用于导航，您必须能够将它们识别为您之前跟踪的相同建筑物 - 以及您相对于它们的方向。

这种类型的重新识别是人类的第二天性，但对计算机来说却很难。在6月的IEEE计算机视觉和模式识别会议上，麻省理工学院的研究人员将通过识别三维场景中的主要方向，提出一种新的算法，使其更加容易。相同的算法还可以简化场景理解问题，这是计算机视觉研究的核心挑战之一。

该算法主要用于帮助机器人驾驶不熟悉的建筑物，而不是驾驶者在不熟悉的城市中航行，但原理是相同的。它的工作原理是识别给定场景中的主导方向，它表示为一组轴 - 称为“曼哈顿帧” - 嵌入在一个球体中。当机器人移动时，它实际上将观察球体在相反方向上旋转，并且可以测量其相对于轴的方向。每当它想要重新定位时，它就会知道它的哪些地标的面应该朝向它，使它们更容易识别。

事实证明，相同的算法也极大地简化了平面分割的问题，或者决定了视觉场景的哪些元素位于哪个平面的哪个深度。平面分割允许计算机在场景中构建对象的四四方形模型 - 反过来，它可以与存储的已知对象的三维模型匹配。

麻省理工学院电子工程和计算机科学研究生Julian Straub是该论文的第一作者。他的顾问是麻省理工学院计算机科学与人工智能实验室的高级研究科学家John Fisher，以及机械与海洋工程教授John Leonard，以及Fisher's Sensing，Learning的博士后Oren Freifeld和Guy Rosman。和推理组。

研究人员的新算法适用于Microsoft Kinect或激光测距仪捕获的三维数据。首先，使用已建立的程序，算法估计场景中的大量单个点的方向。然后将这些方向表示为球体表面上的点，每个点定义相对于球体中心的唯一角度。

由于初始方向估计是粗略的，球体上的点形成松散的簇，这些簇很难区分。使用关于初始方向估计的不确定性的统计信息，算法然后尝试将曼哈顿帧拟合到球体上的点。

基本思想类似于回归分析 - 找到最接近点分散的线条。但是球体的几何形状使它变得复杂。“大多数经典统计数据都是基于线性和欧几里德距离，因此你可以得到两个点，你可以将它们相加，除以2，这将给你平均值，”Freifeld说。“但是一旦你在非线性空间中工作，当你进行平均化时，你就会落在空间之外。”

例如，考虑测量地理距离的例子。“说你在东京，我在纽约，”弗雷菲尔德说。“我们不希望我们的平均值位于地球中部; 我们希望它在表面上。“新算法的关键之一是它将这些几何结合到关于场景的统计推理中。

原则上，通过使用数百个不同的曼哈顿帧可以非常精确地近似点数据，但这会产生一个太复杂而无用的模型。因此，该算法的另一个方面是成本函数，其权衡近似与帧数的准确度。该算法以固定数量的帧开始 - 大约在3到10之间，具体取决于场景的预期复杂性 - 然后尝试在不影响总体成本函数的情况下减少该数量。

得到的曼哈顿帧集合可能不代表彼此略微错位的对象之间的细微区别，但这些区别对于导航系统并不十分有用。“想想你如何导航房间，”费舍尔说。“你没有建立一个精确的环境模型。你有点捕捉松散的统计数据，这些统计数据允许你以一种你不会在椅子上绊倒的方式完成你的任务。“

一旦确定了一组曼哈顿帧，平面分割的问题就变得容易得多。不占用大部分视野的物体 - 因为它们很小，很远或被遮挡 - 会给现有的平面分割算法带来麻烦，因为它们产生的深度信息很少，无法可靠地推断出它们的方向。但如果问题只是在少数几种可能的方向中进行选择，而不是潜在的无限，那就变得更容易处理。

乔治亚理工学院交互式计算教授弗兰克德拉特尔没有参与这项研究，称这项工作“有趣”，并补充说它“推广到非垂直框架，这在操纵环境中很重要，并且它适用于深度图像，随着Kinect和其他深度传感器的兴起而变得非常受欢迎。“

“我相信应该应用这些技术，”Dellaert说。“无论他们是否愿意，取决于那些最终将在大规模生产的自动系统中实施和部署这些技术的公司所看到的增值价值，无论是家用机器人还是自动驾驶汽车。在算法通用性和一定量的复杂性之间总是存在权衡以利用诸如人造结构之类的约束。在目前的情况下，我认为使用这些约束的优势是显着的，并将在未来的自治系统中得到利用。“