Méthode de Viola et Jones

Un exemple des types de caractéristiques utilisées par Viola et Jones.

Plutôt que de travailler directement sur les valeurs de pixels, et pour être à la fois plus efficace et plus rapide, Viola et Jones proposent d'utiliser des caractéristiques, c'est-à-dire une représentation synthétique et informative, calculée à partir des valeurs des pixels. Viola et Jones définissent des caractéristiques très simples, les caractéristiques pseudo-Haar[2], qui sont calculées par la différence des sommes de pixels de deux ou plusieurs zones rectangulaires adjacentes. La figure ci-contre donne des exemples des caractéristiques proposées par Viola et Jones à 2, 3 ou 4 rectangles, dans lesquelles la somme de pixels sombres est soustraite de la somme des pixels blancs. Leur nom vient de leur similitude avec les ondelettes de Haar, précédemment proposées comme caractéristiques par Papageorgiou[5] et dont se sont inspirés Viola et Jones[2].

Pour calculer rapidement et efficacement ces caractéristiques sur une image, les auteurs proposent également une nouvelle méthode, qu'ils appellent « image intégrale ». C'est une représentation sous la forme d'une image, de même taille que l'image d'origine, qui en chacun de ses points contient la somme des pixels situés au-dessus de lui et à sa gauche. Plus formellement, l'image intégrale ${\displaystyle ii}$ au point ${\displaystyle (x,y)}$ est définie à partir de l'image ${\displaystyle i}$ par[2] :

${\displaystyle ii(x,y)=\sum _{x'\leq x,\ y'\leq y}i(x',y')}$

Grâce à cette représentation, une caractéristique formée de deux zones rectangulaires peut être calculée en seulement 6 accès à l'image intégrale, et donc en un temps constant quelle que soit la taille de la caractéristique[2].

Les caractéristiques sont calculées à toutes les positions et à toutes les échelles dans une fenêtre de détection de petite taille, typiquement de 24 × 24 pixels[2] ou de 20 × 15 pixels[13]. Un très grand nombre de caractéristiques par fenêtre est ainsi généré, Viola et Jones donnant l'exemple d'une fenêtre de taille 24 × 24 qui génère environ 160 000 caractéristiques.

En phase de détection, l'ensemble de l'image est parcourue en déplaçant la fenêtre de détection d'un certain pas dans le sens horizontal et vertical (ce pas valant 1 pixel dans l'algorithme original[2]). Les changements d'échelles se font en modifiant successivement la taille de la fenêtre de détection[note 1]. Viola et Jones utilisent un facteur multiplicatif de 1,25, jusqu'à ce que la fenêtre couvre la totalité de l'image.

Finalement, et afin d'être plus robuste aux variations d'illumination, les fenêtres sont normalisées par la variance[2].

La conséquence de ces choix techniques, notamment le recours aux images intégrales, est un gain notable en efficacité, les caractéristiques étant évaluées très rapidement quelle que soit la taille de la fenêtre.

Le deuxième élément clé de la méthode de Viola et Jones est l'utilisation d'une méthode de boosting afin de sélectionner les meilleures caractéristiques. Le boosting est un principe qui consiste à construire un classifieur « fort » à partir d'une combinaison pondérée de classifieurs « faibles », c'est-à-dire donnant en moyenne une réponse meilleure qu'un tirage aléatoire. Viola et Jones adaptent ce principe en assimilant une caractéristique à un classifieur faible, en construisant un classifieur faible qui n'utilise qu'une seule caractéristique. L'apprentissage du classifieur faible consiste alors à trouver la valeur seuil de la caractéristique qui permet de mieux séparer les exemples positifs des exemples négatifs. Le classifieur se réduit alors à un couple (caractéristique, seuil).

L'algorithme de boosting utilisé est en pratique une version modifiée d'AdaBoost, qui est utilisée à la fois pour la sélection et pour l'apprentissage d'un classifieur « fort ». Les classifieurs faibles utilisés sont souvent des arbres de décision. Un cas remarquable, fréquemment rencontré, est celui de l'arbre de profondeur 1, qui réduit l'opération de classification à un simple seuillage.

L'algorithme est de type itératif, à nombre d'itérations déterminé. À chaque itération, l'algorithme sélectionne une caractéristique, qui sera ajoutée à la liste des caractéristiques sélectionnées aux itérations précédentes, et le tout va contribuer à la construction du classifieur fort final. Cette sélection se fait en entraînant un classifieur faible pour toutes les caractéristiques et en sélectionnant celui avec l'erreur la plus faible sur l'ensemble d'apprentissage. L'algorithme tient également à jour une distribution de probabilité sur l'ensemble d'apprentissage, réévaluée à chaque itération en fonction des résultats de classification. En particulier, plus de poids est attribué aux exemples difficiles à classer, c'est-à-dire ceux dont l'erreur est élevée. Le classifieur « fort » final construit par AdaBoost est composé de la somme pondérée des classifieurs sélectionnés.

Plus formellement, on considère un ensemble de ${\displaystyle n}$ images ${\displaystyle (x_{1},\ldots ,x_{n})}$ et leurs étiquettes associées ${\displaystyle (y_{1},\ldots ,y_{n})}$, qui sont telles que ${\displaystyle y_{i}=0}$ si l'image ${\displaystyle x_{i}}$ est un exemple négatif et ${\displaystyle y_{i}=1}$ si ${\displaystyle x_{i}}$ est un exemple de l'objet à détecter. L'algorithme de boosting est constitué d'un nombre ${\displaystyle T}$ d'itérations, et pour chaque itération ${\displaystyle t}$ et chaque caractéristique ${\displaystyle j}$, on construit un classifieur faible ${\displaystyle h_{j}}$. Idéalement, le but est d'obtenir un classifieur ${\displaystyle h}$ qui prédise exactement les étiquettes pour chaque échantillon, c'est-à-dire ${\displaystyle y_{i}=h(x_{i})}$ ${\displaystyle \forall i\in \{1\ldots n\}}$. En pratique, le classifieur n'est pas parfait et l'erreur engendrée par ce classifieur est donnée par :

${\displaystyle \epsilon _{j}=\sum _{i=1}^{n}w_{i}\left|h_{j}(x_{i})-y_{i}\right|}$,

les ${\displaystyle w_{i}}$ étant les poids associés à chaque exemple et mis à jour à chaque itération en fonction de l'erreur obtenue à l'itération précédente. On sélectionne alors à l'itération ${\displaystyle t}$ le classifieur ${\displaystyle h_{t}}$ présentant l'erreur la plus faible : ${\displaystyle \epsilon _{t}=\min _{j}(\epsilon _{j})}$.

Le classifieur fort final ${\displaystyle h(x)}$ est construit par seuillage de la somme pondérée des classifieurs faibles sélectionnés :

${\displaystyle h(x)={\begin{cases}1&\displaystyle {\text{si }}\sum _{t=1}^{T}\alpha _{t}h_{t}(x)\geq {\frac {1}{2}}\sum _{t=1}^{T}\alpha _{t}\\0&{\text{sinon}}\end{cases}}}$

Les ${\displaystyle \alpha _{t}}$ sont des coefficients calculés à partir de l'erreur ${\displaystyle \epsilon _{t}}$.

Illustration de l'architecture de la cascade : les fenêtres sont traitées séquentiellement par les classifieurs, et rejetées immédiatement si la réponse est négative (F).

La méthode de Viola et Jones est basée sur une approche par recherche exhaustive sur l'ensemble de l'image, qui teste la présence de l'objet dans une fenêtre à toutes les positions et à plusieurs échelles. Cette approche est cependant extrêmement coûteuse en calcul. L'une des idées-clés de la méthode pour réduire ce coût réside dans l'organisation de l'algorithme de détection en une cascade de classifieurs. Appliqués séquentiellement, ces classifieurs prennent une décision d'acceptation — la fenêtre contient l'objet et l'exemple est alors passé au classifieur suivant —, ou de rejet — la fenêtre ne contient pas l'objet et dans ce cas l'exemple est définitivement écarté —. L'idée est que l'immense majorité des fenêtres testées étant négatives (c.-à-d. ne contiennent pas l'objet), il est avantageux de pouvoir les rejeter avec le moins possible de calculs. Ici, les classifieurs les plus simples, donc les plus rapides, sont situés au début de la cascade, et rejettent très rapidement la grande majorité des exemples négatifs[2]. Cette structure en cascade peut également s'interpréter comme un arbre de décision dégénéré, puisque chaque nœud ne comporte qu'une seule branche[2].

