CN111323037B - 一种移动机器人新型骨架提取的Voronoi路径规划算法 - Google Patents
一种移动机器人新型骨架提取的Voronoi路径规划算法 Download PDFInfo
- Publication number
- CN111323037B CN111323037B CN202010131142.7A CN202010131142A CN111323037B CN 111323037 B CN111323037 B CN 111323037B CN 202010131142 A CN202010131142 A CN 202010131142A CN 111323037 B CN111323037 B CN 111323037B
- Authority
- CN
- China
- Prior art keywords
- path
- map
- voronoi
- point
- pixel
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Classifications
-
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
- G01C21/34—Route searching; Route guidance
- G01C21/3446—Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
Landscapes
- Engineering & Computer Science (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Automation & Control Theory (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
- Numerical Control (AREA)
- Manipulator (AREA)
- Feedback Control In General (AREA)
Abstract
本发明提供一种移动机器人新型骨架提取的Voronoi路径规划算法,包括如下步骤:步骤一、首先对移动机器人已知先验信息的三色栅格地图进行二值化处理,在对其进行腐蚀、膨胀处理;步骤二、对处理后的二值地图经进行骨架提取,得到Voronoi图;步骤三、用原始的三色地图进行机器人定位,在骨架地图上进行全局路径搜索,对得到的全局路径进行改进的三次样条平滑处理,得到优化后的全局路径。根据本发明提出的算法提取出来的Voronoi骨架没有大量毛边,整体的路径规划更加高效。同时对最后搜索出来的路径进行改进的三次差值优化,去除了路径上尖点,使最终优化的路径更为平滑,使机器人进行更加高效的移动。
Description
技术领域
本发明属于移动机器人技术领域,特别涉及一种移动机器人的全局路径规划算法。
背景技术
移动机器人技术近年来得到快速发展,它在物流仓储、智能巡检、智能家居、商场导购等诸多领域得到了广泛的应用,同时吸引越来越多的学者进行深入研究。路径规划是影响移动机器人性能最为关键的因素之一。路径规划的目的是在已知的机器人环境地图中规划出一条从机器人当前位置到达目标地点的最优路径。机器人的移动效率直接取决于路径规划的质量。
移动机器人路劲规划一般分为全局路径规划和局部路径规划,其中常用的全局路径规划算法有A*、Dijkstra、Voronoi图算法。其中A*更适合于解决单个目标问题;Dijkstra为广度优先算法,在时间、空间复杂度高,这会导致路径规划计算成本大;传统Voronoi图算法进行骨架提取后生成的路径过于冗余。
其中移动机器人的全局路径规划算法大都是基于栅格地图进行计算的,但是栅格地图存在无法同时满足精度和实时性的要求。因为当栅格划分较精确时,网格数量快速增加,这将导致机器人计算量加大、实时性降低而决策迟钝;当栅格划分粗糙时,每个栅格面积较大,这使机器的导航精度大大降低。
发明内容
本发明针对现有移动机器人全局路径规划方法存在的上述问题,提供了一种移动机器人新型骨架提取的Voronoi路径规划算法,该算法提取的骨架精简,规划的路径平滑,该算法在保证了路径规划的实时性的同时也保证了路径的精度。
本发明为解决现有技术中存在的问题采用的技术方案如下:
一种移动机器人新型骨架提取的Voronoi路径规划算法,其特征在于,包括如下步骤:
步骤一、首先对移动机器人已知先验信息的三色栅格地图进行二值化处理,在对其进行腐蚀、膨胀处理;
步骤二、对处理后的二值地图经进行骨架提取,得到Voronoi图;
步骤三、用原始的三色地图进行机器人定位,在骨架地图上进行全局路径搜索,对得到的全局路径进行改进的三次样条平滑处理,得到优化后的全局路径。
所述步骤一中,机器人首先获得的黑白灰三色栅格地图每个像素值设为S(x,y),二值化处理后的像素值为D(x,y),其中(x,y)代表的是像素点的坐标,二值化运算过程为:
得到只有黑白两色地图,再进行腐蚀、膨胀处理。
所述步骤二包括如下两步:
步骤2.1、首先使用八邻域标记图像上的每一个像素点,设某一像素点为P1,其相邻的8个点分别标记为P2~P9,黑色像素值为0,白色像素值为1;
步骤2.2、进而设P1的八邻域P2~P9像素值从0到1的变化次数为N,P1点的八邻域之和为M(PX),将满足以下四个条件的像素点的值设置为0:
条件1、P1的八邻域之和满足:2≤P2+P3+P4+P5+P6+P7+P8+P9≤6;
条件2、P1的八邻域像素值的变化次数N=1;
条件3、三个像素值的积P2·P4·P8=0或M(P2)≠1;
条件4、三个像素值的积P2·P4·P6=0或M(P4)≠1;
重复进行步骤2.1、步骤2.2两步,最终生成Voronoi骨架图。
所述步骤三先通过原始的三色地图对机器人进行定位,得到目标点后,在提取的骨架图中搜索出最优路径;
对得到的最优路径进行改进的三次样条处理过程如下:
步骤3.1、先将最优路径的像素点坐标排列成点集B1、B2、B3...Bn;
步骤3.2、取优化窗口m(m为大于2小于n的正整数),将路径点集以m为单位截取为多组数据B1~Bm~B2m~Bn,计算每组数据始末的直线方程L,其中L:Ax+By+C=0(4);
步骤3.3、取距离阈值为Dd,依次计算每组数据中间m–2个点到直线L的距离为D,若最大值Dm>Dd时,去除中间m–2个点集,连接始末两点,去除路径中的尖点,并计算出该直线上所有像素点坐标作为新的路径点集,反之则不作处理,其中
步骤3.4、在对经过上述过程处理后的点集进行三次样条插值处理,设点集起点为(x0,y0),最后点为(xn,yn),计算步长hi,带入三次差值的矩阵方程求解,得到曲线方程;其中,步长hi=xi+1+xi(i=0,1,...,n-1)(6),在每个子区间xi≤x≤xi+1中,创建的方程为gi(x)=ai+bi(x-xi)+ci(x-xi)2+di(x-xi)3(7)。
本发明具有如下优点:
本发明提出的算法没有直接在传统栅格地图上进行路径规划,避免了传统栅格地图无法同时满足精度与实时性的缺点,该方法对骨架提取方法进行改进,提取出来的Voronoi骨架没有大量毛边,因此所生成的路径不会出现过于臃肿的情况,整体的路径规划更加高效。同时本发明对最后搜索出来的路径进行改进的三次差值优化,去除了路径上尖点,使最终优化的路径更为平滑,使机器人进行更加高效的移动。
附图说明
图1为本发明算法整体流程图;
图2为机器人三色环境地图;
图3为处理后的二值地图;
图4为腐蚀、膨胀示意图;
图5为二值地图进行腐蚀处理后得到的地图;
图6为二值地图进行膨胀处理后得到的地图;
图7为像素点八邻域标记图;
图8为提取的Voronoi骨架图;
图9为路径搜索三个过程;
图10为路径平滑的优化窗口;
图11为平滑前的路径;
图12为平滑后的路径。
具体实施方式
下面通过实施例,并结合附图,对本发明的技术方案作进一步具体的说明,如图1所示,为本发明路径规划算法的主要流程图,本发明提出了一种移动机器人新型骨架提取的Voronoi路径规划算法,该算法主要的步骤包括以下三步:
步骤一、首先对移动机器人已知先验信息的三色栅格地图进行二值化处理,在对其进行腐蚀、膨胀处理;
具体来说,步骤一中的过程主要包含以下步骤:首先已知机器人的三色环境地图,如图2所示,它是由黑白灰三色构成的,黑、白像素对应的值分别为255、0,灰色像素对应的值大于0小于255,设地图中每个像素值为S(x,y),二值化处理后的像素值为D(x,y),其中(x,y)代表的是像素点的坐标。二值化运算过程为:每个像素经过二值化处理得到的新地图,如图3所示。
腐蚀、膨胀过程的图形示意图,如图4所示,M-N为腐蚀过程,M+N为膨胀过程,对二值地图进行腐蚀、膨胀过程后的地图,如图5和图6所示。
步骤二、对处理后的二值地图经进行骨架提取,得到Voronoi图;
具体来说,步骤二包括以下过程:首先使用八邻域标记图像上的每一个像素点,设某一像素点为P1,其相邻的8个点分别标记为P2~P9,黑色像素值为0,白色像素值为1,如图7所示。
对经过步骤一处理后的图片进行骨架提取,设P1的八邻域P2~P9像素值从0到1的变化次数为N,P1点的八邻域之和为M(PX),将满足以下四个条件像素点的值设置为0:
条件1、P1的八邻域之和满足:2≤P2+P3+P4+P5+P6+P7+P8+P9≤6;
条件2、P1的八邻域像素值的变化次数N=1;
条件3、三个像素值的积P2·P4·P8=0或M(P2)≠1;
条件4、三个像素值的积P2·P4·P6=0或M(P4)≠1;
对二值地图的所有像素进行上述步骤,最终得到Voronoi骨架图,如图8所示。
步骤三、用原始的三色地图进行机器人定位,在骨架地图上进行全局路径搜索,对得到的全局路径进行改进的三次样条平滑处理,得到优化后的全局路径。
具体来说,步骤三的过程包括:先通过原始的三色地图对机器人进行定位,得到目标点后,在提取的骨架图中搜索出最优路径,路径的搜索分为三个部分,第一部分为起始点到骨架图的路径,第二部分为目标点到骨架图的路径,第三部分为起始点与目标点之间的骨架部分,如图9所示;
对得到的最优路径进行改进的三次样条处理:
先将最优路径的像素点坐标排列成点集B1、B2、B3...Bn;取优化窗口m(m为大于2小于n的正整数),路径平滑的优化窗口,如图10所示。将路径点集以m为单位截取为多组数据B1~Bm~B2m~Bn,计算每组数据始末的直线方程L:Ax+By+C=0,取距离阈值为Dd,依次计算每组数据中间m–2个点到直线L的距离为D,若最大值Dm>Dd时,去除中间m–2个点集,连接始末两点,去除路径中的尖点,计算该直线上所有像素点坐标作为新的路径点集,反之则不作处理,其中,
最后将处理过的路径进行三次样条差值处理,生成的平滑路径,处理前原始路径如图11所示,处理后路径如图12所示。
经过多次实验证明了移动机器人采用本发明所提出的路径规划算法,能进行更加高效的路径规划,该算法同时满足路径规划的精度与实时性,规划出来的路径精简且准确,最终得到的路径平滑,移动机器人能进行更加高效的移动。
本发明提出了新型骨架提取的路径规划算法,在对栅格地图进行处理后提取骨架,在此基础上搜索路径更加快捷,再对路径进行改进的三次样条插值处理,最终得到更加精简、平滑的路径。机器人依据这样的路径可以进行更快速、准确、高效的移动。
本发明的保护范围并不限于上述的实施例,显然,本领域的技术人员可以对本发明进行各种改动和变形而不脱离本发明的范围和精神。倘若这些改动和变形属于本发明权利要求及其等同技术的范围内,则本发明的意图也包含这些改动和变形在内。
Claims (5)
1.一种移动机器人新型骨架提取的Voronoi路径规划算法,其特征在于,包括如下步骤:
步骤一、首先对移动机器人已知先验信息的三色栅格地图进行二值化处理,在对其进行腐蚀、膨胀处理;
步骤二、对处理后的二值地图经进行骨架提取,得到Voronoi图;
步骤三、用原始的三色地图进行机器人定位,在骨架地图上进行全局路径搜索,对得到的全局路径进行改进的三次样条平滑处理,得到优化后的全局路径;
所述步骤三先通过原始的三色地图对机器人进行定位,得到目标点后,在提取的骨架图中搜索出最优路径;对得到的最优路径进行改进的三次样条处理过程如下:
步骤3.1、先将最优路径的像素点坐标排列成点集B1、B2、B3...Bn;
步骤3.2、取优化窗口m,m为大于2小于n的正整数,将路径点集以m为单位截取为多组数据B1~Bm~B2m~Bn,计算每组数据始末的直线方程L,其中L:Ax+By+C=0 (4);
步骤3.3、取距离阈值为Dd,依次计算每组数据中间m–2个点到直线L的距离为D,若最大值Dm>Dd时,去除中间m–2个点集,连接始末两点,去除路径中的尖点,并计算出该直线上所有像素点坐标作为新的路径点集,反之则不作处理,其中
步骤3.4、在对经过上述过程处理后的点集进行三次样条插值处理,设点集起点为(x0,y0),最后点为(xn,yn),计算步长hi,带入三次差值的矩阵方程求解,得到曲线方程;其中,步长hi=xi+1+xi(i=0,1,...,n-1) (6),
在每个子区间xi≤x≤xi+1中,创建的方程为:
gi(x)=ai+bi(x-xi)+ci(x-xi)2+di(x-xi)3 (7)。
5.如权利要求1所述的一种移动机器人新型骨架提取的Voronoi路径规划算法,其特征在于,所述步骤二包括如下两步:
步骤2.1、首先使用八邻域标记图像上的每一个像素点,设某一像素点为P1,其相邻的8个点分别标记为P2~P9,黑色像素值为0,白色像素值为1;
步骤2.2、进而设P1的八邻域P2~P9像素值从0到1的变化次数为N,P1点的八邻域之和为M(PX),将满足以下四个条件的像素点的值设置为0:
条件1、P1的八邻域之和满足:2≤P2+P3+P4+P5+P6+P7+P8+P9≤6;
条件2、P1的八邻域像素值的变化次数N=1;
条件3、三个像素值的积P2·P4·P8=0或M(P2)≠1;
条件4、三个像素值的积P2·P4·P6=0或M(P4)≠1;
重复进行步骤2.1、步骤2.2两步,最终生成Voronoi骨架图。
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN202010131142.7A CN111323037B (zh) | 2020-02-28 | 2020-02-28 | 一种移动机器人新型骨架提取的Voronoi路径规划算法 |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN202010131142.7A CN111323037B (zh) | 2020-02-28 | 2020-02-28 | 一种移动机器人新型骨架提取的Voronoi路径规划算法 |
Publications (2)
Publication Number | Publication Date |
---|---|
CN111323037A CN111323037A (zh) | 2020-06-23 |
CN111323037B true CN111323037B (zh) | 2022-07-05 |
Family
ID=71163586
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
CN202010131142.7A Active CN111323037B (zh) | 2020-02-28 | 2020-02-28 | 一种移动机器人新型骨架提取的Voronoi路径规划算法 |
Country Status (1)
Country | Link |
---|---|
CN (1) | CN111323037B (zh) |
Families Citing this family (8)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN112344941B (zh) * | 2020-11-06 | 2022-04-26 | 杭州国辰机器人科技有限公司 | 路径规划方法、系统、机器人及存储介质 |
CN113189988B (zh) * | 2021-04-21 | 2022-04-15 | 合肥工业大学 | 一种基于Harris算法与RRT算法复合的自主路径规划方法 |
CN113238554A (zh) * | 2021-05-08 | 2021-08-10 | 武汉科技大学 | 一种基于激光与视觉融合slam技术的室内导航方法及系统 |
CN113358129B (zh) * | 2021-05-25 | 2023-11-21 | 南京邮电大学 | 基于Voronoi图的避障最短路径规划方法 |
CN113724383A (zh) * | 2021-07-30 | 2021-11-30 | 深圳市普渡科技有限公司 | 机器人拓扑地图生成系统、方法、计算机设备及存储介质 |
CN114485707B (zh) * | 2022-01-17 | 2024-04-30 | 武汉科技大学 | 一种基于骨架关键点重规划的Voronoi路径规划方法 |
CN114639088A (zh) * | 2022-03-23 | 2022-06-17 | 姜妹英 | 大数据自动导航方法 |
CN115373399B (zh) * | 2022-09-13 | 2024-07-12 | 中国安全生产科学研究院 | 一种基于空地协同的地面机器人路径规划方法 |
Citations (6)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN1279451A (zh) * | 1999-07-06 | 2001-01-10 | 英业达集团(西安)电子技术有限公司 | 数字化字体轮廓的三角化向量趋近方法 |
CN104732789A (zh) * | 2015-04-08 | 2015-06-24 | 山东大学 | 一种基于公交车gps数据生成道路路网地图的方法 |
CN106017472A (zh) * | 2016-05-17 | 2016-10-12 | 成都通甲优博科技有限责任公司 | 全局路线规划方法、全局路线规划系统及无人机 |
CN108549388A (zh) * | 2018-05-24 | 2018-09-18 | 苏州智伟达机器人科技有限公司 | 一种基于改进a星策略的移动机器人路径规划方法 |
CN110728686A (zh) * | 2019-10-11 | 2020-01-24 | 湖南科技大学 | 一种基于Voronoi的车载灯具图像分割方法 |
CN110823241A (zh) * | 2019-11-19 | 2020-02-21 | 齐鲁工业大学 | 基于可通行区域骨架提取的机器人路径规划方法及系统 |
Family Cites Families (4)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US20130114900A1 (en) * | 2011-11-07 | 2013-05-09 | Stanford University | Methods and apparatuses for mobile visual search |
CN106682787A (zh) * | 2017-01-09 | 2017-05-17 | 北京航空航天大学 | 一种基于wavefront算法的快速生成广义维诺图的方法 |
CN107505939B (zh) * | 2017-05-13 | 2019-07-12 | 大连理工大学 | 一种移动机器人的全覆盖路径规划方法 |
CN108549378B (zh) * | 2018-05-02 | 2021-04-20 | 长沙学院 | 一种基于栅格地图的混合路径规划方法和系统 |
-
2020
- 2020-02-28 CN CN202010131142.7A patent/CN111323037B/zh active Active
Patent Citations (6)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN1279451A (zh) * | 1999-07-06 | 2001-01-10 | 英业达集团(西安)电子技术有限公司 | 数字化字体轮廓的三角化向量趋近方法 |
CN104732789A (zh) * | 2015-04-08 | 2015-06-24 | 山东大学 | 一种基于公交车gps数据生成道路路网地图的方法 |
CN106017472A (zh) * | 2016-05-17 | 2016-10-12 | 成都通甲优博科技有限责任公司 | 全局路线规划方法、全局路线规划系统及无人机 |
CN108549388A (zh) * | 2018-05-24 | 2018-09-18 | 苏州智伟达机器人科技有限公司 | 一种基于改进a星策略的移动机器人路径规划方法 |
CN110728686A (zh) * | 2019-10-11 | 2020-01-24 | 湖南科技大学 | 一种基于Voronoi的车载灯具图像分割方法 |
CN110823241A (zh) * | 2019-11-19 | 2020-02-21 | 齐鲁工业大学 | 基于可通行区域骨架提取的机器人路径规划方法及系统 |
Also Published As
Publication number | Publication date |
---|---|
CN111323037A (zh) | 2020-06-23 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
CN111323037B (zh) | 一种移动机器人新型骨架提取的Voronoi路径规划算法 | |
CN108647577B (zh) | 一种自适应难例挖掘的行人重识别方法与系统 | |
CN112132856B (zh) | 一种基于自适应模板更新的孪生网络跟踪方法 | |
CN112348864B (zh) | 一种融合线激光轮廓特征的三维点云自动配准方法 | |
CN113807355A (zh) | 一种基于编解码结构的图像语义分割方法 | |
CN109146838A (zh) | 一种基于几何特征与区域融合的g显带粘连染色体分割方法 | |
CN110533601B (zh) | 一种激光光斑中心位置及轮廓获取方法 | |
CN112712546A (zh) | 一种基于孪生神经网络的目标跟踪方法 | |
KR102305230B1 (ko) | 객체 경계정보의 정확도 개선방법 및 장치 | |
CN105654483A (zh) | 三维点云全自动配准方法 | |
CN109712160B (zh) | 基于广义熵结合改进的狮群算法实现图像阈值分割方法 | |
CN108765434B (zh) | 基于增材再制造点云模型的轮廓提取方法 | |
CN112581368B (zh) | 一种基于最优图匹配的多机器人栅格地图拼接方法 | |
CN110163894B (zh) | 基于特征匹配的亚像素级目标跟踪方法 | |
CN108122202A (zh) | 一种基于形状上下文的地图线状要素多尺度信息派生方法 | |
CN114943659A (zh) | 地图区域分割方法以及相关设备 | |
CN103198510B (zh) | 数据驱动的模型渐变方法 | |
CN105955191A (zh) | 一种基于图像特征数据进行路径规划的方法 | |
CN112837420B (zh) | 基于多尺度和折叠结构的兵马俑点云的形状补全方法及系统 | |
CN115908818A (zh) | 一种基于深度学习的高精度图像分割方法及装置 | |
CN111260723B (zh) | 棒材的质心定位方法及终端设备 | |
CN114399428A (zh) | 面状人工要素降维处理方法 | |
CN110348163B (zh) | 一种轮胎花纹边界连续相切圆弧的拟合方法 | |
CN109934837B (zh) | 一种3d植物叶片轮廓的提取方法、装置及系统 | |
CN110658783A (zh) | 一种五轴加工刀轴可行域的求解方法及系统 |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
PB01 | Publication | ||
PB01 | Publication | ||
SE01 | Entry into force of request for substantive examination | ||
SE01 | Entry into force of request for substantive examination | ||
TA01 | Transfer of patent application right | ||
TA01 | Transfer of patent application right |
Effective date of registration: 20220607 Address after: Room 313-314, building 2, Yangchenghu international science and technology entrepreneurship Park, No. 116, Chengyang Road, Chengyang street, Xiangcheng District, Suzhou, Jiangsu 215131 Applicant after: Haibo (Suzhou) robot technology Co.,Ltd. Address before: 430081 No. 947 Heping Avenue, Qingshan District, Hubei, Wuhan Applicant before: WUHAN University OF SCIENCE AND TECHNOLOGY |
|
GR01 | Patent grant | ||
GR01 | Patent grant |