thumb|alt=Un exemple de détection de visage par la méthode de Viola et Jones, les 7 visages présents sur l'image sont correctement détectés, sans fausses alarmes.|Un exemple de détection de visage par la méthode de Viola et Jones.

La méthode de Viola et Jones est une méthode de détection d'objet dans une image numérique, proposée par les chercheurs Paul Viola et Michael Jones en 2001. Elle fait partie des toutes premières méthodes capables de détecter efficacement et en temps réel des objets dans une image. Inventée à l'origine pour détecter des visages, elle peut également être utilisée pour détecter d'autres types d'objets comme des voitures ou des avions. La méthode de Viola et Jones a été l'une des méthodes les plus connues et les plus utilisées, en particulier pour la détection de visages et la détection de personnes.

En tant que procédé d'apprentissage supervisé, la méthode de Viola et Jones nécessite de quelques centaines à plusieurs milliers d'exemples de l'objet que l'on souhaite détecter, pour entraîner un classifieur. Une fois son apprentissage réalisé, ce classifieur est utilisé pour détecter la présence éventuelle de l'objet dans une image en parcourant celle-ci de manière exhaustive, à toutes les positions et dans toutes les tailles possibles.

Considérée comme étant l'une des plus importantes méthodes de détection d'objet, la méthode de Viola et Jones est notamment connue pour avoir introduit plusieurs notions reprises ensuite par de nombreux chercheurs en vision par ordinateur, à l'exemple de la notion d'image intégrale ou de la méthode de classification construite comme une cascade de classifieurs boostés.

Cette méthode bénéficie d'une implémentation sous licence BSD dans OpenCV, une bibliothèque très utilisée en vision par ordinateur.

Historique

Paul Viola et Michael Jones, alors employés au de la société américaine Compaq ., publient la méthode qui porte leur nom pour la première fois le dans le journal scientifique (IJCV).. Les deux auteurs publient ensuite deux autres articles sur la méthode : une version moins détaillée, présentée à la (CVPR) en . et une version révisée en 2004, toujours dans IJCV..

Les caractéristiques extraites par cette méthode sont inspirées des travaux de Papageorgiou, Oren et Poggio, datant de 1998., qui utilisent des caractéristiques construites à partir d'ondelettes de Haar. La méthode s'inspire également de précédents travaux de Paul Viola et Kinh Tieu dans un autre domaine, celui de la recherche d'image par le contenu, en reprenant l'idée de sélection de caractéristiques par AdaBoost.. Parmi les nombreuses méthodes de détection de visages publiées à l'époque., Viola et Jones considèrent en particulier celle de Rowley-Kanade : en raison de ses excellents résultats et de sa rapidité, ils la prennent comme référence pour les comparaisons. À performances équivalentes, Viola et Jones notent que la détection par leur méthode est 15 fois plus rapide que le détecteur de Rowley-Kanade.

La méthode, considérée comme l'une des plus efficaces en détection de visage, devient rapidement un standard dans ce domaine.. Les travaux de Viola et Jones sont parmi les plus utilisés et les plus cités par les chercheurs, et de nombreuses améliorations sont ainsi proposées.. Leurs travaux sont également étendus à d'autres types d'objets que les visages et la méthode devient ainsi un standard en détection d'objet. La méthode est par ailleurs reconnue comme étant celle ayant eu le plus d'impact dans le domaine de la détection de visage dans les années 2000..

Éléments de la méthode La méthode de Viola et Jones est une approche basée sur l'apparence., qui consiste à parcourir l'ensemble de l'image en calculant un certain nombre de caractéristiques dans des zones rectangulaires qui se chevauchent. Elle a la particularité d'utiliser des caractéristiques très simples mais très nombreuses. Une première innovation de la méthode est l'introduction des images intégrales, qui permettent le calcul rapide de ces caractéristiques. Une deuxième innovation importante est la 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 un processus en cascade, ce qui apporte un net gain en temps de détection.

La méthode, en tant que méthode d'apprentissage supervisé, est divisée en deux étapes : une étape d'apprentissage du classifieur basé sur un grand nombre d'exemples positifs (c'est-à-dire les objets d'intérêt, par exemple des visages) et d'exemples négatifs, et une phase de détection par application de ce classifieur à des images inconnues.

Caractéristiques Description thumb|right|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, 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 et dont se sont inspirés Viola et Jones.

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 au point est définie à partir de l'image 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 un 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, typiquement de pixels ou de pixels.. 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 qui génère environ 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). Les changements d'échelles se font en modifiant successivement la taille de la fenêtre de détectionLes méthodes alternatives recourent principalement à la construction d'une pyramide d'images.. 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.

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.

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 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 images et leurs étiquettes associées , qui sont telles que si l'image est un exemple négatif et si est un exemple de l'objet à détecter. L'algorithme de boosting est constitué d'un nombre d'itérations, et pour chaque itération et chaque caractéristique , on construit un classifieur faible . Idéalement, le but est d'obtenir un classifieur qui prédise exactement les étiquettes pour chaque échantillon, c'est-à-dire . En pratique, le classifieur n'est pas parfait et l'erreur engendrée par ce classifieur est donnée par : ,

les é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 le classifieur présentant l'erreur la plus faible : .

Le classifieur fort final est construit par seuillage de la somme pondérée des classifieurs faibles sélectionnés :

Les sont des coefficients calculés à partir de l'erreur .

Cascade de classifieurs thumb|upright=2|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).