Chinese Journal of Computers   Full Text
Title	A Novel Color Based Particle Filter Algorithm for Object Tracking
Authors	LI Pei-Hua
Address	(College of Computer Science and Technology, Heilongjiang University, Harbin 150080)
Year	2009
Issue	No.12(2454—2463)
Abstract &   Background	Abstract The traditional histogram based particle filter often has to compromise between accurate representation of color distribution and computational efficiency, which affects the performance of the tracking algorithm or even results in tracking failures. To address this problem, the paper presents a novel color based particle filter algorithm for object tracking. The proposed algorithm utilizes a model based on adaptive partition of color space, which can represent accurately the color distribution of the object with smaller number of subspaces. The paper proposes extended integral images, by which the pixel number, mean vector and covariance matrix of each sub-space can be obtained in simple array read operations that results in fast computation of the color model. The construction of the proposed integral images on CPU is, however, time-consuming, thus this paper proposes a GPU based parallel algorithm for fast computation of the integral images. The parallel algorithm consists of three thread grids respectively executing three Kernel functions with GPU on the video card, which sequentially builds the raw integral images, performs prefix sum with respect to rows and then with respect to columns of the original integral images. Compared to the traditional histogram based particle filter algorithm, the proposed one has much shorter tracking time, and in the meantime, attains improved tracking accuracy and robustness. Keywords object tracking; particle filter; color model; integral images; parallel algorithm Background The research of the paper is supported by National Natural Science Foundation of China under grant Nos.60673110 and 60973080. It is well known that color is common and highly useful information in object tracking, due to its invariance to translation and rotation, and robustness to pose variation and partial occlusion. Traditional color histogram based particle filter suffers from contradiction between accurate color density modeling and efficient computation. Concretely speaking, if the authors try to represent color distribution more accurately, for example, with a larger number of bins in histogram, then computational cost increases considerably; otherwise, very coarse description of color density may decrease performance of particle filter tracker and even lead to tracking failures. The paper focuses on addressing the problem by proposing a novel algorithm. The authors propose to use a new color model based on clustering, which automatically partitions a color space into several sub-spaces, and considers both the number of pixels falling into each sub-space and color distribution in each sub-space with Gaussian. In order for fast computation of the color model, we present extended integral images, upon which we can compute in simple array read operations the pixel number, the mean vector and the covariance matrix of each sub-space. The computation of integral images on CPU is time-consuming, thus a parallel algorithm is proposed based on NVIDIA G80 GPU for very quick construction of the integral images. Experiments show that the proposed algorithm is superior to the traditional histogram based particle filter in both average tracking time and performance.