微软专利提出优化的空间环境3D映射更新方法
更新环境的3D映射
（映维网Nweon 2023年11月27日）环境的3D映射是环境中的3D位置和与3D位置相关的捕获图像的集合。所述关联或者来自描述环境中3D位置的landmark的捕获图像，或者来自由具有环境中的3D位置和方向的捕获设备捕获的图像。绘制的环境是任何室内或室外环境，如家庭、办公室内部、花园、公共火车站或其他环境。
现有的3D映射优化方法在处理大量数据时遇到了严重的瓶颈，并且对不断增长的输入数据的适应性要求较低。
所以在名为“Updating a 3d map of an environment”的专利申请中，微软提出了一种优化的3D映射更新方法。
发明的各种实施例描述了用于更新环境的3D映射的方法，所述3D映射包含描绘环境的传感器数据项，每个传感器数据项具有一个或多个相关变量。关联变量的一个示例是捕获设备的姿态。关联变量的另一个例子是landmark的3D位置。在通信网络的管理节点上，接收传感器数据项。传感器数据项通常是已被捕获设备捕获的任何数据项。
至少部分地基于所接收的传感器数据项计算图形。例如，接收到的数据用于计算图形。计算图包括节点和边，表示所接收的传感器数据项中的至少一个变量的节点和表示变量之间关系的边。
所述通信网络的管理节点将所述映射划分为多个子图。对映射进行分区，以减少子图之间共享的变量数量。所述多个子图中的每一个分配到所述通信网络的各自工作节点。在每个工作节点，计算变量的更新值。采用基于共识的近端算法等共识过程来更新子图之间共享的变量值。根据变量的更新值更新环境的3D映射。
通过在工作节点使用本地计算作为consensus-based近端算法的一部分，可以以高效和可扩展的分布式方式计算精确的3D映射。这里的术语“接近”意味着局部计算试图使共享变量接近先前的共识值。近端步骤和一致步骤以交替的方式发生。生成的3D映射与使用相同数据和等效非分布式算法计算的映射具有相同的质量。
consensus-based近端算法是一种利用近端算子来解决涉及共识约束的优化问题的过程，其中约束强制执行给定变量组的相等性。consensus-based近端算法结合了consensus-based方法和近端优化两种思想。
consensus-based方法将大型优化问题分解为可独立解决的子问题，并将子问题的优化与子问题之间的共识优化交替进行，使共享变量一致。
近端优化可以表示分多个步骤解决优化问题的想法，每次向原始问题添加一个二次项，迫使变量更新接近其先前的解决方案，通过布雷格曼距离实现，并通常表现为每个变量的简单二次。这样做可以使原始问题呈现强凸性，从而实现精确而有效的优化。
consensus-based近端算法结合了这两个过程。通过将包含与传感器数据项相关联的变量值相关的信息以及变量之间关系对应的信息的映射划分为多个子图，减少了所要解决的各自优化问题的大小和复杂性。
另外，将每个子图分配给一个工作节点，以便每个子图在单个节点进行优化。在分散更新变量的计算时，映射的优化比在单个节点上优化更快、更有效，并且实现了可扩展性。微软指出，预计随着世界的数字化转型，代表物理世界的数字映射的尺寸将大大增加。
由于对映射进行了分区，减少了子图之间共享的变量数量，因此减少了通信量。换句话说，工作节点之间的流量减少了。对映射进行划分，以减少在子图之间共享的变量的数量，可以改善底层计算机设备的功能。
在发明示例的任何组合中，相关方法包括重复交替的步骤：在工作节点计算子图优化和使用consensus过程将共享变量更新为公共值。所述方法同时包括在工作节点的子图优化处使用可变数量的优化步骤和在consensus过程中使用可变数量的优化步骤。
允许每个局部问题和每个全局步骤的可变步数使得对每个工作节点的单个步骤进行非常灵活的处理，并显着加速优化过程。请注意，consensus问题很容易在一个步骤中精确地解决/解决，而不是“不精确地”和分成多个步骤。本地更新需要消耗计算时间和内存。consensus更新很便宜，但数据必须从本地节点接收并发送回来。
所以，微软表示他们的环境3D映射更新新方法只需低内存占用，可缩放到任意大小，并且优于现有的3D映射优化方法。3D映射的更新将考虑到环境的变化和/或考虑到以前无法获得的传感器数据。
图1A是作为云服务部署的映射更新功能118的示意图。使用分布式架构部署映射更新功能，分布式架构包括多个相互通信的工作节点和管理节点。在一个示例中，工作节点和管理节点部署在数据中心、计算节点集群或其他计算功能中。
映射更新功能通过通信网络114接收从一个或多个传感器捕获的传感器数据。映射更新功能可以访问存储在可通过通信网络114访问的位置的一个或多个3D映射107。映射更新功能118更新和/或创建一个或多个3D映射107。
3D映射107通过通信网络114可访问，例如通过全息图持久性服务120和通过导航服务122。在一个示例中，导航服务122能够向3D映射107发送查询，以查找与给定3D位置关联的图像数据，或查找与给定图像关联的3D位置。在另一个示例中，导航服务122能够下载3D映射的一个区域或整个3D映射，以便规划路线并向最终用户指示方向。
在一个示例中，全息图持久性服务120能够向3D映射107发送查询，以查找与给定3D位置关联的图像数据，或查找与给定图像关联的3D位置。全息图持久化服务使用检索到的数据在一段时间内和/或在多个增强现实头戴式计算设备持久化全息图。
在图1B中，当人100或104在房间周围移动时，捕获装置捕获描述环境的传感器数据。从这样的传感器数据，捕获设备的3D位置和方向计算和/或3D环境中landmark的3D位置使用任何传统的众所周知的追踪技术计算。
通过使用任何合适的已知技术，传感器数据用于计算捕获设备的三维位置和方向。例如，其中传感器数据包含图像，图像拟合到环境的3D模型，以便使用模型拟合过程计算捕获设备的姿态。在另一个例子中，landmark在环境的3D模型中预先指定，并使用机器训练的模型在捕获的传感器数据中检测到。当传感器数据是全球定位系统数据时，它直接提供三维位置信息。当传感器数据是IMU测量值时，它直接提供捕获设备的方向。
图3是一个3D映射的例子。所述映射包括多个landmark310的三维位置。所述映射同时包括诸如捕获装置202和206的两个捕获装置的相对轨迹。黑色实线304表示第一捕获装置的轨迹。黑色实线308表示第二捕获装置的轨迹。在每个轨迹标记的实点302、306是各自捕获装置的姿态。在轨迹304、308内和周围显示的小黑点310是待优化环境中landmark的位置。
图4是捕获装置的图像帧405的示例。在3D映射中存在关于多个landmark的知识，并且使用捕获装置的模型和关于光线、光学和物理的规则将landmark投影到图像框架405。在工作节点的束调整过程中，将landmark的预测位置与捕获设备捕获的实际图像进行比较。
束调整过程的作用是最小化在给定工作节点表示的所有捕获设备的预测landmark位置和观察到的landmark位置之间的差异。束调整过程调整三维映射中捕获设备的三维landmark位置和姿态，以最小化重投影误差。
图5是用于更新环境的3D映射的方法流程图。所述环境的3D映射包括传感器数据项，其中每个传感器数据项具有一个或多个相关变量。传感器数据项是由一个或多个捕获设备捕获的项。如本文所述，关联变量的一个示例是捕获设备的姿态。关联变量的另一个例子是landmark的位置。
在通信网络的管理节点处接收多个传感器数据项502。所述通信网络还包括多个工作节点。在通信网络的管理节点上，至少部分地基于所接收的传感器数据项计算包含节点和边的图504。图中的一个节点表示至少一个变量，一条边表示变量之间的关系。
图5的过程计算位姿图优化。姿态图的每个节点表示捕获设备的姿态，图形的边表示姿态之间的关系。姿态图优化过程的输出是三维映射，映射是捕获设备的多个姿态值。
在其他示例中，图是一个共可视性图，其中每个节点表示捕获描绘指定landmark的图像的捕获设备的姿态。在这种情况下，图5所示的过程使用束调整计算优化以产生三维映射，映射是捕获设备的多个姿态值以及多个landmark的3D位置。
在506，映射划分为多个子图，以减少子图之间共享的变量数量。由于用于计算图的传感器数据项的性质，图的分区将导致至少一个变量复制到两个或多个子图中。因此，当将映射划分为多个子图时，这可以减少在子图之间共享/复制的变量数量。有利的是，在多个子图之间存在的共享变量越少，多个子图之间的变量之间的解耦就越大。
在508，管理节点将多个子图中的每个分配给通信网络的各自工作节点。在510，在每个工作节点计算子图变量的更新值。变量的更新值是通过计算优化来计算。在512，使用consensus-based近端算法来更新子图之间共享的变量值。consensus-based近端算法寻求在整个映射计算全局优化，这样子图之间共享的变量约束为相同。
510和512的操作以交错的方式迭代，以达到全局优化的收敛。当在决策点514满足停止准则时发生收敛。使用所述变量的更新值更新所述3D映射514，例如通过将所述值存储在图1A的映射存储区107中。
微软指出，所述方法更加实用和灵活，能够适应任意尺度的环境映射，并消除了计算优化中的瓶颈。在目前的方法中，在512执行的consensus步骤是分散的，这样单个节点就不需要对子图之间共享的所有变量执行共识。这反过来又大大增加了可由通信网络处理的传感器数据量。
图6为3D映射优化示意图。在图6中，使用捕获设备602分别捕获时间为t0至t4的一系列图像630至638。图像630至638描绘了当捕获装置具有特定位置和方向时在602的图像帧中捕获的landmark。当捕获设备602在时间t0至t4移动通过不同的位置和方向时，捕获设备602所观察到的landmark的2D图像位置将发生变化。
如上所述，捕获设备的姿态和地标的3D位置可从多种方法获取。然而，在放入3D映射之前，姿势和/或3D landmark位置必须优化。在特定情况下，使用环境的初始映射640获得输入到该过程的捕获设备的landmark和姿态的3D位置，其中初始地图将根据传感器数据进行更新。
管理节点650接收传感器数据项。管理节点650还接收姿态和/或3D landmark位置。
如图5中504至508所述，管理节点650计算表示接收到的传感器数据项的映射652。映射652包括节点652a和边652b，其中节点652a表示至少一个变量，边表示变量之间的关系。为简单起见，在图6中，每个节点652a对应一个捕获设备位姿。
所述管理节点650配置为将所述映射划分为多个子图654a、654b，以减少子图之间共享的变量数量。
在姿态图的情况下，通过将每条边分配给一个工作节点来对图进行分区，以便在consensus-based近端算法的consensus步骤中最小化所需的通信量，同时保持工作节点上的负载平衡。
在共可见性图的情况下，通过将每条边分配给一个工作节点来划分图，以便在consensus-based近端算法的consensus步骤中最小化所需的通信量，同时保持工作节点上的负载平衡。除了减少通信量之外，这同时减少了耦合并提高了收敛性。
在图6中，每个子图由管理节点分配给各自的工作节点656a和656b。在每个工作节点，计算各自子图变量的更新值。
另外在每个工作节点，子图之间共享的变量值作为consensus-based近端算法的一部分更新，如上面的图5所述。consensus-based近端算法具有考虑初始图640中的变量值以及作为输入接收到图6所示过程的变量值的全局优化功能。consensus-based近端算法约束子图之间共享的变量值相同。
更新来自各自工作节点656a和656b的变量值，并将其用于更新环境的3D映射645。这是3D映射640的更新版本。
有利的是，发明描述的方法和系统使得问题能够扩展到现实世界的问题实例，并更有效地处理不断增加的数据和输出映射的大小。微软指出，所述方法进一步为现代3D映射数据的大内存需求提供了解决方案。实际上，发明所述的方法和系统能够在分布式云环境中优化和更新3D映射。
例如基于上述和图5所示的方法，即便在存在节点故障的情况下，本发明的系统都能够优化3D映射数据。如图5中区块510和512所示，共识步骤的去中心化性质和子图中变量值更新的去中心化性质分别实现了鲁棒优化，因为目前的方法和系统不依赖于单个节点来执行图的所有更新。
名为“Updating a 3d map of an environment”的微软专利申请最初在2022年5月提交，并在日前由美国专利商标局公布。
