Insertion d’équations pour les fans de lateX

Une méthode simple pour insérer des équations pour les utilisateurs de lateX :

il suffit d’insérer une image de l’équation obtenue à partir de l’adresse :

http://www.forkosh.dreamhost.com/mathtex.cgi?formdata=
+ écriture de l’équation comme sous latex

Exemple : pour l’image ci-dessous 

j’ai inséré une image avec comme source le lien :

http://www.forkosh.dreamhost.com/mathtex.cgi?formdata=\int_a^b(x^2)

Voilà pour l’astuce.
Un grand merci à mon chéri qui est vraiment très fort et très gentil de s’être préoccupé de mon petit problème.

C’est la fin des haricots

Ca y est ma semaine de partiels est terminée ! Je suis assez satisfaite :

• 100 % d’efficacité, le temps éveillé n’a servi qu’au travail
• 75 % de succès, le travail paye toujours

Bref je garderai un bon souvenir de cette semaine éprouvante. J’espère juste qu’il me restera assez de force pour entamer mon stage de façon dynamique.

Emploi du temps de cette semaine :

•  lundi : matin DS d’ANREC, après-m : DS de GRAPH
• mardi : matin conférence, après-m : DS de MADIS
• mercredi : matin soutenance projet de veille, midi : DS d’APPLI, après-m : DS de QLOGI
• jeudi : soutenance d’anglais pour le matin, DS de finance l’après-m
• vendredi : conférence (soutenance des collègues), après-m : soutenance de projet d’application (développement sous OpenOffice.org), il faudra d’ailleurs que je vous parle de ce projet

À part ça j’ai tellement aimé mon projet de veille que je crois que je vais le continuer mais de manière plus cool. En plus j’ai repéré quelques erreurs potentielles dans ce que j’ai écrit. Bref il faut que je reprenne tout ça. D’ailleurs je change de méthode : j’avais essayé de passer directement de source informatique à des résumés informatiques, résultat : j’ai l’impression que je n’ai aucun recul sur ce que j’ai fait. Donc je reprends tout en passant par des notes que je vais faire au fur et à mesure. C’est plus long mais ça me permettra de communiquer des informations exactes (ou presque ^^).

Lundi je commence mon stage (à Paris, à Mobile Devices) : je vais faire des GPS !!! trop cool ^^ J’espère que ça va bien se passer. Je vous en dirai plus Lundi soir !

Segmentation split-and-merge

Tous le mérite revient à : la thèse de M. Fontaine

1) méthode par quadtree

Le principe de l’algorithme est d’associer un arbre à l’image à segmenter.

• Initialement, il n’y a que la racine.
• Puis, de manière itérative on attribue quatre noeuds fils à chaque noeud correspondant à une zone non homogène. Le découpage correspond a une division en 4 carrés de la région.
  Chaque noeud correspond donc une région carré de l’image.
• On arrête l’analyse récursive lorsque toutes les feuilles de l’arbre respectent le prédicat d’homogénéité.
• On démarre une nouvelle analyse récursive pour tester si des régions présentent des caractéristiques d’homogénéité deux à deux et on réalise la fusion lorsque le cas se présente.
• L’itération est arrêtée lorsqu’il n’y a plus de couple qui respecte le prédicat d’homogénéité.

Inconvénients : 

• la forme carrée des régions ne permet pas d’être précis sur la forme des objets
• l’algorithme est sensible à l’ordre de parcours du quadtree.

2) méthode par partitionnement de Voronoï

La méthode de segmentation proposée comporte une étape d’initialisation, une étape de division suivie d’une étape de fusion : 

• Initialisation : Des germes sont positionnés et répartis uniformément dans l’image grâce à un processus de Poisson. A chaque germe est associée une région dont les frontières sont établies grâce à un diagramme de Voronoï. 
• Division : Un prédicat d’homogénéité est calculé pour chaque région et les régions non homogènes sont divisées par introduction de nouveaux germes. Le diagramme de Voronoï est remis à jour et le processus de division est réitéré jusqu’à ce que toutes les régions de Voronoï respectent un prédicat d’homogénéité. 
• Fusion : Les germes qui ne correspondent pas à un objet dans l’image sont éliminés dans cette dernière étape. Ainsi, les régions adjacentes dont les couleurs moyennes sont proches et pour lesquelles la longueur de la frontière commune divisée par la somme de leurs périmètres est inférieure à un seuil sont fusionnées. 

