DEIM Forum 2014 D9-2

3D Objects Tracking by GPGPU-Enhanced Particle Filter Algorithms
Jieyun ZHOU†

Masayuki NUMAO‡

Xiaofeng LI† andHaitao CHEN††The School of Communication and Information, University of Electronic Science and Technology of China
No.2006, Xiyuan Ave, West Hi-Tech Zone, 611731, Chengdu, Sichuan, P.R.China‡Graduate School of Informatics and Engineering, University of Electro-Communications
1-5-1 Chofugaoka, Chofu-shi, Tokyo, 182-0021 Japan
E-mail:†zidongyi@gmail.com,‡numao@cs.uec.ac.jp

Abstract Objects tracking methods have been wildly used in the field of video surveillance, motion monitoring, robotics
and so on. Particle filter is one of the promising methods, but it is difficult to apply for real time objects tracking because of its
high computation cost. In order to reduce the processing cost without sacrificing the tracking quality, this paper proposes a new
method for real-time 3D objects tracking, using GPGPU-enhanced particle filter algorithms.
Keyword Objects Tracking，Particle filter，3D，GPGPU

1. Introduction
In recent years, visual tracking research is getting
popular among researchers in the fields of video
surveillance, robot vision, etc. A large amou nt of research
papers focus on the improvement of efficiency andaccuracy of tracking algorithms. In our approach, tracking
problem can be solved by the three basic theories: filtering
theory, similarity function, and partial differential
equation.
The first way is based on the filtering theory. Objects
tracking problem can be converted to the probability
density function estimation problem. In this way we often
use the Kalman filter[1] or particle filter[2] for tracking.
The merits of this method are that we can easily deal withthe occluded objects problem. But the drawbacks of thismethod is that computing complexity is very high so it
will take a large amount of calculation time and makereal-time performance difficult. So nowadays a lot of
researchers concentrate on how to decrease the computing
complexity. Second way is based on the Mean-Shiftobjects tracking[3]. It is based on the probability
similarity function between the target model and the target
candidate to calculate Mean-shift iteration equation bygradient descent algorithm. The advantage of it is that thecomputing complexity is not very high. But the
shortcoming of this method is that it cannot deal with theoccluded objects problem. The last method is based onpartial differential equation. Changing the target tracking
problem into functional optimization problem, by thefunctional extremum from a partial differential equation.
We choose particle filter as our tracking method
because its ability of solving non-linear and non-Gaussian
dynamic system. And it becomes more attractive due to its
high robustness and effectiveness. 3D tracking becomes
popular nowadays due to the effectiveness[4]. The object
itself is a 3D object. But in traditional 2D tracking we
directly take the projection of object. So we lose a lot ofeffective information . By 3D objects tracking we canretrieve these effective information to get high robustness
and effectiveness.
General Purpose Graphics Processing Units (GPGPU)[5]recently becomes more and more popular due to its highparallel computing ability and lower cost. Compute
Unified Device Architecture (CUDA) ， utilizes the blocks
and the threads of graphics processing units (GPU) torealize the parallel computing. There are some designs ofparticle filter on GPU. But which part of the algorithm canbe migrated into GPGPU and how to parallelize thealgorithm to realize the time reduction is still a challenge.
This paper proposes a development of a robust andeffective system for object tracking. The design is asfollows. First, we use a Kinect to get the 3D informationof objects. Unlike the traditional 2D-based objects
tracking, 3D objects tracking add depth information. It can
track not only from the x and y axis but also from the zaxis, and the depth information can correct some errors
caused by self-adaptive windows in 2D objects tracking.
Second, to solve the high computation cost problem, we
decided to use the GPGPU to parallelize the particle filter
algorithm. We propose a several way to implement particle
filter algorithms on GPU and evaluate the performance byactually running a program using CUDA. We use GPU in
the following two area, We use the parallel computing
ability of GPU to get a large number of transition particles.
We can also calculate the similarity function and theweight of each particles from the histogram by eachparticles’ region using GPU. We can also use optimizing
parallel reduction in CUDA method to reduce thecomputing complexity when calculate the weight of eachparticles. From the experiment result this tracking method
can be more real-time and robust.
This paper is organized as follows. Section 2 describes
the background, particle filter and the platform CUDA.
Section 3, the two proposed design techniques aredemonstrated. The experiment result is showed in section
4. And the section 5 draws the conclusion.

2. Backgroundp ( x k | z1:k ) 

2.1 Particle filter
Particle filter is a tracking method based on Monte
Carlo sampling. Two kinds of state variables are defined inthis method, state variable and measurement variable. In
hidden Markov model we can ’t obverse the state of target
very clearly, and only measurement variable is available.
From the measurement model we can conjecture the stateof state model.
The definition of the state model has been given in [6],the state sequence { xk , k  N } of a target given byxk  f k ( xk 1 , vk 1 )(1)

Where f k is the nonlinear system function, xk is thestate vector, vk is the noise of this system. k is the index
of time step. In tracking problem, state model means
actual movement of the target object.
The measurement model can be measured from thestate modelz k  hk ( xk , nk )p ( z k | x k ) p ( x k | z1:k 1 )p ( z k | z1:k 1 )(4)

Where the part below is the normalizing constantp ( z k | z1:k 1 )   p ( z k | xk ) p ( xk | z1:k 1 )d xk(5)

Where p ( z k xk ) is the likelihood function. It defines
the similarity of measurement model and state model. The
similarity between target model and target candidate isalso defined by p ( z k xk ) . So we define the likelihood
function as the weights of particles.

wk  p ( z k xk )(6)

So from the equation (3) (4) (6)and the known systemmodel p ( xk xk 1 ) we can easily get the state sequence or
the target model, fig1 shows how the transition works.
The tracking method based on particle filter can be used
as follow.

(2)

Where z k is the measurement vector, nk
is themeasurement noise caused by measure method. hk is themeasurement function. In tracking problem, measurement
model means the estimated movement of target candidate.
The possibility of target candidates are calculated by the
likelihood function.

2.2 GPGPU calculate by Compute Unified
Device Architecture (CUDA)
Fig1 state transition graph
Such a filter consists of two stages: prediction andupdate.
● The prediction stage uses the known systemmodel p ( x k x k 1 ) to predict the state probability density
function (pdf) forward from one measurement time to thenext. p ( x k x k 1 ) defines how the particles moves, it isa dynamic model.

p ( xk | z1:k 1 )   p ( xk | xk 1 ) p ( xk 1 | z1:k 1 )d xk 1(3)● The update operation uses the latest measurement tomodify the prediction pdf. This is achieved by using Bayes
theorem, which is the mechanism for updating knowledge
about the target state in the light of extra information fromnew data.

General-purpose computing on graphics processing
units (GPGPU)[7] which use thegraphics processing
units (GPU) to calculate the data for CPU. GPU is usuallyused in image processing, but how to migrated it fromCPU to GPU is still a challenge.
CUDA is a parallel computing platform and program
model invented by NVIDIA. It enables a large increase ofcomputing performance by migrating the data from CPU to
GPU by using parallel computing ability of GPU. A new
execution model has been used is Single instruction
multiple thread (SIMT). SIMT use 32 parallel threads tocreate, manage and execute. We call it warp. A warp
executes one common instruction at a time, so fullefficiency is realized when all 32 threads of a warp agree
on their execution path.
Data-parallel processing maps data elements to parallel
processing threads. Many applications that process large
data sets can use a data-parallel programming model tospeed up the computations. In 3D rendering, large sets ofpixels and vectors are mapped to parallel threads.
Similarly, image and media processing applications suchas post-processing of rendered images, video encoding anddecoding, image scaling, stereo vision, and patternrecognition can map image blocks and pixels to parallel
processing threads. In fact, many non-image-processing
algorithms can be accelerated by data-parallel processing,from general signal processing or physics simulation tocomputational finance or computational biology.

3D self-adaptive tracking window. Scale is used fordescribing the changes of tracking window.
If we use the depth information, we can get the correct
value of the tracking window by the first chosen window
and the distance between camera and target. So it doesn't
need N random numbers.

2.3 Kinect for 3D information
Kinect is a motion sensing input device by Microsoft for
the Xbox 360 video game console and Windows PCs[8].
Based around a webcam-style add-on peripheral for theXbox 360 console, it enables users to control and interact
with the Xbox 360 without the need to touch a gamecontroller, through a natural user interface using gesturesand spoken commands.
The device features, RGB camera, Depth sensor (IR),Multi-array microphone, Motor to adjust camera angle. It
can get three kinds of informations, Color image, Depth
image and Skeleton.
We use a Kinect as a camera for objects tracking. We
use RGB information for normal tracking. Depth
information from Kinect is used to correct the trackingarea.

3. Design

methodfor

3D

objects

tracking

improvement
Because of the time consuming algorithm, it is a criticalissue for tracking object in a real time. In this section, twodesign techniques have been proposed , (A) 3D
self-adaptive tracking window. (B) Parallelization on thetransition part and the likelihood part.
In the following explanations we will use the following
notations,(1) Tracking window. The target object has beenchosen in the first frame, and the surrounding rectangle isdefined as tracking window. Some of image pixels are
sampled as particles.
(2) Particle. The basic unit of the particle filter
algorithm. It moves in every frame to confirm the locationof the tracking window.
(3) Block. The basic unit in GPU. For parallel
computation.
(4) Thread. The basic unit in GPU. For serial
computation.

Fig2 Relation between distance and size of window
From the triangle similarity function we can get theequation of the gray part as below.
 H / 2 H1 / 2
 D  D 1

 H / 2  H2 / 2
 D2
D

(7)
 D1 H1  D2 H 2

In equation (7) we can get D1 and D2 from Kinect by
distance sensor, and H1 by the first selected tracking
window. So from equation (7), we can get the size of eachparticle. Compared with random window size, the size
calculated by Kinect is much more correct than before.
The

difference

betweentheoriginal

versionandproposed version is to “get particle” algorithm. It is shown
as below.

3.1 3D self-adaptive tracking window
Traditional particle filter tracking method uses therandom number generator to get random sizes of the
tracking windows[8]. It uses N random numbers to get N
random scales and compute similarity function values. The
window which has the maximum value should be the target
window. This method may have some shortcomings. Even
if the point is in the target window point, the similarity
function value can become very small because the window
size is different. So we need another way to calculate thecorrect size of tracking window. We propose a method of

3.2 Parallelization in particle filter
If we do every step of algorithm1 in CPU it’s very slow
because it must repeat the same kind of calculation for N
times. If we can do all the calculation in one time it can
reduce the time cost.We will use GPGPU to realize theparallel computation[9][10]. Fig.3 shows the basic design
on GPU.

particles on larger weight area, on the other hand remove
the particles which have small value of weight.
The designed method’s pseudocode is showed asfollows.

Fig3 Block design of proposed particle filter on CUDA
● Initialize N particles (CPU). This part is done inCPU. We first have to choose a tracking window. And thenproduce N pairs of (x, y) random numbers. This random
number set can be moved to GPU and stored in each block.
The present location(x0, y0) is also sent to each block.
● Transport of N particles (GPU). In this step, in eachblock that we use random numbers to computesecond-order autoregressive dynamics to sample newparticles, which get a new position of each particle (xp,yp). In GPU the data is stored in N blocks. Each block is
independent and can calculate parallelly in one time. Then
new particles’ position is sent back from GPU to CPU.
● Histogram calculation (CPU). For each particle’s
position, the distance information is added by Kinect, thesize of the area of each particle is calculated on GPU.
From the area we can get the histogram of each target
candidate. Send N area’s histogram (The length of eachhistogram is L) to N blocks and each block exploit L
threads on GPU, each histogram array put in one sharedthread.
● Likelihood calculation (GPU). In each block
likelihood between the histogram of each particle’s area
and the previous target histogram is calculated. Then thelikelihood should be normalized. In order to calculate theaverage, we need to add all the blocks value together. In
this situation we can use an optimizing parallel reductionin CUDA method to optimizing the processing speed.
When the calculation results have been obtained, we takethe weight data from GPU to CPU again to continue thenext calculation.
● Resampling. Processed on CPU to produce more

● Parallel Reduction. The normalization processing
needs to add a lot of summation of large numbers.
Optimizing parallel reduction is the method how to makebest use of the parallel ability which showed in Fig.4. So
it reduces the calculation time for getting sum from O(N)to O(log(N)).

Fig4 Way of calculate sum in parallel

