Méthodes d’optimisation pour l’analyse de processus invariants d’échelle

Méthodes d’optimisation pour l’analyse de processus invariants d’échelle

Segmentation vectorielle par approche TV (2D)

Dans cette section, nous considérons le cas bidimensionnel o`u z ∈ R |Ω| désigne une image avec un total de |Ω| pixels. Par analogie avec la Section 3.3, nous pouvons estimer (C1,j )j∈Z et (C2,j )j∈Z localement dans le voisinage de chaque pixel ℓ, concevoir les estimateurs locaux cb1 et cb2, puis appliquer un procédé de segmentation vectorielle de (cb1, cb2). Cependant, cette méthode repose sur l’hypoth`ese forte que les textures ou les signaux issus du monde réel suivent précisément le comportement d’échelle prescrit à la Proposition 1.3. Dans cette section, nous choisissons de relˆacher cette contrainte et de segmenter directement les quantités vectorielles Cb1 et/ou Cb2 à travers les échelles. Dans la suite, nous considérons la quantité y = (y1, . . . , yM) ⊤ ∈ RM×|Ω| pouvant soit modéliser hb (i.e., M = 1), Cb1 ou Cb2 (i.e., M = J), ou leur concaténation (Cb1, Cb2) ⊤ (i.e., M = 2J).

Segmentation vectorielle

