CN108268516A - 基于八叉树的云端地图地图更新方法及设备 - Google Patents

Abstract

本发明实施例提供一种基于八叉树的云端地图地图更新方法及设备，属于计算机领域。所述云端地图更新方法包括：接收位置信息及对应于该位置信息的云点信息；根据所述位置信息，在八叉树存储结构中确定该位置所处的平面空间所构成的八叉树；以及利用所述点云信息来更新该位置所处的平面空间所构成的八叉树。通过上述技术方案，通过采用八叉树空间存储方法，可节省存储空间。另一方面，在需要进行地图更新时，可精确定位出服务器所存储的地图中需要修改的部分。

Description

基于八叉树的云端地图地图更新方法及设备

技术领域

本发明涉及计算机领域，具体地，涉及一种基于八叉树的云端地图地图更新方法及设备。

背景技术

随着自动驾驶技术的不断发展，越来越多的自动驾驶服务开始进入人们的生活圈。无人车定位是自动驾驶的关键技术之一，精确的定位对于无人驾驶的环境感知和路径规划等任务至关重要。但是在城市环境下，受遮挡的GPS信号为基于全球卫星的定位方法提出了新的挑战。另外有研究人员提出采用激光里程计或者视觉里程计的方法进行位姿估计的方法，但是复杂的交通环境，繁多的动态/静态障碍物使得这一类方法的稳定性大大降低。高精度地图的提出为无人车在城市环境下的定位方式提出了新的策略，通过局部点云(由无人车激光获取)和高精度地图进行实时匹配实现高精度的定位结果，根据Google的技术报告，采用这种定位方法的精度可以达到厘米级别。高精度地图的使用一方面可以使得无人车系统摆脱对高分辨率激光设备的依赖，另一方面也可以获得稳定有效的定位、环境感知的结果。

高精度点云地图是一种高精度分辨率的激光点云地图，往往由高精度传感器进行离线的地图融合得到。基于高精度地图信息可以实现精确的定位以及静态环境感知。本申请发明人在实现本发明的过程中发现，传统的地图存储方式一般采用存储原始点云的方法，一方面需要大量存储空间，另一方面不方便进行地图修改。

发明内容

本发明实施例的目的是提供一种基于八叉树的云端地图地图更新方法及设备，其可针对上述背景技术中所提及的一个或多个问题，给出解决方案，实现云端地图更新。

为了实现上述目的，本发明一实施例提供一种基于八叉树的云端地图更新方法，该方法包括：接收位置信息及对应于该位置信息的云点信息；根据所述位置信息，在八叉树存储结构中确定该位置所处的平面空间所构成的八叉树；以及利用所述点云信息来更新该位置所处的平面空间所构成的八叉树。

可选的，所述八叉树存储结构内存储有多个针对预设大小平面空间的八叉树。

可选的，利用所述点云信息来更新该位置所处的平面空间所构成的八叉树的步骤包括：在所述位置所处的平面空间位于一预设大小平面空间之内的情况下，利用所述点云信息来更新该预设平面空间大小所构成的八叉树；或在所述位置所处的平面空间位于多个预设大小平面空间的交叉区域之内的情况下，利用所述点云信息更新对该交叉区域所涉及的八叉树。

可选的，所述位置信息及对应于该位置信息的云点信息接收自可移动终端。

可选的，所述位置信息及对应于该位置信息的云点经由GPRS网络或Wifi网络而从所述可移动终端接收。

相应的，本发明一实施例还提供一种基于八叉树的云端地图更新设备，该设备包括：接收单元，用于接收位置信息及对应于该位置信息的云点信息；确定单元，用于根据所述位置信息，在八叉树存储结构中确定该位置所处的平面空间所构成的八叉树；以及更新单元，用于利用所述点云信息来更新该位置所处的平面空间所构成的八叉树。

可选的，所述八叉树存储结构内存储有多个针对预设大小平面空间的八叉树。

可选的，所述更新单元用于执行以下操作：在所述位置所处的平面空间位于一预设大小平面空间之内的情况下，利用所述点云信息来更新该预设平面空间大小所构成的八叉树；或在所述位置所处的平面空间位于多个预设大小平面空间的交叉区域之内的情况下，利用所述点云信息更新对该交叉区域所涉及的八叉树。

可选的，所述位置信息及对应于该位置信息的云点信息接收自可移动终端。

可选的，所述位置信息及对应于该位置信息的云点经由GPRS网络或Wifi网络而从所述可移动终端接收。

