Optimisation non-convexe

Nous vous rappelons que, afin de garantir l'accès de tous les inscrits aux salles de réunion, l'inscription aux réunions est gratuite mais obligatoire.

Inscriptions closes à cette réunion.

Inscriptions

47 personnes membres du GdR ISIS, et 28 personnes non membres du GdR, sont inscrits à cette réunion.
Capacité de la salle : 100 personnes.

Annonce

La résolution de problèmes non-convexes couvre un large spectre des travaux de la communauté signal/image avec des développements récents sur les thématiques telles que la reconstruction parcimonieuse, la résolution de problèmes inverses non-linéaires ou la segmentation. D'un point de vue théorique, le panel des méthodes dites de résolution de problèmes non-convexes est vaste. On peut par exemple citer les techniques d'optimisation globale, d'optimisation discrète, de relaxation convexe, ou encore les approches basées sur des hypothèses de type inégalité de Kurdyka-Lojasiewicz.

Le but de cette première journée consacrée à l'optimisation non-convexe est de focaliser sur une partie des techniques existantes à savoir la résolution de problèmes inverses non-linéaires ainsi que les méthodes d'optimisation globales et discrètes. 

Les membres du GdR sont priés de s’inscrire sur le site http://www.gdr-isis.fr/. Toute autre personne intéressée par cette journée est invitée à contacter les organisateurs.

 

Organisateurs :

- Saïd Moussaoui : said.moussaoui@irccyn.ec-nantes.fr

- Nelly Pustelnik : nelly.pustelnik@ens-lyon.fr

 

Programme

 

10h00. Nikos Komodakis (Ecole des ponts ParisTech)  :  

Tutoriel optimisation discrète

11h00. Mireille El Gheche (Université Paris-Est) : 

Méthodes d'optimisation pour l'estimation de disparité à partir d'images multivues

