# Robust Object Tracking Based on Simplified Codebook Masked Camshift Algorithm

Authors: Yuanyuan Zhang; Xiaomei Zhao; Fengjiao Li; Jiande Sun; Shuming Jiang; Changying Chen
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Moving targets detection and tracking is an important and basic issue in the field of intelligent video
surveillance. The classical Codebook algorithm is simplified in this paper by introducing the average intensity
into the Codebook model instead of the original minimal and maximal intensities. And a hierarchical matching
method between the current pixel and codeword is also proposed according to the average intensity in the high
and low intensity areas, respectively. Based on the simplified Codebook algorithm, this paper then proposes a
robust object tracking algorithm called Simplified Codebook Masked Camshift algorithm (SCMC algorithm),
which combines the simplified Codebook algorithm and Camshift algorithm together. It is designed to
overcome the sensitiveness of traditional Camshift algorithm to background color interference. It uses
simplified Codebook to detect moving objects, whose result is employed to mask color probability distribution
image, based on which we then use Camshift to predict the centroid and size of these objects. Experiment
results show that the proposed simplified Codebook algorithm simultaneously improves the detection accuracy
and computational efficiency. And they also show that the SCMC algorithm can significantly reduce the
possibility of false convergence and result in a higher correct tracking rate, as compared with the traditional
Camshift algorithm.


---

## Body

## 1. Introduction

Moving object detection and tracking is the basis of object recognition and behavior understanding and has very broad application and research prospects. There are mainly three different categories of object detection algorithms, such as interframe difference methods [1], optical flow methods [2], and background subtraction methods. Background subtraction methods are the most popular ones in real world because of their high detection accuracy and medium computational complexity. Classical background subtraction algorithms include kernel density estimation [3], Gaussian Mixture Background Modeling [4], and Codebook background modelling [5].Codebook algorithm was first proposed in 2004 by Kim et al. [5], and it has been one of the most advanced motion detection methods because of its high memory utilization, high computation efficiency, and strong robustness. Many improvements have been made based on Codebook algorithm. For example, Wu and Peng [6] proposed a modified Codebook algorithm based on spatiotemporal context which improves the detection accuracy by adding the correlation of the spatiotemporal pixels. However, the computational complexity of the whole algorithm has been increased at the same time. Tu et al. [7] made simplifications to accelerate the computational speed by introducing box-based Codebook model in RGB space to represent the matching field of the codewords. However, these simplifications decreased the detection accuracy. Most of the improvements to Codebook can improve either the detection accuracy or computational efficiency, but not both of them.Camshift algorithm is a classical object tracking algorithm. Camshift is evolved from Mean Shift algorithm. It performs tracking according to the color information of an object and has very good real-time performance and high robustness. Mean Shift algorithm was first proposed in 1975 by Fukunaga and Hostetler [8]. Cheng [9] expended the algorithm and enlarged its application range. After that, Comaniciu and Meer [10] successfully applied it to image segmentation and object tracking. Bradski [11] established Camshift algorithm based on Mean Shift, which cannot only predict the centroid position of an object but also adaptively alter the size of an object frame. Currently, the improvement on Camshift algorithm exists in the following aspects: to improve the accuracy by improving the features of a histogram [12–14], to reduce computation time by increasing convergence velocity [15, 16], to increase robustness for objects rotation [17], and to solve the problem of background color interference. The improvement for Camshift algorithm in this paper concentrates on the issue of background color interference. In the literature, Camshift and Kalman combined algorithm [18–20] is easy to fail when object movement is nonlinear. The tracking accuracy of Camshift and interframe difference combined algorithm [21, 22] could be affected by a low performance interframe difference motion detection algorithm.In order to simultaneously improve the detection accuracy or computational efficiency of Codebook algorithm, this paper first proposes a simplified Codebook algorithm. It is called hierarchical matching 5-tuple-based Codebook algorithm which is a modification of the original 6-tuple Codebook algorithm. The average intensity is introduced as a variable into the Codebook model instead of the minimal and maximal intensities. And different matching methods between the current pixel and codeword are adopted according to the average intensity in the high and low intensity areas, respectively. Based on the simplified Codebook algorithm, this paper then proposes a concise and robust object tracking algorithm called Simplified Codebook Masked Camshift algorithm (SCMC algorithm), which combines the simplified Codebook algorithm and Camshift algorithm together. A similar work is proposed by Wang [23], which uses the results of Codebook moving objects detection algorithm to mask the manual initialization searching box. However, our experimental results show that better tracking performance can be obtained when the color probability distribution images were masked by the simplified Codebook algorithm.


## 2. Simplified Codebook Algorithm