相应的，本发明一实施例提供了一种电子设备，包括：至少一个处理器；以及与所述至少一个处理器通信连接的存储器；其中，所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述至少一个处理器执行，以使所述至少一个处理器执行上述基于八叉树的云端地图更新方法。

相应的，本发明实施例提供了一种非暂态计算机可读存储介质，所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令用于使所述计算机执行上述基于八叉树的云端地图更新方法。

相应的，本发明实施例提供了一种计算机程序产品，所述计算机程序产品包括存储在非暂态计算机可读存储介质上的计算程序，所述计算机程序包括程序指令，当所述程序指令被计算机执行时，使所述计算机执行上述基于八叉树的云端地图更新方法。

通过上述技术方案，通过采用八叉树空间存储方法，可节省存储空间。另一方面，在需要进行地图更新时，可精确定位出服务器所存储的地图中需要修改的部分。

本发明实施例的其它特征和优点将在随后的具体实施方式部分予以详细说明。

附图说明

附图是用来提供对本发明实施例的进一步理解，并且构成说明书的一部分，与下面的具体实施方式一起用于解释本发明实施例，但并不构成对本发明实施例的限制。在附图中：

图1为本发明一实施例提供的云端地图更新系统的结构示意图；

图2为本发明一实施例提供的基于八叉树的云端地图更新方法的流程图；

图3为八叉树与空间划分区域的对应关系；

图4为本发明另一实施例提供的基于八叉树的云端地图更新方法的流程图；

图5为在进行基于八叉树的云端地图更新方法所涉及的平面空间示意图；

图6为在进行基于八叉树的云端地图更新方法所涉及的节点示意图；

图7为本发明一实施例提供的基于八叉树的云端地图更新设备的结构示意图；以及

图8为本发明一实施例提供的执行云端地图更新方法的电子设备的硬件结构示意图。

具体实施方式

以下结合附图对本发明实施例的具体实施方式进行详细说明。应当理解的是，此处所描述的具体实施方式仅用于说明和解释本发明实施例，并不用于限制本发明实施例。

图1为本发明一实施例提供的云端地图更新系统的结构示意图。如图1所示，该云端提供更新系统可包含可移动设备100A-100C及云端服务器200，该可移动设备100A-100C可为车辆，云端服务器200内存储有云端地图，每一车辆可向所述云端服务器200请求云端地图，进而依据该云端地图进行导航或其他操作，例如观看当前的路况信息(例如，哪条路处于堵车，哪条路畅通等等)。所述可移动设备100A-100C与云端服务器200可经由各种通信网络进行通信，诸如IEEE 802.16(即全球微波互联接入(WiMAX))、CDMA2000、CDMA2000 1x、CDMA2000EV-DO、临时标准2000(IS-2000)、临时标准95(IS-95)、临时标准856(IS-856)、全球移动通信系统(GSM)、增强型数据速率GSM演进(EDGE)、GSM EDGE(GERAN)等。

其中所述可移动设备100A-100C中的每一者可获取其自身的当前位置，例如其当前位置坐标，并将该当前位置及与该当前位置相对应的局部地图点云请求发送至所述云端服务器200，该云端服务器200可响应于该局部地图点云请求，从其存储的云端地图内获取与所述当前位置相对应的局部地图点云，并将该点云发送回所述可移动设备100A-100C，以便该可移动设备100A-100C利用该局部地图点云进行导航。本发明以下实施例所提供的云端地图更新方法可在该图1所示的云端地图更新系统的云端服务器内执行，当然，并本发明以下实施例也不仅仅限于在图1所示的云端地图更新系统的云端服务器内执行，其还可以执行于现有的离线地图更新系统的服务器内。

图2为本发明一实施例提供的基于八叉树的云端地图更新方法的流程图。如图2所示，所述基于八叉树的云端地图更新方法包括：

步骤S210，接收位置信息及对应于该位置信息的云点信息；

该位置信息例如可为经纬度信息，亦可为表征其在某一参考坐标系内的位置的其他位置信息。该位置信息可通过可移动设备内配备的GPS定位系统获取，当然其他可位置定位方式亦是可行的，可移动设备还可通过空中接口从基站接收位置信息，和/或基于从两个或更多个相邻基站接收到的信号的定时来确定其位置。需要理解的是，在与实施方式一致的同时，该可移动设备可以通过任何合适的位置确定方法来获取位置信息。

所述云点信息可由诸如摄像头、高分辨率激光设备、红外摄像仪等可感知周围环境的设备来获取，可移动设备可借助该捕获设备来感知获取其所处位置的环境信息，例如哪个方位存在障碍物、存在何种障碍物等等，并将其作为对应于该位置信息的点云信息。

