Camshift

Le Camshift est un algorithme de segmentation d'images couleur introduit par Gary Bradski en 1998, le Camshift exploite habilement l'algorithme du mean-shift en modifiant la taille de la fenêtre quand ce dernier est arrivé à convergence.



Catégories :

Vision artificielle

Page(s) en rapport avec ce sujet :

  • ... ICamshift appliqué à une image fixe : après convergence du mean shift, on agrandit la fenêtre située et on estime l'ellipse englobant la... (source : commons.wikimedia)
  • Mean Shift (CAMSHIFT)». La tolérance de la méthode aux bruits, ces contraintes...... La visualisation est faite par le biais d'une fenêtre représentant de ... (source : liris.cnrs)
  • fenêtre d'initialisation est désignée de manière aléatoire... Shift, trois paramètres principaux affectent l'erreur de suivi.... CamShift 3D. CamShift 2D. CamShift 1D min max mean p min max mean p min max mean p. 0.06 117 28... (source : documents.irevues.inist)

Le Camshift (Continuously Adaptive Mean Shift) est un algorithme de segmentation d'images couleur introduit par Gary Bradski en 1998[1], le Camshift exploite habilement l'algorithme du mean-shift en modifiant la taille de la fenêtre quand ce dernier est arrivé à convergence. Le Camshift couplé en est une adaptation aux séquences d'images couleur, et est exploité en poursuite d'objet en temps réel. Une implémentation gratuite de cet algorithme se trouve dans la bibliothèque logicielle de vision par ordinateur OpenCV.

Mean-Shift pour la détection de mode dans une densité 2D

Le mean-shift est une approche non-paramétrique donnant la possibilité (entre autres) de détecter les modes d'une distribution de probabilité par une procédure récursive convergeant vers le point de stationnarité le plus proche[2]. Cette approche tend à ignorer l'effet des outliers, compensant l'effet des distracteurs[3] et des bruits de l'image.

Les modes à trouver sont les maxima locaux de la distribution spatiale f (x, y) = p (peau | x, y) de la probabilité de teinte chair dans l'image. L'approche du Mean-Shift est une procédure itérative consistant à déplacer sur la distribution f une fenêtre W, de taille fixe, de sa position (x0, y0) à la position (xc, yc) moyenne des points de f inclus dans W pondérés par leur valeur de probabilité.

Détection de mode dans une densité 2D par l'algorithme du mean shift

Le mean shift est un algorithme robuste [4] pour trouver les maxima d'une distribution de probabilité, où plus précisément le maxima le plus proche de sa position d'origine. Cependant, il nécessite de connaître la taille de l'objet recherché, qui est définie par l'utilisateur à l'initialisation du mean shift. La carte de probabilité est obtenue après une opération de rétroprojection [5] d'un modèle de couleur, typiquement un histogramme (modèle non paramétrique) de la couleur qu'on cherche à isoler.

Les étapes de la détection d'un mode peuvent se résumer ainsi :

  1. calculer le barycentre des pixels (x, y) inclus dans la fenêtre, mais aussi leur somme (moment d'ordre zéro)  :M_{00} = \sum_{x,y} I(x,y) \quad M_{10}=\sum_{x,y}xI(x,y) \quad M_{01}=\sum_{x,y}yI(x,y) \quad \Rightarrow x_c = \frac{M_{10}}{M_{00}}, \quad y_c =\frac{M_{01}}{M_{00}}
  2. centrer W sur le barycentre (xc, yc) .



Camshift : cas des images fixes

L'algorithme du Camshift :Continuously Adaptive Mean Shift

L'algorithme du CamShift, Continuously Adaptive Mean Shift, encapsule celui du Mean-Shift dans une boucle faisant fluctuer la taille de la fenêtre jusqu'à convergence. A chaque itération, le mean shift est appliqué avec une fenêtre de taille donnée. Après convergence du mean shift, la procédure est ré-itérée avec une nouvelle fenêtre, centrée sur la position trouvée par le mean shift, mais de taille fonction du moment d'ordre zéro de la distribution spatiale de la probabilité de teinte chair auparavant calculée par le mean shift.

Le Camshift s'applique à la segmentation d'images fixes : après convergence du mean shift, la hauteur de la fenêtre est choisie 20% plus grande que sa largeur, mais ce choix est arbitraire. Il est adapté au cas de la segmentation d'un visage en pose assez frontale. En d'autres termes, l'aspect ratio \frac{h}{w}=1 est donné à titre d'exemple, mais il peut être modifier pour une autre orientation du visage ou tout autre type d'objets. Les différentes étapes du Camshift sont les suivantes :

  1. appliquer le mean shift : retenir (xc, yc) et le moment d'ordre zéro M00
  2. centrer W sur (xc, yc) et lui affecter la largeur w=2\sqrt{\frac{M_{00}}{256}} et la hauteur h = 1.2w

Camshift couplé : cas des séquences d'images

Le Camshift couplé adapte le Camshift au suivi d'objet[6] : le mean shift est appliqué à l'image, avec une taille de fenêtre fixe et jusqu'à convergence, puis la taille de W est modifiée pour l'image suivante. Les nouvelles dimensions de W sont définies à partir de l'ellipse déduite des moments centraux du second ordre de la distribution spatiale de la teinte chair, calculés sur la fenêtre produite par le mean shift augmentée de \pm 5 pixels verticalement et horizontalement. Les différentes étapes du Camshift couplé sont ainsi les suivantes :

Estimation des paramètres de l'ellipse à partir des moments du second ordre de la distribution de probabilité I = Pskin de couleur peau. Quand le mean shift arrive a convergence, le Camshift agrandit la fenêtre W et calcule l'ellipse de confiance à 99% des points qu'elle contient. On suppose en effet que ces points ont une distribution 2D Gaussienne, ce qui permet d'estimer les paramètres de cette ellipse à partir des moments du second ordre de la région d'intérêt W[7].

Le moment central d'ordre i pour et j pour y est définie par :

μi, j = (xxc) i (yyc) jI (x, y)
x, y

la sommation ayant lieu sur la fenêtre agrandie. L'orientation de l'ellipse est donnée par θ :

\theta = arctan2( \,2\mu_{11}, \, \mu_{20}-\mu_{02} + \sqrt{4\mu_{11}ˆ2+(\mu_{20}-\mu_{02})ˆ2} \,)

où la fonction arctan2 est la tangente inverse à quatre quadrants. On évalue alors les moments d'inertie principaux de l'ellipse, définis par :

I_{max}=\sum_{x,y}\big( (x-x_c)I(x,y)\cos\theta + (y-y_c)I(x,y)\sin\theta\big)ˆ2
I_{min}=\sum_{x,y}\big( (x-x_c)I(x,y)\sin\theta - (y-y_c)I(x,y)\cos\theta\big)ˆ2

soit :

Imax = μ20cos2θ + 2μ11cosθsinθ + μ02sin2θ
Imin = μ20sin2θ − 2μ11cosθsinθ + μ02cos2θ

d'où on déduit les dimensions du grand axe a et du petit axe b de l'ellipse :

a=4\sqrt{\frac{I_{max}}{M_{00}}}\quad \quad b=4\sqrt{\frac{I_{min}}{M_{00}}}

Si a < b, ce qui a lieu quand l'ellipse fait un angle supérieur à 45° avec l'horizontale, ces longueurs sont permutées, et l'angle θ est pris égale à π / 2 − θ.

La hauteur et la largeur de la fenêtre d'origine du mean shift pour la prochaine image sont alors déduites par projection des sommets de l'ellipse sur les axes x et y :

w=\max(\,a\cos\theta, \,b\sin\theta\,) \quad \quad h=\max(\,a\sin\theta, \,b\cos\theta\,)

Cette fenêtre permet de initialiser la recherche du maximum de la probabilité de la couleur peau, mais le Camshift couplé précise aussi que cette probabilité doit être calculée sur un voisinage plus étendu de cette fenêtre : p (peau | x, y) est calculée sur la fenêtre agrandie de \pm 20% (par exemple).


Notes et références

  1. Computer Vision Face Tracking For Use in a Perceptual User Interface, Intel Technology Journal, No. Q2. (1998)
  2. Y. Cheng, Mean Shift, Mode Seeking, and Clustering, IEEE Transaction on Pattern Analysis and Machine Intelligence (TPAMI), Vol. 17, pp. 790-799, 1995.
  3. D. Comaniciu, V. Ramesh, P. Meer : Kernel-based object tracking. IEEE Transaction on Pattern Analysis and Machine Intelligence (TPAMI), vol. 25, pp. 564-577, 2003.
  4. D. Comaniciu, P. Meer : Mean shift : A robust approach toward feature space analysis. IEEE Transaction on Pattern Analysis and Machine Intelligence (TPAMI), vol. 24, pp. 603-619, 2002.
  5. MJ Swain, DH Ballard : Color Indexing, International Journal of Computer Vision, 1991
  6. Traitement de l'image et de la vidéo Editions : Ellipses - Technosup (2010)
  7. Gary Bradski and Adrian Kæhler : Learning OpenCV : Computer Vision with the OpenCV Library, O'Reilly Media, 555 pages, 2008

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Camshift.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu