This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
LI et al.: VISUAL TRACKING VIA RANDOM WALKS ON GRAPH MODEL 3
Fig. 2. Pipeline of our method. (a) Input frame at time t. (b) Search region after oversegmentation. (c) Proposed random walks on two graph models.
(d) Proposed structural model. (e) Final confidence map.
states and absorbing states. Given an absorbing chain with
M
a
absorbing states and M
t
transient states, we renumber the
states so that the transient states come first. Then the transition
matrix P has the following canonical form:
P =
QR
0I
(5)
where Q ∈ [0, 1]
M
t
×M
t
contains the transition probability
between any pair of the transient states; R ∈ [0, 1]
M
t
×M
a
con-
tains the probability of reaching any absorbing state from any
transient state; 0 is the M
a
× M
t
zero matrix; and I is the
M
a
×M
a
identity matrix. Starting at any transient state, the ran-
dom walk process on an absorbing Markov chain will always
be absorbed. The fundamental matrix of an absorbing Markov
chain is defined as
N =
(
I − Q
)
−1
(6)
where N = [N
ij
]
M
t
×M
t
; N
ij
denotes the expected number of
times that the process stays in transient state S
j
after starting
from transient state S
i
; and
j
N
ij
is the absorbing time of
node i, i.e., the expected number of times before the chain is
absorbed (into any absorbing state), given that the chain starts
in transient state S
i
. The absorbing time for every transient
state can then be computed by
τ = N1 (7)
where τ = [τ
1
,τ
2
,...,τ
M
t
]
; τ
i
is the absorbing time for
transient state S
i
; 1 is a column vector whose entries are
all ones.
III. T
RACKING VIA RANDOM WALKS ON GRAPH MODELS
The pipeline of our method is illustrated in Fig. 2. When
a new frame arrives, we first segment the search region
1
into n superpixels [see Fig. 2(b)]. Then, we construct two
graph models and perform Markov random walks on them
to compute a confidence map which measures the probabil-
ity of each superpixel belonging to the target area. In order
1
The search region is a square area centered at X
c
t
, the target location of
the last frame. The side length of the search region is set to λ
s
·(S(X
t
))
(1/2)
,
where S(X
t
) represents the area of target area X
t
. The parameter λ
s
controls
the size of this surrounding region and is set to two in experiments.
Fig. 3. Graph model G
e
(V
e
, E
e
) based on ergodic Markov chain. Each
rectangle represents a node. The green candidate nodes and white candidate
nodes denote target nodes and background nodes, respectively. The template
nodes are superpixels in the target region of the first frame.
to make the confidence map more robust, a structural model
is constructed to exploit structural information between object
parts. Finally, the target is located by maximum a posteriori
estimate.
A. Graph Construction
Two kinds of directed graphs, G
e
(V
e
, E
e
) and G
a
(V
a
, E
a
),
are constructed with superpixels as nodes and the relation-
ships between connected nodes as edges. The weight of an
edge indicates how closely related the corresponding two con-
nected nodes are, that is, the random walker will transfer from
node i to j with a high probability if the weight w
ij
of the
directed edge e
ij
is large.
1) Graph Model Based on Ergodic Markov Chain: As
shown in Fig. 3, the nodes of G
e
(V
e
, E
e
) are composed of m
template nodes denoted by T = [T
1
,...,T
m
] and n candidate
nodes denoted by C = [C
1
,...,C
n
], where T
i
and C
j
are the
mean CIE Lab color values of the ith template node and the
jth candidate node, respectively.
2
The template nodes represent
superpixels in the target area of the first frame, while candidate
nodes represent superpixels in the search region of the current
frame. Each template node is connected to the rest nodes in
the graph, including other template nodes and all the candidate
nodes. Each candidate node is connected to its neighboring
candidate nodes and all the template nodes. The weight of the
2
We also use T
i
and C
j
to denote the ith template node and the jth candidate
node in this paper.