On geometry and deformation of shapes represented by piecewise continuous Bézier curves with application to shape optimization

28/08/2013
Auteurs : Olivier Ruatta
OAI : oai:www.see.asso.fr:2552:4902
DOI :

Résumé

On geometry and deformation of shapes represented by piecewise continuous Bézier curves with application to shape optimization

Média

Voir la vidéo

Métriques

101
13
639.21 Ko
 application/pdf
bitcache://16af68d77a1276a29b09a6b8f3ac0c8db74df532

Licence

Creative Commons Aucune (Tous droits réservés)

Sponsors

Sponsors scientifique

logo_smf_cmjn.gif

Sponsors financier

logo_gdr-mia.png
logo_inria.png
image010.png
logothales.jpg

Sponsors logistique

logo-minesparistech.jpg
logo-universite-paris-sud.jpg
logo_supelec.png
Séminaire Léon Brillouin Logo
logo_cnrs_2.jpg
logo_ircam.png
logo_imb.png
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/2552/4902</identifier><creators><creator><creatorName>Olivier Ruatta</creatorName></creator></creators><titles>
            <title>On geometry and deformation of shapes represented by piecewise continuous Bézier curves with application to shape optimization</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2013</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Tue 17 Sep 2013</date>
	    <date dateType="Updated">Wed 31 Aug 2016</date>
            <date dateType="Submitted">Fri 10 Aug 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">16af68d77a1276a29b09a6b8f3ac0c8db74df532</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>25040</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

On the geometry and the deformation of shapes represented by piecewise continuous Bézier curves with application to shape optimization Olivier Ruatta XLIM, UNR 7252 Université de Limoges CNRS Geometric Science of Information 2013 Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 1 / 32 Motivation: Shapes optimisation problems Let Ω ⊂ P R2 such that for each ω ∈ Ω the frontier ∂ω of this "region" is a regular curve (i.e. piecewise continuous here). Let F : Ω −→ R+ be a positive real valued function. Problem Find ω0 ∈ Ω such that F(ω0) ≤ F(ω) for all ω ∈ Ω. Very often, the computation of F(ω) requires to solve a system of PDE. Two problems : The cost of the computation of F(ω) and its differentiability (and computation of derivatives also). Compatibility of the space of shape and discretization of R2 for the system of PDE. Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 2 / 32 Shapes optimization problems R+ M ∂ω F F(ω) ω Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 3 / 32 Shapes optimization methods Geometric gradient techniques (level sets, . . .) : compute how to deform the frontier of the shape and try to deform in a coherent way [Hadamard, Pierre, Henrot, Allaire, Jouve, . . .]. Relaxation method (SIMP, . . .) : compute a density that represent the support of the shape [Bensœ,Sigmund, . . .]. Topologic gradient : generally for PDEs, remove or add finites elements contening the shape [Masmoudi, Sokolowski, . . .]. Parametric optimization : reduce the shapes to a little space controlled by few parameters and look the problem as a parametric optimization problem [Elyssa (Didon in latin, 4 century before J.-C.),. . .,Goldberg,. . .]. Our approach : try to mix the best aspects of the first (level sets) and the last (parametric) approaches. Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 4 / 32 Bézier curves Let P0, . . . , Pd ∈ R2, we define a family of curves parametrized over [0, 1] : B([P0], t) := P0 (degree 0 Bézier curve). B([P0, P1], t) := (1 − t)B([P0], t) + tB([P1], t) = (1 − t)P0 + tP1 (degree 1 Bézier curve) . . . B([P0, . . . , Pd ], t) := (1 − t)B([P0, . . . , Pd−1], t) + tB([P1, . . . , Pd ], t) (degree d Bézier curve). Those are polynomial curves. The points P0, . . . , Pd ∈ R2 are called the control polygon of the curve defined by B([P0, . . . , Pd ], t). Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 5 / 32 Bézier curves P0 P1 P2 P3 Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 6 / 32 Bernstein polynomials Definition Let d be a positive integer, for all i ∈ {0, . . . , d} we define: bi,d (t) = d i (1 − t)d−i ti . The polynomials b0,d , . . . , bd,d are called the Bernstein polynomials of degree d. Proposition The Bernstein polynomials of degree d, b0,d , . . . , bd,d , form a basis of the vector space of polynomials of degree less or equal to d. Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 7 / 32 Bernstein polynomials and Bézier curves Theorem B([P0, . . . , Pd ], t) = d i=0 Pibi,d (t) Corollary Every parametrized curve with polynomial parametrization of degree at most can be represented as a Bézier curve of degree at most d. Definition We define Bd the space of all Bézier curves of degree at most d. Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 8 / 32 Structure of Bd We denote E = R2 and we consider the following map: Ψd : Ed+1 −→ Bd defined by Ψd (P0, . . . , Pd ) = B([P0, . . . , Pd ], t). Proposition Ψd is a linear isomorphism between Ed+1 and Bd . Let t = t0 = 0 < t1 < · · · < td = 1 be a subdivision of [0, 1]. We define the sampling map: St,d : Γ(t) ∈ Bd −→ (Γ(t0), · · · , Γ(td )) ∈ Ed+1 . Proposition St,d is a linear isomorphism between Bd and Ed+1. Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 9 / 32 Evaluation-Interpolation Let t = t0 = 0 ≤ t1 ≤ · · · ≤ td = 1 be a subdivision of [0, 1] and let P0, . . . , Pd ∈ E. Bt,d :=    b0,d (t0) · · · bd,d (t0) ... ... ... b0,d (td ) · · · bd,d (td )    . Proposition (Evaluation) Bt,d    PT 0 ... PT d    =    B([P0, . . . , Pd ], t0)T ... B([P0, . . . , Pd ], td )T    . Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 10 / 32 Multi-evaluation t = (0, 1/3, 2/3, 1),     MT 0 MT 1 MT 2 MT 3     = Bt,3     PT 0 PT 1 PT 2 PT 3     P0 P1 P2 P3 M0 M1 M2 M3 Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 11 / 32 Evaluation-Interpolation Let t = t0 = 0 ≤ t1 ≤ · · · ≤ td = 1 be a subdivision of [0, 1] and let M0, . . . , Md ∈ E. Problem Find P0, . . . , Pd ∈ E such that B([P0, . . . , Pd ], ti) = Mi for all i ∈ {0, . . . , d}. Proposition (Interpolation) The points defined by:    PT 0 ... PT d    = B−1 t,d    B([P0, . . . , Pd ], t0)T ... B([P0, . . . , Pd ], td )T    solve the problem. Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 12 / 32 Summary 1 We have 3 spaces: Pd Ed+1 the vector space of the control polygons, St,d Ed+1 the vector space of the sampling of Bézier curves associated to a subdivision t, Bd the vector space of the degree d Bézier parametrizations. Proposition The following diagram of isomorphisms is commutative: Pd Ψd −→ Bd Bt,d ↓ Et,d St,d . Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 13 / 32 Deformation problem Let Γ(t) := B([P0, . . . , Pd ], t) be a degree d Bézier curve s.t. Et,d (Γ) = M =    MT 0 ... MT d    and let δM :=    δMT 0 ... δMT d    ∈ TMSt,d , we consider the following problem: Problem (Deformation problem) Denoting P =    PT 0 ... PT d    find δP ∈ TPPd such that Λ(t) := B([P0 + δP0, . . . , Pd + δPd ], t) satisfies Λ(ti) = Mi + δMi for all i ∈ {0, . . . , d}. Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 14 / 32 Deformation problem P1 P2 P3 M0 M1 M2 M3 P0 δM0 δM1 δM2 δM3 Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 15 / 32 Deformation curve Proposition (Deformation polygon) Taking δP = B−1 t,d δM, the curve Ψd (P + δP) is a solution of the "Deformation problem". δP ∈ TPPd is called the deformation polygon and Ψd (δP) ∈ TB([P0,...,Pd ],t)Bd is called the deformation curve. Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 16 / 32 Piecewize Bézier curves Let P1 := (P1,0, . . . , P1,d ) ∈ Pd , P2 := (P2,0, . . . , P2,d ) ∈ Pd , . . . and PN := (PN,0, . . . , PN,d ) ∈ Pd be such that P1,d = P2,0, . . . , PN−1,d = PN,0. We define the following parametrization: B((P1, . . . , PN), t) =    B([P1,0, . . . , P1,d ], N ∗ t) if t ∈ [0, 1/N[ B([P2,0, . . . , P2,d ], N ∗ t − 1) if t ∈ [1/N, 2/N[ ... B([PN,0, . . . , PN,d ], N ∗ t − (N − 1)) if t ∈ [N−1 N , N] We denote Ψ(P1, . . . , PN) := B((P1, . . . , PN), t). This is a continuous curve joining P1,0 to PN,d and the curve is a loop if P1,0 = PN,d . Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 17 / 32 Piecewize Bézier curves P1,3 = P2,0 P1,0 P1,1 P1,2 P2,1 P2,2 P2,3 Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 18 / 32 Vector space of Piecewize Bézier curves We define : The vector space PN,d = {(P1, . . . , PN)|P1,d = P2,0, . . . , PN−1,d = PN,0} ⊂ PN d . The vector space LN,d = {(P1, . . . , PN)|P1,d = P2,0, . . . , PN−1,d = PN,0, P1,0 = PN,d } ⊂ PN d . The vector space of PBC BN,d = {B((P1, . . . , Pd ), t)|(P1, . . . , Pd ) ∈ PN,d }. The vector space of PBL Bc N,d = {B((P1, . . . , Pd ), t)|(P1, . . . , Pd ) ∈ LN,d }. Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 19 / 32 Sampling piecewize Bézier curves Let t = (t1,0 := 0, t1,1 := 1 N∗d , . . . , t1,d := 1 N , t2,0 = 1 N , . . . , tN−1,d := N−1 N , tN,0 := N−1 N , . . . , tN,d := 1) be a multi-regular subdivision and denote ti := (ti,0, . . . , ti,d ). We define the following linear map: Et,N,d : λ(t) ∈ BN,d −→ (λ(t1,0), . . . , λ(tN,d )) ∈ St,N,d ⊂ SN d The same way we define: Ec t,N,d : λ(t) ∈ Bc N,d −→ (λ(t1,0), . . . , λ(tN,d )) ∈ Sc t,N,d ⊂ SN d Finally, we define: Bt,N,d : (P1,0, . . . , PN,d ) ∈ PN,d −→ Bt1,d × · · · × BtN ,d    PT 1,0 ... PT N,d    ∈ St,N,d . Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 20 / 32 Summary 2 Proposition The following diagram of isomorphisms is commutative: PN,d ΨN,d −→ BN,d Bt,N,d ↓ Et,N,d St,N,d . Remark B−1 t,N,d := B−1 t1,d × · · · × B−1 tN ,d Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 21 / 32 Deformation problem for PBC Let Γ(t) ∈ BN,d be s.t. Et,N,d (Γ) = M :=    MT 1,0 ... MT N,d    ∈ St,N,d and let δM =    δMT 1,0 ... δMT N,d    ∈ TMSt,N,d , we consider the following problem: Problem (Deformation problem for PBC) Denoting P =    PT 1,0 ... PT N,d    find δP ∈ TPPN,d such that Λ(t) := B((P0 + δP0, . . . , Pd + δPd ), t) satisfies Λ(ti,j) = Mi,j + δMi,j for all i ∈ {1, . . . , N} and j ∈ {0, . . . , d}. Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 22 / 32 Deformation Piecewize Bézier curve Proposition (Deformation polygons) Taking δP = B−1 t,N,d δM, the curve ΨN,d (P + δP) is a solution of the "Deformation problem for PBC". δP ∈ TPPN,d is called the deformation polygons and ΨN,d (δP) ∈ TB((P0,...,Pd ),t)BN,d is called the deformation piecewize Bézier curve. Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 23 / 32 Back to shapes optimization Let ω ⊂ E be such that ∂ω is a piecewise continuous curve and F : P(E) −→ R+ the objective functional. The geometric gradient F(ω) : M ∈ ∂ω −→ F(ω)(M) ∈ TME give a perturbation for each point of the frontier to decrease the objective functional. R+ M ∂ω F F(ω) ω F(ω)(M) Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 24 / 32 Basic idea of the approach The space of admissible shape is ΩN,d := ω ∈ P(E)|∂ω ∈ Bc N,d and let ω ∈ ΩN,d such that ∂ω = B((P1, . . . , PN), t). Let M =    MT 1,0 ... MT N,d    = Et,N,d (B((P1, . . . , PN), t), to obtain a better shape we compute δM =    F(ω)(M1,0)T ... F(ω)(MN,d )T   . Then we compute δP = B−1 t,N,d δM and let λ(t) = B((P + δP), t), we have: Proposition λ(ti,j) = Mi,j + F(ω)(Mi,j) for all i ∈ {1, . . . , N} and j ∈ {0, . . . , d}. Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 25 / 32 Basic theoretical contribution Let Ω = {ω ∈ P(E)|∂ω ∈ C0 p([0, 1], E)} and F : Ω −→ R+ be a smooth function such that F(ω) : ∂ω −→ TE is everywhere well defined. For every γ ∈ BN,d we associate "the" shape γ such that ∂γ = γ. Proposition For every N and d integer and every compatible subdivision t, we associate to F a vector field VF : BN,d −→ TBN,d by: B((P), t) −→ ΨN,d   B−1 t,N,d    ( F(B(P, t))(B((P), t1,0)))T ... ( F(B(P, t))(B((P), tN,d )))T       . Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 26 / 32 Optimal shapes and fixed points Proposition Let ω ∈ Ω such that F(ω) ≡ 0 then, for all N and d and every compatible subdivision t there is γ ∈ BN,d satisfying VF (γ) = 0. In other words, every optimum of F induce at list a fixed point of VF over BN,d . Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 27 / 32 Meta-algorithm for shapes optimization Input: An initial shape ω s.t. ∂ω = B((P), t) ∈ BN,d Output: The control polygon P a the frontier of a local minimum of F(ω). λ ← B((P), t) while criterium not satified do δP ← B−1 t,N,d (Et,N,d (λ)) P ← P + δP λ ← ΨN,d (P) end while Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 28 / 32 Snake-like algorithm for omnidirectional images segmentation Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 29 / 32 Snake-like algorithm for omnidirectional images segmentation Image segmentation can be interpreted as a shapes optimization problem using "snake-approach". The geometric gradient is built from: a "balloon" force making the contour expand, the gradient of the intensity of the image (vanishing at the contours). We use a classical approach: Canny filter to detect contours. This problem is used to detect free space for an autonomous robot with a catadioptric sensor. Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 30 / 32 Snake-like algorithm for classical images segmentation Joint work with Ouiddad Labbani-I. and Pauline Merveilleux-O. of "Université de Picardie - Jules Vernes". Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 31 / 32 Snake-like algorithm for omnidirectional images segmentation Joint work with Ouiddad Labbani-I. and Pauline Merveilleux-O. of "Université de Picardie - Jules Vernes". Ruatta (XLIM) Free Forms for Shapes Optimisation GSI 2013 32 / 32