Compared with original Codebook algorithm [5], our simplified Codebook algorithm has two improvements: First, maximum and minimum brightness in codeword model are substituted by average brightness. So codeword model is simplified and computation speed is increased. Second, different processing methods of high and low brightness regions are applied to the matching between current pixel and codeword, so detection accuracy is improved and the probability of false detection is reduced in the low brightness region. The simplified Codebook algorithm in this paper is called hierarchical matching 5-tuple-based Codebook algorithm.This section will present how to detect the moving object by the proposed simplified Codebook algorithm. First, we will show process of building a codebook for a specific pixel. Then all the other pixels can repeat the same process to complete the detection for a whole image.


### 2.1. Initialization

We build a codebookC
L (C
L
=
{
c
i
∣
1
≤
i
≤
L
}) containing several codewords for every pixel, where L is the number of codewords. The ith codeword c
i includes two parts: RGB vector v
i
=
(
R
-
i
,
G
-
i
,
B
-
i
) and a 5-tuple au
x
i
=
I
-
i
,
f
i
,
λ
i
,
p
i
,
q
i. The 5-tuple is composed of average brightness I
-
i, codeword accessed frequency f
i, maximal nonrepeatable time interval λ
i, the initial codeword accessed time p
i, and the eventual codeword accessed time q
i. Except for the maximum and minimum brightness replaced by the average brightness I
-
i, all the other elements remain the same as the original Codebook algorithm.


### 2.2. Training Background Model

Assume the firstN frames of the video are used to train background model. For a particular pixel, the sequence of pixel values for training is X
=
{
x
⃑
t
∣
1
≤
t
≤
N
}, where each element x
⃑
t is RGB vector extracted from the tth image frame. Now, we take this pixel as an example to explain the codebook training process:(1)
Build a codebook: we build a codebookC
L for the pixel and initialize it with an empty set (let L
=
0).
(2)
Train the codebook: the following steps are executed circularly whilet changes from 1 to N:
(1)
A new pixel value is read from the sequencex
⃑
t
=
(
R
t
,
G
t
,
B
t
). Brightness is calculated through I
=
R
t
2
+
G
t
2
+
B
t
2.
(2)
Match between the pixel value and the codebook.
Find a codeword matchingx
⃑
t in C
L
=
{
c
i
∣
1
≤
i
≤
L
} based on the following two conditions:
(a)
Color distortion(1)
colordist
x
⃑
t
,
v
⃑
i
=
x
⃑
t
-
p
2
<
ε
c
,
wherev
⃑
i
=
(
R
-
i
,
G
-
i
,
B
-
i
) is the RGB vector of the ith codeword, ε
c is the threshold of color distortion matching, and p is the projection of x
⃑
t on v
⃑
i, and it can be calculated by(2)
p
=
x
⃑
t
·
v
⃑
i
v
⃑
i
=
R
-
i
R
t
+
G
-
i
G
t
+
B
-
i
B
t
R
-
i
2
+
G
-
i
2
+
B
-
i
2
.
(b)
Brightness(3)
brightness
I
,
I
-
i
=
true
,
if
I
low
≤
I
≤
I
hi
false
,
otherwise
,
whereI
-
i is the average brightness of the ith codeword and I
hi and I
low are the upper and lower bounds of brightness matching scope. ε
c, I
hi, and I
low can be calculated by the following formulas:(4)
ε
c
=
χ
·
I
-
i
if
I
-
i
>
ε
ε
c
0
=
χ
·
ε
otherwise
,
I
hi
=
β
·
I
-
i
if
I
-
i
>
ε
I
-
i
+
ε
b
0
otherwise
,
I
low
=
α
·
I
-
i
if
I
-
i
>
ε
I
-
i
-
ε
b
0
otherwise
,
whereε is the threshold to determine whether the current pixel belongs to the low brightness region or not. I
-
i is the average brightness of the ith codeword. χ is a variable used to calculate the threshold of color distortion matching, whose value is between 0 and 1. ε
c
0 is a constant threshold of color distortion matching in low brightness region. β is a variable used to calculate the ratio of the upper bound of brightness matching and average brightness in high brightness region. α is a variable used to calculate the ratio of the lower bound of brightness matching and average brightness in high brightness region. ε
b
0 is half of the brightness matching range when the brightness of the current pixel is lower than ε. ε
c
0 and ε
b
0 jointly guarantee the ranges of color distortion and brightness matching are not too small in low brightness area to avoid the occurrence of false detection.
(3)
IfL
=
0 or there is no matching codeword, then let L
=
L
+
1 and create a new codeword c
L
(
v
⃑
L
,
au
x
L
), where the color vector is v
⃑
L
=
x
⃑
t
=
(
R
t
,
G
t
,
B
t
) and the 5-tuple is au
x
L
=
I
,
1
,
t
-
1
,
t
,
t.
(4)
Otherwise, update the matched codewordc
i
(
v
⃑
i
,
au
x
i
) if x
⃑
t matches c
i
(
v
⃑
i
,
au
x
i
). Update the color vector by(5)
v
⃑
i
=
f
i
·
R
-
i
+
R
t
f
i
+
1
,
f
i
·
G
-
i
+
G
t
f
i
+
1
,
f
i
·
B
-
i
+
B
t
f
i
+
1
,
and also update the 5-tuple by(6)
au
x
i
=
f
i
·
I
-
i
+
I
f
i
+
1
,
f
i
+
1
,
max
⁡
λ
i
,
t
-
q
i
,
p
i
,
t
.
(3)
Regulateλ
i for every codeword c
i, and let(7)
λ
i
=
max
⁡
λ
i
,
N
-
q
i
+
p
i
-
1
.
(4)
Delete the nonbackground codeword. Assume the probability of background occurrence is bigger than 50%. LetM denote the background model which is the codebook after temporal filtering step. Specific operations can be expressed as the following formula:(8)
M
=
c
m
∣
c
m
∈
C
L
∧
λ
m
≤
T
M
;
generally,T
M
=
N
/
2. M is the codeword set describing the background, where c
m is the mth codeword in C
L. λ
m is the maximal nonrepeatable time interval of the 5-tuple in c
m.


