{'fraction_non_alphanumeric': 0.0606888443184176, 'fraction_numerical': 0.020471678539318073, 'mean_word_length': 3.909013749787812, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
High Speed Kernelized Correlation Filters without Boundary Effect

Recently, correlation filter based trackers (CF trackers) have attracted much attention in vision community because of their top performance in both location and speed. However, the boundary effect imposed by the periodic assumption for the efficient optimization seriously limits their location accuracy. Although there existed many modern works to relax the boundary effect of CF trackers, they all are not able to eliminate the boundary effect thoroughly as well as exploit the kernel trick to improve their location accuracy, and their speeds are reduced greatly. Either relaxing the boundary effect or being able to exploit kernel trick to improve the accuracy, and either relaxing the boundary effect or keeping CF trackers running at high speed have been two dilemmas in the society of visual tracking. To solve these problems, in this paper, we propose a high speed kernel correlation filter without the boundary effect (nBEKCF). Unlike all current CF trackers which exploited real and virtual image patches to train their regression functions, we construct a set of non-orthogonal bases with a group of circulant basic samples and utilize a function defined in Hilbert space and a set of densely sampled, totally real patches to regress a Gaussian goal. This way, the boundary effect is eliminated thoroughly in theory and the kernel trick can be employed naturally. To ensure nBEKCF runs at high speed, we present two efficient algorithms, ACSII and CCIM, to significantly accelerate the evaluation of kernel matrix without employing FFT. By exploiting the circulant structure of basic samples, the efficiency of CCIM in evaluating correlation exceeds that of FFT remarkably. Preliminary experimental results on two public datasets, OTB2013 and OTB2015, show that, without bells and whistles, nBEKCF outperforms representative trackers with hand-crafted features, in the meanwhile, runs at 70 fps on average.


Introduction
Visual object tracking is one of the fundamental problems in computer vision with many applications. In the model-free tracking task, given the state (e.g., position and size) of a target object in the initial frame, the goal is to estimate the states of the target in the subsequent frames. It is commonly known that despite significant progress in recent decades [35,20,23,30,24,28,25,27,21,45,43,16,37,5,33], visual object tracking is still a challenging problem [41] due to some extremely challenging factors (e.g. large appearance changes, occlusions, background clutters and fast motion), very limited training samples, and the requirement for low computational cost. Therefore, it is crucial to construct a robust appearance model from very limited samples to distinguish target from distractive background, while maintain high speeds in tracking.
Since 2010, correlation filter based trackers (CF trackers) have been being proposed and almost dominated the tracking domain in recent years [3,18,13,8,19,10,12,4,6,31,11,29,26]. CF trackers learn their filters from circular samples to regress Gaussian response maps, and their learning and detection are accelerated with the convolution theorem and fast Fourier transform (FFT). Bolme et al. [3] proposed the Minimum Output Sum of Squared Error (MOSSE) for very high speed tracking on gray-scale images. They used a base image patch and the circulant virtual ones to train the appearance model directly in Fourier domain. Henriques et al. [19] proposed the kernelized correlation filter (KCF) which extended MOSSE to not only learn a multi-channel filter, but also take the advantage of kernel trick to improve its location accuracy. Compared to MOSSE, KCF achieved much higher accuracy on OTB-2013 [42] when exploiting HOG feature [7] and Gaussian kernel, in the meanwhile, it is still able to run at high speed. However, the basic periodic assumption leads to the approximation of real samples, producing the unwanted boundary effect [22] in MOSSES and KCF. This problem negatively affects the discriminativity of appearance models and greatly degrades the location accuracy of MOSSE and KCF. In order to relax the boundary effect, Galoogahi et al. [15] and Danelljan et al. [9] proposed background-aware correlation filters (BACF) and spatially regularized discriminatively correlation filters (SRDCF), respectively. In BACF, a rectangular mask covered the circular samples, and then the alternating direction method of multipliers (ADMM) was employed to solve the optimization problem with equality constraints. In SRDCF, a smooth spatial regularization factor was introduced into the regularizer to penalize the filter coefficients depending on their spatial location. Even though BACF, and SRDCF relaxed the boundary effect, they still can not eliminate the boundary effect thoroughly in theory. And as the costs of relaxing the boundary effect in their ways, SRDCF and BACF can only run at low speed if powerful features of high dimensionality are exploited, in the meanwhile, they are not able to exploit the kernel trick to improve their accuracy, because it is not clear what the window shape is in the non-linear kernel space, despite the shape is known in an image or filter.
To improve the discriminativity of KCF, Tang and Feng [34] and Tang, et al. [36] derived two multi-kernel learning (MKL) [32] based correlation filters (MKCF and MKCFup) which are able to take advantage of the invariance-discriminative power spectrums of various features [39] to improve the location accuracy. Nevertheless, MKCFup, the latest MKL version of KCF, still suffers from the boundary effect, although its location performance outperforms that of KCF.
In summary, up till now, there are at least two principal lines to improve MOSSE and KCF. The first one is to weight the filter or samples with a mask in MOSSE or the KCF of linear kernel, alleviating the boundary effect greatly and improving the location accuracy remarkably. However, the trackers on this line, such as SRDCF and BACF, are unable to employ powerful non-linear kernels to improve their performance. And all trackers on this line are not able to run at high speed if powerful features of high dimensional are exploited. The second line to improve MOSSE and KCF is to modify the objective function of KCF, such as designing more complicated objective functions [2], or introducing the MKL into KCF to adaptively exploit multiple (non-linear) kernels. Although the trackers on this line often maintained high speed in tracking, they suffer from the boundary effect. Consequently, either relaxing the boundary effect or being able to exploit kernel trick to improve the accuracy, and either relaxing the boundary effect or keeping CF trackers running at high speed have been two dilemmas in the visual tracking community.
To solve these two dilemmas, in this paper, we propose a high speed kernel correlation filter without the boundary effect (nBEKCF). Unlike all current CF trackers which exploited several real and virtual patches generated from a single image patch to train their regression functions, we construct a set of non-orthogonal bases with a group of circulant basic samples and utilize a function defined in Hilbert space and a set of densely sampled, totally real patches to regress a Gaussian response map. This way, the boundary effect is eliminated thoroughly in theory and the kernel trick can be exploited naturally. In order to treat multiple images and model update problems, we introduce the modeling scheme over multiple images [13] into our nBEKCF. To ensure nBEKCF runs at high speed, inspired by the integral image [40], we present two efficient algorithms, ACSII and CCIM, to significantly accelerate the evaluation of kernel correlation matrices without employing FFT. And by exploiting the circulant structure of basic samples, the efficiency of CCIM in evaluating correlation exceed that of FFT remarkably in our task.
In summary, our main contributions are as follows.
• We propose a conceptually simple, flexible and novelty correlation filter entitled nBEKCF which eliminates the boundary effect thoroughly in theory as well as is able to exploit kernel trick naturally.
• We present two efficient algorithms, ACSII and CCIM, which fully exploit the circulant structure of basic samples to construct kernel correlation matrices without employing FFT, exceeding the efficiency of FFT in our task.
• We test our novel CF tracker, nBEKCF, on two public datasets, OTB-2013 and OTB-2015. Preliminary experimental results show that, without bells and whistles, our nBEKCF outperforms representative trackers with hand-crafted features, in the meanwhile, runs at 70 fps on averrage.
We will update our latest experimental results on arxiv.org as soon as they are ready, and release the code to facilitate the future research in visual community.

Kernelized Correlation Filters without Boundary Effect (nBEKCF)
Let H be a Hilter space of functions f : R m×n×D → R. Suppose κ : R m×n×D × R m×n×D → R can be represented as dot product in H, X 0,0 ∈ R m×n×D is an m × n × D sample with x 0,0 i,j ∈ R D , i = 0, . . . , m − 1 and j = 0, . . . , n − 1, as its element, X 0,0 d is the d th channel of X 0,0 . And the circulant samples are generated via where P m and Q n are the permutation matrices of m × m and n × n, respectively [14], P ρ m and Q ρ n are the ρ th power of P m and Q n , respectively, The elements of Z, which is not circulant in general, come from the dense sampling of an image patch. Consider {κ(X i ,j , ·)} as a set of basis functions, and let (2) f (Z) is called the kernelized correlation filter without boundary effect (nBEKCF). We then construct the following ridge regression problem.
To solve for α, let ∇ α F (α) = 0; it is achieved that K K + λI α = K y. Because K K is semi-positive definite, K K + λI is invertible if λ > 0. Consequently, if λ > 0, the optimal solution of Problem (3) is It is noted that if Z is circulant and X = Z, K will be a Gram matrix, and the loss of Problem (3) is exactly the same the loss in normal kernelized correlation filters (KCF) [18].

Extend to Multiple Images
In visual tracking, the appearance model is often trained with multiple images from different times to improve its robustness. For example, Hare,et al. [17] and Danelljan,et al. [13] trained appearance models with historical samples. In this section, we will introduce the scheme proposed in [13] into nBEKCF for modelling with multiple images.
Specifically, in nBEKCF, the ridge regression problem of multiple images can be modelled as where K q is the kernel correlation matrix of Z q and X , q = 1, . . . , Q, Z q comes from frame q.
While the images come sequentially, an efficient update scheme similar to what was done in [13] can be designed as follows. Let Then K (S)

Detection of Target Object
Suppose Z is the test set. |Z | = M N . According to Eq. (2), nBEKCF evaluates the response of Then, the response map,

Fast Evaluation of Correlation Matrix
While solving for the optimal α * and detecting the target object, correlation matrices K Q and K , each includes M N × mn different elements, have to be evaluated first. And the evaluation of each element of K Q and K is involved in samples of D channels. In some time-sensitive tasks, such as visual object tracking, M N , mn, and D are huge, e.g., M N = 60 × 60, mn = 15 × 20, and D = 41. If there is no efficient algorithm to evaluate K Q and K , it is almost impossible to apply nBEKCF in such tasks. On the other hand, it ought to be noticed that, while solving for α * , the computational cost of matrix inversion is usually not a main bottleneck for efficient solution if the inversion is achieved through solving a system of linear equations, because the mn × mn coefficient matrices are usually not large. For example, the coefficient matrices are only 300 × 300 in the above example.
Some kernels, such as dot-product kernels, polynomial kernels, and radial basis function kernels [19] are often employed to evaluate the elements of K Q and K . And the evaluation of these usually used kernels are involved in the correlation and/or autocorrelation of samples. In general, the computational complexity of X Z, where is the correlation operator, is O(m 2 n 2 M N D), and that of the autocorrelation Z Z is O(mnM 2 N 2 D). Despite fast Fourier transform (FFT) can accelerate the correlation with the computational complexity O(mnM N (log M + log N )D), it is still not satisfactory for some time-sensitive tasks because it is not able to exploit the cyclicity of X . And FFT is not able to accelerate the autocorrelation in our visual object tracking task. Consequently, the computational burdens of correlation and autocorrelation are still main bottlenecks for some time-sensitive tasks, such as visual object tracking.
The key to acceleration of correlation and autocorrelation is to fully exploit the structure of samples, i.e., X is circulant and Z is densely sampled from an image patch. In this section, we will develop two algorithms, autocorrelation with squared integral image (ACSII) and circulant correlation with integral matrix (CCIM), to efficiently evaluate Z Z and X Z. The computational complexities of ACSII and CCIM are O(M N D) and O(mnM N D), respectively, lower than those with FFT.
In order to experimentally verify the superior efficiency of CCIM over that of FFT, we evaluate X Z under a typical situation in visual object tracking, i.e., m = 15, n = 20, M = N = 60, and D = 31 + 10 = 41, which are the case if CN [38] and HOG with cell sizes being 4 × 4 are employed. It is not surprised to see that CCIM takes only 30ms, while FFT 530ms, to achieve X Z. We also evaluate Z Z in the above example with ACSII. Z Z is then achieved in 3ms.

Autocorrelation with Squared Integral Image (ACSII)
While Z is sampled from a single image patch Z ∈ R M ×N ×D , the necessary computation for Z Z is the squares, z i ,j 2 , where z i ,j ∈ R D is the element of Z, i = 0, . . . , M − 1, and j = 0, . . . , N − 1. We then design an integral image I to evaluate after obtaining all the squares, where Z i ,j ∈ Z with top left corner coordinates (i , j ). The detailed steps are shown in Algorithm 1.

Circulant Correlation with Integral Matrix (CCIM)
where <, > is the dot product. Because X is circulant, the cost of whole computation, i.e., X i ,j Z's for all X i ,j ∈ X , can be reduced significantly. Before formally presenting our efficient algorithm, Circulant Correlation with Integral Matrix (CCIM), we first explain its basic logic steps as follows.
(L1) Only the necessary computation is conducted. Because X is circulant, the necessary computations for the whole

Algorithm 1 Autocorrelation with Square Integral Image (ACSII)
-Input: Z ∈ R M ×N ×D with Z i,j,d 's as its elements, m, and n, where m ≤ M and n ≤ N . D is the number of channels. (L2) Correlation filter X i ,j is divided into four sub-filters (sub-matrices), i.e., L i ,j , G i ,j , K i ,j , and J i ,j , by the position of x 0,0 0,0 . This is shown in Fig.1. In each sub-matrices, the relative spatial positions of different elements are the same as their relative positions in X 0,0 . And the relative spatial positions of two elements belonging to different sub-matrices are different from their original relative positions in X 0,0 . This way, X i ,j Z is decomposed into four parts, i.e., An example to illustrate how CCIM works is provided in supplementary material. The formal description of CCIM is presented in Algorithm 2. The mathematical proof of its correctness is also included in supplementary material. To improve the efficiency of CCIM further, any P i M SQ j N is conducted with periodic extension and retrieval, rather than with matrix multiplication.

Implementation Details
In our experiments, the color names (CN) and HOG are employed as features in nBEKCF. Both cell sizes of CN and HOG are 4 × 4. The numbers of CN and HOG channels are 10 and 31, respectively.

Algorithm 2 Circulant Correlation with Integral Matrix (CCIM)
-Input: X 0,0 ∈ R m×n×D with X 0,0 i,j,d 's as its elements, Z ∈ R M ×N ×D with Z d ∈ R M ×N as its d th channel matrix. m ≤ M and n ≤ N , D is the number of channels.
) is the sub-matrix of matrix H with (a 1 , b 1 ) and (a 2 , b 2 ) as its top left and down right corner subscripts.
The response map y is identical to that in KCF [18]. The learning rate γ = 0.01. While we construct the kernel correlation matrices, Gaussian kernel is employed with σ = 4. m and n are the height and width of the target object. The size of search region is set M = N = 3 √ mn. The initial target object of mn < 1000 is considered small object, and will be resized to 1000, keeping the aspect ratio unchanged in whole sequence. The scale of target object is estimated with fDSST [11].

Experimental Results
The nBEKCF was implemented in MATLAB and C++. The experiments were performed on a PC with Intel Core i7 3.60GHz CPU and 8GB RAM. The speed of nBEKCF is 70 fps on average. The experimental results reported in this section is preliminary.
All trackers are quantitatively evaluated by six criteria, (i) Center Error, which is calculated as the average Euclidean distance between the centers of located objects and their ground truths in a sequence; (ii) Distance Precision, which is the percentage of frames where the objects are located within the center errors of 0 to t c pixels, with t c = 20; (iii) Precision Plot, which is simply a curve of the distance precisions with t c changing from 0 to 50 pixels; (iv) Overlap Ratio, which is defined as the average ratio of intersection and union of the estimated bounding box and ground truth in a sequence; (v) Overlap Precision, which is the percentage of frames with the overlap ratio exceeding t o in a sequence, with t o = 0.5; (vi) Success Plot, which is simply a curve of overlap precisions with the overlap ratio changing from 0 to 1, and AUC is the area under the success plot.    We compare nBEKCF with SRDCF and several other state-of-the-art trackers on OTB-2013 [42] and OTB-2015 [41]. SRDCF is selected because it is one of the representative trackers which only try to alleviate the boundary effect to improve its location accuracy. Fig. 2 shows the results. It is seen from the figure that nBEKCF outperforms SRDCF on the average precision score and AUC by 1.8% and 1.9% on OTB-2013, respectively, and 3.7% and 1.8% on OTB-2015, respectively.

