# Target Centroid Position Estimation of Phase-Path Volume Kalman Filtering

Authors: Fengjun Hu
Journal: Journal of Sensors
 (2016)

---

## Abstract

For the problem of easily losing track target when obstacles appear in intelligent robot target tracking, this paper proposes a target tracking algorithm integrating reduced dimension optimal Kalman filtering algorithm based on phase-path volume integral with Camshift algorithm. After analyzing the defects of Camshift algorithm, compare the performance with the SIFT algorithm and Mean Shift algorithm, and Kalman filtering algorithm is used for fusion optimization aiming at the defects. Then aiming at the increasing amount of calculation in integrated algorithm, reduce dimension with the phase-path volume integral instead of the Gaussian integral in Kalman algorithm and reduce the number of sampling points in the filtering process without influencing the operational precision of the original algorithm. Finally set the target centroid position from the Camshift algorithm iteration as the observation value of the improved Kalman filtering algorithm to fix predictive value; thus to make optimal estimation of target centroid position and keep the target tracking so that the robot can understand the environmental scene and react in time correctly according to the changes. The experiments show that the improved algorithm proposed in this paper shows good performance in target tracking with obstructions and reduces the computational complexity of the algorithm through the dimension reduction.


---

## Body

## 1. Introduction

Robot moving target detection and tracking based on computer vision has become a hot spot of research scholars at home and abroad. Its essence is to use effective characteristics of the target to choose effective matching algorithm, have state estimation on the target, and obtain target parameters such as position, velocity, and trajectory and then provide reliable data information for target behavior analysis and understanding [1]. Moving target tracking technology under complex scene needs to achieve sustained and stable tracking for moving object, have certain robustness on the illumination variation of the environment and obstructions of moving target, and improve the running efficiency and accuracy of the algorithm [2]. The tracking technology advice of moving target runs successfully on intelligent robots, realizing the robot formation, scene understanding, and positioning, and it also has the very high economic benefits and social values in real life, such as intelligent automatic monitoring, human body tracking and identification, detection through a red light, and car speeding detection [3].In order to solve various problems related to the target tracking, many scholars have done a lot of innovative research work in the field, and, in view of the practical problems of the different areas, many different target tracking algorithms are proposed, which mainly concentrate in the SIFT algorithm, Mean Shift algorithm, and Camshift algorithm. The PCA-SIFT algorithm put forward by Ke and Sukthankar adopts Principal Components Analysis (PCA) to reduce the dimension of SIFT feature vector from 128 to 36 when generating feature vector through the interest points neighborhood gradient direction histogram, which makes the matching speed about three times higher than SIFT algorithm, but also paid the cost of reducing a small amount of matching performance [4]. Mikolajczyk proposes a characteristics description method, GLOH (Gradient Location-Orientation Histogram) with better uniqueness and stronger robustness by extending the SIFT algorithm. GLOH is different from SIFT in the selection of interest points neighborhood and statistical method, and it uses the principal component analysis algorithm to reduce the dimension of feature vector to 128d. Although GLOH has stronger robustness than SIFT, its time complexity is also higher [5]. Liu et al. propose PCA-SIFT algorithm and reduce the time complexity of SIFT algorithm, but also reduce the corner detection accuracy [6]. Collins proposes a way of having the Mean Shift iteration in the defied discrete scale space by adding an extra dimension nucleus, so as to find the method for the best bandwidth [7]. Comaniciu proposes the bandwidth selection problem of kernel function in Mean Shift algorithm, but with complex computation and not weak adaptability [8]. Li uses color fusion template and location prediction to improve the performance of Mean Shift tracking algorithm. On the basis of simple linear fusion for RGB trichromatism of image, select the most prominent fusion feature algorithm in the target features through the target template and the candidate similarity function and set up three target templates accordingly [9]. Guo et al. propose a multiple features fusion tracking method, which combines with color and motion edge character at the same time, and have the probability fusion with the particle filtering method. The combination of Mean Shift algorithm and particle filtering has good robustness for tracking target process in the case of complex environment and changed background, but because of the high algorithm complexity of particle filtering, it is not ideal in real time [10]. Wang et al. propose Camshift target tracking algorithm based on the frame difference and motion estimation, although, to some extent, the proposed algorithm can solve the problem of target occlusion and too fast movement, but when the background is complex and there are other moving targets, it cannot track well. At the same time, the algorithm cannot solve the problem of similar target jamming [11]. Qin combines the space histogram and the Camshift, but the algorithm has some shortcomings; for example, background information in the operation area may also be regarded as target information in statistical histogram, which reduces the precision of the histogram, influences on target tracking. At the same time, the algorithm is used in H layer of HSV space and it is hard to extract the targets when the brightness of the target and background are similar [12]. Huang combined frame difference method to realize the Camshift automatic tracking, but because frame difference method only extracts the edge of the part outline to make the holes inside the target, it tends to cause the incomplete or containing background in target extracting or reduce tracking quality for containing the other colors in the color features [13]. Li and others improve the interested area extraction in Camshift algorithm with Canny filtering, making the acquisition of target color histogram resist the influence of noise, while the method is not effective when the background profile is taken into the detection range [14]. Cai improves Camshift tracking performance with three-frame difference method, which makes the extraction of the target more accurate, but still cannot get rid of the inherent defect of frame difference method [15].This paper proposes a target tracking algorithm integrating reduced dimension optimal Kalman filtering algorithm based on phase-path volume integral with Camshift algorithm, improving the existed efficiency in target tracking aiming at Camshift algorithm.


## 2. Performance Analysis of Target Tracking Algorithm

The current common moving object tracking algorithms include SIFT algorithm, Mean Shift algorithm, and Camshift algorithm. This paper first has a performance analysis on the three kinds of algorithms.


### 2.1. Defect Analysis of SIFT Algorithm

