Flip procedure in geometric approximation of multiple-component shapes – Application to multiple-inclusion detection
The SMAI Journal of computational mathematics, Volume 2 (2016), pp. 255-276.

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.

Published online:
DOI: 10.5802/smai-jcm.16
Classification: 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

Pierre Bonnelie 1; Loïc Bourdin 1; Fabien Caubet 2; Olivier Ruatta 1

1 Institut de recherche XLIM. Pôle Mathématiques-Informatique-Image. UMR CNRS 7252. Université de Limoges, France.
2 Institut de Mathématiques de Toulouse. UMR CNRS 5219. Université de Toulouse, France.
@article{SMAI-JCM_2016__2__255_0,
     author = {Pierre Bonnelie and Lo{\"\i}c Bourdin and Fabien Caubet and Olivier Ruatta},
     title = {Flip procedure in geometric approximation of multiple-component shapes {\textendash} {Application} to multiple-inclusion detection},
     journal = {The SMAI Journal of computational mathematics},
     pages = {255--276},
     publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
     volume = {2},
     year = {2016},
     doi = {10.5802/smai-jcm.16},
     zbl = {1416.65417},
     mrnumber = {3633552},
     language = {en},
     url = {https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.16/}
}
TY  - JOUR
AU  - Pierre Bonnelie
AU  - Loïc Bourdin
AU  - Fabien Caubet
AU  - Olivier Ruatta
TI  - Flip procedure in geometric approximation of multiple-component shapes – Application to multiple-inclusion detection
JO  - The SMAI Journal of computational mathematics
PY  - 2016
SP  - 255
EP  - 276
VL  - 2
PB  - Société de Mathématiques Appliquées et Industrielles
UR  - https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.16/
DO  - 10.5802/smai-jcm.16
LA  - en
ID  - SMAI-JCM_2016__2__255_0
ER  - 
%0 Journal Article
%A Pierre Bonnelie
%A Loïc Bourdin
%A Fabien Caubet
%A Olivier Ruatta
%T Flip procedure in geometric approximation of multiple-component shapes – Application to multiple-inclusion detection
%J The SMAI Journal of computational mathematics
%D 2016
%P 255-276
%V 2
%I Société de Mathématiques Appliquées et Industrielles
%U https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.16/
%R 10.5802/smai-jcm.16
%G en
%F SMAI-JCM_2016__2__255_0
Pierre Bonnelie; Loïc Bourdin; Fabien Caubet; Olivier Ruatta. Flip procedure in geometric approximation of multiple-component shapes – Application to multiple-inclusion detection. The SMAI Journal of computational mathematics, Volume 2 (2016), pp. 255-276. doi : 10.5802/smai-jcm.16. https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.16/

[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, Volume 8 (2007) no. 2, p. 389-416 (electronic) | DOI | MR | Zbl

[2] G. Allaire; C. Dapogny; P. Frey Shape optimization with a level set based mesh evolution method, Comput. Methods Appl. Mech. Engrg., Volume 282 (2014), pp. 22-53 https://dx-doi-org.docadis.ups-tlse.fr/10.1016/j.cma.2014.08.028 | DOI | MR | Zbl

[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., Volume 34 (2005) no. 1, pp. 59-80 | MR | Zbl

[4] H. Ammari; H. Kang Reconstruction of small inhomogeneities from boundary measurements, Lecture Notes in Mathematics, 1846, Springer-Verlag, Berlin, 2004, x+238 pages https://dx-doi-org.docadis.ups-tlse.fr/10.1007/b98245 | DOI | MR | Zbl

[5] M. Badra; F. Caubet; M. Dambrine Detecting an obstacle immersed in a fluid by shape optimization methods, Math. Models Methods Appl. Sci., Volume 21 (2011) no. 10, pp. 2069-2101 | DOI | MR | Zbl

[6] E. Bishop A generalization of the Stone-Weierstrass theorem., Pacific J. Math., Volume 11 (1961) no. 3, pp. 777-783 http://projecteuclid.org/euclid.pjm/1103037116 | DOI | MR | Zbl

[7] L. Bourgeois; J. Dardé A quasi-reversibility approach to solve the inverse obstacle problem, Inverse Probl. Imaging, Volume 4 (2010) no. 3, pp. 351-377 | DOI | MR

[8] M. Burger; B. Hackl; W. Ring Incorporating topological derivatives into level set methods, J. Comput. Phys., Volume 194 (2004) no. 1, pp. 344-362 | DOI | MR | Zbl

[9] M. Burger; S. J. Osher A survey on level set methods for inverse problems and optimal design, European J. Appl. Math., Volume 16 (2005) no. 2, pp. 263-301 https://dx-doi-org.docadis.ups-tlse.fr/10.1017/S0956792505006182 | DOI | MR | Zbl

[10] F. Caubet Instability of an inverse problem for the stationary Navier-Stokes equations, SIAM J. Control Optim., Volume 51 (2013) no. 4, pp. 2949-2975 https://dx-doi-org.docadis.ups-tlse.fr/10.1137/110836857 | DOI | MR | Zbl

[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, Volume 10 (2016) no. 2, pp. 327-367 | DOI | MR | Zbl

[12] F. Caubet; M. Dambrine Localization of small obstacles in Stokes flow, Inverse Problems, Volume 28 (2012) no. 10, 105007 pages http://stacks.iop.org/0266-5611/28/i=10/a=105007 | DOI | MR | Zbl

[13] F. Caubet; M. Dambrine; D. Kateb Shape optimization methods for the inverse obstacle problem with generalized impedance boundary conditions, Inverse Problems, Volume 29 (2013) no. 11, 115011, 26 pages | DOI | MR | Zbl

[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, Volume 7 (2013) no. 1, pp. 123-157 https://dx-doi-org.docadis.ups-tlse.fr/10.3934/ipi.2013.7.123 | DOI | MR | Zbl

[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, Volume 49 (2014) no. 3, pp. 387-399 | DOI | MR

[16] D. Colton; R. Kress Inverse acoustic and electromagnetic scattering theory, Applied Mathematical Sciences, 93, Springer-Verlag, Berlin, 1998, xii+334 pages | DOI | MR | Zbl

[17] J. Dardé Quasi-reversibility and level set methods applied to elliptic inverse problems, Université Paris-Diderot - Paris VII, December (2010) https://pastel.archives-ouvertes.fr/tel-00551853 (Theses)

[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

[20] P.J. Frey; P.L. George Mesh Generation: Application to Finite Elements, Second Edition, Wiley-ISTE, 2008

[21] S. Garreau; P. Guillaume; M. Masmoudi The topological asymptotic for PDE systems: the elasticity case, SIAM J. Control Optim., Volume 39 (2001) no. 6, p. 1756-1778 (electronic) https://dx-doi-org.docadis.ups-tlse.fr/10.1137/S0363012900369538 | DOI | MR | Zbl

[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, xii+334 pages | Zbl

[24] V. Isakov Inverse problems for partial differential equations, 127, Springer Science & Business Media, 2006 | MR | Zbl

[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)

[27] A. Marco; J.-J. Martínez A fast and accurate algorithm for solving Bernstein–Vandermonde linear systems, Linear Algebra and its Applications, Volume 422 (2007) no. 2, pp. 616 -628 http://www.sciencedirect.com/science/article/pii/S0024379506005210 | DOI | MR | Zbl

[28] J. O’Rourke Computational Geometry in C, Cambridge University Press, New York, NY, USA, 1998 | Zbl

[29] O. Pantz; K. Trabelsi Simultaneous shape, topology, and homogenized properties optimization, Struct. Multidiscip. Optim., Volume 34 (2007) no. 4, pp. 361-365 | DOI | MR | Zbl

[30] P.-O. Persson Mesh Generation for Implicit Geometries, Massachusetts Institute of Technology (USA), Cambridge, MA, USA (2005) (Ph. D. Thesis AAI0807802) | MR

[31] T.D.M. Pjan 3D Free Form Method and Applications to Robotics, University of Limoges (2014) (Masters thesis http://www.unilim.fr/pages_perso/olivier.ruatta/pub/stage.pdf)

[32] F. Santosa A level-set approach for inverse problems involving obstacles., ESAIM, Control Optim. Calc. Var., Volume 1 (1996), pp. 17-33 | DOI | Numdam | Zbl

[33] A. Schumacher Topologieoptimisierung von Bauteilstrukturen unter Verwendung von Lopchpositionierungkrieterien, Universität-Gesamthochschule-Siegen (1995) (Ph. D. Thesis)

[34] T. W. Sederberg Computer aided geometric design, 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, xx + 378 pages | Zbl

[36] J. Sokołowski; A. Żochowski On the topological derivative in shape optimization, SIAM J. Control Optim., Volume 37 (1999) no. 4, p. 1251-1272 (electronic) | DOI | MR | Zbl

[37] J. Sokołowski; J.-P. Zolésio Introduction to shape optimization, Springer Series in Computational Mathematics, 16, Springer-Verlag, Berlin, 1992, ii+250 pages (Shape sensitivity analysis) | MR

Cited by Sources: