The mean-shift algorithm¹ is an efficient method for mode seeking without doing an exhaustive search, which leads to a real-time property. It has been introduced recently for tracking applications.^{2, 3, 4, 5} However, the fixed kernel bandwidth is always leading to poor localization in tracking objects changing in scale. A moment is used to compute the size of the tracking windows.² However, the computational complexity is too high to meet the real-time requirement. In general, an object scale is detected by calculating the Bhattacharyya coefficient for three different sizes (same scale, $\pm 5\%$ change) and choosing the size that gives the highest similarity to the target model.⁵ Since it is a naive method for scale adaptation without considering the underlying relationship between the similarity and the object scale changes, the size of the tracking windows cannot always keep up with the object scale changes. In this paper, this relationship is theoretically analyzed for a possible total solution in the future.

Definition 1. A round region $T$ containing the whole object region $F$ and some background region $B$ is called a tracking window. Function $c\left(T\right)$ and $c\left(F\right)$ denote the center of $T$ and $F$ , respectively. Their distance is measured by $d(T,F)=\parallel c\left(T\right)-c\left(F\right)\parallel$ .

Definition 2. Let ${\left\{x_i\right\}}_{i=1\dots n}$ be the pixel locations with $c\left(T\right)$ as the origin point. The kernel histogram⁵ of $T$ with $m$ bins is defined by $P={\left\{p_{\mu }\right\}}_{\mu =1\dots m}$ where

Here $k$ is the kernel function and $r$ is the kernel bandwidth, which determines the radius of $T$ . Function $q:R^2\to \{1\dots m\}$ associates the pixel at location $x_i$ to the index $q\left(x_i\right)$ of the kernel-histogram bin corresponding to the color of that pixel. $C$ is derived by imposing the constraint ${\sum }_{\mu =1}^m{p}_{\mu }=1$ . Suppose the color distribution of $F$ is distinguished from $B$ . It can be approximately satisfied in many applications, e.g., traffic surveillance, and described by ${\sum }_{\mu =1}^m{p}_{\mu }^i\bullet p_{\mu }^j=0$ where the color distribution of $F$ and $B$ are represented by $P_i={\left\{p_{\mu }^i\right\}}_{\mu =1\dots m}$ and $P_j={\left\{p_{\mu }^j\right\}}_{\mu =1\dots m}$ , respectively.

Definition 3. The similarity of two kernel histograms $P_i$ and $P_j$ with $m$ bins is measured by the Bhattacharyya coefficient⁵

where $p_{\mu }^i$ and $p_{\mu }^j$ are the value of bin $\mu$ in $P_i$ and $P_j$ , respectively.

Theorem 1. Given $T_1$ with $c\left(F_1\right)=c\left(T_1\right)$ in frame $i$ and $T_2$ with the same position of $T_1$ in frame $i+1$ where object scale and position are changed, $\forall T_3∊\text{frame}$ $i+1$ , if $d(T_2,F_2)<d(T_3,F_3)$ then $\rho (2,1)>\rho (3,1)$ .

Proof. By assuming without loss of generality that (1) the object shrinks its scale from frame $i$ to $i+1$ . (2) $F_i$ , $i=1,2,3$ consists of $u$ subregions with different intensity levels, i.e., $F_i={\left\{f_j\right\}}_{j=1\dots u}$ , while $B_i$ , $i=1,2,3$ consists of ${\nu }_i$ subregions with different intensity levels, i.e., $B_i={\left\{b_j\right\}}_{j=1\dots {\nu }_i}$ . (3) Consider $T_i$ ; suppose its kernel histogram $P_i={\left\{p_{\mu }^i\right\}}_{\mu =1\dots m}$ consists of two entries, sets ${\left\{f{p}_j^i\right\}}_{j=1\dots u}$ and ${\left\{b{p}_j^i\right\}}_{j=1\dots {\nu }_i}$ , corresponding to the subregion ${\left\{f_j\right\}}_{j=1\dots u}$ and ${\left\{b_j\right\}}_{j=1\dots {\nu }_i}$ , respectively, where $u+\max ({\nu }_1,{\nu }_2,{\nu }_3)⩽m$ .

The continuous form of Eq. 1 is as follows:

whereBy using integral theorem of mean, we havewhere $S_{f_i}^2$ and $S_{f_i}^3$ are areas of subregion $f_j$ in $F_2$ and $F_3$ , respectively.

