Efficient structured $\ell 1$ tracker based on laplacian error distribution

Abstract

Recently, sparse representation has been applied to visual tracking by casting the tracking problem into linear regression problem with sparse coefficient constraint. Under the Gaussian error distribution assumption, the reconstructed loss function is composed of sum-of-squares error term and $\ell 1$ regularization, which is sensitive to the outliers caused by occlusion and local deformation. In this paper, we propose a robust and efficient $\ell 1$ tracker based on laplacian error distribution and structured similarity regularization in a particle filter framework. Specifically, we model the error term by laplacian distribution, which has better robustness to the outliers than Gaussian distribution. Meanwhile, in contrast to most existing $\ell 1$ trackers that handle particles independently, we exploit the dependence relationship between particles and impose the structured similarity regularization on the sparse coefficient set. The customized Inexact Augmented Lagrange Method (IALM) is derived to efficiently solve the optimization problem in batch mode. In addition, we also reveal that the proposed method is related to the robust regression with self-adaptive Huber loss function. Both the computational efficiency and tracking accuracy are enhanced by this novel cost function and optimization strategy. Qualitative and quantitative evaluations on the largest open benchmark video sequences show that our approach outperforms most state-of-the-art trackers.

Appendices

Appendix 1: Inference details for structure similarity regularization

For notational simplicity, we ignore the symbol $a$ of the representation coefficient. Under the condition of that $g (c_i,c_j)=\Vert c_i-c_j\Vert _2$, Eq. 4 can be reformulated as follows:

$$\begin{aligned}&\sum _{i=1}^N\sum _{j=1}^Nw_{ij}\Vert c_i-c_j\Vert _2\nonumber \\ =&\sum _{i=1}^N\sum _{j=1}^Nw_{ij}\left( \Vert c_i\Vert _2+\Vert c_j\Vert _2-2c_i^\mathrm {T}c_j\right) \nonumber \\ =&\sum _{i=1}^N\sum _{j=1}^Nw_{ij}\Vert c_i\Vert _2+\sum _{i=1}^N\sum _{j=1}^Nw_{ij}\Vert c_j\Vert _2-2\sum _{i=1}^N\sum _{j=1}^Nw_{ij}c_i^\mathrm {T}c_j\nonumber \\ =&\sum _{i=1}^NW_{(i,:)}\Vert c_i\Vert _2+\sum _{i=1}^NW_{(:,j)}\Vert c_j\Vert _2-2\sum _{i=1}^N\sum _{j=1}^Nw_{ij}c_i^\mathrm {T}c_j\nonumber \\ =&2\left( \sum _{i=1}^NW_{(i,:)}\Vert c_i\Vert _2-\sum _{i=1}^N\sum _{j=1}^Nw_{ij}c_i^\mathrm {T}c_j\right) \nonumber \\ =&2\mathrm {tr}(C\left[ \begin{array}{llll} W_{(1,:)} &{} &{} &{} \\ &{} W_{(2,:)} &{} &{} \\ &{} &{} \ddots &{} \\ &{} &{} &{} W_{(N,:)} \\ \end{array} \right] C^\mathrm {T}-CWC^\mathrm {T})\nonumber \\&i.e. \quad \sum _{i=1}^N\sum _{j=1}^Nw_{ij}\Vert c_i-c_j\Vert _2=2\mathrm {tr}\left( CLC^\mathrm {T}\right) , \end{aligned}$$

(16)

where the fourth equality of (A.1) holds due to the symmetric properties of the matrix $W$, that is $W_{(i,:)}=W_{(:,i)}$.

Appendix 2: The convergence properties of customized IALM algorithm for Eq. 7

To proof Theorems 1, we first give the following two lemmas:

Lemma 1

Given the norm $\Vert \cdot \Vert$ in Hilbert space and the sub-gradient variable $y\in \partial \Vert \cdot \Vert$, the corresponding dual norm $\Vert \cdot \Vert ^*$ is no more than 1. (see [16] for a Proof).

