Kernel based similarity estimation and real time tracking of moving

International Journal of Electronics and Communication Engineering & Technology (IJECET),
INTERNATIONAL JOURNAL OF ELECTRONICS AND
ISSN 0976 – 6464(Print), ISSN 0976 – 6472(Online), Special Issue (November, 2013), © IAEME

COMMUNICATION ENGINEERING & TECHNOLOGY (IJECET)

ISSN 0976 – 6464(Print)
ISSN 0976 – 6472(Online)
Special Issue (November, 2013), pp. 293-300
© IAEME: www.iaeme.com/ijecet.asp
Journal Impact Factor (2013): 5.8896 (Calculated by GISI)
www.jifactor.com

IJECET
©IAEME

Kernel based Similarity Estimation and Real Time Tracking of Moving
Objects
Manoj Pandey1, J S Ubhi2, Kota Solomon Raju3
1Department

of ECE, BKBIET, Pilani, Rajasthan, India
of ECE, SLIET, Longowal, Sangrur, Punjab, India
3 Digital System Group, CSIR-CEERI, Pilani, Rajasthan, India

1,2Department

1manoj2pandey@yahoo.com

ABSTRACT: In this paper, a traditional Mean Shift algorithm is simulated for tracking a moving
object. Kernel based mean-shift algorithm is used for real and non real time tracking and it is
observed at various moving constraints such as uniformly moving, fast moving, moving with
scale change and moving in overlapping of similar objects. The object is initialized in first
frame as a candidate when it first appears in video. The algorithm finds the maximum
correlation between target and candidate with kernel based density estimation by similarity
function of Bhattacharya co-efficient. The shape of object is used as an ellipse. A kernel based
object tracking uses fixed bandwidth which limits the performance when the object scale
exceeds the size of tracking window. Therefore in simulation target windows are made
adaptive with feature matching.

KEYWORDS: Object tracking, Mean Shift, Kernel, Bhattacharya Coefficient.
I.

INTRODUCTION

Object tracking is one of the most popular areas of computer vision. In last two decade object
recognition and its tracking become very popular because of its applicability to daily problems
and ease of production e.g surveillance cameras, adaptive traffic lights with object tracking and
plane detection etc. Objects are represented based on its shape and appearance models
explained by Alper et. al in a survey of object tracking [1]. The model selected to represent
object shape limits the type of motion or deformation it can undergo. In general, visual
tracking algorithms are classified into two categories specified as bottom-up and top-down
approach [2]. Filtering and data association [3] is a top down approach while target
representation and localization is a bottom-up approach [4-7]. Traditionally, in object tracking
implementations feature trackers are used, which gets image sequences, and detect motion
after applying the algorithms. Small windows, called features, with certain attributes are
selected and then attempts are made to find them in the next frame. Models selected to
represent object shape limits the type of motion or deformation it can undergo.

International Conference on Communication Systems (ICCS-2013)
B K Birla Institute of Engineering & Technology (BKBIET), Pilani, India

October 18-20, 2013
Page 293


Object tracking are used for applications includes: pattern generation, clustering, face
recognition, motion analysis or tracking. Numerous approaches have been dedicated to track
non-rigid objects using Kernel based mean shift [4], Mean Shift [5-7] and optical flow [8]
method. Comparison of other algorithms used in the application of object tracking and
recognition are shown in table 1. These algorithms are implemented either on pure General
purpose Processors (GPPs) [9-10] or Field Programmable Gate Arrays (FPGAs) based
embedded architectures [11-12]. Mean shift [4-7] is one of the most popular algorithms in
object tracking applications used independently or with combination of other filtering
techniques. In this paper, a traditional mean Shift algorithm is used in the tracking of two
similar moving objects based on Kernel selection. If the similar objects are overlapped in any
frame, the tracker shifts from first object to the second after finding good similarities. The
tracking object is assumed as shape of ellipse and similarity density function is calculated with
the help of Bhattacharya coefficient between target and candidate window. Implementation of
algorithm is shown in section II, Results and discussion are presented in section III and paper
is concluded finally in section IV.
Algorithm used
Kernel based Mean
Shift[4]
Mean shift[5-7]
Adaptive Block
matching[14]
PCA + ICA[3]
Nonlinear Kalman
filtering[15]
Mean shift with
Particle filter[16]
Eigen Tracking[17]

Edge detector [18]

II.

Feature Selection based on

Advantages/Limitations

Fixed point