The fixed kernel bandwidth leads to $C_2=1∕{\iint }_{\sigma =T_2}k\left({\parallel x∕r\parallel }^2\right)d\sigma =C_3$ , and it is clear that $S_{f_j}^2=S_{f_j}^3$ owing to $F_2=F_3$ . Since $k$ is monotonic decreasing¹ and $d(T_2,F_2)<d(T_3,F_3)$ , we have $k\left({\parallel {\xi }_{f_j}^2∕r\parallel }^2\right)>k\left({\parallel {\xi }_{f_j}^3∕r\parallel }^2\right)$ . Consequently, we obtain $f{p}_j^2>f{p}_j^3$ . Moreover, ${\sum }_{j=1}^{{\nu }_2}b{p}_j^2<{\sum }_{j=1}^{{\nu }_3}b{p}_j^3$ holds owing to the constraint

Since the scale of $F_2$ is less than $F_1$ , the area of $B_2$ is greater than $B_1$ . Thus, ${\sum }_{j=1}^{{\nu }_1}b{p}_j^1<{\sum }_{j=1}^{{\nu }_2}b{p}_j^2$ holds and then ${\sum }_{j=1}^{u}f{p}_j^2<{\sum }_{j=1}^{u}f{p}_j^1$ . Therefore,According to Eqs. 2, 4, the geometric interpretation of the Bhattacharyya coefficient is the cosine of the angle between the $m$ -dimensional unit vectors $(\sqrt{p_1^i}\dots \sqrt{p_m^i})$ and $(\sqrt{p_1^j}\dots \sqrt{p_m^j})$ . The smaller angle they have, the more similar the two kernel histograms are. For the target tracking application, this angle is equal to the angle between two 2-D unit vectors: ${\mathbf{Z}}_i=[{\left({\sum }_{j=1}^{u}f{p}_j^i\right)}^{1∕2},{\left({\sum }_{j=1}^{{\nu }_i}b{p}_j^i\right)}^{1∕2}]$ and ${\mathbf{Z}}_j=[{\left({\sum }_{k=1}^{u}f{p}_k^j\right)}^{1∕2},{\left({\sum }_{k=1}^{{\nu }_j}b{p}_k^j\right)}^{1∕2}]$ . Then, $\rho (i,j)$ can be measured by $\angle ({\mathbf{Z}}_i,{\mathbf{Z}}_j)$ . Using Eqs. 4, 5 in conjunction with the geometric relationship, it is clear that $\angle ({\mathbf{Z}}_3,{\mathbf{Z}}_1)>\angle ({\mathbf{Z}}_2,{\mathbf{Z}}_1)$ . Finally, $\rho (2,1)>\rho (3,1)$ .

Using theorem 1, we can easily determine that the Bhattacharyya coefficient $\rho (t,1)$ is monotonic decreasing and achieves its maximum in the case where $d(T_t,F_t)=0$ . It means the image in $T_t$ $[d(T_t,F_t)=0]$ is most similar to the image in $T_1$ . As long as some parts of the object in the next frame reside inside the kernel, theorem 1 ensures mean-shift iterations converge to the object center.^{2, 5}

In our experiments, the object kernel histogram computed by the Gaussian kernel has been derived in the RGB space with $32\times 32\times 32$ bins. Figure 1 shows two video clips where the size of tracking window (white circle) is unchanged. The top row shows the tracking results where the object expands its scale, while the bottom row demonstrates the results for the object shrinking its scale. In the first frame of each clip, the initial kernel histogram is obtained from the initial tracking window whose center overlaps the object center. Figure 2 shows the Bhattacharyya coefficients corresponding to the tracking windows centered in a $60\times 60$ neighborhood around the object center. Figures 2a and 2b correspond to Figs. 1b and 1d, respectively. The Bhattacharyya coefficient in Fig. 2b is monotonic decreasing and the maximum corresponds to the object center, which validates our theorem. In the case where the object expands its scale and can not be enwrapped by the tracking window, the monotonic decreasing profile in Fig. 2b no longer holds and poor localization potentially occurs; see also top row in Fig. 1. The reason lies in the fact that there are more local maxima in Fig. 2a and any location of a tracking window that is too small will yield a similar value of the Bhattacharyya coefficient.

In conclusion, the changes of object scale and position within the fixed kernel will not impact the localization accuracy of the mean-shift tracking algorithm. When the object scale exceeds the size of the tracking window, the tracker outputs poor localization. On the contrary, when the object shrinks its scale, the center of the tracking window locates the object center all the time. Indeed, our previous work⁴ for tracking rigid objects with scale changes is based on this conclusion. We hope this paper will valuable for fully solving scaling problems within the mean-shift framework in the future.