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

Fig. 10.5. The binary search tree for m =8. Only the first column of the trellis
containing the potential source vertices is shown (from [7]).
source node. If the source node ν 0 is the same as the destination node ν N ,
then we have found the circular shortest path and the algorithm terminates.
Otherwise the source node is split in two and the Viterbi algorithm is
then run on the upper and lower subproblems. Since we know that a circular
shortest path must start and finish on the same node, a new bound on the
circular shortest path is obtained by examining the shortest path length to
the corresponding upper and lower half of the destination nodes. For example,
if m = 8, we would look for the shortest paths between source and destination
nodes with row indices 0-3 and 4-7, respectively. As before, if the shortest
path found is circular, the algorithm terminates.
Otherwise we recursively split the node with the lowest circular shortest
path bound and continue the search. The complete algorithm is given in [7]
and an example segmentation of a diatom is shown in Figure 10.6. On typi-
cal images, the CSP algortihm often identifies the optimum circular shortest