KCF target tracking algorithm

Recently just started to learn single target tracking, recently tried to understand the idea of KCF, read a week of formula derivation, to see the tears ！！！！ I've written down some of the conclusions that I already know to rationalize my thoughts. I'm not sure if you're a good person, but I'm sure you're a good person.

First of all, let's talk about its advantages:

1. Through the matrix loop of the picture, increasing the training samples, improving the correct rate.

2. Perform Fourier transform, avoid matrix inverse operation, calculation is faster.

3. Use Gaussian label, more reasonable.

Now to sort out the whole process of its calculation:

1. Objective function:

Our goal is to minimize the distance between the computed label f(xi) of our sampled data xi and the real label yi (the regression target) of the real target position in the next frame. (This should not be difficult to understand, the more like the real label I calculated, that I find the next frame to get the position of the real position closer to it)

This representation of the form of ridge regression, the following part of the solution process, you can refer to the SVM solution process. Although it is not the same form, but to help understand the solution in this article is very useful (" Support Vector Machines Popular Introduction (Understanding the three realms of SVM) LaTex latest version_2015.1.9.pdf" this article on the meaning of the expression and the solution is written very clearly)

< p> In the linear problem:

In solving the minimum value here, f(xi) according to the formula (1) will be replaced by the matrix form Wt * X (why can be converted to this form refer to the SVM), each row of X represents a sampling result of xi, X is after the first row of xi continuously loop obtained a matrix,Wt represents the transpose of W. y represents the yi composition of the vector . Then calculate the formula (2) on the derivation of W is equal to 0 can be obtained:

(4) is the transpose of (3) will be converted into a *** yoke, as long as it is considered in the following Fourier transformations in the presence of negative numbers.

Here we see that there is a matrix inverse operation in finding the minimum value of w, which makes the computation more intensive. However, according to the previous statement X is a cyclic matrix of the form:

After the matrix is Fourier transformed, the cyclic matrix has a property:

that is, a cyclic matrix can be represented by the vector of its first row after the Fourier transform, x with a hat means that the Fourier transform of the vector x has been performed. For a more detailed understanding of the Fourier transform, see: This Fourier blog

For a description of how to do the Fourier transform, see: Fourier Transform Methods

Then you can see that a cyclic matrix can be converted to be represented by a vector. Bring the formula (6) into the formula (4) to simplify:

w wearing a hat means that the Fourier transformation is carried out, so that the operation from a matrix is exchanged for the operation of a vector. The operation of finding the inverse is reduced.

Of course in most cases we are solving nonlinear problems :

Then we introduce the concept of high dimensional solutions and kernel functions (for a careful solution refer to the SVM article mentioned above).

A nonlinear problem w can be turned into a linear problem in high dimensional space.

fai(xi) denotes the function that maps x to a higher space.

Then our objective function can be expressed as

Where k denotes the kernel function it is defined by the following operation:

From (8) it can be seen that the previous problem of minimizing w is converted into a problem of minimizing algebras. Bringing (8) to the solution of (2) alpha refer to an article " R. Rifkin, G. Yeo, and T. Poggio, "Regularized least-squares classification,Nato Science Series Sub Series III Computer and Systems Sciences, vol. 190, pp. 131-154, 2003."

Finally it can be solved

to perform the Fourier transform:

Here Kxx stands for Fourier transform of the first row of elements of the matrix K. K is also a cyclic matrix provable, omitted here The specific way can be found in the "High-Speed Tracking with Kernelized Correlation Filters Jo?o F. Henriques, Rui Caseiro, Pedro Martins, and Jorge Batista" in Section 5.2.

In this way, equation (8) can be expressed as:

Kz is the kernel matrix between all the training samples and the alternate patches

It now remains to discuss the form of k, which can be converted to the form of the Fourier transform of w that we obtained when discussing the linear problem, if k is a linear kernel. The Gaussian kernel used in this post is of the following form:

This is the pushdown of the main formulas used in it, I think.

When pushing down the place of the next frame is to calculate the sampled features and the previous training data to do Gaussian matching and then multiply with the alpha, to get a response value of the largest is the next frame of the largest possible value of the place.