CSED Algorithm

Using the above considerations, we can design the following algorithm. First, we apply any approximate signed Euclidean DT algorithm. For instance, let us consider a signed version of Danielsson's raster scanning algorithm [37].

Algorithm 6   4-neighbors Sequential Signed Euclidean Distance transformation (4SSED).

As before, a special attention should be taken to the efficient computation of dist_E(dp), either using Leymarie's formulae () or lookup tables to compute the squares of integers.
In the second step, we apply the corner detection and error correction using the principles of the previous sections, with a slight modification. Indeed, for corner pixels with dist_E(SD(p)) < 116, we know from chapter 3 that a $3 \times 3$ neighborhood is always sufficient to ensure a correct distance transformation. It is then more computationally efficient to only test the diagonal pixels rather than to make the complex floating point operations of equations () to (). The algorithm goes as follows.

Algorithm 7   Corner detection and error correction in a signed Euclidean DT.

One can notice that, in contrast with the 4SSED algorithm, the correction step uses a ``write'' formalism in the test() procedure. With the ``read'' formalism, test(p,n) can modify the value of SD(p). With the ``write'' formalism, it can modify the value of SD(p+n).