Inconvénients :

• difficulté d’ajustement du seuil de fusion 
• et résultats influencés par  l’initialisation des germes 

3) méthode utilisant les champs de Markov

Une image est considérée par le formalisme des champs de Markov comme une réalisation particulière d’un champ de variables aléatoires. Les champs de Markov ne se limitent pas à la prise en compte individuelle des pixels car ils permettent de prendre en compte les relations de voisinage entre les pixels. Ainsi, la probabilité qu’un pixel appartienne à une classe dépend non seulement de sa couleur, mais aussi de celles de ses voisins. 

L’algorithme de segmentation se décompose en trois phases : 

• phase de divisions successives de régions, 
       division de division de l’image originale en sous régions déformées carrés ayant une surface supérieure à un seuil et respectant un prédicat d’homogénéité.
       Chaque région est modélisée par sa pseudo-vraisemblance qui est définie comme le produit des probabilités conditionnelles des pixels qui appartiennent à cette région
• phase de fusion préliminaire, 
       deux fusions adjacentes sont fusionnées si le rapport entre les logarithmes de leur pseudo-vraisemblance avant et après fusion est inférieur à un seuil.   
• phase de fusion finale
        les paires de régions adjacentes qui font décroître le moins possible la pseudo-vraisemblance de toute l’image sont fusionnées.
• fin

Les fusions successives s’arrêtent lorsque des régions de couleurs différentes tentent d’être fusionnées. 

Inconvénient :

• la prise en compte des interactions spatiales et colorimétriques entre les pixels , bien qu’adaptée à la segmentation d’images couleur de scènes extérieures, s’avère coûteuse en temps de calcul. 

Segmentation par approche contours

La détection de contour n’est en général qu’une étape préliminaire dans la reconnaissance d’objet car elle fournit plus des informations sur les régions que les régions elle-même et doit donc être complétée par un algorithme de segmentation région. Cependant on peut dire que les contours constituent des indices riches, au même titre que les points d’intérêts, pour toute interprétation ultérieure de l’image et méritent donc d’être traités à part. Les contours dans une image proviennent des : 

• discontinuités de la fonction de réflectance (texture, ombre),  
• discontinuités de profondeur (bords de l’objet), 

et sont caractérisés par des discontinuités de la fonction d’intensité dans les images.

Le principe de la détection de contours repose donc sur l’étude des dérivées de la fonction d’intensité dans l’image :

• les extréma locaux du gradient de la fonction d’intensité d’une part
• et les passages par zéro du laplacien d’autre part.

Ces deux approches ont pour principe d’assimiler les contours aux discontinuités d’ordre 0 de la fonction d’intensité. Hors le calcul de dérivée nécessite un préfiltrage des images. Les filtres sont linéaires dans le cas de bruit de moyenne nulle ou non linéaire pour les bruits impulsionnels.

Les inconvénients sont le plus souvent due à la présence de bruit dans les images.

Les différentes approches existantes peuvent être réparties selon la manière d’estimer les dérivées de la fonction d’intensité :

• par différences finies (opérateurs de Roberts, de Prewitt, de Sobel (très populaire), de Kirch, de Robinson)
• par filtrage optimal (filtres de Shen-Castan, de Deriche, filtre Gaussien)
• par modélisation de la fonction d’intensité

A partir de l’exploitation de la théorie des opérateurs et filtres précédents on peut écrire les algorithmes pour les différentes approches de détection de contours :

1) détection des contours via les gradients

L’algorithme peut donner :

• estimation du gradient en chaque point de l’image, utilisation au choix d’un filtre parmis :
      filtre de Canny
      filtre de Deriche
      filtre de Shen-Castan
  (pour l’essentiel) 
• extraction des maxima locaux de la norme du gradient dans la direction du gradient 
   cela revient à déterminer, pour un pixel donné, les valeurs du gradient sur la droite passant par le pixel et de direction celle de son gradient. On vérifie ensuite que le gradient en le pixel est bien localement maximal sur cette droite. 
• sélection des maxima locaux significatifs par seuillage 
        but : limiter la fragmentation des contours obtenus ; 
        Cette étape repose sur une hypothèse de connexité. Le principe est d’utiliser deux seuils pour la norme du gradient sb et sh et de sélectionner les pixels pour lesquels :
             (a) la norme du gradient est supérieure à sb
             (b) le pixel donné est connecté, par un chemin constitué de pixels dont la norme du gradient est supérieure à sb, à un pixel pour lequel la norme du gradient est supérieure à sh. 
