ISSN : 1796-2048
Volume : 1    Issue : 4    Date : July 2006

K-means Tracker: A General Algorithm for Tracking People
Chunsheng Hua, Haiyuan Wu, Qian Chen and Toshikazu Wada
Page(s): 46-53
Full Text:
PDF (1,541 KB)

In this paper, we present a clustering-based tracking algorithm for tracking people (e.g. hand, head,
eyeball, body, and lips). It is always a challenging task to track people under complex environment,
because such target often appears as a concave object or having apertures. In this case, many
background areas are mixed into the tracking area which are difficult to be removed by modifying the
shape of the search area during tracking. Our method becomes a robust tracking algorithm by
applying the following four key ideas simultaneously: 1) Using a 5D feature vector to describe both
the geometric feature “(x,y)” and color feature “(Y,U,V)” of each pixel uniformly. This description
ensures our method to follow both the position and color changes simultaneously during tracking;
2) This algorithm realizes the robust tracking for objects with apertures by classifying the pixels,
within the search area, into “target” and “background” with K-means clustering algorithm that uses
both the “positive” and “negative” samples. 3) Using a variable ellipse model (a) to describe the
shape of a nonrigid object (e.g. hand) approximately, (b) to restrict the search area, and (c) to model
the surrounding non-target background. This guarantees the stable tracking of objects with various
geometric transformations. 4) With both the “positive” and “negative” samples, our algorithm
achieves the automatic self tracking failure detection and recovery. This ability makes our method
distinctively more robust than the conventional tracking algorithms. Through extensive experiments
in various environments and conditions, the effectiveness and the efficiency of the proposed
algorithm is confirmed.

Index Terms
K-means clustering, negative samples, tracking failure detection and recovery