Errors with a $3 \times 3$ neighborhood

Let us first consider that the approximate EDT was produced using a $3 \times 3$ (8-direct) neighborhood, such as in Danielsson's 8SED [37], Leymarie's [95] and Ragnelmam's [127] algorithms. Either in raster scanning or by increasing distance order, these algorithms propagate the information from sources - the object pixels - to the rest of the image. As illustrated at figure , errors occur when the source of a pixel differs from the sources of all its 8-direct neighbors. p(0,0) is closer to q₂(x₂,y₂) than q₁(x₁,y₁) or q₃(x₃,y₃), but pixels p₁(1,0) and p₃(1,1) are not.

  

Figure 3.2: A typical error made by an approximate EDT using the $3 \times 3$ neighborhood. Object pixel q₂ is hidden from pixel p by object pixels q₁ and q₃, that are closer to p₁ and p₃, respectively.

In general, since q₂ is the source of p, we have

 

x₂²+y₂² < x₁²+y₁² (3.1)

 

x₂²+y₂² < x₃²+y₃² (3.2)

Similarly, since q₁ is the source of p₁,

$$(x_1-1)^2+y_1^2 \leq (x_2-1)^2+y_2^2$$ (3.3)

and q₃ the source of p₃,

$$(x_3-1)^2+(y_3-1)^2 \leq (x_2-1)^2+(y_2-1)^2$$ (3.4)

In [146], Shih restricts these conditions further by setting implicitly x₁=x₂+1 and x₃=x₂-1, and considers strict inequalities for eq. and . Therefore he misses many possible errors, including that of Figure , with q₁(17,1), q₂(15,8) and q₃(13,11).

  

Figure 3.3: Relative locations (dx,dy) for which it is possible that an error occurs, with $0 \leq dx \leq 200$ and $0 \leq dy \leq 200$.

Instead, we find the integer solutions of equations to by exhaustive search. In order to know if an error could occur at the relative location (x₂,y₂), we check eq. for all integer couples (x₁,y₁) with

$$0 \leq x_1 \leq \sqrt{x_2^2+y_2^2+1}$$ (3.5)

$$\sqrt{x_2^2+y_2^2+1-x_1^2} \leq y_1 \leq \sqrt{x_2^2+y_2^2+1-x_1^2} + 1$$ (3.6)

Equation () guarantees that () is fulfilled. If we can find such a couple (x₁,y₁) satisfying (), and if we find another couple (x₃,y₃) satisfying () and () in a similar way, then it is possible that errors do occur for the relative location (x₂,y₂).

Applying this exhaustive search for all couples (x₂,y₂) within a $200 \times 200$ range, we find the result of Figure , where black pixels correspond to possible error locations. Defining the possible errors ratio as the percentage of possible error locations among all locations, we obtain the values of Figure , i.e. $20\%$ for a $100 \times 100$ image, and more than $50\%$ for images larger than $400 \times 400$. Obviously, possible locations are not uncommon. In particular, it means that an ``error locations lookup table'' approach to detect errors, such as suggested by Shih [146], is not practical.

  

Figure 3.4: Possible errors ratio for various image sizes