Influence of the propagation process

Instead of considering all possible relative error locations as in the previous section, we now restrict ourselves to the errors occurring for the particular image on which algorithm is performed. Intuition tells us that errors only happen near pixels that do not propagate.

More formally, let N₁ and N₂ be two neighborhoods such that $N_1 \subset N_2$. Let D₁ and D₂ be the resulting signed distance maps generated using N₁ and N₂ respectively. If there is a pixel p such that $D_1(p) \neq D_2(p)$, i.e. D₁(p) is inexact and D₁(p)>D₂(p), then there is a pixel $r \in N_2(p)$ such that either $D_1(r) \neq D_2(r)$, either D₁(r) was not propagated using N₁.

To prove this, let us first consider that pixels belonging to a Voronoi polygon VP(q) can only propagate to other locations belonging to VP(q) with the same q, which is what ordered propagation aims to achieve. Let us consider q such that $p \in VP(q)$, i.e. let q be the nearest object pixel to p. Let us consider the set $S=VP(q) \bigcap (N2(p) \backslash N1(p))$ (Figure ). We know this set is not empty since at least one pixel propagated to p using N₂ but none did using N₁. Let us suppose that all pixels $r \in S$ have a correct value and were propagated using N₁. Since propagation implies a strict increase of the distance value, at least one pixel $r \in S$ must propagate to a pixel $r' \not\in S$, i.e. a pixel $r \in VP(q) \bigcap N1(p)$. This is impossible since r' would then have been propagated to p using N₁, and D₁(p) would then be correct.

  

Figure 3.5: $S=VP(q) \bigcap (N2(p) \backslash N1(p))$

In practice, the ordered propagation of algorithm allows propagation to locations that are either in the same VP or in the neighborhood of this VP. Nevertheless, the above proof remains correct since propagated pixels located in the wrong VP are corrected before being propagated, and do not propagate themselves. Q.E.D.