Segmentation d’images texturées par régularisation de classificateurs

Classification supervisée de données

La classification de données est une branche de l’apprentissage automatique. Ce domaine vise à produire des « machines » qui, à partir d’un jeu de données caractéristique d’un système, sont capables d’inférer un ensemble de règles visant à modéliser le système dans son ensemble. De manière générale, cette modélisation permet d’associer un label à chaque individu de l’espace considéré. Ces techniques s’opposent donc aux systèmes experts, des outils d’aide à la décision conçus pour appliquer un ensemble de règles à de nouveaux jeux de données. À la différence des méthodes d’apprentissage automatique, les systèmes experts requièrent que les règles aient au préalable été fixées par un expert humain, selon un formalisme spécifique à l’outil. L’intérêt des systèmes experts a cependant décliné avec la généralisation des outils informatiques : ces derniers permettant d’obtenir facilement de grands volumes de données, il est devenu impossible pour un expert humain de fournir une modélisation pertinente d’un système complexe. Les méthodes d’apprentissage automatique se divisent en plusieurs catégories qui identifient le mode d’apprentissage. Les trois principales sont : l’apprentissage supervisé, l’apprentissage non-supervisé et l’apprentissage semi-supervisé. Nous allons voir que lorsque les données sont représentées à l’aide de graphes, ou encore que la modélisation du système est soumise à certaines contraintes, il est alors possible d’établir un pont entre certaines de ces catégories. En apprentissage supervisé, un ensemble d’apprentissage constitué de n individus et de leurs labels respectifs est requis. Cet ensemble, choisi pour être le plus représentatif possible des différentes classes que l’on souhaite identifier, est utilisé pour entraîner l’algorithme et générer la modélisation du problème. En comptant sur la capacité du modèle à généraliser ce qu’il a assimilé durant la phase d’apprentissage, celui-ci peut ensuite être appliqué à tout nouvel individu d’un ensemble de test afin de lui associer son propre label. Un algorithme d’apprentissage est qualifié de non-supervisé lorsque son objectif est de détecter des structures cachées dans un ensemble de test. Puisque ces structures sont a priori inconnues, l’algorithme se base sur des notions de proximité et d’homogénéité afin d’identifier des groupes composés des données les plus similaires. L’apprentissage semi-supervisé consiste à utiliser à la fois des données labellisées et non-labellisées pour entraîner l’algorithme. Afin de compléter l’information contenue dans l’ensemble d’apprentissage, des notions de régularité ou de proximité sont utilisées. La labellisation automatique de certaines données – qui viendront s’ajouter à l’ensemble d’apprentissage initial – permet en particulier de rendre un algorithme supervisé plus robuste. Cette technique minimise en effet l’éventualité d’un sur-apprentissage lorsque les données labellisées ne sont disponible qu’en faible quantité [Zhu, 2005, Chapelle et Schölkopf, 2006]. Certains méthodes d’apprentissage supervisé peuvent être vues comme des problèmes d’interpolation : des marqueurs initiaux sont fournis pour un ensemble d’individus qui doivent être utilisés pour calculer le label d’individus « intermédiaires ». Le problème est alors résolu par diffusion des labels présents dans l’ensemble d’apprentissage aux individus non-labellisés. Cette diffusion se déroule de proche en proche, en suivant les règles de voisinage imposées par la structure des données. L’une des hypothèses sur lesquelles s’appuie l’apprentissage semi-supervisé est que, dans un espace de grande dimension, les données reposent en réalité dans une variété de faible dimension. Cela s’illustre aisément à l’aide d’un graphe de similarité : les nœuds similaires sont généralement situés dans des sous-graphes présentant une forte connexité (voir figure 3.1). La topologie du graphe constitue ainsi une représentation implicite de ces variétés, permettant à un processus de diffusion de se dérouler selon un principe géodésique (en suivant la structure des données) et non plus selon un principe Euclidien. L’algorithme est donc capable de tirer parti des relations qui ont été établies avec des données potentiellement non labellisées pour mener à bien sa tâche. Pour cette raison, les méthodes d’apprentissage automatique qui se basent sur des graphes sont souvent qualifiés de semi-supervisées.

