论文
# 基于改进DBSCAN与OPTICS的踝部激光雷达行人跟踪
马哈茂杜尔·哈桑 $^{*}$, $^{**a}$，非会员
花川纯一 $^{*}$，非会员
后藤理久 $^{*}$，非会员
福田久人 $^{*}$，非会员
久野义宪 $^{*}$，会员
小林义宪 $^{*}$，非会员
随着深度学习技术的发展，利用摄像机进行行人跟踪已经变得简便而准确。然而，基于视觉的监控尚未充分解决隐私与安全问题。人们无法接受在日常生活的各处都安装监控摄像头，并且基于摄像头的系统在烟雾、大雾、黑暗等特殊环境下无法稳定运行。为解决这些问题，我们提出一种基于聚类算法的二维（2D）激光雷达行人跟踪技术。激光雷达传感器是一种十分出色的方案，即使在复杂条件下也能在不泄露行人身份的前提下完成跟踪。针对行人跟踪任务，我们提出改进后的具有噪声的基于密度的空间聚类（DBSCAN）算法和基于点排序识别聚类结构（OPTICS）算法，用于对二维激光雷达数据进行聚类。我们通过实验证实，该方法显著提升了行人跟踪的准确性与鲁棒性。© 2021 日本电气学会。由Wiley Periodicals LLC出版。
关键词：行人跟踪；DBSCAN；OPTICS；基于密度的聚类；激光雷达
收稿日期：2020年10月30日；修回日期：2021年2月1日
## 1. 引言
如今，人们在办公室、道路上甚至家中都处于监控之下。为打造一个安全稳固的社会，保护公民免受各类侵害，我们必须对所有活动保持监管。另一方面，由于监控视频存在泄露风险，人们也在不断主张自身的隐私权与保密权。机场、车站、博物馆、大型超市等公共场所的服务需要获取人员轨迹，以此提供更高质量的服务。我们基于二维（2D）LiDAR的追踪系统能够稳健、准确地追踪个人目标。当不需要识别个人身份，仅需要完成人员追踪时，我们的系统能发挥关键作用。宽视角和低计算成本也是基于2D LiDAR追踪方案的优势。使用摄像机、三维（3D）LiDAR和深度神经网络（DNN）会让系统在成本和时间上都有很高开销。本应用非常适用于应急场景，尤其是自然灾害中的救援系统。在计算速度和抗遮挡鲁棒性方面，2D LiDAR传感器相比RGB/RGB-D相机更具优势。
基于视频的人体跟踪是一项应用广泛的技术，已在各类不同场景中得到普遍采用。我们用二维激光雷达（2D LiDAR）替代摄像机，尝试寻找一种替代方案。我们将二维激光雷达放置在小腿（脚踝）高度位置，在$270^{\circ}$个方向上采集距离信息。我们将距离数据绘制在类似俯视图的二维图像平面上（我们将该图像称为「激光雷达图像」）。在此基础上，系统利用背景减除技术可以去除墙体、静止物体这类结构信息，最终在激光雷达图像上仅保留运动物体的位置数据。
要实现单人跟踪，必须通过某种方式区分出属于同一个人的数据点。常规方法分为两个步骤：先对每个脚踝对应的数据点聚类，再将同一个人的两个脚踝进行配对。换句话说，我们先通过计算像素间距离生成聚类来确定脚踝位置，再计算两个脚踝之间的距离从而区分不同个体。
这种方法存在多个难点：首先，两步聚类流程十分耗时，而处理速度是跟踪任务的关键影响因素；其次，在检测到多个人的脚踝后，在多人场景中很难判断哪两个脚踝属于同一个人。与此不同，本文提出的方法仅需一步聚类即可识别出不同个体。通常情况下，同一个人的两个脚踝在行走时会近距离交错经过，因此我们基于二维激光雷达数据（绘制在同一图像上的距离数据时间序列）生成运动历史图像，其中包含两个脚踝近距离交错经过的帧，随后我们采用一步聚类区分不同个体。
---
Fig. 1. Block diagram of LiDAR-based person tracking
针对本次数据聚类，我们此前采用的是传统聚类算法，本次研究我们使用了基于密度的算法。基于密度的聚类在寻找任意形状的簇和便捷去除噪声方面优势十分突出。这类算法的另一项显著优点是无需预先设定聚类簇的数量，它会根据数据密度生成聚类结果。我们结合maxPts参数，针对我们的系统修改了两种知名的基于密度算法：带噪声的基于密度空间应用聚类算法（DBSCAN）和点排序识别聚类结构算法（OPTICS）。这一修改提升了这两种算法在人体跟踪任务中的鲁棒性。我们研究发现，这些改进后的算法时间复杂度与原算法保持一致，同时性能得到了大幅提升。
在Fig. 1中，我们展示了所提出的基于LiDAR的人体追踪方案的框图。三个独立模块协同工作实现人体追踪。第一个模块是传感：我们使用2D LiDAR传感器获取距离数据，特定时刻的所有距离数据会被绘制在一张图像上，我们将该图像称为“帧”。我们采用边界去除技术去除传感图像中的冗余无效数据，再从运动历史图像中追踪脚踝位置。得到帧内的脚踝位置后，我们使用改进后的聚类算法实现精准的人体追踪，其中卡尔曼滤波（Kalman filter, KF）被用于人体追踪。本研究的核心目标是构建一套使用2D LiDAR数据的先进人体追踪系统。为了提升系统精度，我们分别测试了两种基于密度的改进算法，结果表明改进后的算法能得到更准确的追踪结果。EDBSCAN和EOPTICS均可满足本文的聚类需求，两种算法都有良好效果，不过EOPTICS在本研究场景中表现更优。本研究也可为时间序列2D LiDAR数据处理中的聚类算法应用提供参考。
### 2. 相关研究
2.1 基于传感器的追踪相关研究 许多研究者针对基于不同传感技术的人体追踪开展了大量工作。基于视频的人体追踪[^1]是该领域十分常见的研究方向。技术与处理方法的进步让这项研究的精度日益提升。基于三维骨架的人体追踪[^2]为该研究领域带来了全新思路，这类方法基于拓扑框架，提出了用于识别与追踪的三维骨骼模型。视频录制需要依托监控摄像头，部分研究者使用循环卷积网络（Recurrent Convolutional Network, RCN）进行行人识别[^3]，他们采用循环神经网络架构完成视频分析与行人重识别。从视频中完成多人体追踪是持续监控的必要需求[^4]，这类追踪需要兼具即时性与准确性。除视频方案外，也有研究者尝试开发基于传感器的人体追踪方案，基于射频的多传感器方案[^5]被用于人体追踪，该研究将防护系统与人体运动传感相结合实现人体追踪。通常这类转换在定位过程中会耗费不必要的时间，此外，使用多传感器还会提升系统的复杂度。
在多人追踪系统中，遮挡是最核心的基础问题之一。在基于视频的方法中，有时会利用阴影来实现多人追踪 [^6]。使用多个摄像机进行人员追踪和索引不仅成本过高，还会受到计算能力的限制。针对这一情况，研究者提出了一种基于多视图架构的无监督特征选择机制 [^7]。该研究提出了一种用于特征选择的分布式编码，并展示了其在多视图识别中的应用。在此期间，新型传感器不断被研发出来，科学家们尝试将其应用在不同场景中。基于低分辨率红外热传感器的人员追踪框架 [^8] 就是这类研究成果之一。该研究结合了RGB相机和红外相机来实现追踪。我们的研究仅聚焦于基于单个传感器的追踪，力求找到摄像机的替代方案，而上述这类方法都基于多传感器应用。一直以来，研究人员都在尝试寻找摄像机的替代方案。基于LiDAR的步态分析 [^9] 以及用于监控的人类不同活动研究是一项很有前景的工作。他们将提出的算法植入到一个可视化系统中，该系统可以分析并协同展示户外行人行走的实际场景。他们尝试基于LiDAR传感器，研究基于步态的人员识别以及相关活动识别。
2.2 基于聚类跟踪的相关研究 我们的研究聚焦于基于密度的聚类方法。在此领域中，DBSCAN [^10]、OPTICS和点云相关方法 [^11] 相较其他方案取得了显著提升。然而，将这些算法应用于激光雷达（LiDAR）传感器数据的研究十分有限。针对激光雷达数据的DBSCAN邻域参数Eps估计研究 [^12] 是一项具有影响力的工作。该研究聚焦于DBSCAN的自动点云分割与参数估计问题，研究人员使用点云数据对所提方法进行了评估，但他们的方法并未应用于行人跟踪和实时激光雷达数据场景。我们正是针对这一方向展开研究，探索该领域技术对跟踪性能的影响。
激光扫描技术已经在各类应用中使用了数十年。部分研究者针对激光雷达点云开展了上下文分类研究 [^13] [^14]，他们提出了一种用于点云数据上下文分类的概率方法，还进一步尝试基于分类后的点云检测建筑物目标。但该研究未能提取出具有区分度的特征，因此导致了部分分类错误，我们也因此致力于在该方向得到更理想的结果。
已有研究表明，HDBSCAN [^15] 是一种比DBSCAN更鲁棒的改进型基于密度聚类算法。HDBSCAN无需手动设定DBSCAN所需的半径参数，例如它可以直接将该参数设为无穷大。但我们改进后的EDBSCAN在激光雷达数据集上的工作机制不同，能够实现更准确的跟踪计算。HDBSCAN对欧几里得空间的适配性不佳，且HDBSCAN和DBSCAN都不是完全确定性算法，二者都存在维数灾难问题。我们提出的EDBSCAN和EOPTICS在解决这些问题上发挥了重要作用。
在我们之前的工作[^16]中，我们尝试构建一个基于LiDAR的跟踪系统，实现对行人的可靠跟踪。我们使用DBSCAN算法对数据进行聚类，使用KF跟踪行人的运动路径。我们根据实验结果设置了DBSCAN的不同参数[^17]。在本研究中，我们尝试
---
提升跟踪的准确性。我们对传统的DBSCAN聚类进行改进，得到增强版DBSCAN（E-DBSCAN），并结合改进后的OPTICS算法来获得最优性能。我们发现，使用这两种改进的聚类方法后，我们此前实验的效果得到了显著提升。
### 3. 研究方法
对行人进行跟踪时，传感器的放置位置是一项非常关键的决策。因此，将LiDAR传感器布置在脚踝位置是合理的解决方案。因为LiDAR可以跟踪每个脚踝，这有助于确定行走路径，还能够避免人体遮挡，此外该方案也有其他应用场景。移动机器人通常将LiDAR布置在脚踝高度，用于障碍物检测。
独立追踪单个人体是一项极具挑战的工作。当多人在同一平面行走时，脚踝位置过近容易造成分类错误。图2(a)直观展示了2D LiDAR传感过程。该传感器可输出相对于自身位置，运动脚踝在X、Y坐标系下的水平距离。这些距离值会被绘制在坐标系中，得到如图2(b)所示的数据。我们对这些距离值采用单聚类方法逐个识别脚踝，最终按顺序将每一对配对的脚踝对应到一个行人。从图2(b)中可以看到，多名行人正在平面上行走。在图2(c)中，红色标记的圆圈标出了一处错误识别：两个距离很近的脚踝被判定为同一个行人。第四张子图即图2(d)给出了不同的聚类计算结果。这就是聚类异常，会导致误分类。
利用LiDAR获取传感数据并实现更优的分类效果是我们的首要研究目标。我们反复将传感器放置在10厘米至200厘米之间的不同高度位置进行测试。通常，人体腿长范围在0到100厘米之间。为获取对应数据并分析不同高度的显著影响，我们将LiDAR传感器设置在20厘米高度。我们发现，该高度能提供最准确的追踪数据。该方案在单个行人运动追踪上拥有极佳的精度，但在群体运动追踪中我们遇到了瓶颈。判断哪个脚踝属于哪个行人确实是一个非常棘手的问题。我们反复调整传统聚类方法的聚类阈值，但问题仍然存在。为了获得更好的逼近效果和精度，我们引入了一种基于密度聚类的先进追踪方法，该方法能够解决错误聚类的问题。
3.1 感知 我们使用HOKUYO UMT30LX LiDAR传感器进行数据采集。在本次实验中，我们保持传感器固定不动，研究对象为运动物体，此处的物体特指行人。在下图（图3）中，我们将传感器安装在脚踝位置，使用LiDAR采集了时序视频数据。这些数据被存储下来用于后续监测研究。我们应用了多种预处理技术，让数据具备更好的鲁棒性和准确性。图片的第二部分展示了一张基于LiDAR生成的图像，表面边界用白色标记标出。图中居中的白色标记点代表特定帧内行人的脚踝位置。我们尝试去除采集图像中的白色背景，这使得我们只需要处理帧内的脚踝位置，不会受到多余噪声的干扰。我们使用背景减除法去除边界，之后得到了每个时刻仅标注出脚踝的帧。这些帧的序列就组成了一段基于LiDAR的视频。
从预处理数据中提取特征是本研究的另一项核心问题。我们选取连续帧用于特征
Fig. 2. (a) Different distance values of ankles; (b) LiDAR-based ankle positions on the frame; (c) considering close ankles as a person; and (d) ankles in different orientations make a cluster
Fig. 3. Image sensing using LiDAR sensor and preprocessing
选择。每一条时序数据对应每一帧中的各个脚踝位置。我们将一个人的单脚踝运动和双脚踝运动归属于对应同一个行人。但数据采集过程中总会出现各类问题：遮挡、脚踝移动速度过快、行人的全方向移动，所有这些挑战都让本研究变得更为复杂棘手。为了解决这些缺陷，提升系统在时间和计算层面的性能，我们曾考虑在平面的另一方向增设第二台LiDAR传感器。但增设额外传感器会降低系统效率，还会推高安装成本。因此我们调整了实验架构，决定专注于基于单传感器的方案，在这里我们重点开发能够应对所有上述不足的鲁棒算法。
3.2 聚类 本研究的下一阶段工作是对数据进行聚类，从而能够应对所有极端场景。我们选用基于密度的算法。基于密度的聚类可以找到任意形状的簇，也能够处理噪声。在基于密度的聚类方法中，簇是依据与稀疏区域区分开的密集区域生成的。这类算法基于数据密度运行，无需提前做出假设，完全根据数据密度生成簇。DBSCAN是我们在本研究中使用的经典基于密度聚类算法之一，我们还在研究中应用了OPTICS算法。两种算法在行人跟踪任务中都表现优异。尽管这两种算法有诸多实际优势，但仍存在一些需要解决的局限。我们尝试解决这些问题，并对这两种算法提出了改进方案，即增强型DBSCAN和增强型OPTICS
---
这两种算法是对传统算法的改进，能够在基于LiDAR的跟踪任务中取得更优异的性能。
3.2.1 增强型（E）DBSCAN 基于密度的噪声应用空间聚类（DBSCAN）旨在定位非球形簇。DBSCAN的稠密邻域由两个特定参数决定：第一个是半径$\epsilon$，即定义邻域的精确距离，第二个是被视为邻点的最小点数（minPts）。DBSCAN是基于激光雷达（LiDAR）数据实现聚类的一项出色进展。但要构建鲁棒的跟踪系统，DBSCAN仍存在一些会降低跟踪性能的缺陷。初始参数（$\epsilon$、minPts）的选择是该算法的一个短板，此外它的$O(n^2)$计算成本很高，会影响实时计算。与普通分层算法的其他缺点相比，我们发现DBSCAN是性能更优的算法，在LiDAR数据处理中尤其突出。针对本文的脚踝跟踪任务，我们成功设置了适配的初始参数，该参数在大多数情况下都能稳定工作。此外，我们使用LiDAR传感器并应用背景减除法，减少了数据拥塞和处理负荷。因此，我们的系统功能完备，可实现实时行人跟踪。
我们在使用DBSCAN时遇到了另一项难题。当多个人在平面上行走时，他们的脚踝位置会相互靠近。正如我们此前所述，DBSCAN基于minPts和$\epsilon$生成聚类，不同人的脚踝会靠得极近，使得两个来自不同人的脚踝的距离差值低于聚类半径，看起来就像是同一个人的脚踝。此时DBSCAN会失效：它会将范围内所有距离较近的脚踝归为同一个簇，哪怕这些脚踝分属于不同的人。调整半径阈值或许能解决这一问题，但在实际应用中，半径无法根据人群规模和移动情况做出调整。因此，我们必须调整DBSCAN的结构，使其更好地适配我们的应用场景，解决这种数据过拟合的缺陷。
从图4的图像中，我们可以清楚了解DBSCAN的缺陷。左上方最顶部的图像展示了帧中不同的脚踝位置，对应的最底部图像根据DBSCAN参数minPts和半径$\epsilon$生成聚类。我们此处设置参数为minPts = 20和$\epsilon = 900$，这意味着DBSCAN在半径$\epsilon$范围内获得至少20个点时，就会生成一个聚类，并判定为一个人。从第一张图中我们能看到有四个人在平面上行走，但对应的最底部图像检测出了五个人。原因在于第五个人的两个脚踝间距大于我们的阈值$\epsilon$，但每个脚踝本身都满足成为一个聚类的条件，因此生成了两个聚类，被显示为两个人。两帧之后，顶行的第二幅图重新计算了距离，生成了四个聚类，对应结果显示在其下方的最底部图像中。再过两帧，顶行的第三幅图中行人之间的距离变得更近，他们的脚踝相互遮挡。这种情况下，两个或多个行人之间的脚踝间距小于$\epsilon$，因此生成了一个聚类，这是数据过拟合的一个示例。第二行的最后一幅图得到的结果是两个人，这就是直接使用DBSCAN的一个缺陷。
为了解决这些问题，我们为DBSCAN算法增设了第三个参数。我们在此引入最大点数参数（maxPts），同时保留原先的两个参数（minPts和$\epsilon$）。设置该参数可以快速减少数据过拟合和固定半径带来的问题。假设10个点即可构成一个脚踝，那么至少20个点
Fig. 4. The uppermost images show an ankle position on the frame—Lowermost images pointing persons with the handler
我们需要创建对应单个人的聚类。此时DBSCAN的minPts可设置为20。此外，我们可以使用欧氏距离，将两个点之间的距离$\epsilon$设为900个单位。如果两个人的四个脚踝距离较近，且它们的点间距在900个单位以内，那么传统DBSCAN会将这些点归为同一个聚类。DBSCAN只对形成聚类所需的最小数据量作出要求，并不对最大数据量设限，但基于激光雷达（LIDAR）的追踪在这种设定下会失效。
如果我们新增另一个参数maxPts，例如将其设为50，这种改进后的DBSCAN就只会将点数量在20–50之间的数据点归为一个聚类。一方面，少于20个点无法形成聚类；另一方面，如果点数量超过最大值50，算法也会丢弃该聚类。引入该参数可以解决数据过拟合问题。如果超过两个脚踝距离较近，且它们的总点数超过maxPts，增强型DBSCAN（Enhanced DBSCAN, EDBSCAN）就不会接受该聚类，而是直接将其丢弃。但此时仍存在另一个问题：需要从过拟合数据中重新创建聚类。在这里，EDBSCAN会立即调整它的半径$\epsilon$，将半径大幅缩小，仅在之前被丢弃的点中（而非整个数据集中）寻找新的聚类。这一步骤会持续进行，直到过拟合问题得到解决。整个过程中minPts和maxPts的值保持不变，仅缩小半径。
在图5中，半径$\epsilon$范围内的圆内存在大量点。由于该聚类的数据点数量超过了maxPts，EDBSCAN会将其丢弃。该方法印证了这样一种场景：多人在LiDAR传感器前方行走时，脚踝位置相距较近。我们提出的增强型DBSCAN（Enhanced DBSCAN）可以解决传统DBSCAN的瓶颈问题。EDBSCAN的另一项创新设计是可变半径选择。由于初始半径选择会引发数据过拟合问题，我们可以大幅缩小半径，同时保持minPts和maxPts参数与原设置一致。这样就可以在拥挤场景中重新识别出每个人。在下图（图6）中，半径$\epsilon$被缩小为$\epsilon'$，此时算法可以在初始minPts为20、maxPts为50的设置下找到新的聚类，仅保留满足条件的聚类。在此场景中，尽管不同人员的脚踝相距极近，存在误分类的可能性，但缩小后的半径可以快速解决该问题，只有距离非常近的点才会形成一个聚类。
在DBSCAN中设置最大点数（maxPts）参数，我们还可以处理虚假聚类问题。假设平面上存在一个移动对象，它并非脚踝。如果该对象生成了满足要求的
---
Fig. 5. Enhanced DBSCAN (EDBSCAN) mechanism
Fig. 6. Reduced radius of EDBSCAN
Fig. 7. Anomaly in tracking without using maxPts
minPts和$\epsilon$条件，传统DBSCAN会将其判定为平面上移动的人员，进而生成一个聚类。我们提出的maxPts参数可以轻松处理该问题。该算法基于运动历史图像生成聚类，如果聚类内点数量超过maxPts，且该聚类未连续出现在连续图像中，就会被作为虚假聚类丢弃。
假设在图7中，共有四帧数据记录了一个人在激光雷达传感器前方行走的某一时刻。第一帧是传感器捕获的激光雷达数据，第二帧展示了该时刻的运动历史图像。当使用传统DBSCAN跟踪行人时，第三帧出现了跟踪异常。从前几帧可知，该帧中只有一个人在行走，但由于垃圾数据和物体运动误判，DBSCAN在该帧中额外检测出了两个人。当我们使用取值为300的maxPts参数时，我们提出的EDBSCAN消除了错误分类，与原始数据一致，仅在帧中检测出一个行人。
3.2.2. 增强型（E）OPTICS算法
OPTICS与DBSCAN非常相近，但采用了不同的处理流程，是一种基于数据密度对空间数据进行聚类的新方法。当数据密度存在变化时，DBSCAN的聚类性能较差。OPTICS解决了这一缺点，能够对不同密度的数据生成合理的聚类。它的工作方式与前文的算法类似，会将输入数据中的所有点划分为核心点、边界点和离群点。OPTICS同样需要两个输入参数：待考虑的最大距离即半径$\epsilon$，以及生成聚类所需的最小点数minPts。核心点Q与S之间的可达距离$R_{d}$可通过下式计算：
$$ R_{d}=\max\left\{\mathrm{Dist}(Q,S),\mathrm{Core}\mathrm{Dist}(Q)\right\} $$
OPTICS可在同一聚类上运行，能够识别聚类内部的子聚类。该方法可以挖掘中心聚类内部各聚类的内在规律。我们对OPTICS进行了改进，提出了增强型OPTICS，命名为EOPTICS，该算法在原有minPts和Radius $\epsilon$ 的基础上，新增了一个表示最大数据点数的参数maxPts。这一思路非常贴合我们的实际应用场景，即基于LiDAR的追踪任务。要形成一个聚类，数据点需要满足minPts、最大点数（max pts）以及半径 $\epsilon$ 的约束。我们的方法构造基于密度的聚类时，要求聚类包含的数据点数量不超过最大点数限制，其余流程与原始OPTICS算法保持一致，同样会进行聚类密度校验。该方法是对OPTICS算法明确的扩展和重大修改。在多个行人脚踝距离较近的高密度区域，传统OPTICS算法会将所有数据点合并为一个无法使用的单一聚类，我们的方法解决了该问题。此次对OPTICS的改进还有另一项显著优势：如果聚类包含的数据点数量超过最大点数限制，我们的算法会舍弃外层的主聚类，转而计算基于核心距离和可达距离的内层子聚类。这些内部聚类有助于确定平面上脚踝的位置。之后，我们的EOPTICS算法会大幅缩小半径 $\epsilon$，重新计算聚类，并再次得到内层子聚类，以此分析主聚类内部数据的关联性。该方法有助于找到对应平面上单个人的关联子聚类。
在所有场景下，聚类参数都将根据若干关键准则计算得到：
a 如果聚类半径仅生成一个聚类，算法会计算核心距离并寻找子聚类。如果子聚类数量超过一个，则舍弃外围的主子聚类，将内部子聚类作为主聚类。如果仅生成了少数几个满足minPts要求但点数量极少的聚类，算法会增大其半径 $\epsilon$ 并重新计算聚类。
b 如果对于n个minPts，EOPTICS生成了m个聚类，满足$m \geq \frac{D}{2}$，则舍弃该聚类，将minPts重新计算为minPts = 2 * minPts < maxPts。该过程会一直持续到$m < \frac{D}{2}$，其中D为数据点。
c 如果使用半径$\epsilon$未找到任何聚类，EOPTICS会增大$\epsilon$并重新尝试计算聚类。如果找到超过一个聚类，则保留结果；否则舍弃。
在图8（Fig. 8）中，我们可以看到EOPTICS算法的传统实现方案，该方案与OPTICS算法相近。它从传感器获取脚踝位置数据并完成聚类。左图展示了某一帧的场景：四个人在LiDAR传感器前方移动，基于KF的追踪算法根据数据对所有目标人员进行追踪。参数maxPts的设置是一个启发式过程，在我们的实验中，该参数的取值范围为50到300个点，具体取决于人群规模和地面采样频率。
图中也标注出了每个人的移动方向。一帧之后，有一个人的一只脚踝移出了传感器的检测范围，同时两个人距离变近，二人脚踝之间的距离落在我们设置的半径范围内。传统OPTICS
---
Fig. 8. EOPTICS with LiDAR data; (a) ankle positions in front of the sensor, (b) KF-based tracking
Fig. 9. OPTICS; (a) one frame later, ankle positions, (b) corresponding Kalman-based tracking
此处仅生成了两个聚类，一个聚类因minPts参数的限制被省略，本例中仅一个脚踝无法满足minPts的要求。第二个聚类生成时无异常，对应图9(b)中的ID 275。关键情况出现在下一区域：这里有两个人相互靠近。在上一帧中，二人已被准确识别，ID分别为267和278。但普通OPTICS在此仅生成了一个编号为267的聚类，将二人显示为同一个人，这就是OPTICS的缺陷。
我们提出的EOPTICS针对这一不足发挥了极为关键的作用。在下图（图10）中可以看到，EOPTICS相比OPTICS有非常显著的改进：当帧中KF识别出三个人时，EOPTICS成功得到了三个聚类。同样在这里，OPTICS拒绝生成一个聚类，EOPTICS也会出于同样的原因拒绝生成该聚类，原因都是数据点数量少于参数minPts的要求。第二个聚类的生成情况和此前一致。
此处数据点分别满足大于minPts、小于maxPts的范围要求。相比OPTICS，EOPTICS对第三个聚类进行了修正。当OPTICS将两个人的脚踝点仅合并为一个聚类时，EOPTICS不会将其当作单个聚类处理。该算法的核心思路是同时考虑minPts和maxPts两个参数。在当前场景下，数据点满足minPts条件，但数据点数量超过了maxPts的限制。由于不满足生成条件，EOPTICS会停止生成该聚类，进入下一阶段处理。它会缩小半径$\epsilon$，仅使用这些排序后的数据再次尝试生成聚类。缩小$\epsilon$后，只有相关的脚踝点满足所有条件，最终生成了两个独立的聚类。在右侧图中，编号267和278标识了这两个聚类。
3.3. 跟踪 我们研究的下一步是跟踪。KF对聚类的重心进行跟踪。预测方程和修正方程是KF的基础。
$$ Forecast,F(n)=XF(n-1)+S(n-1) $$
$$ \mathrm{Revise},\boldsymbol{R}(n)=\boldsymbol{Y}\boldsymbol{F}(n)+\boldsymbol{M}(n) $$
Fig. 10. EOPTICS, (a) ankle positions, (b) KF-based tracking
式中，$F(n)$和$R(n)$分别为预测估计量和修正测量变量，X和Y分别为状态转移矩阵和测量矩阵。S表示系统噪声，M表示测量噪声。将输入的运动历史图像作为输入，KF会对其进行预测。若检测成功，则将其送入修正环节。若需要进行修正，则会再次将结果反馈回预测环节。该过程会持续进行，直至得到理想的跟踪结果，最终完成对行人的跟踪。
### 4. 结果与讨论
由于目前不存在成熟的基于LiDAR的行人跟踪数据集，我们自行构建了实验用数据集。基于LiDAR的跟踪一直面临数据失配和精度较低的问题。我们所使用的LiDAR传感器在该场景下这类问题尤为突出。最初我们使用录制的视频开展实验，得到了可观的结果。随后我们对系统进行了改进，使其支持实时跟踪。有趣的是，我们的系统取得了与基于视频的行人跟踪系统相当的提升效果。
我们邀请了不同的男性和女性参与者开展实验，另设一组参与者参与本次实验。我们为该分析选定了五个主要类别：独立行走、独立跑步、仅踝关节运动、组合行走和组合跑步。我们将自研的EDBSCAN算法应用于个人和群体的轨迹追踪中。图11重点展示了组合行走与组合跑步的测试结果。第一帧中，我们可以看到三个人正行走在LiDAR传感器前方，我们的渐进式方法成功追踪到了这些人，结果显示在最右侧的图中。第二幅图里，有四个人正在跑步，我们的自研方法成功识别出了所有目标。相较于传统DBSCAN，EDBSCAN实现了十分显著的改进：当多个踝关节距离较近时，它能够避免误分类，maxPts参数会剔除异常聚类并重新完成计算。
我们还在实验中测试了EOPTICS算法。将OPTICS改进为EOPTICS后，在我们的系统中取得了十分显著的效果。我们将该算法应用在同一数据集上，发现EOPTICS在逐帧分析中的表现最优。在图12中，我们将三种手势放在一起测试，发现EOPTICS的性能优于以往的DBSCAN和OPTICS。图中最左侧图片展示了帧内的踝关节位置，对应的最右侧图片展示了基于KF的运动分析和追踪结果。如果某一单独帧出现误分类，EOPTICS会通过其参数更新技术在后续帧中解决该问题。该方法同样适用于不同群体的组合行走与组合跑步场景。
我们还解决了遮挡问题。当一只脚踝位于另一只脚踝前方时就会发生这种情况，障碍物会导致LiDAR无法获取后方脚踝的信号。在人体跟踪系统中，这种遮挡问题会引发故障，有时会
---
Fig. 11. EDBSCAN based group peoples tracking with LiDAR sensor
Fig. 12. EOPTICS based on individual tracking with LiDAR sensor
Fig. 13. Tracking and occlusion handling, a frame by frame analysis
无法在该场景下实现准确的人体跟踪。我们提出的基于LiDAR的跟踪系统能够处理这一问题。在图13中，假设两帧之前，我们提出的算法计算了脚踝之间的距离，发现该距离大于接受阈值，系统就会将其判定为两个人。在前一帧中，两个目标相互靠近，脚踝间距小于我们设定的半径，系统就会将其更新为一个人。这就是跟踪过程的持续更新。如果任意一帧出现异常，都可以在后续连续帧中得到修正。对于人体跟踪而言，这些出现在单帧或极少帧中的跟踪异常是可以接受的。
类似地，在当前帧中，如果一只脚踝被另一只脚踝遮挡，就无法计算两者的脚踝间距。这种情况由脚踝间距过小或遮挡导致。如果此时半径小于阈值，就不会存在问题，满足判定条件。如果数据点数量少于maxPts参数，系统就会生成一个聚类，并将其识别为一个人。如果多个人距离过近，导致无法测量脚踝间距，且点总数超过maxPts，系统就会舍弃当前聚类，重新计算半径并再次生成聚类。
在表I中，我们展示了不同手势的部分实验结果。本次研究共考虑了五种动作。另一组人员参与了我们历时数分钟的实验。我们在此抽取随机帧用于验证与核对。如下表所示，单人步行和单人跑步实验分别有3人和4人参与，我们随机抽取了44帧和49帧连续帧。基于我们开发的EDBSCAN和EOPTICS算法，我们在该场景下得到了近乎准确的识别结果。
类似地，仅针对踝关节运动的实验中，我们在56帧中获得了52帧和53帧的准确识别，结果表现相当出色。针对步行与跑步组合场景，我们邀请了9名人员参与实验。在群体步行场景下，EOPTICS的表现优于EDBSCAN。而与以往开发的算法相比，我们的算法也取得了令人瞩目的进展。我们的系统在组合跑步场景仍有较大的改进空间。如果一群人快速来回跑动，很难实现极高精度的追踪。我们的实验共采用136帧，其中EOPTICS准确识别了106帧，EDBSCAN准确识别了101帧，两种算法的总耗时分别为32.41 s和27.63 s。我们使用的LiDAR传感器（UTM-30LX）每次扫描耗时25 ms。
我们将本文改进后的算法与传统DBSCAN和OPTICS算法进行了对比。为便于理解，我们在表II中展示了各算法的性能与准确率。对于单人步行场景，四种传统算法和改进算法均表现良好，单人跑步场景也得到了相同的结果。仅针对脚踝运动的场景中，EOPTICS实现了显著的性能提升，它相比其他算法能够处理更多误分类问题，该优势同样存在于群体步行和跑步场景中。几乎在所有测试场景下，EOPTICS都能取得更优的结果，EDBSCAN的表现也优于此前应用的各类基于密度的算法。
现有研究已经明确，传统的核心聚类算法并不适用于基于LiDAR的人员跟踪任务。我们此前针对该问题开展了相关实验，并在本文展示了实验结果。EDBSCAN和EOPTICS均可适配这类数据集，此外，对DBSCAN和OPTICS的改进并未提升算法复杂度：最坏情况下的复杂度仍为$O(n^{2})$，且不进行矩阵补全时，仅需要$O(n)$内存空间。
我们将本文方法与当前先进方法的精度进行了对比（表III）。不同研究人员使用不同的聚类方法和数据集开展人员追踪研究，而本文在此展示我们改进后的EDBSCAN和EOPTICS方法的精度。2011年，Rusu等人[^11]提出了一种基于欧几里得聚类的追踪策略，他们在聚类阈值为0.5 m的条件下获得了64.5%的准确率。2016年，深度聚类（Depth Clustering）[^18]方法被应用于同一任务，在$10^{\circ}$输入下得到了39.2%的精度。2017年，另一种方法运行聚类（Run Clustering）[^19]被用于三维追踪，得到了51.7%的准确率。2020年，在线学习（Online Learning）[^20]提出了自适应阈值选择方法，得到了89.8%的准确率。我们此前的方法仅使用了DBSCAN
---
Table I. Experimented results for EDBSCAN and EOPTICS
| Gestures | Persons | Frames | Correctly Identified by EDBSCAN | Correctly Identified by EOPTICS |
| Individual walking | 3 | 44 | 44 | 44 |
| Individual running | 4 | 49 | 48 | 48 |
| Ankle movement | 5 | 56 | 52 | 53 |
| Combined walking | 9 | 131 | 123 | 127 |
| Combined running | 9 | 136 | 101 | 106 |
Table II. Comparison of EDBSCAN and EOPTICS with DBSCAN and OPTICS
| Gestures | Accuracy with DBSCAN | Accuracy with OPTICS | Accuracy with EDBSCAN | Accuracy with EOPTICS |
| Individual walking | 99% | 99.5% | 100% | 100% |
| Individual running | 98.01% | 97.86% | 97.96% | 97.96% |
| Ankle movement | 92.07% | 92.02% | 92.86% | 94.64% |
| Combined walking | 93.71% | 93.81% | 93.89% | 96.95% |
| Combined running | 71.87% | 72.11% | 74.26% | 77.94% |
Table III. Comparison with existing approaches and precisions
| Approach | Cluster threshold | Precisions |
| Euclidean clustering [^11] | 0.5 m | 64.5% |
| DBSCAN [^16] | Adaptive | 93.7% |
| Depth clustering [^18] | $10^{\circ}$ | 39.2% |
| Run clustering [^19] | Params $_{SLR}$ | 51.7% |
| Online learning [^20] | Adaptive | 89.8% |
| Our (EDBSCAN) | Adaptive | 93.9% |
| Our (EOPTICS) | Adaptive | 96.9% |
，在步行人员追踪中获得了93.7%的准确率。本研究提出了两种全新方法EDBSCAN和EOPTICS，结合自适应阈值选择机制，在相同数据集上分别获得了最高93.3%和96.9%的准确率。
### 5. 结论
本研究通过独家引入经预先改进的基于密度的聚类方法，实现了对LiDAR传感器人体追踪的增强理解。我们应用了全新参数，其协同扩展优化了这些算法，尤其适配LiDAR数据。尽管目前基于视频和多传感器的人体追踪技术已得到改进，但这类技术存在需要警惕的隐私问题。此外，这类改进后的追踪系统落地实现需要更高的计算量与成本。我们充分考量了所有这些约束条件，并将本文方法与其他现有顶尖技术进行了对比。较低的安装成本与计算成本、运行时处理能力以及算法的自适应参数选择令我们的系统具备出色的鲁棒性。我们精心整理的自有数据集也让该系统更便于其他研究者使用。
我们计划将该技术应用于可独立实时检测人体的移动机器人。该方法除可应用于护理机构场景外，还可开发出多种商业用途。我们后续计划开发基于LiDAR的步态识别系统。未来可引入DNN架构，解决大样本学习训练过程中存在的诸多不足。
## 参考文献
(1) Brubaker MA, Sigal L, Fleet DJ. 基于视频的人体追踪. 收录于《环境智能与智能环境手册》，Nakashima H, Aghajan H, Augusto JC（编）. Springer：马萨诸塞州波士顿；2010.
(2) Devarakota PR, Castillo-Franco M, Ginhoux R, Mirbach B, Kater S, Ottersten B. 基于三维骨架、利用距离图像实现的人头检测与追踪. IEEE Transactions on Vehicular Technology 2009;58(8):4064-4077.
(3) 麦克劳克林 N, 林孔 JMD, 米勒 P. 用于基于视频的行人重识别的循环卷积网络. IEEE计算机视觉与模式识别会议（CVPR）论文集，内华达州拉斯维加斯，2016年；1325–1334.
(4) 罗伯托·亨舍尔, 蒂莫·冯·马卡德, 博多·罗森哈恩. 利用视频和IMU同时实现多人识别与跟踪. IEEE计算机视觉与模式识别会议（CVPR）研讨会论文集，2019年.
(5) 克佩 E, 巴托尔迈 M, 利尔斯 A, 希勒 J. 用于行人跟踪与室内定位的基于无线电的多传感器系统. 第九届定位、导航与通信研讨会论文集，德累斯顿，2012年；180–186.
(6) 盖 W, 齐 M, 马 M, 王 L, 杨 C, 刘 J, 边 Y, 德梅洛 G, 刘 S, 孟 X. 基于单RGB-D相机利用阴影实现多人跟踪. 《传感器》2020年；20(4):1056.
(7) 克里斯托迪亚斯 CM, 乌尔塔松 R, 达雷尔 T. 面向多视图目标识别的分布式编码无监督特征选择方法. IEEE计算机视觉与模式识别会议（CVPR）论文集，阿拉斯加州安克雷奇，2008年；1–8.
(8) 库马尔 S, 马克斯 TK, 琼斯 M. 利用低成本红外热传感器改进行人跟踪. IEEE计算机视觉与模式识别会议（CVPR）研讨会论文集，俄亥俄州哥伦布，2014年；217–224
(9) 贝内德克 C, 高莱 B, 纳吉 B, 扬科 Z. 4D监控系统中基于Lidar的步态分析与活动识别. IEEE视频技术电路与系统汇刊 2018年；28(1):101–113.
(10) M 埃斯特, H-P 克里格尔, J 桑德, X 徐. 一种基于密度的算法，用于在大规模空间数据库中发现簇
---
噪声。第二届知识发现与数据挖掘国际会议论文集（KDD'96），AAAI出版社，1996年；226–231。
(11) Rusu RB、Cousins S。3D已落地：点云库（PCL）。IEEE机器人与自动化国际会议论文集，上海，2011年；1–4。
(12) Wang C、Ji M、Wang J、Wen W、Li T、Sun Y。一种带有自动eps估计的改进型DBSCAN LiDAR数据分割方法。《Sensors》2019；19(1):172。
(13) Hollaus M、Wagner W、Eberhöfer C、Karel W。复杂高山环境运行约束下基于LiDAR数据得到的大范围冠层高度精度研究。《ISPRS Journal of Photogrammetry and Remote Sensing》2006；60(5):323–338。
(14) Niemeyer J、Rottensteiner F、Soergel U。城区LiDAR数据的上下文分类与建筑物目标检测。《ISPRS Journal of Photogrammetry and Remote Sensing》2014；87:152–165。
(15) Campello RJGB、D Moulavi、J Sander。基于分层密度估计的密度聚类算法。亚太知识发现与数据挖掘会议论文集，Springer，柏林、海德堡，2013年。
(16) Hasan M、Hanawa J、Goto R、Fukuda H、Kuno Y、Kobayashi Y。用于步态分析的脚踝高度2D LiDAR行人跟踪。《人工智能、软件与系统工程进展》，AHFE 2020。智能系统与计算进展，第1213卷，Springer，Cham，2020
(17) Amini A、Wah TY、Saboohi H。基于密度的数据流聚类算法综述。《Journal of Computer Science and Technology》2014；29:116–141。
(18) Bogoslavskyi I 和 Stachniss C. 面向在线运行的稀疏三维激光扫描的快速距离图像分割，发表于2016年IEEE/RSJ智能机器人与系统国际会议（IROS）论文集，2016；163–169。
(19) Zermas D, Izzat I 和 Papanikolopoulos N. 三维点云快速分割：自动驾驶汽车领域激光雷达数据的处理范式，发表于2017年新加坡IEEE机器人与自动化国际会议（ICRA）论文集，2017；5067–5073
(20) Yan Z, Duckett T, Bellotto N. 基于三维激光雷达人体检测的在线学习：点云聚类与分类方法的实验分析. 自主机器人（Auton Robot） 2020; 44:147–164.
（非会员），日本埼玉大学人机交互实验室博士研究生，同时兼任孟加拉国库米拉大学计算机科学与工程系教师，研究方向为人机交互与计算机视觉。
（非会员），埼玉大学理工学研究科学生，2020年于埼玉大学获得信息与计算机科学工学学士学位，研究方向为人体感知方向的计算机视觉。
后藤 陆（Riku Goto，非会员），埼玉大学理工学研究科学生，2019年于埼玉大学获得信息与计算机科学工学学士学位，研究方向为人体感知方向的计算机视觉。
（on-Member）2015年于日本埼玉县埼玉大学获得信息与计算机科学博士学位。现任埼玉大学理工学研究科助理教授，研究方向包括目标识别与人机交互。
（Member）是埼玉大学荣誉教授。他1982年在东京大学取得博士学位，1988年前往美国卡内基梅隆大学担任访问研究员。1993年至2000年于大阪大学任副教授，之后加入埼玉大学信息与计算机科学系任教授。研究方向包括计算机视觉、智能机器人、人机交互。
（Non-Member）2007年于东京大学取得博士学位，随后加入埼玉大学信息与计算机科学系担任助理教授，现任埼玉大学教授。研究方向包括用于人体感知的计算机视觉及其在HCI和HRI中的应用。
