# Least Trimmed Squares Approach to Lucas-Kanade Algorithm in Object Tracking Problems

Authors: Yih-Lon Lin
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

The object tracking problem is an important research topic in computer vision. For real applications such as vehicle tracking and face tracking, there are many efficient and real-time algorithms.  In this study, we will focus on the Lucas-Kanade (LK) algorithm for object tracking. Although this method is time consuming, it is effective in tracking accuracy and environment adaptation. In the standard LK method, the sum of squared errors is used as the cost function, while least trimmed squares is adopted as the cost function in this study. The resulting estimator is robust against outliers caused by noises and occlusions in the tracking process.  Simulations are provided to show that the proposed algorithm outperforms the standard LK method in the sense that it is robust against the outliers in the object tracking problems.


---

## Body

## 1. Introduction

The Lucas-Kanade (LK) algorithm was originally proposed by Lucas and Kanade in 1981 [1], which makes use of the spatial intensity gradient of the images to find a good match using a type of the Newton-Raphson iteration. The goal of the standard LK algorithm is to minimize the sum of squared errors (SSE) function between the template and the warped image region by adjusting the warping parameters.Based on the theory of robust statistics, various types of cost functions were adopted in many practical applications such as regression. One of the main approaches to robust regression involvesM-estimation [2–6]. The M-estimator is found to be robust to outliers in the response variable, but turned out not to be resistant to outliers in the explanatory variables, called leverage points. In fact, when there are outliers in the explanatory variables, the method has no advantage over least squares. In the 1980s, several alternatives to M-estimation were proposed as attempts to overcome the lack of such resistance. Least trimmed (sum of) squares (LTS) is a viable alternative [7–10].There are several robust LK algorithms proposed in the following literatures. TheM-estimators were adopted to LK models for tracking problems in [11–15]. The basic idea is to replace the cost function SSE by Huber or Hampel function so that the effects of outliers may be degraded. In [11], the authors generalized the LK approach to histogram-based tracking algorithm. It establishes a closer link between template matching and histogram-based tracking methods. Schreiber [12] proposed a novel variant of the LK algorithm for tracking bilaterally symmetric planar objects from a moving platform. This algorithm was capable of coping with any warping transformation and can be generalized for the case of objects possessing higher symmetry. According to analysis of data distributions, Senst et al. [13] proposed a robust local optical flow approach based on a modified Hampel estimator with robust characteristics. Fan et al. [14] proposed a robust template tracking with weighted active drift correction. The minimization of active drift correction is achieved by the inverse compositional algorithm, which consists of the tracking term and the drift correction term. In [15], a robust LK template matching algorithm was based on evidence which is accumulated over many frames. This algorithm described the drift correcting and used robust weights that are being updated from frame to frame. The previous papers emphasized robust inverse composition algorithm using a robust Huber or Hampel cost functions. However, there are many other methods for robust LK algorithm such as robust measurement of ocular torsion [16], visual tracking and learning [17], and graph-based transductive learning [18].The LTS estimator is highly resistant to leverage points and is robust to outliers in the response. When we expect there to be some number of observations in the data that we wish to put no weight in the modeling, LTS estimator is usually a good choice. The percentage of the data that we wish to put no weight is termed the trimming percentage or trimming parameter, and this parameter is usually prespecified for the data at hand. In this study, the main idea is to utilize the resistant property of the LTS estimators in the LK algorithm (LTS-LK) for object tracking problems when there are outliers caused by, for instance, noises and occlusions. The updating rules for the warping parameters using LTS-LK approach will be derived. Three simulations are provided in this paper, two for book-object tracking and one for face-object tracking. The simulation results show that the proposed method can effectively track the object when salt-and-pepper noises corruption or occlusion appears.The rest of this paper is organized as follows. In Section2, we outline the standard LK algorithm. Section 3 presents the detail of the proposed LTS-LK method. Some experimental results are provided in Section 4 to verify the performances of the proposed method. Finally, a conclusion is made in Section 5.


## 2. Lucas-Kanade Algorithm

