Camshift

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).

• Portail de l’imagerie numérique