Image Processing Reference
In-Depth Information
Reprinted from Sadhana 18(1993), P. P. Das and B. N. Chatterji,
Digital Distance Geometry: A Survey
, 159-187,
Copyright (1993), with permission from Indian Academy of Sciences.
FIGURE 2.3: O(2) or 8-paths between two points u = 0 and v = (9,5) in
2-D. The paths Π
1
(marked by '*') and Π
2
(marked by '#') are both minimal
while the path Π (marked by '$') is not minimal. Note that |Π
∗
1
|=|Π
∗
2
|=9 and
|Π|=14.
2.2.2.1 Shortest Path Algorithm
For a neighborhood set N(·), there may be infinitely many paths in Z
n
between u and v. Here, we formulate a shortest path tracing algorithm to
trace one of the many shortest paths between the two points. Once the path
has been traced, we analyze the algorithm to find the length of the shortest
path.
Without loss of generality, we assume that u = 0 and v = x, where
x ∈ Σ
n
. That is, x belongs to the all-positive hyperoctant and its components
are sorted in non-increasing order. x is obtained from v by first taking the
absolute value of the components of v and then sorting them in non-increasing
order.
By our assumption of translation invariance, the choice of origin is im-
material. Hence, u = 0 offers no restriction. In addition, an N(·) usually is
isotropic and symmetric. Therefore the choice of v = x is justified. Combining
the two assumptions, it is clear that for any arbitrary choice of u and v in any
hyperoctant, there is a corresponding x satisfying the condition above such
that any shortest path from u to v bears a point-by-point correspondence
with a shortest path from 0 to x.
We now present an algorithm TRACE to trace such a shortest path.
Though there may be a number shortest paths between 0 and x, TRACE
traces any one of them.
Note on the choice of the next point: Usually, there are many choices for
the next point on the path TRACE(x, n, N(·)). Depending on N(·), we need
to make an appropriate choice to ensure that the algorithm approaches the
origin (0) in every step and terminates in as many steps as there are points
on the shortest path. For a specific neighborhood set, this choice is guided
by the fact that shortest paths can be concatenated. That is, at any stage of