Lemma 2

The sequences $\{Y_{(\cdot ,k)}\}$ , $\{Y_{(\cdot ,k)}\}^*$ and $\{\tilde{Y}_{(\cdot ,k)}\}$ are all bounded, where $\tilde{Y}_{(G,k)}=Y_{(G,k-1)}+\mu _{k-1}(C_{k-1}-G_{k-1})$, $\tilde{Y}_{(H,k)}=Y_{(H,k-1)}+\mu _{k-1}(C_{k-1}-H_{k-1})$ and $\tilde{Y}_{(E,k)}=Y_{(E,k-1)}+\mu _{k-1}(X-DC_k-E_{k-1})$.

Proof

Setting the derivatives of Eq.8 with respect to $G$ equal to zero, we obtain the following condition: $\quad 0\in \partial \Vert G_{k+1}^*\Vert _1-Y_{(G,k)}^*-\mu _k(C_{k+1}^*-G_{k+1}^*)$, i.e. $Y_{(G,k+1)}^*=Y_{(G,k)}^*+\mu _k(C_{k+1}^*-G_{k+1}^*)\in \alpha \partial \Vert G_{(k+1)}^*\Vert _1$. Combing Lemma 1 and the fact that dual norm of $\Vert \cdot \Vert _1$ is $\Vert \cdot \Vert _\infty$, we have that $\Vert Y_{(G,k+1)}^*\Vert _\infty \le \alpha$. Hence, the sequence $\{Y_{(G,k+1)}^*\}$ is bounded. The other sequences $\{Y_{(H,k)}^*\}$, $\{Y_{(E,k)}^*\}$, $\{Y_{(\cdot ,k)}\}$ and $\{\tilde{Y}_{(\cdot ,k)}\}$ can be proved to be bounded in the same way. $\square$

Proof of Theorem 1

First, we proof that the variables sequences $\{E_k,C_k,G_k,H_k\}$ have the limit $\{\hat{E},\hat{C},\hat{G},\hat{H}\}$. Note that $\tilde{Y}_{(E,k)}=Y_{(E,k-1)}+\mu _{k-1}(X-DC_k-E_{k-1})$ and $Y_{(E,k)}=Y_{(E,k-1)}+\mu _{k-1}(X-DC_k-E_k)$ (defined in Alg.1),we have that $\Vert E_k-E_{k-1}\Vert =\mu _{k-1}^{-1}\Vert \tilde{Y}_{(E,k)}-Y_{(E,k)}\Vert$. Due to the boundedness of $\{\tilde{Y}_{(E,k)}\}$ and $\{Y_{(E,k)}\}$, we get that $\Vert E_k-E_{k-1}\Vert =O(\mu _{k-1}^{-1})$. Based on the assumption $\sum _{k=1}^{+\infty }\mu _k^{-2}\mu _{k+1}<+\infty ,\mu _{k+1}>\mu _k$ (i.e. $\sum _{k=1}^{+\infty }\mu _k^{-1}<+\infty )$, the sequence $\{E_k\}$ is a Cauchy sequence, hence it has a limit $\hat{E}$. By $Y_{(E,k+1)}=Y_{(E,k)}+\mu _k(X-DC_{k+1}-E_{k+1})$ and the boundedness of $\{Y_{(E,k)}\}$, we have that $\lim \limits _{k\rightarrow \infty }(X-DC_k-E_k)=\mu _k^{-1}(Y_{(E,k+1)}-Y_{(E,k)})=0$. We conclude that $\{C_k\}$ also has the limit $\hat{C}$. So does with $\hat{G}$ and $\hat{H}$ cause that $\lim \limits _{k\rightarrow \infty }(C_k-G_k)=0$ and $\lim \limits _{k\rightarrow \infty }(C_k-H_k)=0$. $\square$

