A SYSTEM FOR VIDEO OBJECT SEGMENTATION - Video Object Extraction and Representation: Theory and Applications - page 90

where x and y are subproblems/points in the video space.

→ →

Using the algorithm in Figure 4.13, we can find good estimate of a

contour (C) from the path returned from the following function call:

C =DP-Path-Find

where X is the given object center, is a function that returns the

counterclockwise angle from x point with X as the center, x o is a starting

θ

→ →

point along the line θ ( X , x )=0, x o is the point along the line

→ →

θ ( x )=2

→

π -

as → 0 that is adjacent to x o , R ring is defined by Eq. 4.20, and c ring

→

is defined by Eq. 4.19. Since we know, at finite resolution, the number
of points that are adjacent to a given point is bounded by a constant,
this computation is O ( n ) where n is the number of points. Pictorially,
we can see that this DP is a variation of the Viterbi algorithm over a
circularly warped space (see Figure 4.14), i.e., the polar coordinates. In
our surface optimization, we apply the Viterbi algorithm over a Voronoi
Ordered Space.
For Viterbi Rings, we find the set of contours that cover the edges
that follow the heuristics. By iteratively finding the optimal contour,
and removing intensity values from the R ring ( x, y ) that coincide with

→→

the optimal contour, we find a concentric set of contours and this set
of contours are our Viterbi Rings (see Figure 4.15a). This manageable
and relevant subset of edges enables efficient use of our motion boundary
coherence test (see Figure 4.15b).

ITERATIVE VITERBI
Iterative Viterbi applies the contour optimization techniques of the
previous section within an iterative framework for surface optimization.
DP requires a l-D ordering / parameterization of the surface: we must
decompose the 2-D surface into a series of l-D contours along the time
axis. To maintain time smoothness of the surface while decomposing the
problem, we expand our surface optimization over multiple iterations.
We decompose our problem into a set of l-D problems that will be
reintegrated together to form an estimate of 2-D surface. A dynamic pro-
gramming solution requires that the subproblems of the original prob-
lem be ordered, i.e., parametrized and ordered w.r.t. a single variable.
However, a straightforward decomposition does NOT approximate the
surface optimization.