Good tracking for uniform, single
and slow moving objects
mode seeking , clustering, Shadow,
Good for Cluster analysis and
Kernel, Gaussian Kernel
global optimization
Using object contour, motion vector, Computationally superior, good in
object boundary
compression
Basis image, generalization of PCA
Better face recognition
DTA + EGP + Unscented Kalman filter Fast operation
Means shift for gradient descend and
Particle filter fornon gauss and non
linear
View based representation, Eigen
space representation, articulated
objects, rigid, affine, image motion
Deformed object

Tracking in video images

Useful for view point and changes
in pose and Robust matching

Accurate with occlusion and
spurious edges
Table 1: Comparison of object tracking algorithms

KERNAL BASED MEAN ALGORITHM

Mean shift is a non parametric statistical method which was first introduced by Fukunaga in
1975[13], later it is used and explored by D Comaniciu [4-5] for object tracking applications. To
characterize the target, first a feature space is chosen. Then reference target model is
represented by its probability density function (PDF) q in the feature space. Similarly, a
candidate model is represented with PDF function p. A similarity density is calculated between
the target model and candidate model to match the maximum similarity with the help of
Bhattacharya coefficient ρ [p(x), q]. For example, the reference model can be chosen to be the
color PDF of the target. Without loss of generality, the target model can be considered as
centered at the spatial location 0. In the subsequent frame, a target candidate is defined at
location y, and is characterized by the PDF p(y). Both PDFs are to be estimated from the data.

October 18-20, 2013
Page 294


To satisfy the low-computational cost imposed by real-time processing discrete densities, i.e.,
m-bin histograms are used.
A. Target Model
First we need to initialize position and size of search window in first frame. The probability of
the feature u = 1, 2 ...m in the target model is then computed as in equation (1)
݊

‫ݍ‬௨ ൌ ‫ ܥ‬෍

݇||‫ߜ 2|| ݅ݔ‬ሾܾሺ‫ ݅ݔ‬ሻ െ ‫ݑ‬ሿ … … .1

݅ൌ1

Kernel profile k weights contribution by distance to centroid and is the Kronecker delta
function i.e
࢑ሺ࢞ሻ ൌ

ൌ૙

૚
ሺࢊ ൅ ૛ሻ ‫ כ‬ሺ૚ െ ԡ࢞ԡ૛ ሻ
૛࡯ࢊ

ܑ܎ԡ࢞ԡ ൏ 1

‫܍ܛܑܟܚ܍ܐܜ۽‬

Where Cd is the volume of a unit sphere in an equal number of dimensions to the histogram, x
is the distance between normalized pixel location (xi) and the center of the kernel(y), and d is a
given constant of 2. In order to apply a mean shift calculation, the set of histogram values is
weighted by Epanechnikov kernel to yield a smoothed set of values. it defines an ellipsoidal
region and gives more weights to pixel closer to the center of the kernel. This is useful because
pixels farther from the center of the object that those pixels are least reliable, The rationale for
using a kernel to assign smaller weights to pixels farther from the centre is that those pixels are
the least reliable, since they are the ones most affected by occlusion or interference from the
background. A kernel with Epanechnikov profile was essential for the derivation of the smooth
similarity function between the distributions, since Its derivative is constant; thus the kernel
masking lead to a function suitable for gradient optimization, which gave us the direction of the
target’s movement. The search for the matching target candidate in that case is restricted to a
much smaller area and therefore it is much faster than the exhaustive search.
A. Candidate model
Let {xi} be the normalized pixel locations of the target candidate, centred at y in the current
frame. The normalization is inherited from the frame containing the target model. Using the
same kernel profile k(x), but with bandwidth h, the probability of the feature u =1, 2 . . . m in
the target candidate is given by equation (2).
௡

ଶ

‫ ݕ‬െ ‫ݔ‬௜
‫݌‬௨ ሺ‫ݕ‬ሻ ൌ ‫ܥ‬௛ ෍ ݇ ൭ቤቚ
ቚቤ ൱ ߜሾܾሺ ‫ݔ‬௜ ሻ െ ‫ݑ‬ሿ. … .2
݄
௜ୀଵ

A. Similarity Function
Now a similarity functions between p and q plays the role of likelihood and its local maxima in
the image indicate the presence of objects in the second frame having representations similar
to q defined in the first frame as below in equation 3 and 4.


October 18-20, 2013
Page 295


݀ሺ‫ݕ‬ሻ ൌ ඥ1 െ ߩሾ‫݌‬ሺ‫ݕ‬ሻ, ‫ݍ‬ሿ........3

