Computational Complexity

In order to evaluate the computational cost and complexity of this new algorithm, we apply the same tests as in chapter 3, i.e. the test images of figure . The result of these experiments is found in figures to .
In this section, we compare five different algorithms. Three of those are PSN, PMN and PMON, the propagation algorithms of chapter 3. The other two are the approximate and exact algorithms of this chapter. The approximate one is called 4-neighbors Sequential Signed Euclidean Distance transformation, or 4SSED. The exact one is a correction on 4SSED, and we call it 4SSED+.

  

Figure 5.3: Test1: Empty circle image.

In all three tests, 4SSED performs marginally better than the other approximate algorithm, PSN. There is no difference between them for test 1, the empty disk image. For tests 2 and 3, 4SSED does not suffer from the slight orientation dependence that affects PSN.

  

Figure 5.4: Test2: Random squares .

The exact 4SSED+ algorithm is faster than the exact PMN and PMON algorithms in all cases. Actually, for tests 2 and 3, it is even as fast as the approximate PSN. Also, 4SSED+ is nearly unaffected by the image orientation. Indeed, during the ``corner detection and error correction'' step, most of the processing power is spent on the constant time corner detection. Corners typically represent less than 2% of the image pixels, which keeps the correction cost low.

  

Figure 5.5: Test3: Straight line.

To conclude, 4SSED+ is both faster and less orientation dependent than its propagation counterparts. In average, it is only 15 to 20% slower than 4SSED. This makes it arguably the optimal exact signed Euclidean DT algorithm.