# 基于自下而上-自上而下检测器的三维人体跟踪
Luciano Spinello、Matthias Luber 与 Kai O. Arras
德国弗莱堡大学社会机器人实验室 {spinello, luber, arras}@informatik.uni-freiburg.de
摘要——人体检测与跟踪是人类环境中机器人和自动驾驶汽车的核心组件。现有研究此前主要使用图像或二维测距数据完成该任务，本文则利用三维测距数据解决这一问题。我们的方法中，自上而下分类器从自下而上检测器生成的候选假设中进行筛选，二者均基于多组提升特征构建。自下而上检测器从针对人体不同高度层的一组专用分类器中学习分层人体模型，所有分类器共同在连续空间中投票，该空间中的模态代表检测候选，每个检测候选都会对数据提出一个分割假设。在自上而下步骤中，我们使用在提升体积镶嵌的体素中计算得到的特征对候选进行分类。我们学习得到最优体积镶嵌，这使得该方法能够稳定处理稀疏采样的关节物体。随后我们将该检测器与三维跟踪结合，采用多目标多假设跟踪方法。该方法既不需要地平面假设，也不依赖背景学习。
在人口稠密城市环境下的实验结果表明，该方法可实现三维跟踪，且在20米范围内都能实现高鲁棒性人体检测，等错误率至少达到93%。
## 一、引言
人体检测与跟踪是人口稠密环境中移动机器人和智能汽车的核心能力。该领域大多数相关研究都使用视觉完成这一任务，而测距传感是一种极具优势的传感器模态，因为它精度高、视场大，对光照变化和振动都具有鲁棒性，后两点对于移动观测平台而言尤为重要。
本文解决两个问题：三维测距数据中的人体检测，以及三维空间中的人体跟踪。我们在之前三维人体检测工作[^1]的基础上，增加了跟踪阶段，并在检测流程中新增了自上而下步骤。该步骤旨在减少误检，这类误检通常出现在距离传感器较远、采样稀疏的人体身上。我们进一步将检测与跟踪结合，给出了能够估计三维空间中多个人体运动状态的跟踪器结果。为此，我们采用了由Reid [^2]和Cox等人[^3]提出的多假设跟踪方法（MHT）。实验中我们将本文方法与三维测距数据人体检测的相关技术进行了对比，特别是旋转图像[^4]和基于模板的分类方法。
目前针对三维人体检测与跟踪的相关研究较少，已有许多研究者使用二维测距数据开展该任务。在早期工作[^5]、[^6]、[^7]中，研究人员使用专用分类器检测人体，在扫描数据中寻找运动的局部极小值。首个原理性的学习方法
Fig. 1. Two persons are detected and tracked in 3D, one is descending a flight of stairs. The z axis in the figure is magnified for clarity.
Arras等人已开展了相关研究[^8]，该研究通过提升一组几何和统计特征得到了二维点云分类器。由于仅使用单层二维距离数据天然存在性能上限，已有多位学者采用多个共面二维激光扫描仪开展研究[^9]、[^10]、[^11]。在三维数据行人检测领域，Navarro等人[^12]将三维扫描压缩为虚拟二维切片，以检测地面上方的显著垂直目标。他们将窗口与数据主方向对齐，计算一组特征，并使用多个支持向量机对行人分类。Bajracharya等人[^13]通过处理垂直目标，基于固定行人模型提取点云的一组几何与统计特征，在立体视觉生成的点云中检测行人。上述两种方法都属于自上而下的检测流程。
本文方法在多个方面扩展了现有顶尖技术。首先，上述所有现有方法都需要地平面假设，这导致它们无法成为真正的三维方法，而本文方法不需要该假设。我们将自上而下的分类器与自下而上的检测器结合，并量化了这种结合带来的性能提升。随后我们将本文方法与两种成熟的三维目标检测技术（旋转图像和基于模板的分类）进行对比，结果表明，对于最远20米处的行人，本文方法的等错误率（EER）可达至少93%，性能明显优于其他对比技术。最后，我们将本文检测器与三维跟踪技术结合。
本文结构安排如下：下一节将介绍结合自下而上与自上而下的检测方法，包括学习阶段和分类阶段。第四节介绍跟踪方法，第五节给出定量对比与实验结果，第六节总结全文。
### 二、三维行人检测的自下而上方法
本节我们简要总结[^1]提出的自下而上检测器。首先我们对相关术语进行定义。我们所说的自下而上
---
Fig. 2. Overview of the approach. The 3D range data are first processed by the bottom-up detector that generates candidate detection hypotheses (gray). They are verified by the top-down procedure. Confirmed detections (green) are finally tracked using a multi-hypothesis tracker (MHT).
指的是这样一种由局部到整体的框架：从二维距离数据的局部分割片段出发，逐步处理得到三维空间中的检测假设。而自上而下指的是另一种由整体到局部的流程：从三维空间中预先定义的体积区域以及该区域内的全部数据出发，逐步处理得到该区域数据的分类结果。
[^1]中提出的方法基于如下观察：大多数三维测距设备都是以二维数据切片或二维数据线（通常为非共面）的形式获取三维点云。这类设备包括本文使用的Velodyne HDL-64E、Alaska XT，或是安装在转台上的二维激光扫描仪。这一特性让我们可以在第一步复用已经成熟、经过验证的二维距离数据行人检测技术，再将这些结果结合得到三维检测器。
### A. 学习阶段
作为第一步预处理，每条扫描线会通过跳距聚类（Jump Distance Clustering, JDC）分割为多个片段。每当两个连续点之间的距离超过阈值$\theta_{d}$时，JDC就会初始化一个新片段，最终将原始数据缩减为数量更少的多个片段。随后，每个二维片段会通过一组几何特征和统计特征进行描述，该步骤一共提取17个特征。这些特征已在[^8]、[^14]和[^1]中进行了介绍，例如包括紧致度、凸度、曲率、圆度、平滑度等度量。
为了应对人体关节运动与形状的高度可变性，我们采用基于部件的方法，将人体划分为K个不同的高度层。对于每个被称为部件$\pi^k$的高度层，我们构建一个分类器，最终得到一组K个独立的部件分类器，每个分类器专门针对特定高度层进行优化。所有扫描线中落入对应部件的分段都会参与对应分类器的训练。我们在该任务中使用AdaBoost [^15]，这是一种知名的机器学习技术，已被证实在二维测距数据的人体检测任务中十分有效 [^8]。
为了组合各部件输出的单独分类结果，我们采用投票模型，该模型的设计大致受到隐式形状模型方法的启发 [^16]。为了训练该投票模型，对于训练集中属于部件$S_i$的每个分段$\pi^k$，我们存储从分段中心到人体中心的三维位移向量。随后收集部件$\pi^k$对应的所有位移向量，采用平均连接凝聚聚类方法对其进行聚类，得到的向量即为一票。每个聚类得到的投票都会被赋予一个权重（详见 [^1]），从而让关节运动变异性更高的部件（例如足部）获得更低的投票置信度。
最后，为了在三维空间中对人体进行实用化表示，我们从所有人样例中计算得到平均包围框$\bar{\mathcal{B}} = (\bar{w}, \bar{d}, \bar{h})$，其中$\bar{w}, \bar{d}, \bar{h}$分别表示平均宽度、深度和高度。对于自上而下的检测器，我们将该体积绕经过传感器原点与假设中心的直线的方位角$\beta$旋转，完成对齐（参见图3右侧）。
### B. 检测阶段
在评估阶段，我们对新获取的扫描数据执行JDC分割步骤，得到一组分段。对于每条激光线中的每个分段，我们计算其特征集合，并使用全部K个经提升的部件分类器对其分类。随后我们基于弱分类器的加权线性组合，计算该分段属于每个部件的似然度，该似然度即为每个部件分类器所投投票的权重。
当多个部件一致投票时，会在三维投票空间中形成高密度位点，人体检测假设最终就从这些位点中得到。我们使用均值漂移模态估计 [^17] 定位这些位点。检测假设的分数由投票权重、投票数量和为该位点贡献投票的部件数量共同计算得到。更多细节请参见 [^1]。
### III. 三维人体检测的自上而下方法
使用上述方法，我们在传感器距离10米范围内实现了鲁棒的人体检测，EER不低于95%。但在20米范围内，EER下降到了63%，这是因为在该距离下人体的采样十分稀疏，难以与背景杂区区分开来。接下来我们分析造成该问题的原因。
自下而上的检测假设代表了不同高度的多个区段一致投票支持其属于人体一部分的证据。该方法的优势在于，即使发生部分遮挡、仅身体一部分可见时也能够检测出人体。不过该方法的缺点是，杂乱背景中恰好以一致方式投票的区段也会生成错误假设。此外，在某些情况下，该方法会因对称性在投票空间中产生模式歧义。例如，当两名行人并排行走时，每个人不仅会在自身中心位置形成一个强模态，还会在两人中间位置形成一个强模态，该模态来自两人的手臂和腿部。有趣的是，这些问题在基于视觉投票的目标检测技术中也已被发现 [^18]。
为解决这些问题，我们额外提出了一个自顶向下的检测步骤，该步骤仍可处理部分
---
Fig. 3. Left: Tessellations generated to select the best volume subdivision for the top-down classifier. Right: Alignment of the volume for evaluating hypothesis p (top view).
可见身体的情况。该分类器会将自下而上的检测结果作为候选假设，采用扩展三维人体模型对其进行验证。组合方法的概述请参见图2。
## 体积镶嵌
我们的目标是通过在镶嵌体积 $\bar{\mathcal{B}}$ 中计算特征来表征人体的三维形状。我们选择这种细分方法是因为它可以很好地描述局部形状特性。由此引出一个问题：如何将一个体积镶嵌为多个更小体积，这一问题在计算几何中被称为平铺问题。为简化起见，我们仅考虑轴对齐（但非立方体）的体素，这大幅降低了问题的复杂度。由于 $\bar{\mathcal{B}}$ 仍然存在无限多种镶嵌方式，我们定义了一些约束条件：我们预定义了需要考虑的长宽比 $\mathcal{V}$（以避免体素出现极端比例），并定义了体素放大的增量列表 $\Delta\mathbf{v}$。$\mathbf{v}$ 中的每个元素 $\mathcal{V}$ 都是一个宽-深-高三元组 $(w, d, h)$，是某个体素维度的乘法系数。
### A. 学习阶段
训练自顶向下检测器分为两个步骤：学习最优体积镶嵌，以及学习在该镶嵌下计算得到的特征。
最终流程如算法1所示。该算法生成所有可能的体素尺寸（受限于 $\mathcal{V}$ 和 $\Delta\mathbf{v}$），测试它们能否无空隙填充体积 $\mathcal{B}$，并将 $\mathcal{B}$ 细分为规则网格。函数 Tess( $\mathcal{B}$, w, d, h, $\Delta_w$, $\Delta_d$, $\Delta_h$) 使用体素 (w, d, h) 生成 $\mathcal{B}$ 的规则面接触镶嵌，剔除突出体素，并将得到的网格偏移 ( $\Delta_w$, $\Delta_d$, $\Delta_h$)。带偏移调用该函数会得到相互重叠的体素（另参见图3左侧）。该算法生成的 $\mathcal{B}$ 无空隙细分是完备的，即在给定约束下不会遗漏任何一种镶嵌方式。
我们选择这种镶嵌方法是因为我们希望能够描述不同尺度的形状。此外，我们希望体素可以反映人体解剖结构，即能够对应到腿部、头部这类身体部位。由不重叠的固定尺寸体素构成的体积细分更难建立这种对应关系。
// Algorithm 1: Compute all axis-parallel tessellations $\mathcal{T}$ of a volume $\mathcal{B}$.
Input: Volume $\mathcal{B}$, set of allowed voxel aspect ratios $\mathcal{V}$, list of voxel size increments $\Delta\mathbf{v}$.
Output: Set of all possible tessellations $\mathcal{T}$
$\mathcal{T} \leftarrow \{\}$
foreach $\Delta v_{j} \in \Delta\mathbf{v}$ do
foreach $\mathbf{v}_{k} \in \mathcal{V}$ do
$w = \Delta v_{j} \cdot \mathbf{v}_{k}^{w}; d = \Delta v_{j} \cdot \mathbf{v}_{k}^{d}; h = \Delta v_{j} \cdot \mathbf{v}_{k}^{h}$
if $floor(w, w_{\mathcal{B}}) = 0 \land floor(d, d_{\mathcal{B}}) = 0$ $\land floor(h, h_{\mathcal{B}}) = 0$
then
$\mathcal{T} = \mathcal{T} \cup \text{Tess}(\mathcal{B}, w, d, h, 0, 0, 0)$
$\mathcal{T} = \mathcal{T} \cup \text{Tess}(\mathcal{B}, w, d, h, \frac{w}{2}, \frac{d}{2}, \frac{h}{2})$
end
end
end
返回 $\mathcal{T}$
## 三维特征
给定一个细分网格 $\mathcal{T}_j$，我们通过计算每个体素内点的一组几何特征和统计特征来表征形状。所有体素的特征值共同构成了对人体形状的整体描述。设 $\mathcal{T}_j$ 的第i个体素为 $\mathcal{T}_j^i$，则特征 $f_k$ 在形式上被定义为映射 $f_k: \mathcal{T}_j^i \to \mathbb{R}$，该映射接收包含在 $\mathcal{P} = \{\mathbf{x}_1, \ldots, \mathbf{x}_N\}$ 中的N个点 $\mathcal{T}_j^i$，并返回一个实数值。我们使用以下九种特征：
- 点数量：$\mathcal{T}_j^i$ 的基数，记为n。 $f_1(\mathcal{T}_i^i) = n$
- 球形度：该特征通过从 $\lambda_1, \lambda_2, \lambda_3$ 上计算得到的散射矩阵中提取的特征值 $\mathcal{P}$ 的比值来表征球形程度。 $f_2(\mathcal{T}_j^i) = 3 \frac{\lambda_3}{\sum_i \lambda_i}$，其中 $\lambda_1 > \lambda_2 > \lambda_3$。
• 平面度：该特征通过特征值表征平面程度。$f_3(\mathcal{T}_i^i) = 2\frac{\lambda_2 - \lambda_3}{\sum \lambda_i}$。
- 线性度：该特征通过特征值表征线性程度。 $f_{4}(\mathcal{T}_{i}^{i})=\frac{\lambda_{1}-\lambda_{2}}{\sum_{i}\lambda_{i}}$。
- 相对于质心的标准差： $f_5 = \sqrt{\frac{1}{n-1} \sum_i (\mathbf{x}_i - \bar{\mathbf{x}})^2}$，其中 $\bar{\mathbf{x}}$ 是质心。这是一种对紧凑性的度量。
- 相对于质心的峰度：该特征是 $\mathcal{T}_j^i$ 内数据分布的四阶中心矩。 $f_6(\mathcal{T}_j^i) = \sum_i (\mathbf{x}_i - \bar{\mathbf{x}})^4 / f_5(\mathcal{T}_j^i)$。这是一种对峰度的度量。
- 相对于中位数的平均偏差： $f_7 = \frac{1}{n} \sum_i \| \mathbf{x}_i - \tilde{\mathbf{x}} \|$，其中 $\tilde{\mathbf{x}}$ 是独立中位数向量 $\tilde{\mathbf{x}} = (\tilde{x}, \tilde{y}, \tilde{z})$。这是另一种对紧凑性的度量。
• 归一化残差平面度：拟合数据得到的平面的平方误差之和，再除以n进行归一化。$f_8 = \sum_i^n (a x_i + b y_i + c z_i + d)^2$，其中a、b、c、d是由散射矩阵特征值得到的平面参数。这也是一种对平面度的度量。
- 点数量比：该特征度量体素相对于整个体积 $\mathcal{B}$ 的点密度： $f_9(\mathcal{T}_j^i) = \frac{n}{\|\mathcal{B}\|}$。
## 训练
学习自上而下检测器的任务是找到最适配形状特征的细分网格
---
Fig. 4. Selecting the best volume tessellation and features. A set of features is computed on the points within each voxel. All features of all voxels over all tessellations are concatenated in a vector. These features are computed for all people and background samples and they constitute the training set for an AdaBoost classifier. The resulting strong classifier achieves the double objective of selecting the best features and the optimal tessellation. The final tessellation is shown and largely reflects the anatomy of the human articulated body.
三维点云中的人体，并为此选择信息量最大的特征。核心思路是同时优化细分网格和特征（图4）。
第一步，我们通过将边界框 $\mathcal{B}$ 对齐到每个正样本（人体）和负样本（背景）的中心来生成训练数据。该过程得到的结果类似于图像人体检测任务中的多视图数据集 [^19]。对于每个正负样本，都会计算所有细分网格集合 $\mathcal{T}$ 中所有体素的全部特征。这会得到形式为 $\mathbf{s} = (f_1^1, \ldots, f_9^1, f_1^2, \ldots, f_9^2, \ldots, f_1^V, \ldots, f_9^V)$ 的训练向量，其中V是所有细分网格集合 $\mathcal{T}$ 中的体素总数。随后，训练向量连同人工标注的标签 $\{-1, +1\}$ 被用于构建一个以决策桩为弱学习器的AdaBoost分类器。训练集中负样本数量多于正样本，这也符合背景点云形状多样性的特点。正负样本数量的不对等要求调整初始样本权重，我们采用 [^1] 中的方案完成调整。
我们通过不断添加弱分类器训练AdaBoost，直到分类错误率低于1%。最终得到的强分类器实现了双重目标：它为分类任务选择了尽可能最优的特征（其中“最优”由投票权重量化），并隐式选择了$\mathcal{T}_{opt}$对$\widetilde{\mathcal{B}}$的最优细分。之所以说是“隐式”，是因为$\mathcal{T}_{opt}$由已计算出所选特征的体素集合定义。该方法可以灵活地在每个体素中选择任意数量的特征，特征数量越多意味着该体素包含特征特别显著的局部形状。请注意，最优镶嵌也可由来自不同镶嵌的体素混合构成。
对图4中学习得到的最优镶嵌进行解读很有意义。该细分很大程度上反映了人体铰接结构的解剖特征。身体最稳定的部位是肩部和膝上区域，因此这些区域被赋予最高分辨率；对应脚、手、手臂和头部的区域（头部区域的变化由人们身高差异导致）被赋予较低分辨率。此外，嵌入的垂直伸长体素有助于在更粗的尺度上区分人体，将人类的整体形状刻画为细长圆柱体。
### B. 组合检测方法
我们最终将两种检测线索结合，形成了本文提出的自底向上-自顶向下方法（图2）。当新的扫描数据输入后，检测流程首先由自底向上检测器给出一组候选检测假设$\hat{Z}$。随后，将体积$\bar{B}$在这些检测位置进行中心对齐。接下来自顶向下检测器开始发挥作用，在学习得到的最优镶嵌$\mathcal{T}_{opt}$的所有体素中的所有点上计算所选特征集。利用这组特征值，训练得到的强分类器对候选假设进行验证。自顶向下分类器返回正响应的候选构成了时刻t的正检测集合$\mathcal{Z}(t)$。
### IV. 多假设跟踪
前文介绍的检测器是单帧检测器，仅从单次扫描生成检测假设。为了随时间整合这些信息，我们对这些假设进行跟踪，以估计人体的三维位置和运动状态，从而平滑检测器的输出结果。
在跟踪方面，我们采用了由Reid [^2]、Cox等人[^3]和Arras等人[^20]提出的多假设跟踪方法（MHT）的三维实现，该实现能够对完整三维状态和测量结果进行滤波。详细介绍该跟踪方法超出了本文的研究范围，因此我们仅给出简要概述。
MHT属于最通用的数据关联方案，它生成联合兼容分配，随时间对其进行整合，并能够在一致的概率框架内处理航迹的完整生命周期（创建、确认、遮挡和删除）。该算法对测量值与航迹之间所有统计可行的分配，以及所有可能的解释（即测量为虚警或新航迹、航迹为匹配、遮挡或过时航迹）都进行了假设。
在时刻t，每一组可能的赋值与解释都会形成一个数据关联假设$\Omega_i^t$（请勿与检测假设混淆）。由于将测量结果分配给航迹、分配解释标签存在组合复杂度，每个时间步都会存在许多可能的假设。随着时间推移，这些假设会形成一棵指数增长的树，需要进行剪枝。为此，我们会为每个假设计算一个概率，例如该概率可反映测量结果是虚警或是航迹进入视场的概率。随后，仅保留最优的$N_{hyp}$个假设。使得MHT能够成为实时处理流程的关键因素之一在于，这些$N_{hyp}$个假设可以直接在多项式时间内确定。
跟踪器输出一组航迹，用于估计三维空间中行人经过滤波的位置和速度（示例航迹见图1）。
---
Fig. 5. Comparison of the bottom-up top-down detector (BUTD) with the bottom-up (BU) approach in [^1]. The Equal Error Rate (EER) of the BUTD approach is at least 93% over all ranges in both data sets. The performance gain of BUTD over BU is particularly evident for far away detections. Left: Precision recall graph for the Tannenstrasse data set. Right: Precision recall graph for the Polyterrasse data set.
### 五、实验
我们在两个由Velodyne HDL 64E S2激光扫描仪采集的户外数据集上评估了本文算法。第一个数据集名为Polyterrasse，采集自苏黎世联邦理工学院（ETH Zurich）主楼前的大片开放区域，该区域仅允许行人和自行车通行。第二个数据集名为Tannenstrasse，采集自苏黎世市中心一个繁忙的十字路口，场景中包含电车、汽车、行人和自行车。我们为第一个数据集采集了900帧全视角点云，为第二个数据集采集了500帧全视角点云。传感器以5Hz的频率旋转，最大探测范围限制为20米，每次三维扫描大约产生120000个点。
### A. 训练
我们手动标记了每一帧：如果行人包含至少200个点且高度超过1.20米，我们会为其标注包围框。我们还针对包含至少100个点且高度超过1米的行人制作了第二类标注，后续会对此进行说明。我们仅保留高度与均值偏差在±15厘米以内的目标。最终得到了455个行人样本（覆盖所有可能视角，包含静止和行走状态）和6025个背景样本。镶嵌算法的约束条件为$\Delta\mathbf{v} = (0.2m, ..., 0.8m)$和$\mathcal{V}$为$\{1, 1, 2, 5\}$、$\{1, 1, 5\}$、$\{1, 1, 1.25\}$、$\{1, 1, 1\}$、...、$\{4, 4, 4\}$，以及$\{1, 1, 2\}$、$\{1, 1, 3\}$、$\{2, 2, 3\}$、$\{4, 4, 3\}$、$\{4, 4, 2\}$的排列。这些约束得到的最小体素尺寸为0.2米。设置这个相对较大的值是为了，当检测假设相对于物体中心定位不精确时，方便完成检测。自上而下方法的训练误差目标为1%，该目标在使用95个决策桩时达成。
### B. 检测器评估
本节我们展示实验结果，并与其他检测技术进行对比。对于定量分析，我们采用了[^21]提出的无奖励无惩罚策略。该策略规定：当检测结果匹配第二类标注时，既不将其记为真正例，也不将其记为假正例。
在第一个实验中，我们将结合自下而上-自上而下结构的检测器（BUTD）的性能与
Fig. 6. Comparison of the bottom-up top-down detector (BUTD) with the template based approach (TEMP) and the spin image-based bag-of-words approach with several dictionaries (SPIN20-SPIN500) in [0,20m] range. None of the compared technique achieves the performance of BUTD. The SPIN method is apparently not able to generalize the articulated shape of people and/or their sparse representation at large distances. Further, a large dictionary (500 words) leads to overfitting. TEMP achieves good results only in the data set with simple background. Left: Precision recall graph for the Tannenstrasse data set. Right: Precision recall graph for the Polyterrasse data set.
本文提出的自底向上方法见[^1]（图5）。在距离传感器不同范围下，新方法的等错误率（EER，即精确率等于召回率时的指标）分别为：对于Tannenstrasse数据集，距离范围[0, 10m]、[0, 15m]、[0, 20m]对应的EER为95.4%、94.5%、93.4%；对于Polyterrasse数据集，对应结果为97.6%、97.2%、96.2%。BUTD在精确率-召回率性能上明显优于其他方法，尤其是对于距离传感器较远的目标，BUTD比BU技术的性能提升超过30%。因此，自顶向下检测器的主要作用是去除自底向上方法的假阳性结果，同时增强BU方法的弱检测结果。计算机视觉领域的其他自底向上-自顶向下检测器也得到了类似的结论[^16]。我们在两个数据集中都观察到了一致的性能提升，这表明该新算法具备良好的泛化能力。
在第二组实验中，我们将本文提出的方法与两种成熟的3D目标检测技术进行对比：旋转图像（SPIN）和基于模板的分类（TEMP）。在讨论实验结果之前，我们首先介绍这两种技术的实现方案。
TEMP训练：对于每个正训练样本，我们对齐体积$\widehat{B}$（如图3所示），再使用边长为0.2m的立方体单元对其进行划分。这些单元对应模板直方图$\mathcal{H}$的分箱。如果样本中的点落在某个单元内，该单元对应的直方图分箱计数加1。所有正训练样本用于学习模型$\mathcal{H}_m$，之后将直方图归一化到总和为1。
TEMP检测：对于BU方法得到的每个候选检测假设，我们对齐体积$\bar{B}$，然后采用与训练阶段相同的流程计算直方图$\mathcal{H}_z$，最后使用欧氏距离完成直方图匹配$d(\mathcal{H}_m, \mathcal{H}_z)$。
SPIN方法遵循3D词袋检测方案[^22]。该方法将点云表示为局部描述子的集合，忽略描述子的空间分布。
SPIN训练：我们分别在正样本集和负样本集上计算旋转图像描述子。对于每个
---
样本，我们在体积内分辨率为0.2m的规则3D网格中随机抽取160个旋转图像描述子$\bar{\mathcal{B}}$。旋转图像每个维度的分辨率为0.1m。共收集到289415个描述子，我们使用针对大数据集优化的k-means实现对其进行聚类[^23]。聚类数分别设置为20、150、300和500，以此生成多个词词典，每个词对应一个聚类中心。基于这些词得到直方图，统计各个词在当前样本中的出现频率。最终，我们利用所有正负样本的直方图训练得到AdaBoost分类器，对词进行增强，共使用100个决策桩。
SPIN检测：我们采用与训练阶段相同的网格，对所有候选检测假设周围的旋转图像进行采样。每个旋转图像与词典中的所有词进行匹配，分配给欧氏距离最小的词。然后利用这些词构建直方图，输入到训练好的强分类器中完成检测。
范围$[0,20m]$的TEMP对比结果如图6所示。在两个数据集上，该方法的性能明显低于新的BUTD方法。它在Polyterrasse数据集上获得了超过75%的EER，这主要是因为该数据集的背景较为简单。对于更复杂的Tannenstrasse数据集，在$[0,20m]$范围内EER低至7.7%。
范围[0,20m]的SPIN对比结果如图6所示。对于Tannenstrasse数据集，各字典对应的EER分别为11.8%、12.7%、12.7%、10.8%；对于Polyterrasse数据集，对应的EER分别为31.2%、33.6%、39.5%、21.9%。无论参数如何设置，SPIN方法的性能都无法与本文提出的检测器相媲美。值得注意的是，大型字典（500词）会导致过拟合，因此分类器性能低于更紧凑的字典。类似的现象在计算机视觉领域早已被观察到[^24]。
讨论：基于模板的方法性能较差，显然是因为它不基于判别式分类器，且仅通过固定网格划分上的点密度分布对形状进行编码。自旋图像描述子同样依赖固定的空间细分和单一特征（投影到拟合局部平面上的距离）。相比之下，本文方法组合了一组特征（点密度只是其中之一）并自动学习网格划分。因此，我们能够学习特征计算所在的位置和尺度，从而稳定、鲁棒地表征形状，使该方法能够处理复杂的关节形状。基于自旋图像的方法性能较差的另一个原因是，其描述子依赖于局部法向量的估计质量。对于这类3D数据通常存在的稀疏且带噪声的测量结果而言，这可能会带来问题。本文的自上而下检测器的一大优势是它没有需要调优的参数。虽然网格划分算法存在约束，AdaBoost也存在误分类界，但这不同于自旋图像的分箱分辨率、尺度（分箱数量）或字典词数这些参数。这些参数
TABLE I
TRACKING PERFORMANCE COMPARISON: BUTD vs BU.
| Data set | MOTP | MOTA | FN | FP | ID |
| BU (Tann) | < 0.16m | 26.2% | 51.4% | 22.1% | 6 |
| BUTD (Tann) | < 0.16m | 73.6% | 16.9% | 8.2% | 30 |
| BU (Poly) | < 0.16m | 23.1% | 18.7% | 57.7% | 11 |
| BUTD (Poly) | < 0.16m | 89.1% | 2.6% | 7.6% | 20 |
会对方法的表现产生强烈影响，想要找到合适的参数值通常需要调优和经验积累。
本文的自底向上自顶向下检测器采用C++实现，未针对速度进行优化，在标准PC上处理单次3D扫描的约12万个点，运行速度为$\sim 1Hz$。
### C. 跟踪评估
为了评估本文的3D跟踪结果，我们采用CLEAR MOT指标[^25]作为评估标准。该指标相对于真实标注，在每一帧累计三个统计量：漏检（真实位置处本应存在却未被检出的轨迹，FN）、误检（本不应存在的轨迹，FP）和错配（轨迹标识符切换，ID）。基于这些统计量可以得到两个评估值：MOTP（估计目标与真实标注之间的平均度量距离）和MOTA（相对于真实标注，正确跟踪输出的平均比例）。
为了完成本次评估，我们基于两类标注手动标注了两个数据集中的轨迹，其中包括用于无奖励无惩罚策略的标注，这类标注由于点密度较低，检测难度尤其大。
我们对比了使用BU检测器和组合方法时的MHT跟踪性能（见表I）。实验在假设数量为$N_{Hyp} = 100$的条件下开展，当$N_{Hyp}$取更大数值时并未得到不同的实验结果。BUTD方法相较BU检测器的性能提升在两个数据集上都十分明显。Tannenstrasse数据集的MOTA指数高出$2.8\times$，Polyterrasse数据集的MOTA指数高出$3.8\times$。所有情况下MOTP指数都保持恒定。在两个数据集中，FN值至少降低了$3\times$，FP值至少降低了$2.8\times$。组合方法的轨迹混淆数ID更高，原因很简单：该方法能对更多目标进行更长时段的跟踪。相比之下，BU方法仅能短时间跟踪距离传感器较近的目标。
我们针对速度优化后的MHT系统，在标准PC上处理每次3D扫描的平均周期为$\leq 5$毫秒。
### 六、结论
本文提出了一种结合自下而上与自上而下流程的3D距离数据人体检测器。与以往研究不同，该方法不需要地面平面假设。自下而上检测器生成候选检测假设，再由自上而下流程对其进行验证。自上而下方法依赖一种新颖技术，该技术同时对特征以及计算特征所用的体积细分进行了增强。这
---
Fig. 7. Qualitative comparison of MHT tracking and detection with BUTD and BU in an urban scene (Tannenstrasse data set). Red circles represent false positives, magenta circles false negatives. Left Bottom-up detection only: false positives are detected in clutter and generate false tracks, two people are not detected due to point cloud sparsity. Right Bottom-up top-down detection, every person has been correctly detected and tracked, the asterisk indicates correct detection of a sparsely described target (annotation of the second type).
使得检测器能够在多个尺度、不同位置表征局部三维形状，因此具备稳定处理稀疏采样铰接物体的能力。
我们在杂乱城市环境的两个不同数据集上开展了实验，该方法能够对距离传感器最远20米的人体实现高鲁棒性检测，等错误率至少达到93%。该方法的性能明显优于两种成熟的三维目标识别方法，即自旋图像法和基于模板的分类法。与这两种方法不同，该自上而下检测器还无需设置参数。
经过验证的检测假设随后被输入至多假设跟踪器的三维实现中。我们使用CLEAR MOT指标量化了新增的自上而下检测器相较自下而上检测器对跟踪性能的提升幅度。实验表明，我们的方法能够在三维空间中稳定跟踪人体。
## 致谢
作者感谢Rudolph Triebel围绕三维数据分类问题开展的富有成效的讨论。本研究得到德国研究基金会（DFG）的支持，项目编号SFB/TR-8。
## 参考文献
[^1]: L. Spinello, K. O. Arras, R. Triebel, and R. Siegwart, “A layered approach to people detection in 3D range data.” in AAAI Conf. on Artif. Intell. (AAAI), 2010.
[^2]: D. B. Reid, “An algorithm for tracking multiple targets,” IEEE Transactions on Automatic Control, vol. 24, no. 6, pp. 843–854, 1979.
[^3]: I. J. Cox and S. L. Hingorani, “An efficient implementation of Reid's multiple hypothesis tracking algorithm and its evaluation for the purpose of visual tracking,” IEEE Trans. Pattern Anal. Mach. Intell. (PAMI), vol. 18, no. 2, pp. 138–150, 1996.
[^4]: A. Johnson and M. Hebert, “Using spin images for efficient object recognition in cluttered 3d scenes,” IEEE Trans. on Pattern Analysis & Machine Intell., vol. 21, no. 1, pp. 433–449, May 1999.
[^5]: B. Kluge, C. Köhler, and E. Prassler, “Fast and robust tracking of multiple moving objects with a laser range finder,” in Int. Conf. on Rob. & Autom. (ICRA), 2001.
[^6]: A. Fod, A. Howard, and M. Mataric, “Laser-based people tracking,” in Int. Conf. on Rob. & Autom. (ICRA), 2002.
[^7]: D. Schulz, W. Burgard, D. Fox, and A. Cremers, “People tracking with a mobile robot using sample-based joint probabilistic data association filters,” Int. Journ. of Rob. Research, vol. 22, no. 2, pp. 99–116, 2003.
[^8]: K. O. Arras, O. Martínez Mozos, and W. Burgard, “Using boosted features for the detection of people in 2d range data,” in Int. Conf. on Rob. & Autom. (ICRA), 2007.
[^10]: A. Carballo, A. Ohya, and S. Yuta, “Fusion of double layered multiple laser range finders for people detection from a mobile robot,” in IEEE Int. Conf. on Multisensor Fusion and Integration for Intelligent Systems (MFI), 2008.
[^9]: S. Gidel, P. Checchin, C. Blanc, T. Chateau, and L. Trassoudaine, “Pedestrian detection method using a multilayer laserscanner: Application in urban environment,” in Int. Conf. on Intel. Rob. and Sys. (IROS), 2008.
[^11]: O. M. Mozos, R. Kurazume, and T. Hasegawa, “Multi-part people detection using 2d range data,” International Journal of Social Robotics, vol. 2, no. 1, 2010.
[^12]: L. Navarro-Serment, C. Mertz, and M. Hebert, “Pedestrian detection and tracking using three-dimensional ladar data,” in Int. Conf. on Field and Service Robotics, 2009.
[^13]: M. Bajracharya, B. Moghaddam, A. Howard, S. Brennan, and L. Matthies, “Results from a real-time stereo-based pedestrian detection system on a moving vehicle,” in Workshop on People Detection and Tracking, IEEE ICRA, 2009.
[^14]: L. Spinello, R. Triebel, and R. Siegwart, “Multimodal people detection and tracking in crowded scenes,” in AAAI Conf. on Artif. Intell. (AAAI), 2008.
[^15]: Y. Freund and R. E. Schapire, “A decision-theoretic generalization of on-line learning and an application to boosting,” Jour. of Comp. and System Sciences, vol. 55, no. 1, 1997.
[^16]: B. Leibe, E. Seemann, and B. Schiele, “Pedestrian detection in crowded scenes,” in IEEE Conf. on Comp. Vis. and Pat. Recog. (CVPR), 2005.
[^17]: D. Comaniciu and P. Meer, “Mean shift: A robust approach toward feature space analysis,” IEEE Trans. on Pattern Analysis & Machine Intell., vol. 24, pp. 603–619, 2002.
[^18]: B. Leibe, A. Leonardis, and B. Schiele, “Combined object categorization and segmentation with an implicit shape model,” in In ECCV workshop on stat. learning in comp. vis., 2004, pp. 17–32.
[^19]: M. Oren, C. Papageorgiou, P. Sinha, E. Osuna, and T. Poggio, "Pedestrian detection using wavelet templates," in IEEE Conf. on Comp. Vis. and Pat. Recog. (CVPR), 1997.
[^20]: K. O. Arras, S. Grzonka, M. Luber, and W. Burgard, “Efficient people tracking in laser range data using a multi-hypothesis leg-tracker with adaptive occlusion probabilities,” in Int. Conf. on Rob. & Autom. (ICRA), 2008.
[^21]: M. Enzweiler and D. Gavrila, “Monocular pedestrian detection: Survey and experiments,” IEEE Trans. on Pattern Analysis & Machine Intelligence, vol. 31, no. 12, pp. 2179–2195, 2009.
[^22]: G. Csurka, C. R. Dance, L. Fan, J. Willamowski, and C. Bray, “Visual categorization with bags of keypoints,” in In Wshop on Stat. Learning in Computer Vision, ECCV, 2004.
[^23]: T. Kanungo, D. M. Mount, N. S. Netanyahu, C. Piatko, R. Silverman, and A. Y. Wu, “An efficient k-means clustering algorithm: Analysis and implementation,” IEEE Trans. on Pattern Analysis & Machine Intelligence, 2000.
[^24]: E. Nowak, F. Jurie, and B. Triggs, “Sampling strategies for bag-of-features image classification,” in Eur. Conf. on Comp. Vis. (ECCV), 2006.
[^25]: K. Bernardin and R. Stiefelhagen, “Evaluating multiple object tracking performance: the CLEAR MOT metrics,” J. Image Video Process., vol. 2008, pp. 1–10, 2008.