Geodesic metrics

As defined in chapter 2, the geodesic distance between two pixels p and q is the length of the shortest path from p to q. Suppose $P=\{p_1,p_2,...,p_n\}$ is a path between pixels p₁ and p_n, i.e. p_i and p_i+1 are connected neighbors for $i \in \{1,2,...,n-1\}$ and p_i belong to the domain for all i. The path length l(P) is defined as

$$l(P) = \sum_{i=1}^{n-1}d_N(p_i,p_{i+1})$$ (8.1)

the sum of the neighbor distances d_N between adjacent points in the path. A particular geodesic metric is defined by which neighbors are considered to be connected and the values of d_N for each pair of connected neighbors.
The simplest metric is the geodesic version of the city-block distance, used in [122,167,93]. It is defined as

d_N(p,q) = 0 if p = q

d_N(p,q) = 1 if dist_e(p,q)=1

$$d_N(p,q) = \infty$$ if dist_e(p,q) > 1 (8.2)

In order to get better approximations of the Euclidean metric, geodesic chamfer metrics were also used. Piper [122] uses the 3-4 chamfer metric, Verwer [167] considers a 5-7 metric, and Verbeek [165] uses a $5 \times 5$ neighborhood with $1-\sqrt{2}-\sqrt{5}$ weights. For instance, for the 3-4 chamfer metric, this gives

d_N(p,q) = 0 if p = q

d_N(p,q) = 3 if dist_e(p,q)=1

$$dist_e(p,q)=\sqrt{2}$$ d_N(p,q) = 4 if

$$d_N(p,q) = \infty dist_e(p,q) > \sqrt{2}$$ if (8.3)

  

Figure 8.1: Left: Domain and object - Right: Geodesic DT with a 3-4 metric.

Such a geodesic DT is illustrated at figure . We compute the geodesic distance from the dot in the upper right corner, under the constraint that the domain is restricted to the white pixels. The distances are shown using a cyclic grayscale colormap so that the iso-distance curves are visible. Obviously this DT is only a coarse approximation of the geodesic Euclidean DT defined on a continuous domain.
We propose to use a more general definition of the geodesic DT. Given a ball B_d of radius d, the local distances d_N in () are defined as

d_N(p,q) = dist_e(p,q) (8.4)

if $dist_e(p,q) \leq d$ and there is a path $R=\{r_1,r_2,...,r_m\}$ such that p=r₁, q=r_m, $dist_e(r_j,r_{j+1})=1 \; , \; \forall \; 1 \leq j \leq m-1$ and $dist_e(p,r_j) \leq d \; , \; \forall \; 1 \leq j \leq m$. Otherwise,

$$d_N(p,q) = \infty$$ (8.5)

We call this the B_d-geodesic DT. This means that there is a direct path between a pixel p and any pixel q in the neighborhood defined by the ball B_d, provided there is a path made of direct neighbors only and entirely included in B_d(p), that connects p and q. This definition allows a large variety of trade-offs according to the size d. A larger d approximates the Euclidean DT better in obstacle-less regions. A smaller d follows the obstacles' shape better.
This definition is a generalization of those used in [122,167,165,93]. In particular, d=1 corresponds to the city-block metric, $d=\sqrt{2}$ is similar to the chamfer 3-4 metric and $d=\sqrt{5}$ corresponds to the chamfer $1-\sqrt{2}-\sqrt{5}$ metric used by Verbeek [165]. In figure , distance maps using $d=\sqrt{2}$ and d=6 are shown.

  

Figure 8.2: Left: Geodesic DT, ball size$=\sqrt{2}$ - Right: Geodesic DT, ball size=6