Create your own awesome maps

Even on the go

with our free apps for iPhone, iPad and Android

Get Started

Already have an account?
Log In

Segmentation by Mind Map: Segmentation
0.0 stars - 0 reviews range from 0 to 5

Segmentation

Quantification

F travaille sur l'image

Seuillage

2 niveaux : Moyennes

2 niveaux : écarts types

Otsu : Moyenne + écart type

3,4, N classes

K-means

Algorithme, Sélection de k objets M servant de centre à k clusters, Ré-affecter chaque couleur au cluster de centre M, tel que distance (C,M) minimal, Recalculer la nouvelle position des points M comme centres de gravité des éléments du cluster associé, Les points ont bougé ?, Oui : on recommence, Non : ARRET

Type de fonctionnement, On cherche à minimiser la variance des clusters

Bilan, Rapide : On ne compare pas toutes les observasions entre elles, Permet Détection valeurs extrèmes, Pratique sur problèmes de grande taille, Nombre de classes prédéfini, Importance du choix des germes, Ne détecte pas bien les formes convexes, Tend à donner trop d'importance aux éléments marginaux, Solution : modifier les notions de distance et de barycentre

Variante, K-Menoïde : les points M doivent faire parti du nuage de point

Segmentation spatiale

F travaille sur l'image, le voisinage de P et la position (x,y)

WaterShed

Algorithme, Entrée : image des gradients Vp, On sélectionne les points tq Vp < ε comme étant des germes, Si deux germes sont voisins, on leur donne la même étiquette, sinon étiquette différente, On attribut aux points tq ε <= Vp <= ε1 l'étiquette ?, 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

Bilan, Nombre de classes variable, Rarement appliqué a l'image originale : Pré filtrage, SurSegmentation

Structure de donnée, Image de gradient, Image d'étiquette

Region Growing

Algorithme, Choix d'un germe S, Étiqueter S avec Reg (Reg=S), Prendre les pixels voisins de Reg, Version parallèle, Pour tous les voisins Si critère empiler p Dépiler pile d'ajout dans Reg MAJ Reg, Version séquentielle, Pour tous les pixels voisins Si critère ajouter p MAJ Reg

Bilan, Bilan global, Opposé du split and merge, Régions définies par un point initial et agrandies autour de celui ci, Importance du choix des premiers points, On peut déterminer les graines et les critères de voisinage (same()), Peu efficace avec bruit, Complexité, Version séquentielle, 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

Critères, Variance, Séquentiel, Mauvais sur les image bruités, Parallèle, Différence de couleur entre le germe et le point courant, Idem pour les deux techniques car on ne prend pas en compte le reste de la région, Séquentiel, Parallèle, Différence entre la couleur moyenne et la couleur courante, Séquentiel, Parallèle

Type de fonctionnement, Toutes les variances sont inférieures à un certain seuil (si on utilise un critère de variance)

Structure de donnée, Il faut utiliser une file pour stocker le voisinage : sinon on privilégie le dernier point

Quantification renforcée par le voisinage

F travaille sur l'image et le voisinage de P

Relaxation

Évaluation d'une fonction f(v) (avec v vecteur de paramètres)

Renforcement de la valeur les valeurs de f sur le voisinage

Seuillage : donc deux classes uniquement

Segmentation probabiliste

Champs de Markov

Principe, Hypothèse 1 : approche globale, L'objectif général de la segmentation est de retrouver la scène X (l'ensemble des objets) à partir de l'image Y, Si on teste plusieurs scènes, cela revient à minimiser l'erreur entre l'image Y et la projection des scènes X., 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., Hypothèse 2 : approche locale, Dans une image, un objet à plus de chance d'appartenir à une région R si ses proches voisins y appartiennent., 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., 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.), Hypothèse 3 : synthèse, 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., Trouver l'objet réel sous-jacent correspond à maximiser la probabilité du pixel à avoir telle ou telle étiquette., Cela revient à minimiser l'erreur entre l'étiquette choisie et l'étiquette réelle. Cette erreur est appelée potentiel., Algorithme, La distribution de l'hypothèse 1 est connue, On utilise une pré-segmentation prenant en compte le voisinage (pas de clustering), 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., Utilisation d'un critère d'arrêt (par exemple potentiel moyen inférieur à un seuil ε), Calcul du potentiel pour chaque point, Hypothèse 4 : séquence, Itérer cet algorithme plusieurs fois permet d'affiner la distribution du voisinage, et ainsi minimiser encore plus le potentiel de chaque point.

Bilan, 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., Calcul avec les voisins

Définitions

Structure de donnée

Ensemble connexe maximal, Pour tout p,p' appartenant à R, il existe un chemin de p à p' passant par tous les points de R

Région, R Zone homogène de l'image

Partition, I = union Ri, !i≠j, Ri Inter Rj = 0

Évolution d'une partition, Fusion/Merge, Division/Éclatement/Split

Algorithmes

Algorithme supervisé, Algorithme dont on fixe le nombre de classe

Types d'algorithmes non supervisés, Top/down (split), Bottom/up(merge)

Critères d'arrêt des algorithmes de clustering, Maximisation Cohérence intraCluster, Minimisation Variance, Minimisation Cohérence interClusters

Clustering Hierarchique, Fusion contrôlée par un prédicat, F(p1,p2), On arrête la fusion, On fusionne, Division contrôlée par un prédicat, S(p), On divise, On arrête la division

Processus de segmentation

Image

Segmentation initiale

Partition initiale

Fusion des régions

Sélection des régions à éclater

Segmentation qui éclate

Partition P

Évaluation des Ri

Satisfassent le critère : ARRET

Sinon : CONTINUER

Représentation d'une partition en régions 4-connexes

Géométrie : la frontière

Généralités, Chemin interpixel (lignel+pointel), Dimension 2,5 : pointel+déplacement

Définitions, Segment : Succession de points interpixels tel que p1 ... pi ... pn avec pi≠nœud et p1,pn nœuds., Frontière : Ensemble de segments et de noeuds, Nœud : point interpixel qui est demi voisin d'au moins trois régions

Topologie : utilisation d'un graphe dessiné (orientation dans l'espace qui induit un ordre sur les arcs du graphe)

Notation, Face (Fi), Région, Arc (d,α(d)), Segment, Sommet (Vi), Nœud, Le bord de l'image est noté par un nœud infini

Propriétés, Orientation de la frontière : par convention lors du parcours, l'intérieur est à droite

Permutations, α(d) : involution sans point fixe, Permet d'atteindre l'autre extrémité de l'arête, τ(d), Permet d'atteindre l'arête suivante pour un sommet, φ = τ(α(d)), Parcours des bords de la face

Exemples d'utilisation

Merge : suppression d'une arête sur le graphe

Trouver à quel régions appartient un point P(x,y), Passer en coordonnées 1/2 entières, Se déplacer dans n'importe qu'elle direction jusqu'à atteindre un segment, Parcours du segment jusqu'à atteindre un nœud, On arrive sur le nœud avec une direction, On peut trouver un brin, donc la région

Relation Géométrie/Topologie : le brin

Définition, <Noeud N, départ>, Départ, Haut, Droit, Bas, Gauche

Avantages

Reconstruction de la frontière

Arc commun à deux régions

Domaine de la région

Localisation

Split/Merge facile