Image intégrale

Une image intégrale (ou summed area table) est une représentation sous la forme d'une image numérique et un algorithme, permettant de calculer rapidement des sommes de valeurs dans des zones rectangulaires.

Calcul de la somme des pixels dans une zone rectangulaire arbitrairement située dans une image numérique: seuls 4 accès à l'image intégrale (A,B,C,D) sont nécessaires.

Proposée à l'origine comme une méthode d'infographie en 1984^[1], les images intégrales sont surtout connues en vision par ordinateur depuis 2001 par leur reformulation dans la méthode de Viola et Jones^[2].

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 et à gauche de ce point. Plus formellement, l'image intégrale ${\displaystyle ii}$ 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 sous forme de table de correspondance, la somme des valeurs dans une zone rectangulaire peut être calculée en seulement 4 accès à l'image intégrale (6 accès pour deux zones rectangulaires contiguës), et donc en temps constant quelle que soit la taille de la zone^[2].

Cette somme peut se calculer par récurrence, par:

${\displaystyle s(x,y)=s(x,y-1)+i(x,y)}$

${\displaystyle ii(x,y)=ii(x-1,y)+s(x,y)}$

où ${\displaystyle s(x,y)}$ est la somme cumulée de la ligne x jusqu'à la colonne y. L'image intégrale peut donc se calculer avec un seul parcours de l'image d'origine.

Une fois l'image intégrale calculée, la somme des pixels à l'intérieur de n'importe quel rectangle ABCD peut être évaluée en seulement 4 accès:

${\displaystyle \sum _{\begin{smallmatrix}x_{A}<x'\leq x_{C}\\y_{A}<y'\leq y_{C}\end{smallmatrix}}i(x',y')=ii(A)+ii(C)-ii(B)-ii(D).}$

Extensions

La méthode a été étendue aux zones rectangulaires orientées à 45° en 2002^[3],[4]. Le principe est identique, sauf que la somme est maintenant calculée dans un demi-rectangle orienté à 45°:

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

Le calcul de la somme dans le rectangle souhaité à partir de l'image intégrale s'effectue toujours en une simple somme de 4 éléments de l'image intégrale^[3].

L'idée à la base des images intégrales a été reprise en 2005 pour proposer l'histogramme intégral, qui permet le calcul rapide d'histogrammes locaux^[5].

Applications

Les images intégrales ont surtout été utilisées pour le calcul des caractéristiques pseudo-Haar dans la méthode de Viola et Jones et ses dérivées, mais également pour calculer d'autres types de caractéristiques nécessitant le calcul de sommes locales de pixels, par exemple les histogrammes de gradients orientés^[6].

Notes et références

1. Franklin Crow « Summed-area tables for texture mapping » (1984) (lire en ligne)
   — « (ibid.) », dans SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p. 207–212
2. Paul Viola et Michael Jones, Robust Real-time Object Detection IJCV 2001
3. Rainer Lienhart et Jochen Maydt, An Extended Set of Haar-like Features for Rapid Object Detection, In IEEE ICIP, 2002
4. Rainer Lienhart, Alexander Kuranov, and Vadim Pisarevsky. Empirical analysis of detection cascades of boosted classifiers for rapid object detection. pages 297–304. 2003.
5. Porikli, F., "Integral Histogram: A Fast Way to Extract Histograms in Cartesian Spaces", proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2005
6. Qiang Zhu, Shai Avidan, Mei C. Yeh, and Kwang T. Cheng. Fast Human Detection Using a Cascade of Histograms of Oriented Gradients. In IEEE CVPR, p.  1491-1498. 2006.

• Portail de l’imagerie numérique