La sélection automatique de données de grande dimension pour la classification

Télécharger le fichier original (Mémoire de fin d’études)

La méthode de classification avec notion de probabilité d’appartenance

La notion de probabilité et de loi de probabilité

Le premier usage du mot probabilité apparaît en 1370 avec la traduction de l’éthique à Nicomaque d’Aristote par Oresme et désigne alors « le caractère de ce qui est probable » (Oresme, 1940). Le concept de probable chez Aristote est défini dans les Topiques (de Pater, 1965) par : « Sont probables les opinions qui sont reçues par tous les hommes, ou par la plupart d’entre eux, ou par les sages, et parmi ces derniers, soit par tous, soit par la plupart, soit enfin par les plus notables et les plus illustres ».
La notion d’opinion collective introduite par Aristote illustre bien la probabilité de prise de décision. Chaque décision est prise en fonction de tous les observateurs, quelle que soit leur importance, ce qui implique une notion de normalisation et de collectivité.
La probabilité objective d’un évènement n’existe pas et n’est donc pas une grandeur mesurable, mais tout simplement une mesure d’incertitude, pouvant varier avec les circonstances et l’observateur, donc subjective. La seule exigence étant qu’elle satisfasse aux axiomes du calcul des probabilités (Saporta, 2006).
La théorie mathématique des probabilités ne dit pas quelle loi de probabilité mettre sur un ensemble IM parmi toutes les lois possibles. Ce problème concerne les applications du calcul des probabilités, et renvoie à la nature « physique » du concept de probabilité qui formalise et quantifie le sentiment d’incertitude vis-à-vis d’un évènement (Saporta, 2006).
Définissons la notion de probabilité dans un cadre mathématique.
Définition : On appelle probabilité ou mesure de probabilité sur un espace mesurable (IM, ) une application P de → [0,1] telle que :
i. ∀A∈ ,0≤P(A)≤1
ii. P(∅) = 0 et P(IM) = 1
iii. ∀ An une suite d′ensembles disjoints de , P(⋃∞n=1 An) = ∑∞n=1 P(An)
La loi de probabilité la plus utilisée en classification probabiliste est la loi gaussienne car ses hypothèses sur les données permettent de réduire la complexité de calcul et le risque d’erreur. Rappelons que dans le cas de la classification, la loi gaussienne suppose qu’une classe peut être modélisée par son vecteur des moyennes et sa matrice de covariance (De Moivre, 1756)(figure I.15).

La classification par Maximum de Vraisemblance

La méthode de classification par Maximum de Vraisemblance fut développée par Fisher en 1922 (Fisher, 1922). Le principe de cette méthode est le suivant : chaque pixel de l’image sera associé à la classe dont il maximise la probabilité d’appartenance.

Les méthodes de classification non paramétriques à noyaux

A la différence des méthodes présentées précédemment, il n’y a ici aucune estimation de statistique à partir des échantillons. Ces méthodes sont donc particulièrement intéressantes lorsque le nombre de points de certains échantillons est limité. Dans certaines conditions, la nature des échantillons ne permet pas un échantillonnage suffisant, exemple des zones urbaines très hétérogènes et riches en diversité de classe. Inversement, lorsque le nombre d’échantillons est trop important, la complexité de calcul des méthodes de classifications non paramétriques à noyau devient trop élevée et les résultats peuvent être détériorés du fait de la considération de certains pixels non significatifs.
Parmi ces méthodes de classification non paramétriques à noyau, nous introduirons les méthodes Support Vector Machines et Réseaux neuronaux.
Nous n’entrerons pas ici dans les détails des méthodes et nous ne fournirons que les éléments nécessaires à la compréhension globale des méthodes et de leurs avantages et inconvénients vis-à-vis des autres méthodes citées précédemment, laissant ainsi le lecteur intéressé se diriger vers la bibliographie fournie.

La méthode des Support Vectors Machines (SVM)