### 2.3. Foreground Detection

We match current pixel with a codeword by the same method as the training codebook. If matching exists, we update the codeword and take the current pixel as background. Otherwise, we take it as foreground.


## 2.1. Initialization

We build a codebookC
L (C
L
=
{
c
i
∣
1
≤
i
≤
L
}) containing several codewords for every pixel, where L is the number of codewords. The ith codeword c
i includes two parts: RGB vector v
i
=
(
R
-
i
,
G
-
i
,
B
-
i
) and a 5-tuple au
x
i
=
I
-
i
,
f
i
,
λ
i
,
p
i
,
q
i. The 5-tuple is composed of average brightness I
-
i, codeword accessed frequency f
i, maximal nonrepeatable time interval λ
i, the initial codeword accessed time p
i, and the eventual codeword accessed time q
i. Except for the maximum and minimum brightness replaced by the average brightness I
-
i, all the other elements remain the same as the original Codebook algorithm.


## 2.2. Training Background Model

Assume the firstN frames of the video are used to train background model. For a particular pixel, the sequence of pixel values for training is X
=
{
x
⃑
t
∣
1
≤
t
≤
N
}, where each element x
⃑
t is RGB vector extracted from the tth image frame. Now, we take this pixel as an example to explain the codebook training process:(1)
Build a codebook: we build a codebookC
L for the pixel and initialize it with an empty set (let L
=
0).
(2)
Train the codebook: the following steps are executed circularly whilet changes from 1 to N:
(1)
A new pixel value is read from the sequencex
⃑
t
=
(
R
t
,
G
t
,
B
t
). Brightness is calculated through I
=
R
t
2
+
G
t
2
+
B
t
2.
(2)
Match between the pixel value and the codebook.
Find a codeword matchingx
⃑
t in C
L
=
{
c
i
∣
1
≤
i
≤
L
} based on the following two conditions:
(a)
Color distortion(1)
colordist
x
⃑
t
,
v
⃑
i
=
x
⃑
t
-
p
2
<
ε
c
,
wherev
⃑
i
=
(
R
-
i
,
G
-
i
,
B
-
i
) is the RGB vector of the ith codeword, ε
c is the threshold of color distortion matching, and p is the projection of x
⃑
t on v
⃑
i, and it can be calculated by(2)
p
=
x
⃑
t
·
v
⃑
i
v
⃑
i
=
R
-
i
R
t
+
G
-
i
G
t
+
B
-
i
B
t
R
-
i
2
+
G
-
i
2
+
B
-
i
2
.
(b)
Brightness(3)
brightness
I
,
I
-
i
=
true
,
if
I
low
≤
I
≤
I
hi
false
,
otherwise
,
whereI
-
i is the average brightness of the ith codeword and I
hi and I
low are the upper and lower bounds of brightness matching scope. ε
c, I
hi, and I
low can be calculated by the following formulas:(4)
ε
c
=
χ
·
I
-
i
if
I
-
i
>
ε
ε
c
0
=
χ
·
ε
otherwise
,
I
hi
=
β
·
I
-
i
if
I
-
i
>
ε
I
-
i
+
ε
b
0
otherwise
,
I
low
=
α
·
I
-
i
if
I
-
i
>
ε
I
-
i
-
ε
b
0
otherwise
,
whereε is the threshold to determine whether the current pixel belongs to the low brightness region or not. I
-
i is the average brightness of the ith codeword. χ is a variable used to calculate the threshold of color distortion matching, whose value is between 0 and 1. ε
c
0 is a constant threshold of color distortion matching in low brightness region. β is a variable used to calculate the ratio of the upper bound of brightness matching and average brightness in high brightness region. α is a variable used to calculate the ratio of the lower bound of brightness matching and average brightness in high brightness region. ε
b
0 is half of the brightness matching range when the brightness of the current pixel is lower than ε. ε
c
0 and ε
b
0 jointly guarantee the ranges of color distortion and brightness matching are not too small in low brightness area to avoid the occurrence of false detection.
(3)
IfL
=
0 or there is no matching codeword, then let L
=
L
+
1 and create a new codeword c
L
(
v
⃑
L
,
au
x
L
), where the color vector is v
⃑
L
=
x
⃑
t
=
(
R
t
,
G
t
,
B
t
) and the 5-tuple is au
x
L
=
I
,
1
,
t
-
1
,
t
,
t.
(4)
Otherwise, update the matched codewordc
i
(
v
⃑
i
,
au
x
i
) if x
⃑
t matches c
i
(
v
⃑
i
,
au
x
i
). Update the color vector by(5)
v
⃑
i
=
f
i
·
R
-
i
+
R
t
f
i
+
1
,
f
i
·
G
-
i
+
G
t
f
i
+
1
,
f
i
·
B
-
i
+
B
t
f
i
+
1
,
and also update the 5-tuple by(6)
au
x
i
=
f
i
·
I
-
i
+
I
f
i
+
1
,
f
i
+
1
,
max
⁡
λ
i
,
t
-
q
i
,
p
i
,
t
.
(3)
Regulateλ
i for every codeword c
i, and let(7)
λ
i
=
max
⁡
λ
i
,
N
-
q
i
+
p
i
-
1
.
(4)
Delete the nonbackground codeword. Assume the probability of background occurrence is bigger than 50%. LetM denote the background model which is the codebook after temporal filtering step. Specific operations can be expressed as the following formula:(8)
M
=
c
m
∣
c
m
∈
C
L
∧
λ
m
≤
T
M
;
generally,T
M
=
N
/
2. M is the codeword set describing the background, where c
m is the mth codeword in C
L. λ
m is the maximal nonrepeatable time interval of the 5-tuple in c
m.


## 2.3. Foreground Detection

We match current pixel with a codeword by the same method as the training codebook. If matching exists, we update the codeword and take the current pixel as background. Otherwise, we take it as foreground.


## 3. Classical Camshift Algorithm

The original Camshift algorithm [11] takes the color histogram of an object as its characteristic model based on its color information. Video frame images are then changed into color probability distribution images. The centroid of the object is searched and the size of the object box is predicted on these images.The implementation of the classical Camshift algorithm can be depicted as follows:(1)
Initialize the position of the centroid and the size of the bounding box of the object.
(2)
Compute the color histogram of the bounding box.
(3)
Compute the color probability distribution image for the current frame.
(4)
Predict the position of the centroid with Mean Shift algorithm.
(5)
Predict the size of the bounding box.The original Camshift algorithm can easily converge the bounding box to an object position, when there are significant differences between the object color and background color. Under such circumstance, pixel value of the object area is much higher than those of background on the color probability distribution image. However, when the object color is similar to the background color, the pixel value of the object area is no longer distinctive to those of background on the color probability distribution image. The algorithm will not guarantee that it will correctly converge the bounding box to an object position because it is color sensitive. This phenomenon is shown in Figures1 and 2, respectively.Figure 1
Tracking results of Camshift when obvious difference exists in object color and background color.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)Figure 2
Tracking results of Camshift when no obvious difference exists in object color and background color.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)The video image sequences in Figures1 and 2 are downloaded from the ITEA CANDELA project [24]. Figures 1(a)–1(d) and 2(a)–2(d) are color probability distribution images, and Figures 1(e)–1(h) and 2(e)–2(h) are tracking result images. From those figures, we can easily see that the original Camshift algorithm can track effectively when the object is significantly different to the background color. However, if the object color is similar to the background color, the algorithm may fail, just like Figure 2(h) shows.


## 4. Simplified Codebook Masked Camshift Algorithm

To overcome the background interference problem of Camshift algorithm, this paper proposes a SCMC algorithm, which is short for Simplified Codebook Masked Camshift algorithm. SCMC algorithm combines the simplified Codebook algorithm and the Camshift algorithm together. The detection result of simplified Codebook is utilized to mask the color probability distribution images. The main purpose is to filter out the background interference on tracking.The implementation process of SCMC algorithm can be summarized as follows:(1)
Detect moving objects with simplified Codebook algorithm.
(2)
Perform median filtering to the detection results to filter out noise and make the object connectable.
(3)
Compute the color probability distribution image for the current frame.
(4)
Mask the color probability distribution images with the processed foreground images in step (2).Pixel values in background area are assigned as 0, and the pixel values in foreground area remain unchanged to guarantee Camshift algorithm converges only to the area of the moving object. The masking procedure of color probability distribution images is shown in Figure3.(5)
Search the centroid of the object with Camshift algorithm and predict the size of the bounding box.Figure 3
Illustration of the masking procedure of a color probability distribution image.The whole process of the proposed CMC algorithm is depicted in the flowchart of Figure4.Figure 4
Flowchart of the proposed SCMC algorithm.


