Camshift

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[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 ${\displaystyle 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 ${\displaystyle f}$ une fenêtre W, de taille fixe, de sa position ${\displaystyle (x_{0},y_{0})}$ à la position ${\displaystyle (x_{c},y_{c})}$ moyenne des points de ${\displaystyle 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 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[5] 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 :

• ${\displaystyle I=f(x,y)}$ image de probabilité de la couleur peau (${\displaystyle 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):${\displaystyle 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 ${\displaystyle (x_{c},y_{c})}$.

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 ${\displaystyle {\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 ${\displaystyle (x_{c},y_{c})}$ et le moment d'ordre zéro ${\displaystyle M_{00}}$
2. centrer W sur ${\displaystyle (x_{c},y_{c})}$ et lui affecter la largeur ${\displaystyle w=2{\sqrt {\frac {M_{00}}{256}}}}$ et la hauteur ${\displaystyle h=1.2w}$

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 ${\displaystyle \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 ${\displaystyle W_{f}}$ la fenêtre obtenue.
• Augmenter la taille de ${\displaystyle W_{f}}$ de ${\displaystyle \pm }$ 5 pixels: évaluer l'ellipse à partir des moments du second ordre de la distribution de probabilité située sous ${\displaystyle W_{f}}$.
• Calculer le rectangle initial du mean shift pour l'image suivante, et l'agrandir de ${\displaystyle \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é ${\displaystyle 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[7].

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

${\displaystyle \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 ${\displaystyle \theta }$:

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

${\displaystyle I_{max}=\sum _{x,y}{\big (}(x-x_{c})I(x,y)\cos \theta +(y-y_{c})I(x,y)\sin \theta {\big )}^{2}}$

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

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

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

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

Si ${\displaystyle 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 ${\displaystyle \theta }$ est pris égale à ${\displaystyle \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 :

${\displaystyle 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 : ${\displaystyle p(peau|x,y)}$ est calculée sur la fenêtre agrandie de ${\displaystyle \pm }$ 20 % (par exemple).