SIFT algorithm extracts the target key points from the image, and these feature points have invariance in the image scaling, rotation, some degree of light intensity, and camera angle changing.The first step of key points detection is on the insensitive pixel location for the changes of image scales in different scales. The scale space of the image is defined as a function ofL
(
x
,
y
,
σ
), which is from the input image I
(
x
,
y
) and convolution of Gaussian kernel function G
(
x
,
y
,
σ
) with different scales:(1)
L
x
,
y
,
σ
=
G
x
,
y
,
σ
·
I
x
,
y
,in which · is a convolution operation about x and y. Consider(2)
G
x
,
y
,
σ
=
1
2
π
σ
2
e
x
2
+
y
2
/
2
σ
2
.In order to detect the key position effectively in image scale space, the differential Gaussian functionD
(
x
,
y
,
σ
) is used here, which can be composed of image convolution results in two adjacent scales by subtracting(3)
D
x
,
y
,
σ
=
G
x
,
y
,
k
σ
-
G
x
,
y
,
k
-
1
σ
·
I
x
,
y
=
L
x
,
y
,
k
σ
-
L
x
,
y
,
k
-
1
σ
.Then set the gotten extreme value point as alternative key point, using the Taylor expansion of the scale space functionD
(
x
,
y
,
σ
):(4)
D
X
=
D
+
∂
D
T
∂
X
X
+
1
2
X
T
∂
2
D
∂
X
2
X
,in which D
(
X
) and its expansion item calculate in the sampling point and X
=
(
x
,
y
,
σ
)
T is the compensation amount of the point. When the expansion item of D
(
X
) is 0, the corresponding X is the extreme point, and the position is decided by the following formula:(5)
X
^
=
-
∂
2
D
-
1
∂
X
2
∂
D
∂
X
.In the specific calculation, the difference value between adjacent sampling points is used as the approximate scale space functionD
(
x
,
y
,
σ
) and its expansion. If the amount of compensation X
^ in various scales is greater than 0.5, then the distance between the current sample point and the extreme value point is regarded as not the shortest. Next exclude the current sample point and continue the same calculation for the other sample points. Finally get the approximate estimation of extreme value point location by combining X
^ with its corresponding sampling points.The valueD
(
X
^
) of scale space function in the extreme point will be used to eliminate the unstable extreme value points of low contrast. Substitute formula (5) into (4) and we can get(6)
D
X
^
=
D
+
1
2
∂
D
T
∂
X
X
^
.By setting the threshold value, abandon the extreme value points whoseD
(
X
^
) is less than the threshold value. A typical threshold size can be set as 0.05.It can be seen from the above analysis that SIFT algorithm relies on extracting features in great quantities; thus it achieves precise matching with information redundancy strategy and, at the same time, also increases the amount of calculation of the algorithm itself.


### 2.2. Defect Analysis of the Mean Shift Algorithm

Mean Shift algorithm is a kind of estimation technique with smooth and density estimation, and algorithm convergence is the heart of determining the precision of the target tracking. The convergence of Mean Shift and the increasing of the value is equivalent to the proven proposition: if kernel function is defined by a descending concave functionk
(
x
), then sequences y
j
j
=
1,2 and f
^
h
,
K
j are decreasing convergence.Asn is limited, and sequence f
^
h
,
K
j is bounded, according to the definition of sequence f
^
h
,
K
j,(7)
f
^
h
,
K
j
-
f
^
h
,
K
j
=
c
k
,
d
n
h
d
∑
i
=
1
n
k
y
j
+
1
-
x
i
h
2
-
k
y
j
-
x
i
h
2
.According to the definition of concave function, for allx
1
,
x
2
∈
0
,
∞, x
1
≠
x
2, they have(8)
k
x
2
≥
k
x
1
+
k
′
x
2
x
2
-
x
1
.Asg
(
x
)
=
-
k
′
(
x
), formula (8) can be written as(9)
k
x
2
-
k
x
1
≥
+
g
x
1
x
1
-
x
2
.Substituting the above formula into (7), we can get(10)
f
^
h
,
K
j
+
1
-
f
^
h
,
K
j
≥
c
k
,
d
n
h
d
+
2
∑
i
=
1
n
g
y
j
-
x
i
h
2
y
j
-
x
i
2
-
y
j
+
1
-
x
i
2
=
c
k
,
d
n
h
d
+
2
∑
i
=
1
n
g
y
j
-
x
i
h
2
y
j
2
+
2
y
j
+
1
T
-
y
j
T
x
i
-
y
j
+
1
2
.We can get(11)
f
^
h
,
K
j
+
1
-
f
^
h
,
K
j
≥
c
k
,
d
n
h
d
+
2
y
j
+
1
-
y
j
2
∑
i
=
1
n
g
y
j
-
x
i
h
2
.Ask
(
x
) is monotone decreasing in x
≥
0, so ∑
i
=
1
n
g
y
j
-
x
i
/
h
2 is a positive real number, for if only y
j
+
1
≠
y
i, (
c
k
,
d
/
n
h
d
+
2
)
y
j
+
1
-
y
j
2
∑
i
=
1
n
g
y
j
-
x
i
/
h
2 is a nonnegative real number. This shows that f
^
h
,
K
j is an increasing sequence. Since it is bounded, it is a convergent sequence.Then accumulatem items of (11); we can get(12)
f
^
h
,
K
j
+
m
-
f
^
h
,
K
j
≥
c
k
,
d
n
h
d
+
2
y
j
+
m
-
y
j
2
M
.M means the minimum of the ∑
i
=
1
n
g
(
y
j
-
x
i
)
/
h
2 in m items of the above formula. It shows that y
j
j
=
1,2 is Cauchy series, and y
j
j
=
1,2 is also convergent.As can be seen from the above analysis, the Mean Shift algorithm will fail in tracking when the target scale changes due to the fact that the window width remains the same in the target tracking process, and when the target speed is high, the tracking effect is not good.


### 2.3. Defect Analysis of Camshift Algorithm