步骤S220，根据所述位置信息，在八叉树存储结构中确定该位置所处的平面空间所构成的八叉树。

八叉树(octree)是一种用于描述三维空间的树状数据结构。八叉树的每个节点表示一个正方体的体积元素，每个节点有八个子节点，这八个子节点所表示的体积元素加在一起就等于父节点的体积。一般中心点作为节点的分叉中心。图3为八叉树与空间划分区域的对应关系。如图3所示，可把一空间视为一个长方体(优选为立方体)，对应八叉树的根节点；再将该长方体划分成八个一级区域，每个一级区域对应根节点的一级子节点；更进一步地，将每个一级区域再划分成八个二级区域，每个二级区域对应该一级区域所对应的一级子节点的子节点，即二级子节点……通过上述方法将空间层层划分，对应的八叉树各节点存储对应的空间划分区域的环境信息，例如该空间划分区域内是否有障碍物。最后，可根据八叉树存储结构中所存储的各个划分区域中所存储的环境信息建立空间地图。本发明实施例即为采用八叉树的数据结构对于给定空间大小的区域进行八叉树建模，一般空间的大小可选取100mx100mx3m的空间，如果以0.1m为空间的分辨率，则对应的3D栅格大小为1000x1000x30，通过基于八叉树的空间压缩方法，此空间的地图存储大小可以压缩到10mb空间大小以内。

步骤S230，利用所述点云信息来更新该位置所处的平面空间所构成的八叉树。

可利用八叉树数据存储结构对所述云点信息进行解析，并将解析结果更新至该云端服务器内之前存储的对应于所述位置的八叉树结构内。所述云端服务器内之前可存储有一对应于某一空间范围的八叉树存储结构，可将该空间范围划分为多个具有预设大小的平面空间(例如，100mx100mx3m)，该八叉树存储结构内含有针对该多个预设大小平面空间中每一预设大小平面空间的八叉树，这些八叉树相互之间存在节点交叉。

通过该实施例提供的技术方案，通过采用八叉树空间存储方法，可节省存储空间。另一方面，在需要进行地图更新时，可精确定位出服务器所存储的地图中需要修改的部分，仅对该部分所对应的八叉树进行更新即可，方便快捷。

图4为本发明另一实施例提供的基于八叉树的云端地图更新方法的流程图。如图4所示，发明另一实施例提供的基于八叉树的云端地图更新方法包括：

步骤S410，接收位置信息及对应于该位置信息的云点信息。

本步骤与前述实施例中的步骤S210的原理、实现过程及效果相同，为了简洁在此不再赘述。

步骤S420，根据所述位置信息，在八叉树存储结构中确定该位置所处的平面空间所构成的八叉树。

本步骤与前述实施例中的步骤S220的原理、实现过程及效果相同，为了简洁在此不再赘述。

步骤S430，判断所述位置所处的平面空间是位于一预设大小平面空间之内还是位于多个预设大小平面空间的交叉区域之内。在所述位置所处的空间平面是位于一预设大小平面空间之内的情况下，执行步骤S440；在所述位置所处的平面空间位于多个预设大小平面空间的交叉区域之内的情况下，执行步骤S450。

图5为在进行基于八叉树的云端地图更新方法所涉及的平面空间示意图。如图5所示，图中示出了两种灰度的区块，其中每块灰度较深的区域可代表100m*100m的平面空间所构成的八叉树，而每块灰度交浅的区域可代表上述灰度较深的区域之间的交叉区域的八叉树。对于对应于A位置的点云信息而言，仅需要对A位置所处的区域的八叉树信息进行环境建模与动态地图更新。对于对应于B位置的点云信息而言，仅需要对B位置所处的交叉区域的八叉树信息进行环境建模与动态地图更新。

步骤S440，利用所述点云信息来更新该预设平面空间大小所构成的八叉树。

步骤S450，利用所述点云信息更新对该交叉区域所涉及的八叉树。

图6为在进行基于八叉树的云端地图更新方法所涉及的节点示意图。当所接收的点云信息对应于A位置时，可根据该A位置所处的区域的八叉树进行地图建模以得到之前存储的对应于该A位置的区域的点云信息，并比对该之前存储的对应于该A位置的区域的点云信息与所接收的对应于A位置的点云信息，根据两者之间的差异来对A位置所处的区域的八叉树的子节点进行更新。当所接收的点云信息对应于B位置时，可根据该B位置所处的区域的八叉树进行地图建模以得到之前存储的对应于该B位置的区域的点云信息，并比对该之前存储的对应于该B位置的区域的点云信息与所接收的对应于B位置的点云信息，根据两者之间的差异来对B位置所处的区域的八叉树的子节点进行更新。由于B位置涉及到交叉区域，因此该更新还需对对应于该B位置的区域的八叉树的相邻子节点进行更新。藉此，可实现平滑的地图提取和地图更新。

