Segmentation (1 ère partie) Références: Sonka et al.: sections 6.3 (6.5) Autres: chap. 14 Forsyth...

Segmentation(1ère partie)

Références:Sonka et al.: sections 6.3 (6.5)

Autres: chap. 14 Forsyth

Dernière révision: Patrick Hébert 2008

Le problème Parmi les pixels de l'image, lesquels

représentent un objet? En général, cela dépend de l'objectif, i.e.

de l'application. Absence de théorie

générale La segmentation est

liée à la reconnaissance

*tirée de Forsyth

Exemples d’applications Trouver des pièces machinées sur un

convoyeur Trouver des personnes dans une image

issue d’une caméra de surveillance Trouver des bâtiments, des végétaux

dans une image satellite Résumer une séquence vidéo (des

groupes d’images consécutives d’une même scène)

Définition Un segment: groupe d’éléments extraits

de l’image qui ont des caractéristiques similaires (cohérentes) ou qui, comme groupe, présente des caractéristiques intéressantes.

Exemple: un groupe de pixels forment une région un groupe de régions forment un objet un groupe de edgels forment une droite

Premier cas Traitons d’abord le cas où tous les

éléments d’un segment sont similaires

Deux façons de former des segments

par division (partition) d'une image en régions uniformes (texture,

couleur, etc …) d'une séquence vidéo en groupes d'images d'un objet suivi dans une séquence vidéo

(mouvement) par regroupement (agglomération) de

pixels selon des propriétés semblables

Deux algorithmes

*tirés de Forsyth

Fixer le nombre de groupes(clusters)

Inspiration de la psychologie/ de l'humain et de son environnement

segmentation figure/fond théorie des Gestalt (groupes)

proximité similarité tendance commune (mouvement) appartenance à une région commune parallélisme fermeture symétrie continuité Configuration familière

Importance du contexte dans cette approche.

exemples

*tirée de Forsyth

Questions sur l’approche Gestalt

Comment intégrer des règles de regroupement dans un algorithme?

Comment générer des hypothèses?

*tirée de Forsyth

Configuration familière

Application de la segmentation:détection de séquences dans une vidéo

une vidéo est un ensemble de séquences une séquence se modélise par une trame

type définition d'une trame de transition: trame

significativement différente de la précédente distances entre des propriétés simples:

différence de trame, (Sursegmentation) différence d'histogrammes, (trop global) différence inter-blocs, différence de la carte des arêtes

Les défis de la segmentation

Quelles sont les propriétés d'un groupe? Comment définir une distance inter-

groupes? Combien y a-t-il de groupes?Formaliser le problème:

une approche: celle des k-moyennes

groupesi

igroupejij

tij cxcxdonnéesgroupes )()(),(

xj : donnée j Ci : centre du groupe i

exemples (groupes ou clusters)

position seulement position + autres caractéristiques

Algorithme des k-moyennes Principe: Supposez que les centres sont connus

et assignez chaque point au groupe dont le centre est le plus près.

Algorithme (suite)

*tirée de Forsyth

Mesures d’affinité Principe

Distance (spatiale) dans l’image Illuminance Couleur Texture (ex: vecteur statistique issu d'un filtre)Difficulté*: comment combiner des

caractéristiques différentes?

)}2/)()((exp{),( 2d

t yxyxyxaff

Complément Approche basée sur les graphes

Voir Sonka section 7.6 Formalisme basé sur les vecteurs propres Normalized cuts

B)pour principe (mêmeA ensemblel' dans

extrémités leursont liens les que sauf idem ),(

et, groupe chaque dans extrémité uneont qui

liensaux associés poids des somme laest ),(

où ),(

),(

),(

),(

VAassoc

BAcut

VBassoc

BAcut

VAassoc

BAcut