Extend Mean Shift algorithm to the continuous image sequence, which generally refers to the image sequence; thus it forms the Camshift algorithm. The basic idea of Camshift algorithm is to have Mean Shift algorithm for all the frames of the image; then set the center and size of the search window on the previous frame as the initial value of the search window on the next frame, and the target tracking can be achieved with such iteration.Camshift algorithm tracks target with elliptical lock. The size and the deflection angle of the tracking target are shown in Figure1.Figure 1
The size and the deflection angle of the tracking target region.Define the secondary moment as follows:(13)
M
20
=
∑
x
∑
y
x
2
I
c
x
,
y
,
M
02
=
∑
x
∑
y
y
2
I
c
x
,
y
,
M
11
=
∑
x
∑
y
x
y
I
c
x
,
y
.Then long axis and short axis of target ellipse area, respectively, are(14)
l
=
a
+
c
+
b
2
+
a
-
c
2
2
,
w
=
a
+
c
+
b
2
+
a
-
c
2
2
.In the formula, the values ofa, b, c are obtained with the following formula:(15)
a
=
M
20
M
00
-
x
c
2
,
b
=
2
M
11
M
00
-
x
c
y
c
,
c
=
M
02
M
00
-
y
2
.The target angleθ of the direction is defined as the included angel less than 18
0
° between long axis and the horizontal plane. Consider(16)
θ
=
1
2
tan
-
1
⁡
b
a
-
c
.Camshift algorithm is to set the result of the previous frame as the initial value of the next search window frame; then find optimal target location in the field of the center coordinates. If the target moves too fast, which makes the distance between the current frame and the previous frame center larger, the previous location is still used in the current frame search as the initial position, which will lead to increasing times in searching target, and even failure in tracking target.


### 2.4. Performance Analysis on the Three Algorithms

Use ten different image sequences to test the target tracking of the above three algorithms, and extract 100 observation sequences from each image sequence to check the accuracy of target tracking. The algorithm testing results of five image sequences without obstructions are shown in the Figure2. And the testing results of the other five image sequences with obstructions are shown in Figure 3.Figure 2
The performance comparing results of three algorithms without obstructions.Figure 3
The performance comparing results of three algorithms with obstructions.After analyzing the results of the experiment, Camshift algorithm has better performance in terms of target tracking. So this paper will apply Camshift algorithm to target tracking and improve the efficiency of Camshift algorithm.


## 2.1. Defect Analysis of SIFT Algorithm

SIFT algorithm extracts the target key points from the image, and these feature points have invariance in the image scaling, rotation, some degree of light intensity, and camera angle changing.The first step of key points detection is on the insensitive pixel location for the changes of image scales in different scales. The scale space of the image is defined as a function ofL
(
x
,
y
,
σ
), which is from the input image I
(
x
,
y
) and convolution of Gaussian kernel function G
(
x
,
y
,
σ
) with different scales:(1)
L
x
,
y
,
σ
=
G
x
,
y
,
σ
·
I
x
,
y
,in which · is a convolution operation about x and y. Consider(2)
G
x
,
y
,
σ
=
1
2
π
σ
2
e
x
2
+
y
2
/
2
σ
2
.In order to detect the key position effectively in image scale space, the differential Gaussian functionD
(
x
,
y
,
σ
) is used here, which can be composed of image convolution results in two adjacent scales by subtracting(3)
D
x
,
y
,
σ
=
G
x
,
y
,
k
σ
-
G
x
,
y
,
k
-
1
σ
·
I
x
,
y
=
L
x
,
y
,
k
σ
-
L
x
,
y
,
k
-
1
σ
.Then set the gotten extreme value point as alternative key point, using the Taylor expansion of the scale space functionD
(
x
,
y
,
σ
):(4)
D
X
=
D
+
∂
D
T
∂
X
X
+
1
2
X
T
∂
2
D
∂
X
2
X
,in which D
(
X
) and its expansion item calculate in the sampling point and X
=
(
x
,
y
,
σ
)
T is the compensation amount of the point. When the expansion item of D
(
X
) is 0, the corresponding X is the extreme point, and the position is decided by the following formula:(5)
X
^
=
-
∂
2
D
-
1
∂
X
2
∂
D
∂
X
.In the specific calculation, the difference value between adjacent sampling points is used as the approximate scale space functionD
(
x
,
y
,
σ
) and its expansion. If the amount of compensation X
^ in various scales is greater than 0.5, then the distance between the current sample point and the extreme value point is regarded as not the shortest. Next exclude the current sample point and continue the same calculation for the other sample points. Finally get the approximate estimation of extreme value point location by combining X
^ with its corresponding sampling points.The valueD
(
X
^
) of scale space function in the extreme point will be used to eliminate the unstable extreme value points of low contrast. Substitute formula (5) into (4) and we can get(6)
D
X
^
=
D
+
1
2
∂
D
T
∂
X
X
^
.By setting the threshold value, abandon the extreme value points whoseD
(
X
^
) is less than the threshold value. A typical threshold size can be set as 0.05.It can be seen from the above analysis that SIFT algorithm relies on extracting features in great quantities; thus it achieves precise matching with information redundancy strategy and, at the same time, also increases the amount of calculation of the algorithm itself.


## 2.2. Defect Analysis of the Mean Shift Algorithm