ߩሺ‫ݕ‬ሻ ൌ ߩሾ‫݌‬ሺ‫ݕ‬ሻ, ‫ ݍ‬ሿ ൌ ∑௠ ඥ‫݌‬௨ ሺ‫ݕ‬ሻ, ‫ݍ‬௨ ……….4
Ԧ
Ԧ
Ԧ
௨ୀଵ
The mode of this density in the local neighbourhood is the sought maximum which can be
found employing the mean shift procedure. In this procedure the kernel is recursively moved
from the current location to the new location according to the relation shown in equation (5).
Apply mean shift: Compute new location Z as

zൌ

౯ష౯౟ మ
ቚ| ሻ୷୧
h
౯ష౯౟ మ ………… 5
∑౤h ሺ୵୧୥|ቚ
ቚ| ሻ
౟సభ
h

∑౤h ሺ୵୧୥|ቚ
౟సభ

Where g(x) = -k’(x), assuming that the derivative of k(x) exists for all except for a finite set of
points and weight of pixel values are calculated as in equation (6).
௠

‫ݍ‬௨
‫ݓ‬௜ ൌ ෍ ඨ
ߜሾܾሺ‫ݔ‬௜ ሻ െ ‫ݑ‬ሿ … … … 6
‫݌‬௨ ሺ‫ݕ‬଴ ሻ
௨ୀଵ

A. Implementation Steps
The software based design flow of algorithm is well shown by flow chart in figure 1. Each
function is shown with red cooled.

III.

RESULTS AND DISCUSSION

In the implementation of the tracker, RGB colour spaces are used as a feature space, in which
feature space is quantized into 5 x 5 x 5 bins. The set of histogram values is weighted by
Epanechnikov kernel which yields a smoothed set of values. In the calculation of the kernel
profile the value of Cd = 2 and d=1is taken. The algorithm runs comfortably at 24 frames per
second (FPS) on 2.70 GHz PC, Matlab (version 7.60) as an implementation.
The tracking results of the mean shift algorithm are shown in figure 2, from left to right:
tracking before overlapping of two similar objects, in middle overlapping of both similar
objects and last tracker shifts to another similar object. The distance of target is calculated
between frames 320 to 550 with respect bin variations. Graph in figure 3, shows the metric
distance between the frames 320 to 550 which is very less compare to frames 450 to 470. It
signifies the maximum similarity (i.e. minimum distance) between the target window and the
candidate window in the successive frames from 320 to 340. The movement of the object in
these consecutive frames is slow in respect to frames from 450 to 470. The change in the
histogram affects the similarity (i.e. distance) between the target model and the candidate
model. Tracking of object coming towards the camera is used to check the scaling effect as
shown in figure 3 from left to right frames (50, 65 and 80). In frame 80 tracker moves out of
object which shows that this implementation cannot handle a change of scale from the object.
In first case, the size of the ellipse surrounding the object was fixed. Since the orientations of
the ellipse are only vertical or horizontal but to get movement in the Z axis difficult to follow in
this case. For example an object from the background and advancing toward the camera which

October 18-20, 2013
Page 296


means that size will increase due to which it is hard to monitor the object effectively in 2
dimensional. To track object in such case a scale change function is required to incorporate in
the algorithm. Tracking is observed in real time video streaming are shown in figure 4 with the
variation in speed of moving objects. Tracker follow the object very well once it is moving with
slow and uniform speed but it fails to track the objects for fast and non-uniform speeds.

Fig. 1: Flow chart of kernel based Mean Shift algorithm

October 18-20, 2013
Page 297


Fig. 2: Tracking of a moving person from left to right: in left figure, in middle overlapping of
similar object, at bottom tracker shifts to other similar object after overlapping.

Fig. 3: The minimum value of distance function of the frame index

Fig. 4: Tracking of object coming towards the frame (scale change): from left to right (frames
50, 65 and 80)

Fig. 5: Real Time Tracking

October 18-20, 2013
Page 298


IV.

CONCLUSION

The results of Kernel based mean shift algorithm is found to be smoothly tracking a single
object if there is a good separation between the two or more than two objects. But if the objects
are found similar and overlapped then simple mean shift may track a wrong object. So this
shortcoming may overcome by using the filters or with the combination of other algorithms.

REFERENCES
[1] Alper Yilmaz, Omar Javed, Mubarak Shah, “Object Tracking: A Survey”. ACM Computing
Surveys, Vol. 38, No. 4, Article 13, December 2006.
[2] Usman Ali, M.B. Malik and Khalid Munawar, hardware/software co-design of a real-time
kernel based tracking system, in journal of systems architecture, Volume 56, Issue 8, August
2010, pp. 317–326
[3] Y. Bar-Shalom, Tracking and Data Association, Academic Press Professional,Inc., San Diego,
CA, 1987
[4] D Comaniciu, Visvnathan Ramesh, Peter Meer, “Kernel-Based Object Tracking”, IEEE Trans
Pattern Anal. Mach.Intell, 25(5):564-577.
[5] Comaniciu, D., Ramesh, V., Meer, P., “Real-time tracking of non-rigid objects using mean
shift, in: Proc. IEEE Conference on Computer Vision and Pattern Recognition, Hilton Head,
vol. 2, pp. 142--149 (2000)
[6] Yizong Cheng, “Mean Shift, Mode Seeking, and Clustering”, IEEE Transaction on pattern
analysis and machine intelligence, Vol. 17, No. 8, August 1995.
[7] D. Comaniciu and P. Meer, “Mean shift: A robust approach toward feature space analysis,”
IEEE Trans. Pattern Anal. Machine Intel. vol. 24, no. 5, pp. 603–619, Dec. 2002.
[8] M. Correia, A. Campilho, “Real-time implementation of an optical flow algorithm”, Proc. ICIP,
Vol. 4, pp. 247-250, 2002
[9] Manoj Pandey, Dorothi Borgohain, Gargi Baruah, J S Ubhi and Kota Solomon Raju, Real Time
Object Tracking: Simulation and Implementation on FPGA based Soft Processor, Proc.
QSHINE 2013, Book Chapter, QSHINE 2013, LNICST 115, Springer, pp. 441–450, 2013.
[10] Manoj Pandey, Dorothi Borgohain, J S Ubhi and Kota Solomon Raju, Real Time
Histogram Computation in Kernel based Tracking System, in Proc. ICAES, pp. 171–174,
IEEE Computer Society 2013
[11] Usman Ali, M.B. Malik and Khalid Munawar, FPGA/Soft- Processor based real-time
object tracking system, in: Proceedings of the IEEE, 5th Southern Programmable Logic
Conference, 2009, pp. 33-37.
[12] Usman Ali, M.B. Malik and Khalid Munawar, hardware/software co-design of a real-time
kernel based tracking system, in journal of systems architecture, Volume 56, Issue 8, August
2010, pp. 317–326.
[13] K. Fukunaga, L.D. Hostetler, “The Estimation of the Gradient of a Density Function, with
applications in Pattern Recognition”, IEEE Transactions on Information Theory, January
1975, Vol. 21, pp. 32-40
[14] Karthik Hariharakrishnan and Dan Schonfeld, “Fast object tracking using adaptive block
matching”, IEEE Transaction on multimedia, Vol. 7, No. 5, October 2005.
[15] Constantinos Antoniou, Member, IEEE, Moshe Ben-Akiva, and Haris N. Koutsopoulos,
“Nonlinear Kalman Filtering Algorithms for On-Line Calibration of Dynamic Traffic
Assignment Models”, IEEE transactions on Intelligent Transportation Systems, vol. 8, no. 4,
December 2007, pp 661-670


October 18-20, 2013
Page 299


[16] Bai and Weiming Liu, “Improved Object Tracking with Particle Filter and Mean Shift”,
Proceedings of the IEEE International Conference on Automation and Logistics, August 18 21, 2007, Jinan, China.
[17] Michael J. Black and Allan D. Jepson “Eigen Tracking: Robust Matching and Tracking of
Articulated Objects Using a View-Based Representation” European Conf. on Computer
Vision, ECCV’96, Cambridge, England, April 1996
[18] Michael A. Greminger and Bradley J. Nelson “A Deformable Object Tracking Algorithm
Robust to Occlusions and Spurious Edges”, Proceedings of the 2005 IEEE International
Conference on Robotics and Automation Barcelona, Spain, April 2005

BIOGRAPHY
Manoj Pandey (Corresponding Author) was born in Sidharthnagar
(U.P.), India in October 10, 1982. He did his M.Sc in Electronics from
Deen Dayal Upadhyay Gorakhpur University, Gorakhpur, UP, India in
2005 and received M.Tech in Electronics Design and Technology from
Tezpur University (Central), Tezpur in year 2007. At present he is
working as an Assistant Professor at B K Birla Institute of Engineering
and Technology Pilani and pursuing PhD from Sant Longowal Institute of
Engineering & Technology, Longowal Punjab in area of FPGA based
Reconfigurable Architectures for Image Processing applications. The co-authors of this paper
are supervisor for his PhD thesis.


October 18-20, 2013
Page 300

Kernel based similarity estimation and real time tracking of moving

Recommended

More Related Content

What's hot (18)

Viewers also liked (7)

Similar to Kernel based similarity estimation and real time tracking of moving (20)

More from IAEME Publication (20)

Recently uploaded (20)

Kernel based similarity estimation and real time tracking of moving