Histogramme de gradient orienté

Une image de piéton (gauche) et son gradient (droite)

Un histogramme de gradient orienté (en anglais, histogram of oriented gradients ou HOG) est une caractéristique utilisée en vision par ordinateur pour la détection d'objet. La technique calcule des histogrammes locaux de l'orientation du gradient sur une grille dense, c'est-à-dire sur des zones régulièrement réparties sur l'image. Elle possède des points communs avec les SIFT, les Shape contexts et les histogrammes d'orientation de contours, mais en diffère notamment par l'utilisation d'une grille dense. La méthode est particulièrement efficace pour la détection de personnes.

Les HOG ont été proposés par Navneet Dalal et Bill Triggs, chercheurs au CNRS et à l'INRIA de Grenoble, à la conférence CVPR de juin 2005.

Méthode

Description générale

L'idée importante derrière le descripteur HOG est que l'apparence et la forme locale d'un objet dans une image peuvent être décrites par la distribution de l'intensité du gradient ou la direction des contours. Ceci peut être fait en divisant l'image en régions adjacentes de petite taille, appelées cellules, et en calculant pour chaque cellule l'histogramme des directions du gradient ou des orientations des contours pour les pixels à l'intérieur de cette cellule. La combinaison des histogrammes forme alors le descripteur HOG. Pour de meilleurs résultats, les histogrammes locaux sont normalisés en contraste, en calculant une mesure de l'intensité sur des zones plus larges que les cellules, appelées des blocs, et en utilisant cette valeur pour normaliser toutes les cellules du bloc. Cette normalisation permet une meilleure résistance aux changements d'illuminations et aux ombres.

Dalal et Triggs ont testé de nombreuses combinaisons de pré et post-traitements ou de valeurs de paramètres. On ne décrit ici que les valeurs et les méthodes retenues.

Construction du descripteur

Calcul du gradient

Une étape de pré-traitement peut être effectuée avant le calcul du gradient, afin que les couleurs de l'image soient normalisées et une correction gamma correcte. Cette étape ne s'est finalement pas avérée nécessaire, la normalisation du descripteur lui-même s'avérant suffisante. Dalal et Triggs ont également testé plusieurs espaces de couleur, le meilleur étant RGB.

La première étape de la méthode est le calcul du gradient, la méthode la plus courante pour cela consistant à appliquer un filtre dérivatif 1-D centré, dans les directions horizontales et verticales. Les masques suivants sont utilisés pour cela:

$[-1,0,1]{\text{ et }}[-1,0,1]^{T}.\,$

Dans le cas des images couleurs, le gradient est calculé séparément pour chaque composante, et on retient pour chaque pixel le gradient de plus grande norme.

D'autres types de masques plus complexes ont été testés, comme des filtres de Sobel 3x3, ou des masques diagonaux, ou non centrés. Dalal et Triggs ont également essayé d'appliquer un filtrage gaussien avant l'application du masque, mais toutes ces opérations font baisser sensiblement les performances par rapport à l'application du masque dérivatif le plus simple, et sans filtrage préalable.

Construction de l'histogramme

La seconde étape est la création des histogrammes de l'orientation des gradients. Ceci est fait dans des cellules carrées de petite taille (de 4x4 à 12x12 pixels). Chaque pixel de la cellule vote alors pour une classe de l'histogramme, en fonction de l'orientation du gradient à ce point. Le vote du pixel est pondéré par l'intensité du gradient en ce point. Les histogrammes sont uniformes de 0 à 180° (cas non signé) ou de 0 à 360° (cas signé).

Dalal et Triggs font remarquer qu'une quantification fine de l'histogramme est nécessaire, et ils obtiennent leurs meilleurs résultats avec un histogramme à 9 classes. Prendre en compte le signe du gradient n'améliore pas les performances pour la détection de personnes, mais peut être significatif pour d'autres types d'objets.

Formation des blocs

Une étape importante est la normalisation des descripteurs afin d'éviter les disparités dues aux variations d'illumination. Cette étape introduit également de la redondance dans le descripteur.

