Influence of the neighborhood size

Next: Influence of the propagation Up: Errors in approximate EDT Previous: Errors with a neighborhood

Influence of the neighborhood size

Let us now consider any neighborhood N. Similarly to the previous section, an error may occur at a relative location (dp_x,dp_y) if, for every neighbor $n \in N$ , one can find (dq_x,dq_y) such that

dq_x²+dq_y² > dp_x²+dp_y²

(3.7)

$\begin{displaymath}(dq_x-n_x)^2+(dq_y-n_y)^2 \leq (dp_x-n_x)^2+(dp_y-n_y)^2 \end{displaymath}$

(3.8)

Once again, the possible errors relative locations can be determined by exhaustive search, for any neighborhood N. In particular, we are interested in the shortest distance for which an error can occur when computing the approximate DT with a neighborhood N. This is determined as follows.

Algorithm 2 Compute the closest error location (dp_x,dp_y) for a neighborhood N

$\begin{algorithmic}\AINPUT A neighborhood $N$ . \AOUTPUT $dp_{err}$\space and $... ...p_x \leftarrow dp_x+1$ \UNTIL{ $dp_x^2 > D_{err}$ } \STATE \end{algorithmic}$

The results for the 4-direct neighborhood and several $N \times N$ neighborhoods are found in table . In the right column of this table, we also find the relative location of the nearest pixel with the same source as the pixel where the error occurs. Using this table, we know the size of the neighborhood to consider to produce an exact EDT up to a given distance. For instance, if we want it to be correct up to dist_E(dp)=1000, we find in table 1 that 1000 is between 674 and 2404. Therefore, a $7 \times 7$ neighborhood is large enough to ensure an exact result, but a $5 \times 5$ neighborhood might be too small.

Table: Errors closest to (0,0) for the 4-direct and a number of $N \times N$ neighborhoods. The first two lines correspond to the errors illustrated at Figure

Neighborhood	Smallest error		Non-propagating pixel
	(dp_x,dp_y)	dist_E	(dp_x,dp_y)	dist_E
4-direct	(2,2)	8	(1,1)	2
$3 \times 3$	(12,5)	169	(10,4)	116
$5 \times 5$	(25,7)	674	(22,6)	520
$7 \times 7$	(48,10)	2404	(44,9)	2017
$9 \times 9$	(72,12)	5328	(67,11)	4610
$11 \times 11$	(108,15)	11889	(102,14)	10600
$13 \times 13$	(143,17)	20738	(136,16)	18752
$15 \times 15$	(192,20)	37264	(184,19)	34217
$17 \times 17$	(238,22)	57128	(229,21)	52882
$19 \times 19$	(300,25)	90525	(290,24)	84676
$21 \times 21$	(357,27)	128178	(346,26)	120392
$23 \times 23$	(420,29)	177241	(408,28)	167248
$25 \times 25$	(500,32)	251024	(487,31)	238130
$27 \times 27$	(574,34)	330632	(560,33)	314689
$29 \times 29$	(667,37)	446258	(652,36)	426400
$31 \times 31$	(728,40)	591424	(752,39)	567027

Unfortunately, increasing the neighborhood size to produce an exact EDT soon leads to a prohibitive computational cost when the image size increases.

Next: Influence of the propagation Up: Errors in approximate EDT Previous: Errors with a neighborhood

Olivier Cuisenaire
1999-10-05