# «Combination of paths for interactive segmentation Julien MILLE1, S´bastien BOUGLEUX2 and Laurent D. COHEN3 e 1 Universit´ de Lyon, CNRS e ...»

Combination of paths for interactive

segmentation

Julien MILLE1, S´bastien BOUGLEUX2 and Laurent D. COHEN3

e

1

Universit´ de Lyon, CNRS

e

Universit´ Lyon 1, LIRIS UMR5202, F-69622, France

e

http://liris.cnrs.fr/∼jmille

2

Universit´ de Caen-Basse Normandie, CNRS, GREYC, UMR6072

e

F-14050, Caen, France

https://bougleux.users.greyc.fr

3

Universit´ Paris Dauphine, CNRS, CEREMADE, UMR7534

e

F-75016, Paris, France

https://www.ceremade.dauphine.fr/∼cohen

Abstract. Active contours and minimal paths have been extensively studied theoretical tools for image segmentation. The recent geodesically linked active contour model, which basically consists in a set of vertices connected by paths of minimal cost, blend the beneﬁts of both concepts.

This makes up a closed piecewise-smooth curve, over which an edge or region energy functional can be formulated. As an important shortcom- ing, the geodesically linked active contour model in its initial formulation does not guarantee the curve to be simple, consistent with respect to the purpose of segmentation. In this paper, we propose to extract a relevant contour from a set of possible paths, such that the resulting structure ﬁts the image data and is simple. Toward this goal, we introduce a novel term to favor the simplicity of the generated contour, as well as a local search method to choose the best combination among possible paths.

1 Introduction Minimum cost paths for interactive two-phase segmentation provide a solid mathematical background and have proven to ﬁnd suitable solutions in many practical situations. Provided a set of landmark points typically located along the boundary of interest, paths are computed between these points in order to build a closed contour. Optimality is the main advantage of such approaches, since in most cases, a minimum cost path can be eﬃciently found as the global solution of the corresponding minimization problem, like Dijkstra’s algorithm for shortest paths in directed graphs with no negative cycle. Interactive segmentation methods based on a graph modeling of the image, making them discrete by nature, include the intelligent scissors (or live-wire) [18] and their on-the-ﬂy extension [11], as well as the riverbed approach [17] based on the image foresting transform [10].

2 Mille et al v2

As regards continous models, the minimal path method [7] achieved global minimization of the geodesic active contour functional [5], with ﬁxed userprovided endpoints, using the Fast Marching method [20, 21]. An interactive extension was later proposed by [12]. Since the control points are ﬁxed and must be located on the target contour, the minimal path approach does not represent a curve which deforms its shape. Moreover, due to the restricted number of these points, the geodesic may fail to capture a relevant contour if the image is too noisy, not contrasted enough, or if the target contour is too lengthy. While several methods concentrate on avoiding this second drawback [2, 4, 13], the geodesically linked active contour model of [16] allows to overcome the ﬁrst one, as it can be evolved thanks to a local search method. This latter model combines the advantages of geodesics with the ones of region-based energies, such as the minimal variance term proposed by [6]. Despite its robustness to local minima, this model can fail to construct a simple curve, i.e. without double point, from the initialization step to the end of the evolution.

To overcome this drawback, we propose to generate several relevant paths between landmark points and to select the combination of paths generating the best closed contour. In this extent, we introduce an energy functional, combining contour and region terms with a novel term favoring the simplicity of the curve, penalizing self-overlapping and self-intersections. Our three contributions, i.e. the construction of admissible paths, the simplicity energy as well as the selection of the optimal combination of paths, are described in details. The concepts on which relies the proposed approach are recalled in the following section.

2 Background: geodesic and piecewise-geodesic curves

where γ are the geodesics, according to Eq. (2), between the current position in ˜ the window and the adjacent vertices of vi, and γi is a shortened form for γvi,vi+1.

While this model allows to blend the beneﬁts of minimal paths and region-based terms, it turns out to have a signiﬁcant drawback, as its initial state is not necessarily a simple closed curve. As depicted in Fig. 1(e), this can occur when the initial vertices are unevenly distributed around the target boundary. In this case, geodesics gather on particular sides of the target boundary, as γv3,v1 overlaps γv1,v2 and γv2,v3. The reason is that each geodesic is generated independently from the others, such that the obtained piecewise-geodesic curve does not depend on the visiting order of pairs of adjacent vertices. This undesirable phenomenon may occur either as soon as the geodesically linked contour is initialized, or after several evolution steps on a previously well initialized contour.

One could consider imposing hard constraints on the overlapping between paths, or penalizing paths enclosing a region with excessively small area, but the independent construction of paths, which allows parallel implementation, prevents such constraints to be implemented. We address this shortcoming in what follows.

<

**3 Combination of admissible paths**

We study a more relevant contour construction preserving the advantages of piecewise geodesic curves. Assuming that a set of several possible relevant paths is available for each pair of successive vertices, we may select a single path from each set and combine these paths in order to build the best boundary curve.

The relevancy of the generated contour is measured by an energy functional, combining existing contour and region terms with a novel term penalizing selftangencies and self-intersections, ensuring the contour to be simple.

Sets of admissible paths Given an ordered pair of successive vertices (vi, vi+1 ), let Ai be a set of Ki admissible paths linking the two vertices, Ai = {γi,j }1≤j≤Ki, which we refer to as admissible set. To generate these admissible paths, one could ﬁrst think about solving the K shortest paths problem [9, 23]. However, it is unlikely to generate interesting contours in the context of real images, as the K − 1 next shortest paths might be identical to the shortest one, up to some very small localized oﬀset, bypassing the shortest path at one place. Moreover, the K shortest paths principle does not ﬁt well into the continuous framework Combination of paths for interactive segmentation 5

Fig. 2. Saddle points for determining relevant admissible paths between a and b: (a) Potential highlights two possible distinctive paths, (b) Action map with two admissible paths with their respective saddle points located halfway and (c) corresponding 3D plot of minimal paths. A second intuitive technique consists in computing K disjoint paths, as in [15], i.e. preventing each path to pass through points already visited by a previous path. This is achieved by setting P (x) to +∞ for all x belonging to each newly generated path. However, it would arbitrarily remove sections of contour that could be taken by other relevant paths. Moreover, in case of unsharp contours, low potential areas may get undesirably thick, so that two paths C1 and C2 may take the same contour section, C2 being only an oﬀset curve of C1.

To generate supplemental paths, we propose an approach based on the extraction of saddle points. Such critical points were already addressed in the case of minimal action maps, like in [8]. As explained in Section 2, the geodesic linking two points a and b is extracted by propagating the minimal action from a, stop when b is reached, and perform gradient descent from b. The opposite may also be done, provided that the path is reversed afterwards. A third way to compute γa,b consists in propagating simultaneously from a and b, stopping at the ﬁrst location where the two fronts meet, performing two gradient descents both sides apart from the meeting location, and assembling the two obtained paths adequately. This principle serves a basis for the generation of multiple paths. When propagation is performed from two source points, yielding the combined action map Ua,b = min(Ua, Ub ), the two propagation fronts meet at the saddle points of Ua,b (see Fig 2(a) and 2(b)). If one intuitively imagine the action as the height in a mountainous area, the saddle points are the mountain passes on the diﬀerent roads travelling from a to b, as depicted in Fig. 2(c).

These roads can share common sections, but each road lies in the bottom of a particular valley.

Let ma,b : [0, 1] −→ D be the medial curve, assumed to be of class C 2, sweeping along the points geodesically equidistant to a and b, 6 Mille et al i.e. {x | Ua (x) = Ub (x)}. It forms a crest on the combined action map and contains only critical points, put another way Ua,b is not deﬁned over ma,b.

However, Ua,b may be diﬀerentiated along the medial curve, which allows to deﬁne the saddle points as the local minima of Ua,b along ma,b.