## 5. Experimental Results and Analysis

The experiments were carried out on an ordinary PC with configuration of Intel(R) Core(TM) i3, 3.0 GB RAM, and 64-bit Windows 7 operating system. The programming environment is Microsoft Visual Studio 2010 and OpenCV 2.4.4.


### 5.1. Results of Simplified Codebook Algorithm

We use five different videos to illustrate the detection performance of the proposed simplified Codebook algorithm. Video #1 is captured by us. Video #2 is the famous video called Waving Tree [25]. Video #3 is chosen from the project of PETS2000 [26]. Videos #4 and #5 are selected from the ITEA CANDELA project [24].The detection results of Video #1 and Video #2 using the proposed simplified Codebook algorithm are depicted in Figure5. In order to show the superiority of the proposed algorithm, we also performed comparisons with several other motion detection algorithms such as Gaussian Mixture Model and original Codebook model. The real foreground extracted by hand is also depicted in Figure 5.Figure 5
Object detection results of Video #1 and Video #2 (each row).
(a)
Video frame
(b)
Real foreground
(c)
Gaussian Mixture Model
(d)
Original Codebook model
(e)
Simplified Codebook modelFrom Figure5, we can see that detection results of the proposed simplified Codebook algorithm are better than the Gaussian Mixture Model and the original Codebook model. The original Codebook model may lead to false detection in the region with low brightness. The simplified Codebook algorithm can reduce the influence of low brightness area by using the method of hierarchical matching.The computational difference between the simplified Codebook algorithm and the original Codebook model mainly lies in the process of calculating direct parameters from indirect parameters. The original Codebook model includes 2 multiplications, 1 division, and 1 subtraction, while the simplified Codebook algorithm includes 1 division and 3 multiplications, or 2 divisions and 1 addition. It is more likely to save a lot of operations by using the simplified Codebook algorithm especially when the average brightness is lower thanε. The detection speed of the simplified Codebook algorithm to Video #1 is 47 ms/frame, while detection speed of the original Codebook model is 62 ms/frame.More experimental results of different detection algorithms of Video #3, Video #4, and Video #5 are given in Figure6. From these figures, we can also see the superiority of the proposed simplified Codebook algorithm.Figure 6
Object detection results of Video #3, Video #4, and Video #5 (each row).
(a)
Video frame
(b)
Gaussian Mixture Model
(c)
Original Codebook model
(d)
Simplified Codebook modelIn order to illustrate the validation performance of the proposed simplified Codebook algorithm, we draw the ROC curves of three different algorithms in Figure7. In this figure, the false positive rate is defined to be the ratio of amount number of background pixels which are falsely detected as foreground pixels to amount number of background pixels, and true positive rate is defined to be the ratio of amount number of foreground pixels which are correctly detected as foreground pixels to amount number of foreground pixels. The validation performance is better when the area under ROC curve is larger.Figure 7
ROC curves of three different algorithms.


### 5.2. Results of SCMC Algorithm

