EP08_03 — 🟢 Image intégrale : sommes rectangulaires en temps constant

8.14.3 EP08_03 🟢 Image intégrale : sommes rectangulaires en temps constant

Imaginez une caméra de sécurité traitant 30 images par seconde, et pour chaque image, le système doit balayer l’image à des dizaines de positions et d’échelles différentes, testant à chaque fois un ensemble de caractéristiques rectangulaires pour décider « y a-t-il un visage ici ? ». Si le calcul de la somme des intensités de chaque rectangle exigeait de sommer pixel par pixel, le système n’aurait aucune chance de fonctionner en temps réel — le goulot d’étranglement se situerait précisément dans la partie la plus répétée de l’algorithme. C’est exactement ce goulot d’étranglement que l’image intégrale élimine.

Le détecteur Haar Cascade évalue des milliers de caractéristiques rectangulaires par fenêtre, à de multiples positions et échelles — une approche irréalisable en temps réel si chaque rectangle exigeait la somme de ses pixels un par un. L’image intégrale, définie dans la section consacrée au Haar Cascade, résout ce problème : une fois précalculée, la somme des intensités de n’importe quelle région rectangulaire s’obtient avec seulement quatre consultations et trois opérations arithmétiques, quelle que soit la taille du rectangle.

Vous êtes chargé d’implémenter cette structure à partir de zéro : d’abord, calculer l’image intégrale à partir de l’image originale ; ensuite, répondre aux requêtes rectangulaires arbitraires.

8.14.3.1 📋 Directives d’implémentation

Entrée : Lire les dimensions \(H \times W\) de l’image et ses \(H \times W\) valeurs entières d’intensité.
Image intégrale : Calculer, pour chaque position \((i,j)\) (indexation à partir de \(0\), [ligne][colonne]), \[ II(i,j) = \sum_{i' \le i,\ j' \le j} I(i', j'), \] c’est-à-dire la somme de tous les pixels au-dessus et à gauche de \((i,j)\), y compris la position elle-même.
Requêtes : Lire l’entier \(Q\), puis \(Q\) lignes, chacune avec quatre entiers \(x_1\ y_1\ x_2\ y_2\) — les coins supérieur-gauche et inférieur-droit d’un rectangle, tous deux inclusifs, avec \(0 \le x_1 \le x_2 < W\) et \(0 \le y_1 \le y_2 < H\).
Somme rectangulaire en O(1) : Pour chaque requête, calculer la somme des intensités dans le rectangle en utilisant uniquement des valeurs déjà présentes dans \(II\) (sans parcourir les pixels originaux) : \[ S(x_1,y_1,x_2,y_2) = II(y_2,x_2) - II(y_2, x_1{-}1) - II(y_1{-}1, x_2) + II(y_1{-}1, x_1{-}1), \] en traitant tout terme dont l’indice de ligne ou de colonne est égal à \(-1\) comme \(0\).
Sortie : D’abord, imprimer l’image intégrale complète — \(H\) lignes avec \(W\) entiers chacune. Ensuite, pour chaque requête, imprimer un seul entier : la somme de la région correspondante.

8.14.3.2 📌 Contraintes de calcul

Ne recalculez pas par force brute : la réponse à chaque requête doit utiliser la formule à quatre termes sur \(II\), et non une somme directe des pixels du rectangle (même si le résultat numérique est le même, l’objectif de l’exercice est précisément cette technique).
Rectangles à coordonnées inclusives : \((x_1,y_1)\) et \((x_2,y_2)\) appartiennent à la région sommée.
Traitement des bords : lors de la consultation de \(II\) avec l’indice \(-1\) (lorsque \(x_1=0\) ou \(y_1=0\)), utiliser la valeur \(0\).

8.14.3.3 🧠 Fondement théorique

Élément	Rôle dans le détecteur Haar Cascade
Image intégrale \(II\)	Précalculée une seule fois par image, en temps \(O(HW)\)
Requête en O(1)	Chaque caractéristique Haar (différence entre les sommes de régions rectangulaires) est évaluée avec peu d’opérations, quelle que soit l’aire du rectangle
Scalabilité	C’est cette constance qui rend possible l’évaluation de milliers de caractéristiques, à de multiples positions et échelles, en temps réel
Principe d’inclusion-exclusion	Les quatre termes de la formule additionnent la région souhaitée et soustraient exactement les zones comptées en double

8.14.3.4 📦 Spécification des entrées et sorties (VPL)

Entrée :

Ligne 1 : Entiers \(H\) et \(W\).
\(H\) lignes suivantes : \(W\) entiers chacune (image originale).
Ligne suivante : Entier \(Q\).
\(Q\) lignes suivantes : quatre entiers \(x_1\ y_1\ x_2\ y_2\).

Sortie :

\(H\) lignes avec \(W\) entiers chacune (image intégrale).
\(Q\) lignes, une par requête, avec la somme de la région correspondante.

8.14.3.5 📌 Exemples

Entrée	Sortie	Observation
3 3 1 2 3 4 5 6 7 8 9 1 0 0 2 2	1 3 6 5 12 21 12 27 45 45	La requête couvre l’image entière ; la somme coïncide avec \(II(2,2)\) et avec la somme des 9 valeurs.
3 3 1 2 3 4 5 6 7 8 9 2 1 1 2 2 0 0 1 1	1 3 6 5 12 21 12 27 45 28 12	La première requête utilise les quatre termes de la formule ; la seconde coïncide directement avec \(II(1,1)\), car elle commence à l’origine.

🎮 Simulateur EP08_03 : Somme rectangulaire avec image intégrale Interne

Choisissez un rectangle (x₁, y₁) – (x₂, y₂). L'image intégrale II inclut une bordure virtuelle (−1) avec des zéros pour une validation sans exceptions.

Coin supérieur-gauche (x₁, y₁) = (1,1)

x₁

y₁

Coin inférieur-droit (x₂, y₂) = (2,2)

x₂

y₂

Image originale I (4×4)

Image intégrale II (Avec bordure virtuelle −1)

+ II(y₂, x₂) − II(y₂, x₁−1) − II(y₁−1, x₂) + II(y₁−1, x₁−1)

Figure 8.17: Simulateur EP08_03 : Somme Rectangulaire en O(1) — Multiples Situations de Bord

%%writefile EP08_03.py
# Code Python

Overwriting EP08_03.py

TestSuite("EP08_03.py").run()

✔️ EP08_03.cases existe déjà dans casos/
📋 6 cas chargé(s) depuis casos/EP08_03.cases

🔍 Test de Python : EP08_03.py
⚠️ EP08_03.py : fichier vide (moins de 3 lignes). Tests ignorés.