Possible error detection and correction methods in 3D

The error detection and correction methods of chapters 3 and 5 are summarized as in table . Actually, other algorithms combining the methods of both chapters could also be designed. One could detect corners of the Voronoi polygons in a signed EDT, and then use neighborhoods from table to propagate them further. Alternatively, one could detect non propagating pixels in a signed version of PSN, and then compute the corner of the continuous VP.

 

Table 6.1: The error detection and correction phases of the algorithms of chapter 3 and 5.

	Chapter 3	Chapter 5
Detection	non-propagating pixels	Corners of the digital
	in the PSN algorithm	Voronoi Polygons.
Correction	use of neighborhoods	explicit computation
	of increasing sizes	of the true VP corner

 

Unfortunately, not all of these methods can be extended to 3 dimensions. For instance, there can be errors in the 3D EDT while none of the neighboring voxels fails to propagate, as illustrated at figure where there is an error in p while both r₁ and r₂ propagate. Hence, the detection method of chapter 3 cannot be used.

  

Figure 6.2: Why PMN's detection criterion does not work in 3D: p(0,0,0) is closer to q(4,4,8) than to s₁(8,0,6), s₂(0,8,6) and s₃(0,0,10). Still, pixels r₁(3,3,7) and $r_2(3,3,8) \in VP(q) \bigcap N(p)$ propagate.

Similarly, computing the exact corner of the continuous VP from the 3 direct neighbors in the propagation direction does not necessary provide a finite volume. It makes the error correction method of chapter 5 impractical.
On the other hand, the corner detection of chapter 5 and the multiple neighborhoods correction of chapter 3 can be extended to 3D. For corner detection, one should be aware that there are two types of corners. Either the three neighbors in the propagation direction belong to different tiles of the Voronoi diagram than the current voxel. We call this a 3-corner. Either only two neighbors out of three belong to different tiles. We call this a 2-corner. As illustrated at figure , considering 2-corner such as r₂ is a needed to detect errors such as that in p.
Similarly to chapter 3, one can compute the limits for which a neighborhood of a given size guarantees that no error occurs in the Euclidean DT. These limits are found in table . The middle column gives the error for which the distance is the smallest. The right column contains the voxel closest to the error and that belongs to the same tile of the Voronoi diagram.

 

Table 6.2: Errors closest to (0,0,0) for a number of $N \times N \times N$ neighborhoods.

Neighborhood	Smallest error		Non-propagating pixel
	(dpx,dpy,dpz)	distE	(dpx,dpy,dpz)	distE
$3 \times 3 \times 3$	(6,3,2)	49	(4,2,2)	24
$5 \times 5 \times 5$	(12,4,3)	169	(9,2,3)	94
$7 \times 7 \times 7$	(24,5,5)	626	(20,4,4)	432
$9 \times 9 \times 9$	(24,9,4)	673	(19,7,3)	419
$11 \times 11 \times 11$	(37,11,5)	1515	(31,9,4)	1058
$13 \times 13 \times 13$	(45,12,5)	2194	(38,10,4)	1560
$15 \times 15 \times 15$	(52,12,5)	2873	(44,10,4)	2052
$17 \times 17 \times 17$	(60,12,5)	3769	(51,10,4)	2717