Camshift

Le Camshift (Continuously Adaptive Mean Shift) 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 lorsque 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 permettant (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. Cette approche tend à ignorer l'effet des outliers, compensant l'effet des distracteurs 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 $(x_{0},y_{0})$ à la position $(x_{c},y_{c})$ 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 pour trouver les maxima d'une distribution de probabilité, où plus exactement le maxima le plus proche de sa position initiale. Toutefois, 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 d'un modèle de couleur, typiquement un histogramme (modèle non paramétrique) de la couleur que l'on cherche à isoler.

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

• $I=f(x,y)$ image de probabilité de la couleur peau ($P_{skin}$) obtenue par rétroprojection d'un histogramme 32x32x32 dans l'espace colorimétrique HSV (pour l'exemple) construit off-line à partir d'une base d'exemples de pixels de couleur peau.
• Initialisation de la fenêtre W du mean shift: position et taille.
• Tant que W est déplacée de plus d'un certain seuil et que le nombre d'itérations maximal n'est pas atteint:

1. calculer le barycentre des pixels (x, y) inclus dans la fenêtre, ainsi que 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 $(x_{c},y_{c})$.

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 varier la taille de la fenêtre jusqu'à convergence. À 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 précédemment 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 relativement frontale. En d'autres termes, l'aspect ratio ${\frac {h}{w}}=1.2$ est donné à titre d'exemple, mais il peut être modifié pour une autre orientation du visage ou tout autre type d'objets. Les différentes étapes du Camshift sont les suivantes :

• Initialiser W : position et taille.
• Tant que W est déplacée de plus d'un certain seuil et que le nombre maximal d'itérations n'est pas atteint:

1. appliquer le mean shift: retenir $(x_{c},y_{c})$ et le moment d'ordre zéro $M_{00}$
2. centrer W sur $(x_{c},y_{c})$ 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 : 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 :

• Calculer la distribution de probabilité sur une région de recherche plus grande que la fenêtre initiale du mean shift.
• Initialiser la fenêtre W du mean shift.
• Appliquer le mean shift jusqu'à convergence : soit $W_{f}$ la fenêtre obtenue.
• Augmenter la taille de $W_{f}$ de $\pm$ 5 pixels: évaluer l'ellipse à partir des moments du second ordre de la distribution de probabilité située sous $W_{f}$.
• Calculer le rectangle initial du mean shift pour l'image suivante, et l'agrandir de $\pm$ 20 % pour définir la région de recherche.
• Réitérer les étapes précédentes pour l'image suivante.

Estimation des paramètres de l'ellipse à partir des moments du second ordre de la distribution de probabilité $I=P_{skin}$ de couleur peau. Lorsque 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.

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

$\mu _{i,j}=\sum _{x,y}(x-x_{c})^{i}(y-y_{c})^{j}I(x,y)$

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

$\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 :

$I_{max}=\mu _{20}\cos ^{2}\theta +2\mu _{11}\cos \theta \sin \theta +\mu _{02}\sin ^{2}\theta$ $I_{min}=\mu _{20}\sin ^{2}\theta -2\mu _{11}\cos \theta \sin \theta +\mu _{02}\cos ^{2}\theta$

d'où l'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 lorsque l'ellipse fait un angle supérieur à 45° avec l'horizontale, ces longueurs sont permutées, et l'angle $\theta$ est pris égale à $\pi /2-\theta$.

La hauteur et la largeur de la fenêtre initiale 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 sert à 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).