Conclusions
A novel high speed kernelized correlation filter without boundary effect (nBEKCF) is presented in this paper. Without boundary effect, being able to exploit kernel trick, and running at high speed, for the first time in the history of correlation filters, nBEKCF possesses all these characteristics that were hard to manage simultaneously. , respectively, where the numbers in X 0,0 indicate the elements of X 0,0 , rather than the elements' real feature values. X 0,0 and Z are called base correlation filters and signal, respectively. Let 5 × 5 minimal evaluation matrices A i,j = X 0,0 i,j · Z, and 5 × 5 fundamental matrices B i,j = P −i 5 A i,j Q −j 5 , where P 5 and Q 5 are defined by Eq.(2) with M = N = 5, i = 0, 1, 2, and j = 0, 1, 2. A i,j 's and B i,j 's are shown in Fig.1 1 . 2.1 Correlation of X 0,0 and Z It is clear that X 0,0 Z(0, 0) =< (1,2,3,4,5,6,7,8,9), (a, b, c, f, g, h, k, l, m) >. According to the construction of A i,j 's and B i,j 's, X 0,0 i,j · Z i,j = B i,j 0,0 , i = 0, 1, 2 and j = 0, 1, 2. X 0,0 i,j · Z i,j 's are marked by the blue blocks in Fig.1(b). Therefore,

