Forward-Backward Error: Automatic Detection of Tracking Failures
Zdenek Kalal
CVSSP, UK
z.kalal@surrey.ac.uk
Krystian Mikolajczyk
CVSSP, UK
k.mikolajczyk@surrey.ac.uk
Jiri Matas
CMP, Czech Republic
matas@cmp.felk.cvut.cz
Abstract
This paper proposes a novel method for tracking fail-
ure detection. The detection is based on the Forward-
Backward error, i.e. the tracking is performed forward
and backward in time and the discrepancies between
these two trajectories are measured. We demonstrate
that the proposed error enables reliable detection of
tracking failures and selection of reliable trajectories
in video sequences. We demonstrate that the approach
is complementary to commonly used normalized cross-
correlation (NCC). Based on the error, we propose a
novel object tracker called Median Flow. State-of-the-
art performance is achieved on challenging benchmark
video sequences which include non-rigid objects.
1. Introduction
Point tracking is a common computer vision task:
given a point location in time t, the goal is to estimate its
location in time t + 1. In practice, tracking often faces
with a problem where the points dramatically change
appearance or disappear from the camera view. Under
such conditions, tracking often results in failures. We
study the problem of failure detection and propose a
novel method that enables any tracker to self-evaluate
its reliability.
The proposed method is based on so called forward-
backward consistency assumption that correct tracking
should be independent of the direction of time-flow. Al-
gorithmically, the assumption is exploited as follows.
First, a tracker produces a trajectory by tracking the
point forward in time. Second, the point location in the
last frame initializes a validation trajectory. The vali-
dation trajectory is obtained by backward tracking from
the last frame to the first one. Third, the two trajectories
are compared and if they differ significantly, the for-
ward trajectory is considered as incorrect. Fig. 1 (top)
illustrates the method when tracking a point between
two images (basic trajectory). Point no. 1 is visible in
both images and the tracker is able to localize it cor-
I
t
I
t+k
^
x
t
x
t
backward trajectory
forward trajectory
I
t+1
. . .
x
t+1
forward-backward
error
x
t+k
2
1
^
x
t+1
Figure 1. The Forward-Backward error penalizes in-
consistent trajectories. Point 1 is visible in both im-
ages, tracker works consistently forward and back-
ward. Point 2 is occluded in the second image, for-
ward and backward trajectories are inconsistent.
rectly. Tracking this point forward or backward results
in identical trajectories. On the other hand, point no.
2 is not visible in the right image and the tracker lo-
calizes a different point. Tracking this point backward
ends in a different location then the original one. The
inconsistency can be easily identified and as we show
in the experimental section, it is highly correlated with
real tracking failures.
A commonly used approach to detect tracking fail-
ures is to describe the tracked point by a surrounding
patch R which is compared from time t to t + 1 us-
ing sum-of-square differences (SSD) [3, 9]. This differ-
ential error enables detection of failures caused by oc-
clusion or rapid movements, but does not detect slowly
drifting trajectories. The detection of a drift can be ap-
proached by defining an absolute error, such as a com-
parison between the current patch and affine warps of
the initial appearance [11]. This method is applicable
only to planar targets. Recently, a general method for
assessing the tracking performance was proposed [13],
which is based on a similar idea to the one explored in
International Conference on Pattern Recognition, 23-26 August, 2010, Istambul, Turkey