With cedram.org   version française
Search for an article
Table of contents for this volume | Previous article | Next article
Pierre Bonnelie; Loïc Bourdin; Fabien Caubet; Olivier Ruatta
Flip procedure in geometric approximation of multiple-component shapes – Application to multiple-inclusion detection
SMAI-Journal of computational mathematics, 2 (2016), p. 255-276, doi: 10.5802/smai-jcm.16
Article PDF
Class. Math.: 68U05, 68W25, 49Q10, 65N21
Keywords: Shape approximation; free-form shapes; multiple-component shapes; Bézier curves; intersecting control polygons detection; flip procedure; inverse obstacle problem; shape optimization


We are interested in geometric approximation by parameterization of two-dimensional multiple-component shapes, in particular when the number of components is a priori unknown. Starting a standard method based on successive shape deformations with a one-component initial shape in order to approximate a multiple-component target shape usually leads the deformation flow to make the boundary evolve until it surrounds all the components of the target shape. This classical phenomenon tends to create double points on the boundary of the approximated shape.

In order to improve the approximation of multiple-component shapes (without any knowledge on the number of components in advance), we use in this paper a piecewise Bézier parameterization and we consider two procedures called intersecting control polygons detection and flip procedure. The first one allows to prevent potential collisions between two parts of the boundary of the approximated shape, and the second one permits to change its topology by dividing a one-component shape into a two-component shape.

For an experimental purpose, we include these two processes in a basic geometrical shape optimization algorithm and test it on the classical inverse obstacle problem. This new approach allows to obtain a numerical approximation of the unknown inclusion, detecting both the topology (i.e. the number of connected components) and the shape of the obstacle. Several numerical simulations are performed.


