本发明涉及机器人室内地图建立技术领域，尤其设计一种提高存储效率的机器人室内地图及其生成方法。
背景技术：
近年来，随着科学技术的不断发展和进步，随着现代人们的工作和生活信息化水平不断的提高,各种室内导航机器人也相继的出现,为了人们的日常生活学习工作提供便利。
机器人在室内环境中的导航技术是当前机器人研究领域的热点问题，研究人员需要对室内地图构建，机器人定位以及机器人导航算法进行研究。机器人在室内环境中的定位与导航都依赖于环境地图，因此精确地地图表示和高效的地图创建方法成为机器人室内导航的关键技术。常用的机器人室内地图表示方法有几何表示地图，特征地图，概率占用栅格地图和拓扑地图。
栅格地图是机器人室内导航领域的最流行的地图模型之一，该地图模型将概率引入到栅格地图表示中。栅格地图可由占用概率地图生成，占用概率地图每一个网格都存储一个该处被物体占用的概率值。概率占用地图的表示方式与灰度图像的表示方式十分类似，故而栅格地图的构建算法通常将占用概率值输出为图像灰度值。栅格地图的图像中接近白色的部分表示该区域为自由区域；灰色部分表示该区域为未知区域，即区域没有被传感器观测到；接近黑色的部分表示该区域为占用区域，即该区域有障碍物。
栅格地图存在一些问题，主要体现在两个方面：编码冗余，栅格地图为8比特灰度图像，可以表示256个灰度级，然而用于导航的地图中只需要3个灰度级，分别代表该区域为自由区域，占用区域和未知区域；空间冗余，栅格地图中，自由区域和未知区域通常大片的出现，也就是说这些区域的像素点是空间相关的，在相关的像素表示中，信息被没有必要的重复了。
技术实现要素：
针对机器人室内地图构建技术，本发明提出一种提高存储效率的机器人室内地图生成方法，以解决现有概率占用栅格地图的编码冗余与空间冗余问题，提高机器人室内地图存储效率。
本发明提出了一种提高存储效率的机器人室内地图，其特征在于，该地图由三种带有数值的节点表示地图信息，每个节点代表一个实际空间区域，每个带有数值的节点占用两个存储空间，一个用来存储区域类型，另一个用来存储像素数；存储区域类型的空间中的数据通过霍夫曼编码得到，存储像素数的空间中的数据通过行程编码得到。
为生成该地图，本发明公开了一种提高存储效率的机器人室内地图生成方法，包括：
a、使用控制器操控机器人在未知的室内环境中移动，里程计数据对机器人定位，激光雷达传感器提供环境观测数据，从而更新占用概率地图；
b、将占用概率地图转化为栅格地图，再得到简化的栅格地图；
c、利用简化栅格地图生成一种高存储效率的机器人室内地图。
进一步的，所述a包括：
a1、机器人在未知室内环境中建立占用概率地图的问题表示为：
p(x1:t,m|z1:t,u1:t)
其中m表示环境地图的所有路标的集合；z1:t为机器人在1至t时刻内的观察数据，第k时刻机器人的观察数据为zk；u1:t为机器人在1至t时刻接受到的控制指令；x1:t为机器人室内的位姿，采用同时定位与地图构建算法解决未知环境下建立占用概率地图的问题；
a2、控制器提供控制指令u1:t，里程计数据提供机器人室内的位姿x1:t；
a3、激光雷达传感器提供环境观测数据zk，观测数据表示成：
其中
a4、占用概率地图是栅格地图的概率表示形式，每个栅格中的概率值为0～1，每个栅格被占用的概率的计算公式为：
式中belt(mi)表示t时刻第mi个区域被占用的概率，lt(mi)为该概率对应的对数值，l0(mi)为初始值，lt-1(mi)是上一时刻belt-1(mi)对应的对数值，p(mi|zt)为反演观测概率，利用a3中的激光雷达数据计算反演观测概率。
进一步的，所述b包括：
b1、将占用概率地图转化为栅格地图，像素点灰度值v(mi)与节点概率值p(mi)之间的转
化关系为：
b2、再用栅格地图生成简化栅格地图，其步骤为：
对灰度级设置阀门，设置下限阀门为vmin，上限阀门为vmax，低于下限阀门的灰度转化为0，，高于上限阀门的灰度转化为255，介于两阀门之间的灰度转化为205，用公式表示为：
v(mi)＝(v(mi)≤vmin)？0:((v(mi)≥vmax)？255:205)
如此将栅格地图转化为了只有三种灰度级的简化栅格地图。
进一步的，所述c包括：
c1、统计简化栅格地图图像中各个灰度值的像素数量，通过像素数量计算归一化概率即每个灰度值出现的概率值；
c2、根据概率从大到小的顺序，将像素灰度值排序，按照霍夫曼编码流程对每个像素进行编码；将原灰度值与对应简化编码值之间的形成查找表；
c3、根据查找表对整个图像中的每个像素进行霍夫曼编码；
c4、对霍夫曼编码后的图像的每一行，按照像素的行程进行行程编码，即得本发明所述的一种高存储效率的机器人室内地图。
本发明的有益效果为：
一、本发明提出一种高存储效率的机器人室内地图，霍夫曼编码有效改善编码冗余问题，行程编码有效改善空间冗余问题，融合两种编码的一种高存储效率的机器人室内地图有效地提高了机器人室内地图的存储效率。
二、霍夫曼编码和行程编码都是无损编码，所以通过霍夫曼编码和行程编码，可以将栅格地图无损的转化为本发明提出的一种高存储效率的机器人室内地图，所以该方法对栅格地图的信息保存的很完整。
三、本发明将本发明缇欧出的一种高存储效率的机器人室内地图与slam算法相结合，完整的描述了机器人在未知环境中生成一种高存储效率的机器人室内地图的过程，有利于技术工作。
四、由于存储效率的提高，本发明适用于较大场景下的机器人室内地图建立领域，具有一定的普适性。
附图说明
图1为本发明实施例的一种高存储效率的机器人室内地图生成方法原理图；
图2为本发明实施例的slam问题的模型图；
图3为本发明实施例的占用概率地图更新算法流程图；
图4为本发明的机器人室内里程计运动模型图；
图5为本发明实施例的一个简化栅格地图的示例图；
图6为本发明实施例的对像素灰度进行霍夫曼编码形成查找表的示意图；
图7为本发明实施例的一种数据结构示意图；
图8为本发明实施例的一个室内仿真实验环境图；
图9为本发明实施例仿真的机器人turtlebot3burger；
图10为本发明实施例在实验过程中使用基于粒子滤波的slam算法进行地图构建过程的示意图；
图11本发明实施例通过实验得到的简化栅格地图。
具体实施方式
下面结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅是本发明一部分实施例，而不是全部的实施例。基于本发明的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实例，都属于本发明的保护范围。
实施例一
图1为本发明实施例提供的一种提高存储效率的机器人室内地图生成方法。
如图1所示，该方法主要包括如下步骤：
a、使用控制器操控机器人在未知的室内环境中移动，里程计数据对机器人定位，激光雷达传感器提供环境观测数据，利用数据更新占用概率地图。
b、将占用概率地图转化为栅格地图，再得到简化的栅格地图。
c、利用简化栅格地图生成一种高存储效率的机器人室内地图。
步骤a实际上是机器人在未知环境中进行同时定位与地图创建(slam)。为了便于理解本发明，下面对步骤a做出详细说明。
1、slam模型建立。
slam问题的建模如图2所示，图中三角形代表的机器人在环境中移动，在不同位置收集传感器数据，然后根据这些数据融合出完整的地图模型。从概率学的观点，可以将图2中的slam问题表示为：
p(x1:t,m|z1:t,u1:t)
m＝{m1,m2,...,mn}
u1:t＝{u1,u2,...,ut}
z1:t＝{z1,z2,...,zt}
其中m表示环境地图的所有路标的集合；z1:t为机器人在1至t时刻内的观察数据，第k时刻机器人的观察数据为zk；u1:t为机器人在1至t时刻接受到的控制指令；x1:t为机器人的位姿。
2、用基于粒子滤波的slam算法解决1中slam问题。
本实施例中采用的slam算法为基于粒子滤波的slam算法，多次试验表明该算法有效的契合本发明提出的一种高存储效率的机器人室内地图。基于粒子滤波的slam算法的核心思想是：在已知每一时刻机器人位姿的条件下，机器人路径与地图环境无关，对于每一个粒子，单个地图的误差是条件独立的。因此，地图构建问题可以分解为很多单独的问题，地图中的每个特征对应一个问题，那么地图构建问题将表示为：
式中，该算法使用粒子滤波器计算机器人路径的后验概率p(x1:t|z1:t,u1:t)，使用单独的位置后验概率p(mi|x1:t,z1:t)表示地图中的每个特征，即每个路标点i(i＝1,2,...,n)，使用这种因式分解的方式将地图构建问题可以分解为路径和地图的n 1个后验概率的乘积。
3、占用概率地图更新流程。
本实施采用的占用概率地图更新算法流程如图3所示，其中粒子滤波算法用于将slam问题分解。
1)首先初始化机器人在室内的位姿(x0,y0,θ0)t，其中x和y表示机器人的坐标，θ表示机器人的方位角也即机器人的朝向，这三个变量组成机器人的位姿数据x1:t。
2)利用控制器手动操控机器人在未知的室内环境中移动，控制器提供控制指令u1:t。
3)里程计数据提供机器人在室内的位姿x1:t，里程计是机器人在室内进行定位的一种常用方式。设机器人移动前的位姿为(xk,yk,θk)t，移动后的为(xk 1,yk 1,θk 1)t，则一次机器人室内的运动可以描述为如图4所示的模型。设机器人在时刻te内的平移速度为vk，旋转速度为ωk，那么利用上一时刻机器人位姿计算下一时刻机器人位姿公式为：
4)激光雷达传感器提供环境观测数据kk，观测数据可以表示成：
其中
5)占用概率地图是栅格地图的概率表示形式，每个栅格中的概率值为0～1，所以不能直接用图像表示，每个栅格被占用的概率的计算公式为：
式中belt(mi)表示t时刻第mi个区域被占用的概率，lt(mi)为该概率对应的对数值，l0(mi)为初始值，lt-1(mi)是上一时刻belt-1(mi)对应的对数值，p(mi|zt)为反演观测概率，p(mi|zt)为反演观测概率，利用激光雷达数据计算反演观测概率。
步骤b将占用概率地图转化为栅格地图，再得到简化的栅格地图。为了便于理解本发明，下面对步骤b做出详细说明。
1、将占用概率地图转化为栅格地图
占用概率地图中每个节点存储0～1的概率值，而栅格地图中每个像素存储0～255的灰度值，像素点灰度值v(mi)与节点概率值p(mi)之间的转化关系为：
2、利用栅格地图生成简化栅格地图，
由于概率值的分散性以及随机噪声，导致转化后的栅格地图图像灰度值可能分布在0～255这256个灰度级上，而所需栅格地图只需三个灰度级表示区域占用、自由或未知。因此需要对灰度级设置阀门，设置下限阀门为vmin，上限阀门为vmax，低于下限阀门的灰度转化为0，即表示占用区域的黑色像素值，高于上限阀门的灰度转化为255即表示空闲区域的白色像素值，介于两阀门之间的灰度转化为205即表示位置区域的灰色像素值，用公式表示为：
v(mi)＝(v(mi)≤vmin)？0:((v(mi)≥vmax)？255:205)
如此将栅格地图转化为了只有三种灰度级的简化栅格地图，一个简化栅格地图的示例如图5所示。
步骤c利用简化栅格地图生成一种高存储效率的机器人室内地图。为了便于理解本发明，结合图5对步骤c做出详细说明。
1、统计图5图像中各个灰度值的像素数量，通过像素数量计算归一化概率即每个灰度值出现的概率值，统计数据如下表：
2、将上表根据概率从大到小的顺序，将像素灰度值排序，按照霍夫曼编码流程对每个像素进行编码，即将具有最小概率的两个符号合并为一个符号，从何递归简化信息源，过程如图6所示，最底部的两个概率0.19和0.4被合成新的概率0.59，较大概率赋值为1，则0.59对应灰度值编码为1，0.41对应灰度值编码为0，在将0.59分解为概率0.4和0.19，那么0.4对应灰度值编码为11，0.19对应灰度值编码为10。从而得到原灰度值与对应简化编码值之间的查找表。
3、根据查找表对整个图像中的每个像素进行霍夫曼编码。即将图6中所有的灰度值转化为对应的二进制霍夫曼编码值,255编码为0,205编码为11,0编码为10。
4、对霍夫曼编码后的图像的每一行，按照像素的行程进行行程编码，即得本发明所述的一种高存储效率的机器人室内地图。该种高存储效率的机器人室内地图的一个例子如图7所示。图中只取了图5中的几行像素，其中圆圈节点表示未知区域，空心正方形节点表示自由区域，实心正方形节点表示被占用区域，图形节点中的数字代表像素数，因此每个图形代表的节点占用两个存储空间，一个用来存储区域类型，另一个用来存储像素数。原本图像中存储一行像素点需要62个存储空间，而使用霍夫曼编码和行程编码后，一行数据最少只需要两个存储空间，存储效率大大提升。
本实施例的实验结果及分析如下：
1、首先计算原地图、霍夫曼编码之后和本发明提出的一种高存储效率的机器人室内地图所需的比特数量。原来简化栅格地图即图5的比特数为：
62×70×8＝34720bit
霍夫曼编码后的比特数为：
1761×1 1754×2 825×2＝6919bit
霍夫曼编码和行程编码后比特数即本发明提出的一种高存储效率的机器人室内地图所需的比特数量：
∑(每一行数据行程编码比特数)＝1996bit
2、计算可知本发明提出的一种高存储效率的机器人室内地图相对于简化栅格地图压缩的压缩率为：
压缩率＝34720÷1996＝17.3948
分析可知本实施例中本发明提出的方法有效地提高了机器人室内地图的存储效率。
实施例二
本实施例设计了基于ros机器人软件平台和gazebo仿真软件的仿真实验。
1、搭建室内仿真实验环境如图8所示，其大小为8m*14m，用来模拟一个普通的室内家庭环境，其中摆放了一些常用的家具，比如床、沙发、柜子、椅子等。
2、使用仿真机器人turtlebot3burger(如图9所示)进行地图构建，用虚拟遥控控制机器的运动，让其遍历整个室内环境，并收集激光雷达传感器的数据，使用基于粒子滤波的slam算法进行地图构建，该过程的示意图如图10所示。
3、将2中得到的地图进行处理，得到简化的栅格地图如图11所示。
4、将简化的栅格地图进行霍夫曼编码和行程编码，得到本发明提出的一种高存储效率的机器人室内地图。
简化栅格地图需要存储空间为255*158*8＝322320bit，转化为本发明提出的一种高存储效率的机器人室内地图后，所需存储空间仅为18639bit，将简化栅格地图压缩了17.3倍，减少内存消耗94.2％。本实施例充分说明了本发明提出的一种高存储效率的机器人室内地图生成方法建图效果良好，本发明提出的一种高存储效率的机器人室内地图有着高效存储性能。
本文中所描述的具体实施例仅是对本发明精神作举例说明。本发明所属技术领域的技术人员可以对所描述的具体实施例做各种各样的修改或补充或采用类似的方式替代，但并不会偏离本发明的精神或者超越所附权利要求书所定义的范围。
