The mean shift algorithm

The mean shift algorithm is a nonparametric estimator of density gradient. It has led to many applications such as tracking [18,56], filtering and image segmentation [19] or recognition of freehand sketches [100].

The goal of the algorithm is to find a local maximum of density amongst a set of $n$ points $\left\{{\bf x}_i\right\}_{i=1 \ldots n}$ in a $d$-dimensional Euclidian space. In our case, the space is the appearance parameter space $P$.

The discrete density of the set of points $\left\{{\bf x}_i\right\}_{i=1 \ldots n}$ is approximated by a continuous density. A kernel $K({\bf x})$ is placed at each point $\bf {x}$ to get a multivariate kernel density estimate for the whole set of points.

Given a window radius $h$, the density computed at a point ${\bf x}$ is given by:

$$\hat{f}({\bf x})=\frac{1}{nh^d}\sum^n_{i=1}K\left(\frac{{\bf x}-{\bf x}_i}{h}\right)$$ (24)

In practice, we are using the Epanechnikov kernel given by the formula:

$$K({\bf x})=\left\lbrace \begin{array}{ll} \frac{1}{2}v_d^{-1... ...bf x}^T {\bf x} < 1 \\ 0 & {\rm otherwise} \end{array}\right.$$ (25)

where $v_d$ is the volume of the unit $d$-dimensional sphere [90].

Since $K$ is differentiable, we can compute the gradient of $\hat{f}$:

$$\nabla\hat{f}({\bf x})=\frac{1}{nh^d}\sum^n_{i=1}\nabla K\left(\frac{{\bf x}-{\bf x}_i}{h}\right)$$ (26)

For the Epanechnikov kernel it becomes:

$$\nabla \hat{f}({\bf x})=\frac{1}{n h^d }\frac{d+2}{v_d h^2}\sum_{{\bf x}_i \in S_h({\bf x})}\left({\bf x}_i-{\bf x}\right)$$ (27)

where $S_h({\bf x})$ is a hypersphere of radius $h$ centred on ${\bf x}$.

We can see, from equation 5.4 that an extremum of density is reached at the point ${\bf y}$ given by:

$${\bf y}=\frac{1}{n_{\bf {\bf x}}}\sum_{{\bf {\bf x}}_i \in S_h({\bf {\bf x}})}{\bf {\bf x}}_i$$ (28)

where $n_{\bf x}$ is the number of points present in the hypersphere $S_h({\bf x})$.

The vector $M_h({\bf x})={\bf y}-{\bf x}$ is called the mean-shift vector. If we translate $\bf x$ by $M_h({\bf x})$, we reach an extremum in the kernel density function $\hat{f}$.

The idea of the mean shift algorithm is to iteratively find an estimate of the local extremum of density within the current window and then translate the centre of the window to the found extremum.

Comaniciu and Meer have proved the convergence of this algorithm as well as the monotonic increase in the density estimate through the iterations given some hypotheses that are verified in the case of an Epanechnikov kernel [20].

The mean shift algorithm involves iterating the following steps:

• computation of the mean shift vector $M_h({\bf x})$
• translation of the window $S_h({\bf x})$ by $M_h({\bf x})$

until convergence.

Figure 5.5 summarises the algorithm.

Figure 5.5: The mean shift algorithm.

In the mean shift algorithm, the radius $h$ of the hypersphere acts as a smoothing parameter. It represents the scale at which we consider the extrema to be local. A small value will end up in selecting only the start position as being a maxima of density in its close neighbourhood. A large value will skip some local maxima of small areas to focus on local maxima of larger areas. Since different data have different scales, $h$ has to be adapted manually for each dataset.

We can use the mean shift algorithm to find local maxima of density in the set of points defined by the trajectory. We initialise the mean shift algorithm at each point in turn, the result being the closest local maxima of density. This provides us with a set of local maxima in the trajectory points distribution. In practice, we are only using every $q$ points as it does not significantly affect the result to much while increasing the speed of the search by a factor of $q$.

We compute the set of nodes by adding all nodes that are close to the local maxima. We use the same procedure as algorithm A2 to find the closest node with a distance less than $d$ to a local maxima: we select the node amongst the consecutive nodes that lies in the hypersphere of radius $d$ and centred at the closest local maxima.

The parameter $d$ has to be adapted manually for each dataset. A too small value of $d$ results in too few points being selected in the neighbourhood of a maxima of density. Often, only one point is selected in that case, as shown by figure 5.6. If the value is too large, we take the risk of selecting too few good nodes by choosing each nodes between too many candidates at a time. This is shown on figure 5.7.

Figure 5.6: Small distance for the selection of neighbours. The maxima found by the mean shift algorithm is located by a black square. Only one point can be selected as a node due to the small size of the hypersphere.

Figure 5.7: Large distance for the selection of neighbours. The maxima found by the mean shift algorithm is located by a black square. Only one point can be selected as a node on figure 5.7(a) due to the large size of the hypersphere covering a large part of the trajectory. A smaller distance $d$ for the selection would have led to two nodes selected as shown on figures 5.7(b) and 5.7(c), since we are entering and leaving the hypersphere twice while following the trajectory.

[Large radius] [Selection of one node] [Selection of the other node]