First departure algorithms and image decompositions into peaks and wells
Résumé
An image may be decomposed as a difference between an image of peaks and an image of wells. This decomposition depends upon the point of view, an arbitrary set from where the image is considered: a peak appears as a peak if it is impossible to reach it starting from any position in the point of view without climbing. A well cannot be reached without descending. To each particular point of view corresponds a different decomposition. The decomposition is reversible. If one applies a morphological operator to the peaks-and-wells components before applying the inverse transform, one gets a new, transformed image. The decomposition is produced by a generalized shortest path algorithm on weighted graphs; the node weights represent departure times and the arc weights represent traversal times. If a train starts at each node at a time equal to the weight of this node and crosses each arc in a time equal to the weight of the node, the outcome of the algorithm is the earliest departure time of a train from each node: equal to the initial node weight if no other train arrives earlier, and equal to the earliest train coming from another node otherwise. Reconstruction closings or floodings also belong to this family of first departure algorithms. A number of applications illustrate the method.