Une extension vectorielle du Probl`eme 2.10 peut ˆetre formulée à l’aide de θ qui dépend à la fois de m ∈ {1, . . . , M} et de la partition q ∈ {1, . . . , Q + 1} de la mani`ere suivante : Probl`eme 3.2 (Probl`eme ℓ0-TV 2D vectoriel à Q niveaux). Soit une quantité y = (y1, . . . , yM) ⊤ ∈ RM×|Ω| et un ensemble de valeurs de niveaux (vq,m)1≤q≤Q,1≤m≤M avec comme convention (2D) vq,m ≤ vq+1,m. Alors le probl`eme consiste à trouver le vecteur θ = (θ1, . . . , θQ+1) ⊤ ∈ [0, 1](Q+1)×M×|Ω| tel que min θ∈[0,1](Q+1)×M×|Ω| X Q q=1 X M m=1 (θq,m − θq+1,m) ⊤(ym − vq,m) 2 + λ X M m=1 X Q q=1 TV(θq,m − θq+1,m) sujet à (∀m ∈ {1, . . . , M}) θ1,m ≡ 1, θQ+1,m ≡ 0, 1 ≥ θ2 ≥ . . . ≥ θQ ≥ 0, (3.23) avec λ ≥ 0 et o`u TV désigne la variation totale définie en (2.68). Remarque 3.2. Dans toute la suite, les niveaux vq,m ∈ R seront choisis de mani`ere équidistante entre minℓ∈Ω ym,ℓ et maxℓ∈Ω ym,ℓ. Il apparait clairement que le crit`ere (3.23) est séparable en m, et aucun couplage entre les composantes m ∈ {1, . . . , M} n’est imposé. Par conséquent, résoudre le Probl`eme 3.2 revient à trouver le meilleur étiquetage des régions (Ω1,m, . . . , ΩQ,m) indépendamment sur chacune des composantes m ∈ {1, . . . , M}. Cependant, nous devons garder à l’esprit que nous ne souhaitons pas seulement segmenter le vecteur des caractéristiques y mais nous cherchons avant tout à segmenter la texture z. En d’autre termes, nous souhaiterions obtenir un partitionnement (Ω1, . . . , ΩQ) commun à toutes les composantes (ym)1≤m≤M. Pour se faire, nous considérons l’extension du Probl`eme 2.10 au cadre vectoriel proposé dans [37] pour l’étiquetage d’images RGB (i.e., M = 3). Il repose sur l’utilisation d’une seule variable θ qui est cette fois-ci commune à toutes les composantes, i.e., θq ≡ θq,m (∀m ∈ {1, . . . , M}). Probl`eme 3.3 (Relaxation convexe du probl`eme ℓ0-TV 2D vectoriel à Q niveaux). Soit y = (y1, . . . , yM) ∈ RM×|Ω| et un ensemble de valeurs de niveaux (vq)1≤q≤Q avec comme convention vq ≤ vq+1. Alors le probl`eme consiste à trouver θ = (θ1, . . . , θQ+1) ⊤ ∈ [0, 1](Q+1)×|Ω| tel que min θ∈[0,1](Q+1)×|Ω| X Q q=1 (θq − θq+1) ⊤ X M m=1 (ym − vq,m) 2 + λ X Q q=1 TV(θq − θq+1) sujet à θ1 ≡ 1, θQ+1 ≡ 0, 1 ≥ θ2 ≥ . . . ≥ θQ ≥ 0, (3.24) avec λ ≥ 0 et o`u TV désigne la variation totale définie en (2.68). Remarque 3.3. Pour que tous les termes d’attache aux données soient du mˆeme ordre de grandeur dans le crit`ere 3.24, il est important de normaliser y composante par composante. Afin d’estimer efficacement θ, nous utilisons la stratégie algorithmique proposée dans [55] qui consiste à utiliser une méthode d’éclatement proximal couplée à une stratégie efficace pour calculer les opérateurs proximaux. Le lecteur peut se référer à [55] pour des détails quant à la stratégie algorithmique. 70

Quantification des performances Configuration expérimentale

Les performances de la solution du Probl`eme 3.3 sont évaluées sur des données synthétiques, produites numériquement par l’inclusion d’un patch 2D ΩA d’une réalisation de marche aléatoire multifractale (voir Exemple 1.2) de param`etres (c1, c2)A sur un fond ΩB de param`etres (c1, c2)B. Le fond et le patch sont normalisés afin d’assurer que la variance locale ne dépende pas de la position de l’image. Les simulations sont conduites en utilisant la transformée standard des coefficients d’ondelettes 2D avec le tenseur orthogonal produit de Daubechies à 2 moments nuls sur J = 3 échelles. Le procédé de segmentation est appliqué pour Q = 2, λ = 1 et M = J = 3. Pour chaque composante m ∈ {1, . . . M}, les (vq,m)1≤q≤Q sont initialement choisis de mani`ere équidistante entre minℓ∈Ω ym,ℓ et maxℓ∈Ω ym,ℓ. Puis, nous alternons la minimisation de (3.24) et la ré-estimation (vq,j )1≤q≤Q 5 fois. Segmentation scalaire vs. vectorielle. Considérons le patch ΩA et le fond ΩB respectivement représentés par la Figure 3.8 (b) en blanc et en noir. Une réalisation de texture multifractale par morceaux z est fournie Figure 3.8 (a) o`u les param`etres du patch sont (c1, c2)A ≡ (0.4, −0.001) et ceux du fond sont (c1, c2)B ≡ (0.5, −0.1). La segmentation scalaire de y = hb, originellement envisagée pour l’analyse des processus monofractal par morceaux [176], est illustrée par la Figure 3.8-(c)). Nous observons que segmenter hb fournit de mauvais résultats. En effet, puisque le processus z est multifractal, toutes les valeurs de régularité locale h du support de D sont présentes dans tout interval ouvert de z pour des données de taille finie. Par conséquent, l’estimation locale de h n’est pas pertinente. De plus, puisque le support de DA et DB se recouvrent, la seule quantité h ne peut pas permettre de discriminer entre ΩA et ΩB. Cette limitation démontre le besoin d’examiner des quantités multi-échelles liées au spectre multifractal, à savoir C1 et C2. En effet, les résultats de segmentation vectorielle de Cb1, Cb2 et (Cb1, Cb2) ⊤, respectivement illustrés Figure 3.8-(d), Figure 3.8-(e) et Figure 3.8-(f), montrent que le masque est cette fois-ci estimé de fa¸con satisfaisante. Performances de segmentation. Pour le mˆeme masque représenté par la Figure 3.8 (b), nous avons considéré 8 configurations reportées dans la Figure 3.9 permettant de modéliser différents écarts de c1 et c2 entre les régions ΩA et ΩB. De plus, nous avons également examiné davantage l’impact de c2 : les résultats en bleu correspondent à un spectre DB à support étendu alors que ceux en orange sont associés à un spectre DB à support serré. Les performances d’estimation sont quantifiées en termes de pixels mal classés et sont moyennés sur 20 réalisations. Sans surprise, segmenter hb offre dans chaque configuration de mauvaises performances d’estimation. Par contre, les résultats de segmentation vectorielle de Cb1, Cb2 et (Cb1, Cb2) ⊤ sont systématiquement satisfaisantes. De plus, toutes ces expériences reproduisent le comportement espéré suivant : les performances de segmentations associées à Cb1 (resp. Cb2) sont d’autant meilleures que la différence de c1 (resp. c2) entre ΩA et ΩB est grande. Cependant, une inspection plus minitieuse des résultats montre qu’une plus grande différence de c1 ne m`ene pas nécessairement à de meilleurs résultats de segmentation de Cb2, comme le montre la ligne orange dans la Figure 3.9 (graphes de gauche). Globalement, on observe que plus y est informatif (e.g., y = (Cb1, Cb2) ⊤), meilleure sera la segmentation. Finalement, il convient également de noter que la segmentation scalaire de hb est seulement 2 fois plus rapide que la segmentation vectorielle de Cb1, Cb2 ou (Cb1, Cb2) ⊤. En pratique, les simulations durent moins d’une minute par image de taille |Ω| = 29 × 2 9 pixels. (a) z multifractal par morceaux (b) Masque (c) Segmentation basée sur hb (d) Segmentation basée sur Cb1 Pixels mal classés : 29.0 % Pixels mal classés : 5.7 % (e) Segmentation basée sur Cb2 (f) Segmentation basée sur (Cb1, Cb2) Pixels mal classés : 3.0 % Pixels mal classés : 0.96 % Figure 3.8 – Illustration des résultats de segmentation conjointe. L’image ≪ multifractale par morceaux ≫ z est présentée en (a) et a été générée à partir du masque en (b). La solution du Probl`eme 3.2 pour y = hb est illustrée en (c). Les solutions du Probl`eme 3.3 pour y = Cb1, Cb2 et (Cb1, Cb2) ⊤ sont respectivement illustrées en (d), (e) et (f). 72 CHAPITRE 3. ANALYSE MULTIFRACTALE INHOMOGENE ` h -0.5 0 0.5 1 1.5 0 0.5 1 1.5 2 DA DB DB bh Cb1 Cb2 (Cb1, Cb2) Misclassification rate 0 5 10 15 20 25 30 35 40 (0.4, −0.001)A,(0.7, −0.04)B (0.4, −0.001)A,(0.7, −0.1)B h -0.5 0 0.5 1 1.5 0 0.5 1 1.5 2 DA DB DB bh Cb1 Cb2 (Cb1, Cb2) Misclassification rate 0 5 10 15 20 25 30 35 40 (0.4, −0.005)A,(0.7, −0.04)B (0.4, −0.005)A,(0.7, −0.1)B h -0.5 0 0.5 1 1.5 0 0.5 1 1.5 2 DA DB DB bh Cb1 Cb2 (Cb1, Cb2) Misclassification rate 0 5 10 15 20 25 30 35 40 (0.4, −0.001)A,(0.5, −0.04)B (0.4, −0.001)A,(0.5, −0.1)B h -0.5 0 0.5 1 1.5 0 0.5 1 1.5 2 DA DB DB bh Cb1 Cb2 (Cb1, Cb2) Misclassification rate 0 5 10 15 20 25 30 35 40 (0.4, −0.005)A,(0.5, −0.04)B (0.4, −0.005)A,(0.5, −0.1)B Figure 3.9 – Performances de segmentation conjointe. Comparaison des performances de segmentation selon le choix de la quantité y indiquée en abscisse. Chaque graphe représente deux configurations (bleu et orange) de (c1, c2) choisis sur ΩA et ΩB

Conclusion et perspectives

Ce chapitre propose une premi`ere tentative visant à analyser des processus multifractals par morceaux caractérisés par des propriétés multifractales homog`enes différentes sur plusieurs régions distinctes. Elle repose sur l’estimation locale dans une fenˆetre glissante des quantités multi-échelles c1 et c2, voire C1 et C2, impliquées dans la formulation du spectre multifractal, combinée à un procédé d’estimation ou de segmentation. L’apport des approches TV vectorielles par rapport aux approches scalaires a tout d’abord été évalué sur des signaux constants par morceaux corrompus par un bruit Gaussien. Nous avons montré que lorsque le SNR est du mˆeme ordre de grandeur sur chacune des composantes, alors les approches vectorielles bénéficient d’une erreur de Jaccard plus faible, ce qui quantifie une meilleure localisation des positions des discontinuités. Des résultats similaires ont ensuite également été obtenus pour l’analyse d’une marche aléatoire multifractale par morceaux produit synthétiquement et reproduisant un cas d’intérˆet pratique. Nous avons montré dans le cas unidimensionel que l’estimation doit ˆetre conduite dans des voisinages W de grande taille. Cependant, la corrélation (temporelle ou spatiale) de cb1, cb2, Cb1 et Cb2, inhérente à la nécessité d’estimer ces quantités dans des voisinages de taille significative, est susceptible de compliquer a priori les méthodes d’estimation et de segmentation utilisées, reposant sur une formulation par variation totale, qui sont adéquates lorsque les signaux à régulariser ne sont pas corrélés. Nous envisageons de poursuivre ce travail en modifiant les termes d’attache aux données présents dans les équations (3.21), (3.24) et (B.1) afin de prendre en compte ces corrélations. De récentes études [72, 73, 190] ont montrées l’intérˆet d’analyser les propriétés multifractales du rythme cardiaque foetal (RCF) pour caractériser l’état de santé du foetus. Nous envisageons alors la possibilité d’estimer les discontinuités de (cb1, cb2) ⊤ comme un moyen de quantifier l’évolution de la santé du foetus au cours du temps. Afin d’offrir une estimation des discontinuités au fur et à mesure de l’acquisition du RCF, nous proposons dans le chapitre suivant une solution algorithmique permettant de fournir une solution approchée du Probl`eme 3.1 à la volée. Le procédé de segmentation proposé au Probl`eme 3.3 démontre des performances tr`es satisfaisantes mais repose sur la forte hypoth`ese que θq ≡ θq,m (∀m ∈ {1, . . . , M}). D’un cˆoté, cela a l’avantage de définir des partitions (Ω1, . . . , ΩQ) communes à toutes les M composantes. De l’autre cˆoté, cela implique que les performances sont tr`es sensibles au choix arbitraire et à l’ordre des niveaux vq,m. Afin de pallier cette limitation, différents termes de régularisation sont actuellement envisagés pour permettre une stratégie de segmentation plus flexible. Un premier pas dans cette direction peut par exemple ˆetre lié à l’utilisation du tenseur de structure de la variation totale, dont la méthode est décrite dans l’Annexe B, qui permet d’introduire des corrélations entre les composantes sans toutefois permettre une segmentation conjointe

Table des matières

Introduction
I Etat de l’art
1 Analyse multifractale homogène
1.1 Invariance d’échelle et autosimilarité
1.2 Analyse multifractale
1.2.1 Exposant de H¨older
1.2.2 Spectre multifractal
1.3 Formalisme multifractal
1.3.1 Fonction de partition et fonction d’échelle
1.3.2 Processus monofractal et coefficients d’ondelettes
1.3.3 Processus multifractal et coefficients dominants
1.4 Questions ouvertes
2 Variation totale
2.1 Introduction aux problèmes ℓ-TV et ℓ1-TV
2.1.1 Problème non convexe ℓ-TV
2.1.2 Problème convexe ℓ1-TV
2.1.3 Schémas itératifs d’optimisation convexe
2.2 Résolution du problème ℓ1-TV
2.2.1 Passage au dual
2.2.2 Augmentation de la dimensionnalité
2.2.3 Lagrangien augmenté
2.2.4 Algorithme primal-dual
2.2.5 Comparaison des algorithmes
2.2.5.1 Choix des paramètres des algorithmes
2.2.5.2 Coˆut de calcul
2.3 Evaluation des performances d’estimation
2.3.1 Rappels sur l’indice de Jaccard
2.3.2 Application à la détection de discontinuité
2.3.3 Choix du filtre passe-bas gaussien
2.4 Extension bidimensionnelle
2.4.1 Problème non convexe ℓ-TV 2D
2.4.2 Problème convexe ℓ1-TV 2D
2.4.3 Problème convexe ℓ-TV 2D à Q niveaux
2.5 Questions ouvertes
II Estimation constante par morceaux vectorielle
3 Analyse multifractale inhomogène
3.1 Modèle de processus multifractals par morceaux
3.1.1 Processus monofractal par morceaux
3.1.2 Processus multifractal par morceaux
3.2 Formalisme multifractal local
3.3 Estimation vectorielle par approche TV (1D)
3.3.1 Estimation vectorielle
3.3.1.1 Présentation et résolution du problème ℓ1,2-TV
3.3.1.2 Apport de l’estimation vectorielle
3.3.2 Quantification des performances
3.4 Segmentation vectorielle par approche TV (2D)
3.4.1 Segmentation vectorielle
3.4.2 Quantification des performances
3.5 Conclusion et perspectives
4 Estimation ℓ1,2-TV à la volée
4.1 Nature non locale du problème ℓ1,2-TV
4.2 Conditions de Karush-Kuhn-Tucker
4.2.1 Formulation duale
4.2.2 Réécriture des conditions de KKT
4.2.3 Solution approchée
4.3 Solution algorithmique à la volée
4.3.1 Cas idéal o`u bz est connu
4.3.1.1 Bornes inférieures et supérieures
4.3.1.2 Règles de mise à jour & Règle 1
4.3.1.3 Prolongation du signal & Règle 2
4.3.1.4 Estimer la position de la discontinuité nrupt
4.3.1.5 Commencer un nouveau segment
4.3.2 Estimation du vecteur auxiliaire bz
4.3.2.1 Estimateur constant par morceaux de bz
4.3.2.2 Estimer les positions candidates de la discontinuité n(q)rupt
4.3.2.3 Estimer la position de la discontinuité nrupt
4.3.2.4 Commencer un nouveau segment
4.4 Résultats
4.4.1 Configuration expérimentale
4.4.2 Conception de Q
4.4.3 Performances hors ligne
4.4.4 Performances en ligne
4.5 Conclusion et perspectives
III Autosimilarité multivariée
5 Régression non linéaire pour l’analyse d’OfBm
5.1 Autosimilarité multivariée et OfBm
5.1.1 Autosimilarité multivariée
5.1.2 Mouvement Brownien opérateur fractionnaire
5.1.3 Modèle paramétrique et indéterminations
5.2 Analyse en ondelettes des Biv-OfBm
5.2.1 Modèle paramétrique des Biv-OfBm
5.2.2 Spectre en ondelettes
5.2.2.1 Mélange de lois de puissance
5.2.2.2 Indétermination supplémentaire
5.2.2.3 Spectre en ondelettes empirique
5.3 Régression non linéaire pour l’identification d’OfBm
5.3.1 Formulation variationnelle du problème d’identification d’OfBm
5.3.2 Algorithme séparation-évaluation pour les problèmes de minimisation globale
5.3.3 Algorithme séparation-évaluation pour l’identification de Biv-OfBm
5.3.3.1 Relaxation convexe
5.3.3.2 Encadrement via l’arithmétique par intervalles
5.3.3.3 Algorithme séparation-évaluation
5.4 Performances d’estimation : étude théorique asymptotique
5.4.1 Normalité asymptotique du spectre d’ondelettes
5.4.2 Consistance de l’estimateur ΘbMN
5.4.3 Normalité asymptotique de l’estimateur ΘbMN
5.5 Performances d’estimation : étude empirique
5.5.1 Configurations expérimentales
5.5.2 Performances d’estimation
5.5.3 Coˆut de calcul
5.5.4 Nombre d’échantillons vs. précision
5.5.5 Normalité asymptotique de Θ
5.6 Conclusion et perspectives
6 Détection d’anomalies dans le trafic internet
6.1 Identifiation paramétrique de Biv-OfGns
6.1.1 Bruit Gaussien opérateur fractionnaire
6.1.2 Intégration fractionnaire et analyse en ondelettes
6.1.3 Spectre en ondelettes paramétrique de Biv-OfGn
6.1.4 Procédure d’identification
6.1.5 Performances
6.2 Application aux données internet
6.2.1 Données MAWI et projections aléatoires
6.2.2 Rˆole du paramètre d’intégration fractionnaire
6.2.3 Résultats
6.3 Conclusion et perspectives
IV Développements méthodologiques autour de la TV
7 Processus de Poisson homogènes par morceaux
7.1 Présentation du problème
7.1.1 Modèle
7.1.2 Impact de l’aggrégation
7.2 Statistique Poissonienne vs. Gaussienne
7.2.1 Divergence de Kullback-Leibler
7.2.2 Transformée d’Anscombe
7.3 Méthodologies
7.3.1 Méthode du seuil
7.3.2 Méthodes d’estimation par approche TV
7.3.2.1 Estimées par approche TV
7.3.2.2 Réestimation à 2 niveaux
7.3.3 Méthode de segmentation par approche TV
7.4 Comparaison des différentes méthodes
7.4.1 Configuration expérimentale
7.4.2 Quantification des performances
7.5 Conclusion et perspectives
8 Estimation du paramètre de régularisation ℓ-TV
8.1 Paramétrisation du problème .
8.1.1 Paramétrisation des discontinuités r
8.1.2 Paramétrisation des valeurs des segments µ
8.1.3 Reformulation du problème
8.2 Dérivation Bayésienne de la pénalisation φ
8.2.1 Modèle hiérarchique Bayésien
8.2.2 Critère MAP joint
8.3 Solution algorithmique
8.4 Sélection automatique de χ : Illustration et performances
8.4.1 Configuration expérimentale et choix des hyperparamètres
8.4.2 Illustration du principe de sélection automatique de χ
8.4.3 Quantification des performances
8.4.4 Comparaison contre de l’inférence bayésienne
8.4.5 Robustesse de l’estimateur proposé
8.5 Conclusion et perspectives
Conclusion
A Définitions utiles en optimisation convexe
B Algorithme de segmentation vectorielle couplée
B.1 Enoncé du problème
B.2 Solution algorithmique
B.3 Quantification des performances
C Démonstrations
C.1 Démonstration du Théorème 5.2
C.2 Démonstration du Théorème 5.3
C.3 Discussion à propos de la Remarque 5.5
D Estimateurs bayésiens
Bibliographie