4. Experiment Result
The experiment environment is Windows 7 and Visual
Studio 2012 combined with OpenCV 2.3.1, gsl 1.8, andCUDA 5.5. The camera is Kinect 360. The GPU of thisexperiment platform is NVIDA GeForce 9300M Gs 512M
and NVIDA GeForce GTX 480 . In this part we compare
the different effects and time cost of original algorithm
and the proposed algorithm in different number ofparticles. We can also compare the time cost of each partof particle filter algorithm.

GPU

GPU 1

GPU2

Model

nVIDA GeForce 9300M

nVIDIA GeForce GTX

GP U memory

256MB

1536 MB

480

MB

64bit

384bitMemory Clock

1000MHz

3696MHzBus bandwidth

8GB/s

177. 4GB/s

Main Clock

567MHz700M Hz

400MHz

400M Hzfrequency
RAMDAC
frequency

Table 1 Hardware information for evaluation

(c)

(a)

(d)
Fig4 Experiment result by Kinect(b)

In Fig4 (a) is the original algorithm of particle filter,
the target is a book. (b) is the new algorithm of 3D
tracking by Kinect, the target is also a book. (c) is theoriginal algorithm of particle filter, the target is a smallcup. (d) is the new algorithm of 3D tracking by Kinect, thetarget is also a small cup. These yellow windows showeach particles’ area, and the red window shows the final
location of the target. The original algorithm sometimes
loses the target and the tracking window does not fit thetarget. But the proposed method shows that the target
window is self-adaptive by distance.

method.

Fig7 Time cost of Likelihood calculation (GPU).

5. Conclusion
From the method we mentioned above we propose two
design techniques. (A) 3D self-adaptive tracking window.
(B) Parallelization on the transition part and the likelihood
part. And from the experiment we have done on CUDA the
proposed design can reduce global operation, provide
significant speedup and shows a very good robustness.

Reference

Fig5 Time cost result of new algorithm. (a) is simulated byCPU(b) is simulated by GPU1 (c) is simulated by GPU2

We evaluated the result of the whole time cost in Fig 5.
The experiment result has showed that the proposed
algorithm has a higher real-time ability and robustness.
Then we move to each part. First fig6 shows the transportpart of each particle on two different GPU.

Fig6 Time cost of Transport of N particles (GPU).
Second fig7 shows the likelihood calculating part. We
can see the different performance of these two different
GPU. On GPU2 we also use the Parallel Reduction[1] R.E.Kalman A new approach to linear filtering andprediction problems. Vol.82D,March 1960,pp. 35-45.
[2] M. SanjeevArulampalam, Simon Maskell, Neil
Gordon, and Tim Clapp. A Tutorial on Particle Filtersfor
OnlineNonlinear/Non-Gaussian
Bayesian
Tracking of IEEE International Conference on
Acoustics 2002, 723-737[3] D. Comaniciu and P. Meer, “ Mean Shift: A Robust
Approach Toward Feature Space Analysis, ” IEEE
Trans. Pattern Analysis and Machine Intelligence, vol.
24, no. 5, pp. 603-619, May 2002.
[4] Iason Oikonomidis ,Efficient Model-based 3D
Tracking of Hand Articulations using Kinect, 2012[5] Nan Zhang, Yun-shan Chen, Jian-li Wang. Image
parallel processing based on GPU. In International
Conference on Advanced Computer Control(ICACC),
2010. Shenyang:2010.367-371[6] Min-An Chao, Chun-Yuan Chu, Chih-Hao Chao, andAn-Yeu (Andy) Wu EFFICIENT PARALLELIZEDPARTICLE FILTER DESIGN ON CUDA. IEEE
2010,299-304[7] NVIDIA CUDA Programming Introduction 2008 6/7[8] Microsoft Corp. Redmond WA. Kinect for Xbox 360.
[9] Changhyun Choi, Henrik I. Christensen , “RGB-D
Object Tracking: A Particle Filter Approach on
GPU,” in Proceedings of IEEE/RSJ International
Conference on Intelligent Robots and Systems(IROS), 2013.
[10] Iason Oikonomidis ,Efficient Model-based 3D
Tracking of Hand Articulations using Kinect, 2012[11] Maggio. E, Cavallaro, A. Hybrid Particle Filter andMean Shift tracker with adaptive transition model. In
Proceedingsof IEEE International Conference on
Acoustics,Speech, and Signal Processing(ICASSP
2005): 221-224