of 52

Diffusion sur graphes, construction de classificateurs parcimonieux : deux approches pour le traitement d images microscopiques

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
Diffusion sur graphes, construction de classificateurs parcimonieux : deux approches pour le traitement d images microscopiques Olivier Lezoray Université de Caen Basse-Normandie,
Transcript
Diffusion sur graphes, construction de classificateurs parcimonieux : deux approches pour le traitement d images microscopiques Olivier Lezoray Université de Caen Basse-Normandie, GREYC UMR CNRS 6072, Caen, France Paris, Janvier 2009 1 Introduction 2 Construction de classificateurs parcimonieux 3 Diffusion sur graphes 4 Vers de nouvelles modalités 1 Introduction 2 Construction de classificateurs parcimonieux 3 Diffusion sur graphes 4 Vers de nouvelles modalités Pathologie La pathologie est une discipline de la médecine dédiée à l étude des causes et des mécanismes des maladies. L anatomie pathologique est l étude morphologique des maladies par l examen macroscopique ou l examen microscopique. Il s agit principalement de l étude des lésions crées par les maladies et les phénomènes pathologiques. La pathologie diagnostique a pour but d analyser des liquides biologiques (cytologie) ou des prélèvements tissulaires (histologie) dans le but d identifier une maladie ou une tumeur (diagnostic), de caractériser sa cause ou son prognostic. Cytologie et Histologie Gynécologie (Papanicolaou x20), Hématologie (H&E x100), ADN (Feulgen x60) Sein (Immuno x33), Sein (Feulgen x33), Colon (Feulgen x33) Éléments de modélisation d images microscopiques Nous parlerons uniquement de Classification/Segmentation : Automatique basée sur des classificateurs parcimonieux, Semi-automatique basée sur une diffusion sur graphes. Traitement et analyse d images microscopiques 1 Introduction 2 Construction de classificateurs parcimonieux 3 Diffusion sur graphes 4 Vers de nouvelles modalités Traitement et analyse d images en cytopathologie Le traitement et l analyse d images sont des outils d aide au diagnostic pour le screening automatique en cytopathologie. La quantité d information visuelle exploitée par un cytopathologiste est énorme (beaucoup de cellules par image et beaucoup d image par lame). Un pathologiste va cependant mettre quelques dizaines de minutes pour analyser une lame. Contraintes Environ images par lame. Un schéma de segmentation d images microscopiques doit être efficace et rapide afin de permettre une analyse d un grand nombre d images. Cytologie bronchique Nous nous intéressons à la cytologie bronchique pour l aide au diagnostic du cancer du poumon. Schéma de segmentation Nous avons adopté le schéma de segmentation général suivant pour l extraction des cellules (cytoplasme et noyau) : 1 Changement éventuel d espace couleur de réprésentation des couleur des pixels, 2 Classification supervisée des pixels en trois classes (fond, cytoplasme, noyau), 3 Rafinement des frontières par segmentation morphologique (érosion des frontières et ligne de partage des eaux). Classification supervisée de pixels d images microscopiques Nous disposons d une base de 10 images manuellement annotées par un pathologiste ou les pixels sont répartis en trois classes. Ces images sont représentatives des différentes configurations cellulaires. Une image couleur fait 752x576 pixels, soit une base d apprentissage de plus de 4 millions d exemples! Exemples de résultats de classification de pixels Classification de pixels par SVM Premier bilan Les SVM sont des classificateurs efficaces pour la classification de pixels en microscopie. Le temps d apprentissage est très consommateur de temps. Il faut régler deux paramètres (σ et C). La complexité de la fonction de décision augmente avec la taille de la base d apprentissage, mais pas forcément l efficacité de la fonction de décision. Beaucoup de redondance parmi les exemples de la base d apprentissage Le choix de l espace couleur a une grande influence sur les résultats La contrainte imposée de rapidité d analyse est mise à mal avec : Des temps d apprentissage prohibitifs, Des temps de classification trop longs (10 minutes pour classer une image avec un SVM ayant appris sur la base d apprentissage complète). Nécéssité de disposer de classificateurs efficaces et de complexité réduite (parcimonieux). Apprentissage supervisé Les composants usuels Données x X Sélection des exemples pertinents Sélection des attributs pertinents Schéma de décomposition Sélection des hyperparamètres Algorithme d apprentissage supervisé Fonction de décision Principe de Décodage Décision y Y Vers des classificateurs parcimonieux Le problème Une base de pixels étiquetée de taille importante en terme de volume (nombre d exemples) et de dimension (nombre d attributs). Cette grande taille s accompagne d une redondance au niveau des exemples et des attributs (qui peuvent alors être non pertinents). Ceci a deux conséquences : des temps d apprentissage longs et des fonctions de décision de grande complexité. Notre point de vue Nous voulons Avoir des fonctions de décision parcimonieuses qui ont de bonnes performances en généralisation tout en restant efficaces. Il nous faut diposer d un sélection de modèle qui peut simultanément de : Sélectionner les exemples pertinents, Sélectionner les attributs pertinents, Sélectionner les hyper-paramètres du classificateur. Sélectionner des exemples pertinents (1) Pour réduire la taille de la base d apprentissage, nous utilisons un algorithme de quantification vectorielle (LBG). Sélectionner des exemples pertinents (2) L hyperplan trouvé avec l algorithme des SVM sur la base simplifiée est une bonne approximation de celui produit avec une base non simplifiée. Sélectionner des exemples pertinents (3) Avantages de la sélection des exemples pertinents Temps d apprentissage réduit pour évaluer un couple d hyper-paramètres Complexité réduite de la fonction de décision (peu de vecteurs supports) Possibilités d obtenir de bonnes capacités en généralisation (relativement à une plus grande sensibilité aux valeurs des hyper-paramètres). Sélectionner des exemples pertinents (4) Sélection de modèle pour un SVM Élements pour une sélection de modèle d un SVM Utiliser la quantification vectorielle pour trouver 2 k prototypes pertinents. Modifier la fonction noyau pour intégrer la prise en compte d une sélection d attributs (utiliser un vecteur d entiers β spécifiant la sélection ou non d un attribut). Sélectionner les hyper-parametres (C and σ). 0 n 1 P β i `ui v 2 i K β (u, v) = exp i=1 2σ 2 C A Probleme L espace de recherche est trop grand. Nous utilisons une sélection de modèle à l aide d une méta-heuristique : la recherche tabou. Optimization globale par recherche Tabou Évaluation de la qualité d une fonction de décision Nous la définissons comme un compromis entre fidélité et complexité : q FD = E fidélité + E complexité Une fonction de décision est parcimonieuse et efficace si : Le taux de reconnaissance est élevé (Fidélité), Peu de vecteurs supports sont nécéssaires (Complexité), Peu d attributs sont utilisés (Complexité). Pour un modèle donné θ = (C θ, σ θ,k θ,β θ ) Optimization q FD = (1 e BER ) c VS log 2 (1 + n VS ) c β log 2 ( β) Une recherche tabou est réalisée pour effectuer la sélection de modèle : θ = arg max θ Θ q FD (h θ ) Résultats Résultats avec c VS = 10 2 sans sélection d attributs. FDB1 : fond vs autres FDB2 : cytoplasme vs autres FDB3 : noyau vs autres Le nombre de vecteurs supports dépend fortement du problème de discrimination et des attributs, Cela permet de réduire le nombre de vecteurs supports sans trop perdre en qualité de reconnaissance. Classification de pixels : résultats Espace couleur multi-spectral de 25 composantes provenant de 11 espaces couleur (c VS = c β = 10 2 ). Image Originale ω 1 =fond ω 2 =cytoplasme ω 3 =noyau ω 1 vs-(ω 2, ω 3 ) β = (u,ch 1 ) n vs = 8 taux: 84,9% ω 2 vs-(ω 1, ω 3 ) β = (u,s) n vs = 2 taux: 96,2% ω 3 vs-(ω 1, ω 2 ) β = (B) n vs = 2 taux: 89,6% Classification de pixels Vérité terrain Segmentation Tps de segmentation 2s (environ une heure pour segmenter une lame entière). Conclusion Segmenter des images microscopiques est un problème difficile Nous avons détaillé une sélection de modèle pour SVM qui permet de Sélectionner les exemples pertinents, Sélectionner les attributs pertinents, Sélectionner les hyper-paramètres. Cela permet de construire des classificateurs de complexité réduite qui sont efficaces et rapides La perte en taux de reconnaissance n a pas quasiment pas d incidence sur le résultat final en segmentation. 1 Introduction 2 Construction de classificateurs parcimonieux 3 Diffusion sur graphes 4 Vers de nouvelles modalités Continu versus Discret Les méthodes variationelles, basées sur la régularisation, fournissent un cadre général pour la conception de méthodes efficaces de traitement d image. Les solutions de tels modèles variationnels peuvent être obtenus en minimisant des fonctions d énergie appropriées. Ceci est habituellement effectué par des des Equations aux Dérivées Partielles, dont les solutions sont discrétisées pour correspondre au domaine de l image (une grille régulière). Nous admettons la nature discrète des images et nous utilisons des graphes pour les représenter Nous proposons un analogue discret de la régularisation continue qui opère sur des graphes de topologies arbitraires. Topologie d un graphe en traitement d image Une Image Topologie d un graphe en traitement d image Une Image 8-voisinage : 3 3 Topologie d un graphe en traitement d image Une Image 8-voisinage : voisinage : 5 5 Topologie d un graphe en traitement d image Une Image 8-voisinage : voisinage : 5 5 Interactions locales : une valeur par noeud Topologie d un graphe en traitement d image Une Image 8-voisinage : voisinage : 5 5 Interactions nonlocales: un Interactions patch (vecteur locales des valeurs : une valeur dans unpar voisinage) noeud par noeud. Topologie d un graphe en traitement d image Une Image 8-voisinage : voisinage : 5 5 Interactions nonlocales: un Interactions patch (vecteur locales des valeurs : une valeur dans unpar voisinage) noeud par noeud. Avec des graphes Le caractère nonlocal est directement exprimé par la topologie du graphe. La similarité entre patchs est utilisée pour pondérer les arêtes. Topologie d un graphe en traitement d image Une Image 8-voisinage : voisinage : 5 5 Interactions nonlocales: un Interactions patch (vecteur locales des valeurs : une valeur dans unpar voisinage) noeud par noeud. Notre point de vue Avec cette représentation, nous désirons reformuler des problèmes de traitement d images sur graphes de topologie arbitraires. Éléments de base sur les graphes pondérés Un graphe G est un couple G = (V,E) où V est un ensemble fini de noeuds et E V V est en ensemble d arêtes. Les graphes sont supposés simple, non dirigé et sans boucles. Un graphe est dit pondéré si une fonction de pondération lui est associée w : E R + satisfaisant w(u,v) = w(v,u) et w(u,v) 0 (u,v) E. u v désigne l ensemble des noeuds connectés au noeud u par une arête. Espace des fonctions sur graphes Soit H(V) l espace de Hilbert des fonctions à valeurs réelles sur les noeuds, dans lequel chaque fonction f : V R + associe une valeur réelle f (v) à chaque noeud v. L espace des fonctions H(V) est muni du produit scalaire usuel f,g H(V) = f (v)g(v) où f et g sont deux fonctions de H(V). v V On définit de manière similaire H(E) comme l espace des fonctions à valeurs réelles sur les arêtes, dans lequel chaque fonction h : E R + associe une valeur réelle à chaque arête e E Opérateurs différentiels sur graphes L opérateur de différence d : H(V) H(E) d une fonction f H(V) en une arête (u,v) est défini par (df )(u,v) = w(u,v)(f (v) f (u)) (1) La dérivée directionnelle de f, en v V, le long d une arête e = (u,v), est définie par : f e = v f (u) = (df )(u,v). (2) u L opérateur adjoint de l opérateur de différence, noté d : H(E) H(V), est un opérateur linéaire défini par : df,h H(E) = f,d H H(V), (3) pour tout f H(V) et tout H H(E). L opérateur adjoint d, d une fonction H H(E), peut s exprimer pour un noeud u V par l expression suivante : (d H)(u) = ( div(h))(u) = v u w(u,v)(h(v,u) H(u,v)). (4) Opérateur de gradient pondéré L opérateur de gradient pondéré d une fonction f H(V), en un noeud u V, est l opérateur vectoriel défini par : w f (u) = [ v f (u) : v u] T = [ v1 f (u),..., vk f (u)] T, (u,v i ) E. La norme L 2 de ce vecteur représente la variation locale de la fonction f en un noeud du graphe. Elle est définie par : w f (u) = (2) = ( v f (u)) 2 v u w(u,v)(f (v) f (u)) 2. v u (5) Une famille d opérateurs p-laplacien pondérés Soit p (0,+ ) un nombre réel. Le p-laplacien pondéré d une fonction f H(V), noté p w : H(V) H(V), est défini par : p wf (u) = 1 2 d ( w f (u) p 2 df (u,v)). (6) Le p-laplacien d une fonction f H(V), en un noeud u V, est défini par : p wf (u) = 1 2 γw(u,v)(f f (u) f (v)), (7) v u avec γ f w(u,v) = w(u,v)( w f (v) p 2 + w f (u) p 2 ). (8) Laplacien et courbure Pour p = 2, cela correspond au combinatorial graph Laplacian w f (u) = v u w(u,v)(f (u) f (v)). (9) Pour p = 1, c est la courbure pondérée ( w(u,v) κ w f (u) = 1 2 w f (v) + w(u,v) ) (f (u) f (v)). (10) w f (u) v u Régularisation p-laplacienne La régularisation de données discrètes sur un graphe pondéré d une fonction f 0 H(V) est formalisée par le problème suivant de minimisation : { E p w (f,f 0, λ) = Rw(f p ) + λ 2 f f 0 2 } 2, (11) min f H(V) où p (0,+ ) est de le degré de régularité, λ est le paramètre d attache aux données. La fonctionnelle de régularisation R p w : H(V) R est définie par : R p w(f ) = 1 p w f (u) p = 1 p ( w(u,v)(f (v) f (u)) 2 ) p 2. (12) u V u V v u Pour obtenir la solution de ce problème de minimisation, nous considérons le système suivant d équations: E p w(f,f 0, λ) f (u) = 0, u V, (13) qui est réécrit comme : De plus, on peut prouver que Alors, on obtient qui est équivalent à ( R p w(f ) f (u) + λ(f (u) f 0 (u)) = 0, u V. (14) R p w(f ) f (u) = 2 p wf (u), u V. (15) 2 p wf (u) + λ(f (u) f 0 (u)) = 0, u V, (16) λ + v u γ f w(u,v) ) f (u) v u γ f w(u,v)f (v) = λf 0 (u). (17) Une famille de processus de diffusion discrets Nous utilisons une méthode itérative pour résoudre le précédent système d équations. Soit t le numéro de l itération, et soit f (t) la solution à l itération t. Alors l algorithme est le suivant : f (0) = f 0 f (t+1) (u) = λf 0 (u) + v u λ + v u γf (t) w (u,v)f (t) (v), u V. (t) γf w (u,v) Cela décrit une famille de processus discrets de diffusion dont les paramètres sont la structure du graphe (topologie et fonction de poids), les paramètres p et λ. (18) Clustering semi-supervisé Soit C={c i } i=1,...,k un ensemble des noeuds labélisés et V \C l ensemble des noeuds non labélisés (que l on cherche à affecter à l un des k labels). Nous considérons k fonctions d appartenance (une par classe) fi 0 :V R, avec i=1,..., k. Pour un noeud u V, si u est labelisé alors f 0 i (u)= { +1, si u c i 1, sinon. (19) Si u est non labelisé (i.e. u V \C) alors fi 0 (u)=0. Nous utilisons notre processus de diffusion discret pour estimer les probabilités d appartenance d un noeud à chaque classe: k processus sont effectués en parallèle et, à convergence, la décision finale est prise par: { argmax f i (u)/ } f i (u). (20) i i Applications en Traitement d images microscopiques Segmentation semi-supervisée (p = 1, λ = 1) avec graphe grille ((d), (h), t = 50), RAG avec 98% de réduction ((e), (i), t = 5), graphe complet ((f)-(g), (j)-(k), t = 2). Applications en Traitement d images microscopiques Applications en Traitement d images microscopiques Conclusion Intérêt de l approche proposée Formulation discrète de la régularisation p-laplacienne, Expression directe de nombreux filtres de la littérature, Unifie, généralise et étend les trois modèles de traitement (local, semi-local, nonlocal), Repose sur des graphes de topologies arbitraires, Un même formalisme permet d effectuer filtrage et segmentation. L utilisation de graphes d adjacence de régions permet d obtenir des méthodes rapides et efficaces. 1 Introduction 2 Construction de classificateurs parcimonieux 3 Diffusion sur graphes 4 Vers de nouvelles modalités Images de lame entière Merci de votre attention. Publications disponibles à : lezoray
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