2013年International Conference on Robot and Automation(ICRA)上，由Carnegie Mello大学计算机系的Benjamin Choi和Manuela Veloso发表了一篇<Fast Human Detection For Indoor Mobile Robots Using Depth Images>。希望能与阅读这篇文章或者对这篇文章有兴趣的同仁交流探讨,共同学习。

摘要

本文提出了一种运行在indoor mobile robot上的human detection algorithm，该算法可以address包括cluttered environment带来的occlusion，由robot motion带来的changing background，和limited on-board computational capability等多种挑战。我们介绍了一种基于equip depth camera的robot的fast human detection algorithm。 首先，我们使用graph-based segmentation来对深度图像进行segment。接下来，我们利用a set of parameterized heuristic进行filter和merge分割的region来获得a set of candidate。最后，我们对每一个candidate计算一种Histogram of Oriented Depth (HOD) 描述子，然后通过linear SVM来检测human presence。我们在publicly avaiable的dataset上以及cluttered cafe environment上experimentally评估了这种方法。我们的algorithm在single CPU core上运行比其他在GPU上运行的HOD算法还要良好。特别我们的traning example被减少了一半的情况。我们讨论了training example的数量对于performance的影响，demonstrate该方法可以不同posture下的带有occlusion情况下detect human。

简介

运行在autonomous indoor mobile robot上的human detector会遇到several challenges。由于robot自身运动产生的perceived environment motion使得isolate moving human非常difficult。 根据是否sitting或者standing，何种furniture，以及观测的angle，观测到的human拥有a variety of posture。除此以外，与robot交互的human可能对于robot只是partially visible。Mobile robot拥有limited computational resources，并且由多个autonomous operation进行共享。所以human detector必须拥有一个small computational footprint。

我们contribute一种基于depth image的human detection algorithm来解决这些挑战。该算法可以在such as occlusion, clutter和different posture的challenging环境下detect human。我们的algorithm首先segment each observed depth image为与geometrically distinct object对应的region。这些region然后通过一系列的parametric heuristic，被filtered into一系列的candidate。这些candidate用来计算histogram of oriented depth(HOD)，HOD descriptor可以通过trained linear support vector machine(SVM)进行分类为human和not human。主要的contribution包括：

1）一种新型的结合了randomized subsampling的graph-based segmentation算法。2)  一种parameterized heuristic可以进一步的reduce candidate segment的数量。3）对这两个public dataset和自己产生的clutter environment的dataset进行performance evaluation。并且研究了training set对性能的影响。

在paper的remainder part，我首先discuss related work，然后详细的描述了这种方法，最后呈现了在standard dataset和custom dataset上的emperial result。

相关工作

Human detection是一种一个confine用color image的extensively studied subject。随着RGB-D camera的广泛采用，基于depth image的human detection已经在robotic community引起了广泛的attention。

两种广泛adopted的human detection approach分别是whole body detection和body part detection。这个section,我们集中注意为基于whole-body detection的方法，并且briefly介绍相关的工作。

通常的whole-body human detection的method包含两部分：首先determine可能包含human的region，然后使用trained的classifier来test这些存在human presence的candidate region。一种naive way来determine candidate region是在整个image范围内slide一种fixed size的window，并且treat每个区域作为candidate。这种方法用来在RGB图像中检测pedestrian。当covering整个image并且test每一个possible candidate。但是这种在整个图像上的brute-force search是非常的计算expensive。对于human在一系列range的distance的场景中，需要对不同size的candidate window进行search，这更加增加了computational cost。

不同的方法都被提出来improve通过improve这种brute-force sliding window search的速度，来extract candidate region。Zhu 使用图像中的salient feature并且只test包含这些feature的region，从而产生significant speed increase。Spinello和Arras只对其深度在metric space里可能fit human的区域来测试。这些算法如果要在incomming depth image stream上运行full frame rate，仍旧需要在GPU上运行。Spinello和Siegwart使用cluttered laser scan reading，并且只在RGB Image上对relevant area进行test。Xu和Fujimura使用基于深度图像的connected component来确认foreground object。Zhou和Hoang使用background subtraction来identify可以用来测试对应code book的区域来分类为human或者non-human。Shi和Malik呈现了一种针对不同的color channel的进行构建weighted graph的算法，并且使用normalized -cut来分割given image。Felzenszwalb和Huttenlocher呈现了一种similiar segmentation algorithm并且拥有更好的asymptotic running time。Pulli和Pietikainen给出了使用normal进行depth image分割的方法。我们使用了一种graph-based segmentation 算法，结合了depth image和surface normal来segment图像。