Mean Shift algorithm is a kind of estimation technique with smooth and density estimation, and algorithm convergence is the heart of determining the precision of the target tracking. The convergence of Mean Shift and the increasing of the value is equivalent to the proven proposition: if kernel function is defined by a descending concave functionk
(
x
), then sequences y
j
j
=
1,2 and f
^
h
,
K
j are decreasing convergence.Asn is limited, and sequence f
^
h
,
K
j is bounded, according to the definition of sequence f
^
h
,
K
j,(7)
f
^
h
,
K
j
-
f
^
h
,
K
j
=
c
k
,
d
n
h
d
∑
i
=
1
n
k
y
j
+
1
-
x
i
h
2
-
k
y
j
-
x
i
h
2
.According to the definition of concave function, for allx
1
,
x
2
∈
0
,
∞, x
1
≠
x
2, they have(8)
k
x
2
≥
k
x
1
+
k
′
x
2
x
2
-
x
1
.Asg
(
x
)
=
-
k
′
(
x
), formula (8) can be written as(9)
k
x
2
-
k
x
1
≥
+
g
x
1
x
1
-
x
2
.Substituting the above formula into (7), we can get(10)
f
^
h
,
K
j
+
1
-
f
^
h
,
K
j
≥
c
k
,
d
n
h
d
+
2
∑
i
=
1
n
g
y
j
-
x
i
h
2
y
j
-
x
i
2
-
y
j
+
1
-
x
i
2
=
c
k
,
d
n
h
d
+
2
∑
i
=
1
n
g
y
j
-
x
i
h
2
y
j
2
+
2
y
j
+
1
T
-
y
j
T
x
i
-
y
j
+
1
2
.We can get(11)
f
^
h
,
K
j
+
1
-
f
^
h
,
K
j
≥
c
k
,
d
n
h
d
+
2
y
j
+
1
-
y
j
2
∑
i
=
1
n
g
y
j
-
x
i
h
2
.Ask
(
x
) is monotone decreasing in x
≥
0, so ∑
i
=
1
n
g
y
j
-
x
i
/
h
2 is a positive real number, for if only y
j
+
1
≠
y
i, (
c
k
,
d
/
n
h
d
+
2
)
y
j
+
1
-
y
j
2
∑
i
=
1
n
g
y
j
-
x
i
/
h
2 is a nonnegative real number. This shows that f
^
h
,
K
j is an increasing sequence. Since it is bounded, it is a convergent sequence.Then accumulatem items of (11); we can get(12)
f
^
h
,
K
j
+
m
-
f
^
h
,
K
j
≥
c
k
,
d
n
h
d
+
2
y
j
+
m
-
y
j
2
M
.M means the minimum of the ∑
i
=
1
n
g
(
y
j
-
x
i
)
/
h
2 in m items of the above formula. It shows that y
j
j
=
1,2 is Cauchy series, and y
j
j
=
1,2 is also convergent.As can be seen from the above analysis, the Mean Shift algorithm will fail in tracking when the target scale changes due to the fact that the window width remains the same in the target tracking process, and when the target speed is high, the tracking effect is not good.


## 2.3. Defect Analysis of Camshift Algorithm

Extend Mean Shift algorithm to the continuous image sequence, which generally refers to the image sequence; thus it forms the Camshift algorithm. The basic idea of Camshift algorithm is to have Mean Shift algorithm for all the frames of the image; then set the center and size of the search window on the previous frame as the initial value of the search window on the next frame, and the target tracking can be achieved with such iteration.Camshift algorithm tracks target with elliptical lock. The size and the deflection angle of the tracking target are shown in Figure1.Figure 1
The size and the deflection angle of the tracking target region.Define the secondary moment as follows:(13)
M
20
=
∑
x
∑
y
x
2
I
c
x
,
y
,
M
02
=
∑
x
∑
y
y
2
I
c
x
,
y
,
M
11
=
∑
x
∑
y
x
y
I
c
x
,
y
.Then long axis and short axis of target ellipse area, respectively, are(14)
l
=
a
+
c
+
b
2
+
a
-
c
2
2
,
w
=
a
+
c
+
b
2
+
a
-
c
2
2
.In the formula, the values ofa, b, c are obtained with the following formula:(15)
a
=
M
20
M
00
-
x
c
2
,
b
=
2
M
11
M
00
-
x
c
y
c
,
c
=
M
02
M
00
-
y
2
.The target angleθ of the direction is defined as the included angel less than 18
0
° between long axis and the horizontal plane. Consider(16)
θ
=
1
2
tan
-
1
⁡
b
a
-
c
.Camshift algorithm is to set the result of the previous frame as the initial value of the next search window frame; then find optimal target location in the field of the center coordinates. If the target moves too fast, which makes the distance between the current frame and the previous frame center larger, the previous location is still used in the current frame search as the initial position, which will lead to increasing times in searching target, and even failure in tracking target.


## 2.4. Performance Analysis on the Three Algorithms

Use ten different image sequences to test the target tracking of the above three algorithms, and extract 100 observation sequences from each image sequence to check the accuracy of target tracking. The algorithm testing results of five image sequences without obstructions are shown in the Figure2. And the testing results of the other five image sequences with obstructions are shown in Figure 3.Figure 2
The performance comparing results of three algorithms without obstructions.Figure 3
The performance comparing results of three algorithms with obstructions.After analyzing the results of the experiment, Camshift algorithm has better performance in terms of target tracking. So this paper will apply Camshift algorithm to target tracking and improve the efficiency of Camshift algorithm.


## 3. Target Centroid Position Estimation Optimization of Camshift Algorithm

### 3.1. Reduced Dimension Optimization of Kalman Filtering Algorithm