还存在以下实施情形：当所接收的点云信息对应于A位置时，按照八叉树存储结构对所接收的对应于该A位置的点云信息进行解析以生成八叉树；之后，从八叉树存储结构寻找之前存储的对应于该A位置的区域的八叉树；将该两个八叉树进行比对，并根据两者之间的差异来对八叉树存储结构内所存储的A位置所处的区域的八叉树的子节点进行更新。当所接收的点云信息对应于B位置时，按照八叉树存储结构对所接收的对应于该B位置的点云信息进行解析以生成八叉树；之后，从八叉树存储结构寻找之前存储的对应于该B位置的交叉区域的多个八叉树；将解析得到的八叉树与该多个八叉树中的对应子节点进行比对，并根据比对结果来对八叉树存储结构内所存储的B位置所处的交叉区域的多个八叉树的子节点进行更新。

需要说明的是，上述位置信息及对应于该位置信息的云点信息可接收自图1所示实施例中的可移动终端，所述位置信息及对应于该位置信息的云点可经由GPRS网络或Wifi网络而从所述可移动终端接收。当然，本发明并不限于此，所述位置信息及对应于该位置信息的云点信息亦可接收自其他存储了该位置信息及对应于该位置信息的云点信息的设备。

图7为本发明一实施例提供的基于八叉树的云端地图更新设备的结构示意图。相应的，本发明一实施例还提供一种基于八叉树的云端地图更新设备，该设备包括：接收单元710，用于接收位置信息及对应于该位置信息的云点信息；确定单元720，用于根据所述位置信息，在八叉树存储结构中确定该位置所处的平面空间所构成的八叉树；以及更新单元730，用于利用所述点云信息来更新该位置所处的平面空间所构成的八叉树。

可选的，所述八叉树存储结构内存储有多个针对预设大小平面空间的八叉树。

可选的，所述更新单元730用于执行以下操作：在所述位置所处的平面空间位于一预设大小平面空间之内的情况下，利用所述点云信息来更新该预设平面空间大小所构成的八叉树；或在所述位置所处的平面空间位于多个预设大小平面空间的交叉区域之内的情况下，利用所述点云信息更新对该交叉区域所涉及的八叉树。

可选的，所述位置信息及对应于该位置信息的云点信息接收自可移动终端。

可选的，所述位置信息及对应于该位置信息的云点经由GPRS网络或Wifi网络而从所述可移动终端接收。

关于上述实施例中的基于八叉树的云端地图更新设备，其中各个模块执行操作的具体方式已经在有关该方法的实施例中进行了详细描述，此处将不做详细阐述说明。

图8是本发明实施例提供的执行云端地图更新方法的电子设备的硬件结构示意图，如图8所示，该设备包括一个或多个处理器810以及存储器820，图8中以一个处理器810为例。

执行云端地图更新方法的电子设备还可以包括：输入装置830和输出装置840。

处理器810、存储器820、输入装置830和输出装置840可以通过总线或者其他方式连接，图8中以通过总线连接为例。

处理器810可以为中央处理器(Central Processing Unit，CPU)。处理器810还可以为其他通用处理器、数字信号处理器(Digital Signal Processor，DSP)、专用集成电路(Application Specific Integrated Circuit，ASIC)、现场可编程门阵列(Field-Programmable Gate Array，FPGA)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件等芯片，或者上述各类芯片的组合。通用处理器可以是微处理器或者该处理器也可以是任何常规的处理器等。

存储器820作为一种非暂态计算机可读存储介质，可用于存储非暂态软件程序、非暂态计算机可执行程序以及模块，如本申请实施例中的可移动设备的环境感知建模方法对应的程序指令/模块(例如，附图7所示的接收单元710、确定单元720以及更新单元730)。处理器810通过运行存储在存储器820中的非暂态软件程序、指令以及模块，从而执行服务器的各种功能应用以及数据处理，即实现上述方法实施例可移动设备的环境感知建模方法。

