Les images intégrales de A à Z

Les images intégrales sont une façon de représenter des images matricielles pour permettre une rapidité accrue sur certaines opérations de calculs.
Ah yes, j’ai tout compris. 🙃

Ne vous inquiétez pas, on va bien expliquer ça en détails, et je vous garantis que vous allez vouloir utiliser des images intégrales partout après ça !

Qu’est-ce qu’une image matricielle ?

Si on part de la définition la plus simple d’une image matricielle, c’est une matrice de points colorés appelés pixels¹.
Pour une image en noir et blanc, chaque point sera représenté par une valeur, qui quantifie la luminosité de l’image. Un pixel valant « 0% de luminosité » sera noir, un pixel valant « 100% de luminosité » sera donc blanc.

Et pour une image en couleurs, un pixel sera représenté par un triplet/quadruplet de valeurs. Le triplet de valeur correspond aux pourcentages de rouge, vert et bleu dans le pixel, c’est ce qu’on appelle le modèle RVB. (On utilise le terme « canal » pour désigner chaque valeur du triplet.)
Si l’image supporte la transparence, cela devient un quadruplet avec la dernière valeur correspondant à ce pourcentage de transparence.

Malheureusement, ce n’est pas aussi simple, l’ordinateur ne manipule pas des pourcentages, mais bien des valeurs entières.

Donc en fonction du type d’image, on pourra stocker plus ou moins de nuances de chaque canal RVB. Le type d’image le plus répandu est celui qu’on appelle « true colors », qui permettent de stocker jusqu’à environ 16,8 millions de couleurs. Chaque canal est un nombre entre 0 et 255.
256 * 256 * 256 possibilités = 16 777 216 couleurs possibles

Décomposition des canaux

Une image en noir et blanc est simplement une matrice d’entiers. Il est très simple de travailler sur cette structure de données.

Il n’est donc pas rare de faire la décomposition des canaux des images colorées, pour pouvoir passer d’une matrice de triplets à 3 matrices d’entiers. On finit avec une matrice pour le rouge, une pour le vert et une pour le bleu.

Petit exemple de matrice d’entiers :

Bon, et dans tout ça les images intégrales ?

J’y viens, j’y viens.

Pour la suite, nous allons considérer que nous travaillons uniquement sur une matrice d’entier, par exemple celle d’une image en noir et blanc (mais cela pourrait tout autant correspondre au canal rouge (ou vert ou bleu) d’une image colorée).

Imaginons que nous avons notre belle matrice d’entiers, et que nous voulions faire la somme d’une certaine région de celle-ci.

Maintenant, on veut calculer cette somme. On fera donc :
(case[i,j] désigne la case à la ième ligne et à la jème colonne)

  case[2,2] + case[2,3] + case[2,4] + case[3,2] + case[3,3] + case[3,4]
=     12    +     10    +     5     +     2     +     13    +     1
= 43

Pour obtenir cette somme, nous avons donc dû accéder à 6 valeurs dans la matrice, et faire l’addition de ces termes. Très bien.

On remarque que le nombre d’accès à la matrice augmente en fonction de la taille de la région à sommer. Ici, la région faisait 3 cases de large sur 2 cases de haut. Mais si nous avions une vraie image, disons au format Full HD (1920 pixels de large x 1080 pixels de haut), une somme de région peut rapidement revenir à faire plusieurs milliers d’accès.
Par exemple sur une région de 600 x 910, cela donne 546 000 accès. 😕
Les accès à la mémoire sont des opérations relativement rapides pour un ordinateur, mais un nombre très élevé comme celui-ci peut très vide ralentir un programme, encore plus s’il faut calculer des sommes de beaucoup de régions.

Et c’est là qu’interviennent les images intégrales !

Ah ben enfin, c’est pas trop tôt !

Les images intégrales sont une façon de représenter la même matrice, mais en précalculant des sommes partielles.
La valeur d’une case correspond à la somme de toutes les cases en haut et à gauche d’elle.

Donc l’image intégrale de notre matrice précédente serait :

Et ça c’est une belle image intégrale !

Où est l’avantage ?

L’avantage, maintenant que nous travaillons déjà avec des sommes, c’est que pour faire la somme d’une région donnée, on ne fera que 4 accès à l’image intégrale, en tout et pour tout ! 🤯

Comment cela se fait-il ?

Disons que nous voulons à nouveau calculer la somme de la même région qu’avant. On va considérer les valeurs aux cases A, B, C et D.

Je vais donc vous donner la formule magique :

somme_rouge = D - C - B + A

Pourquoi ça marche ?

Voici la somme que contient la case D :

Si on lui enlève la somme de la case C, voilà ce qu’on obtient :

Si on enlève à D - C la somme de la case B, voilà ce qu’on obtient :

Très bien, on y arrive presque ! Sauf qu’en enlevant B et C, on a malheureusement enlevé 2 fois la région A ! 😱

Et c’est donc pour cela qu’on rajoute à la fin cette dernière, nous donnant au passage la région voulue :

Vous connaissez maintenant le principe derrière une image intégrale !

Dernière formalisation du calcul

• $(x_1, y_1)$ étant les coordonnées de la case la plus en haut à gauche de la région voulue
• $(x_2, y_2)$ les coordonnées de la case la plus en bas à droite de cette même région
• $ii$ étant l’image intégrale

La somme en passant par l’image intégrale se calcule donc ainsi :

$$Somme((x_1, y_1), (x_2, y_2)) = ii[x_2, y_2] - ii[x_1-1, y_2] - ii[x_2, y_1-1] + ii[x_1-1, y_1-1]$$

Moyenne d’une région d’une image ?

Un traitement qui est parfois réalisé sur une image est la moyenne des pixels d’une région. C’est notamment utilisé dans le downscaling (rendre les images plus petites qu’à l’origine).

Pour calculer cette moyenne de région, il nous faut simplement calculer la somme des pixels dans cette région, puis diviser cette somme par le nombre de cases ayant été sommées.

$$Moyenne((x_1, y_1), (x_2, y_2)) = \frac{Somme((x_1, y_1), (x_2, y_2))}{(x_2 - x_1 + 1) * (y_2 - y_1 + 1)}$$

Utilisation réelle

Les images intégrales ont été popularisées par la méthode de Viola–Jones, une méthode de détection d’objet dans une image. C’est l’une des premières méthodes efficaces pour la détection en temps réel, et elle a été inventée pour la détection de visages.

Les auteurs de la méthode ont proposé cette structure de données, l’image intégrale, et un algorithme l’utilisant, permettant de calculer des caractéristiques pseudo-Haar.

La viabilité de leur méthode pour l’utilisation en temps réel est surtout venu de cette utilisation des images intégrales, qui permettaient un calcul en temps constant de sommes de régions de n’importe quelle taille.

Alors, faut-il utiliser des images intégrales partout ?

Et bien…, oui et non.

Les images intégrales sont une structure de données permettant des gains de performances extrêmement élevés pour les opérations de somme et de moyenne, mais leur création est un peu coûteuse. En effet, il faut d’abord calculer l’image intégrale en parcourant entièrement l’image de départ.

Donc oui, les images intégrales sont très efficaces et devrait être utilisées quand plusieurs opérations de sommes de régions doivent être réalisées sur une même image.

Et non, si vous savez que votre algorithme ne calcule la somme que d’un très petit nombre de régions par image, il n’est pas forcément bénéfique d’utiliser une image intégrale.

Je ne sais toujours pas comment terminer mes articles.
« La toupie tournera jusqu’à ce qu’elle ne tourne plus. »