of 189

THÈSE. En vue de l obtention du DOCTORAT DE L UNIVERSITÉ DE TOULOUSE

0 views
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
THÈSE En vue de l obtention du DOCTORAT DE L UNIVERSITÉ DE TOULOUSE Délivré par : l Université Toulouse 3 Paul Sabatier (UT3 Paul Sabatier) Présentée et soutenue le 06/11/2015 par : Pierre LASSALLE Étude
Transcript
THÈSE En vue de l obtention du DOCTORAT DE L UNIVERSITÉ DE TOULOUSE Délivré par : l Université Toulouse 3 Paul Sabatier (UT3 Paul Sabatier) Présentée et soutenue le 06/11/2015 par : Pierre LASSALLE Étude du passage à l échelle des algorithmes de segmentation et de classification en télédétection pour le traitement de volumes massifs de données. JURY Jordi INGLADA Chercheur Directeur de thèse Jean-Philippe GASTELLU Professeur Président du Jury Grégoire MERCIER Professeur Rapporteur Sébastien LEFEVRE Professeur Rapporteur Julien MICHEL Ingénieur Examinateur Pierre GANÇARSKI Professeur Examinateur École doctorale et spécialité : SDU2E : Océan, Atmosphère et Surfaces Continentales Unité de Recherche : Centre d Études Spatiales de la BIOsphère (UMR 5126) Directeur de Thèse : Jordi INGLADA Rapporteurs : Grégoire MERCIER et Sébastien LEFÈVRE 2 Sommaire Sommaire Liste des figures Liste des tables ii vii ix Introduction aux algorithmes échelonnables 8 1 Algorithmes échelonnables Définition et notations Définition d un algorithme Passage à l échelle Algorithmes et programmation informatique Modélisation d un ordinateur Description générale d un ordinateur Différents types de mémoire Modélisation d un ordinateur dans le cadre de nos travaux Complexité algorithmique Notation de Landau Structures de données Techniques algorithmiques pour le passage à l échelle Algorithme de flots de données Diviser pour mieux régner Réduction de la dimension des données Stabilité 31 Segmentation 32 2 Segmentation par fusion de régions Introduction 33 ii 2.2 Segmentation basée sur les régions Différents critères locaux d homogénéité Différentes heuristiques pour la fusion des segments Motivations pour l unification des méthodes par fusion de régions 41 3 Algorithme GRM Introduction Structures de données Représentation basée sur un graphe Représentation d un segment Représentation d un lien d adjacence Représentation du contour d un segment Description de l algorithme GRM et analyse de la complexité Initialisation des segments dans l image Calcul des coûts de fusion Mise à jour du contour Mise à jour du voisinage Suppression des segments fusionnés Algorithme GRM Stabilisation de l algorithme GRM Introduction Impact du tuilage État de l art GRM : un algorithme piloté par les données Stabilité des algorithmes de segmentation Zone d influence d un segment Calcul de la marge de stabilité 75 5 Algorithme échelonnable proposé : LSGRM Aperçu général de la LSGRM Suppression des segments instables Stockage et chargement des graphes Stockage des graphes dans la mémoire externe Chargement des graphes depuis la mémoire externe Ajout d une marge de stabilité à un graphe 84 iii 5.5 Fusion de graphes de segment Traitement des segments dupliqués Mise à jour des arêtes Example quantitatif des complexités de l algorithme LSGRM 90 6 Validation de l algorithme LSGRM et expérimentations Étude de la stabilité du LSGRM Segmentation d une scène complète Pléiades 96 7 Bilan sur la segmentation échelonnable Conclusions Perspectives 101 Classification Contexte des travaux Classification en télédétection Classification non supervisée Classification supervisée Revue des méthodes Classification bayésienne Les réseaux de neurones Les séparateurs à vaste marge Les arbres de décision Problématique Forêts aléatoires Description générale de l algorithme Calcul de l impureté basé sur le critère de Gini Détermination de la coupure optimale Partitionnement des données et distribution aux nœuds fils Construction récursive de l arbre de décision Construction de la forêt aléatoire Passage à l échelle : état de l art La méthode SLIQ La méthode SPRINT La méthode RainForest Google PLANET iv 9.2.5 Forêt aléatoire utilisant MapReduce Discussions Algorithme SMART Aperçu général de l algorithme SMART Génération des listes d attributs Tri des listes d attributs Choix de la stratégie initiale Description des stratégies d exécution dans SMART Stratégie En Mémoire Stratégie Partitionnement En Mémoire Stratégie Hors Mémoire Conclusions Validation de SMART et expérimentations associées Validation de la stabilité de l algorithme SMART Principales difficultés Méthodologie proposée Performance de l algorithme SMART Bilan sur la classification échelonnable Bilan Perspectives 158 Conclusions Conclusions générales Segmentation Bilan Perspectives Classification Bilan Perspectives v Bibliographie 165 Annexes 175 A Description des satellites Pléiades 176 B Description des données d apprentissage 177 C Valorisation scientifique 179 D Applications et développement logiciel 180 vi Table des figures 1.1 Algorithme d Euclide pour le calcul du PGCD Fonctionnement d un disque dur Modélisation simplifiée d un ordinateur Modélisation d une liste simplement chaînée Opération d insertion dans un tableau dynamique Suppression plus efficace des valeurs dans un tableau dynamique Algorithme External Merge Étapes génériques de la segmentation par fusion de régions Densité du graphe de segments au fil des itérations Représentation du graphe des segments avec une liste d adjacence Représentation du rectangle englobant un segment Bordure commune entre 2 segments adjacents Déplacements possibles le long d un contour Représentation des contours Ensemble des déplacements possibles le long d un contour Contour du segment S Génération de l image étiquetée à partir du contour des segments Résultat de segmentation avec l algorithme GRM Réduction de la mémoire avec l utilisation des contours types de connectivité disponibles dans l algorithme GRM Mise à jour du voisinage lors de la fusion de S j dans S i Évolution du temps d exécution de l algorithme GRM Application d un filtre gaussien en utilisant le tuilage Image utilisée pour les expériences Analyse visuelle de l impact du tuilage sur les segments résultants Protocole pour la comparaison des segmentations GT et TS Évolution des instances de Hoover Impact du tuilage sur les segments au fil des itérations La propriété de couverture vii 4.8 Zone d influence d un segment Représentation de la marge de stabilité M n pour une tuile Zone d influence d un segment initial Marge de stabilité M n+1 en fonction de M n et n Diagramme d exécution de l algorithme LSGRM Délimitation d une tuile dans l image Ajout de la couronne de stabilité dans le cas où n = Fusion de 2 graphes Recherche des segments dupliqués Traitement d un segment dupliqué Images satellite Ikonos et Quickbird Évolution de RC en fonction de la valeur incorrecte de la marge Évolution de RC en fonction de la valeur correcte de la marge Algorithme LSGRM : répartition du temps d exécution Résultat de segmentation d une image Pléiades Topologie d un réseau de neurones Hyperplan SVM Structure d un arbre de décision Étude bibliométrique des méthodes de classification Paramètres de l algorithme forêt aléatoire Diagramme d exécution de l algorithme SMART Hiérarchie des stratégies de l algorithme SMART Niveau d un arbre de décision Détermination des coupures optimales de tous les nœuds d un même niveau de l arbre avec la stratégie PEM Évolution du nombre de noeuds Ajout des nœuds fils aux nœuds du niveau courant Représentation de la MFU Procédure pour vérifier la stabilité de SMART Données utilisées pour la validation de l algorithme SMART Influence du nombre de données sur le temps d exécution Influence du nombre d attributs sur le temps d exécution Apport de la combinaison des stratégies sur le temps d exécution Données d apprentissage Landsat viii Liste des tableaux 1.1 Hiérarchie mémoire et temps de latence en nanosecondes (ns) Temps d exécution et mémoire utilisée par l algorithme LSGRM Temps d exécution de la première segmentation partielle Temps d exécution de la seconde segmentation partielle Répartition du temps d exécution lors de la segmentation finale Temps d exécution de l algorithme LSGRM Simulation MFU pour différentes valeurs de M Description des satellites Pléiades Description du satellite Landsat ix x Remerciements Avant de rentrer dans cette aventure algorithmique, je tiens à remercier les personnes qui m ont soutenu durant ces trois années de thèse et qui m ont permis de mener à terme un travail de recherche avec des contributions importantes. Je tiens à remercier dans un premier temps mon directeur de thèse, Jordi Inglada, Ingénieur Chercheur CNES, qui m a accompagné durant toute cette formation et a su m orienter dans mes recherches. Nos nombreux échanges constructifs, même à km de distance, m ont toujours été profitables et m ont permis de garder le cap pour remplir tous les objectifs que nous nous étions fixés. Enfin, il m a accordé toute sa confiance lorsque je voulais approfondir de nouvelles pistes de recherche et pour cela, je l en suis très reconnaissant. En second lieu, je tiens à remercier, Julien Michel, Ingénieur Chercheur CNES, Manuel Grizonnet, Ingénieur Chercheur CNES et enfin Julien Malik, Ingénieur C-S Communication & Systèmes, pour avoir suivi avec intérêt mes travaux de recherche lors de nos nombreuses réunions et pour la bienveillance dont ils ont fait preuve à mon égard. La multitude des points de vue a fortement contribué à la qualité de mes recherches et j en ai tiré un immense bénéfice. Je tiens à remercier le Centre National d Études Spatiales et l entreprise C-S Communication & Systèmes pour le cofinancement de cette thèse et leur contribution à l effort de recherche. Je tiens également à remercier les deux rapporteurs : M. Sébastien Lefèvre, Professeur à l Université Bretagne-Sud et M. Grégoire Mercier, Professeur à Télécom Bretagne, pour avoir étudié et commenté avec pertinence mes travaux de recherche. J ai eu la chance d effectuer ce travail de recherche dans un evironnement international en participant au projet Toloméo Tools for Open Multi-Risk Assessment using Earth Observation Data où j ai séjourné 1 an au Brésil à Rio De Janeiro. J ai connu une expérience multiculturelle très enrichissante et je tiens à remercier tous les membres du projet Toloméo présents à Rio De Janeiro pour leur accueil et leur bienveillance à mon égard. Revenant à la France, je tiens à remercier l ensemble des équipes du laboratoire CESBIO, en particulier Julien Osman et Mohamed Kadiri pour leur amitié et nos échanges divers sur ce monde et enfin Tristan Grégoire pour nos échanges Geek sur Tikz, Python, C++ et Git. Je tiens à remercier infiniment ma famille pour leur soutien et leur confiance à chaque instant de ma vie qui font ce que je suis devenu aujourd hui. Enfin, je tiens à remercier mon rayon de soleil Fiorella pour son soutien et sa patience de ces deux dernières années. 1 Introduction générale 2 Contexte Depuis les années 1970, la télédétection a permis d améliorer l analyse de la surface de la Terre grâce aux images satellites produites sous format numérique (LANDSAT-I en 1972). En comparaison avec les images aéroportées, les images satellites apportent plus d information car elles ont une couverture spatiale plus importante et une période de revisite courte. L essor de la télédétection a été accompagné de l émergence des ordinateurs. Les ordinateurs ont permis aux utilisateurs de la communauté de la télédétection d analyser les images satellites avec l aide de chaînes de traitement automatiques. La télédétection permet de mesurer l impact de l activité humaine sur l environnement. En effet, cette activité peut avoir des conséquences sur le climat, le terrain avec le développement des cultures dans le mileu agricole et l urbanisation galopante, etc. Grâce à la télédétection, nous pouvons déterminer la composition des sols, catégoriser les types de végétation sur un territoire, calculer les indices tels que l évaporation et la biomasse et cartographier les conséquences des activités humaines comme l urbanisation et l utilisation de certains pesticides. Pour effectuer cela, il est nécessaire de produire des cartes d occupation des sols qui représentent une cartographie de types homogènes de milieux (zones urbaines, zones agricoles, forêts, véhicule, arbre,...) de la surface des terres émergées. La production de ces cartes est effectuée à l aide de chaînes de traitement automatiques utilisant des méthodes de segmentation pour l extraction de données et de classification pour l identification des objets dans une scène satellite. Ce nouveau dynamisme a aussi eu des effets positifs du point de vue technologique. Depuis les années 1970, les différentes missions d observation de la Terre ont permis d accumuler une quantité d information importante dans le temps. Ceci est dû notamment à l amélioration du temps de revisite des satellites pour une même région, au raffinement de la résolution spatiale et à l augmentation de la fauchée (couverture spatiale d une acquisition). La télédétection, autrefois cantonnée à l étude d une seule image, s est progressivement tournée vers l analyse de longues séries d images multispectrales acquises à différentes dates. Une illustration de ce changement est le programme Sentinel de l ESA, avec notamment la mission Sentinel-2 [1], qui fournira une couverture complète des terres émergées tous les 5 jours avec 13 bandes spectrales et des résolutions spatiales de 10, 20 et 60 mètres. Cela correspondra potentiellement à un volume de 1,8 téraoctets de données par jour. En parallèle, la performance des processeurs des ordinateurs s est aussi accrue. La loi de Moore [2] prédisait que le nombre de transistors dans les microprocesseurs doublerait tous les deux ans, ce qui a été plus ou moins le cas jusqu à présent. Cependant, la capacité des mémoires internes 1 n a pas suivi l évolution de la puissance de calcul des ordinateurs [3]. La situation actuelle montre que les ordinateurs ne sont capables de garder qu une faible proportion des volumes de données à exploiter en mémoire interne. Par conséquent, durant un traitement, une application nécessite d accéder fréquemment 1. La mémoire interne est la mémoire pour laquelle le CPU ( Control Processor Unit ) peut accéder aux données sans utiliser le bus entrée/sortie ( IO channels ). 3 à la mémoire externe 2, ce qui constitue le principal goulot d étranglement à cause des CPU qui attendent le rapatriement des données depuis la mémoire externe en mémoire interne. En effet, le temps d accès en mémoire externe est 1000 à fois supérieur à celui de la mémoire interne, ce qui entraîne des temps de latence importants. En télédétection, l augmentation du volume de données à exploiter est devenue une problématique due à la contrainte de la mémoire [4]. Les algorithmes de télédétection traditionnels ont été conçus pour des données pouvant être stockées en mémoire interne tout au long du traitement. Cette condition ne sera plus vraie lors du traitement d images à très hautes résolutions spatiale, spectrale et temporelle comme celles fournies par la constellation des satellites Pléiades [5] ou par les satellites Sentinel-2. Les algorithmes de télédétection traditionnels nécessitent d être revus et adaptés pour le traitement de données à grande échelle. Ce besoin n est pas propre à la télédétection et se retrouve dans d autres secteurs comme le web, la médecine, la reconnaissance vocale, etc. Cette thèse se focalise sur l adaptation des algorithmes de télédétection pour le traitement de volumes de données massifs qui ne peuvent être stockés en mémoire interne. Besoins Face à la problématique du traitement de larges volumes de données liée à la contrainte de la mémoire, il est nécessaire d apporter des solutions pour adapter les algorithmes de télédétection traditionnels. En particulier, l étude sera faite sur les méthodes de segmentation et de classification, qui constituent les étapes les plus importantes dans le processus d extraction d information en télédétection. Afin de préparer les futures missions d observation de la Terre, il est nécessaire d adapter ces algorithmes pour le traitement de volumes de données ne pouvant être stockés en mémoire tout en garantissant des résultats identiques à ceux que nous aurions obtenus dans le cas où la mémoire ne serait pas une contrainte. Répondre à ce besoin constitue un réel enjeu pour la construction de chaînes de production des cartes d occupation des sols à l échelle globale. Segmentation Elle constitue une étape fondamentale pour l extraction d objets d intérêt dans l image. Les récentes missions d observation de la Terre fournissent des images multi-spectrales à très haute résolution avec une couverture spatiale importante. La taille de ces images peut-être conséquente. Par exemple, la constellation des satellites Pléiades [5] fournit quotidiennement des images de résolution 70 cm rééchantillonées à 50 cm avec une couverture spatiale de km 2. La taille standard d une image Pléiades est donc de pixels. Une description plus détaillée des satellites Pléiades est faite dans l annexe A. Une telle image requiert quelques gigaoctets pour être stockée en mémoire. 2. La mémoire externe est la mémoire pour laquelle le CPU accède aux données en utilisant le bus entrée/sortie 4 La segmentation de celle-ci fait intervenir l utilisation de structures de données nécessitant une quantité de mémoire égale voire beaucoup plus importante que celle nécessaire pour stocker l image. Par conséquent, il peut s avérer impossible de segmenter une telle image en une seule fois à cause de la limitation de la mémoire. Face à cette situation, la stratégie généralement choisie est de diviser l image en tuiles 3, de segmenter chaque tuile séparément et de reconstituer l image segmentée en regroupant les tuiles [6]. Bien que cette stratégie résolve le problème de la mémoire, nous verrons qu elle ne garantit pas un résultat identique à celui obtenu sans tuilage. Ceci est problématique dans la mesure où la qualité de l identification des objets d intérêt dans une scène pourrait être dégradée. Ainsi, une méthode revisitant la façon de découper les tuiles afin d assurer un résultat de segmentation identique à celui obtenu sans tuilage doit être proposée pour assurer la qualité des futures cartes d occupation des sols. Classification La classification permet de catégoriser les objets présents dans la scène d une image satellite. Elle est souvent composée d une phase d apprentissage qui permet de construire une fonction de décision à partir d exemples déjà caractérisés. Ces exemples constituent un ensemble de données d apprentissage où chaque donnée est un vecteur d attributs et est associée avec une étiquette qui représente une classe (forêt, zone agricole, bâtiment,...). L augmentation de la fréquence de revisite d une même région de la Terre induit une augmentation de la taille des ensembles de données d apprentissage. Généralement, un algorithme d apprentissage est complexe en temps de calcul puisqu il nécessite souvent de nombreuses itérations. Par conséquent, lorsque l ensemble des données en entrée devient trop volumineux pour être stocké en mémoire interne, cela peut nécessiter de nombreux accès en lecture et écriture dans la mémoire externe. Ces nombreux accès peuvent rendre les algorithmes inutilisables lors du traitement de données à grande échelle à cause du temps de latence qui est important. Ainsi, des solutions algorithmiques doivent être investiguées afin d utiliser des structures de données optimales pour assurer une visibilité totale de l algorithme d apprentissage sur l ensemble des données, tout en minimisant les accès dans la mémoire externe. Cadre de la thèse Cette thèse se situe dans le cadre de l élaboration de chaînes de traitement automatiques de production des cartes d occupation des sols à partir d images à hautes ou très hautes résolutions spatiale, temporelle et spectrale afin de préparer l exploitation des données issues des missions spatiales d observation de la Terre comme les satellites Pléiades et la famille des satellites Sentinel. 3. Une tuile représente une portion rectangulaire de l image dont les côtés sont parallèles à ceux de l image. 5 Les méthodes développées dans cette thèse ont été validées à pa
Related Search
Advertisements
Related Docs
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks