本申请涉及机器人导航
技术领域：
：，尤其是涉及一种基于分裂型层次聚类的轨迹分析方法、设备及存储介质。
背景技术：
：：视觉定位就是通过安装在机器人上的视觉传感器，进行环境图像的采集，然后通过对图像信息的处理，来估计机器人的位姿变化。视觉传感器相较于其他用于移动机器人定位的传感器，例如gps、imu、激光雷达、轮式里程计等具有非常多的优点。计算机视觉顾名思义就是通过技术手段来模拟人的视觉，摄像头好比人的眼睛，可以提供丰富的图像信息。人依靠眼睛就能实现绝大多数的导航任务，就是因为人的眼睛提供的图像中包含着大量的信息。同样，机器人通过视觉传感器提供的图像也可以从中提取出非常多的信息，例如场景的纹理、颜色以及物体的形状大小等各类信息。通过这些丰富的信息，机器人可以实现在各种环境中的定位与导航。轨迹的聚类分析是利用对象的轨迹数据，发现有共同行为与模式的对象组，同组对象之间具有较高的相似度，而不同组内差别较大，可有效发掘出用户的移动模式及热点区域，为轨迹检测、应急管理、位置服务等提供有效的参考。根据不同的应用需求，机器人需要在各种复杂的、多变的环境下进行工作，完成自己负担的任务。而在此过程中，机器人不仅仅需要在明确自己位置的同时，确定下一步的行进方向，还需要能够将当前行动轨迹反馈给终端决策者进行轨迹分析与调整，以增加工作效率。技术实现要素：为了便于实现机器人的定位与导航，本申请提供了一种基于分裂型层次聚类的轨迹分析方法、设备及存储介质。第一方面，本申请提供的一种基于分裂型层次聚类的轨迹分析方法，采用如下的技术方案。一种基于分裂型层次聚类的轨迹分析方法，包括：实时获取机器人自身视觉传感器采集的第一视角图像；根据所述第一视角图像进行实时定位与地图构建；根据所述地图，生成机器人当前位置与目的地之间的所有轨迹路线；利用轨迹特征点提取方法，提取所述所有轨迹路线中的轨迹特征点，得到轨迹路线的特征点集合；根据所述轨迹路线的特征点集合得到相应轨迹路线的特征轨迹，计算任意两个特征轨迹之间的相似度；利用基于轨迹相似度的聚类算法对所有的特征轨迹进行聚类分析。通过采用上述技术方案，通过机器人自身的视觉传感器获取的视觉数据，完成对机器人实时定位与地图的构建，从而生成机器人当前位置到目的地之间所有可能的轨迹路线，计算所有的轨迹路线的相似度，利用基于轨迹相似度的聚类算法，对轨迹集合进行分裂型层次聚类的分析，便于为机器人移动路线规划和推荐提供决策支持和依据。可选的，采用slam方法根据所述第一视角图像进行实时定位与地图构建，具体包括：利用视觉里程计对所述第一视角图像进行处理，计算姿态变化；对所述第一视角图像进行回环检测，得到全局一致性轨迹；利用滤波或非线性优化理论对视觉里程计和回环检测输出的结果进行优化；完成实时定位与地图的构建。通过采用上述技术方案，slam方法的思想是机器人在未知环境中从一个未知位置开始移动，在移动过程中根据位置估计和传感器数据进行自身定位，同时建造地图。因此采用slam方法能够便于实现机器人的实时定位与机器人周围环境地图的构建。可选的，根据构建的地图，生成机器人当前位置与目的地之间的所有轨迹路线，具体为：将机器人当前位置与目的地位置均映射至地图中对应的坐标，得到地图中当前位置坐标与目的地位置坐标之间的所有轨迹，从而生成机器人当前位置到目的地位置的所有轨迹路线。通过采用上述技术方案，为了便于根据地图生成机器人当前位置与目的地之间的所有轨迹路线，需要将机器人当前位置与目的地位置均映射至地图中，从而根据地图中机器人当前位置坐标和目的地坐标得到所有轨迹。可选的，所述利用轨迹特征点提取方法，提取所有轨迹路线中的轨迹特征点，得到轨迹路线的特征点集合，具体过程为：构造移动轨迹序列，预设角度偏移阈值和停留时间阈值；构造特征点集合；将轨迹路线的起始位置加入特征点集合；根据所述预设角度偏移阈值和停留时间阈值筛选中间特征点；将轨迹路线的结束位置加入特征点集合，得到相应轨迹路线的特征点集合。通过采用上述技术方案，构建移动轨迹序列和一个特征点集合，该特征点集合用于存储从移动轨迹序列中筛选出的特征点。将轨迹路线的起始位置加入特征点集合中作为第一个特征点，然后根据预设角度偏移阈值和停留时间阈值筛选出能够表明位置重要性的中间特征点，最后将轨迹路线的结束位置作为最后一个特征点加入特征点集合中，从而得到能够表明该轨迹路线的完整的特征点集合。可选的，所述根据所述轨迹路线的特征点集合得到相应轨迹路线的特征轨迹，计算任意两个特征轨迹之间的相似度，具体为：将同一轨迹路线中每两个相邻特征点之间通过线段连接，构成由若干轨迹线段组成的特征轨迹；计算特征轨迹中每两个相邻特征点之间的距离，得到所述特征轨迹的长度；计算任意两个特征轨迹之间同一序号的轨迹线段之间的距离；根据两个特征轨迹中同一序号的轨迹线段之间的距离，计算所述两个特征轨迹的相似度。通过采用上述技术方案，将轨迹路线的所有特征点用经纬度坐标来表示其空间地理位置，计算出每两个相邻特征点之间的距离，并计算两个不同特征轨迹之间同一序号的轨迹线段之间的距离，从而计算出两个特征轨迹之间的相似度。可选的，采用改进的实数代价编辑距离方法计算所述两个特征轨迹的相似度。通过采用上述技术方案，改进的edr方法能够对不同间隔、长度的轨迹数据进行采样，结合基于轨迹特征点的距离计算方法进行相似度的计算，同时对于因为仪器故障引起的的轨迹噪声有较好的鲁棒性。可选的，所述聚类算法为分裂型层次聚类算法，进行聚类分析的步骤包括：将所有的特征轨迹初始化为一个簇，计算簇中每一个特征轨迹与其他特征轨迹之间的相似度，在相似度小于预设的相似度阈值的轨迹对中，将相似度最小的一对特征轨迹分裂到一个新的簇中；迭代聚类并反复分裂出新的簇；当簇中所有特征轨迹之间的相似度均大于预设的相似度阈值时或者簇的数量达到要求时，停止分裂，聚类结束。通过采用上述技术方案，利用特征轨迹数据，发现有共同行为特征轨迹的对象组，同组对象之间具有较高的相似度，而不同组内差别较大，可有效发掘出移动模式及热点区域，为轨迹检测、位置服务等提供有效的参考。第二方面，本申请提供的一种用于基于分裂型层次聚类的轨迹分析的设备，采用如下的技术方案。一种计算机设备，包括存储器、处理器以及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现：实时获取机器人自身视觉传感器采集的第一视角图像；根据获取的第一视角图像完成实时定位与地图构建；根据构建的地图，生成机器人当前位置与目的地之间的所有轨迹路线；利用轨迹特征点提取方法，提取所有轨迹路线中的轨迹特征点，得到轨迹路线的特征点集合；根据所述轨迹路线的特征点集合得到相应轨迹路线的特征轨迹，计算任意两个特征轨迹之间的相似度；利用基于轨迹相似度的聚类算法对所有的特征轨迹进行聚类分析的步骤。通过采用上述技术方案，所述计算机设备上能够实现执行本申请所提供的基于分裂型层次聚类的轨迹分析方法。第三方面，本申请提供的一种基于分裂型层次聚类的轨迹分析的存储介质，采用如下的技术方案。一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器运行时执行：实时获取机器人自身视觉传感器采集的第一视角图像；根据获取的第一视角图像完成实时定位与地图构建；根据构建的地图，生成机器人当前位置与目的地之间的所有轨迹路线；利用轨迹特征点提取方法，提取所有轨迹路线中的轨迹特征点，得到轨迹路线的特征点集合；根据所述轨迹路线的特征点集合得到相应轨迹路线的特征轨迹，计算任意两个特征轨迹之间的相似度；利用基于轨迹相似度的聚类算法对所有的特征轨迹进行聚类分析的步骤。通过采用上述技术方案，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器运行时能够实现执行本申请所提供的基于分裂型层次聚类的轨迹分析方法。综上所述，本申请包括以下有益技术效果：1、通过机器人自身的视觉传感器获取的视觉数据，采用slam方法能够便于实现机器人的实时定位与机器人周围环境地图的构建。2、采用改进的实数代价编辑距离方法计算各轨迹路线的相似度，能够对不同间隔、长度的轨迹数据进行采样，同时对于因为仪器故障引起的的轨迹噪声有较好的鲁棒性。3、利用分裂型层次聚类算法对所有的轨迹路线进行相似度的聚类分析，便于为机器人移动路线规划和推荐提供决策支持和依据。附图说明图1是本申请其中一实施例的分裂型层次聚类的轨迹分析方法流程图。图2是本申请其中一实施例的slam方法流程图。图3是本申请其中一实施例的轨迹特征点提取算法流程图。图4是本申请其中一实施例的基于轨迹相似度的聚类算法流程图。具体实施方式为了使本申请的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本申请进行进一步详细说明。本具体实施例仅仅是对本申请的解释，其并不是对本申请的限制，本领域技术人员在阅读完本说明书后可以根据需要对本实施例做出没有创造性贡献的修改，但只要在本申请的权利要求范围内都受到专利法的保护。本申请实施例公开一种基于分裂型层次聚类的轨迹分析方法，如图1所示，所述方法的主要流程描述如下。s100，实时获取机器人自身视觉传感器采集的第一视角图像。所述视觉传感器安装在机器人上，用于进行机器人第一视角的环境图像的采集。本实施例中，视觉传感器可以是psd图像传感器、ccd图像传感器、cmos图像传感器等摄像元件。s200，根据所述第一视角图像进行实时定位与地图构建。定位与地图两者是相辅相成的，精准的定位可以提高所构建的地图的精确性，而精确的地图亦能够帮助实现更精准的地位。slam（simultaneouslocalizationandmapping，同步定位与地图构建），指的是机器人在自身位置不确定的条件下，在运动过程中重复地读取传感器观测数据，分析获取环境特征与自身位置姿态，并以此实时构建周围环境的地图。slam不仅可以使用预先得到的地图，还能随着机器人的移动对机器人经过的区域进行实时的地图构建。slam技术包括激光slam技术和视觉slam技术。本实施例中采用视觉slam技术，即vslam进行机器人实时定位与地图构建。vslam分为前端和后端，前端为视觉里程计和回环检测，相当于对图像数据进行关联，后端是对前端输出的结果进行优化，利用滤波或非线性优化理论，得到最优的位姿估计和全局一致性地图。如图2所示，首先，利用视觉里程计（visualodometry，vo）对获取的第一视角图像进行处理，计算姿态变化，得到视觉传感器的运动关系。随着时间的累积，误差会累积，这是由于仅仅估计两个图像间的运动造成的，后端主要是使用优化方法减小整个框架误差（包括机器人位姿和空间地图点）。并对获取的第一视角图像进行回环检测，主要是利用图像间的相似性来判断是否到达过先前的位置，以此来消除累积误差，得到全局一致性轨迹和地图。根据估计的轨迹，建立与任务要求对应的地图。视觉里程计可分为特征点法和直接法。本实施例中的视觉里程计采用基于特征点法的视觉里程计，主要是根据图像上的特征匹配关系得到相邻帧间的视觉传感器运动。需要对特征进行提取和匹配，然后根据匹配特征构建重投影误差函数，并将其最小化从而得到视觉传感器的相对运动。s300，根据构建的地图，生成机器人当前位置与目的地之间的所有轨迹路线。根据机器人当前位置、目的地位置以及步骤s200中构建的地图，生成所有可能的轨迹路线。本实施例中，可以依据机器人当前所处位置的经纬度信息，在步骤s200构建的地图中查找到与该经纬度信息对应的坐标点，从而将机器人当前位置映射至地图中，获得机器人当前位置对应在地图中的位置。再将目的地位置的经纬度信息在步骤s200构建的地图中查找与该经纬度信息对应的坐标点，获得目的地位置对应在地图中的位置。从而生成机器人当前位置到目的地位置的所有可能的轨迹路线。s400，利用轨迹特征点提取方法，提取所有轨迹路线中的轨迹特征点，得到轨迹路线的特征点集合。轨迹特征点是指一条轨迹路线中能反应轨迹移动模式的关键位置，提取轨迹特征点能够使原始轨迹路线更加简单清晰，而且能够缩短度量轨迹相似性的时间。图3为本实施例进行特征点提取的算法流程图，如图3所示，得到轨迹路线的特征点集合具体包括以下步骤。s401，构造初始参数。具体的，构造一个移动轨迹序列tra={p1,p2,…,pn}，预设角度偏移阈值thra和停留时间阈值thrt。构造一个特征点集合cp，用于存储从移动轨迹序列中筛选出的特征点。对于每一条移动轨迹路线，通过特征点提取都可以得到轨迹路线的特征点集合cp。s402，将轨迹路线的起始位置加入特征点集合cp，作为所述特征点集合cp中的第一个特征点。s403，筛选中间特征点。当轨迹路线中的位置pi满足以下任一条件就可以选为一个特征点：（1）pi是轨迹路线中典型的转折点，如陡坡、台阶、楼梯等位置。（2）角度偏移值api大于预设的角度偏移阈值thra的位置点，角度偏移值可以表明移动轨迹在该位置的移动方向发生了明显的变化。（3）pi是停留时间tpi超过预设的停留时间阈值thrt的位置点，停留时间的长短在一定程度上可以表明该位置的重要性。将筛选出的中间特征点按照其在轨迹路线中的先后顺序加入到特征点集合cp中。s404，将轨迹路线的结束位置加入特征点集合cp中，作为所述特征点集合cp中的最后一个特征点，得到相应轨迹路线的特征点集合cp。s405，输出特征点集合cp，根据该特征点集合cp可以得到在原始轨迹路线基础上提取特征点之后的特征轨迹。s500，根据所述轨迹路线的特征点集合cp得到相应轨迹路线的特征轨迹，计算任意两个特征轨迹之间的相似度。1）将同一轨迹路线中每两个相邻特征点之间通过线段连接，构成由若干轨迹线段组成的特征轨迹。同一特征轨迹中相邻的两个特征点之间通过线段连接，由此轨迹路线就可以用多个线段构成的有序序列trl=={l1,l2,…,lm}来表示，即特征轨迹。其中，l1表示特征轨迹中第一个特征点与第二个特征点构成的线段，l2表示该特征轨迹中第二个特征点与第三个特征点构成的线段，以此类推，m为特征轨迹中线段的数量。2）计算特征轨迹中每两个相邻特征点之间的距离，得到所述特征轨迹的长度。特征点集合cp中的轨迹特征点都可以用经纬度坐标来表示其空间地理位置，因此两个相邻特征点之间的距离可以以地球半径的弧度为基准换算得到。计算同一特征轨迹中两个相邻特征点之间的距离，即两个相邻特征点所连接形成的线段的长度，计算公式为：（1）其中，dist(p,q)表示特征点p到相邻的特征点q之间的距离；特征点p的经纬度坐标为(lngp,latp)，特征点q的经纬度坐标为(lngq,latq)，r表示地球半径，根据地球上任意两点的经度和纬度计算公式获得两个特征点之间的距离。3）计算两个不同特征轨迹之间同一序号的轨迹线段之间的距离。计算不同特征轨迹序列中同一序号的轨迹线段之间的距离，如两条移动轨迹的第一个轨迹线段之间的距离。两条不同特征轨迹中同一序号的轨迹线段之间的距离可以由四部分构成：垂直距离d┴、水平距离d||、高度距离dh和角度距离dθ。高度距离dh是两条不同特征轨迹中同一序号的轨迹线段在三维空间里的高度差；垂直距离d┴是这两个轨迹线段投影到二维平面上后，在垂直方向上的距离。垂直距离d┴、水平距离d||、高度距离dh和角度距离dθ可以通过经纬度坐标计算得到。（2）其中，θ是两条不同特征轨迹中同一序号的轨迹线段之间的角度。计算两条不同特征轨迹中同一序号的轨迹线段之间的距离公式为：（3）其中，ω┴、ω||、ωh、ωθ分别是d┴、d||、dh和dθ的权重，可以根据实际情况取值，li和ri分别代表两条不同特征轨迹上同一序号的轨迹线段，dθ表示以li线段作为参考，线段ri与li之间的角度距离。4）根据两个特征轨迹中同一序号的轨迹线段之间的距离，计算所述两个特征轨迹的相似度。本实施例中通过改进的实数代价编辑距离（editdistanceonrealsequence，edr）方法来计算轨迹相似度，edr是计算轨迹相似度的经典方法，改进的edr方法能够对不同间隔、长度的轨迹数据进行采样，结合基于轨迹特征点的距离计算方法进行相似度的计算，同时对于因为仪器故障引起的的轨迹噪声有较好的鲁棒性。公式如下：（4）（5）其中，distr(tra1,tra2)为计算特征轨迹tra1和tra2之间的距离，tra(i)表示特征轨迹tra的第i个线段，|tra1|和|tra2|分别表示两条特征轨迹中特征点的数目，rest(tra)表示tra移除当前比较线段后的剩余轨迹线段，cost(tra1(1),tra2(1))为编辑操作代价。通过公式（6）可以计算出特征轨迹tra1和特征轨迹tra2的空间相似度spasim(tra1,tra2)。（6）由公式（6）可知，两个特征轨迹之间的距离越小，相似度越高s600，利用基于轨迹相似度的聚类算法对所有的特征轨迹进行聚类分析。在本实施例中，利用分裂型层次聚类算法对所有的特征轨迹进行聚类分析。分裂型层次聚类采用自顶向下的的思想，将所有的数据看成一个簇，根据一定规则渐渐分解直到簇的数目达到预期值或者满足其他终止条件为止。在传统算法中，通常使用树形结构表示层次聚类的过程，并构建相似度矩阵存储聚类过程中簇之间的相似度。本实施例中，采用线性表结构代替矩阵簇之间的相似度，线性表可以表示为ltable={x1,x2,…,xk}，该线性表中包括k个元素，每个元素中包含三部分，第一部分为簇1，第二部分为簇2，第三部分为簇1和簇2的相似度。例如，元素xi=〈cr,cs,ε〉，表示簇cr与簇cs之间的相似度值为ε。将所有的特征轨迹看作一个簇，采用二分的方式进行分裂。若ε大于预先设定的相似度阈值，则将这cr和cs归为一个新的簇，如果小于阈值则将cr和cs分别分到两个簇里。对线性表中的所有相似度满足条件的簇进行该操作，直到簇之间的最大相似度小于相似度阈值。利用分裂型层次聚类算法进行聚类的过程如图4所示。图4为本申请提出的一种基于轨迹相似度的聚类算法流程图，包括：s601，初始数值。根据所有特征轨迹构建一个轨迹集tr={tra1,tra2,…,tral}，并预设相似度阈值v；其中l为特征轨迹的数量。s602，初始化特征轨迹。将所有特征轨迹初始化为一个簇。s603，计算轨迹相似度并存入线性表结构。计算簇内每一个特征轨迹与其他所有特征轨迹之间的轨迹相似度，存入线性表结构。s604，分裂簇。比较每一个特征轨迹与其他特征轨迹之间的相似度，在轨迹相似度小于相似度阈值v的特征轨迹对中，找到轨迹相似度最小的一对特征轨迹并将其分裂达到一个新的簇里，同时原簇中其他特征轨迹保持不变。在之后的操作中迭代聚类并反复分裂出新的簇。s605，判断。当簇中所有特征轨迹之间的相似度均大于相似度阈值v时或者簇集合的数量达到要求时，停止分裂。s606，输出。输出簇的集合。本申请实施例还公开一种计算机设备，包括存储器、处理器以及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现：实时获取机器人自身视觉传感器采集的第一视角图像；根据获取的第一视角图像完成实时定位与地图构建；根据构建的地图，生成机器人当前位置与目的地之间的所有轨迹路线；利用轨迹特征点提取方法，提取所有轨迹路线中的轨迹特征点，得到轨迹路线的特征点集合；根据所述轨迹路线的特征点集合得到相应轨迹路线的特征轨迹，计算任意两个特征轨迹之间的相似度；利用基于轨迹相似度的聚类算法对所有的特征轨迹进行聚类分析的步骤。本申请实施例还公开一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器运行时执行：实时获取机器人自身视觉传感器采集的第一视角图像；根据获取的第一视角图像完成实时定位与地图构建；根据构建的地图，生成机器人当前位置与目的地之间的所有轨迹路线；利用轨迹特征点提取方法，提取所有轨迹路线中的轨迹特征点，得到轨迹路线的特征点集合；根据所述轨迹路线的特征点集合得到相应轨迹路线的特征轨迹，计算任意两个特征轨迹之间的相似度；利用基于轨迹相似度的聚类算法对所有的特征轨迹进行聚类分析的步骤。以上所述，仅为本申请较佳的具体实施方式，但本申请的保护范围并不局限于此，任何熟悉本
技术领域：
：的技术人员在本申请揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本申请的保护范围之内。因此，本申请的保护范围应该以权利要求的保护范围为准。本说明书中未作详细描述的内容属于本领域专业技术人员公知的现有技术。当前第1页1 2 3 当前第1页1 2 3
技术特征：1.一种基于分裂型层次聚类的轨迹分析方法，其特征在于，包括：
实时获取机器人自身视觉传感器采集的第一视角图像；
根据所述第一视角图像进行实时定位与地图构建；
根据所述地图，生成机器人当前位置与目的地之间的所有轨迹路线；
利用轨迹特征点提取方法，提取所述所有轨迹路线中的轨迹特征点，得到轨迹路线的特征点集合；
根据所述轨迹路线的特征点集合得到相应轨迹路线的特征轨迹，计算任意两个特征轨迹之间的相似度；
利用基于轨迹相似度的聚类算法对所有的特征轨迹进行聚类分析。
2.根据权利要求1所述的基于分裂型层次聚类的轨迹分析方法，其特征在于，采用slam方法根据所述第一视角图像进行实时定位与地图构建，具体包括：
利用视觉里程计对所述第一视角图像进行处理，计算姿态变化；
对所述第一视角图像进行回环检测，得到全局一致性轨迹；
利用滤波或非线性优化理论对视觉里程计和回环检测输出的结果进行优化，完成实时定位与地图的构建。
3.根据权利要求1所述的基于分裂型层次聚类的轨迹分析方法，其特征在于，根据所述地图，生成机器人当前位置与目的地之间的所有轨迹路线，具体为：将机器人当前位置与目的地位置均映射至地图中对应的坐标，得到地图中当前位置坐标与目的地位置坐标之间的所有轨迹，从而生成机器人当前位置到目的地位置的所有轨迹路线。
4.根据权利要求1所述的基于分裂型层次聚类的轨迹分析方法，其特征在于，所述利用轨迹特征点提取方法，提取所述所有轨迹路线中的轨迹特征点，得到轨迹路线的特征点集合，具体过程为：
构造移动轨迹序列，预设角度偏移阈值和停留时间阈值；构造特征点集合；
将轨迹路线的起始位置加入特征点集合；
根据所述预设角度偏移阈值和停留时间阈值筛选中间特征点；
将轨迹路线的结束位置加入特征点集合，得到相应轨迹路线的特征点集合。
5.根据权利要求1所述的基于分裂型层次聚类的轨迹分析方法，其特征在于，所述根据所述轨迹路线的特征点集合得到相应轨迹路线的特征轨迹，计算任意两个特征轨迹之间的相似度，具体为：
将同一轨迹路线中每两个相邻特征点之间通过线段连接，构成由若干轨迹线段组成的特征轨迹；
计算特征轨迹中每两个相邻特征点之间的距离，得到所述特征轨迹的长度；
计算不同两个特征轨迹之间同一序号的轨迹线段之间的距离；
根据两个特征轨迹中同一序号的轨迹线段之间的距离，计算所述两个特征轨迹的相似度。
6.根据权利要求5所述的基于分裂型层次聚类的轨迹分析方法，其特征在于，采用改进的实数代价编辑距离方法计算所述两个特征轨迹的相似度。
7.根据权利要求1所述的基于分裂型层次聚类的轨迹分析方法，其特征在于，所述聚类算法为分裂型层次聚类算法，进行聚类分析的步骤包括：
将所有的特征轨迹初始化为一个簇，计算簇中每一个特征轨迹与其他特征轨迹之间的相似度，在相似度小于预设的相似度阈值的轨迹对中，将相似度最小的一对特征轨迹分裂到一个新的簇中；
迭代聚类并反复分裂出新的簇；
当簇中所有特征轨迹之间的相似度均大于预设的相似度阈值时或者簇的数量达到要求时，停止分裂，聚类结束。
8.一种计算机设备，包括存储器、处理器以及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述计算机程序时实现上述权利要求1-7中任一项所述的方法的步骤。
9.一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，其特征在于，所述计算机程序被处理器运行时执行上述权利要求1-7任一项所述的方法的步骤。
技术总结本申请涉及一种基于分裂型层次聚类的轨迹分析方法、设备及存储介质,涉及机器人导航技术领域。所述方法包括：实时获取机器人自身视觉传感器采集的第一视角图像；根据第一视角图像进行实时定位与地图构建，从而生成机器人当前位置与目的地之间的所有轨迹路线；利用轨迹特征点提取方法，提取所有轨迹路线中的轨迹特征点，得到轨迹路线的特征点集合；根据所述轨迹路线的特征点集合得到相应轨迹路线的特征轨迹，计算任意两个特征轨迹之间的相似度；利用基于轨迹相似度的聚类算法对所有的特征轨迹进行聚类分析。通过地图构建、特征点提取以及计算特征轨迹相似度，对机器人的轨迹进行分析，便于为机器人的移动路线规划和推荐提供决策支持和依据。
技术研发人员：石碰;蒋涛;左昉;余军;周成成;林福宏
受保护的技术使用者：北京集光通达科技股份有限公司
技术研发日：2020.11.25
技术公布日：2021.03.12
