Méthode de Viola et Jones - Définition
La liste des auteurs de cet article est disponible ici.
Introduction
La Méthode de Viola et Jones est une méthode de détection d'objet (en) dans une image numérique, proposée par Paul Viola and Michael Jones en 2001. C'est l'une des premières méthodes qui permet de détecter efficacement des objets dans une image en temps réel.
C'est une méthode d'apprentissage supervisé qui nécéssite en général un grand nombre d'exemples (de quelques centaines à plusieurs milliers) pour réaliser l'apprentissage d'un classifieur. Elle a introduit plusieurs notions qui ont été ensuite reprises par de nombreux chercheurs en vision par ordinateur: la notion d'image intégrale (en), ainsi qu'une méthode de classification construite comme une cascade de classifieurs boostés. La méthode a été proposée à l'origine pour détecter des visages, mais peut être utilisée pour détecter d'autres type d'objet.
Historique
La méthode a été publiée pour la première fois le 13 juillet 2001 à la conférence IJCV. Une version moins détaillée est également publiée par les auteurs à CVPR en décembre 2001.
la méthode s'inspire des travaux de Papageorgiou et al. pour ce qui est des caractéristique (vision par ordinateur) (en), en reprenant leur idée de caractéristiques proches des ondelettes de Haar. La méthode s'inspire également de précédents travaux de Paul Viola avec Kinh Tieu dans un autre domaine, la recherche d'image par le contenu, en reprenant l'idée de sélection de caractéristiques par AdaBoost.
La méthode devient rapidement une méthode standard en détection de visage (en) et est reconnue comme l'une des plus efficace. Les travaux de Viola et Jones deviennent également parmi les plus utilisés et cités en vision artificielle.
Description de la méthode
La méthode de Viola et Jones est une approche basée apparence, qui consiste à scanner l'ensemble de l'image en calculant un certain nombre de caractéristiques dans des zones rectangulaires qui se chevauchent. Sa particularité repose sur le fait que les caractéristiques utilisées sont très simples mais très nombreuses. Une première contribution de la méthode est l'introduction des images intégrales, qui permettent un calcul rapide de ces caractéristiques. La deuxième contribution importante est de proposer une sélection de ces caractéristiques par boosting, en interprétant les caractéristiques comme des classifieurs. Enfin, la méthode propose une architecture pour combiner les classifieurs boostés en une cascade, qui permet un net gain en temps de détection.
C'est une méthode d'apprentissage supervisé, qui est donc divisée en deux étapes: l'apprentissage du classifieur à partir d'un grand nombre d'exemples positifs (les objets d'intérêts, i.e. des visages) et négatifs, et l'application de ce classifieur lors d'une phase de détection.
Caractéristiques
Définition
Viola et Jones proposent d'utiliser un certain nombre de caractéristiques, plutôt que de travailler directement sur les valeurs de pixels, ce qui est à la fois plus efficace et plus rapide. Ce sont des caractéristiques quasi-Haar (en), qui sont des différences de sommes de pixels calculées dans des zones rectangulaires. La figure montre les quatre types caractéristiques proposées par Viola et Jones, dans lesquelles la somme de pixels en gris est soustraite de la somme des pixels blancs. Leur nom vient de la similarité avec les ondelettes de Haar proposées comme caractéristiques par Papageorgiou et al., et dont s'inspirent Viola et Jones.
Pour calculer efficacement ces caractéristiques sur une image, les auteurs proposent également une méthode rapide, qu'il 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 en dessus et à gauche de ce point. Plus formellement, l'image intégrale ii est définie à partir de l'image i par:
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 temps constant quelle que soit la taille de la caractéristique.
Calcul
Les caractéristiques sont calculées à toutes les positions et toutes les échelles dans une fenêtre de détection de petite taille, des tailles de 24x24 ou de 20x15 sont typiques. Ceci génère un très grand nombre de caractéristiques par fenêtre, Viola et Jones donnent l'exemple pour une fenêtre de taille 24x24, qui génère 45396 caractéristiques.
Lors de la détection, l'ensemble de l'image est scannée en faisant varier la position de cette fenêtre de détection, avec un certain pas horizontal et vertical (un pas de 1 pixel est utilisé dans la méthode originale). La taille de la fenêtre est également augmentée successivement, Viola et Jones utilisent un pas de 1,25 jusqu'à ce que la fenêtre prenne la totalité de l'image.
Sélection de caractéristiques par boosting
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 légèrement meilleurs que le hasard. Viola et Jones adaptent ce principe en identifiant une caractéristique à un classifieur faible, en construisant un classifieur faible qui n'utilise qu'une seule caractéristique. Le classifieur se réduit alors à un couple (caractéristique, seuil).
L'algorithme de boosting utilisé en pratique est une version modifiée d'AdaBoost, qui est utilisée à la fois pour réaliser la sélection et l'apprentissage d'un classifieur « fort ». Les classifieurs faibles utilisés sont souvent des arbres de décision. Un cas fréquent est lorsque l'arbre est de profondeur 1, qui réduit l'opération de classification à un simple seuillage.
Plus précisément, l'algorithme est de type itératif, avec un nombre d'itération donné. A chaque itération, l'algorithme sélectionne une caractéristique, utilisée pour construire le classifieur fort final. Cette sélection se fait en apprenant 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 maintient également une distribution de probabilité sur l'ensemble d'apprentissage, qui est ré-évaluée à chaque itération en fonction des résultats de classification. En particulier, plus de poids est donnée aux exemples difficiles à classer. Le classifieur « fort » final construit par AdaBoost est la somme pondéré des classifieurs sélectionnés.