一旦一个candidate region被extracted，common approach是对candidate region计算feature descriptor，然后对计算的descriptor分类决定是否该region包含human或者not $G_{normal}$ 。而对human detection最广泛使用的descriptor是由Dalal和Triggs提出的Histogram of Oriented Gradient(HOG) descriptor。HOG descriptor把given image region分为一定数量的cells，然后对每个cell计算edge orientation的histogram。最近，Spinello和Arras提出一种depth image上采用的新的descriptor。该Histogram of Oriented Depth(HOD) descriptor实际上是Histogram of Oriented Gradient的varient。该descriptor使用depth value而不是color information来计算gradient。我们使用HOD descriptor结合graph-based segmentation来有效地处理由moving camera captured的image。该mobile robot通过多种surface类型，capture带有不同perturbation的图像。

方法

我们使用Microsoft Kinect Depth camera来进行human detection。尽管Kinect提供both color以及detph images，我们只使用depth image来进行human detection。 Kinect可以以30Hz的频率提供640*480分辨率的的深度图像。我们的算法分别处理each depth image并且检测其中的human。由Kinect Value来获得的深度图像上的raw pixel value（raw depth) 并不与physical unit(metric depth)成比例的对应。 Metric depth和raw depth通过下述公式进行计算：

$D_{x,y}^{'}=\frac{1}{a+b\cdot D_{x,y}}$

其中a和b都是Kinect sensor的intrinsic parameter，这通过calibration来决定。由于noise和Kinect的hardware limitation，一些raw pixel拥有invalid value，而这些并没有转化为positive metric depth。

为了计算对应于metric depth的kinect sensor上的reference frame上的3d point，我们使用下述公式：

$p_{x}=D_{x,y}{'}(\frac{y}{w-1}-0.5)tan(\frac{f_{h}}{2})$

$p_{y}=D_{x,y}^{'}(\frac{x}{h-1}-0.5)tan(\frac{f_{v}}{2})$

$p_{z}=D_{x,y}^{'}$

其中 $f_{h}$ 是horizontal field of view，而 $f_{v}$ 是camera的vertical field。并且w和h是图像的宽度和高度。这篇文章中，w=640，h=480。这种图像detection algorithm输入depth image $D$ ，通过三个步骤输出一系列的detected humans。

1）depth image segmentation。这一步接收一个depth image $D$ ，产生对应于深度图像上distinct area的a set of region。这通过 $D$ 上的sampling point，计算这些sampling point的3d position，来construct graph $G_{depth}$ 和 $G_{normal}$ 。对于 $G_{depth}$ ，edge weight代表neighboring point间的depth difference。对于 $G_{normal}$ ，这代表neighboring point间的surface normal间的angle。 $G_{depth}$ 和 $G_{depth}$ 被分割出来以实现group points into regions。

2) region filtering and merging。这一步take一组region $R$ ，然后返回a set of candidate $C$ 。而每个candidate都是由 $R$ 构建更小的depth image。这一步使用了parametric heuristic rules来reject regions of infeasible dimension。Remaining area基于location进行融合。

3) Candidate Classification。这一步take一组candidate $C$ 并且返回 $H$ ，the set of human( $H\subseteq C$ )。对于每个candidate，首先计算每个HOD descriptor。计算的descriptor通过SVM进行分类。Finally，一系列的分类为human的candidate会被返回。

具体的的细节如下：

A.    Depth Image Segmentation

这一步的purpose是获得 $R$ ，一系列的对应深度图像 $D$ 中distinct objects或者parts of objects的region。深度图像的resolution会随着distance不断地deteriorate。因此，在Larger distance不一定能够完美地区域分割。我们subsample深度图像从而significantly减少segmentation所需要的the amount of computation以及subsequent region filtering steps。

我们考虑depth image $D$ 作为a grid of cells。每个cell包含 $\alpha \times \alpha$ depth pixels。 $s$ pixel 在cell范围内被random sampled，具有median depth value的pixel被selected。如果depth value是有效的，3d space中的corresponding point通过前面的公式进行计算，并存储为 $p_{i,j}$ 。每一个point $p_{i,j}$ 对应一个distinct cell。最后在subsampled image上有最多 $\frac{wh}{\alpha ^{2}}$ points。

在下一步，我们使用一种image segmentation algorithm的variation形式。这种algorithm初始用于color images。这种original algorithm在separate graph上进行multiple segmentation，他们的edge对neighboring pixel间的相似性进行encode，并且combine这种结果。每个segmentation使用single parameter $k$ , 这设定了connected component的preferred size。我们adapt这种算法，让其工作于depth images。我们对graph进行perform两种separate segmentation。这些graph的edge利用neighboring point间的depth和normal间的similarity进行encode。

首先，我构建graph $G_{depth}$ ，其vertices都是 $P$ 上的points。每个vertex都在4 cardinal direction上联通到它的neighbor。Metric depth $z_{1}$ 和 $z_{2}$ 点间的edge的weight可以用 $\left | z_{1}-z_{2} \right |$ 来表示。当进行graph segmentation的时候，这些vertices基于深度值的相似性被group into联通的components。

对于每个点 $p_{i,j}$ ，我们通过对该point以及8 neighbor points进行least-square regression，来计算normal。这8个neighbor point需要lie on同一个connected component。只Including位于connected component上的点移除了那些远离于3d space的outlier。

在下一步，我们构建graph $G_{normal}$ 类似于 $G_{depth}$ 。但是edge的衡量是normal间的angular difference。Normal为 $u$ 和 $v$ 间的Vertices间的edge weight用 $cos^{-1}(u\cdot v)$ 来表示。因此，我们实现了对 $G_{normal}$ 的graph segmentation。

Segmentation的最后输出是region $R$ 。每一个region都是 $P$ 上的在同一个connected component上的一个distinct set of point。 $R$ 在decreasing order的size上进行分类。所以 $\left | r_{i} \right |\geqslant \left | r_{i+1} \right |$ 是strictly true，并且只有点数不低于 $\beta$ 的点会被考虑。这种filtering帮助remove由noisy data和不太可能correspond to human part的a number of region。

B    Region Filtering and Merging

这一步take一系列的region $R$ 作为输入，丢弃掉那些heuristic认为不太可能是human的区域，并且merge remaining region，返回C，可能对应于不同distinct object的a set of candidate。对于每个region $r_{i}$ ，它在real space中的mean depth，height和width，中心点 $u\left ( r_{i} \right )$ ，以及适合plane的proportion of point被计算。区域的mean depth实际上是所有区域上point的平均深度。该区域的top，bottom，left 和 right点计算其平均深度以及每一边的midpoints。该region的metric height实际上是top midpoint和bottom midpoint的difference。而该区域的metric width是left midpoint和right midpoint之间的difference。而区域的center point $\left \langle u_{x},u_{y},z_{z} \right \rangle$ 是由 $u_{x}$ (left和right point间的midpoint)， $u_{y}$ (top和bottom point间的midpoint)， $u_{z}$ (区域的mean depth）。我们在XZ平面上用 $u_{xz}=\left \langle u_{x},u_{z} \right \rangle$ denote区域的position。

我们使用RANSAC来fit plane到region。对于每次n迭代，region上的3 point被随机picked并且用来model一个hypothesis plane。

一个参数化的heuristic rules定义了有效的mean depth的range，以及通过量测positive example的range来发现minimum inlier fraction（适合平面的proportion of points)。这些rules用来eliminate 那些不可能是human的region。

这些区域从largest到smallest的顺序processe。如果region $r_{i}$ 满足所有的rule并且看起来像个planar(proportion of point fitting plane非常大）。我们检测是否有更大的region $r_{j}$ 存在，并且满足：

$\left \| u_{xz}\left ( r_{i}\right )-u_{xz}(r_{j}) \right \|\leq \delta _{xz}$ and $\left \| u_{y}(r_{i}) \right \-u_{y}(r_{j})|\leq \delta _{y}$

C    Candidate Classification

最后一步是输入set $C$ 并且返回 $H$ ，这是分类为human的set $C$ 的subset。我们使用HOD descriptor。首先我们计算candidate window上的each pixel的metric depth。然后我们计算HOD descriptor，而任何undefined value和some other value间的gradient value往往是zero。因为metric depths间的sign of gradient非常重要，我们使用signed gradient。在非遮挡的情况下，objects总是比background更接近camera。

在最后的classification step，我们使用带有linear kernel的support vector machine(SVM)来分类computed descriptor。然后决定是否该区域包含human or not。

D    Training the Algorithm

训练这个classifier, 这算法运行在training set上的image frames。Candidate存贮，并且label为positive或者negative。这种heuristic rule用于region filtering step并且可以通过选择包含postive value的range来派生。

实验结果

我们通过两个两个dataset来evaluate我们的human detector。在第一个set的experiment中，我们评估了这个方法的accuracy，而这第二个set我们investigate不同的number of training example对accuracy的影响。我们使用具有不同characteristic的two datasets。第一个dataset包含从publicly available RGB-D dataset提供的depth image。该dataset由Spinello和Luber提供。The dataset包含通过three vertical mounted kinect sensor获取的images of people。我们称这种dataset为hallway dataset。这一环境不是cluttered，并且有不同occlusion level不同距离的human，但是并不是所有的human都在upright position。我们还collected另外一种dataset，是从crowded cafe area获得的叫做cafe dataset。这是driving我们的robot around来获得的。这里有substantial environmental clutter，包括plants，counter,pillars,和不同类型的tables和chair。Standing, sitting, and walking human是混合的，并且被其他human、furniture或者plant所occluded。