存储器820可以包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能所需要的应用程序；存储数据区可存储根据可移动设备的环境感知建模装置的使用所创建的数据等。此外，存储器820可以包括高速随机存取存储器，还可以包括非暂态存储器，例如至少一个磁盘存储器件、闪存器件、或其他非暂态固态存储器件。在一些实施例中，存储器820可选包括相对于处理器810远程设置的存储器，这些远程存储器可以通过网络连接至可移动设备的环境感知建模装置。上述网络的实例包括但不限于互联网、企业内部网、局域网、移动通信网及其组合。

输入装置830可接收输入的数字或字符信息，以及产生与基于八叉树的云端地图更新设备的用户设置以及功能控制有关的键信号输入。输出装置840可包括显示屏等显示设备。

所述一个或者多个模块存储在所述存储器820中，当被所述一个或者多个处理器810执行时，执行如图2及4所示的方法。

上述产品可执行本发明实施例所提供的方法，具备执行方法相应的功能模块和有益效果，未在本实施例中详尽描述的技术细节，具体可参见如图2及4所示的实施例中的相关描述。

本发明实施例还提供了一种非暂态计算机存储介质，所述计算机存储介质存储有计算机可执行指令，该计算机可执行指令可执行上述任意方法实施例中的可移动设备的环境感知建模方法。其中，所述存储介质可为磁碟、光盘、只读存储记忆体(Read-OnlyMemory，ROM)、随机存储记忆体(Random Access Memory，RAM)、快闪存储器(FlashMemory)、硬盘(Hard Disk Drive，缩写：HDD)或固态硬盘(Solid-State Drive，SSD)等；所述存储介质还可以包括上述种类的存储器的组合。

本领域技术人员可以理解，实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的程序可存储于一计算机可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。其中，所述的存储介质可为磁碟、光盘、只读存储记忆体(ROM)或随机存储记忆体(RAM)等。

虽然结合附图描述了本发明的实施例，但是本领域技术人员可以在不脱离本发明的精神和范围的情况下作出各种修改和变型，这样的修改和变型均落入由所附权利要求所限定的范围之内。

Claims (10)

1.一种基于八叉树的云端地图更新方法，其特征在于，该方法包括：

接收位置信息及对应于该位置信息的云点信息；

根据所述位置信息，在八叉树存储结构中确定该位置所处的平面空间所构成的八叉树；以及

利用所述点云信息来更新该位置所处的平面空间所构成的八叉树。

2.根据权利要求1所述的云端地图更新方法，其特征在于，所述八叉树存储结构内存储有多个针对预设大小平面空间的八叉树。

3.根据权利要求2所述的云端地图更新方法，其特征在于，利用所述点云信息来更新该位置所处的平面空间所构成的八叉树的步骤包括：

在所述位置所处的平面空间位于一预设大小平面空间之内的情况下，利用所述点云信息来更新该预设平面空间大小所构成的八叉树；或

在所述位置所处的平面空间位于多个预设大小平面空间的交叉区域之内的情况下，利用所述点云信息更新对该交叉区域所涉及的八叉树。

4.根据权利要求1所述的云端地图更新方法，其特征在于，所述位置信息及对应于该位置信息的云点信息接收自可移动终端。

5.根据权利要求4所述的云端地图更新方法，其特征在于，所述位置信息及对应于该位置信息的云点经由GPRS网络或Wifi网络而从所述可移动终端接收。

6.一种基于八叉树的云端地图更新设备，其特征在于，该设备包括：

接收单元，用于接收位置信息及对应于该位置信息的云点信息；

确定单元，用于根据所述位置信息，在八叉树存储结构中确定该位置所处的平面空间所构成的八叉树；以及

更新单元，用于利用所述点云信息来更新该位置所处的平面空间所构成的八叉树。

7.根据权利要求6所述的云端地图更新设备，其特征在于，所述八叉树存储结构内存储有多个针对预设大小平面空间的八叉树。

8.根据权利要求7所述的云端地图更新设备，其特征在于，所述更新单元用于执行以下操作：

在所述位置所处的平面空间位于一预设大小平面空间之内的情况下，利用所述点云信息来更新该预设平面空间大小所构成的八叉树；或

在所述位置所处的平面空间位于多个预设大小平面空间的交叉区域之内的情况下，利用所述点云信息更新对该交叉区域所涉及的八叉树。

9.根据权利要求6所述的云端地图更新设备，其特征在于，所述位置信息及对应于该位置信息的云点信息接收自可移动终端。

10.一种电子设备，其特征在于，包括：

至少一个处理器；以及

与所述至少一个处理器通信连接的存储器；其中，所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述至少一个处理器执行，以使所述至少一个处理器执行权利要求1-5中任一项所述的基于八叉树的云端地图更新方法。