Sequential processing by propagation.

In the above parallel methods, a lot of computational power is wasted because, at each iteration, only a small fraction of the processed pixels actually change values. Ragnelmam [127] and Eggers [42] implement the above methods efficiently by storing the pixels in the propagation front in a dynamic list. Vincent [168] proposes an alternative approach where the propagation front is considered as chain.

In the same paper where he describes the approximate Euclidean DT by ordered propagation, Ragnelmam [127] proposes an efficient implementation of Yamada's parallel algorithm. First, object pixels are put in a dynamic list. Then, Yamada's mask is applied only to the pixels taken from that list. Any neighbor that changes value is itself put into the list for next iteration. Also, the updating of pixel values is delayed until the next iteration, so that all pixels seem to be processed simultaneously as in purely parallel processing.

Because it only processes the pixels in the propagation front, and because it also restricts the neighbors it considers to those of Figure , this implementation is obviously much faster that Yamada's. For instance, for a single object pixel placed in the middle of an $n \times n$ image, the computational complexity becomes o(n²) instead of o(n³). Unfortunately, there is not always such a gain in complexity. In the approximate algorithm, ordered propagation guaranteed that pixels did not propagate more than once. This time, the propagation is ordered with the dist_chess metric, but not with dist_e anymore. Therefore, propagation fronts may follow each other, and some pixels may be updated many times, up to once per object pixel in the worst case configuration, a oblique line of object pixels. This brings us back to a o(n³) complexity.

Eggers [42] adapts Huang's parallel algorithm in a similar way. His implementation turns out to be even faster than Ragnelmam's for two reasons. First, Huang's masks (eq. ) provide a very efficient way to compute distances, similar to Leymarie's improvement of Danielsson's algorithms. Secondly, Eggers notices that, for parallel algorithms, one only needs to support propagation along the path made of diagonal steps only, followed by horizontal or vertical steps only. Therefore, he uses the neighborhoods of Figure . He calls this sufficient propagation.

  

Figure 2.10: Eggers' sufficient propagation neighborhoods. Left: for D(p)=0. Right: for D(p)>0

On the other hand, the propagation order is exactly the same as before, so that there is still a o(n³) complexity for worst case $n \times n$ images. Finally, Vincent [168] - using his experience of the efficient implementation of mathematical morphology operators [169] - proposes to represent the borders of the object as chains, and to propagate these chains by applying dilations repeatedly. The elements of the chains remember the location of their nearest object pixels, so that the exact Euclidean distance can be computed. In order to avoid errors as in Figure , the propagation isn't stopped as soon as the propagated distance becomes larger than the distance of the pixels it reaches, but continues a little further, until it reaches its value plus one. This idea is similar to Mullikin's in next section.

This approach is obviously tempting because the structure of the chains should prevent non-desired multiple propagation to occur and keep the computational complexity low. Unfortunately, the method requires the chains to be broken at every non-convex part of the object border. And the worst-case images for propagation DTs, i.e. a sloping line or an empty disk, are made essentially or entirely of non-convex borders, so that there is no real gain in using chains instead of a simple list of pixels to represent the propagation front.