Limitations to the 3D error detection and correction methods

Unfortunately, although it is theoretically possible, the generation of an exact Euclidean DT in 3D using VP corner detection and multiple neighborhoods correction suffers from two major drawbacks. On one hand, corners are not as uncommon in 3D as in 2D. For instance, for the sphere test images used in the next section, there are typically only 1 or 2% of 3-corners, but sometimes as many as 20% of 2-corners. This makes the correction phase a non-negligible part of the computational cost. On the other hand, the use of large 3D neighborhoods guarantees exact EDT up to much smaller values than in 2D. For instance, the $17 \times 17 \times 17$ neighborhood only guarantees an exact EDT up to dist_E = 3769, while the 2D $17 \times 17$ was sufficient up to dist_E = 57128.
Because of these drawbacks, we first assess the feasibility of the 3D error detection and correction approach by studying the computational complexity of a prototype algorithm, that computes an approximate EDT using the full error detection, and an error detection limited to $3 \times 3 \times 3$ neighborhoods.
We compare the computational costs and complexities of 5 algorithms. These algorithms are

• Ragnelmam's corner EDT, that uses 8 scans with 3 direct neighbors each.
• The 3D version of the PSN algorithm, with the neighborhoods of figure .
• The same algorithm used to produce a signed DT, as required by the error detection method. We call it signed-PSN
• Our prototype algorithm, where 3-corners are further checked with the $3 \times 3 \times 3$ neighborhood and 2-corners are further checked with a $3 \times 3$ neighborhood in the corner plane. We call this $3 \times 3 \times 3$ PMN.
• Saito's exact Euclidean DT algorithm.

In order to compare these algorithms, we use two classes of test images. In test 1, non-object pixels are included in one eighth of a sphere centered in (0,0,0), with a radius equal to the image size. This image size varies from $32 \times 32 \times 32$ to $256 \times 256 \times 256$. In test 2, the object consists of a plane whose orientation varies from 0^o to 90^o. The image size is $200 \times 200 \times 200$. The algorithms were implemented in C and executed on a SUN Sparc Ultra 1 workstation.

  

Figure 6.3: Test1: Empty sphere image.

Figure shows the computational cost per pixel for test 1. PSN is the fastest in all cases but for very small images. Its cost is only marginally affected by the image size. The corner EDT, which gives a similar approximation of the EDT, is the slowest in all cases. This illustrates the weakness of raster scanning methods in higher dimensions.
The signed PSN has a computational cost significantly higher than the unsigned one. It also has much larger memory requirements. The hybrid $3 \times 3 \times 3$ PMN requires an approximately constant additional cost compared to the signed PSN. It corresponds mostly to the cost of the detection phase since corrections are strictly restricted within the $3 \times 3 \times 3$ neighborhood.
Finally, Saito's algorithm appears to be quite efficient in 3D. For images smaller than $50 \times 50 \times 50$, it is the fastest algorithm of all. For images smaller than $150 \times 150 \times 150$, only the unsigned PSN is faster. Even for images as large as $256 \times 256 \times 256$, its computational cost is similar to the $3 \times 3 \times 3$ PMN, only twice slower than PSN.
On the other hand, its complexity appears to be higher than that of the approximate algorithms. Actually, one can show that Saito's algorithm has a O(n⁴) complexity for $n \times n \times n$ images. More generally, it has a O (D.n^D+1) complexity in D dimensions, for an $n \times ... \times n$ image. Indeed, in Saito's algorithm, the scans in each direction are independent. In one direction, scanning one line of n voxels has a O(n²) complexity, and there are n^D-1 such lines, so that the computational cost of a full scan in one direction is O(n^D+1).

  

Figure 6.4: Test2: Oriented plane.

The results of test 2 are found in figure . The approximate algorithms are ordered in the same way as for test 1. The PSN-based algorithms are somewhat orientation dependent, in contrast with the slower corner EDT. Saito's algorithm performs better than all others in most orientations, but worse for orientations close to 60^o.