• fermeture des contours en traçant les chemins suivant une ligne de crète dans l’image de la norme du gradient
  Idée : suivre une ligne de crète dans l’image de la norme du gradient à par tir de chaque extrémité de contour. 
        1- Repérer les points extrémité (énumération des configurations possibles) 
        2- Choix entre les points candidats : on explore tous les chemins possibles à par tir de chaque point candidat. Le poids d’un chemin peut être défini comme la somme de la norme du gradient en chacun de ses points

2) détection des contours suivant le laplacien

Les points de contour sont caractérisés par des passages par zéro du laplacien. La détection de ces points s’effectue en deux étapes :

• Détection des passages par zéros. Les pixels pour lesquels le laplacien change de signe sont sélectionnés.
• Seuillage des passages par zéros de fortes amplitudes (par hystérésis par exemple)

Référence

• cours de M. Lachaud
• cours de segmentation contours

Exemple d’algorithme de segmentation approche régions

1) Méthode région par fusion itérative
issu de ‘Efficient Graph-Based Image Segmentation’

Principe :
construction d’un graphe à partir de l’image et de ses pixels.
méthode par fusion itérative des composants de l’image

Méthodologie :

Méthodologie de segmentation

Algorithme de segmentation :
en entrée : le graphique G=(V,E) avec n éléments et m arcs 
     les éléments sont à l’origine les pixels
     les arcs sont la matérialisation de l’adjacence des pixels auxquels on affecte un poids correspondant               à la valeur donnée par le critère de différence
en sortie : une segmentation de l’image en composants S=(C1,…,Cr) 

1. Trier E en pi = (o1,…,om), selon les poids des arcs non décroissants
2. initialement (segmentation initiale ou S(0)) chaque élément est son propre composant
3. répéter l’étape 4 pour q=1,…,m
4. construction de S(q) à partir de S(q-1)
   vi et vj sont deux éléments connectés par le q ième arcs selon l’ordre défini plutôt.
   si vi et vj sont dans des composants disjoints (respectivement Ci(q-1) et Cj(q-1))
   et si le critère de différence est petit comparé à la différence interne propre aux deux composants
         alors on unie les deux composants.
   sinon rien 
   S(q) est donc obtenue à partir de la fusion éventuelle de Ci(q-1) et Cj(q-1) sinon S(q) = S(q-1)
5. on renvoie S=S(m)

Le document source détaille les critères de similitude/différence.

Segmentation par classification/seuillage

Ce type de segmentation a pour objectif d’affecter chaque pixel à une classe unique.

Les méthodes sont :

• les méthodes de seuillage pures
• les méthodes de nuées dynamiques (K-moyenne)
• les méthodes par minimisation de variance
• les méthodes par détection de vallées
• les méthodes de classification bayesienne
• les méthodes neuronales
• les méthodes de classification floue

Ces types de méthodes présentent les inconvénients 

• du choix du nombre de classe (approches non supervisées)
• du choix des attributs 

Les deux étant peu aisés à déterminer.

Présentation rapide des différentes méthodes :

1) Méthode de seuillage par détection de vallée

Cette méthode se base sur l’histogramme des niveaux de gris :

• Recherche des minima locaux de l’histogramme normalisé
• Positionnement des seuils de classification sur ces minima locaux (multiseuillage)

Remarques sur cette méthode :

• Résultats assez moyens sur histogrammes bruités
       nombreuses irrégularités = mauvaise détection des minima locaux
• Assez peu utilisée malgré des techniques d’amélioration de la robustesse par des algorithmes de type lissage d’histogrammes
   

2) Seuillage par minimisation de variance

Cette méthode se base sur la répartition des pixels en K classes : c’est un problème classique de classification.

• on minimise l’intertie intra-classe
• on maximise l’inertie inter-classe

Algorithme de Otsu

• on balaie toutes les valeurs de seuil possible T
• pour chaque seuil T
  on calcule les moyennes et les variances de chaque classe
  on s’intéresse à la variance intra-classe

fin algorithme ? manque de détail dans mes sources

3) méthode de seuillage par classification bayésienne