Here, we also use several videos to test the tracking performance of the proposed SCMC algorithm. Video #3, Video #4, Video #5, and Video #6 [27] are used in this part. First, we show the tracking results of a white car in Video #4 using the original Camshift algorithm in Figure 8. Figure 8(a) shows original color probability distribution images, and Figure 8(b) shows the corresponding tracking result images of the original Camshift algorithm. From Figure 8, we can easily see that serious tracking error occurs when background color and object color are slightly similar using the original Camshift algorithm.Figure 8
Tracking results of a red car in the 165th, 173rd, 181st, and 189th frames in Video #4.
(a)
Original color probability distribution images
(b)
Tracking result images of the original Camshift algorithmThen we show the tracking results of the same object in Video #4 using the proposed SCMC algorithm in Figure9. Figure 9(a) shows color probability distribution images masked by the moving object detection result using the simplified Codebook algorithm. Figure 9(b) shows the corresponding tracking result images of the proposed SCMC algorithm. In this figure, most of the background information was filtered out by the masked color probability distribution image. So the probability of false convergence is greatly reduced when using the SCMC algorithm, and higher tracking accuracy is obtained.Figure 9
Tracking results of a red car in the 165th, 173rd, 181st, and 189th frames in Video #4 using the proposed SCMC algorithm.
(a)
Color probability distribution images of masked simplified Codebook algorithm
(b)
Tracking result images of the proposed SCMC algorithmMore comparisons about the tracking performance between the original Camshift algorithm and the proposed SCMC algorithm are shown in Figures10, 11, and 12. We also give the tracking results of original Codebook with Camshift algorithm and Compressive Tracking algorithm [28] in these figures. From these figures, we can see that the tracking performance can be easily influenced by the background color when using the original Camshift algorithm. However, most of the background information has been filtered out after using the SCMC algorithm. As a consequence, it largely reduces the possibility of false convergence. So better tracking performance is obtained. The tracking results are also better than those of original Codebook with Camshift algorithm and Compressive Tracking algorithm.Figure 10
Tracking results of a red car in the 70th, 85th, 100th, and 115th frames in Video #3.
(a)
Original Camshift algorithm
(b)
The original Codebook + Camshift algorithm
(c)
Compressive Tracking algorithm
(d)
The proposed SCMC algorithmFigure 11
Tracking results of a black car in the 205th, 210th, 215th, and 220th frames in Video #3.
(a)
Original Camshift algorithm
(b)
The original Codebook + Camshift algorithm
(c)
Compressive Tracking algorithm
(d)
The proposed SCMC algorithmFigure 12
Tracking results of a crimson car in the 50th, 60th, 70th, and 80th frames in Video #4.
(a)
Original Camshift algorithm
(b)
The original Codebook + Camshift algorithm
(c)
Compressive Tracking algorithm
(d)
The proposed SCMC algorithmIn Figure13, we show the tracking results of a person using 4 different algorithms. As you can see in this figure, the tracking performance of the proposed SCMC algorithm is also better than those of original Camshift algorithm and original Codebook with Camshift algorithm. In Figure 13(c), one of the targets is missing by using the method of incremental learning for robust visual tracking. However, the person can be correctly tracked by the proposed SCMC algorithm.Figure 13
Tracking results of a person in the 181st, 191st, 254th, and 349th frames in Video #6.
(a)
Original Camshift algorithm
(b)
The original Codebook + Camshift algorithm
(c)
Incremental learning for robust visual tracking
(d)
The proposed SCMC algorithmIn order to illustrate the superiority of the proposed SCMC algorithm, we perform comparison with some state-of-the-art object tracking algorithm such as original Camshift algorithm, CT (Compressive Tracking) algorithm [28], and TLD algorithm [29] in Table 1. The number of correct tracking frames of some cars in Video #3, Video #4, and Video #5 is summarized in this table. We consider correct tracking if the center of the bounding box falls into the object area.Table 1
Comparison of tracking results for different tracking algorithms.
Objects in videos
First frame of object shows
Frame number of object shows
Number of correct tracking frames
Original Camshift [11]
TLD [29]
CT [28]
Proposed SCMC
Red car in Video #3
65
89
6
89
58
89
Black car in Video #3
193
151
13
151
151
151
White car in Video #3
403
61
0
61
53
61
Crimson car in Video #4
47
98
17
25
61
98
Black car 1 in Video #4
69
113
67
34
61
113
White car 1 in Video #4
97
113
53
55
10
53
Gray car in Video #4
139
30
27
30
30
16
White car 2 in Video #4
162
30
17
1
30
30
Black car 2 in Video #4
192
37
37
31
37
37
Red car in Video #4
285
79
7
0
79
79
Black car in Video #5
36
20
20
20
13
20
Gray car in Video #5
106
26
26
26
18
26
Red car in Video #5
133
25
22
22
22
25
Blue car in Video #5
420
29
29
28
29
29
Number of total frames (901)
341
573
652
827
Correct tracking rate
37.8%
63.6%
72.4%
91.8%From Table1, we discover that the proposed SCMC algorithm can correctly track most objects in Video #3, Video #4, and Video #5, and the tracking performance is significantly superior to the original Camshift algorithm. Moreover, the correct tracking rate of SCMC is 28.2% higher than that of TLD and is 19.4% higher than CT. SCMC algorithm is therefore superior to TLD and CT algorithms when the camera is stable.Notice that the tracking performance of the proposed SCMC algorithm for the gray car in Video #3 is worse than that of all the other algorithms in Table1. This special case is shown in Figure 14, too. The reason is that a black car approaches the object and then leaves it in the tracking progress, which causes the false tracking of SCMC algorithm. By contrast, gray road information near the gray car is not filtered out for Camshift algorithm, which is a benefit to the convergence of the centroid of the object on the gray car. One possible disadvantage of the proposed SCMC algorithm is that the tracking performance may be affected if there is another moving object with similar color in the video, even if the interference of the background has already been restrained.Figure 14
Tracking results of a gray car in Video #3 using SCMC algorithm; the 144th, 149th, 154th, and 159th frames are shown here.


## 5.1. Results of Simplified Codebook Algorithm