Template tracking of an object in a video sequence is performed by extracting a template in the first frame and then finding the region which matches the template as close as possible in the surplus frames. The goal of LK method is to align a template imageT(x) to an input image I(x), where x=[xy]T is a column vector representing the pixel coordinates. Let W(x;p) denote the parameterized set of allowed warps, where p=[p1⋯p6]T is a vector of warping parameters. Here, we consider the following set of affine warps:
(1)W(x;p)=[W1W2]=[1+p1p3p21+p4][xy]+[p5p6].
The best match to the template in the new frame is found by minimizing the following SSE function:
(2)E=∑x[I(W(x;p))-T(x)]2,
where W(x;p) is defined in (1) and the sum is performed over all of the pixels x in the template image T(x). Based on the SSE function in (2), the goal of the LK algorithm is therefore to find
(3)pn+1=argminp∑x[I(W(x;pn))-T(x)]2,forn≥1,
where n is the frame number. Suppose that a current estimate of p is known and we wish to compute an appropriate increment Δp. The minimization problem in (3) can then be converted to
(4)argminΔp∑x[I(W(x;p+Δp))-T(x)]2.
Performing a first-order Taylor series expansion on I(W(x;p+Δp)) at Δp=0 in (4) yields
(5)∑x[I(W(x;p)+∇I∂W∂pΔp)-T(x)]2,
where ∇I=[∂I/∂x∂I/∂y]T is the gradient of the image I evaluated at W(x;p). The term ∂W/∂p is the Jacobian of the warp given by
(6)∂W∂p=[∂W1∂p1∂W1∂p2⋯∂W1∂p6∂W2∂p1∂W2∂p2⋯∂W2∂p6]=∂∂p[x+xp1+yp3+p5xp2+y+yp4+p6]=[x0y0100x0y01].
An approximate solution to (4) can be obtained by taking the partial derivatives of (5) with respect to Δp and setting them to zero. It is easy to derive that this approximate solution is given by
(7)Δp=H-1∑x[∇I∂W∂p]T[I(W(x;p))-T(x)],
where H is Gauss-Newton approximation to the Hessian matrix
(8)H=∑x[∇I∂W∂p]T[∇I∂W∂p].
Finally, the parameters are updated as
(9)p⟵p+Δp,
and the process is iterated until the estimate of parameters p converge or the pre-specified stopping criterion is met.


## 3. LK Algorithm Using LTS Approach

LetX⊆ℜn and Y⊆ℜp. Suppose we are given the training set
(10)S:={(xq,dq)}q=1l⊆X×Y.
In the following, we will use the subscript q to denote the qth observation. For instance, xqi denotes the ith component of the qth input xq∈ℜn, q∈l_, i∈n_. The residual (or error) eqk at the kth component of the difference between the desired output dqk and the predicted output yqk due to the qth observation is defined by
(11)eqk:=dqk-yqk,q∈l_,k∈p_.The LTS approach is to choose parameters that minimize the total sum of trimmed squared errors given by(12)Ψtotal=12∑k=1p∑q=1l*e(q)k2=12∑k=1p∑q=1la(R(eqk2))eqk2,
where l*≤l and the penalizing weight a(j) is defined by
(13)a(j):={1,1≤j≤l*,0,l*<j≤l.
Here, R(eqk2) denotes the rank of the residual eqk2, q∈l_, and e(1)k2≤…≤e(l)k2 are the ordered values of e1k2,…,elk2. A popular choice of l* is
(14)l*=[l2]+[(n+1)2],
where [b] indicates the largest integer less than or equal to b. In the following, the term (l-l*)/l is referred to as the trimming percentage.As given in the previous section, the values ofΔp in (7) are computed from the inverse compositional algorithm. To adapt the notation for LTS model, we regard the template image T(x) and subpixel location W(x;p) as one-dimensional vectors di and zi, 1≤i≤l, respectively, where l is the number of pixels in the template image. Now the training set becomes
(15)S:={(zi,di)}i=1l⊆ℜ2×ℜ.
The predictive function, a two-dimensional image, is given by
(16)f(x):=I(W(x;p)).
It can be regarded as a one-dimensional vector f(zi). The residuals are given by
(17)ρi:=di-f(zi),i∈l_.
One of the commonly used cost function is the l2-norm of the residuals ρ:=[ρ1…ρl]T∈ℜl. This is the cost function used in (4). To address the object tracking problems when there are outliers caused by, for instance, noises and occlusions, we will use sum of trimmed squared errors instead of the l2-norm. Consequently, the goal of the LTS estimator is to find the parameters Δp of LK algorithm that minimize the cost function defined by
(18)E=∑xa(R([I(W(x;p))-T(x)]2))×[I(W(x;p)+∇I∂W∂pΔp)-T(x)]2.
It is not difficult to derive that the variable Δp can be calculated as
(19)Δp=HT-1∑xa(R([I(W(x;p))-T(x)]2))×[∇I∂W∂p]T[I(W(x;p))-T(x)],
where the robust Hessian matrix is
(20)HT=∑xa(R([I(W(x;p))-T(x)]2))×[∇I∂W∂p]T[∇I∂W∂p].The flowchart of the proposed LTS-LK algorithm is shown in Figure1. Note that the linearized formulation (18) may be regarded as a linear weighted least squares regression problem. In practice, the inverse of Hessian matrix may pose some numberical difficulties in six-dimensional space. For higher dimension, recursive weighted least squares algorithm can be applied to solve this optimization problem. Here, we adopt direct computation of the inverse.Figure 1
Flowchart of LTS-LK algorithm.


## 4. Experimental Simulation

In this section, we compare the performances of standard LK and the LTS-LK algorithms for object tracking. Emphasis is put particularly on the robustness against outliers. Simulation programs are implemented using Borland C++ Builder 6.0 running on Microsoft Windows 7, Intel Core 2 Quad CPU, and 4 GB RAM platform.To demonstrate the robustness of the proposed algorithm, we present three object-tracking experiments, consisting of two “book-tracking” and one “face-tracking” video sequences. In Example1, the frames after the 100th of the “book” sequence are corrupted by salt-and-pepper noises in which a corrupted pixel has the intensity of 0 or 255. In Example 2, we add another type of corruption, a severe occlusion of about 1/3 template area at the 35th frame. Example 3 shows the same situation on face tracking with occlusion at the 240th frame. The trimming percentages used in our simulations are 5%, 20%, and 35% in the three examples, respectively. In the simulations, we set 20 as the maximal number of iterations and 0.0001 as the minimal change of Δp. The iteration stops when either of the two conditions is met.Example 1.
The “book” sequence is of size 320 × 240 containing 250 frames in which the object to be tracked is the book. In this experiment, the initial bounding box size is 60 × 80 pixels and contains about 6.25% of the frame size. Simulation results are shown in Figure2. The first and second rows show the results of the standard LK and the proposed LTS-LK algorithms, respectively. To demonstrate the robustness of LTS-LK algorithm, we randomly corrupt the video sequence with 20% noises, about 15,360 pixels, in the frames after the 100th frame. As observed, the standard LK algorithm fails to track the object in the 160th frame (the 3rd column), whereas our LTS-LK algorithm can effectively track the “book” object.Figure 2
Results of “book-tracking” sequence. Salt-and-pepper noises are added after Frame 100.Example 2.
In this example, the experiment deals with severe occlusions in another “book” sequence containing 60 frames, of size 320 × 240. Initial bounding box size is 50 × 70 containing about 4.5% of its original size. The results are shown in Figure3. As can be seen, the area of LK algorithm bounding box shrinks down to 50% of its original szie at Frame 25 since occlusion appears, that is, because the standard LK algorithm is based on least-squares principle and is, therefore, sensitive to outliers. In the second row, we can see that the proposed LTS-LK algorithm on this sequence produces much better results when the object “book” suffers from severe occlusions. The mean squared error (MSE) of the tracked areas from LK algorithm and trimmed MSE from LTS-LK algorithm at the 35th frame are 8.95 and 1.76, respectively. As a consequence, LTS-LK algorithm demonstrates significant robustness under severe occlusion.Figure 3
Results of “book-tracking” sequence. Occlusion is added after Frame 25.Example 3.
The experiment deals with severe occlusions in “face-tracking” sequence containing 350 frames, of size 320 × 240. The results are shown in Figure4. In the LK algorithm, there appears numerical error on updating the variable Δp at the 240th frame. It means that the standard LK algorithm diverges. Therefore, the variable Δp needs not be updated after the 240th frame. As observed, the LK algorithm fails after the 240th frame, whereas our proposed algorithm can effectively track the “face” object. Again, the proposed LTS-LK algorithm is quite robust against severe occlusion.
From the illustrative examples above, when applying the LTS approach to object tracking problems, the proposed LTS-LK model is robust against outliers. This is achieved by choosing an appropriate trimming percentage. Unfortunately, there is no systematic way to select a proper trimming percentage for the general object tracking problem at hand. The choice is usually problem dependent.Figure 4
Results of “face-tracking” sequence. Occlusion is added after Frame 100.


## 5. Conclusion

The main issue of this paper is the robustness against outliers caused by noises and occlusions in the video object tracking problems. The proposed robust algorithm adopts the LTS scheme for the LK algorithm. Experimental results show that the proposed LTS-LK algorithm outperforms the standard LK. It is noted that SSE minimization criterion is used in standard approach to search the optimal parameters. However, it is known that the estimation of parameters based on least squares criterion is vulnerable to outliers. The main contribution of this paper is the use of LTS robust criteria, instead of the standard least squares criterion, for the search for the LK parameters, and this provides a robust object tracking application.



---

*Source: 324824-2013-07-16.xml*