FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 |

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

-- [ Page 1 ] --

Combination of paths for interactive


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



Universit´ de Lyon, CNRS


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




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


F-14050, Caen, France



Universit´ Paris Dauphine, CNRS, CEREMADE, UMR7534


F-75016, Paris, France


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 benefits 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 fits 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 find 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 efficiently 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-fly 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 fixed userprovided endpoints, using the Fast Marching method [20, 21]. An interactive extension was later proposed by [12]. Since the control points are fixed 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 first 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 benefits of minimal paths and region-based terms, it turns out to have a significant 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 first 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 offset, bypassing the shortest path at one place. Moreover, the K shortest paths principle does not fit 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 offset 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 first 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 different 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 defined over ma,b.

However, Ua,b may be differentiated along the medial curve, which allows to define the saddle points as the local minima of Ua,b along ma,b.

In order to extract robust local minima in spite of the effect 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 fixed 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 different directions, making the curve cross itself. This distinction allows to address separately two different 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 first kind of double points, the amount of overlapping is quantified 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 configurations 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

–  –  –

Pages:   || 2 |

Similar works:

«Aegon Group Remuneration Disclosure Identified Staff 2013 Dutch Regulation on Sound Remuneration The Hague, July 2014 aegon.com Table of Content Qualitative Report 2 1. Introduction and Scope 2 2. Global Remuneration Framework 2 3. General Compensation Practices 2 3.1. Circuit breaker 3 3.2. Claw-Back provision 3 4. Governance 3 4.1. Supervisory Board and Compensation Committee 3 4.2. Remuneration Steering Committee 4 4.3. Role of Control Functions 4 4.4. Remuneration Framework and risk 5 4.5....»

«Austin Center for Events 2013 Progress Report Austin Center for Events Progress Report Table of Contents I. Introduction 3 II. Austin Center for Events Overview 4 III. Outreach Overview _ 5 IV. Action Steps _ 7 Appendices Music Commission Resolution _ A City Council Resolution _ B Public Feedback Summary _ C Event-Related Ordinances _ D Event-Related Deadlines E Draft Comprehensive Application _ F Proposed Application Process G 2 Introduction E ffective special event management is...»

«Raising the Greatest Generation of Missionaries ELDER M. RUSSELL BALLARD Of the Quorum of the Twelve Apostles This address was given, May 2, 2003 at the BYU Women’s Conference © 2003 by Brigham Young University, Women’s Conference All rights reserved.For further information write: BYU Women’s Conference, 352 Harman Continuing Education Building, Provo, Utah 84602. (801) 422-7692 E-mail: womens_conference@byu.edu Home page: http://womensconference.byu.edu It’s wonderful to be here this...»

«Comments from Bart Herbison Executive Director Nashville Songwriters Association International on Review ofASCAP and BMI Consent Decrees before the United States Department of Justice Antitrust Division August 5, 2014 FOREWORD My name is Bart Herbison, Executive Director of the Nashville Songwriters Association International (NSAI). When I accepted this position in 1997 the songwriting profession in Nashville and around the United States was at its apex. There were several thousand professional...»

«ETSI TS 103 127 V1.1.1 (2013-05) Technical Specification Digital Video Broadcasting (DVB); Content Scrambling Algorithms for DVB-IPTV Services using MPEG2 Transport Streams 2 ETSI TS 103 127 V1.1.1 (2013-05) Reference DTS/JTC-DVB-322 Keywords DVB ETSI 650 Route des Lucioles F-06921 Sophia Antipolis Cedex FRANCE Tel.: +33 4 92 94 42 00 Fax: +33 4 93 65 47 16 Siret N° 348 623 562 00017 NAF 742 C Association à but non lucratif enregistrée à la Sous-Préfecture de Grasse (06) N° 7803/88...»

«Tab B, No. 4(b) Allocation Analysis of the Gulf of Mexico Gag and Red Grouper Fisheries Prepared for: Coastal Conservation Association By: Brad Gentner Principal Gentner Consulting Group Table of Contents EXECUTIVE SUMMARY INTRODUCTION ECONOMICS OF ALLOCATION TRENDS IN THE RECREATIONAL FISHERY RECREATIONAL VALUATION METHODOLOGY Nested Logit Data Manipulation Expected Keep Rates Results ESTIMATES OF MARGINAL VALUES OF GROUPER ECONOMIC IMPACTS DISCUSSION REFERENCES 2 Executive Summary Grouper...»

«Thinning Practice A Silvicultural Guide By Gary Kerr and Jens Haufe Version 1.0 January 2011 Thinning Practice A Silvicultural Guide Contents 1. Introduction 1.1 Why thin? – Thinning and management objectives. 5 1.2 What type of stand will be thinned? 1.3 Thinning practice and yield models 2. Some terms explained 3. Silviculture of thinning (even-aged stands) 3.1 Understanding thinning 3.2 Different types of tree 3.3 Response of individual trees to thinning 3.4 Stocking 3.5 Systematic and...»

«SPECIAL PUBLIC MEETING AGENDA JULY 20, 2015 1. Salute to the Flag 2. Presiding Officer’s Meeting Notice Statement “I hereby call to order the Special Public Meeting of the Teaneck Board of Education, held on Monday, July 20, 2015, in the Eugene Field Administration Building’s, Margaret Angeli Staff Development Room. Adequate notice of this meeting has been sent to the Record, the Suburbanite, filed with the Municipal Clerk of the Township of Teaneck, and posted inside the Teaneck Board of...»


«15 minutes a day to building Speech and speechreading skills with deaf and hard-of-hearing students Created for the interpreter, speech aid, or parent By Michelle Radin of the Special Education Service Agency With a special thanks to Kim Ward, Krista Galyen, Joyce Dale, and Patricia McDaid WHO ARE THESE LESSONS FOR? WHO ARE THESE LESSONS NOT FOR? WHERE DO I BEGIN? INTRODUCTORY LESSON: WHEN DO I USE MY VOICE? LESSON ONE: SPEECH TWINS LESSON TWO: SPEECH TWINS, YOUR TURN! LESSON THREE: LIP POPPERS...»

«Bronson, J., Levine, J. Whitaker R., Lattice Cleaving: Conforming Tetrahedral Meshes of Multimaterial Domains with Bounded Quality. Proceedings of the 21st International Meshing Roundtable (San Jose, CA, Oct 7 10, 2012), pp. 191–209. Lattice Cleaving: Conforming Tetrahedral Meshes of Multimaterial Domains with Bounded Quality Jonathan R. Bronson, Joshua A. Levine, and Ross T. Whitaker Scientific Computing and Imaging Institute, Salt Lake City, UT, U.S.A....»

«GUIDELINES PROCUREMENT UNDER IBRD LOANS AND IDA CREDITS May 2004 GUIDELINES PROCUREMENT UNDER IBRD LOANS AND IDA CREDITS May 2004 Copyright © 2004 The International Bank for Reconstruction and Development / THE WORLD BANK 1818 H Street, N.W. Washington D.C. 20433, U.S.A. First Printing April 2004 All rights reserved ISBN 0-8213-5829-4 ii I. Introduction 1.1 Purpose 1.2 General Considerations 1.5 Applicability of Guidelines 1.6 Eligibility 1.9 Advance Contracting and Retroactive Financing 1.10...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.