Admin

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 neighborhood only guarantees an exact EDT up to distE = 3769, while the 2D was sufficient up to distE = 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 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 neighborhood and 2-corners are further checked with a neighborhood in the corner plane. We call this 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 to . In test 2, the object consists of a plane whose orientation varies from 0o to 90o. The image size is . The algorithms were implemented in C and executed on a SUN Sparc Ultra 1 workstation.


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 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 neighborhood.
Finally, Saito's algorithm appears to be quite efficient in 3D. For images smaller than , it is the fastest algorithm of all. For images smaller than , only the unsigned PSN is faster. Even for images as large as , its computational cost is similar to the 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(n4) complexity for images. More generally, it has a O (D.nD+1) complexity in D dimensions, for an 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(n2) complexity, and there are nD-1 such lines, so that the computational cost of a full scan in one direction is O(nD+1).


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 60o

merryjay

spamming...

pistoneliv

spam error

yespkorg

kill spam

peakyesno

spamming...

tijnema

hard to read, but it's nice information

------------------
2oo7