Thèses à venir

  • Antoine GLORIEUX, « Optimiser les déséquilibres dans un graphe »
    29 juin 2017 à 14:30
    Amphi 11 de Télécom SudParis
Résumé :
 
Le déséquilibre d’un sommet dans un graphe orienté est la valeur absolue de la différence entre son degré sortant et son degré entrant. Nous étudions le problème de trouver un orientation des arêtes du graphe telle que l’image du vecteur dont les composantes sont les déséquilibres des sommets par une fonction objectif f est maximisée.
Le premier cas considéré est le problème de maximiser le minimum des déséquilibres sur toutes les orientations possibles. Nous caractérisons les graphes dont la valeur objective optimale est nulle. Ensuite nous donnons plusieurs résultats concernant la complexité du problème. Enfin, nous introduisons différentes formulation du problème et présentons quelques résultats numériques.
Par la suite, nous montrons que le cas f=1/2||·||1 mène au célèbre problème de la coupe de cardinalité maximale. Nous introduisons de nouvelles formulations ainsi qu’un nouveau majorant qui domine celui de Goemans et Williamson. Des résultats théoriques et numériques concernant la performance des approches sont présentés.
Pour finir, dans le but de renforcer certaines des formulations des problèmes étudiés, nous étudions une famille de polyèdres spécifique consistant en l’enveloppe convexe des matrices d’affectation 0/1 (où chaque colonne contient exactement une composante égale à 1) annexée avec l’indice de leur ligne non-identiquement nulle la plus basse. Nous donnons une description complète de ce polytope ainsi que certaines de ses variantes qui apparaissent naturellement dans le contexte de divers problèmes d’optimisation combinatoire. Nous montrons également que résoudre un programme linéaire sur un tel polytope peut s’effectuer en temps polynomial. 


  • Nicolas HASCOËT, « Méthodes pour l'interprétation automatique d'images en milieu urbain »
    27 juin 2017 à 14:00
    Salle 211 - Tour 55,  Université Paris 6 - 4 place Jussieu 75252 Paris cedex 05

Résumé :

Cette thèse présente une étude pour l'interprétation automatique d'images urbaines. Nous proposons une application permettant de reconnaître différents monuments au sein d'images représentant des scènes complexes. La problématique principale est ici de différencier l'information locale extraite des points d'intérêt du bâtiment recherché parmi tous les points extraits de l'image. En effet, la particularité d'une image en milieu urbain vient de la nature publique de la scène. L'objet que l'on cherche à identifier est au milieu de divers autres objets pouvant interférer avec ce dernier.

Nous présentons dans une première partie un état de l'art des méthodes de reconnaissance d'image en se concentrant sur l'utilisation de points d'intérêts locaux ainsi que des bases de données pouvant être employée lors des phases d'expérimentation. Nous retenons au final le modèle de sac de mots appliqué aux descripteurs locaux SIFT.

Dans un second temps nous proposons une approche de classification des données locaux faisant intervenir le modèle de machine à vecteurs de support. L'intérêt présenté dans cette approche proposée est le faible nombre de données requises lors de la phase d'entraînement des modèles. Différentes stratégies d'entraînement et de classification sont exposées ici.

Une troisième parie suggère l'ajout d'une correction géométrique de la classification obtenue précédemment. Nous obtenons ainsi une classification non seulement de l'information locale mais aussi visuelle permettant ainsi une cohérence géométrique de la distribution des points d'intérêt.

Enfin, un dernier chapitre présente les résultats expérimentaux obtenus, notamment sur des bâtiments de Paris et d'Oxford.