Méthode des k plus proches voisins 

La méthode des k plus proches voisins 2 est l’un des algorithmes de classification de données les plus simples [Fix et Hodges, 1951]. Cette méthode ne repose pas sur un algorithme d’apprentissage à proprement parler, mais sur une heuristique qui réalise une classification par analogie : la classe attribuée à un individu inconnu correspond à la classe des individus connus les plus similaires. Plus précisément, il s’agit d’appliquer le principe du vote majoritaire à partir des k individus de l’ensemble d’apprentissage les plus proches. Il n’y a donc pas de phase d’apprentissage, tous les calculs sont effectués lors la phase.de classification. Pour chaque individu à classer, il est nécessaire de calculer la distance entre cet individu et ceux présents dans l’ensemble d’apprentissage. Plusieurs mesures de distances sont couramment employées : distance Euclidienne ou de Manhattan pour les données numérique [Weijer et Schmid, 2006], distance de Hamming pour les données symboliques [Smith et al., 1994] ou encore distance de Mahalanobis lorsque l’on est en présence de données bruitées [Yates et al., 2003]. Étant dépourvu de phase d’apprentissage, ce classificateur est apprécié pour sa capacité à assimiler instantanément de nouvelles connaissances. Cependant, derrière l’apparente simplicité de cette méthode, des précautions doivent être prises quant à la constitution de l’ensemble d’apprentissage. Tout d’abord, il est important de disposer de données dont les attributs sont normalisés. Les mesures de distance traditionnelles ne permettent pas de tenir compte de l’amplitude des valeurs selon chacune des dimensions. Appliqué à notre problématique, cela signifie qu’une caractéristique de textures présentant de faibles variations pourrait être masquée par une caractéristique de plus forte amplitude. De plus, les individus présents dans cet ensemble doivent être identiquement distribués dans leur espace. En effet, étant donné que seuls les k plus proches voisins sont considérés, il y a un risque d’introduire un biais dans la classification si une classe est statistiquement plus représentée qu’une autre. Enfin, lorsque l’espace des individus est composé d’un nombre important de dimensions, les mesures de distance perdent de leur intérêt [Beyer et Goldstein, 1999]. Cette méthode est ainsi sujette à ce qui est couramment appelé la « malédiction de la dimension ». Afin de remédier à cela, il convient d’utiliser des techniques de sélection de caractéristiques, telles que l’analyse en composantes principales. Cependant, cela revient à la mise en place d’une phase d’apprentissage. 

Réseaux de neurones artificiels

 Un neurone biologique est un élément de base du système nerveux. Il s’agit d’une cellule qui peut être excitée par une impulsion nerveuse et qui, en fonction de son excitation, est capable d’émettre de nouvelles impulsions. Les neurones sont présents en grande quantité dans un cerveau, et sont impliqués dans l’essentiel des fonctions cognitives d’un être vivant. Le cerveau fonctionne en effet selon une approche connexionniste : des processus complexes émergent de réseaux d’unités fonctionnelles simples interconnectées (les neurones). Les réseaux de neurones artificiels constituent une classe d’outils de modélisation inspirés du fonctionnement du cerveau. Introduits dans [Rosenblatt, 1958], le principe est d’interconnecter de nombreuses unités de calcul simples, appelées neurones formels, afin de permettre la résolution de problèmes complexes. Présenté dans [Rumelhart et al., 1986], l’un des modèles de réseaux de neurones les plus populaires est le perceptron multicouche 3 , connu pour être un approximateur universel de fonctions [Hornik et al., 1989,Hartman et al., 1990]. Il s’agit d’un réseau à propagation avant composé de plusieurs couches de neurones de type perceptron. Chaque neurone représente une unité de calcul capable de résoudre un problème de séparation linéaire, et reçoit en entrée l’ensemble des valeurs calculées par les neurones de la couche qui le précède (sauf la couche d’entrée qui reçoit les données du problème). Cette interconnexion de neurones permet la résolution de problèmes non-linéaires. La figure 3.2 ainsi que les formules (3.1) et (3.2) décrivent le fonctionnement d’un perceptron d’indice j :avec I = {S1 . . .Sn} l’ensemble des entrées de ce neurone, {Wj1 . . .Wjn} les poids associés aux entrées, bj un biais et fj () une fonction de transfert, généralement une fonction de type sigmoïde ou log-sigmoïde. Sj représente la sortie de ce neurone. Un MLP est ainsi constitué de plusieurs couches. La première est appelée couche d’entrée et reçoit les données du problème, tandis que la dernière est appelée couche de sortie et contient la réponse du réseau. Les couches intermédiaires sont appelées couches cachées. Chaque couche d’un MLP est fortement connectée à la couche précédente : les entrées d’un neurone correspondent aux sorties de ceux de la couche précédente 4 . Le nombre de neurones sur la couche d’entrée est égal à la dimension du problème, tandis que le nombre de neurones de sortie peut varier en fonction de sa modélisation. Le nombre de couches et de neurones cachés est à fixer en fonction de la complexité du problème. La figure 3.3 schématise la structure d’un MLP composé de quatre entrées, une couche cachée de cinq neurones et d’une unique sortie. Un réseau de neurones artificiels nécessite un apprentissage afin de résoudre un problème particulier. Cette phase revient à fixer les poids et les biais de chacun des neurones. L’algorithme de rétropropagation du gradient [Rumelhart et al., 1986], la première méthode permettant d’entraîner un perceptron multicouche, est encore largement utilisée aujourd’hui. Elle consiste à présenter chaque individu de l’ensemble d’apprentissage au réseau de neurones. Les valeurs obtenues en sortie sont ensuite comparées à celles attendues et les poids et biais de chaque neurone sont mis à jour selon leur influence sur l’erreur. Ce processus est exécuté itérativement jusqu’à ce que la modélisation soit suffisamment vraisemblable. Il est ainsi courant de diviser l’ensemble des données disponibles pour l’apprentissage en deux sous-ensembles : l’ensemble d’apprentissage et l’ensemble de validation.reste utilisé pour entraîner le réseau alors que le second permet de mesurer l’aptitude du réseau à généraliser et ainsi de prévenir le sur-apprentissage. Un troisième sous-ensemble, l’ensemble de test, peut aussi être utilisé afin de choisir le nombre de couches et de neurones cachés que doit comporter le réseau pour modéliser au mieux et le plus efficacement le problème.

Machines à vecteurs supports

Les machines à vecteurs supports 5 constituent l’une des plus récentes approches de la classification supervisée de données. Elles sont notamment reconnues pour leur bonnes performances vis à vis du traitement de problèmes non linéairement séparables [Suykens, 2001]. Ce résultat s’oppose cependant à l’une des théories sur lesquelles cette approche repose : la notion de marge maximale. Étant donné un jeu de données composé de deux classes d’éléments et un algorithme chargé de calculer la frontière séparant les données, la marge est définie comme la distance minimale qui existe entre la frontière de séparation et les données les plus proches (voir figure 3.4). La maximisation de cette marge constitue une heuristique dont le but est de réduire l’erreur de généralisation de l’algorithme d’apprentissage en charge du calcul de la frontière : plus la marge est importante, moins l’algorithme a de chances de mal classer un individu inconnu. Dans une machine à vecteurs supports, cette notion de marge maximale est appliquée au calcul d’un hyperplan séparateur. Soit R n l’espace de définition des données. Un hyperplan de cet espace correspond à l’ensemble des x ∈ R n tel que : wT · x + w0 = 0 , (3.3) avec w = (w1 . . . wn) et w0 ses paramètres. Soit X = {(x1, c1). . .(xp, cp)} un ensemble d’apprentissage avec ck ∈ {−1, +1} la classe d’appartenance de l’individu xk. Le calcul de l’hyperplan de marge minimale est obtenu par résolution du problème suivant : arg max w,w0  1 ||w|| min k  ck(wT · xk + w0)  . (3.4) Il s’agit d’un problème d’optimisation quadratique que de nombreuses méthodes permettent de résoudre. Nous pouvons notamment citer celles basées sur les algorithmes génétiques [Pai et Hong, 2005, Zhang et al., 2009] ou encore les méthodes de recuit simulé [Lin et al., 2008,Zhang et al., 2009]. Après calcul de l’hyperplan séparateur, la classification d’un nouvel individu est obtenue en mesurant sa distance à l’hyperplan, par projection orthogonale. Le signe de cette distance est alors indicatif de la classification. Dans cette configuration, l’hyperplan n’est calculé qu’à partir des données les plus proches de la frontière. Il suffit donc d’une donnée bruitée ou erronée à proximité de la frontière pour décaler l’hyperplan séparateur, réduisant ainsi la capacité de généralisation du classificateur. Afin de rendre les machines à vecteurs supports plus robustes, une configuration relaxée du problème appelée « marges souples » fut proposée [Cortes et Vapnik, 1995]. Celle-ci autorise certains éléments de l’ensemble d’apprentissage à se trouver à une distance de l’hyperplan inférieure à la marge, ou même à être mal classés. La frontière étant un hyperplan, l’approche par marge maximale ne peut être appliquée avec succès qu’à des problèmes linéairement séparables. L’originalité des machines à vecteurs supports est due à Vapnik qui proposa de remédier à cette limitation en projetant les données d’entrée dans un espace de plus grande dimension [Vapnik, 1995]. Comme l’illustre la figure 3.5, cette opération peut en effet permettre de rendre linéairement séparable un problème qui ne l’est pas dans son espace d’origine. Cet opérateur de projection s’appelle une fonction noyau. À l’inverse de nombreux algorithmes de classification qui tentent de calculer une frontière non linéaire, ce sont ici les données qui sont modifiées afin de permettre la résolution d’un problème « plus simple ». Cette innovation n’est cependant pas sans défaut puisqu’en 0 x (a) Données non linéairement séparables dans un espace de dimension 1. 0 x x 2 (b) Données linéairement séparables dans un espace de dimension 2. Figure 3.5 – Exemple de problème qui n’est linéairement séparable que lorsque les données sont projetées dans un espace de plus grande dimension. l’absence d’a priori concernant les données, il est nécessaire de recourir à des fonctions noyau qui maximisent la probabilité de rendre le problème linéairement séparable. L’espace dans lequel sont projetées les données peut ainsi être de très grande dimension, rendant le problème insolvable. La solution consiste à appliquer « l’astuce du noyau » (kernel trick) . Pour des fonctions noyau respectant certains propriétés, cette astuce rend inutile l’étape de projection, réduisant ainsi considérablement la complexité des opérations. 

Bilan des méthodes de classification supervisée

 La méthode des k plus proches voisins est souvent choisie pour sa simplicité de mise en œuvre. Nous ne l’avons cependant pas retenue pour plusieurs raisons, essentiellement liées à l’absence de phase d’apprentissage capable de synthétiser les données. Le but recherché par l’ajout d’un classificateur à notre méthode de segmentation est de permettre une pondération automatique des différentes caractéristiques de textures. L’algorithme des k plus proches voisins étant uniquement basé sur une comparaison de mesures de distance, il est, au même titre que le critère d’attache aux données de Chan et Vese, incapable d’identifier la pertinence des différentes caractéristiques de textures et donc de les pondérer. Nous sommes par ailleurs amenés à travailler avec un nombre important de caractéristiques de textures, ce qui est un contexte défavorable aux k-PPV puisque ce classificateur est sujet à la malédiction de la dimension. Nous pouvons aussi noter que la classification d’un individu est un processus relativement long, puisque cela nécessite de calculer sa distance à chacun des éléments de l’ensemble d’apprentissage. La littérature cite régulièrement les mérites des machines à vecteurs supports, qui sont notamment reconnues comme sensiblement plus performantes que les réseaux de neurones, tant en termes de précision que de rapidité d’exécution . L’objectif de nos travaux n’étant pas l’évaluation des performances de classificateurs, nous nous sommes tournés vers celui qui nous est le plus familier : les réseaux de neurones artificiels. Ce choix nous permet notamment de limiter les risques liés à une mauvaise configuration des classificateurs, et ainsi de nous focaliser sur leur intégration dans le processus de régularisation. La méthode que nous proposons reste compatible avec l’ensemble des classificateurs supervisés connu ce jour. Des travaux visant à permettre l’utilisation de classificateurs différents sont actuellement menés.