This paper adopts the integration of Camshift algorithm and Kalman algorithm to improve the defects of Camshift algorithm but considers that it improves the complexity of the algorithm and greatly increases the amount of calculation after combining Kalman algorithm, so the optimization in calculation amount of Kalman algorithm comes first.The sampling point number of Kalman algorithm increases with higher dimension in dealing with nonlinear system, and filtering calculation also increases, while the Gaussian integral has the greatest impact on the calculation of Kalman algorithm, so phase-path volume integral is used instead of Gaussian integral in Kalman algorithm to reduce dimension. In the case of no loss of filtering precision, it reduces the number of sampling points and the amount of calculation in the process of filtering.Phase-path volume integral is an approximate integral after nonlinear function passing to a series of point setD and weighted sum, but the requirements for the point set D are as follows.Ifx
∈
D, change the order and the symbols of the elements in x to get y; there are still y
∈
D, and the weights of the two factors are equal, and D is called the holohedral symmetry.For an elementμ
=
(
u
1
,
u
2
,
…
,
u
r
,
0
,
…
,
0
)
∈
D in holohedral symmetry area D of phase-path volume integral, if u
i
≥
u
i
+
1
>
0,  μ
∈
R
n, then μ can be defined as the generator of the holohedral symmetry area D in n dimensional real number area. At the same time, define (
u
1
,
u
2
,
…
,
u
r
)
T as the same collection with D. Set the Gaussian integral as(17)
I
=
C
∫
f
x
exp
⁡
x
T
x
d
x
.If constantC is not considered, the integral can transform by integral conversion into(18)
I
=
∫
0
∞
∫
U
n
f
r
y
r
n
-
1
e
-
r
2
d
σ
y
d
r
.Among them,U
n is the unit volume of n dimension, and σ
· is the element on U
n; at this point, the integral of formula (18) is converted into a volume integral and a phase-path integral:(19)
S
r
=
∫
U
n
f
r
y
d
σ
y
,
(20)
R
=
∫
0
∞
S
r
r
n
-
1
e
-
r
2
d
r
.The volume integral in formula (20) can be approximate with volume rules. It can be known from the holohedral symmetry rules of the volume that for every monomial y
1
d
1
y
2
d
2
⋯
y
n
d
n in f
r
y, in which d
i is the variable order; when ∑
i
=
1
n
d
i is odd integer, the integral is 0. So if we want to be accurate to three monomial, namely, approximate to the integral with the phase-path volume rules, and as long as the two points can be accurately obtained with the chosen volume point and the corresponding weights, only the conditions ∑
i
=
1
n
d
i
=
0 and ∑
i
=
1
n
d
i
=
2, that is, f
(
y
)
=
1 and f
(
y
)
=
y
1
2, need to be considered. The formula is as follows:(21)
2
n
w
=
w
∑
i
=
1
2
n
1
=
∫
U
n
d
σ
y
=
A
n
,
f
y
=
1
,
2
w
u
1
2
=
w
∑
i
=
1
2
n
f
u
i
=
∫
U
n
y
1
2
d
σ
y
=
A
n
n
,
f
y
=
y
1
2
,in which A
n
=
2
π
n
/
Γ
(
n
/
2
) means the unit volume of n dimension, and Γ
(
n
)
=
∫
0
∞
x
n
-
1
exp
⁡
-
x
d
x.Solve formula (21); we can get w
=
A
n
/
2
n; then we can get the intersection points of volume points and each axis, that is, point set [1]. Consider(22)
S
r
≈
∑
i
=
1
2
n
w
f
r
1
i
.For the phase-path integral type, setx
=
r, and it can be transformed through the integral conversion into(23)
R
=
1
2
∫
0
∞
S
x
x
n
/
2
-
1
e
-
x
d
x
.According to the rules of phase-path volume integral, whenS
x
=
1 or x, that is, when S
(
r
)
=
1 or r
2, the accurate integral type can be obtained. At this time, the selected integral points and weights, respectively, are(24)
ω
1
=
Γ
n
/
2
2
,
(25)
r
1
=
n
2
,
(26)
R
≈
∑
j
=
1
1
ω
j
S
r
j
.Merging (22) and (26), we can get the approximate integral of formula (18):(27)
I
≈
∑
j
=
1
1
∑
i
=
1
2
n
w
ω
j
f
r
j
1
i
=
∑
i
=
1
2
n
w
ω
1
f
r
1
1
i
=
∑
i
=
1
2
n
ω
f
r
1
1
i
,in which ω
=
π
n
/
2
n, r
1
=
n
/
2.Then, use the phase-path volume integral instead of Gaussian integral in Kalman algorithm. The nonlinear system of Kalman algorithm can be shown in the following form:(28)
x
k
+
1
=
F
k
ξ
k
x
k
+
g
k
ξ
k
+
w
k
,
y
k
=
H
k
x
k
+
v
k
,in which ξ
k is the previous l element of x
k; that is, x
k
=
[
ξ
k
T
,
η
k
T
]
T.If statistical properties(
x
^
k
-
1
,
P
k
-
1
) of x at the time k
-
1 are known, then the filtering function of Kalman algorithm is as follows:(29)
P
k
/
k
-
1
=
P
k
/
k
-
1
x
+
Q
k
-
1
,
(30)
K
k
=
P
k
/
k
-
1
H
k
H
k
P
k
/
k
-
1
H
k
T
+
R
k
-
1
,
(31)
x
^
k
=
x
^
k
/
k
-
1
+
K
k
y
k
-
H
k
x
^
k
/
k
-
1
,
(32)
P
k
=
I
-
K
k
H
k
P
k
/
k
-
1
,in which x
^
k
/
k
-
1 and P
k
/
k
-
1
x are the Gaussian integrals about ξ
k
-
1. Consider(33)
x
^
k
/
k
-
1
=
∫
Φ
k
-
1
ξ
k
-
1
N
ξ
k
-
1
,
ξ
^
k
-
1
,
P
k
-
1
ξ
d
ξ
k
-
1
,
P
k
/
k
-
1
x
=
∫
Ψ
k
-
1
ξ
k
-
1
N
ξ
k
-
1
,
ξ
^
k
-
1
,
P
k
-
1
ξ
d
ξ
k
-
1
-
x
^
k
/
k
-
1
x
^
k
/
k
-
1
T
.In the standard Kalman algorithm, the number of sampling points on statex is 2
n, for ξ
k
-
1 is l dimension vector; if the phase-path volume is used to approximate formula (33), then only 2
l sampling points of ξ
k
-
1 are needed. The formulas are as follows:(34)
x
k
-
1
i
=
ξ
^
k
-
1
-
l
P
k
-
1
ξ
i
,
i
=
1,2
,
…
,
l
,
x
k
-
1
i
=
ξ
^
k
-
1
+
l
P
k
-
1
ξ
i
,
i
=
l
+
1
,
l
+
2
,
…
,
2
l
,
x
^
k
/
k
-
1
=
1
2
l
∑
i
=
1
2
l
Φ
k
-
1
x
k
-
1
i
.Then constitute reduced dimension Kalman filtering algorithm by combining formulas (29)~(32).


### 3.2. Camshift Algorithm Based on Kalman Prediction Estimation

The basic idea of Camshift algorithm based on Kalman prediction estimation is that set the optimal estimation of target centroid in currentk frame as the initial position of the Camshift algorithm search window in the next frame and then revise the predicted value with the centroid result of Camshift algorithm iteration as the observation value Y
k of the improved Kalman filtering algorithm, so as to obtain the optimal estimation of target centroid position of the next frame. The forecast of target centroid position can solve the problem of quick target motion effectively, making sure the search window of Camshift algorithm can keep up with the movement of the target, improving the effect of tracking.Definition 1.
The state vectorX
k of Kalman filtering algorithm is (
s
x
k
,
s
y
k
,
v
x
k
,
v
y
k
)
T, in which s
x
k and s
y
k represent the target centroid position, v
x
k and v
y
k, respectively, represent the displacement speed of the target in the direction of x and y. Define observation vector as (
ω
x
k
,
ω
y
k
)
T, in which ω
x
k and ω
y
k represent the target centroid position obtained with Camshift algorithm. Due to the fact that the time interval between two frames in image sequence is short, we regard it as uniform motion in unit time interval and then define the transition matrix A
k as follows:(35)
A
k
=
1
0
Δ
t
0
0
1
0
Δ
t
0
0
1
0
0
0
0
1
,in which Δ
t is the time interval between t
k and t
k
-
1. From the system state and observation state, the observation matrix is as follows:(36)
C
k
=
1
0
0
0
0
1
0
0
.
The estimation on the centroid position of moving targets using improved Kalman filtering algorithm in Camshift tracking algorithm can be roughly divided into three stages, which are as follows.(
1) Initialization of the Kalman Filtering Algorithm. Initialize improved Kalman filtering algorithm, initialize X
0 with the target centroid position and moving speed obtained by the moving target detection algorithm, and record the current time.(2
) Centroid Position Estimation. Calculate the time interval Δ
t with the previous frame image when processing the current frame image and substitute it in the transition matrix A
k. Use the iterative operation by taking the location (
s
x
k
-
1
,
s
y
k
-
1
) of X
k
-
1 as the center of the Camshift algorithm search window and then substitute the searched final location into the observed value Y
k
=
(
ω
x
k
,
ω
y
k
)
T to correct predicted value.(
3) Location Update. Substitute the state vector X
k
-
1 and the observation vector Y
k into the recursive formula of improved Kalman filtering algorithm, get the optimal target centroid position estimation X
^
k of target area centroid in the current frame, and record the moment of the current frame image and target centroid position.


## 3.1. Reduced Dimension Optimization of Kalman Filtering Algorithm

This paper adopts the integration of Camshift algorithm and Kalman algorithm to improve the defects of Camshift algorithm but considers that it improves the complexity of the algorithm and greatly increases the amount of calculation after combining Kalman algorithm, so the optimization in calculation amount of Kalman algorithm comes first.The sampling point number of Kalman algorithm increases with higher dimension in dealing with nonlinear system, and filtering calculation also increases, while the Gaussian integral has the greatest impact on the calculation of Kalman algorithm, so phase-path volume integral is used instead of Gaussian integral in Kalman algorithm to reduce dimension. In the case of no loss of filtering precision, it reduces the number of sampling points and the amount of calculation in the process of filtering.Phase-path volume integral is an approximate integral after nonlinear function passing to a series of point setD and weighted sum, but the requirements for the point set D are as follows.Ifx
∈
D, change the order and the symbols of the elements in x to get y; there are still y
∈
D, and the weights of the two factors are equal, and D is called the holohedral symmetry.For an elementμ
=
(
u
1
,
u
2
,
…
,
u
r
,
0
,
…
,
0
)
∈
D in holohedral symmetry area D of phase-path volume integral, if u
i
≥
u
i
+
1
>
0,  μ
∈
R
n, then μ can be defined as the generator of the holohedral symmetry area D in n dimensional real number area. At the same time, define (
u
1
,
u
2
,
…
,
u
r
)
T as the same collection with D. Set the Gaussian integral as(17)
I
=
C
∫
f
x
exp
⁡
x
T
x
d
x
.If constantC is not considered, the integral can transform by integral conversion into(18)
I
=
∫
0
∞
∫
U
n
f
r
y
r
n
-
1
e
-
r
2
d
σ
y
d
r
.Among them,U
n is the unit volume of n dimension, and σ
· is the element on U
n; at this point, the integral of formula (18) is converted into a volume integral and a phase-path integral:(19)
S
r
=
∫
U
n
f
r
y
d
σ
y
,
(20)
R
=
∫
0
∞
S
r
r
n
-
1
e
-
r
2
d
r
.The volume integral in formula (20) can be approximate with volume rules. It can be known from the holohedral symmetry rules of the volume that for every monomial y
1
d
1
y
2
d
2
⋯
y
n
d
n in f
r
y, in which d
i is the variable order; when ∑
i
=
1
n
d
i is odd integer, the integral is 0. So if we want to be accurate to three monomial, namely, approximate to the integral with the phase-path volume rules, and as long as the two points can be accurately obtained with the chosen volume point and the corresponding weights, only the conditions ∑
i
=
1
n
d
i
=
0 and ∑
i
=
1
n
d
i
=
2, that is, f
(
y
)
=
1 and f
(
y
)
=
y
1
2, need to be considered. The formula is as follows:(21)
2
n
w
=
w
∑
i
=
1
2
n
1
=
∫
U
n
d
σ
y
=
A
n
,
f
y
=
1
,
2
w
u
1
2
=
w
∑
i
=
1
2
n
f
u
i
=
∫
U
n
y
1
2
d
σ
y
=
A
n
n
,
f
y
=
y
1
2
,in which A
n
=
2
π
n
/
Γ
(
n
/
2
) means the unit volume of n dimension, and Γ
(
n
)
=
∫
0
∞
x
n
-
1
exp
⁡
-
x
d
x.Solve formula (21); we can get w
=
A
n
/
2
n; then we can get the intersection points of volume points and each axis, that is, point set [1]. Consider(22)
S
r
≈
∑
i
=
1
2
n
w
f
r
1
i
.For the phase-path integral type, setx
=
r, and it can be transformed through the integral conversion into(23)
R
=
1
2
∫
0
∞
S
x
x
n
/
2
-
1
e
-
x
d
x
.According to the rules of phase-path volume integral, whenS
x
=
1 or x, that is, when S
(
r
)
=
1 or r
2, the accurate integral type can be obtained. At this time, the selected integral points and weights, respectively, are(24)
ω
1
=
Γ
n
/
2
2
,
(25)
r
1
=
n
2
,
(26)
R
≈
∑
j
=
1
1
ω
j
S
r
j
.Merging (22) and (26), we can get the approximate integral of formula (18):(27)
I
≈
∑
j
=
1
1
∑
i
=
1
2
n
w
ω
j
f
r
j
1
i
=
∑
i
=
1
2
n
w
ω
1
f
r
1
1
i
=
∑
i
=
1
2
n
ω
f
r
1
1
i
,in which ω
=
π
n
/
2
n, r
1
=
n
/
2.Then, use the phase-path volume integral instead of Gaussian integral in Kalman algorithm. The nonlinear system of Kalman algorithm can be shown in the following form:(28)
x
k
+
1
=
F
k
ξ
k
x
k
+
g
k
ξ
k
+
w
k
,
y
k
=
H
k
x
k
+
v
k
,in which ξ
k is the previous l element of x
k; that is, x
k
=
[
ξ
k
T
,
η
k
T
]
T.If statistical properties(
x
^
k
-
1
,
P
k
-
1
) of x at the time k
-
1 are known, then the filtering function of Kalman algorithm is as follows:(29)
P
k
/
k
-
1
=
P
k
/
k
-
1
x
+
Q
k
-
1
,
(30)
K
k
=
P
k
/
k
-
1
H
k
H
k
P
k
/
k
-
1
H
k
T
+
R
k
-
1
,
(31)
x
^
k
=
x
^
k
/
k
-
1
+
K
k
y
k
-
H
k
x
^
k
/
k
-
1
,
(32)
P
k
=
I
-
K
k
H
k
P
k
/
k
-
1
,in which x
^
k
/
k
-
1 and P
k
/
k
-
1
x are the Gaussian integrals about ξ
k
-
1. Consider(33)
x
^
k
/
k
-
1
=
∫
Φ
k
-
1
ξ
k
-
1
N
ξ
k
-
1
,
ξ
^
k
-
1
,
P
k
-
1
ξ
d
ξ
k
-
1
,
P
k
/
k
-
1
x
=
∫
Ψ
k
-
1
ξ
k
-
1
N
ξ
k
-
1
,
ξ
^
k
-
1
,
P
k
-
1
ξ
d
ξ
k
-
1
-
x
^
k
/
k
-
1
x
^
k
/
k
-
1
T
.In the standard Kalman algorithm, the number of sampling points on statex is 2
n, for ξ
k
-
1 is l dimension vector; if the phase-path volume is used to approximate formula (33), then only 2
l sampling points of ξ
k
-
1 are needed. The formulas are as follows:(34)
x
k
-
1
i
=
ξ
^
k
-
1
-
l
P
k
-
1
ξ
i
,
i
=
1,2
,
…
,
l
,
x
k
-
1
i
=
ξ
^
k
-
1
+
l
P
k
-
1
ξ
i
,
i
=
l
+
1
,
l
+
2
,
…
,
2
l
,
x
^
k
/
k
-
1
=
1
2
l
∑
i
=
1
2
l
Φ
k
-
1
x
k
-
1
i
.Then constitute reduced dimension Kalman filtering algorithm by combining formulas (29)~(32).


## 3.2. Camshift Algorithm Based on Kalman Prediction Estimation

The basic idea of Camshift algorithm based on Kalman prediction estimation is that set the optimal estimation of target centroid in currentk frame as the initial position of the Camshift algorithm search window in the next frame and then revise the predicted value with the centroid result of Camshift algorithm iteration as the observation value Y
k of the improved Kalman filtering algorithm, so as to obtain the optimal estimation of target centroid position of the next frame. The forecast of target centroid position can solve the problem of quick target motion effectively, making sure the search window of Camshift algorithm can keep up with the movement of the target, improving the effect of tracking.Definition 1.
The state vectorX
k of Kalman filtering algorithm is (
s
x
k
,
s
y
k
,
v
x
k
,
v
y
k
)
T, in which s
x
k and s
y
k represent the target centroid position, v
x
k and v
y
k, respectively, represent the displacement speed of the target in the direction of x and y. Define observation vector as (
ω
x
k
,
ω
y
k
)
T, in which ω
x
k and ω
y
k represent the target centroid position obtained with Camshift algorithm. Due to the fact that the time interval between two frames in image sequence is short, we regard it as uniform motion in unit time interval and then define the transition matrix A
k as follows:(35)
A
k
=
1
0
Δ
t
0
0
1
0
Δ
t
0
0
1
0
0
0
0
1
,in which Δ
t is the time interval between t
k and t
k
-
1. From the system state and observation state, the observation matrix is as follows:(36)
C
k
=
1
0
0
0
0
1
0
0
.
The estimation on the centroid position of moving targets using improved Kalman filtering algorithm in Camshift tracking algorithm can be roughly divided into three stages, which are as follows.(
1) Initialization of the Kalman Filtering Algorithm. Initialize improved Kalman filtering algorithm, initialize X
0 with the target centroid position and moving speed obtained by the moving target detection algorithm, and record the current time.(2
) Centroid Position Estimation. Calculate the time interval Δ
t with the previous frame image when processing the current frame image and substitute it in the transition matrix A
k. Use the iterative operation by taking the location (
s
x
k
-
1
,
s
y
k
-
1
) of X
k
-
1 as the center of the Camshift algorithm search window and then substitute the searched final location into the observed value Y
k
=
(
ω
x
k
,
ω
y
k
)
T to correct predicted value.(
3) Location Update. Substitute the state vector X
k
-
1 and the observation vector Y
k into the recursive formula of improved Kalman filtering algorithm, get the optimal target centroid position estimation X
^
k of target area centroid in the current frame, and record the moment of the current frame image and target centroid position.


## 4. Algorithm Performance Test