[1] L. Afraites, M. Dambrine, K. Eppler & D. Kateb, “Detecting perfectly insulated obstacles by shape optimization techniques of order two”, Discrete Contin. Dyn. Syst. Ser. B 8 (2007) no. 2, p. 389-416 (electronic) Article |  MR 2317815 |  Zbl 1128.49034
[2] G. Allaire, C. Dapogny & P. Frey, “Shape optimization with a level set based mesh evolution method”, Comput. Methods Appl. Mech. Engrg. 282 (2014), p. 22-53 Article |  MR 3269890
[3] G. Allaire, F. de Gournay, F. Jouve & A.-M. Toader, “Structural optimization using topological and shape sensitivity via a level set method”, Control Cybernet. 34 (2005) no. 1, p. 59-80  MR 2211063 |  Zbl 1167.49324
[4] H. Ammari & H. Kang, Reconstruction of small inhomogeneities from boundary measurements, Lecture Notes in Mathematics 1846, Springer-Verlag, Berlin, 2004 Article |  MR 2168949 |  Zbl 1113.35148
[5] M. Badra, F. Caubet & M. Dambrine, “Detecting an obstacle immersed in a fluid by shape optimization methods”, Math. Models Methods Appl. Sci. 21 (2011) no. 10, p. 2069-2101 Article |  MR 2851707 |  Zbl 1239.35182
[6] E. Bishop, “A generalization of the Stone-Weierstrass theorem.”, Pacific J. Math. 11 (1961) no. 3, p. 777-783 Article |  MR 133676 |  Zbl 0104.09002
[7] L. Bourgeois & J. Dardé, “A quasi-reversibility approach to solve the inverse obstacle problem”, Inverse Probl. Imaging 4 (2010) no. 3, p. 351-377 Article |  MR 2671101 |  Zbl 1200.35318
[8] M. Burger, B. Hackl & W. Ring, “Incorporating topological derivatives into level set methods”, J. Comput. Phys. 194 (2004) no. 1, p. 344-362 Article |  MR 2033389 |  Zbl 1044.65053
[9] M. Burger & S. J. Osher, “A survey on level set methods for inverse problems and optimal design”, European J. Appl. Math. 16 (2005) no. 2, p. 263-301 Article |  MR 2155293 |  Zbl 1091.49001
[10] F. Caubet, “Instability of an inverse problem for the stationary Navier-Stokes equations”, SIAM J. Control Optim. 51 (2013) no. 4, p. 2949-2975 Article |  MR 2987910 |  Zbl 1253.76030
[11] F. Caubet, C. Conca & M. Godoy, “On the detection of several obstacles in 2D Stokes flow: topological sensitivity and combination with shape derivatives”, Inverse Probl. Imaging 10 (2016) no. 2, p. 327-367 Article |  MR 3079313 |  Zbl 1291.35439
[12] F. Caubet & M. Dambrine, “Localization of small obstacles in Stokes flow”, Inverse Problems 28 (2012) no. 10 Article |  MR 3507898
[13] F. Caubet, M. Dambrine & D. Kateb, “Shape optimization methods for the inverse obstacle problem with generalized impedance boundary conditions”, Inverse Problems 29 (2013) no. 11 Article |  MR 3116347 |  Zbl 1292.65069
[14] F. Caubet, M. Dambrine, D. Kateb & C. Z. Timimoun, “A Kohn-Vogelius formulation to detect an obstacle immersed in a fluid”, Inverse Probl. Imaging 7 (2013) no. 1, p. 123-157 Article |  MR 3031841 |  Zbl 1266.49076
[15] A. N. Christiansen, M. Nobel-Jørgensen, N. Aage, O. Sigmund & J. A. Bærentzen, “Topology optimization using an explicit interface representation”, Structural and Multidisciplinary Optimization 49 (2014) no. 3, p. 387-399 Article |  MR 3175117
[16] D. Colton & R. Kress, Inverse acoustic and electromagnetic scattering theory, Applied Mathematical Sciences 93, Springer-Verlag, Berlin, 1998 Article |  MR 1635980 |  Zbl 0760.35053
[17] J. Dardé, Quasi-reversibility and level set methods applied to elliptic inverse problems, Theses, Université Paris-Diderot - Paris VII, 2010
[18] C. Ericson, Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology) (The Morgan Kaufmann Series in Interactive 3D Technology), Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2004
[19] G. Farin, Curves and Surfaces for CAGD: A Practical Guide, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2002  Zbl 0848.68112
[20] P.J. Frey & P.L. George, Mesh Generation: Application to Finite Elements, Second Edition, Wiley-ISTE, 2008  MR 2398720 |  Zbl 1156.65018
[21] S. Garreau, P. Guillaume & M. Masmoudi, “The topological asymptotic for PDE systems: the elasticity case”, SIAM J. Control Optim. 39 (2001) no. 6, p. 1756-1778 (electronic) Article |  MR 1825864 |  Zbl 0990.49028
[22] F. Hecht, “Finite Element Library Freefem++.”, http://www.freefem.org/ff++/
[23] A. Henrot & M. Pierre, Variation et optimisation de formes : Une analyse géométrique., Mathématiques & Applications (Berlin) [Mathematics & Applications] 48, Springer, Berlin, 2005  MR 2512810 |  Zbl 1098.49001
[24] V. Isakov, Inverse problems for partial differential equations 127, Springer Science & Business Media, 2006  MR 2193218 |  Zbl 1092.35001
[25] S. Kichenassamy, A. Kumar, P. Olver, A. Tannenbaum & A. Yezzi Jr., “Gradient Flows and Geometric Active Contour Models” 1994
[26] O. Labbani-I., P. Merveilleux-O. & O. Ruatta, “Free Form based active contours for image segmentation and free space perception”, preprint  MR 2305145 |  Zbl 1116.65038
[27] A. Marco & J.-J. Martínez, “A fast and accurate algorithm for solving Bernstein–Vandermonde linear systems”, Linear Algebra and its Applications 422 (2007) no. 2, p. 616 -628 Article
[28] J. O’Rourke, Computational Geometry in C, Cambridge University Press, New York, NY, USA, 1998  MR 1649008 |  Zbl 0912.68201
[29] O. Pantz & K. Trabelsi, “Simultaneous shape, topology, and homogenized properties optimization”, Struct. Multidiscip. Optim. 34 (2007) no. 4, p. 361-365 Article |  MR 2348166 |  Zbl 1273.74391
[30] P.-O. Persson, Mesh Generation for Implicit Geometries, Ph. D. Thesis, Massachusetts Institute of Technology (USA), AAI0807802, 2005  MR 2717235
[31] T.D.M. Pjan, 3D Free Form Method and Applications to Robotics, Masters thesis, University of Limoges, 2014
[32] F. Santosa, “A level-set approach for inverse problems involving obstacles.”, ESAIM, Control Optim. Calc. Var. 1 (1996), p. 17-33 Numdam |  MR 1382514 |  Zbl 0870.49016
[33] A. Schumacher, Topologieoptimisierung von Bauteilstrukturen unter Verwendung von Lopchpositionierungkrieterien, Ph. D. Thesis, Universität-Gesamthochschule-Siegen, 1995
[34] T. W. Sederberg, “Computer aided geometric design”, October 2014
[35] J. A. Sethian, Level set methods and fast marching methods. Evolving interfaces in computational geometry, fluid mechanics, computer vision, and materials science., Cambridge: Cambridge University Press, 1999  MR 1700751 |  Zbl 0973.76003
[36] J. Sokołowski & A. Żochowski, “On the topological derivative in shape optimization”, SIAM J. Control Optim. 37 (1999) no. 4, p. 1251-1272 (electronic) Article |  Zbl 0940.49026
[37] J. Sokołowski & J.-P. Zolésio, Introduction to shape optimization, Springer Series in Computational Mathematics 16, Springer-Verlag, Berlin, 1992, Shape sensitivity analysis  MR 1215733 |  Zbl 0761.73003