Pour cela, les auteurs regroupent plusieurs cellules dans un bloc, qui est l'unité sur laquelle est effectuée la normalisation. Les blocs se recouvrent, donc une même cellule participe plusieurs fois au descripteur final, comme membre de blocs différents. Deux types de géométrie de blocs sont proposées: rectangulaire (R-HOG) ou circulaire (C-HOG). Les expériences faites par Dalal et Triggs ont montré que la meilleure performance était obtenue pour des blocs rectangulaires contenant 3x3 cellules de 6x6 pixels chacune. Une amélioration mineure de performance est obtenue en pondérant les pixels par une fenêtre gaussienne sur le bloc, diminuant la contribution des pixels sur les bords. Les auteurs remarquent que la formation du descripteur R-HOG est assez semblable au descripteur SIFT, à la différence que les R-HOG sont calculés sur une grille dense et à une seule échelle, et non sur des points d'intérêts à plusieurs échelles comme les SIFT.

Normalisation des blocs

Quatre types de normalisation sont explorées. Le vecteur non normalisé contenant tous les histogrammes d'un seul bloc est désigné par $v$, sa k-norme par $||v||_{k}$ et $\epsilon$ est une constante de faible valeur. Le facteur de normalisation est alors défini par:

L2-norme: $f={v \over {\sqrt {||v||_{2}^{2}+\epsilon ^{2}}}}$

L1-norme: $f={v \over (||v||_{1}+\epsilon )}$

L1-racine: $f={\sqrt {v \over (||v||_{1}+\epsilon )}}$

Une quatrième norme L2-hys, consistant à calculer v tout d'abord par la L2-norme, puis limiter les valeurs maximales de v à 0.2, et ensuite à renormaliser. Les normes L2-Hys, L2-norme, et L1-racine obtiennent des performances similaires, tandis que L1-norme obtient de moins bons résultats, mais toutefois bien meilleurs que l'absence de normalisation.

Classification

L'étape finale dans le processus de détection d'objet est l'utilisation des descripteurs HOG pour entraîner un classifieur supervisé. Cette étape ne fait pas partie de la définition du descripteur HOG à proprement parler et différents types de classifieurs peuvent être utilisés. Dalal et Triggs choisissent volontairement un classifeur simple, un SVM à noyau linéaire, afin de mesurer essentiellement l'apport des HOG. Ils précisent en particulier qu'il serait intéressant de développer une méthode à base de cascade comme la méthode de Viola et Jones, en utilisant les HOG.

Ils précisent que l'utilisation d'un noyau gaussien améliore les performances de 3 %, pour un taux de faux positifs par fenêtre de $10^{-4}$, mais un coût de calcul bien plus élevé.

Extensions

Lors du workshop PASCAL sur la détection de classe d'objet en 2006, Dalal et Triggs ont présenté des résultats de l'application des HOG sur d'autres types d'objets, en particulier des voitures, des bus, des vélos, ainsi que des animaux comme des chiens, chats, vaches. Pour obtenir de bons résultats, les paramètres de taille de blocs et la méthode normalisation doivent être adaptés pour chaque classe d'objet. Toujours en 2006, à ECCV, Dalal et Triggs, avec Cordelia Schmid ont proposé une extension à la vidéo, pour détecter des personnes dans des films. Cela consiste à combiner les HOG calculés sur chaque image de la vidéo, avec un histogramme de mouvement (Internal Motion Histograms IMH) entre deux images successives. Les IMH utilisent l'amplitude du gradient provenant du Flux optique calculé sur deux images consécutives, et ces amplitudes sont utilisées de la même manière que les HOG calculés sur les images statiques. Lors de tests sur des corpus extraits de plusieurs DVD de films, la méthode qui combine HOG et IMH obtient un taux de ratés de 0.1, pour $10^{-4}$ de taux de fausse alarme.

Les HOG ont rapidement été repris par d'autres chercheurs pour des systèmes de détection de personnes. En 2006, des chercheurs de l'INSA Rouen et de l'université de Parme proposent un système basé sur les HOG et deux caméras infrarouges, et la position des personnes est estimée par stéréovision

Lors de la conférence CVPR de 2006, des chercheurs de Mitsubishi Electric proposent d'utiliser les HOG en combinaison avec une cascade de classifieurs, similaire à celle présente dans la méthode de Viola et Jones. Ils introduisent également des blocs qui varient en taille et en position, et les meilleurs sont sélectionnés par AdaBoost. Leurs expériences donnent des résultats similaires à ceux de Dalal et Triggs, mais avec des temps de détection jusqu'à 70 fois plus rapide. Un brevet a été déposé par Mitsubishi sur cette méthode.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Histogram of oriented gradients » (voir la liste des auteurs).