Correlation of X 1,1 and Z
In general, as shown in Fig.2(c), any circulant correlation filter X i ,j generated with Eq.(1) can always be divided into four parts, L i ,j , G i ,j , K i ,j , and J i ,j by the position of X 0,0 0,0 . Note that L i ,j and G i ,j or L i ,j and K i ,j will not exist if i = 0 or j = 0. Further, X i ,j Z can be achieved through evaluating four sub-correlations, d i ,j L , d i ,j G , d i ,j K , and d i ,j J , as expressed in Eq.(3). In the following, we will explain how CCIM works with X 1,1 Z.

Design Integral Matrix to Accelerate Correlation
According to the beginning of this section, X 0,0 i,j is the common factor of all elements of B i,j . Replacing X 0,0 i,j by B i,j in X 0,0 , we achieve Based on the examples given in Secs.2.1 and 2.2, it is necessary to evaluate 2 i=0 2 j=0 B i,j to achieves X 0,0 Z, and to evaluate B 2,2 , B 2,0 + B 2,1 , B 0,2 + B 1,2 , and B 0,0 + B 0,1 + B 1,0 + B 1,1 to obtain X 1,1 Z. In order to eliminate unnecessary additions, the three summations of matrices, which are necessary for evaluating X 1,1 Z, should be reused to evaluate X 0,0 Z. Notice that each above summation of B i,j 's is involved with the summation of the elements of T's sub-matrices. Constructing the integral matrix M I with CCIM, we have It is seen that the five summations of B i,j 's are achieved within constant duration by means of M I . This way, the unnecessary additions of B i,j 's are eliminated.
In general, because W i ,j is a sub-matrix of X 0,0 , where W = L, G, K, J, the B i,j 's with the elements of W as their common factors also constitute a T's sub-matrix. While evaluating d i ,j W , where W ∈ {L, G, K, J}, similar to the examples in Secs.2.1 and 2.2, it is necessary to evaluate the summation of all elements of the T's sub-matrix. For a given X 0,0 , while (i , j ) traverses all possible pairs, i.e., X i ,j traverses all possible circulant correlation filters, the brute force evaluation of the summations will arise a great deal of unnecessary computation, decreasing the efficiency of correlations greatly especially when the size of base correlation filter is large. Therefore, it is a natural choice to constructe the integral matrix, as described in CCIM, to calculate such summations without unnecessary additions.

