Accuracy

As mentioned in section , the accuracy of a geodesic DT is a trade-off between how precisely it approximates the Euclidean DT in obstacle free domains and how closely it follows the obstacles in their corners. The larger B_d, the better it approximates the Euclidean DT, but large B_d may cut through corners of the domain.
In this section, we focus on the first part of the trade-off, i.e. how closely the B_d-geodesic DT can approximate the Euclidean DT on an obstacle free domain. Let us consider an object pixel q and domain pixel p. The difference between dist_e(p,q) and D(p) comes from two sources.
First, when the direction of p-q is not supported by the neighbors in B_d, the distance is approximated similarly to the chamfer metrics of section . This creates a systematic relative error depending on the angle made by p-q.
Secondly, the restrictions imposed by () introduce an additional error on the last segment of the path. This non-systematic error is null if $d_N(p_{m-1},p_m) \approx d$, it is maximum when d_N(p_m-1,p_m)=1. Let us try to evaluate it. In figure , the path from p to q is composed of two parts, as in (). D(p_m-1) is considered as an error free distance d. d_N(p_m-1,p_m) is the last segment of the path.

  

Figure 8.3: Non-Systematic error

The true value of D(p) is D_exact(p) = dist_e(p,q) = d+e. The computed value of D(p) is $D_{comp}(p) = \min \{d+h,d+v)\}$ with $\max \{h,v\} = 1$. The error is $E = D_{comp}(p) - D_{exact}(p) = \min \{d+h,d+v\} - (d+e) = \min \{h,v\} - e$. It is maximum for a 45^o orientation, where $E = 1 - \cos(45^o) \approx 0.3$ pixel. This non-systematic error is an absolute error, and its importance fades for large distances.
In order to reduce the non-systematic error, one can use larger neighborhoods than N₄ during the propagation process. In particular, with N₈, the non-systematic error is reduced to $E = 1 - \cos(22.5^o) \approx 0.075$ pixel.

  

Figure 8.4: Systematic error

In figure , we show the systematic errors for 3 geodesic DT algorithms: the bucket sorting algorithm using N₄, and the circular (ordered) propagation algorithm both with N₄ and N₈. We notice that the use of N₈ - suggested to decrease the non-systematic error - also decreases the systematic error. Indeed, using N₈ in () increases the class of acceptable paths, and adds a few directions to $\delta(B_d)$.