1. Quantification
1.1. Seuillage
1.1.1. 2 niveaux : Moyennes
1.1.2. 2 niveaux : écarts types
1.1.3. Otsu : Moyenne + écart type
1.1.4. 3,4, N classes
1.2. K-means
1.2.1. Algorithme
1.2.1.1. Sélection de k objets M servant de centre à k clusters
1.2.1.2. Ré-affecter chaque couleur au cluster de centre M, tel que distance (C,M) minimal
1.2.1.3. Recalculer la nouvelle position des points M comme centres de gravité des éléments du cluster associé
1.2.1.4. Les points ont bougé ?
1.2.1.4.1. Oui : on recommence
1.2.1.4.2. Non : ARRET
1.2.2. Type de fonctionnement
1.2.2.1. On cherche à minimiser la variance des clusters
1.2.3. Bilan
1.2.3.1. Rapide : On ne compare pas toutes les observasions entre elles
1.2.3.2. Permet Détection valeurs extrèmes
1.2.3.3. Pratique sur problèmes de grande taille
1.2.3.4. Nombre de classes prédéfini
1.2.3.5. Importance du choix des germes
1.2.3.6. Ne détecte pas bien les formes convexes
1.2.3.7. Tend à donner trop d'importance aux éléments marginaux
1.2.3.7.1. Solution : modifier les notions de distance et de barycentre
1.2.4. Variante
1.2.4.1. K-Menoïde : les points M doivent faire parti du nuage de point
2. Segmentation spatiale
2.1. WaterShed
2.1.1. Algorithme
2.1.1.1. Entrée : image des gradients Vp
2.1.1.2. On sélectionne les points tq Vp < ε comme étant des germes
2.1.1.3. Si deux germes sont voisins, on leur donne la même étiquette, sinon étiquette différente
2.1.1.4. On attribut aux points tq ε <= Vp <= ε1 l'étiquette ?
2.1.1.5. Pour tous les points d'étiquette ? si un voisin de P sans collision à une étiquette, elle est assigné à P sinon, P reçoit une nouvelle étiquette si collision : frontière
2.1.2. Bilan
2.1.2.1. Nombre de classes variable
2.1.2.2. Rarement appliqué a l'image originale : Pré filtrage
2.1.2.3. SurSegmentation
2.1.3. Structure de donnée
2.1.3.1. Image de gradient
2.1.3.2. Image d'étiquette
2.2. Region Growing
2.2.1. Algorithme
2.2.1.1. Choix d'un germe S
2.2.1.2. Étiqueter S avec Reg (Reg=S)
2.2.1.3. Prendre les pixels voisins de Reg
2.2.1.4. Version parallèle
2.2.1.4.1. Pour tous les voisins Si critère empiler p Dépiler pile d'ajout dans Reg MAJ Reg
2.2.1.5. Version séquentielle
2.2.1.5.1. Pour tous les pixels voisins Si critère ajouter p MAJ Reg
2.2.2. Bilan
2.2.2.1. Bilan global
2.2.2.1.1. Opposé du split and merge
2.2.2.1.2. Régions définies par un point initial et agrandies autour de celui ci
2.2.2.1.3. Importance du choix des premiers points
2.2.2.1.4. On peut déterminer les graines et les critères de voisinage (same())
2.2.2.1.5. Peu efficace avec bruit
2.2.2.1.6. Complexité
2.2.2.2. Version séquentielle
2.2.2.2.1. Modification permanente des propriétés de la région : deux pixels voisins au propriétés identiques peuvent être traités différemment, si l'état de la région à changé entre temps
2.2.3. Critères
2.2.3.1. Variance
2.2.3.1.1. Séquentiel
2.2.3.1.2. Parallèle
2.2.3.2. Différence de couleur entre le germe et le point courant
2.2.3.2.1. Idem pour les deux techniques car on ne prend pas en compte le reste de la région
2.2.3.2.2. Séquentiel
2.2.3.2.3. Parallèle
2.2.3.3. Différence entre la couleur moyenne et la couleur courante
2.2.3.3.1. Séquentiel
2.2.3.3.2. Parallèle
2.2.4. Type de fonctionnement
2.2.4.1. Toutes les variances sont inférieures à un certain seuil (si on utilise un critère de variance)
2.2.5. Structure de donnée
2.2.5.1. Il faut utiliser une file pour stocker le voisinage : sinon on privilégie le dernier point
3. Quantification renforcée par le voisinage
3.1. Relaxation
3.1.1. Évaluation d'une fonction f(v) (avec v vecteur de paramètres)
3.1.2. Renforcement de la valeur les valeurs de f sur le voisinage
3.1.3. Seuillage : donc deux classes uniquement
4. Processus de segmentation
4.1. Image
4.2. Segmentation initiale
4.3. Partition initiale
4.4. Fusion des régions
4.5. Sélection des régions à éclater
4.6. Segmentation qui éclate
4.7. Partition P
4.8. Évaluation des Ri
4.8.1. Satisfassent le critère : ARRET
4.8.2. Sinon : CONTINUER
5. Segmentation probabiliste
5.1. Champs de Markov
5.1.1. Principe
5.1.1.1. Hypothèse 1 : approche globale
5.1.1.1.1. L'objectif général de la segmentation est de retrouver la scène X (l'ensemble des objets) à partir de l'image Y
5.1.1.1.2. Si on teste plusieurs scènes, cela revient à minimiser l'erreur entre l'image Y et la projection des scènes X.
5.1.1.1.3. Pour construire ces scènes, il faut avoir une connaissance a priori des probabilité d'avoir tel ou tel objet. Ces probabilités correspondent, pour chaque pixel, à une distribution.
5.1.1.2. Hypothèse 2 : approche locale
5.1.1.2.1. Dans une image, un objet à plus de chance d'appartenir à une région R si ses proches voisins y appartiennent.
5.1.1.2.2. Cette notion de chance peut être assimilée à une distribution. Si on a 8 voisins, qui ont tous une étiquette différente, alors le tirage est équi-probable. Sinon, il varie en fonction des étiquettes.
5.1.1.2.3. Cette influence dans la distribution locale peut être pondérée, pour chaque voisin, en fonction de sa position dans le voisinage (plus ou moins loin, etc.)
5.1.1.3. Hypothèse 3 : synthèse
5.1.1.3.1. Si on additionne ces deux distributions, on obtiens une distribution qui prend en compte l'allure globale de l'image (celle de l'hypothèse 1), et l'allure du voisinage proche (celle de l'hypothèse 2). Tirer une étiquette dans cette distribution prend en compte tous les paramètres.
5.1.1.3.2. Trouver l'objet réel sous-jacent correspond à maximiser la probabilité du pixel à avoir telle ou telle étiquette.
5.1.1.3.3. Cela revient à minimiser l'erreur entre l'étiquette choisie et l'étiquette réelle. Cette erreur est appelée potentiel.
5.1.1.4. Algorithme
5.1.1.4.1. La distribution de l'hypothèse 1 est connue
5.1.1.4.2. On utilise une pré-segmentation prenant en compte le voisinage (pas de clustering)
5.1.1.4.3. Pour chaque pixel, on utilise cette segmentation pour connaître la tendance du voisinage (Hypothèse 2). Pour éviter de valoriser une direction dans l'image, on peut réaliser un parcours aléatoire.
5.1.1.4.4. Utilisation d'un critère d'arrêt (par exemple potentiel moyen inférieur à un seuil ε)
5.1.1.4.5. Calcul du potentiel pour chaque point
5.1.1.5. Hypothèse 4 : séquence
5.1.1.5.1. Itérer cet algorithme plusieurs fois permet d'affiner la distribution du voisinage, et ainsi minimiser encore plus le potentiel de chaque point.
5.1.2. Bilan
5.1.2.1. Efficace avec bruit : en effet, si le bruit est connu, sa distribution aussi. Elle est donc intégrée dans la distribution 1et peut être utilisée normalement.
5.1.2.2. Calcul avec les voisins
6. Définitions
6.1. Structure de donnée
6.1.1. Ensemble connexe maximal
6.1.1.1. Pour tout p,p' appartenant à R, il existe un chemin de p à p' passant par tous les points de R
6.1.2. Région
6.1.2.1. R Zone homogène de l'image
6.1.3. Partition
6.1.3.1. I = union Ri
6.1.3.2. !i≠j, Ri Inter Rj = 0
6.1.4. Évolution d'une partition
6.1.4.1. Fusion/Merge
6.1.4.2. Division/Éclatement/Split
6.2. Algorithmes
6.2.1. Algorithme supervisé
6.2.1.1. Algorithme dont on fixe le nombre de classe
6.2.2. Types d'algorithmes non supervisés
6.2.2.1. Top/down (split)
6.2.2.2. Bottom/up(merge)
6.2.3. Critères d'arrêt des algorithmes de clustering
6.2.3.1. Maximisation Cohérence intraCluster
6.2.3.1.1. Minimisation Variance
6.2.3.2. Minimisation Cohérence interClusters
6.2.4. Clustering Hierarchique
6.2.4.1. Fusion contrôlée par un prédicat
6.2.4.1.1. F(p1,p2)
6.2.4.2. Division contrôlée par un prédicat
6.2.4.2.1. S(p)
7. Représentation d'une partition en régions 4-connexes
7.1. Géométrie : la frontière
7.1.1. Généralités
7.1.1.1. Chemin interpixel (lignel+pointel)
7.1.1.2. Dimension 2,5 : pointel+déplacement
7.1.2. Définitions
7.1.2.1. Segment : Succession de points interpixels tel que p1 ... pi ... pn avec pi≠nœud et p1,pn nœuds.
7.1.2.2. Frontière : Ensemble de segments et de noeuds
7.1.2.3. Nœud : point interpixel qui est demi voisin d'au moins trois régions
7.2. Topologie : utilisation d'un graphe dessiné (orientation dans l'espace qui induit un ordre sur les arcs du graphe)
7.2.1. Notation
7.2.1.1. Face (Fi)
7.2.1.1.1. Région
7.2.1.2. Arc (d,α(d))
7.2.1.2.1. Segment
7.2.1.3. Sommet (Vi)
7.2.1.3.1. Nœud
7.2.1.4. Le bord de l'image est noté par un nœud infini
7.2.2. Propriétés
7.2.2.1. Orientation de la frontière : par convention lors du parcours, l'intérieur est à droite
7.2.3. Permutations
7.2.3.1. α(d) : involution sans point fixe
7.2.3.1.1. Permet d'atteindre l'autre extrémité de l'arête
7.2.3.2. τ(d)
7.2.3.2.1. Permet d'atteindre l'arête suivante pour un sommet
7.2.3.3. φ = τ(α(d))
7.2.3.3.1. Parcours des bords de la face
7.3. Exemples d'utilisation
7.3.1. Merge : suppression d'une arête sur le graphe
7.3.2. Trouver à quel régions appartient un point P(x,y)
7.3.2.1. Passer en coordonnées 1/2 entières
7.3.2.2. Se déplacer dans n'importe qu'elle direction jusqu'à atteindre un segment
7.3.2.3. Parcours du segment jusqu'à atteindre un nœud
7.3.2.4. On arrive sur le nœud avec une direction
7.3.2.4.1. On peut trouver un brin, donc la région
7.4. Relation Géométrie/Topologie : le brin
7.4.1. Définition
7.4.1.1. <Noeud N, départ>
7.4.1.2. Départ
7.4.1.2.1. Haut
7.4.1.2.2. Droit
7.4.1.2.3. Bas
7.4.1.2.4. Gauche
7.5. Avantages
7.5.1. Reconstruction de la frontière
7.5.2. Arc commun à deux régions
7.5.3. Domaine de la région
7.5.4. Localisation
7.5.5. Split/Merge facile