# An Improved Kernelized Correlation Filter Algorithm for Underwater Target Tracking
## 2 Kernelized Correlation Filter Algorithm  
The KCF is based on the correlation filter framework; it converts the solution of the filter into the problem of training binary classifier. Specifically, a sample centered on the target is selected as a positive sample and a negative sample around the target is selected to train the classifier. Then, the next frame image is detected with the classifier, and the result of the detection is used as the location of target in the next frame. In the KCF, assuming that a number of training samples and their tag values are given as \(\{\left(\chi_{1},y_{1}\right),\left(\chi_{2},y_{2}\right),\ldots,\left(\chi_{ i},y_{i}\right),\ldots,\left(\chi_{n},y_{n}\right)\}\), the purpose of training is to find a function \(f\left(z\right)=w^{T}z\), which makes the label \(f\left(\chi_{i}\right)\) of sample \(\chi_{i}\) predicted by the classifier model have the minimum mean square error with its real tag \(y_{i}\). It can be expressed as:  
\[\min\sum_{i}\left(f\left(\chi_{i}\right)-y_{i}\right)^{2}+\lambda\parallel w \parallel^{2} \tag{1}\]  
where \(\chi_{i}\) represents the \(i\)th sample, \(w\) is the coefficient vector of the linear classifier, \(y_{i}\) is the label of the \(i\)th sample, and \(\lambda\) is the regularization parameter, which is used to prevent overfitting. A closed-form solution can be obtained by finding the partial derivative of \(w\) and equating the derivative result to zero. Therefore, \(w\) is defined as follows:  
\[w=\left(X^{T}X+\lambda I\right)^{-1}X^{T}y \tag{2}\]  
where the matrix \(X\) is composed of samples, \(X=\left[\chi_{1},\chi_{2},\dots\chi_{i},\dots\chi_{n}\right]\), \(y\) is the column vector formed by the label of the sample, \(y=\left[y_{1},y_{2},\dots y_{i},\dots y_{n}\right]\), and \(I\) is the identity matrix. Equation (2) to the complex domain can be expressed as:  
\[w=\left(X^{H}X+\lambda I\right)^{-1}X^{H}y \tag{3}\]  
where \(X^{H}\) is a Hermitian transpose. Then, the coefficients \(w\) of the linear regression classifier \(f\left(x\right)\) are solved and the training of the linear classifier is finished. In order to reduce the computational complexity, the KCF uses cyclic shift to construct the training sample \(X\). The cyclic shift operation is carried out on the base sample. The base sample is a rectangular image block whose center is the target and the size is a fixed multiple of the target size. Assuming that the \(n\times 1\) dimensional vector \(\chi=\left[\varepsilon_{1},\varepsilon_{2},\dots,\varepsilon_{i},\dots, \varepsilon_{n}\right]^{T}\) is used to represent the base sample, the cyclic shift operation of the base sample in one dimension is expressed as follows:  
\[\left\{P^{u}\chi|u=0,...,n-1\right\} \tag{4}\]  
where \(u\) represents the direction and time of cyclic shifts, \(P\) is a permutation matrix, and the specific form of \(P\) is expressed as:  
\[P=\left[ \begin{array}{cccc}0&0&\dots&1\\ 1&0&\dots&0\\ 0&1&\dots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&1&0\end{array} \right] \tag{5}\]  
A training sample \(X\) generated by shifting one element of the base sample \(\chi=\left[\varepsilon_{1},\varepsilon_{2},\dots\varepsilon_{i},\dots \varepsilon_{n}\right]^{T}\) is shown as:  
\[X=C\left(\chi\right)=\left[ \begin{array}{cccc}\varepsilon_{1}&\varepsilon_ {2}&\dots&\varepsilon_{n}\\ \varepsilon_{n}&\varepsilon_{1}&\dots&\varepsilon_{n-1}\\ \varepsilon_{n-1}&\varepsilon_{n}&\dots&\varepsilon_{n-2}\\ \vdots&\vdots&\ddots&\vdots\\ \varepsilon_{2}&\varepsilon_{3}&\dots&\varepsilon_{1}\end{array} \right] \tag{6}\]  
where \(C\left(\chi\right)\) represents a circular matrix generated by \(\chi\). According to the properties of the circulant matrix, \(X\) can be diagonalized by the discrete Fourier transform. It is:  
\[X=Fdiag\left(\hat{\chi}\right)F^{H} \tag{7}\]where \(F\) is a discrete Fourier transform matrix, which is a constant value.