First take performance test to the improved Kalman filtering algorithm in order to verify the effectiveness of the improved algorithm proposed in this paper, having 100 Monte Carlo simulations under the same condition with the standard Kalman filtering algorithm and reduced dimension Kalman filtering algorithm (IM-Kalman). The applied software is Matlab, and the computer processor is Core I7-3610 with the main frequency of 2.3 GHz, memory of 4 G. The mean absolute error curves of two filtering algorithms for state estimation are shown in Figures4~6.Figure 4
Absolute value error of moving targets.Figure 5
Mean absolute error ofX axial position.Figure 6
Mean absolute error ofY axial position.When processing the single frame image, the accuracy of state estimation of standard particle filter (PF) algorithm, standard Kalman filter algorithm and IM-Kalman filter algorithm is contrasted, respectively, at the particle number of 50, 100, and 150, and the results are shown in Tables1 and 2.Table 1
The comparison results of used time in single frame image processing.
Algorithm
Population
Used time of single frame image processing/s
PF
50
0.0621
Kalman
50
0.0416
IM-Kalman
50
0.0248
PF
100
0.8013
Kalman
100
0.6104
IM-Kalman
100
0.2957
PF
150
2.6383
Kalman
150
1.3727
IM-Kalman
150
0.2269Table 2
The comparison results of state estimation accuracy.
Algorithm
Particle number
State estimation accuracy/RMSE
PF
50
4.9528
Kalman
50
3.2105
IM-Kalman
50
2.1031
PF
100
3.5131
Kalman
100
1.9921
IM-Kalman
100
1.7045
PF
150
3.0168
Kalman
150
0.8563
IM-Kalman
150
0.2305It can be seen from Table1 that when the particle number is 50, the time used in single frame image processing of the three algorithms has no big differences, while the time used of the improved Kalman filtering algorithm proposed in this paper is slightly less than that of the other two algorithms. But when the particle number increases to 100, the processing speed of PF algorithm and the standard Kalman filtering algorithm is significantly slower, while the speed of IM-Kalman filtering algorithm proposed in this paper changes slightly. When the particle number increases to 150, the processing speed of IM-Kalman filtering algorithm proposed in this paper is much higher than the PF algorithm and the standard Kalman filtering algorithm.As can be seen from Table2, when the particle number is 50, there has been a certain gap among the state estimation accuracy of three algorithms, and the accuracy of IM-Kalman filtering algorithm proposed in this paper is much higher than the other two algorithms. When particles are increased to 100, the precision of PF algorithm and the standard Kalman filtering algorithm has been reduced slightly, but there is no significant reduction in the IM-Kalman filter algorithm proposed in this paper. When the particle number increases to 150, the estimation accuracy of the PF algorithm and the standard Kalman filtering algorithm has been less than 1, while the estimation accuracy of IM-Kalman filter algorithm reduces a little.The simulation results show that IM-Kalman algorithm has better estimation precision and uses less time. Then the standard Camshift algorithm and the improved Camshift algorithm are used for target tracking the four 100 frames video sequences, which are human motion video sequences without obstructions (Test 1), human motion video sequences with obstructions (Test 2), vehicle motion video sequences without obstructions (Test 3), and vehicle motion video sequences with obstructions (Test 4). Results are shown as follows.(
1) The Human Body Target Tracking. First have the human body target tracking with obstructions and without them. Figure 7 shows target tracking result of the standard Camshift algorithm in the absence of any obstructions, and Figure 8 shows the result of improved Camshift algorithm in the same case. Figure 9 is the target tracking result of standard Camshift algorithm with obstructions, while Figure 10 is the result of improved Camshift algorithm in the same case.Figure 7
Target tracking result of Camshift algorithm without obstructions (Test 1).Figure 8
Target tracking result of improved Camshift algorithm without obstructions (Test 1).Figure 9
Target tracking result of Camshift algorithm with obstructions (Test 2).Figure 10
Target tracking result of improved Camshift algorithm with obstructions (Test 2).It can be seen from the above experimental results that the improved Camshift algorithm put forward in this paper has better effect than the standard Camshift algorithm in the human body tracking with obstructions.(
2
) Vehicle Target Tracking. Then have the vehicle target tracking with obstructions and without them. Figure 11 shows target tracking result of the standard Camshift algorithm in the absence of any obstructions, and Figure 12 shows the result of improved Camshift algorithm in the same case. Figure 13 is the target tracking result of standard Camshift algorithm with obstructions, while Figure 14 is the result of improved Camshift algorithm in the same case.Figure 11
Target tracking result of Camshift algorithm without obstructions (Test 3).Figure 12
Target tracking result of improved Camshift algorithm without obstructions (Test 3).Figure 13
Target tracking result of Camshift algorithm with obstructions (Test 4).Figure 14
Target tracking result of improved Camshift algorithm with obstructions (Test 4).In the above experiment, the results of processing time on four video sequences with two algorithms are shown in Table3.Table 3
The comparison results of processing time on four video sequences with two algorithms.
Test number
Processing time/s
Camshift algorithm
Improved Camshift algorithm
Test 1
4.3518
2.1546s
Test 2
6.9451
3.0845
Test 3
5.9341
2.8458
Test 4
8.0135
4.2141It can be seen from the above experimental results that the improved Camshift algorithm proposed in this paper has better effect than the standard Camshift algorithm in the vehicle tracking with obstructions, improving the efficiency and accuracy of the intelligent robot target tracking algorithm under complex environment. From the comparison results of the processing time of two algorithms in four video sequences, the improved Camshift algorithm proposed in this paper uses relatively less time and is with excellent performance.


## 5. Conclusion

This paper proposes a target tracking algorithm integrating reduced dimension optimal Kalman filtering algorithm based on phase-path volume integral with Camshift algorithm, reduces dimension of Kalman filtering algorithm, fixes the predictive values with the target centroid position as the observation value of the improved Kalman filtering algorithm, and thus takes the optimal estimation for target centroid position. Under the condition of the target with obstructions, it can detect the target centroid position accurately, solve the problem of transient target occlusion, improve the running speed of intelligent robot system, and have higher efficiency and robustness in tracking process.



---

*Source: 4879293-2015-11-22.xml*