Correctness of Algorithm 2 (CCIM)
Suppose X 0,0 ∈ R m×n×D is the m × n × D base correlation filter with X 0,0 i,j,d as its elements, (i, j) is the spatial coordinate, d is the channel, circulant correlation filters where P l1 , l 1 ∈ {m, M }, and Q l2 , l 2 ∈ {n, N }, are the permutation matrices of l 1 × l 1 and l 2 × l 2 , respectively [3], P ρ l1 and Q ρ l2 are the ρ th power of P l1 and Q l2 , respectively, 0 l−1 is (l − 1) × 1 vector of all zeros, I l−1 is (l − 1) × (l − 1) identity matrix, l ∈ {l 1 , l 2 }. Note that the matrix operation works only on the spatial coordinate in Eq.(1). Z ∈ R M ×N ×D is the M × N × D signal matrix with Z i ,j ,d as its elements. Z d ∈ R M ×N is its d th channel matrix.
Note that B i,j 's are generated through cyclic-shifts of A i,j . Then, X 0,0 i,j only appears in A i,j and B i,j as a common factor of their elements. The sets of whole A i,j 's and B i,j 's are denoted as A and B, respectively.
In this appendix, we will prove that CCIM will produce X i ,j Z correctly. To simplify the mathematical expression, we only present our proof in the case of D = 1. It is straightforward to extend the proof to the general case of D > 1.
In general, as shown in Fig.2(c), given i and j , X i ,j can always be divided into four parts, L i ,j , G i ,j , K i ,j , and J i ,j by the position of X 0,0 , respectively, and their top left elements are L i ,j 0,0 = X 0,0 m−i ,n−j , G i ,j 0,0 = X 0,0 m−i ,0 , K i ,j 0,0 = X 0,0 0,n−j , and J i ,j 0,0 = X 0,0 0,0 , respectively. Note that L i ,j and G i ,j or L i ,j and K i ,j will not exist if i = 0 or j = 0. where

Evaluation of
While evaluating d i ,j L (i , j ), L i ,j 0,0 and Z i ,j multiply. According to the construction of A and B, we have We also have 0,0 · Z i ,j and L i ,j p,q · Z i +p,j +q possess the same subscripts, although they belong to different fundamental matrices.
It is seen from Fig.2(c) that the top left and bottom right elements of L i ,j are According to the construction of integral matrix, S L,i ,j can be evaluated within constant time as

Evaluation of
While evaluating d i ,j G (i , j ), G i ,j 0,0 and Z i ,j +j multiply. According to the construction of A and B, we have On the other hand, G i ,j p,q = X 0,0 m−i +p,q , where p = 0, . . . , i − 1 and q = 0, . . . , n − j − 1. It only appears in B m−i +p,q , and G i ,j p,q · Z i +p,j +j +q = A m−i +p,q i +p,j +j +q . We also have therefore G i ,j p,q · Z i +p,j +j +q = B m−i +p,q (i −(m−i ))modM,j +j . That is, G i ,j 0,0 · Z i ,j +j and L i ,j p,q · Z i +p,j +j +q possess the same subscripts, although they belong to different fundamental matrices.
It is seen from Fig.2(c) that the top left and bottom right elements of G i ,j are According to the construction of integral matrix, S G,i ,j can be evaluated within constant time as Then, we have While evaluating d i ,j K (i , j ), K i ,j 0,0 and Z i +i ,j multiply. According to the construction of A and B, we have On the other hand, K i ,j p,q = X 0,0 p,n−j +q , where p = 0, . . . , m − i − 1 and q = 0, . . . , j − 1. It only appears in B p,n−j +q , and K i ,j p,q · Z i +i +p,j +q = A p,n−j +q i +i +p,j +q . We also have i +i ,j = A p,n−j +q i +i +p,j +q . That is, K i ,j p,q · Z i +i +p,j +q = A (K) i +i ,j . Because therefore K i ,j p,q · Z i +i +p,j +q = B p,n−j +q i +i ,(j −(n−j ))modN . That is, K i ,j 0,0 · Z i +i ,j and K i ,j p,q · Z i +i +p,j +q possess the same subscripts, although they belong to different fundamental matrices.
It is seen from Fig.2(c) that the top left and bottom right elements of K i ,j are According to the construction of integral matrix, S K,i ,j can be evaluated within constant time as Then ,we have