Now, we proof that $\{\hat{E},\hat{C},\hat{G},\hat{H}\}$ converge to the optimal solution $\{G^*,H^*,C^*,E^*\}$ . We denote the optimal value of Fun.7 by $P^*$. According to the equivalent constraint, we get that $C^*=G^*=H^*$, $X=DC^*+E^*$, $C^*\ge 0$, $\varphi (C^*)=0$,and $\varphi (C_{k+1})=0$. We observe that $\hat{Y}_{(G,k+1)}\in \alpha \partial \Vert G_{k+1}\Vert _1$, $\hat{Y}_{(H,k+1)}\in \beta \partial (H_{k+1}LH_{k+1}^\mathrm {T})$ and $\hat{Y}_{(E,k+1)}\in \alpha \partial \Vert E_{k+1}\Vert _1$. By the convexity of norms we have that

$$\begin{aligned}&\Vert E_{k+1}\Vert _1+\alpha \Vert G_{k+1}\Vert _1+\beta \mathrm {tr}(H_{k+1}LH_{k+1}^\mathrm {T})+\varphi (C_{k+1})\nonumber \\&\le \Vert E^*\Vert _1+\alpha \Vert G^*\Vert _1+\beta \mathrm {tr}(H^*LH^{*\mathrm {T}})+\varphi (C^*) -\langle \tilde{Y}_{(G,k+1)},G^*-G_{k+1}\rangle \nonumber \\&\quad - \langle \tilde{Y}_{(H,k+1)},H^*-H_{k+1}\rangle -\langle \tilde{Y}_{(E,k+1)},E^*-E_{k+1}\rangle \nonumber \\&= P^*-\langle \mu _k(C_k-G_k),G^*-G_{k+1}\rangle - \langle \mu _k(C_{k+1}-G_{k+1}), G^*-G_{k+1}\rangle \nonumber \\&-\langle \mu _k(C_k-H_k),H^*-H_{k+1}\rangle \nonumber \\&\quad + \langle \mu _k(C_{k+1}-H_{k+1}),H^*-H_{k+1}\rangle - \langle \mu _k(E_{k+1}-E_k), E^*-E_{k+1}\rangle \nonumber \\&- (\langle Y_{(G,k+1)}, G^*-G_{k+1}\rangle \nonumber \\&\quad + \langle Y_{(H,k+1)}, H^*-H_{k+1}\rangle + \langle Y_{(E,k+1)}, E^*-E_{k+1}\rangle ). \end{aligned}$$

(17)

The last three term of Eqn.17 can be reformulated as follows:

$$\begin{aligned}&\langle Y_{(G,k+1)}, G^*-G_{k+1}\rangle + \langle Y_{(H,k+1)}, H^*-H_{k+1}\rangle + \langle Y_{(E,k+1)}, E^*-E_{k+1}\rangle \nonumber \\&=\langle Y_{(G,k+1)}, C^*-G_{k+1}\rangle + \langle Y_{(H,k+1)}, C^*-H_{k+1}\rangle + \langle Y_{(E,k+1)},\nonumber \\&DC^*-X^*-E_{k+1}\rangle \nonumber \\&=\langle Y_{(G,k+1)}, \mu _k^{-1}(Y_{(G,k+1)}-Y_{(G,k)})\rangle + \langle Y_{(H,k+1)},\mu _k^{-1}(Y_{(H,k+1)}-Y_{(H,k)})\rangle \nonumber \\&\quad + \langle Y_{(E,k+1)}, \mu _k^{-1}(Y_{(E,k+1)}-Y_{(E,k)})\rangle + \langle C_{k+1}-C^*,DY_{(E,k+1)}\nonumber \\&-Y_{(G,k+1)}-Y_{(H,k+1)}\rangle \nonumber \\&=\langle Y_{(G,k+1)}, \mu _k^{-1}(Y_{(G,k+1)}-Y_{(G,k)})\rangle + \langle Y_{(H,k+1)}, \mu _k^{-1}(Y_{(H,k+1)}-Y_{(H,k)})\rangle \nonumber \\&\quad + \langle Y_{(E,k+1)}, \mu _k^{-1}(Y_{(E,k+1)}-Y_{(E,k)})\rangle + \langle C_{k+1}-C^*,\mu _{k+1}[\mu _{k+1}^{-1}D^\mathrm {T}(Y_{(E,k+1)}\nonumber \\&\quad -Y_{(E,k+2)})\nonumber \\&\quad + D^\mathrm {T}(E_{k+1}-E_{k+2})+C_{k+2}-G_{k+2}+C_{k+2}-H_{k+2}] \rangle \end{aligned}$$

