EP08_03 — 🟢 Immagine Integrale: Somme Rettangolari a Tempo Costante

8.14.3 EP08_03 🟢 Immagine Integrale: Somme Rettangolari a Tempo Costante

Immagina una telecamera di sorveglianza che elabora 30 fotogrammi al secondo e, per ogni fotogramma, il sistema deve analizzare l’immagine in decine di posizioni e scale diverse, testando in ciascuna un insieme di caratteristiche rettangolari per decidere “c’è un volto qui?”. Se calcolare la somma delle intensità di ogni rettangolo richiedesse sommare pixel per pixel, il sistema non avrebbe alcuna possibilità di valutare in tempo reale — il collo di bottiglia sarebbe proprio nella parte più ripetuta dell’algoritmo. È esattamente questo collo di bottiglia che l’immagine integrale elimina.

La Haar Cascade valuta migliaia di caratteristiche rettangolari per finestra, in molteplici posizioni e scale — qualcosa di irrealizzabile in tempo reale se ogni rettangolo richiedesse di sommare i propri pixel uno a uno. L’immagine integrale, definita nella sezione sulla Haar Cascade, risolve questo problema: una volta pre-calcolata, la somma delle intensità di qualsiasi regione rettangolare si ottiene con solo quattro query e tre operazioni aritmetiche, indipendentemente dalla dimensione del rettangolo.

Sei stato incaricato di implementare questa struttura da zero: in primo luogo, calcolare l’immagine integrale dall’immagine originale; successivamente, rispondere a query rettangolari arbitrarie.

8.14.3.1 📋 Linee Guida di Implementazione

Input: Leggere le dimensioni \(H \times W\) dell’immagine e i suoi \(H \times W\) valori interi di intensità.
Immagine integrale: Calcolare, per ogni posizione \((i,j)\) (indicizzazione a partire da \(0\), [riga][colonna]), \[ II(i,j) = \sum_{i' \le i,\ j' \le j} I(i', j'), \] ovvero la somma di tutti i pixel sopra e a sinistra di \((i,j)\), inclusa la posizione stessa.
Query: Leggere l’intero \(Q\) e, successivamente, \(Q\) righe, ciascuna con quattro interi \(x_1\ y_1\ x_2\ y_2\) — gli angoli superiore-sinistro e inferiore-destro di un rettangolo, entrambi inclusivi, con \(0 \le x_1 \le x_2 < W\) e \(0 \le y_1 \le y_2 < H\).
Somma rettangolare in O(1): Per ogni query, calcolare la somma delle intensità all’interno del rettangolo utilizzando esclusivamente valori già presenti in \(II\) (senza scorrere i pixel originali): \[ 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), \] trattando qualsiasi termine con indice di riga o colonna uguale a \(-1\) come \(0\).
Output: In primo luogo, stampare l’immagine integrale completa — \(H\) righe con \(W\) interi ciascuna. Successivamente, per ogni query, stampare un singolo intero: la somma della regione corrispondente.

8.14.3.2 📌 Vincoli Computazionali

Non ricalcolare per forza bruta: la risposta a ogni query deve utilizzare la formula a quattro termini su \(II\), non una somma diretta dei pixel del rettangolo (sebbene il risultato numerico sia lo stesso, l’obiettivo dell’esercizio è proprio questa tecnica).
Rettangoli con coordinate inclusive: \((x_1,y_1)\) e \((x_2,y_2)\) appartengono alla regione sommata.
Gestione dei bordi: quando si interroga \(II\) con indice \(-1\) (quando \(x_1=0\) o \(y_1=0\)), utilizzare il valore \(0\).

8.14.3.3 🧠 Fondamentazione Teorica

Elemento	Ruolo nella Haar Cascade
Immagine integrale \(II\)	Pre-calcolata una sola volta per immagine, in tempo \(O(HW)\)
Query in O(1)	Ogni caratteristica Haar (differenza tra somme di regioni rettangolari) viene valutata con poche operazioni, indipendentemente dall’area del rettangolo
Scalabilità	È questa costanza che rende possibile valutare migliaia di caratteristiche, in molteplici posizioni e scale, in tempo reale
Principio di inclusione-esclusione	I quattro termini della formula sommano la regione desiderata e sottraggono esattamente le aree conteggiate in eccesso

8.14.3.4 📦 Specifica di Input e Output (VPL)

Input:

Riga 1: Interi \(H\) e \(W\).
Prossime \(H\) righe: \(W\) interi ciascuna (immagine originale).
Riga successiva: Intero \(Q\).
Prossime \(Q\) righe: quattro interi \(x_1\ y_1\ x_2\ y_2\).

Output:

\(H\) righe con \(W\) interi ciascuna (l’immagine integrale).
\(Q\) righe, una per query, con la somma della regione corrispondente.

8.14.3.5 📌 Esempi

Input	Output	Osservazione
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 query copre l’intera immagine; la somma coincide con \(II(2,2)\) e con la somma di tutti i 9 valori.
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 prima query usa i quattro termini della formula; la seconda coincide direttamente con \(II(1,1)\), poiché inizia dall’origine.

🎮 Simulatore EP08_03: Somma Rettangolare con Immagine Integrale Interno

Scegli un rettangolo (x₁, y₁) – (x₂, y₂). L'immagine integrale II include un bordo virtuale (−1) con zeri per una validazione senza eccezioni.

Angolo Superiore-Sinistro (x₁, y₁) = (1,1)

x₁

y₁

Angolo Inferiore-Destro (x₂, y₂) = (2,2)

x₂

y₂

Immagine Originale I (4×4)

Immagine Integrale II (Con Bordo Virtuale −1)

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

Figura 8.17: Simulatore EP08_03: Somma Rettangolare in O(1) — Molteplici Situazioni di Bordo

%%writefile EP08_03.py
# Codice Python

Overwriting EP08_03.py

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

✔️ EP08_03.cases esiste già in casos/
📋 6 caso/i caricato/i da casos/EP08_03.cases

🔍 Test di Python: EP08_03.py
⚠️ EP08_03.py: file vuoto (meno di 3 righe). Test saltati.