Stefan Duffner
email: stefan.duffner@liris.cnrs.fr

Christophe Garcia
email: christophe.garcia@liris.cnrs.fr

PixelTrack: a fast adaptive algorithm for tracking non-rigid objects

In this paper, we present a novel algorithm for fast tracking of generic objects in videos. The algorithm uses two components: a detector that makes use of the generalised Hough transform with pixel-based descriptors, and a probabilistic segmentation method based on global models for foreground and background. These components are used for tracking in a combined way, and they adapt each other in a co-training manner. Through effective model adaptation and segmentation, the algorithm is able to track objects that undergo rigid and non-rigid deformations and considerable shape and appearance variations. The proposed tracking method has been thoroughly evaluated on challenging standard videos, and outperforms state-of-theart tracking methods designed for the same task. Finally, the proposed models allow for an extremely efficient implementation, and thus tracking is very fast.

Introduction

Given a video stream, tracking arbitrary objects that are non-rigid, moving or static, rotating and deforming, partially occluded, under changing illumination and without any prior knowledge is a challenging task. This unconstrained tracking problem where the object model is initialised from a bounding box in the first video frame and continuously adapted has been increasingly addressed in the literature in the past years. When no prior knowledge about the object's shape and appearance is available, one of the main difficulties is to incrementally learn a robust model from consecutive video frames. This model should generalise to new unseen appearances and avoid drift, i.e. the gradual inclusion of background appearance, which can ultimately lead to tracking failure.

Our method addresses these issues with an adaptive approach combining a detector based on pixel-based descriptors and a probabilistic segmentation framework.

Related Work

Earlier works [21,[START_REF] Comaniciu | Real-time tracking of non-rigid objects using mean shift[END_REF][START_REF] Pérez | Color-based probabilistic tracking[END_REF][START_REF] Odobez | Embedding motion in model-based stochastic tracking[END_REF][START_REF] Yao | Multi-camera multi-person 3D space tracking with MCMC in surveillance scenarios[END_REF][START_REF] Hare | Struck: Structured output tracking with kernels[END_REF] on visual object tracking mostly consider a bounding box (or some other simple geometric model) representation of the object to track, and often a global appearance model is used. These classical methods are very robust to some degree of appearance change and local deformations (as in face tracking), and also allow for a fast implementation. However, for tracking non-rigid objects that undergo a large amount of deformation and appearance variation, e.g. due to occlusions or illumination changes, these approaches are less suitable. Although some algorithms effectively cope with object deformations by tracking their contour (e.g. [31,[START_REF] Yilmaz | Object contour tracking using level sets[END_REF][START_REF] Chockalingam | Adaptive fragments-based tracking of non-rigid objects using level sets[END_REF]), most of them require the object to be moving or need prior shape knowledge [12]. Others, describe an object by a relatively dense set of keypoints that are matched in each frame [START_REF] Lepetit | Keypoint recognition using randomized trees[END_REF][START_REF] Hare | Efficient online structured output learning for keypoint-based object tracking[END_REF] to track the object. However, these methods have mostly been applied to relatively rigid objects.

Many existing methods, follow a tracking-by-detection approach, where a discriminative model of the object to track is built and updated "online", i.e. during the tracking, in order to adapt to possible appearance changes. For example, Adam et al. [START_REF] Adam | Robust fragmentsbased tracking using the integral histogram[END_REF] use a patch-based appearance model with integral histograms of colour and intensity. The dynamic patch template configuration allows to model spatial structure and to be robust to partial occlusions. Grabner et al. [START_REF] Grabner | Real-time tracking via on-line boosting[END_REF] proposed an Online Adaboost (OAB) learning algorithm that dynamically selects weak classifiers that discriminate between the object image region and the background. Later, they extended this method to a semi-supervised algorithm [START_REF] Grabner | Semi-supervised on-line boosting for robust tracking[END_REF] that uses a fixed (or adaptive [START_REF] Stalder | Beyond semisupervised tracking: Tracking should be as simple as detection, but not simpler than recognition[END_REF]) prior model to avoid drift and an online boosting framework learning with unlabelled data. Babenko et al. [START_REF] Babenko | Visual tracking with online multiple instance learning[END_REF] presented another online method based on Multiple Instance Learning (MIL), where the positive training examples are bags of image patches containing at least one positive (object) image patch. Besides boosting algorithms, Online Random Forests have been proposed for adaptive visual object tracking [START_REF] Saffari | On-line random forests[END_REF][START_REF] Santner | Parallel robust online simple tracking[END_REF], where randomised trees are incrementally grown to clas-sify an image region as object or background. Kalal et al. [START_REF] Kalal | P-N learning: Bootstrapping binary classifiers by structural constraints[END_REF] also use randomised forests which they combine effectively with a Lucas-Kanade tracker in a framework called Tracking-Learning-Detection (TLD) where the tracker updates the detector using spatial and temporal constraints and the detector re-initialises the tracker in case of drift.

In order to cope with changing appearance, Mei et al. [28] introduced the l 1 tracker that is based on a sparse set of appearance templates that are collected during tracking and used in the observation model of a particle filter. Recently, several extensions have been proposed [START_REF] Bao | Real time robust l1 tracker using accelerated proximal gradient approach[END_REF][START_REF] Hong | Dual-force metric learning for robust distracter-resistant tracker[END_REF][START_REF] Zhang | Robust visual tracking via structured multi-task sparse learning[END_REF] to improve the robustness and reduce the complexity of this method. However, these approaches are still relatively timeconsuming due to the complex l 1 minimisation. A sparse set of templates has also been used by Liu et al. [27], but with smaller image patches of object parts, and by Kwon et al. [START_REF] Kwon | Visual tracking decomposition[END_REF] in their Visual Tracking Decomposition (VTD) method. In a similar spirit, Ross et al. [START_REF] Ross | Incremental learning for robust visual tracking[END_REF] propose a particle filter algorithm called IVT that uses an observation model relying on the eigenbasis of image patches computed online using an incremental PCA algorithm. Other approaches, more similar to ours, consist in using a pixelbased classifier [START_REF] Avidan | Ensemble tracking[END_REF][START_REF] Cannons | Visual tracking using a pixelwise spatiotemporal oriented energy representation[END_REF]. Avidan et al. [START_REF] Avidan | Ensemble tracking[END_REF], for example, proposed an ensemble tracking method that label each pixel as foreground or background with an Adaboost algorithm that is updated online. However, all of these methods still operate more or less on image regions described by bounding boxed and inherently have difficulties to track objects undergoing large deformations.

To overcome this problem, recent approaches integrate some form of segmentation into the tracking process. For example, Nejhum et al. [START_REF] Nejhum | Visual tracking with histograms and articulating blocks[END_REF] proposed to track articulated objects with a set of independent rectangular blocks that are used in a refinement step to segment the object with a graphcut algorithm. Similarly, although not segmenting the object, Kwon et al. [START_REF] Kwon | Tracking of a non-rigid object via patch-based dynamic appearance modeling and adaptive Basin Hopping Monte Carlo sampling[END_REF] handle deforming objects by tracking configurations of a dynamic set of image patches, and they use Basin Hopping Monte Carlo (BHMC) sampling to reduce the computational complexity. Other approaches [START_REF] Ren | Tracking as repeated figure/ground segmentation[END_REF][START_REF] Wang | Superpixel tracking[END_REF] use a segmentation on the superpixel level. Bibby et al. [8] propose an adaptive probabilistic framework separating the tracking of non-rigid objects into registration and level-set segmentation, where posterior probabilities are computed at the pixel level. Aeschliman et al.

[2] also combined tracking and segmentation in a Bayesian framework, where pixel-wise likelihood distributions of several objects and the background are modelled by Gaussian functions the parameters of which are learnt online. In a different application context, pixel-based descriptors have also been used for 3D articulated human-body detection and tracking by Shotton et al. [START_REF] Shotton | Realtime human pose recognition in parts from single depth images[END_REF] on segmented depth images. In the approach recently proposed by Belagiannis et al. [START_REF] Belagiannis | Segmentation based particle filtering for real-time 2d object tracking[END_REF], a graph-cut segmentation is applied separately to the image patches provided by a particle filter.

The work of Godec et al. [START_REF] Godec | Hough-based tracking of nonrigid objects[END_REF] is probably the most similar to ours. The authors proposed a patch-based voting algorithm with Hough forests [START_REF] Gall | Lempitsky. Hough forests for object detection, tracking, and action recognition[END_REF]. By back-projecting the patches that voted for the object centre, the authors initialise a graph-cut algorithm to segment foreground from background. The resulting segmentation is then used to update the patches' foreground and background probabilities in the Hough forest. This method achieves state-of-the-art tracking results on many challenging benchmark videos. However, due to the graph-cut segmentation it is relatively slow. Also, the segmentation is discrete and binary, which can increase the risk of drift due to wrongly segmented image regions.

Motivation

The algorithm presented in this paper is inspired by these recent works on combined tracking and segmentation, which is beneficial for tracking non-rigid objects. Furthermore, patch-based local descriptors have shown state-ofthe-art performance due to their possibility of handling appearance changes with large object deformations.

In this paper, we integrate these concepts and present a novel tracking-by-detection algorithm that relies on a Hough-voting scheme based on pixel descriptors. The method tightly integrates with a probabilistic segmentation of foreground and background that is used to incrementally update the local pixel-based descriptors and vice versa. The local Hough-voting model and the global colour model operate both at the pixel level and thus allow for very efficient model representation and inference.

The following scientific contributions are made:

• a fast tracking algorithm using a detector based on the generalised Hough transform and pixel descriptors in combination with a probabilistic soft segmentation method,

• a co-training framework, where the local pixel-based detector model is used to update the global segmentation model and vice versa,

• a thorough performance evaluation on standard datasets and a comparison with other state-of-the-art tracking algorithms.

Note that the main goal of the proposed approach is to provide an accurate position estimate of an object to track in a video. Here, we are not so much interested in a perfect segmentation of the object from the background. Better approaches for segmentation exist in the literature but they are rather complex. Thus, instead of using these, we aimed at reducing the overall computational complexity.

In the following, we will first describe the overall approach (Section 2). Then we will detail each of the com- ponents of the algorithm (Sections 3-5). And finally, some experimental results will be presented (Section 7).

Overall Approach

The overall procedure of detection, segmentation, tracking, and model adaptation for one video frame is illustrated in Fig. 1. The algorithm receives as input the current video frame as well as the bounding box and segmentation from the tracking result of the previous frame. The pixelbased Hough transform is applied on each pixel inside the search window, the enlarged bounding box, i.e. each pixel votes for the centre position of the object according to the learnt model. Votes are cumulated in a common reference frame, the voting map, and the position with the highest sum of votes determines the most likely position of the object's centre (see Section 3 for a more detailed explanation). Then, the pixels that have contributed to the maximum vote are determined. This process is called backprojection. In parallel, the image region corresponding to the search window is segmented using the current segmentation model. That is, each pixel is assigned a foreground probability (see Section 4). The position of the tracked object is updated using the maximum vote position and the centre of mass of the segmentation output (see Section 5). Finally, the models are adapted in a co-training manner to avoid drift. That means, the segmentation model is updated using the back-projection, and the pixel-based Hough model is adapted according to the segmentation output (see Section 6 for more details).

Pixel-based Hough Voting

We developed a new detection algorithm relying on the generalised Hough transform [START_REF] Ballard | Generalizing the hough transform to detect arbitrary shapes[END_REF]. In contrast to existing models developed recently for similar tasks (e.g. [START_REF] Gall | Lempitsky. Hough forests for object detection, tracking, and action recognition[END_REF][START_REF] Godec | Hough-based tracking of nonrigid objects[END_REF]) which use Hough forests, i.e. Random Forests trained on small image patches, or the Implicit Shape Model (ISM) [START_REF] Leibe | Combined object categorization and segmentation with an implicit shape model[END_REF] our method operates at the pixel-level.

This has the following advantages:

• pixel-based descriptors are more suitable for detecting objects that are extremely small in the image (e.g. for far-field vision),

• the feature space is relatively small and does not (or very little) depend on spatial neighbourhood, which makes training and updating of the model easier and more coherent with the object's appearance changes,

• the training and the application of the detector is extremely fast as it can be implemented with look-up tables.

One drawback of using a pixel-based Hough model is when the object's image region contains primarily pixels of very similar colours (and gradients). In that case, the pixels on their own may not be discriminative enough to infer the objects centre position. Note that also patch-based methods have difficulties with uniform regions. In practice, however, this is rarely the case and may be controlled by increasing the discriminative power of the descriptors (at the cost of invariance). Also, in this tracking framework, this risk is considerably reduced by combining the detector with the segmentation output.

Let us now consider the model creation and application in detail. Figure 2 illustrates the model creation (training) and detection process.

Training

Let us denote x = (x 1 , x 2 ) the position of a pixel I(x) in an image I. In the training image, the pixels inside a given initial bounding box are quantised according to the vector composed of its HSV colour values (with separate V quantisation) and its x and y gradient orientation (with a separate quantisation for low gradient magnitudes) (see Fig. 2 contain M z displacement vectors d m z = (x zm , w zm ), each associated with a weight w zm = 1.0. Thus, training consists in constructing D, where each pixel I(x) in the given bounding box produces a displacement vector d z (arrows in Fig. 2) corresponding to its quantised value z x and pointing to the centre of the bounding box.

Detection

In a new video frame, the object can be detected by letting each pixel I(x) inside the search window vote according to D z corresponding to its quantised value z x . The right part of Fig. 2 illustrates this. Each vote is a list of displacements d m z that are weighted by w zm and accumulated in a voting map. The detector's output is then simply the position in the voting map with the maximum value x max .

Note that, as illustrated in figure 2, the position estimation is "diffused" by two factors: the deformation of the object (one of the green pixels in the figure), and pixels of the same colour (green and blue pixels). But the maximum value in the voting map is still distinctive and corresponds well to the centre position of the object. This could also be observed in our experiments.

Nevertheless, to be robust to very small deformations we group the votes in small voting cells of 3×3 pixels (as [START_REF] Godec | Hough-based tracking of nonrigid objects[END_REF]).

Backprojection

With the position of the maximum in the voting map x max , we can determine which pixels in the search window contributed to it during the detection. This process is illustrated in Fig. 1 and is called backprojection. More precisely, let z be the value of pixel I(x). Then, the backprojection b at each position x ∈ Ω is defined as:

b x = w zm if d m z voted for x max , 0 otherwise. (1)
The backprojected pixels are used for adapting the segmentation model (see Section 6 for more details). The idea behind this is that, intuitively, pixels that contributed to x max are most likely corresponding to the object.

Segmentation

to the local pixel-wise Hough model, a global segmentation model is trained and adapted to allow for varying object shapes and for a better discrimination between foreground (object) and background, especially when the shape and appearance changes drastically and abruptly.

A probabilistic soft segmentation approach is adopted here (similar to [2]). Let c t,x ∈ {0, 1} be the class of the pixel at position x at time t: 0 for background, and 1 for foreground, and let y 1:t,x be the pixel's colour observations from time 1 to t. For clarity, we'll drop the index x in the following. In order to incorporate the segmentation of the previous video frame at time t -1 and to make the estimation more robust, we use a recursive Bayesian formulation, where, at time t, each pixel (in the search window) is assigned the foreground probability:

p(c t = 1|y 1:t ) = Z -1 p(y t |c t = 1) c ′ t-1 p(c t = 1|c ′ t-1 ) p(c ′ t-1 |y 1:t-1 ) , ( 2
)
where Z is a normalisation constant to make the probabilities sum to 1. The distributions p(y t |c t ) are modelled with HSV colour histograms with 12 × 12 bins for the H and S channels and 12 separate bins for the V channel. The foreground histogram is initialised from the image region defined by the bounding box around the object in the first frame. The background histogram is initialised from the image region surrounding this rectangle (with some margin between). The transition probabilities for foreground and background are set to:

p(c t = 0|c t-1 ) = 0.6 p(c t = 1|c t-1 ) = 0.4 (3)
which is an empirical choice that has been validated experimentally. Note that the tracking algorithm is not very sensitive to these parameters.

As opposed to recent work on image segmentation (e.g. [START_REF] Rother | Grabcut: Interactive foreground extraction using iterated graph cuts[END_REF]), we treat each pixel independently, which, in general, leads to a less regularised solution but at the same time reduces the computational complexity considerably. As stated in section 1.2, we are not so much interested here in a perfectly "clean" segmentation but rather in fast and robust tracking of the position of an object.

Tracking

In a new video frame, pixel-based detection and segmentation are performed inside a search window Ω, which is set here to twice the size of the object's bounding box. Then, the object's position X t can be re-estimated. To this end, we utilise not only the output of the detector, i.e. the maximum position in the voting map, but also the segmentation output. Clearly, this makes the tracking algorithm more robust to non-rigid deformations. More precisely, we calculate the centre of mass of the soft segmentation produced by Eq. 2:

x s = 1 S x∈Ω p(c x = 1|y) x, (4)
where S is the sum of all foreground probabilities p(c x = 1|y) in the search window Ω. Then, we set the new object position to a linear combination of voting map maximum x max and x s :

X t = αx s + (1 -α)x max . (5)
The factor α determines how much we trust in the segmentation's position compared to the Hough model's estimation. It is computed dynamically at each frame by a simple reliability measure that is defined as the proportion of pixels in the search window that change from foreground to background or vice versa, i.e. crossing the threshold p(c x = 1|y) = 0.5. A high value of α means that the shape of the object has changed considerably from the previous frame to the current one, and consequently the Hough voting is assumed to be less accurate.

Model adaptation

Both pixel-based Hough model and segmentation model are updated at each frame in a co-training manner, i.e. the output of one model is used to update the other one. To update the Hough model, only foreground pixels are used, that is pixels for which p(c x = 1|y) > 0.5. For each of these pixels x the displacement d to the new object's centre is calculated, and its weight w is set according to its foreground probability:

w ← γ p(c x = 1|y) + (1 -γ) w if d ∈ D z , p(c x = 1|y) otherwise,
where γ = 0.1 is the update factor. In the second case, d is added to D z . For computational and memory efficiency, we limit the size of each D z and only keep the K displacements with the highest weights (K = 20 in our experiments). The foreground and background distributions of the segmentation model are adapted using the backprojection b x . That is, the colour distribution p(y|b > 0.5) of the backprojected pixels is calculated, and used to linearly update the current foreground colour distribution: p(y t |c t = 1) = δ p(y|b > 0.5) + (1δ) p(y t-1 |c t-1 = 1) , (6) where δ = 0.1 is the update factor. The background colour distribution is updated in the same way but using the colour distribution from a rectangular frame surrounding the object borders (as for initialisation).

Evaluation

Evaluation Protocol

We conducted quantitative evaluation on two sets of challenging standard videos that are commonly used in the literature. The tracking accuracy and speed on these datasets has been measured and compared to two state-ofthe-art tracking methods.

The first dataset1 has been constructed by Babenko et al. [START_REF] Babenko | Visual tracking with online multiple instance learning[END_REF] from various other publications, and it has been used by Godec et al. [START_REF] Godec | Hough-based tracking of nonrigid objects[END_REF]. It contains 8 videos (with more than 5 000 frames) of objects or faces that undergo mostly rigid deformations and some rather large lighting variations as well as partial occlusions. Most of these sequences are actually in grey-scale format (except "David", "Girl", and "Face Occlusions 1"). For this reason, we do not use the segmentation part of our algorithm here because it is based on colour. That means, tracking is only performed by Hough voting.

The second dataset2 is composed of 11 videos (around 2 500 frames) showing moving objects that undergo considerable rigid and non-rigid deformations. This dataset has also been used by [START_REF] Godec | Hough-based tracking of nonrigid objects[END_REF] and partially by [START_REF] Kwon | Visual tracking decomposition[END_REF] among others.

We compared our algorithm which we call PixelTrack to two state-of-the-art methods: HoughTrack (HT) proposed by Godec et al. [START_REF] Godec | Hough-based tracking of nonrigid objects[END_REF] and Tracking-Learning-Detection (TLD) by Kalal et al. [START_REF] Kalal | P-N learning: Bootstrapping binary classifiers by structural constraints[END_REF]. Although, these and other previous works have reported tracking accuracy results on some of the videos from our datasets, we evaluated these methods again using our performance measure in order to have a consistent comparison. Initialisation is done manually, where HT has been initialised by the values given by their authors, and the same initialisation has been used for TLD. For our method, the initial rectangle is smaller as it should contain as background pixels as possible in order to obtain a good initial segmentation model.

To measure the performance of the different tracking algorithms, we determine, for each video, the percentage of frames in which the object is correctly tracked. In each video frame, the tracking is considered correct if the PAS-CAL VOCC [START_REF] Everingham | The pascal visual object classes (VOC) challenge[END_REF] overlap measure RT ∩RGT RT ∪RGT is above a threshold, where R T is the rectangle from the tracking algorithm, and R GT is the ground truth rectangle surrounding the object. We set the threshold to 0. value would discriminate our method too much because the bounding box that is output currently does not change its size and aspect ratio during the tracking, and it is rarely initialised to surround the complete object. Finally, we want to emphasise that we strictly used the same parameters of our algorithm for all the videos and all the experiments.

Results

Table 1 summarises the evaluation results on the Babenko videos. Although our method is not designed for grey-scale videos and, thus, does not show its full potential, it still performs better than other state-of-the-art methods on many videos of the dataset and also on average. Fig. 3 shows some tracking results from the "Tiger 2" sequence. HoughTrack loses track after frame 100. Also TLD very early stops to detect the object and removes the track, whereas PixelTrack is able to follow the object despite the appearance changes and occlusions.

Table 2 shows the results for dataset 2 with non-rigid deformations. For 8 out of 11 video sequences our method outperforms the other algorithms or is on par. Also the average of correct tracking is almost 7 percentage points HT TLD PixelTrack 2. [START_REF] Avidan | Ensemble tracking[END_REF] 5.2 113.8

Table 3. Average overall processing speed in frames per second. Measured without screen display.

higher than HT . The two videos that are the most difficult for the proposed method are "Motocross", where the motorbike does a complete flip, changes its size in the video, and where the background is very cluttered, and "Cliff Dive 2" where the appearance (and shape) of foreground and background changes dramatically. Fig. 4 illustrates some tracking results of the three compared methods on one of the sequences: "Diving". The two baseline methods lose the track at some point. The proposed algorithm is able to track the diver despite considerable shape and appearance changes. Fig. 5 shows some more tracking results of PixelTrack.

Finally, we measured the average processing speed of each algorithm for all the 19 videos on a 3.4 GHz Intel Xeon processor. In terms of speed, the proposed method outperforms the other two by a factor of around 20 for TLD and 50 for HT. The reason why HT is relatively slow is the graphcut segmentation, which is computationally demanding (but on the other hand also quite accurate). The code of HT is implemented in C++ using OpenCV library. Whereas, TLD uses Matlab with pre-compiled OpenCV code. The fast execution speed is a real advantage of the proposed approach. This is due to pixel-based Hough voting that allows for an extremely efficient implementation with lookup-tables as well as a fast segmentation algorithm.

Conclusions

We presented an algorithm for tracking generic objects in videos without any prior knowledge. It is an effective combination of a local pixel-based detector based on a Hough voting scheme and a global probabilistic segmentation method that operate jointly and update each other in a co-training manner. Our algorithm is very fast compared to existing methods, which makes it suitable for realtime applications, or tasks where many objects need to be tracked at the same time, or where large amounts of data need to be processed (e.g. video indexation). Experimental results show that the method outperforms state-of-theart tracking algorithms on challenging videos from standard benchmarks.

Figure 1 .

 1 Figure 1. The overall tracking procedure for one video frame.Each pixel inside the search window (blue dotted rectangle) in the input image casts a vote (1) according to the current Hough transform model (darker: high vote sum, lighter: low vote sum). Then the maximum vote sum (circled in red) and all pixels that have contributed (i.e. the backprojection) are determined (2). In parallel, the current segmentation model is used to segment the image region inside the search window (3) (binarised segmentation shown in red). Finally, after updating the objects current position (4), the segmentation model is adapted (5) using the backprojected image pixels, and the Hough transform model is updated[START_REF] Bao | Real time robust l1 tracker using accelerated proximal gradient approach[END_REF] with foreground pixels from the segmentation and background pixels from a region around the object (blue frame).

Figure 2 .

 2 Figure 2. Training and detection with the pixel-based Hough model. Left: the model D is constructed by storing for each quantised pixel value in the given bounding box all the displacement vectors to the object's centre position (here only colour is used for illustration). Right: the object is detected in a search window by accumulating the displacement votes of each pixel in a voting map (bright pixels: many votes, dark pixels: few votes).

Table 1 .

 1 Babenko sequences: percentage of correctly tracked frames.

	1. A higher

Table 2 .

 2 Non-rigid object tracking: percentage of correctly tracked frames.

http://vision.ucsd.edu/ bbabenko/project miltrack.shtml

http://lrs.icg.tugraz.at/research/houghtrack/


Stefan Duffner
email: stefan.duffner@liris.cnrs.fr

Christophe Garcia
email: christophe.garcia@liris.cnrs.fr

Unsupervised Online Learning of Visual Focus of Attention

In this paper, we propose a novel approach for estimating visual focus of attention in video streams. The method is based on an unsupervised algorithm that incrementally learns the different appearance clusters from low-level visual features extracted from face patches provided by a face tracker. The clusters learnt in that way can then be used to classify the different visual attention targets of a given person during a tracking run, without any prior knowledge on the environment and the configuration of the room or the visible persons. Experiments on public datasets containing almost two hours of annotated videos from meetings and video-conferencing show that the proposed algorithm produces state-of-the-art results and even outperforms a traditional supervised method that is based on head orientation estimation and that classifies visual focus of attention using Gaussian Mixture Models.

Introduction

Generally, the Visual Focus of Attention (VFOA) of a person denotes the target -an object or another personthe person is looking at, at a given point in time. The automatic estimation of the VFOA of a person from video is of great importance in many applications, such as humancomputer interaction, advanced video-conferencing, smart meeting rooms, or human behaviour analysis in general, and much research has been conducted in this area in the past.

Principally, the VFOA of a person is defined by the person's eye gaze direction. Many studies about automatic gaze estimation from video exist [START_REF] Morimoto | Eye gaze tracking techniques for interactive applications[END_REF][START_REF] Wang | Study on eye gaze estimation[END_REF], but their use is mostly limited to close-up and near-frontal views of a person's face, for example in Human-Computer Interaction applications. In this paper, we will focus on more challenging scenarios where the camera is fixed at a few meters from the filmed persons and where the persons stay roughly at the same places, like in formal meetings or video-conferencing applications. Previous work on VFOA analysis in such open spaces has mostly been based on the estimation of head pose as a surrogate for gaze [START_REF] Stiefelhagen | Head orientation and gaze direction in meetings[END_REF][START_REF] Siracusa | A multi-modal approach for determining speaker location and focus[END_REF][START_REF] Ba | A Rao-Blackwellized mixed state particle filter for head pose tracking[END_REF][START_REF] Otsuka | Conversation scene analysis with dynamic bayesian network based on visual head tracking[END_REF][START_REF] Ba | Recognizing visual focus of attention from head pose in natural meetings[END_REF][START_REF] Voit | Deducing the visual focus of attention from head pose estimation in dynamic multi-view meeting scenarios[END_REF][START_REF] Zhang | Monitoring visual focus of attention via local discriminant projection[END_REF]. This is done either globally, e.g. by learning to classify image patches of the head at different angles based on lowlevel visual features or locally, i.e. by localising certain facial features and by geometrically and statistically inferring the global orientation (see [START_REF] Murphy-Chutorian | Head pose estimation in computer vision: a survey[END_REF] for a literature survey). Further, with video, head pose estimation can be included in a joint head and pose tracking algorithm [START_REF] Lu | Model and exemplar-based robust head pose tracking under occlusion and varying expression[END_REF][START_REF] Ba | A Rao-Blackwellized mixed state particle filter for head pose tracking[END_REF][START_REF] Lanz | Joint bayesian tracking of head location and pose from low-resolution video[END_REF][START_REF] Ricci | Learning large margin likelihoods for realtime head pose tracking[END_REF]. Early works of Stiefelhagen et al. [START_REF] Stiefelhagen | Modeling focus of attention for meeting indexing based on multiple cues[END_REF], for example, used a Gaussian Mixture Model (GMM) on head pose angles to estimate VFOA. The model is initialised with k-means and further updated with an Expectation-Maximisation algorithm. They also showed that using the other participant's speaking status increases the VFOA performance. Otsuka et al. [START_REF] Otsuka | Conversation scene analysis with dynamic bayesian network based on visual head tracking[END_REF] proposed a method based on a Dynamic Bayesian Network that also analyses the group behaviour and detects certain conversational patterns. A GMM and Hidden Markov Model (HMM) approach for modelling and recognising VFOA was proposed by Smith et al. for people walking by an outdoor advertisement [START_REF] Smith | Tracking the visual focus of attention for a varying number of wandering people[END_REF] and by Ba and Odobez for analysing meeting videos [START_REF] Ba | Recognizing visual focus of attention from head pose in natural meetings[END_REF]. In the latter work, the authors also presented a MAP adaptation method to automatically adapt the VFOA model to the individual persons as well as a geometrical model (based on findings from [START_REF] Freedman | Eye-head coordination during head-unrestrained gaze shifts in rhesus monkeys[END_REF][START_REF] Hayhoe | Eye movements in natural behavior[END_REF]) combining head orientation and eye gaze direction. Voit and Stiefelhagen [START_REF] Voit | Deducing the visual focus of attention from head pose estimation in dynamic multi-view meeting scenarios[END_REF] built on this geometrical model and presented VFOA recognition results on a dynamic dataset with multiple cameras. Recently, Ba and Odobez [START_REF] Ba | Multiperson visual focus of attention from head pose and meeting contextual cues[END_REF] extended their approach on VFOA estimation for meetings with a Dynamic Bayesian Network (DBN) that incorporates contextual information, like speaking status, slide change, and modelling conversation behaviour.

As the experimental results of these works show, head pose can be used effectively to estimate the VFOA of a group of people, e.g. in a meeting room, to a certain extend. However, there are certain drawbacks of this approach: for example, in uncontrolled environments it is difficult to estimate head pose reliably because it often requires a large amount of annotated training data of head appearances or shapes beforehand in order to model all the possible varia-Figure 1. Process of the proposed approach tions of a head and face among different people as well as for a given individual. These data are often not available, or too time-consuming to produce. Further, for accurate results, a relatively precise localisation of the head, the face, or facial features is crucial but challenging in unconstrained application scenarios.

In this paper, we propose a novel approach that alleviates these problems. Our algorithm, given a video stream from a single camera and the rough 2D position estimation of a person's head, incrementally learns to automatically extract the VFOA of the person without explicitly estimating head pose or gaze and without any prior model of the head, face, the room configuration, or other external conditions. The proposed method learns on-the-fly the different classes of targets in an unsupervised way directly from the lowlevel visual features. This means also that, as opposed to supervised algorithms, it will not assign labels to the different targets (e.g.'table', 'screen', 'person 1'). However, we will experimentally show that the proposed unsupervised approach is able to identify and estimate the (unlabelled) targets with higher accuracy than a classical supervised approach. The fact that no pre-trained model is needed makes this approach especially interesting for applications where the specific environment, as well as the configuration of the room and the filmed persons is not known a priori, and where an explicit training phase is not possible.

Principal approach

The overall process of our approach is illustrated in figure 1. First, a basic tracking algorithm is initialised and tracks a rectangular face region throughout the video stream. The image patch inside the tracked face region is extracted and visual features, Histograms of Oriented Gradients (HOG), are calculated to initialise the VFOA model at the first video frame and to update it at each subsequent frame. At the same time, the model that has been learnt so far is used to estimate the person's VFOA target (e.g. table, other person) from the face patch. Note that the learning is done on-the-fly and does not require any prior knowledge on head pose or room configuration. Another advantage of this approach is that the VFOA estimation is completely independent from the face tracking algorithm, which means that the standard tracking method used here can easily be replaced by a different, possibly more accurate, algorithm.

For tracking a face, we used a standard particle filter approach, very similar to the one presented in [START_REF] Pérez | Color-based probabilistic tracking[END_REF]. It provides a solution for the classical recursive Bayesian model, where, assuming we have the observations Y 1:t from time 1 to t, we estimate the posterior probability distribution over the state X t at time t:

p(X t |Y 1:t ) = 1 C p(Y t |X t ) × Xt-1 p(X t |X t-1 )p(X t-1 |Y 1:t-1 ) dX t-1 , (1)
where C is a normalisation constant. In our experiments, the state X t ∈ R 3 is composed of the position and scale of the face. The state dynamics p(X t |X t-1 ) is defined by a first order auto-regressive model with Gaussian noise:

p(X t |X t-1 ) = N (X t-1 ; 0, Σ p ) . (2)
The observations likelihood is defined as:

p(Y t |X t ) ∝ exp -λ 9 r=1 D 2 B [h * r , h r (X t )] , (3)
where λ is a constant, h r (X t ) are HSV colour histograms extracted from a grid of r = 9 cells centred at X t , h * r is the reference histogram initialised from the face region in the first frame, and D B is the Bhattacharyya distance. As in [START_REF] Pérez | Color-based probabilistic tracking[END_REF], the histogram bins for the H and S channels are decoupled from the V channel. Also the quantisation is applied at two different levels, i.e. 4 bins and 8 bins, to improve the robustness under difficult lighting conditions. This leads to an overall observation vector size of 828.

Learning Visual Focus of Attention

Overview

The tracking algorithm described in the previous section provides us at each video frame with a bounding box of the tracked face. The principal idea is to compute visual features from the underlying image patch described by this rectangle and directly classify the VFOA of the person at that point in time.

Here, we make use of the fact that the head orientation of a person in a given scenario (e.g. a meeting) is not completely random. There are a few stationary angles that a head takes most of the time. And in the scenarios we are dealing with, these head poses mostly correspond to VFOA targets. Using an unsupervised clustering algorithm we model these stationary head poses directly in the lowlevel feature space. Thus, we estimate VFOA from these low-level features without an error-prone intermediate step of head pose estimation. The proposed algorithm incrementally learns these clusters from the texture features extracted on-the-fly from the video stream, which makes it appropriate for applications that do not require (or even allow) prior training or adaption of different room configurations, lighting conditions, or other scene-dependant variables.

Learning Algorithm

Let us denote O t ∈ R N the observed feature vector of a face image patch at time t. Here, we propose to use HOG-like features computed on an array of 4 by 4 nonoverlapping cells (see Fig. 2(a)). For each cell, two normalised two-dimensional histograms of unsigned oriented gradients and magnitudes are computed using a specific quantisation scheme illustrated in Fig. 2(b). The gradient orientation is quantised in 4 bins and the magnitude in 2 bins. An additional bin (with no orientation) is used for very weak gradients (in the centre of the half circle in the diagram). Also, to improve the overall robustness and discriminative power, we compute two histograms at different quantisation levels for orientation: 4 and 8, and normalise each of them separately. Thus, the dimension N of the feature vector is: 16•(4•2+1+8•2+1) = 416. One advantage of these histogram features is that they are relatively robust to small spatial shifts of the overall bounding box, which frequently occur with common face tracking methods.

The visual feature vectors O t at time t are used to incrementally learn the VFOA classes. To this end, we propose a specific sequential k-means clustering algorithm with an adaptive number of clusters. The algorithm constructs a model of k clusters corresponding to the VFOA classes and described by their mean feature vectors µ i and a global diagonal co-variance matrix Σ = diag(σ 1 , . . . , σ N ). Algorithm 1 summarises the main learning procedure. At each point in time t the observed feature vector O t is computed, and the closest cluster c t is determined using the normalised Algorithm 1 Proposed incremental learning algorithm

k = k ini µ i = O 0 i = 1..k n i = 0 i = 1..k Σ = Σ ini for t = 1 to T do c t = argmin i (D(O t , µ i )) d = 2 N (N +1) k i=1 k j=i+1 (D(µ i , µ j )) if d(O t , c t ) > θ d then k ← k + 1 µ k = O t end if n c ← n c + 1 µ ct ← µ ct + 1 nc t (O t -µ ct ) µ ct-1 ← µ ct-1 + α nc t-1 (O t -µ ct-1 ) µ i ← µ i + 1 n 2 i (O t -µ i ) i ∈ Ω incrementally update Σ end for
Euclidean distance:

D(O t , µ i ) = N j=1 (o t,i -µ i,j ) 2 σ 2 j + ǫ , (4)
with ǫ being a small constant avoiding division by zero. Also, the mean distance d between each of the k clusters is calculated, and a new cluster is created if the distance of the current feature vector to the closest cluster is greater than θ d, where θ is a parameter of our algorithm (set to 2 in our experiments). Existing clusters are not removed or merged in this algorithm.

Eventually, we incrementally update the mean µ ct of the closest cluster, the mean of the previous closest cluster µ ct-1 (with a lower factor α = 0.3 here), and also the means in a "neighbourhood" Ω (i.e. with adjacent indexes) but with a quadratically decreasing update factor. Updating the previous closest cluster enforces a certain temporal continuity of the model. Updating the neighbouring means (inspired by self-organising maps) ensures a certain topographical coherence in the feature space and limits outliers in the initial learning phase.

Finally, the global covariance matrix Σ is incrementally updated using the current feature vector O t . At each time t, the algorithm classifies the observed features O t of a face into one of the k clusters: c t , and, as we will show in the following experimental results, the learnt classes correspond a large degree to specific targets of VFOA.

Experiments 4.1. Data

We evaluated the proposed approach on three public datasets from different scenarios, each containing a certain number of persons sitting around a table and filmed roughly from the front (see Fig. 3). The VFOA targets are different for each dataset, due to the scenario and the layout of the room. The three datasets are the following:

TA2 1 [5]: in this set there are two videos from two different rooms where people communicated over a videoconferencing system and performed a shared task on a laptop in front of them. In the first video there are four persons and in the second there are two, and the defined VFOA targets are the table, the camera, and the other persons, resulting in 5 targets for the first video and 3 for the second. For each person, the targets over 7 500 frames (5 minutes), 30 minutes in total, have been annotated.

IHPD2 [START_REF] Ba | Evaluation of multiple cue head pose estimation algorithms in natural environements[END_REF]: this dataset consists of the "meeting" part the Idiap Head Pose Database. It contains eight meeting recordings with four persons, where one video shows two participants behind a table. The annotated VFOA targets here are the table, the slide screen, and the other persons (the whiteboard target has not been used here). 110 040 frames (∼ 1 hour 13 minutes) with VFOA annotation have been used in total for the evaluation. PETS 20033 : this dataset contains two videos from a formal meeting of six participants (scenario D), where each video shows 3 of the persons roughly from the front (similar to IHPD). Here, the VFOA targets that have been annotated for each participant are the other five participants. The provided VFOA annotation for the 6 persons and 47 000 frames (∼30 minutes) in total has been used. Table 1 summarises the properties of these datasets.

Annotation has been done manually and frame-byframe, where frames with ambiguous visual focus and transition phases have not been annotated. Table 1. The three datasets and annotation used for evaluation.

Evaluation

As our algorithm is unsupervised, we don't have the actual estimated VFOA targets (the labels) that we can directly compare to the ground truth. For evaluation purposes, i.e. after running our method on the whole video, we therefore assign to each cluster the VFOA target that maximises VFOA accuracy. That means, we assume that we know which target each cluster corresponds to. We believe that this is not a very restrictive assumption, as the labels could be assigned in a separate processing step, for example by incorporating a more general discriminative classifier trained beforehand.

As an accuracy measure, we used the Frame-based Recognition Rate (FRR) of the VFOA for all the videos and averaged it over each datasets and over several runs. The FRR is simply the proportion of frames with correctly recognised VFOA:

F RR = N c N t , (5)
where N c is the number of correct classifications, and N t is the total number of annotated video frames. As our algorithm is learning the VFOA model incrementally, we need to account for a certain training phase, which we don't include in the evaluation. We used 8 000 (∼ 5 min.) training frames in the beginning of the videos (not annotated), and evaluated the FRR on the following sequence with annotation. This length has been chosen in order to have enough training data for all the VFOA targets of a person, as sometimes a target is focused for the first time only after several minutes.

We compared the proposed approach to a variant that uses a fixed number of clusters. We also compared it to a classical supervised approach, that uses a specific face detection and tracking algorithm, a head pose estimator as in [14], and Gaussian Mixtures Models (GMM) to model different VFOA targets in terms of head pose pan and tilt angles as in [START_REF] Stiefelhagen | Modeling focus of attention for meeting indexing based on multiple cues[END_REF][START_REF] Ba | Recognizing visual focus of attention from head pose in natural meetings[END_REF]. In this approach, the head pose model is trained beforehand in a supervised way, and the GMM parameters have been partly trained and partly defined manually.

Results

First, we will show some qualitative results on the clustering that is obtained on some of the videos. To illustrate this, we saved for each tracking run the face image regions corresponding to the feature vectors that were closest to the cluster centres. Fig. 4 shows some examples. We can see that the images come from different head poses mostly corresponding to real VFOA targets. Clearly, some targets might not be captured by the model, as in the top right example of Fig. 4 (corresponding to the left-most person in the top-left image of Fig. 3) because the three other persons are almost seated in the same gaze direction. In the bottom right example, two clusters (corresponding to the second and fourth image) have been created for the same VFOA target: the table. Apart from these errors, the results mostly make sense.

Additionally, we evaluated the proposed algorithm using the metric and the three datasets described above. The tracking algorithm has been initialised manually with a bounding box around the face. Table 2 shows the FRR for each dataset, for the proposed method with fixed cluster size k = 5, variable cluster size, and the classical supervised approach described above. One can see that the proposed approach outperforms the supervised method with an average FRR of 52% compared to 46%. The variant with fixed cluster size is generally worse than the baseline method, except for the PETS 2003 dataset. This is probably due to the fact that the cluster centres are all initialised at the beginning and not when they are actually required as in the variable case. These results are comparable or superior to those published in the literature, although the evaluation protocols are not exactly the same due to the unsupervised and incremental nature of our method. Note that we do not include any temporal modelling (e.g. a HMM) or contextual information in the VFOA estimation process as in other existing work. This may additionally improve the overall performance.

The overall tracking algorithm, implemented in C++, runs at around 80-90 fps on a 3.6GHz processor for a 720 × 576 video (face size ∼ 50 × 80), where around 11% of CPU time is spent on feature extraction for VFOA, i.e. gradient computation on the whole image, and less than 1% on the VFOA learning and classification.

Conclusion

We presented an algorithm that incrementally, and in an unsupervised way, learns a VFOA model directly from lowlevel gradient histogram features extracted from face images coming from a tracking algorithm. In a meeting room or video-conferencing setting, the proposed method is able to automatically learn the different VFOA targets of a person without any prior knowledge about the number of persons or the room configuration. By assigning a VFOA label to each cluster, a posteriori, we evaluated the VFOA recognition rate for three different datasets and almost 2 hours of annotated data. The obtained results are very promising and show that this type of unsupervised learning can outperform traditional supervised approaches.

Future work will investigate different types of visual features, cluster merging, and the possibility of automatically assigning meaningful labels to the clusters. Also, we will study the generalisation capability of the algorithm to unseen videos (same room with different persons) as this might enable a broader range of practical applications.

Figure 2 .

 2 Figure 2. Visual features extraction for the VFOA model. a) HOGlike features are computed on a grid of 4 × 4 cells placed on the tracked face. b) To compute the histograms, gradient orientation is quantised into 4 bins (respectively 8 bins) and magnitude into 2 bins.

Figure 3 .

 3 Figure 3. Example frames from the three datasets that have been used for evaluation. First two: TA2 dataset, middle two: PETS 2003 dataset, and last two: IHPD dataset. (Faces have been blurred manually.)

Figure 4 .

 4 Figure 4. Four examples of face images that are closest to the corresponding learnt cluster centres. Upper-left and lower-left: from IHPD dataset. Upper-right and lower right: from TA2 (first video).

Table 2 .

 2 Average frame-based recognition rate of VFOA (in %).

		TA2 IHPD PETS 2003 average
	supervised	58.8	49.4	26.5	46.5
	fixed k = 5 45.7	46.8	35.2	44.1
	variable k	61.5	51.0	45.0	52.0

https://www.idiap.ch/dataset/ta2

https://www.idiap.ch/dataset/headpose

http://www.cvg.rdg.ac.uk/slides/pets.html