Graphics Reference
In-Depth Information
contours that wrap tightly around the origin. Instead, we use a contour energy
of the form [7]
E [ C ]=
C
g
r
ds
(10.4)
where g is a measure of probability of being on the boundary (e.g., image
gradient) and r is the radius of the contour C . Thus all circles centered on
the origin would have the same contour energy.
Now we cut the image plane with an arbitrary cut line as depicted in
Figure 10.7. Let us now consider a point on the cut line, p cut , which is mapped
to two equivalent points p start and p end in the cut plane S . Now to find
the shortest circular path beginning and ending at p cut ,wejustsolvethe
equivalent problem of finding the shortest path from p start to p end in the cut
plane S (using the Fast Marching algorithm described in the next section).
Fig. 10.7. A minimal closed geodesic in the image plane passing through p cut and
the corresponding open shortest path ( i.e., geodesic) in the cut plane between p start
and p end . (from [7]).
A problem with the above approach is that it would not allow the shortest
path to cross the cut line. This would once again restrict the algorithm to
convex shapes only. However Appleton [7] shows that if we represent the
open search space in an augmented helicoidal representation, it allows us
to represent concave contours that cross the cut line (i.e., unwrapping line)
multiple times as illustrated in Figure 10.8. Thus we can now find the shortest
closed path passing through p cut even if the contour wraps around the origin
several times. Thus the arbitrary choice of the cut line does not influence nor
restrict the range of image topology the GOGAC algorithm can handle.
In the above development it was assumed that p cut , the intersection of the
shortest path and the cut line, is known in advance. This is not the case, and
an exhaustive search of all possible values of p cut would be quite inecient.
Instead, we use the branch and bound approach of the CSP algorithm in
Section 10.2. Referring to Figure 10.7, we use the set of all possible points for
Search WWH ::




Custom Search