Les méthodes d’apprentissage à noyau et plus particulièrement les Support Vectors Machines (SVM) ont été introduites depuis plusieurs années en théorie d’apprentissage pour la classification et la régression (Vapnik, 1998). L’application des SVM a commencé avec la reconnaissance de texte (Joachims, 1998) puis la reconnaissance de visage (Osuna, Freund, & Girosit, 1997). Plus récemment, cette méthode est appliquée à la classification d’images de télédétection (Huang, Davis, & Townshend, 2002; Melgani & Bruzzone, 2004; Roli & Fumera, 2001; J. Zhang, Zhang, & Zhou, 2001).
Le principe original de la méthode est simple, il consiste à rechercher une surface de décisions ou hyperplan afin de séparer deux classes. La surface de décisions sera déterminée par un sous-ensemble des échantillons d’apprentissage afin de maximiser la discrimination des deux classes. Les éléments de ce sous ensemble sont appelés vecteurs de support (figure I.19).
Cette approche est intéressante puisque l’optimisation est supposée maximiser directement la performance de la classification. Le noyau (ou système d’équations de l’hyperplan) peut prendre plusieurs formes et nous citerons les plus utilisées : noyau linéaire (figure I.20 et figure I.21), noyau polynomial (figure I.22 et figure I.23) et noyau gaussien (figure I.24 et figure I.25).
Lorsque les deux classes ne sont pas linéairement séparables, la méthode consiste à projeter les données dans des dimensions supérieures dans lesquelles les classes seront linéairement séparables.
L’algorithme de classification SVM a été initialement prévu pour la classification binaire, néanmoins deux méthodes existent pour étendre cet algorithme à la classification multi-classes.
La première méthode est appelée « un contre les autres » et consistent à déterminer pour chaque classe une surface de décisions entre la classe et toutes les autres, ce qui donne #C surfaces de décision. Cette méthode est illustrée aux figures I.20, I.22 et I.24.
La deuxième méthode appelée « un contre un » consiste quant à elle à calculer la surface de décision entre chaque classe et chacune des autres classes, d’où l’obtention de #C × (#C − 1) surfaces de décision. Cette méthode est illustrée aux figures I.21, I.23 et I.25. La seconde méthode est la plus performante mais aussi la plus couteuse en calcul.
Afin de combiner les surfaces de décision, des méthodes de fusion sont appliquées. Certaines de ces méthodes seront citées au chapitre 4.
Les figures I.27 à I.29 illustrent les résultats de ces trois classifications par méthode SVM sur l’exemple de la fleur.

La méthode des Réseaux Neuronaux

Le modèle des réseaux de neurones le plus utilisé pour la classification d’images de télédétection est le perceptron multicouche avec entrainement par algorithme de retro propagation (Rumelhart, Hintont, & Williams, 1986).
Le perceptron multicouche comprend une couche d’entrée (les images à classer) et une couche de sortie (les classes à attribuer). Entre ces deux couches, une ou plusieurs couches cachées peuvent être positionnées. Après la phase d’apprentissage, le système agit en « boite noire » : à un pixel d’entrée correspond une classe de sortie.
La correspondance attendue entre la couche d’entrée et la couche de sortie ne pouvant être absolue, le perceptron se comporte comme un approximateur. Un compromis devra donc être trouvé entre le nombre de couches cachées (et de neurones les composant) et la qualité d’approximation du système (figure I.26).
figure I.26 : Exemple de perceptron à deux couches cachées avec en entrée les images par date et par canal et en sortie une décision sous forme d’attribution de classe de l’ensemble C.
Les détails des algorithmes et les démonstrations associées sont disponibles dans (Collet, 2001). La figure I.30 illustre la classification par méthode des réseaux de neurones sur l’exemple de la fleur.

La méthode de classification dit « objet »

Le principe des méthodes de classification dites « objet » est de ne plus considérer l’élément à classer comme un pixel mais plutôt comme un ensemble de pixels que l’on nommera objet. Cet objet peut être défini de plusieurs façons, l’approche qui sera développée par la suite est la définition d’objet par segmentation.

La notion d’objet obtenu par segmentation

Afin d’obtenir ces objets, il convient de regrouper les pixels par affinité, le plus généralement par homogénéité des valeurs.
Dans le cas d’un regroupement par homogénéité de valeurs, la formation de ces objets commence par le calcul d’une image de gradient (ou image de force de contour) ce qui permet de donner un poids à chaque contour suivant la force de l’hétérogénéité détectée. Celle-ci peut avoir été obtenue par tout type de filtre (Sobel, etc…).
La détection des contours se fait de la manière suivante : à partir d’un premier point du contour présumé, on effectue par connexité un suivi de contour grâce aux renseignements obtenus durant la recherche tels que sa direction ou sa longueur. Avec ces éléments, le contour est reconstruit pour en faire un contour fermé en regroupant les points détectés (figure I.31).
Une fois que les contours sont déterminés et fermés, on peut segmenter l’image par la méthode des bassins versants (Beucher & Lantuéjoul, 1979). La segmentation se base sur l’image de force de contours qui s’interprète comme une surface dont les lignes de crête correspondent aux contours de l’image. Pour détecter les lignes de crête on simule une « inondation » de la surface. Ses « vallées » vont être noyées et des bassins vont se former. Dans un premier temps on « remplit ces bassins » jusqu’à une hauteur prédéterminée S1 (le seuil de détection), telle que seuls les pics les plus hauts émergent, séparant l’eau en plusieurs « lacs » distincts. L’inondation jusqu’au niveau S1 fait disparaître les sommets les plus bas, c’est-à-dire ceux qui ne représentent pas de contours significatifs, puis un identificateur est attribué, unique à chaque bassin formé (figure I.32.a).
Une fois que les bassins sont formés et étiquetés, on fait monter l’eau d’un niveau supplémentaire. En grossissant, des bassins qui étaient jusqu’alors isolés vont se toucher. Ainsi si un point est le lieu de réunion de deux bassins portant des étiquettes distinctes, ce point peut être marqué définitivement comme frontière (figure I.32.b). L’exécution se termine lorsque tous les points de la surface sont immergés. A ce stade les points marqués comme frontières constituent les contours de l’image.
L’image segmentée par les bassins versants est étiquetée et les caractéristiques (moyenne et variance par exemple) sont calculées sur chacune des régions. Les régions voisines sont ensuite comparées par l’intermédiaire d’un critère. Les couples de régions qui ne satisfont pas les limites imposées seront alors fusionnés. Ce principe permet ainsi de regrouper les régions homogènes. On peut ainsi régler la précision de la segmentation obtenue. Les figures I.34 à I.36 illustrent le principe de la segmentation et de la fermeture des contours sur l’image de la fleur.

La classification des objets

Afin de classer les objets, il convient de calculer une distance entre deux ensembles. Pour cela, une distance et une divergence permettent de décider de cet appariement : la distance de Bhattacharyya (équation I.6) et la divergence de Kullbach-Leibler symétrique (équation I.7).
La distance de Bhattacharyya est la plus souvent employée car elle dispose de propriétés supplémentaires vis-à-vis de la divergence de Kullbach-Leibler (paragraphe 2.1.2).
Cet algorithme attribue à l’objet o la classe la plus proche coopt (équation I.14).
copt = arg min dbhata(o, co) (I.14)
o co∈C
Cette méthode est par définition très dépendante du choix lors du seuillage des objets. Prenons l’exemple de deux seuillages différents et de leur étiquetage par la méthode des bassins versants (figure I.37 et figure I.38). Les images classées résultantes sont respectivement présentées aux figures I.39 et I.40. Dans les deux cas, nous observons que le choix de la taille de l’objet est bien adapté à la classe verte ; dans le cas de l’image de la figure I.40, la taille des objets est bien adaptée à la classe jaune mais dans aucun des cas à la classe rouge. A chaque classe devrait donc correspondre un choix de seuil différent, ce qui compliquerait l’algorithme et le choix du seuil. Ceci est une perspective de recherche intéressante dans le domaine de la classification d’objets.

Les méthodes de classification dites « globales »

