Hybrid algorithm, combining 4SSED+ and Saito's methods

For small images, Saito's algorithm is extremely efficient, even out-performing approximate EDT algorithms in many cases. For numerous applications, 3D images indeed have small dimensions, because large dimensions would lead to enormous datasets, that would be impractical to acquire, store and process. A typical PET scan only has a $128 \times 128 \times S$ resolution. A typical MR image would be $256 \times 256 \times S$, where S is the number of slices (typically 100).
For larger images, Saito's method suffers from a O(n⁴) complexity, but it appears that the error detection and correction methods can not provide better results. This makes the Euclidean DT an expensive tool to process CT scans, for instance, where the resolution can easily reach $512 \times 512 \times S$. Also, one may expect that the resolution of other modalities, such as MRI, will increase in the future. Already today, non medical applications such as remote sensing or 3D microscopy provide datasets where the size of each slice is much larger, even though the number of slices may be smaller.
Fortunately, it is possible to improve Saito's 3D EDT by noticing that it works axis by axis. In particular, it means that a 2D EDT is computed in each slice before the algorithm considers the 3rd (inter-slice) axis. Therefore, it is possible to replace the computations along the two first axis by our optimal 2D EDT of chapter 5 applied on all slices. We call this the hybrid algorithm.

  

Figure 6.5: Computational complexity of Saito's and the hybrid algorithm on 3D isotropic data.

The gains in computational cost of this change are illustrated at figure . Saito's and the hybrid algorithm are compared using the test 1 image, i.e. a 3D image containing the 8^th of a sphere, with a size $N \times N \times N$, with N varying from 100 to 600. PSN is also shown as a reference.
Both for Saito's and the hybrid algorithm, the cost of the slice by slice 2D EDT stage is shown as a dashed line. The additional cost for the computations along the 3^rd (inter-slice) axis - the distance between the dashed and plain lines - is of course identical in both cases. Surprisingly, this additional cost is only very lightly dependent on the image size, so that the hybrid method nearly has a O(n³) complexity. Practically^6.2, the hybrid algorithm is faster than Saito's for images larger than $260 \times 260 \times 260$.

  

Figure 6.6: Computational complexity of Saito's and the hybrid algorithm on 3D anisotropic data (voxel size is $1 \times 1 \times 4$

When on considers practical applications, it appears that 3D images are very seldom cubic as considered until now. Instead, they are usually made of a relatively small number of high-resolution slices with a lower inter-slice resolution. We are therefore interested in how the above results adapt to anisotropic data.
Figure considers the same cubic volume as before (the 8^th of a sphere) sampled with $1 \times 1 \times 4$ voxels. Therefore, there are 4 times less slices than pixels along a column or a row of a slice. For instance, an image size of 600 means a $600 \times 600 \times 150$ image. In such a case, the complexity of Saito's algorithm depends on the order in which the axis are considered, i.e. whether the smaller anisotropic axis is considered first, second or third. Obviously, considering it in second place is the best choice. On the other hand, the hybrid method appears to be nearly insensitive to the image size, which makes it asymptotically optimal. Practically, the hybrid method is once again the fastest as soon as the image size exceeds 260. Let us remind that this corresponds to a volume of data that is 4 times smaller than at figure .
Finally, let us notice that the hybrid algorithm is not significantly slower than PSN^6.3, the fastest and coarsest approximate EDT. This is especially true for anisotropic data.