Coupled algorithm

We can certainly consider that the global minimum of the topological gradient is part of the edge set. So we can choose the reference point as being this minimum. It is then possible to compute the distance between and any other point . A gradient descent algorithm can then be used to minimize the distance function, in order to find the minimal path between and the initial point of the optimization scheme. If these two points are part of the same edge, as the potential function has been defined such that it is relatively costless to remain on the edge (thanks to the topological gradient), the minimal path will be a very good approximation of this edge. The main advantage is now that we are sure that this path corresponds to a continuous contour.

For a small additional computation cost, it is possible to consider more than one reference point. The distance function corresponds then to the distance to the set of these points. The corresponding Voronoï diagram can be seen as a dual mesh, and the minimum of the distance function on each edge of this mesh is a saddle-point: minimal distance along the edges of the mesh, maximal distance to the reference points.

The hybrid algorithm we propose is the following:

Compute the topological gradient of the image (see previous sections).

Choose key-points; the main one will be for example the global minimum of the topological gradient.

Fast marching: computation of the distance function to all these key-points, and of the corresponding Voronoï diagram.

Saddle-points: on each edge of the Voronoï diagram, determine the point of minimal distance.

Sort all these saddle-points, from smaller to larger distance.

For each of these points, from smaller to larger distance, check if it will not be used for connecting two key-points, one of which is already connected to two other key-points.

If this is not the case, use this point as an initialization for a descent type algorithm in order to connect the two corresponding key-points.

This algorithm clearly converges, and all the key-points are connected to at most two other key-points at convergence. This provides a continuous contour, connecting the key-points. It is then an approximation of one of the main contours of the image as it corresponds to a valley line of the topological gradient.

As seen in [2], it allows us to appreciably improve our inpainting algorithm. It also improves the quality of the segmentation. For all other image processing problems, there were no noticeable improvements.