Globally Optimal Energy Minimization Techniques - Bezier and Splines in Image Processing and Machine Vision - page 209

matrix is determined by the curvature constraints and the observation matrix
is determined by the gradient image.
A simple way to find shortest paths on the linear trellis that corresponds
to the closed contours in the image domain is to replicate the m nodes. Specif-
ically, we unwrap the circular domain such that the last column of nodes in
the trellis is a copy of the first column. Then if there are m such nodes in a
column, we would need to evaluate each of the m paths, starting and finishing
on the same node i 1]. This would require m evaluations of the

Viterbi algorithm, as described in Section 9.5. So we use the two-pass method
of Gunn and Nixon [71] based on the midpoint heuristic to find the minimum
energy.
Although this heuristic works very well in practice, in theory there are
clearly situations where it could fail to find the optimal solution.

∈ [0 ...M −

Circular Shortest Path Algorithm (CSP)

Appleton and Sun [8] investigated this general problem of optimal circular
shortest paths to address the theoretical deficiencies of the midpoint heuris-
tic. Their circular shortest path algorithm is guaranteed to find the shortest
circular path and uses a branch and bound technique [175, 99] to eciently
locate it.
The need for circular shortest paths arises when the search space is nat-
urally periodic. Here we must satisfy the constraint that the end points of
the shortest path must be connected in the periodic extension of the trellis.
This constraint creates a cyclic dependency in the computation of the path
cost, which prevents us from applying the standard shortest path algorithms
of Section 9.5 based on dynamic programming. However, this dependency is
quite simply overcome by periodically extending the trellis as follows.
We perform a rectangular to polar mapping to convert the circular search
space into a linear one as before. However, in this case, the column at the cut
point is replicated as the last column to provide a periodic extension. In other
words, a circular search space with N nodes is represented by a linear trellis
of length N + 1 where the last column is a replica of the first. Then a contour
is circular if and only if the row index of the first node ν 0 is the same as the
row index of the last node ν N .
The root of the branch and bound search tree consists of the entire first
column of nodes. This set of nodes is recursively split in two to form the
binary search tree as depicted in Figure 10.5. The Viterbi algorithm allows us
to treat a set of nodes in the first column of the trellis as the source rather
than using a single node as the source as described in Section 9.5. The circular
shortest path algorithm progresses as follows.
The shortest path to the other end of the trellis is found from the root
node (i.e., the entire first column) and this forms a lower bound on the cost of
the circular shortest path. We find the destination node corresponding to the
shortest path and follow the backward pointers to determine the corresponding