Signed EDT and Voronoi diagrams

As defined in chapter 2, the signed distance from an object and the Voronoi diagram of the object pixels are equivalent concepts. In particular, we have

$$\forall p \in I, \; p \in VP( p - SD(p) )$$ (5.1)

In order to understand the behaviour of Signed EDT algorithms, it is interesting to consider a few properties of the Voronoi diagram, both on the continuous plane and on a discrete grid. Let us start with the continuous case.
A first property of the continuous Voronoi diagram is that its tiles are connected sets. An even stricter property says that any tile VP(q) in the Voronoi diagram is star-shaped, i.e.

$$p \in VP(q) \Rightarrow \forall \; \; 0 \leq \alpha \leq 1 \; , \; p' = \alpha.p+(1-\alpha).q \in VP(q)$$ (5.2)

This is proved ab absurdo. Consider that there is a $p' \not\in VP(q)$. Then, there exists $q' \in O$ such that

 

dist_e(p',q') < dist_e(p',q) (5.3)

Let us then consider the distance between our point p and this object pixel q'. By the triangular inequality, we have

$$dist_e(p,q') \leq dist_e(p,p') + dist_e(p',q)$$ (5.4)

by combining () and (), we have

 

dist_e(p,q') < dist_e(p,p') + dist_e(p',q) = dist_e(p,q) (5.5)

with the equality a consequence of the alignment of p,p' and q. Obviously, with dist_e(p,q') < dist_e(p,q), p cannot be part of VP(q), which contradicts our assumptions. QED.
While Voronoi diagrams based on any metric that satisfies the triangular inequality are star-shaped, continuous Voronoi diagrams based on the Euclidean metric have an even stronger property: they are convex, i.e.

$$p_1,p_2 \in VP(q) \Rightarrow \forall \; 0 \leq \alpha \leq 1, \; p' = \alpha.p_1 + (1-\alpha).p_2 \; \in VP(q)$$ (5.6)

Once again this can be proved ab absurdo. Let us consider that there is a $p' \not\in VP(q)$, i.e. that $p' \in VP(q')$ with $q \neq q'$. The plane is divided in two by the mid-perpendicular of qq', and each half-plane corresponds to the zones of influence of q and q'. $p' \not\in VP(q)$ implies that this mid-perpendicular intersects p'q between p' and q. On the other hand, $p_1 \in VP(q)$ and $p_2 \in VP(q)$ imply that it intersects p'q beyond p₁p₂. Both propositions contradict each other. QED.
A last property says that the tiles of the Voronoi diagram of a discrete set of point are polygons, because it is constructed from the lines that divide the plane between the pixels two by two. This is why we usually refer to the tiles of the Voronoi diagram as Voronoi Polygons (VP).
Let us now consider what happens for a digital image, i.e. for the Voronoi diagrams defined on discrete grids. In the exact digital Voronoi diagram, the value of each pixel is strictly equal to its value in the underlying continuous plane. Unfortunately, the tiles in such a diagram are not always connected anymore, as illustrated in chapter 2, section . This leads to errors in the computation of the signed DT with limited size neighborhoods.
Interestingly, errors only occur in the corners of the Voronoi polygons, where the corners of a polygon are defined as the locus of the segments smaller than $\sqrt{2}$ that join two edges of the polygon. As illustrated at figure , errors in the signed DT only occur when the VP is disconnected on the digital grid, i.e. when the VP can fit between points of the grid. And the maximum length between two neighboring points of the grid is $\sqrt{2}$.

  

Figure 5.1: Corners of a Voronoi Polygon.

To every corner of the continuous Voronoi diagram corresponds a corner of its digital approximation generated by an approximate signed EDT algorithm. Those corner pixels share the following property. Corner pixels and their two direct neighbors in the propagation direction have 3 different nearest object pixels. This property can easily be checked and provides a fast method to detect corners.