# Robust Visual Tracking via Patch Descriptor and Structural Local Sparse Representation
## 3 Patch Descriptor and Structural Local Sparse Representation
### Structural Local Sparse Representation  
Given a set of target templates \(\mathbf{T}=\{T_{1},T_{2},\ldots,T_{n}\}\), we divided each template in \(\mathbf{T}\) into \(N\) non-overlapped local patches with a spatial layout (Figure 1a), and used these local patches as the dictionary to encode the local patches inside the candidate regions, i.e., \(\mathbf{D}=\left\{\mathbf{d}_{1},\mathbf{d}_{2},\ldots,\mathbf{d}_{(n\times N)}\right\}\in \mathbb{R}^{d\times(n\times N)}\), where \(n\) is the number of target templates, \(d\) is the dimension of each patch vector, and \(N\) is the number of local patches sampled within one target region. Each column in \(\mathbf{D}\) is obtained by \(\ell_{2}\) normalization on the vectorized local image patches. For a target candidate, we divided it into \(N\) patches and turned them into vectors in the same way, which is denoted by \(\mathbf{Y}=\{\mathbf{y}_{1},\mathbf{y}_{2},\ldots,\mathbf{y}_{N}\}\in\mathbb{R}^{d\times N}\). With the sparsity assumption, the local patches within the target candidate region can be sparsely represented as a linear combination of the dictionary \(\mathbf{D}\) by solving the following \(\ell_{1}\)-regularized least squares problem:  
\[\min_{\mathbf{b}_{i}}\lVert y_{i}-\mathbf{D}\mathbf{b}_{i}\rVert_{2}^{2}+\lambda\lVert \mathbf{b}_{i}\rVert_{1},\text{ s.t. }\mathbf{b}_{i}\geq 0, \tag{1}\]  
where \(\lambda\) is the regularized parameter, \(\mathbf{b}_{i}\in\mathbb{R}^{(n\times N)\times 1}\) is the sparse coefficients of the \(i^{\text{th}}\) local image patch, and \(\mathbf{b}_{i}\geq 0\) means all the elements of \(\mathbf{b}_{i}\) are nonnegative. To represent local patch \(i\) at a certain position of the candidate, the sparse coefficients of the \(i^{\text{th}}\) patch are divided into \(n\) segments, i.e., \(\mathbf{b}_{i}^{\text{T}}=[\mathbf{b}_{i}^{(1)\text{T}},\mathbf{b}_{i}^{(2)\text{T}}, \ldots,\mathbf{b}_{i}^{(n)\text{T}}]\), according to the target templates, where \(\mathbf{b}_{i}^{(k)T}=\left[b_{(k-1)\times N+1},b_{(k-1)\times N+2},\ldots,b_{(k- 1)\times N+N}\right]\) denotes the \(k^{\text{th}}\) segment of the coefficient \(\mathbf{b}_{i}\). Then, we weighed these coefficients to obtain \(\mathbf{v}_{i}\) for the \(i^{\text{th}}\) patch:  
\[\mathbf{v}_{i}=\frac{1}{C}\sum_{k=1}^{n}b_{i}^{(k)},\;i=1,2,\ldots,N \tag{2}\]  
where \(\mathbf{v}_{i}\) is the sparse coefficient of the \(i^{\text{th}}\) local patch and \(C\) is a normalization term. Since one candidate target contains \(N\) local patches, all the vectors can form a square matrix \(\mathbf{V},\mathbf{V}=[\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{N}]\). The local appearance variation of a patch can be best described by the blocks at the same positions of the template. Therefore, we used the alignment-pooling method [9] and took the diagonal elements of the square matrix \(\mathbf{V}\) as the final sparse coefficients of the local patches, i.e., \(\mathbf{f}=\text{diag}(\mathbf{V})\), where \(\mathbf{f}=\{f_{1},f_{2},\ldots,f_{N}\}\) is the sparse coefficient vector of all the local patches, i.e., \(f_{j}\) means the sparse coefficient of the \(j^{\text{th}}\) local patch.