In order to extract robust local minima in spite of the eﬀect of discretization, values of the action map are smoothed along ma,b. Not all saddle points are kept as starting points for path construction. In practice, we limit the number of admissible paths per set below a ﬁxed threshold Kmax. As can be seen in Fig. 3(b), many saddle points are intentionally ignored because of their action too high or their proximity to lower saddle points.

The contour resulting from the concatenation of selected paths should exhibit desirable properties in the image. One of these properties is that the generated contour should be simple, i.e. with no multiple point. Instead of imposing simplicity as a hard constraint, which might exclude relevant contours, it is encouraged by an additional energy. Indeed, it is reasonable to allow a certain degree of nonsimplicity, e.g. when vertices are located far from the target boundaries, which might cause several admissible paths to have common sections before splitting up, like in Fig. 1(e). The proposed term is based on a distinction between selftangency and self-intersection, which we present hereafter.

Self-overlap and twisting Consider a curve C closed and regular, i.e. non-singular in the parametric sense, meaning that its velocity vector C vanishes nowhere.

If C is non-simple, it has a number of multiple points that should be studied.

We only consider double points 1, which may be of two kinds. Let (u, v) ∈ [0, 1]2

**s.t. u = v be the unordered pair of curve positions identifying a double point:**

C(u) = C(v). On one hand, if (u, v) corresponds to a point of self-tangency, velocity vectors C (u) and C (v) are colinear. On the other hand, if (u, v) corresponds to a self-intersection - also known as an ordinary double point or crunode - velocity vectors point towards diﬀerent directions, making the curve cross itself. This distinction allows to address separately two diﬀerent defects on curves, which are not necessarily related. A curve with points of self-tangencies will exhibit self-overlapping segments, as depicted in Fig. 4(b), whereas a curve with self-intersections shown in Fig. 4(c) will split the image domain into more than two connected regions.

As regards the ﬁrst kind of double points, the amount of overlapping is quantiﬁed by measuring the length of overlapping curve segments. Considering function φ measuring the Euclidean distance between two points on the curve, φC (u, v) = C(u) − C(v), the zero level set of φC, ZC = {(u, v) | C(u) = C(v)} is the set of pairs of positions giving equal points (trivially, this set is never empty, since it contains at least 1 In our framework, curves with points of multiplicity 2 are detected and excluded from the search Combination of paths for interactive segmentation 7 0 20 200

Fig. 4. Distances φC plotted in (u, v)-space for several types of curve: (a) On a simple closed curve, φC vanishes only the graph diagonal. (b) On a curve with a section of self-tangency, φC additionally exhibits two symetrical zero lines. (c) On a curve with self-intersections, φC additionally exhibits isolated zeros

While tangent double points are used to measure overlapping, ordinary double points will serve as a basis for measuring the amount of twisting. Consider a regular closed curve C oriented clockwise with ordinary double points making self-intersections as shown in Fig. 5(a). It splits the image domain into disjoint subdomains, some of which are demarcated by inverted segments, i.e. portions of curves along which the normal vector C ⊥ points outward (on a simple clockwiseoriented curve, C ⊥ points inward). We propose to quantify the twisting of C as the proportion of area demarcated by inverted segments to the total area of C.

This proportion is related to the energy that one would exert to untwist the curve. A self-intersecting curve can be thought of as a planar projection of a knot, i.e. an embedding of the unit circle into Euclidean R3 space. Following the theory of knots [1, p. 13] [3], we consider twisted conﬁgurations of curves which corresponding knots could be unknotted by Reidemeister moves of type I and II (see Fig. 5(b) and 5(c), respectively). The simple loop, described by a single connected inverted segment and involving a single intersection, is related to the Reidemeister move of type I, whereas the double loop, consisting of two inverted segments and involving two intersections, is related to the Reidemeister move of type II. Let SL(C) ⊂ [0, 1]2 be the set of ordered pairs of curve positions (u, v) s.t. u v describing intersections involved in single loops, and DL(C) ⊂ [0, 1]2 × [0, 1]2 be the set of double ordered pairs ((u1, v1 ), (u2, v2 )) s.t. u1 u2 and v1 v2 describing the couples of intersections involved in double loops. The total inverted area I[C] is computed in linear time with respect