We use five different videos to illustrate the detection performance of the proposed simplified Codebook algorithm. Video #1 is captured by us. Video #2 is the famous video called Waving Tree [25]. Video #3 is chosen from the project of PETS2000 [26]. Videos #4 and #5 are selected from the ITEA CANDELA project [24].The detection results of Video #1 and Video #2 using the proposed simplified Codebook algorithm are depicted in Figure5. In order to show the superiority of the proposed algorithm, we also performed comparisons with several other motion detection algorithms such as Gaussian Mixture Model and original Codebook model. The real foreground extracted by hand is also depicted in Figure 5.Figure 5
Object detection results of Video #1 and Video #2 (each row).
(a)
Video frame
(b)
Real foreground
(c)
Gaussian Mixture Model
(d)
Original Codebook model
(e)
Simplified Codebook modelFrom Figure5, we can see that detection results of the proposed simplified Codebook algorithm are better than the Gaussian Mixture Model and the original Codebook model. The original Codebook model may lead to false detection in the region with low brightness. The simplified Codebook algorithm can reduce the influence of low brightness area by using the method of hierarchical matching.The computational difference between the simplified Codebook algorithm and the original Codebook model mainly lies in the process of calculating direct parameters from indirect parameters. The original Codebook model includes 2 multiplications, 1 division, and 1 subtraction, while the simplified Codebook algorithm includes 1 division and 3 multiplications, or 2 divisions and 1 addition. It is more likely to save a lot of operations by using the simplified Codebook algorithm especially when the average brightness is lower thanε. The detection speed of the simplified Codebook algorithm to Video #1 is 47 ms/frame, while detection speed of the original Codebook model is 62 ms/frame.More experimental results of different detection algorithms of Video #3, Video #4, and Video #5 are given in Figure6. From these figures, we can also see the superiority of the proposed simplified Codebook algorithm.Figure 6
Object detection results of Video #3, Video #4, and Video #5 (each row).
(a)
Video frame
(b)
Gaussian Mixture Model
(c)
Original Codebook model
(d)
Simplified Codebook modelIn order to illustrate the validation performance of the proposed simplified Codebook algorithm, we draw the ROC curves of three different algorithms in Figure7. In this figure, the false positive rate is defined to be the ratio of amount number of background pixels which are falsely detected as foreground pixels to amount number of background pixels, and true positive rate is defined to be the ratio of amount number of foreground pixels which are correctly detected as foreground pixels to amount number of foreground pixels. The validation performance is better when the area under ROC curve is larger.Figure 7
ROC curves of three different algorithms.


## 5.2. Results of SCMC Algorithm

