Computational Complexity

Comparing the complexity and computational costs of DT algorithms is a complex task. For $n \times n$ images, approximate algorithms such as Danielsson's [37], the chamfer DT [10], Leymarie's [95] or Ragnelmam's [127,128] have a fixed O(n²) cost regardless of the image content. Yamada's parallel algorithm [185] has a O(d.n³) cost, proportional to the maximum distance d found in the image. More complex exact algorithms such as Ragnelmam's [127], Eggers' [42] and Saito's [140] have costs that are highly dependent of the image content and can vary between O(n²) and O(n³). For those, experiments give a better knowledge of their complexity than theoretical considerations.

Among the methods described in chapter 2, those of Eggers and Saito appear to be the fastest exact Euclidean DTs. They are used here as the benchmark against which our algorithms are compared. Three versions of our algorithms are considered in this comparison: the approximate PSN and the exact PMN and PMON algorithms. In the PMN algorithm, only the fourth of the neighborhoods N in the same direction as (dp_x,dp_y) is used.

The choice of images on which the tests are performed is subjective and may dramatically affect the results. We perform 3 tests, illustrated at Figure . Test 1, suggested by Saito, is an image filled with an empty disk, whose size varies from $200 \times 200$ to $2000 \times 2000$. Test 2, suggested by Eggers, is made of random squares covering $15\%$ of the image in total, with an orientation varying between 0^o and 90^o. Test 3, our suggestion, is the worst case scenario foreseen by Eggers and Ragnelmam for propagation DTs: a straight line across the image with an orientation varying between 0^o and 90^o. Images for tests 2 and 3 are $1024 \times 1024$ pixels large.

  

Figure 3.7: Test images where object pixels are black and the DT is computed at every white pixel. The size of the ``circle'' image varies from $200 \times 200$ to $2000 \times 2000$. The orientation of the other two images varies from 0 to 90^o.

The algorithms were implemented in C on a Pentium II computer running at 233 MHz. We compare the CPU time required by each algorithm. Results are shown at Figures figure to figure for tests 1 to 3, respectively.

Test 1 (figure ) illustrates the CPU time per pixel for images of increasing size. An optimal O(n²) algorithm should therefore give a constant result. It is of course the case of the approximate PSN algorithm. PMN and PMON display a very slight increase with the image size, but the relative cost compared to PSN remains less then a factor 2, even for $2000 \times 2000$ images. PMON is faster than PMN as soon as the image is larger than $400 \times 400$. Saito's and Eggers' algorithms both have a computational cost per pixel increasing with the image size. Actually, their complexity is O(n³) for $n \times n$ images. Nevertheless, Saito's algorithm is as fast as PMN or PMON for small images ( $n \leq 400$).

  

Figure 3.8: Test1: Saito's empty circle image. Note the logarithmic scale for the CPU times.

Test 2 gives more complex results. All algorithms work faster on images where the squares are either oriented at 0^o, 45^o or 90^o, and slower for orientation near to 22,5^o and 67.5^o. This effect is more accentuated for Eggers' and Saito's. In average, PSN is the fastest, requiring 1.33 sec. PMN follows (1.54), then PMON (1.60), Eggers (1.82) and Saito (2.14), but these are not significant differences.

  

Figure 3.9: Test2: Eggers' random squares

Test 3 shows the worst-case scenario for the propagation methods of Ragnelmam and Eggers, for which they are known to have a O(n³) complexity. As in test 1, the disparity between CPU costs is such that the results are here displayed using a logarithmic scale. Eggers' DT performs very poorly for any orientation but the horizontal, vertical and 45° diagonal. Saito's DT performs reasonably well for orientations between 0 and 45°, but very poorly for orientations around 60°. In average, Eggers and Saito are respectively 14 and 7.5 times slower than PSN. In the worst orientation, Eggers and Saito are respectively 25 and 28 times slower than PSN. On the other hand, PMN and PMON only show a limited influence from the orientation. In average, they are 1.45 and 1.3 times slower than PSN. Even in the worst case, they are still less than twice slower than PSN. In contrast with the results of test 2, PMON out-performs PMN for all orientations.

In Figure , let us also note that Saito's algorithm is the only one that has a non-symetric behaviour around 45^o. This can easily be understood if one considers that all other algorithms treat all axis in the same way, while Saito's chooses to process the image first along one axis, then along the other. This choice can have a major influence on the computational cost. Unfortunately this is data dependent, which precludes the choice of an ordering of the axis that would be optimal in all cases. This issue is further studied for 3D data in chapter 6.

  

Figure 3.10: Test3: the worst case straight line.

In conclusion, both PMN and PMON seem to have a O(n²) complexity. Even in the worst case, the cost required to produce the exact EDT is less than double the cost of the approximate PSN. PMON out-performs PMN when the DT includes very large distance values, but its complexity is not justified for smaller images^3.1. Both algorithms are major improvements over the methods of Eggers and Saito.