L’intérêt de ces méthodes se situe dans l’aspect spatial du traitement qui permet de donner une probabilité a priori d’une classe pour toute l’image, c’est-à-dire dans sa globalité. En pratique, les hypothèses markoviennes permettent de réduire cette dépendance globale aux voisins les plus proches de chaque point à classer. Cet outil simple et efficace s’appelle les champs de Markov. Ces méthodes ont été introduites par Geman & Geman (Geman & Geman, 1984) pour la classification d’images bruitées. Ces méthodes ont été ensuite appliquées aux images radar mais également à d’autres types d’images (Kato, Zerubia, & Berthod, 1999; Kato, Zerubia, & Berthod, 1992). L’idée fondamentale des méthodes de classification globale repose sur les Champs de Markov (CAM) (Cocquerez & Philipp-Foliguet, 1995; Pony, Descombes, & Zerubia, 2000).
En général, les champs de Markov sont stationnaires (id est indépendant de la position du site s) et la fonction potentielle est indépendante de la position de la clique (Ducrot, 2005).
Le théorème de Hammersley-Clifford (Besag, 1974; Hammersley & Clifford, 1968) permet de caractériser les champs de Markov en termes globaux à partir de la probabilité a priori d’une configuration des classes p(C=c). Il permet d’établir une correspondance entre un champ de Markov et un champ de Gibbs lorsqu’aucune réalisation de C n’est de probabilité nulle.
Théorème Hammersley-Clifford: Un champ aléatoire C défini sur un réseau de site S fini et dénombrable est un champ de Markov relativement à V un système de voisinage borné si et seulement si C est un champ de Gibbs de potentiel associé à V.
La distribution de probabilité a priori p(c) est donc une distribution de Gibbs défini par : p(c) = 1Z e−U(c)T, avec Z constante de normalisation et T variable de « temperature »
La constante de normalisation Z est aussi appelée fonction de partition et assure que p(c) définisse bien une mesure de probabilité. Z s’exprime par l’équation I.18.
La variable de « température » T a été ajoutée au processus ICM afin de pondérer la fonction énergie. En pratique, la variation de ce paramètre de température permet de régler la vitesse convergence de l’algorithme. Ce principe est issu de la méthode du recuit simulé (Kirkpatrick, Jr, & Vecchi, 1983)).
Nous voyons donc que la probabilité d’une configuration ne dépend que d’un ensemble d’interactions locales. En outre, plus l’énergie totale U(c) est grande, moins la configuration est possible.
Plusieurs modèles existent pour définir la fonction potentielle Vcl(x). Nous citerons en exemple le modèle de Potts (Potts, 1952) ou encore le « chien-modèle » (Descombes, Mangin, Sigelle, & Pechersky, 1995) qui permet de conserver les structures fines et linéaires à partir d’une image de contour (paragraphe 2.2.1).

Les méthodes de classification contextuelle

Pour des estimateurs de Maximisation a posteriori (MAP), plusieurs méthodes de classification contextuelle basée sur un CAM existent telles que la méthode du recuit simulé (algorithme stochastique) ou l’Iterated Conditional Mode (ICM, algorithme déterministe). Les modèles stochastiques sont beaucoup plus performants et permettent une convergence vers un maximum global alors que les algorithmes déterministes sont plus rapides mais peuvent converger vers un maximum local (Ducrot, 2005).
Nous présenterons dans la suite du manuscrit plusieurs méthodes basées sur l’utilisation de l’algorithme ICM du fait de sa performance, de sa rapidité et de sa robustesse.

Minimisation de l’énergie a posteriori par la méthode ICM

La méthode Iterative Conditional Mode (ICM) est une méthode de recherche déterministe proposée par Besag (Besag, 1974). Cette méthode itérative permet d’approcher la solution optimale du MAP en affectant à chaque pixel s la classe qui maximise la probabilité conditionnelle d’appartenance.

La classification par méthode ICM

Rappelons que la classification par méthode ICM est une méthode itérative basée en règle générale sur un classifieur de type Maximum de Vraisemblance classique comme présenté au paragraphe 2.1.3.2. Puis à chaque itération de l’algorithme ICM, une nouvelle probabilité est calculée en fonction du contexte nominal du pixel id est la classe attribuée au voisinage du pixel à classer. L’écriture de la probabilité a posteriori à maximiser a été introduite à l’équation I.22

Table des matières