(18)

Combing Eqs.17 and 18, we get that

$$\begin{aligned}&\Vert E_{k+1}\Vert _1+\alpha \Vert G_{k+1}\Vert _1+\beta \mathrm {tr}(H_{k+1}LH_{k+1}^\mathrm {T})+\varphi (C_{k+1})\nonumber \\&\le \mathcal {L}^* -\langle \mu _k(C_k-G_k),G^*-G_{k+1}\rangle - \langle \mu _k(C_{k+1}-G_{k+1}), G^*-G_{k+1}\rangle \nonumber \\&\quad -\langle \mu _k(C_k-H_k),H^*-H_{k+1}\rangle + \langle \mu _k(C_{k+1}-H_{k+1}),H^*-H_{k+1}\rangle \nonumber \\&\quad - \langle \mu _k(E_{k+1}-E_k), E^*-E_{k+1}\rangle - (\langle Y_{(G,k+1)}, G^*-G_{k+1}\rangle \nonumber \\&\quad + \langle Y_{(G,k+1)}, \mu _k^{-1}(Y_{(G,k+1)}-Y_{(G,k)})\rangle + \langle Y_{(H,k+1)}, \mu _k^{-1}(Y_{(H,k+1)}-Y_{(H,k)})\rangle \nonumber \\&\quad + \langle Y_{(E,k+1)}, \mu _k^{-1}(Y_{(E,k+1)}-Y_{(E,k)})\rangle \nonumber \\&\quad + \langle C_{k+1}-C^*,\mu _{k+1}[\mu _{k+1}^{-1}D^\mathrm {T}(Y_{(E,k+1)}-Y_{(E,k+2)})\nonumber \\&\quad + D^\mathrm {T}(E_{k+1}-E_{k+2})+C_{k+2}-G_{k+2}+C_{k+2}-H_{k+2}] \rangle \end{aligned}$$

(19)

By the assumption $\lim _{k\rightarrow +\infty }\mu _k(C_{k+1}-H_{k+1})=0$, $\lim _{k\rightarrow +\infty }\mu _k(C_{k+1}-G_{k+1})=0$ and $\lim _{k\rightarrow +\infty }\mu _k(E_{k+1}-E_k)=0$, we get that $\lim _{k\rightarrow +\infty }\mu _k(C_k-G_k)=0$ . When $k\rightarrow +\infty$ , the terms except the first one all approaches to zeros due to the boundedness of $\{Y_{(\cdot ,k)}\}$ and $\{E^*,C^*,G^*,H^*,\hat{E},\hat{C},\hat{G},\hat{H}\}$. Consequently, $\lim _{k\rightarrow +\infty }\Vert E_{k+1}\Vert _1+\alpha \Vert G_{k+1}\Vert _1+\beta \mathrm {tr}(H_{k+1}LH_{k+1}^\mathrm {T})+\varphi (C_{k+1})\le P^*$. Hence, $\{\hat{E},\hat{C},\hat{G},\hat{H}\}$ is the optimal solution of the Fun.7.

Appendix 3: Inference details for Eqs. 13 and 15

We reformulate the form of $\mathcal {L}(E_{k+1})$ in element-wise:

$$\begin{aligned} \mathcal {L}\left( e_{ij}^{k+1}\right)&=\left\| e_{ij}^{k+1}\right\| +y_{ij}^k\left( r_{ij}^{k+1}-e_{ij}^{k+1}\right) +\frac{\mu _k}{2}\left( r_{ij}^{k+1}-e_{ij}^{k+1}\right) ^2\\&=\left\| e_{ij}^{k+1}\right\| +\frac{\mu _k}{2}\left( r_{ij}^{k+1}-e_{ij}^{k+1}+\frac{y_{ij}^k}{\mu _k}\right) ^2-\frac{\left( y_{ij}^k\right) ^2}{2\mu _k}.\\ \end{aligned}$$

• 1. If $|r_{ij}^{k+1}+\frac{y_{ij}^k}{\mu _k}|<\lambda$ , then $e_{ij}^{k+1}=0$ , we have that

  $$\begin{aligned} \mathcal {L}(e_{ij}^{k+1})=\frac{\mu _k}{2}(r_{ij}^{k+1}+\frac{y_{ij}^k}{\mu _k})^2-\frac{(y_{ij}^k)^2}{2\mu _k}. \end{aligned}$$

• 2. If $|r_{ij}^{k+1}+\frac{y_{ij}^k}{\mu _k}|\ge \lambda$ , then $e_{ij}^{k+1}=sgn(r_{ij}^{k+1}+\frac{y_{ij}^k}{\mu _k})(|r_{ij}^{k+1}+\frac{y_{ij}^k}{\mu _k}|-\frac{1}{\mu _k})$, we have that

  $$\begin{aligned} \mathcal {L}\left( e_{ij}^{k+1}\right)&=||r_{ij}^{k+1}+\frac{y_{ij}^k}{\mu _k}|-\frac{1}{\mu _k}| +\frac{\mu _k}{2}\left( \frac{1}{\mu _k}sgn(r_{ij}^{k+1}+\frac{y_{ij}^k}{\mu _k})\right) -\frac{(y_{ij}^k)^2}{2\mu _k}\\&=\left| r_{ij}^{k+1}+\frac{y_{ij}^k}{\mu _k}\right| -\frac{1}{\mu _k}+\frac{1}{2\mu _k}-\frac{(y_{ij}^k)^2}{2\mu _k}\\&=\mu _k\left( \frac{1}{\mu _k}\left| r_{ij}^{k+1}+\frac{y_{ij}^k}{\mu _k}\right| -\frac{1}{2\mu _k^2}\right) -\frac{\left( y_{ij}^k\right) ^2}{2\mu _k}.\\ \end{aligned}$$

As for Eq. 15, combining that $y_{ij}^k=y_{ij}^{k-1}+\mu _{k-1}\left( r_{ij}^k-e_{ij}^k\right)$, we obtain

$$\begin{aligned} \mu _k^{-1}y_{ij}^k&=\mu _k^{-1}\left( y_{ij}^{k-1}+\mu _{k-1}\left( r_{ij}^k-e_{ij}^k\right) \right) \\&=\mu _k^{-1}\left( y_{ij}^0+\mu _0\left( r_{ij}^1-e_{ij}^1\right) +\ldots +\mu _{k-2}\left( r_{ij}^{k-1}-e_{ij}^{k-1}\right) +\mu _{k-1}\left( r_{ij}^k-e_{ij}^{k-1}\right) \right) \\&=y_{ij}^0+\rho ^{-k}\left( r_{ij}^1-e_{ij}^1\right) +\ldots +\rho ^{-2}\left( r_{ij}^{k-1}-e_{ij}^{k-1}\right) +\rho ^{-1}\left( r_{ij}^k-e_{ij}^k\right) \\&=\sum _{l=0}^{l=k-1}\rho ^{l-k}\left( r{ij}^{l+1}-e_{ij}^{l+1}\right) .\\ \end{aligned}$$