Cas de ncl classes

• Hypothèse :  chaque classe suit une répartition gaussienne
• Meilleurs seuils = ceux qui minimisent l’erreur de classification
• Soient μi et μj 2 moyennes successives rangées dans l’ordre croissant, on a :

t_ij = (μi+μj)/2+σ^2/(μi-μj) log(P_j/P_i)

L’affectation des pixels :

• i=1
• pour j allant de 2 à ncl
         si intensité_pixel >tij alors i=j 
  finpour
• affecter le pixel à la classe Ci

Remarques :

• Ne tient pas compte du voisinage du point considéré
• Peu performant pour les images complexes

4) méthode de seuillage par hystérisis

Algorithme :

1. Choisir 2 niveaux de seuil (global)
            TL: faire ressortir les éléments désirés incluant des détails non pertinents 
            TH: éléments désirés, avec des manquements 
2. Marquer tous les pixels >TH
3. Pour tous les pixels adjacents aux pixels marqués :
            marquer si >TL
4. Répéter 3 pour tous les pixels marqués dans 2
5. fin 

Référence :

• Lien vers un cours
• lien vers un autre cours

Segmentation par approche régions

On en distingue de deux sortes : 

• méthode par division/fusion
• méthode d’agrégation

Elles ont pour but de rechercher des similarités dans l’image. Elles ont comme inconvénients de mal déterminer les frontières entre régions

1) Segmentation par décomposition/fusion, aussi appelée “split and merge” en anglais.

Elle suit l’algorithme suivant :

étape d’initialisation avec pré-segmentation en général plutôt exagéré 

processus de segmentation itératif en deux phases
     phase de division : division de toutes les régions non homogènes
     phase de fusion de toutes les régions adjacentes dont l’union respecte les critères d’homogénéité. 

Ce type de méthode fait souvent appel à la théorie des graphes.

On y retrouve les exemples :

• partitionnement de Voronoï
• arbre quaternaire
• approches pyramidales

2) Segmentation par croissance de régions (region-growing)

C’est une méthode locale récursive qui a pour principe de faire croître une région avant de passer à la suivante, sans parcours particulier déterminé a priori (méthode par agrégation libre de pixels)

On part d’un germe, il y a croissance suivant un critère de similarité jusqu’à atteindre le critère d’arrêt : par exemple convexité maximum, etc

Les inconvénients sont :

- méthode récursive avec risques de débordements (piles)
- influence de la position initiale des germes
- choix des conditions d’arrêt de croissance des régions
- temps de calcul important
- tendance des algorithmes à trouver un nombre trop important de régions par rapport au nombre d’objets présents dans l’image.
- méthode sensible au bruit 

L’algorithme est globalement :
      choix des germes de régions
      intégration progressive des pixels voisins à chaque germe.

De manière plus détaillée on peut avoir :

•  division de l’image en cellule de k*k pixels
• pour chaque région en cours (initialement les cellules simples) :
      parcours de l’image de gauche à droite et de haut en bas
      pour chaque cellule rencontrée
          test de similitude avec la cellule/régions en cours
               si similitude alors intégration de la cellule à la région en cours et croissance de la région en cours
               sinon on passe à la suivante
  fin.

Autre algorithme (présenté autrement)

Tant que image n’est pas segmentée en entier
1. choisir un pixel non étiqueté
2. examiner les voisins :
           Vj similaire => étiquette k
3. Tant que Vj \in Région k
           Examiner les voisins
           Vi similaire => étiquette k
4. k = k+1 et retour à 1. 
5. fin et fin

Exemple d’algorithme dit des “bassins topographiques” (watershed ?)
Une image est considérée comme un relief topographique où l’altitude de chaque point peut, par ex, être proportionnelle à son intensité lumineuse. Le fond des bassins les plus importants est percé, et le relief est plongé dans l’eau. Les bassins se remplissent progressivement, délimitant ainsi les principales régions.

Autres ex de méthodes par croissance de régions :

• méthode basée sur les arbres couvrants récursifs de poids minimum 

 

Référence des documents “visités” :

• cours6_M2R_Segmentation-a : cours 5 segmentationpar Alain Dieterlen
• Elec376_segmentation.pdf par Olivier Debeir  
• ‘Revue des approches de segmentation d’images texturées : exemple des images météorologiques’

Les boulettes d’EDF