Introduction générale
1. La télédétection d’hier à demain
2. L’utilisation de données multidimensionnelles de télédétection pour la cartographie des sols : enjeux et problématiques
3. L’approche proposée et l’organisation du manuscrit
Chapitre I. La classification
1. Introduction
1.1. Définitions et existence
1.2. La classification appliquée à la télédétection pour la cartographie de l’occupation des sols
1.3. Les catégories de méthodes de classification
2. Les méthodes de classification multidimensionnelles applicables à la télédétection .. 10
2.1. Les méthodes de classification ponctuelle
2.2. La méthode de classification dit « objet »
2.3. Les méthodes de classification globale
2.4. Amélioration du processus ICM : ajout d’informations exogènes
3. La classification non supervisée et son interprétation
4. Application et comparaison des différents classifieurs avec des données de télédétection multidimensionnelles.
5. Conclusion
Chapitre II. L’évaluation de la classification
1. L’évaluation de classification : définitions et contexte
1.1. Contexte
1.2. Définitions
2. L’évaluation à partir de références spatiales
2.1. La matrice de confusion
2.2. La matrice de confusion par pondération de probabilité
2.3. Indices pour l’évaluation à partir des matrices de confusion
2.4. Introduction et validation de nouveaux indices
2.5. Illustrations des indices présentés
3. L’évaluation de classification à partir de valeurs radiométriques spectrales et temporelles de référence
3.1. Indice de similitude
3.2. Matrice de similitude
3.3. Evaluation d’une matrice de similitude
4. Applications
4.1. Comparaison des classifieurs sur des données de télédétection
4.2. Comparaison des matrice de confusion avec et sans pondération de probabilité
5. Conclusion
Chapitre III. La sélection automatique de données de grande dimension pour la classification
1. Introduction de la sélection de données pour la classification
2. Les algorithmes de sélection
2.1. Le problème à résoudre
2.2. Les méthodes SFS et SBS
2.3. Les méthodes SFFS et SFBS
2.4. La méthode des Algorithmes Génétiques
3. Applications des méthodes de sélection de données
3.1. Application sélection temporelle sur Formosat-2 année 2009
3.2. Application sélection temporelle sur Spot 2/4/5 année 2007
4. Extension du problème de sélection
4.1. Adaptation de la méthode des AG
4.2. Applications du problème complet
5. Introduction du système de Sélection-Classification-Fusion
6. Conclusion
Chapitre IV. La fusion d’images issues de classifications supervisées
1. Introduction
2. La fusion de données
2.1. La fusion de données a priori
2.2. La fusion de décisions de classification
2.3. La fusion de résultats a posteriori
3. La fusion d’images de classification supervisées
3.1. Méthode de fusion par vote majoritaire
3.2. Méthode de fusion par vote majoritaire pondéré
3.3. Méthode de fusion par minimisation de confusion
4. Application au processus de Sélection-Classification-Fusion
5. Applications des méthodes de fusion a posteriori de résultats de classifications
5.1. La fusion de résultats de classifications obtenus à partir de différents classifieurs91
5.2. La fusion de classifications obtenues à partir de jeux de dates différents
5.3. La fusion de classifications obtenues à partir de sources différentes
5.4. La fusion des meilleurs jeux de données temporelles, spectrales et classifieurs, application du système SCF
6. Conclusion
Chapitre V. La classification à partir d’une collection de données statistiques de valeurs radiométriques
1. Introduction
2. Interpolation des données statistiques
2.1. Méthodes d’interpolation par Krigeage
2.2. Evaluation de l’interpolation temporelle des classes
3. Applications
3.1. Application à la classification de données d’années différentes et d’une emprise différente
3.2. Application à la classification de données d’une année différente
4. Conclusion
Chapitre VI. Analyse de changements annuels et modélisation de flux de carbone
1. Introduction
2. La rotation des classes, les enjeux
3. Le modèle de flux de carbone
3.1. Les modèles existants
3.2. Le modèle choisi
4. Applications : carte des changements et estimation des flux de Carbone
4.1. A partir d’images Formosat-2 des années 2006 à 2009
4.2. A partir d’images Spot-2/4/5 des années 2006 à 2010
4.3. Validation croisée de la zone commune des 2 satellites
5. Conclusion
Chapitre VII. La classification de la Trame Verte et Bleue en milieu agricole, entre enjeux et réalités.
1. Introduction
2. Etudes de l’utilisation de la télédétection pour la cartographie de la trame verte en milieu agricole
2.1. Etude de l’impact de la résolution spatiale pour la cartographie de la trame verte en milieu agricole
2.2. Etude de l’impact du choix de la méthode de classification pour la cartographie des haies
3. Conclusion
Conclusion générale
Références
Références de l’auteur
Liste des figures
Liste des tableaux
Annexes
1. Données utilisées pour les applications
1.1. Récapitulatif des données utilisées
1.2. Récapitulatif des caractéristiques des satellites utilisés
1.3. Les données Formosat-2
1.4. Les données Spot-2/4/5
1.5. Les données Landsat-5/7
1.6. Les données Pléiades-1
2. Applications et collaborations
2.1. Apport de la télédétection en géologie
2.2. Cartographie d’une palmeraie aux environs d’Agadir, Maroc
3. Articles
3.1. Article 1, publié dans International Journal of Geomatics and Spatial Analysis, 2012
3.2. Article 2, publié dans IEEE Geoscience and Remote Sensing Symposium, 2012
3.3. Article 3, publié dans IEEE Analysis of Multitemporal Remote Sensing Images, 2011