Here, we also use several videos to test the tracking performance of the proposed SCMC algorithm. Video #3, Video #4, Video #5, and Video #6 [27] are used in this part. First, we show the tracking results of a white car in Video #4 using the original Camshift algorithm in Figure 8. Figure 8(a) shows original color probability distribution images, and Figure 8(b) shows the corresponding tracking result images of the original Camshift algorithm. From Figure 8, we can easily see that serious tracking error occurs when background color and object color are slightly similar using the original Camshift algorithm.Figure 8
Tracking results of a red car in the 165th, 173rd, 181st, and 189th frames in Video #4.
(a)
Original color probability distribution images
(b)
Tracking result images of the original Camshift algorithmThen we show the tracking results of the same object in Video #4 using the proposed SCMC algorithm in Figure9. Figure 9(a) shows color probability distribution images masked by the moving object detection result using the simplified Codebook algorithm. Figure 9(b) shows the corresponding tracking result images of the proposed SCMC algorithm. In this figure, most of the background information was filtered out by the masked color probability distribution image. So the probability of false convergence is greatly reduced when using the SCMC algorithm, and higher tracking accuracy is obtained.Figure 9
Tracking results of a red car in the 165th, 173rd, 181st, and 189th frames in Video #4 using the proposed SCMC algorithm.
(a)
Color probability distribution images of masked simplified Codebook algorithm
(b)
Tracking result images of the proposed SCMC algorithmMore comparisons about the tracking performance between the original Camshift algorithm and the proposed SCMC algorithm are shown in Figures10, 11, and 12. We also give the tracking results of original Codebook with Camshift algorithm and Compressive Tracking algorithm [28] in these figures. From these figures, we can see that the tracking performance can be easily influenced by the background color when using the original Camshift algorithm. However, most of the background information has been filtered out after using the SCMC algorithm. As a consequence, it largely reduces the possibility of false convergence. So better tracking performance is obtained. The tracking results are also better than those of original Codebook with Camshift algorithm and Compressive Tracking algorithm.Figure 10
Tracking results of a red car in the 70th, 85th, 100th, and 115th frames in Video #3.
(a)
Original Camshift algorithm
(b)
The original Codebook + Camshift algorithm
(c)
Compressive Tracking algorithm
(d)
The proposed SCMC algorithmFigure 11
Tracking results of a black car in the 205th, 210th, 215th, and 220th frames in Video #3.
(a)
Original Camshift algorithm
(b)
The original Codebook + Camshift algorithm
(c)
Compressive Tracking algorithm
(d)
The proposed SCMC algorithmFigure 12
Tracking results of a crimson car in the 50th, 60th, 70th, and 80th frames in Video #4.
(a)
Original Camshift algorithm
(b)
The original Codebook + Camshift algorithm
(c)
Compressive Tracking algorithm
(d)
The proposed SCMC algorithmIn Figure13, we show the tracking results of a person using 4 different algorithms. As you can see in this figure, the tracking performance of the proposed SCMC algorithm is also better than those of original Camshift algorithm and original Codebook with Camshift algorithm. In Figure 13(c), one of the targets is missing by using the method of incremental learning for robust visual tracking. However, the person can be correctly tracked by the proposed SCMC algorithm.Figure 13
Tracking results of a person in the 181st, 191st, 254th, and 349th frames in Video #6.
(a)
Original Camshift algorithm
(b)
The original Codebook + Camshift algorithm
(c)
Incremental learning for robust visual tracking
(d)
The proposed SCMC algorithmIn order to illustrate the superiority of the proposed SCMC algorithm, we perform comparison with some state-of-the-art object tracking algorithm such as original Camshift algorithm, CT (Compressive Tracking) algorithm [28], and TLD algorithm [29] in Table 1. The number of correct tracking frames of some cars in Video #3, Video #4, and Video #5 is summarized in this table. We consider correct tracking if the center of the bounding box falls into the object area.Table 1
Comparison of tracking results for different tracking algorithms.
Objects in videos
First frame of object shows
Frame number of object shows
Number of correct tracking frames
Original Camshift [11]
TLD [29]
CT [28]
Proposed SCMC
Red car in Video #3
65
89
6
89
58
89
Black car in Video #3
193
151
13
151
151
151
White car in Video #3
403
61
0
61
53
61
Crimson car in Video #4
47
98
17
25
61
98
Black car 1 in Video #4
69
113
67
34
61
113
White car 1 in Video #4
97
113
53
55
10
53
Gray car in Video #4
139
30
27
30
30
16
White car 2 in Video #4
162
30
17
1
30
30
Black car 2 in Video #4
192
37
37
31
37
37
Red car in Video #4
285
79
7
0
79
79
Black car in Video #5
36
20
20
20
13
20
Gray car in Video #5
106
26
26
26
18
26
Red car in Video #5
133
25
22
22
22
25
Blue car in Video #5
420
29
29
28
29
29
Number of total frames (901)
341
573
652
827
Correct tracking rate
37.8%
63.6%
72.4%
91.8%From Table1, we discover that the proposed SCMC algorithm can correctly track most objects in Video #3, Video #4, and Video #5, and the tracking performance is significantly superior to the original Camshift algorithm. Moreover, the correct tracking rate of SCMC is 28.2% higher than that of TLD and is 19.4% higher than CT. SCMC algorithm is therefore superior to TLD and CT algorithms when the camera is stable.Notice that the tracking performance of the proposed SCMC algorithm for the gray car in Video #3 is worse than that of all the other algorithms in Table1. This special case is shown in Figure 14, too. The reason is that a black car approaches the object and then leaves it in the tracking progress, which causes the false tracking of SCMC algorithm. By contrast, gray road information near the gray car is not filtered out for Camshift algorithm, which is a benefit to the convergence of the centroid of the object on the gray car. One possible disadvantage of the proposed SCMC algorithm is that the tracking performance may be affected if there is another moving object with similar color in the video, even if the interference of the background has already been restrained.Figure 14
Tracking results of a gray car in Video #3 using SCMC algorithm; the 144th, 149th, 154th, and 159th frames are shown here.


## 6. Conclusion

This paper first proposes a simplified Codebook algorithm called hierarchical matching 5-tuple-based Codebook algorithm. The average intensity is introduced as a variable into the Codebook model instead of the minimal and maximal intensities. And different matching methods between the current pixel and codeword are adopted according to the average intensity in the high and low intensity areas, respectively. Based on the simplified Codebook algorithm, the proposed SCMC algorithm masks color probability distribution images with moving objects detection results, in which the pixel values in the background are configured as 0 to filter out the interference of background on Camshift tracking. The probability of false convergence is therefore greatly reduced. The algorithm has higher correct tracking rate than classical Camshift algorithm. Moreover, its correct tracking rate is superior to TLD and CT if the position of the camera is stable. However, it also has some disadvantages: (1) it may not perform tracking if background rapidly changes and (2) it may track a false object if two objects have quite similar colors. To solve the first disadvantage, future improvement may be the construction of more robust background modeling to implement foreground detection for rapidly changing background. For the second disadvantage, we can include some texture information into the model to increase the distinction between different objects through the improvement of characters.



---

*Source: 376494-2015-07-30.xml*