Hier soir j’ai eu l’immense joie de trouver mon appart sans électricité. Merci d’ailleurs à l’éclairage publique qui m’a permis de voir dans mon studio aussi bien qu’en plein jour. Je n’ai pas été très étonnée puisque ça fait un et demi que je ne recevais aucune facture.

Bien sûr, comme ferais tout étudiant responsable, je me suis endormie tranquillou pour me réveiller aujourd’hui avec une bonne inondation issue de mon réfrigérateur qui a décongelé. hin hin hin !

Bon j’ai téléphoné à EDF, j’arrive à joindre un réceptionniste, assez rapidement d’ailleurs, par contre il ne pouvait pas s’empêcher de couper à chaque fois qu’il bidouillait sur son ordi. Absolument insupportable ! J’avais envie de lui parler, de lui demander pourquoi il y avait un problème … mais non, il suivait le chemin : lui, question, moi, réponse (oui/non), musique, lui question, moi réponse, musique … lui question, moi réponse, musique …. Rhaaaaa ! Pour finir un électricien va venir, demain entre 8h et 12h30. Bon heureusement j’ai pas cours. Mais le créneau horaire est un peu large. Je crois que c’est pour la même raison que j’ai râté le premier rdv il y a un an et demi. J’avais la flemme d’attendre. Du coup, peut-être que si je rate ce rdv là-aussi je vais avoir l’électricité gratos pendant la prochaine année ?

L’extraction d’information sémantique des images

• C’est mon projet de veille techno pour l’école !
• Le thème : l’extraction d’information sémantique des images.
• Les limites : aucune. Ma prof est une warrior.

C’est un sujet super intéressant mais tellement vaste ! Je dois faire un rapport de 20 pages et j’avoue que j’ai un peu du mal.

Pour commencer l’extraction d’information sémantique des images a pour but de récupérer une image, reconnaître des objets dessus : les distinguer et leur affecter un nom. Par exemple pour une photo de rue, reconnaître le ciel, les bâtiments, les gens, les véhicules …

C’est une partie du traitement du signal. Tous ce qui concerne la reconnaissance brute d’objets sans association avec une sémantique est appelé traitement bas-niveau de l’image et l’association des objets avec un nom, une sémantique c’est le traitement haut-niveau de l’image. La première se fait grâce à des algorithmes mathématiques de segmentation de l’image, la deuxième aussi mais utilise souvent une ontologie ou connaissance du domaine auquel s’applique l’image afin de pouvoir y associer une sémantique cohérente.

Pour l’instant j’en suis aux algorithmes de segmentation. Il y en a de 4 sortes :

• segmentation par approches régions,
• segmentation par approche contours,
• segmentation par classification/seuillage
• et les mixs des trois types de méthodes précédentes.

Mon prochain billet Jean-Pierre(Jim), si vous l’acceptez, sera de développer le thème des méthodes de segmentation par approche région.

Fin de vie en tant qu’étudiante

Le 30 mars je commence enfin mon stage de fin d’étude. Je rentre dans une start-up à Paris qui fabrique des GPS pour faire un stage en informatique plutôt technique : j’aimerai pouvoir coder un peu avant de rentrer dans une optique de management de projet.

Cela signifie que dans 3 semaines je commence à gagner ma vie (je ne pourrais donc plus pleurer au téléphone pour réclamer du financement à papa), je commence à être bel et bien adulte avec gestion de la paperasse, les impôts …

Or je regarde autour de moi et que vois-je ? une chambre très très mal rangée, 3 ans que je suis à Nantes et j’ai toujours pas de médecin traitant, ça fait 3 mois que je ne reçoit plus la CAF parce que j’ai pas renvoyé la feuille qu’il fallait, j’ai donné mon préavis de départ pour mon appart avec deux mois de retard (donc je vais payer 2 mois supplémentaires pour rien).

Bref c’est le chaos. D’autant plus que comme toute fin d’année scolaire les deux semaines qui viennent ont leur lot de DS et de soutenances devant professeurs.

Ah oui, et je n’ai toujours pas fini la procédure pour que l’école envoie la convention de stage à ma future boîte.

Bon, tout ça pour dire qu’à côté de ça je n’ai pas beaucoup de temps pour avoir une super vie en dehors du boulot (mis à part un chéri). Alors ce blog si j’ai le temps de l’alimenter ce sera essentiellement du boulot.