Evaluation of
While evaluating d i ,j J (i , j ), J i ,j 0,0 and Z i +i ,j +j multiply. According to the construction of A and B, we have J i ,j 0,0 · Z i +i ,j +j = A 0,0 i +i ,j +j . And B 0,0 = A 0,0 . Therefore, J i ,j 0,0 · Z i +i ,j +j = B 0,0 i +i ,j +j .
On the other hand, J i ,j p,q = X 0,0 p,q , where p = 0, . . . , m − i − 1 and q = 0, . . . , n − j − 1. It only appears in B p,q , and J i ,j p,q · Z i +i +p,j +j +q = A p,q i +i +p,j +j +q . We also have B p,q = P −p M A p,q Q −q N . Then, B p,q i +i ,j +j = A p,q i +i +p,j +j +q . Therefore J i ,j p,q · Z i +i +p,j +j +q = B p,q i +i ,j +j .
That is, J i ,j 0,0 · Z i +i ,j +j and J i ,j p,q · Z i +i +p,j +j +q possess the same subscripts, although they belong to different fundamental matrices.
It is seen from Fig.2(c) that the top left and bottom right elements of J i ,j are According to the construction of integral matrix, S J,i ,j can be evaluated within constant time as In this case, ∆ (L) According to this proof, we also have P Consequently, all increments in Eq.(4) are not related to (i , j ), and are constant, given (i , j ). All (N − 2n + j )modN )), and those S J,i ,j ((i , j ), (M − m + i , N − n + j )) are shifted with the same numbers of rows and columns, respectively. Noticed that d i ,j L (0, 0), d i ,j G (0, 0), d i ,j K (0, 0), and d i ,j J (0, 0) are shifted to S i ,j L;0,0 , S i ,j G;0,0 , S i ,j K;0,0 , and S i ,j J;0,0 , respectively, therefore, Q.E.D.

Other Experimental Results
We evaluate nBEKCF on VOT2016 dataset [8] which contains 60 sequences with substantial variations and challenges. We follow the VOT challenge protocol to compare trackers, where a tracker is reinitialized whenever its failure is observed. The evaluation criteria on VOT2016 are different from those on OTB-2013 and OTB-2015. On VOT2016, the accuracy and robustness of each tracker are evaluated in terms of the overlap ratios between bounding boxes and ground-truths and the number of re-initializations. In addition, VOT2016 mainly reports the expected average overlap (EAO) which integrates the accuracy and robustness of a tracker, and ranks trackers according to it, since the EAO score may provide an insight to the comprehensive performance of a tracker.
We compare our method against other top 9 trackers, SRDCF [2], DSST [1], NSAMF [8], deepMKCF [8], SAMF [7], KCF [6], ColorKCF [8], TGPR [4], and Struck [5], of VOT2016 challenge. Figs.3 shows the EAO ranking and accuracy-robustness plots, where the closer to the top-right corner of the plots a tracker is, the better the performance of the tracker is considered. It is seen that nBEKCF is ranked the second best in EAO. Although the EAO of nBEKCF is slightly less than that of SRDCF, it runs much faster than SRDCF (70fps vs. 7fps), and its memory requirement is much smaller than SRDCF's (130MB vs. 600MB), as shown in Table.1.
We also compare our nBEKCF and the above 9 trackers with the criteria used on OTB50 and OTB100. The results are shown in Fig.4. It is seen from the figure that nBEKCF outperforms the second best SRDCF on the average precision score and AUC by 2.0% and 2.1%, respectively. Table 2 shows the means of overlap precisions of all compared trackers, where our nBEKCF is also the best.   , DSST [1], NSAMF [8], deepMKCF [8], SAMF [7], KCF [6], ColorKCF [8], TGPR [4], and Struck [5].