一种基于栅格的轮廓线段特征提取算法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN110335282A(43)申请公布日2019.10.15(21)申请号201811593293.3(22)申请日2018.12.25(71)申请人广州启明星机器人有限公司地址510700广东省广州市黄埔区茅岗路828号自编29号2楼申请人海南大学(72)发明人曹一波刘好新(74)专利代理机构广州粤高专利商标代理有限公司44102代理人陈卫(51)Int.Cl.G06T7/13(2017.01)G06K9/62(2006.01)权利要求书3页说明书7页附图2页(54)发明名称一种基于栅格的轮廓线段特征提取算法(57)摘要本发明涉及移动机器人的技术领域，更具体地，涉及一种基于栅格的轮廓线段特征提取算法，包括数据点的聚类、每个聚类内数据点的排序、每个聚类内数据点的分段、每个数据段内数据点进行线段拟合，前三项为本发明提出的搜寻线段支持区的方法，结合该方法再在支持区内用最小二乘法拟合线段。本发明算法在寻找线段支持区时，不需要较大的内存和较长的计算时间，在拟合线段时，拟合的方法简单；本发明能够降低对旋转激光扫描仪的性能要求，降低噪点对于提取效果的影响；且本发明不用设置阈值等参数，降低对旋转激光扫描仪的性能要求，降低噪点对提取效果的影响，提取线段的分辨率高、鲁棒性强、效率高、实时性强。CN110335282ACN110335282A权利要求书1/3页1.一种基于栅格的轮廓线段特征提取算法，其特征在于，包括以下步骤：S10.构建包括有若干障碍物栅格的栅格地图，提取障碍物栅格的中心点坐标组成数据点集M＝{P1,P2,....,PN}；S20.基于欧式距离的聚类方法，通过数据点之间的欧氏距离度量将点集M划分为若干个第一聚类点集Mi＝{P1,P2,...,PK}；S30.基于路径搜索和分支点判断对每个第一聚类点集Mi的数据点进行排序，得到排序后的第二聚类点集Mii，Mii内的数据点满足拓扑结构的先后顺序；S40.将每个第二聚类点集Mii内的数据点划分为若干个数据段Sj＝{P1,P2,...,PJ}，每个数据段内的数据点可拟合成一条线段；S50.对每个数据段内的数据点采用最小二乘法进行线段拟合。2.根据权利要求1所述的基于栅格地轮廓线段特征提取算法，其特征在于，步骤S10的实现方法是：逐行逐列扫描栅格地图，若扫描到的栅格为障碍物，则将所述栅格的中心点坐标作为数据点加入数据点集M。3.根据权利要求1所述的基于栅格的轮廓线段特征提取算法，其特征在于，步骤S20中，对Mi内每个数据点Pi在Mi内寻找至少一个相邻的数据点Pj满足0＜|Pj-Pi|≤1,Pi,Pj∈Mi。4.根据权利要求3所述的基于栅格的轮廓线段特征提取算法，其特征在于，步骤S20包括以下步骤：S21.建立一个第一聚类点集Mi；S22.从数据点集M中取出第一个数据点P1，作为第一聚类点集Mi的第一个数据点，同时将P1从数据点集M中删除；S23.从第一聚类点集Mi中取出一个数据点Pj；S24.逐点扫描数据点集M中的数据点Pi，若0＜|Pj-Pi|≤1，则将Pi加入第一聚类点集Mi中，并将Pi从数据点集M中删除；S25.重复步骤S23～S24，直至遍历完第一聚类点集Mi中所有的数据点；S26.重复步骤S21～S25，直至遍历完数据点集M中所有的数据点。5.根据权利要求1所述的基于栅格的轮廓线段特征提取算法，其特征在于，步骤S30包括以下步骤：S31.建立一个第二聚类点集Mii，选取第一聚类点集Mi＝{P1,P2,...,PK}的最后一点PK存入第二聚类点集Mii，并将PK从Mi中删除，标记Mii的第一点为未遍历点；S32.从第二聚类点集Mii中取出第一个未遍历点Pii，并将Pii标记为已遍历点；S33.按顺序搜索Pii周围相邻的栅格Pi：若Pi∈Mi，且Pi被判断为分支点，则将Pi存入分支点缓存点集Bii，并将Pi从Mi删除；跳入下一步；若Pi∈Mi，且Pi不是分支点，则将Pi加入Mii，标记为未遍历点，同时将Pi从Mi删除，跳入下一步；S34.重复S33，直至搜索完Pii周围相邻的所有栅格；S35.重复S32-S34，直至第二聚类点集Mii中没有未遍历点；S36.从Bii中取出一点Pj添加到Mii中，标记为未遍历点，并将Pj从Bii删除；S37.重复步骤S32～S36，直至分支点缓存点集Bii中没有数据点。2CN110335282A权利要求书2/3页6.根据权利要求5所述的基于栅格的轮廓线段特征提取算法，其特征在于，步骤S33所述的分支点判定方法为：若Mii中存在至少一个数据点Pjj满足|Pi-Pjj|≥1且则判定Pi为分支点；若Mii中存在至少两个数据点Pjj满足则判定Pi为分支点。7.根据权利要求1所述的基于栅格