Computación de Altas Prestaciones y Optimización
(High-Performance Computing and Optimization)
GAVAB
Multiscale and Local Search Methods for Real Time Region Tracking with Particle Filters
Local Search Driven by Adaptive Scale Estimation on GPUs
Raúl Cabido, Antonio S. Montemayor, Juan José Pantrigo, Bryson R. Payne
Index
- Abstract
- Hypothesis and improvements
- Demo videos
- Results
- Links/Other resources
- About
- Acknowledgements
Abstract
Tracking systems are important in computer
vision, with applications in surveillance, human computer
interaction, etc. Consumer graphics processing units
(GPUs) have experienced an extraordinary evolution in
both computing performance and programmability, leading
to greater use of the GPU for non-rendering applications.
In this work we propose a real-time object tracking
algorithm, based on the hybridization of particle filtering
(PF) and a multi-scale local search (MSLS) algorithm,
presented for both CPU and GPU architectures.
The developed system provides successful results in precise
tracking of single and multiple targets in monocular
video, operating in real-time at 70 frames per second
for 640x480 video resolutions on the GPU, up to 1100%
faster than the CPU version of the algorithm.
Online version
Full text (from Springer)
Hypothesis and improvements
Our hypothesis about the MSLS PF algorithm and the GPU hardware proposals are based on some foundations:
- N-Dimensional state-space PF are computationally very expensive (especially pixel-based approaches)
- Dimensionality reduction methods become more popular for a PF refinement
- Very powerful graphics processors can deliver high memory bandwidth for some data-parallel applications
- PF becomes algorithmically very suitable for GPU hardware (independency, pixel-based approach, computationally intensive,...)
MSLS Algorithmic improvements
- Better shape adjustment than a regular 2D state-space PF (x, y)
- PF dimensionality reduction (x, y, Sx, Sy) --> (x, y) + MultiScale + Local Search
- Workload reduction enables real time performance for multiple object tracking (even in a consumer CPU for some configurations)
GPU Platform
- Very good performance (2-10 times faster than CPU)
- MSLS proposal still very suitable for GPU execution
- Not expensive but high performance hardware (up to 700 M transistors), free and high level programming frameworks
- Very rapid evolution hardware, almost doubling performance each 9 months
Demo Videos
DEMO 1: CAVIAR benchmark [CAVIAR]
Step 1: Segmentation: Here we show the result of the preprocessing fragment program that leads to the measurement model. It performs a simple background subtraction
Ir(t)=|I(t) - I(0)|where I(t) is the actual video frame at time t, I(0) is the background template and Ir(t) is the resulting segmentated video frame at time t
Step 2: Tracking: The resulting tracking for the CAVIAR video sequence is shown here. The method is applied at very high speed although the video visualization is kept at 30 fps.
| Regular PF |  |
| MSLS PF |  |
| Original ROI: 32x32; 1024 particles | |
[CAVIAR] EC Funded CAVIAR project/IST 2001 37540, found at URL: http://homepages.inf.ed.ac.uk/rbf/CAVIAR/
DEMO 2: Head and hands tracking
Step 1: Segmentation: Here we show the result of the preprocessing fragment program that leads to the measurement model. Every pixel is labelled as skin pixel if:
(R > 45) & (G > 40) & (B > 20) & (R > G) & (R > B) & (max(R;G;B) - min(R;G;B) > 15) & ( R - G > 15)is met, as proposed by [Peer03], but any other preprocessing stage could be applied.
 |
Step 2: Tracking: The resulting tracking is shown here. The method is applied to an indoor video sequence at very high speed although the video visualization is kept at 30 fps.
 |
 |
| Regular PF | MSLS PF |
| Original ROI: 16x16; 1024 particles | |
 |
 |
| Regular PF | MSLS PF |
| Original ROI: 16x16; 1024 particles | |
[Peer03] Peer, P., Kovak, J., and Solina, F. "Human skin colour clustering for face detection". In Proc. of the International Conference on Computer as a Tool EUROCON, 2003.
Results
G70: Nvidia GeForce 7800GTX
G80: Nvidia GeForce 8800GTS
CPU: 3.0GHz Pentium 4 with 1GB RAM
fps: Framerate (Frames per second)
| GPU vs. CPU performance | ||
 |
 |
 |
| Regular PF (1 object) | Regular PF (4 objects) | MSLS PF (4 objects) |
A: Accuracy: Average of the difference between the true estimation from the predicted one for a number of frames.
P: Precision (reproducibility or repeatability): degree to which further measurements or calculations show the same or similar results.
| Quality (Accuracy and Precision in pixels) |
 |
| PF vs. MSLSPF1 vs. MSLSPF2 for different number of evaluations and ROI size of 16x16 tracking a 20x20 object |
- First proposal of particle filtering partially using the GPU: Antonio S. Montemayor, Juan José Pantrigo, Ángel Sánchez, Felipe Fernández. Particle Filter on GPUs for Real-Time Tracking, Proc. of the ACM SIGGRAPH 2004 (research poster)
- First and complete particle filtering using the GPU: Antonio S. Montemayor, Juan José Pantrigo, Raúl Cabido, Bryson Payne, Ángel Sánchez, Felipe Fernández. Improving GPU Particle Filter with Shader Model 3.0 for Visual Tracking, Proc. of the ACM SIGGRAPH 2006 (research poster).
About
Authors
Antonio S. Montemayor: Assistant Professor at Universidad Rey Juan Carlos. The title of his Ph.D. was: Optimización de Algoritmos de Procesamiento de Vídeo para su Implementación sobre Tarjetas Gráficas de Consumo (Video Processing Algorithmic Optimization for Implementation on Consumer Graphics Cards). Personal Web: http://www.escet.urjc.es/~asanz/.
Bryson R. Payne: Assistant Professor of Computer Science at North Georgia College & State University. Ph.D. in Computer Science from Georgia State University entitled Accelerating Scientific Computation in Bioinformatics by Using Graphics Processing Units as Parallel Vector Processors. Personal Web: http://www.professorpayne.com/.
Juan José Pantrigo: Ph.D. in Computer Science and Assistant Professor at Universidad Rey Juan Carlos. His main interests include Computer Vision and Optimization Techniques. Personal Web: http://www.escet.urjc.es/~jjpantrigo/
Raúl Cabido: Ph.D. Student and grant holder at Universidad Rey Juan Carlos. His main interests are GPU Programming, Video Processing and Computer Vision.
CAPO
CAPO is the Spanish acronym for High-Performance Computing and Optimization (Computación de Altas Prestaciones y Optimización). CAPO is one of the research lines of the GAVAB group at Universidad Rey Juan Carlos (Madrid, Spain).
We would like to thank the Spanish Ministry of Education and Science that has been supported this research by CICYT TIN2005-08943-C02-02, URJC and CAM by URJC-CM-2007-CET-1724, and the Nvidia Professor Partnership Program