En pratique, la cascade est constituée d'une succession d'étages[note 2], chacune étant formée d'un classifieur fort appris par AdaBoost. L'apprentissage du classifieur de l'étage ${\displaystyle n}$ est réalisé avec les exemples qui ont passé l'étage ${\displaystyle n-1}$ ; ce classifieur doit donc faire face à un problème plus difficile : plus on monte dans les étages, plus les classifieurs sont complexes[2].

Le choix du nombre ${\displaystyle K}$ d'étages est fixé par l'utilisateur ; dans leur méthode originale, Viola et Jones utilisent ${\displaystyle K=38}$ étages. L'utilisateur doit également spécifier le taux de détection minimal ${\displaystyle d_{i}}$ et le taux de fausse alarme maximal ${\displaystyle f_{i}}$ à atteindre pour l'étage ${\displaystyle i}$. Le taux de détection de la cascade est alors donné par :

${\displaystyle D=\prod _{i=1}^{K}d_{i}}$

et le taux de fausse alarme par :

${\displaystyle F=\prod _{i=1}^{K}f_{i}}$

En pratique, les taux ${\displaystyle d_{i}}$ et ${\displaystyle f_{i}}$ sont les mêmes pour tous les étages. Indirectement, ces taux déterminent également le nombre de caractéristiques utilisées par les classifieurs forts à chaque étage : les itérations d'Adaboost continuent jusqu'à ce que le taux de fausse alarme cible soit atteint. Des caractéristiques/classifieurs faibles sont ajoutés jusqu'à ce que les taux cibles soient atteints, avant de passer ensuite à l'étage suivant.

Pour atteindre des taux de détection et de fausse alarme corrects en fin de cascade, il est nécessaire que les classifieurs forts de chaque étage aient un bon taux de détection ; ils peuvent par contre avoir un taux de fausses alarmes élevé. Si l'on prend l'exemple d'une cascade de 32 étages, pour obtenir une performance finale ${\displaystyle D=0.9}$ et ${\displaystyle F=10^{-6}}$, chaque classifieur fort doit atteindre ${\displaystyle d_{i}=0,997}$, mais peut se permettre ${\displaystyle f_{i}=0,65}$ (i.e. ${\displaystyle 0,65^{32}=10^{-6}}$ et ${\displaystyle 0,997^{32}=0,9}$). Chaque étage ajouté diminue donc le nombre de fausses alarmes, mais aussi le taux de détection.

Plusieurs chercheurs font remarquer que cette idée de filtrer rapidement les exemples négatifs les plus simples n'est pas nouvelle[14] - [15]. Elle existe dans d'autres méthodes sous forme d'heuristiques, comme la détection de la couleur chair[16] - [17] ou une étape de pré-classification[17].

L'apprentissage est réalisé sur un très large ensemble d'images positives (c'est-à-dire contenant l'objet) et négatives (ne contenant pas l'objet). Plusieurs milliers d'exemples sont en général nécessaires. Cet apprentissage comprend :

• Le calcul des caractéristiques pseudo-Haar sur les exemples positifs et négatifs ;
• L'entraînement de la cascade : à chaque étage de la cascade, un classifieur fort est entraîné par AdaBoost. Il est construit par ajouts successifs de classifieurs faibles entraînés sur une seule caractéristique, jusqu'à l'obtention de performances conformes aux taux de détection et de fausse alarme souhaités pour l'étage.

La détection s'applique sur une image de test, dans laquelle on souhaite déceler la présence et la localisation d'un objet. En voici les étapes :

• parcours de l'ensemble de l'image à toutes les positions et échelles, avec une fenêtre de taille 24 × 24 pixels, et application de la cascade à chaque sous-fenêtre, en commençant par le premier étage :
  • calcul des caractéristiques pseudo-Haar utilisées par le classifieur de l'étage courant,
  • puis calcul de la réponse du classifieur,
  • passage ensuite à l'étage supérieur si la réponse est positive, à la sous-fenêtre suivante sinon,
  • et enfin l'exemple est déclaré positif si tous les étages répondent positivement ;
• fusion des détections multiples : l'objet peut en effet générer plusieurs détections, à différentes positions et échelles ; cette dernière étape fusionne les détections qui se chevauchent pour ne retourner qu'un seul résultat.

(en) Richard Szeliski, Computer Vision: Algorithms and Applications, Springer, 2010

• Détection de visage
• Détection d'objet

• Une démonstration de détection de visage avec la méthode de Viola et Jones