11h30. Nicolas Lermé (Institut Supérieur d'Electronique de Paris) : 

Optimisation discrète et continue pour un problème d'imagerie mosaïque active

12h00. Pause déjeuner

13h30. Jordan Ninin (ENSTA Bretagne) : 

Tutoriel algorithmes branch and bound

14h30. Valentin Emiya (Aix Marseille Université) :  

Compressed sensing with unknown sensor permutation

15h00. Pause

15h30. Yves Goussard (Polytechnique Montréal) : 

Tutoriel probèmes inverses non-linéaires

16h30. Charles Soussen (Univeristé de Lorraine) :  

Algorithmes de continuation L0 inspirés d'Orthogonal Least Squares

17h00. Aurélie Boisbunon (INRIA Sophia-Antipolis Méditerranée) :  

Résolution de problèmes d'optimisation non convexes et parcimonieux en très grandes dimensions et application à la détection d'objets 

17h30. Bilan de la journée et discussion

 

Résumés des contributions

Titre : Méthodes d'optimisation pour l'estimation de disparité à partir d'images multivues

Auteurs : M. El Gheche, J.-C. Pesquet, V. Nozick, B. Pesquet-Popescu

Résumé : Le développement de la télévision 3D et des supports auto-stéréoscopiques a généré un grand intérêt pour le traitement de séquences multivues. Il s’agit, en particulier, d’extraire de l’information 3D à partir des vues disponibles, sous forme de cartes de disparités, ce qui s'avère particulièrement utile  dans le cadre d’applications où les zones d’occultation sont très larges et posent ainsi de nombreuses difficultés. Le problème d’optimisation associé est néanmoins non-convexe et de grande dimension. Pour le résoudre efficacement, deux approches sont possibles. Une première approche consiste à quantifier le champs de disparité et à se ramener à un problème d’optimisation combinatoire. Deux méthodes de résolution ont été comparées dans ce contexte : l’une relativement classique emploie une approche par coupure de graphe, et la seconde relaxe le problème discret de manière convexe, permettant ainsi l’utilisation de méthodes proximales récentes. La seconde approche consiste à linéariser itérativement le problème. Deux types de linéarisation ont été envisagées dont les performances ont été comparées pour ce problème. Des résultats sur des images synthétiques et réelles ont permis de valider l’efficacité de ces différentes méthodes, pour des mesures d’erreur variées.

 

Titre : Optimisation discrète et continue pour un problème d'imagerie mosaïque active

Auteurs : N. Lermé et F. Malgouyres

Résumé :  L'imagerie mosaïque active est une technique d'acquisition émergente qui consiste à acquérir une mosaïque d’images (spots laser) en dirigeant un rayon laser sur une petite partie d'un objet cible et en le déplaçant progressivement afin d'imager la scène en entier. La restauration de l'image de cette scène à partir d'une telle mosaïque est un problème inverse difficile à résoudre. Une solution originale a récemment été proposée avec l'utilisation d'un modèle direct décrivant le processus d'acquisition. Avec un a priori gaussien sur les paramètres d'acquisition et un a priori basé sur la Variation Totale pour la distribution des images, un algorithme itératif est déduit alternant entre (i) l'estimation des paramètres d'acquisition par une descente de gradient et (ii) l'estimation de l'image restauée par graph cuts. Après avoir présenté brièvement le modèle et l'algorithme proposé, je présenterai quelques méthodes d'optimisation continue avancées (AGD, BFGS, Diagonally-Scaled Newton) et montrerai comment elles peuvent aider à l’accélération de la convergence pour l'estimation des paramètres d'acquisition, même pour des instances modérément mal conditionnées. 

N. Lermé, F. Malgouyres, ''Numerical Study of an Optimization Problem for Mosaic Active Imaging'', Soumis à ICIP, 2014 Lien HAL : http ://hal.archives-ouvertes.fr/hal-00935725

N. Lermé, F. Malgouyres, ''Bayesian Image Restoration For Mosaic Active Imaging'', A paraitre dans ''Journal of Inverse Problems and Imaging'', 2012 Lien HAL : http ://hal.archives-ouvertes.fr/hal-00758753

 

Titre : Acceleration Techniques in Global Optimization

Auteur : J. Ninin

Résumé :  Since about thirty years, the Branch and Bound algorithms based on Interval Analysis are increasingly used to solve non-convex global optimization problems in a deterministic and reliable way. However, these methods may require much CPU time, thus acceleration methods are generally essential. In this talk, we will deal with an overview of different techniques based on interval analysis, constraint programming techniques, linear relaxations and semidefinite relaxations.

 

Titre : Compressed sensing with unknown sensor permutation

Auteur : V. Emiya (cowork with Antoine Bonnefoy, Laurent Daudet and Rémi Gribonval)

Résumé :  Compressed sensing is the ability to retrieve a sparse vector from a set of linear measurements. The task gets more difficult when the sensing process is not perfectly known. We address such a problem in the case where the sensors have been permuted, i.e., the order of the measurements is unknown. We propose a branch-and-bound algorithm that converges to the solution. The experimental study shows that our approach always retrieves the unknown permutation, while a simple convex relaxation strategy almost always fails. In terms of its time complexity, we show that the proposed algorithm converges quickly with respect to the combinatorial nature of the problem.

Article publié à Icassp 2014 et disponible sur http://hal.inria.fr/hal-00881407

 

Titre : Aspects méthodologiques et pratiques de la reconstruction en tomographie à rayons X par des méthodes statistiques

Auteur : Y. Goussard

Résumé :  La tomographie à rayons X est une des modalités les plus utilisées en imagerie médicale. Si, dès la fin des années 1970, les méthodes statistiques de reconstruction ont fait l'objet d'une recherche active, leur utilisation pratique reste encore très marginale en raison des difficultés tant méthodologiques que pratiques. Ici, on abordera certaines de ces difficultés et on proposera quelques pistes de solution. On s'intéressera tout d'abord au processus de formation des données. La plupart des approches existantes se basent sur un modèle linéaire résultant de transformations de la loi de Beer-Lambert. On examinera l'effet de ces transformations sur les caractéristiques de la vraisemblance et sur la possibilité de prendre en compte certains éléments souvent négligés (détecteurs non ponctuels, polychromaticité de la source). On examinera ensuite brièvement les questions du choix d'un estimateur et de sélection d'un algorithme d'optimisation. Enfin, on abordera un point critique du développement d'une méthode capable de traiter des données de taille réaliste : le développement d'une représentation de l'opérateur de projection conduisant à la fois à un encombrement mémoire réduit et à des calculs rapides. On montrera que la décomposition de l'objet dans un système de coordonnées cylindrique présente de nombreux avantages, mais que les questions de conditionnement du problème d'estimation et de choix de pénalisation doivent être traitées avec soin pour parvenir à des résultats satisfaisants.

 

Titre : Algorithmes de continuation L0 inspirés d'Orthogonal Least Squares

Auteur : C. Soussen, J. Idier, J. Duan et D. Brie

Résumé :  Cette présentation concerne le développement d'algorithmes d'approximation parcimonieuse pour les problèmes inverses mal conditionnés. Les algorithmes heuristiques proposés sont conçus pour minimiser des critères mixtes L2-L0 du type min_x J(x;lambda)=||y-Ax||_2^{^2}+lambda||x||_0. Ce sont des algorithmes gloutons "bidirectionnels" définis en tant qu'extensions d' "Orthogonal Least Squares" (OLS). Leur développement est motivé par le très bon comportement empirique d'OLS et de ses versions dérivées lorsque le dictionnaire A est une matrice mal conditionnée. Nous présentons dans un premier temps l'algorithme "Single Best Replacement" (SBR) pour minimiser J(x;lambda) à lambda fixé [1], en mettant en avant ses propriétés structurelles. Dans la deuxième partie de la présentation, nous proposons deux algorithmes permettant de minimiser J pour un continuum de valeurs de lambda, ce qui conduit à estimer le chemin de régularisation L0 [2]. Ces algorithmes sont inspirés de l'algorithme d'homotopie pour la régularisaton L1 et exploitent le caractère constant par morceaux du chemin de régularisation L0. "Continuation Single Best Replacement" (CSBR) est une adaptation directe de SBR qui travaille à des degrés de parcimonie décroissants. L'algorithme plus complexe "L0-regularization Path Track" (L0-PT) effectue un suivi (sous-optimal) du chemin de régularisation en maintenant (i) une liste de supports candidats pour des valeurs décroissantes de lambda; et (ii) une liste de valeurs critiques de lambda autour desquelles la solution change. Les simulations numériques montrent l'efficacité des deux algorithmes pour des problèmes inverses difficiles comme la déconvolution impulsionnelle par un filtre passe-bas.

[1] C. Soussen, J. Idier, D. Brie et J. Duan, From Bernoulli-Gaussian deconvolution to sparse signal restoration, IEEE Transactions on Signal Processing, vol. 59, no. 10, pp. 4572-4584, oct. 2011.

[2] C. Soussen, J. Idier, J. Duan et D. Brie, L2-L0 regularization path tracking algorithms, CRAN - IRCCyN - Université de Xi'an Jiatong, fév. 2014. http://hal.archives-ouvertes.fr/docs/00/94/83/13/PDF/csbr.pdf

 

Titre : Résolution de problèmes d'optimisation non convexes et parcimonieux en très grandes dimensions et application à la détection d'objets.

Auteur : A. Boisbunon

Résumé :  Dans un premier temps, nous avons proposé un algorithme de type "active set" pour résoudre des problèmes d'optimisation avec des fonctions de pénalités induisant des solutions parcimonieuses. L'utilisation de pénalités non convexes permet une parcimonie plus agressive et une solution plus précise que la pénalité l1. Notre algorithme donne des résultats jusqu'à 100 fois plus rapides que GIST, un des algorithmes les plus rapides de l'état de l'art actuel. Dans un deuxième temps, nous avons adapté la méthode à la détection d'objets dans des images. Nous proposons pour cela de traiter le problème de détection comme une somme de convolutions entre des atomes de dictionnaire représentant différentes instances des objets, et des matrices d'activation correspondant aux positions des objets dans l'image. L'estimation des matrices d'activations peut s'écrire sous la forme d'un problème linéaire parcimonieux. Nous avons appliqué cet algorithme à la détection de bateaux dans des images satellitaires de ports, montrant clairement l'apport de la pénalité non-convexe "log-sum" par rapport à la pénalité convexe l1.