EP08_03 — 🟢 Imagen Integral: Sumas Rectangulares en Tiempo Constante

8.14.3 EP08_03 🟢 Imagen Integral: Sumas Rectangulares en Tiempo Constante

Imagina una cámara de seguridad procesando 30 fotogramas por segundo, y para cada fotograma el sistema necesita recorrer la imagen en decenas de posiciones y escalas diferentes, probando en cada una un conjunto de características rectangulares para decidir “¿hay una cara aquí?”. Si calcular la suma de intensidades de cada rectángulo requiriese sumar píxel a píxel, el sistema no tendría la menor oportunidad de evaluar en tiempo real — el cuello de botella estaría justamente en la parte más repetida del algoritmo. Es exactamente ese cuello de botella el que la imagen integral elimina.

El Haar Cascade evalúa miles de características rectangulares por ventana, en múltiples posiciones y escalas — algo inviable en tiempo real si cada rectángulo requiriese sumar sus píxeles uno a uno. La imagen integral, definida en la sección sobre Haar Cascade, resuelve este problema: una vez precomputada, la suma de intensidades de cualquier región rectangular se obtiene con solo cuatro consultas y tres operaciones aritméticas, independientemente del tamaño del rectángulo.

Se te ha encargado implementar esta estructura desde cero: primero, calcular la imagen integral a partir de la imagen original; luego, responder a consultas rectangulares arbitrarias.

8.14.3.1 📋 Directrices de Implementación

Entrada: Leer las dimensiones \(H \times W\) de la imagen y sus \(H \times W\) valores enteros de intensidad.
Imagen integral: Calcular, para cada posición \((i,j)\) (indexación desde \(0\), [fila][columna]), \[ II(i,j) = \sum_{i' \le i,\ j' \le j} I(i', j'), \] es decir, la suma de todos los píxeles arriba y a la izquierda de \((i,j)\), incluyendo la propia posición.
Consultas: Leer el entero \(Q\) y, a continuación, \(Q\) líneas, cada una con cuatro enteros \(x_1\ y_1\ x_2\ y_2\) — las esquinas superior-izquierda e inferior-derecha de un rectángulo, ambas inclusivas, con \(0 \le x_1 \le x_2 < W\) y \(0 \le y_1 \le y_2 < H\).
Suma rectangular en O(1): Para cada consulta, calcular la suma de intensidades dentro del rectángulo usando exclusivamente valores ya presentes en \(II\) (sin recorrer los píxeles originales): \[ 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), \] tratando cualquier término con índice de fila o columna igual a \(-1\) como \(0\).
Salida: Primero, imprimir la imagen integral completa — \(H\) líneas con \(W\) enteros cada una. Luego, para cada consulta, imprimir un único entero: la suma de la región correspondiente.

8.14.3.2 📌 Restricciones Computacionales

No recalcular por fuerza bruta: la respuesta a cada consulta debe usar la fórmula de cuatro términos sobre \(II\), no una suma directa de los píxeles del rectángulo (aunque el resultado numérico sea el mismo, el objetivo del ejercicio es justamente esa técnica).
Rectángulos con coordenadas inclusivas: \((x_1,y_1)\) y \((x_2,y_2)\) pertenecen a la región sumada.
Tratamiento de borde: al consultar \(II\) con índice \(-1\) (cuando \(x_1=0\) o \(y_1=0\)), utilizar el valor \(0\).

8.14.3.3 🧠 Fundamentación Teórica

Elemento	Papel en el Haar Cascade
Imagen integral \(II\)	Precomputada una única vez por imagen, en tiempo \(O(HW)\)
Consulta en O(1)	Cada característica Haar (diferencia entre sumas de regiones rectangulares) se evalúa con pocas operaciones, independientemente del área del rectángulo
Escalabilidad	Es esa constancia la que hace viable evaluar miles de características, en múltiples posiciones y escalas, en tiempo real
Principio de inclusión-exclusión	Los cuatro términos de la fórmula suman la región deseada y restan exactamente las áreas contadas en exceso

8.14.3.4 📦 Especificación de Entrada y Salida (VPL)

Entrada:

Línea 1: Enteros \(H\) y \(W\).
Siguientes \(H\) líneas: \(W\) enteros cada una (imagen original).
Siguiente línea: Entero \(Q\).
Siguientes \(Q\) líneas: cuatro enteros \(x_1\ y_1\ x_2\ y_2\).

Salida:

\(H\) líneas con \(W\) enteros cada una (la imagen integral).
\(Q\) líneas, una por consulta, con la suma de la región correspondiente.

8.14.3.5 📌 Ejemplos

Entrada	Salida	Observación
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 consulta cubre la imagen completa; la suma coincide con \(II(2,2)\) y con la suma de todos los 9 valores.
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 primera consulta usa los cuatro términos de la fórmula; la segunda coincide directamente con \(II(1,1)\), pues comienza en el origen.

🎮 Simulador EP08_03: Soma Rectangular con Imagen Integral Interno

Elija un rectángulo (x₁, y₁) – (x₂, y₂). La imagen integral II incluye borde virtual (−1) con ceros para validación sin excepciones.

Esquina Superior-Izquierda (x₁, y₁) = (1,1)

x₁

y₁

Esquina Inferior-Derecha (x₂, y₂) = (2,2)

x₂

y₂

Imagen Original I (4×4)

Imagen Integral II (Con Borde Virtual −1)

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

Figura 8.17: Simulador EP08_03: Soma Rectangular en O(1) — Múltiples Situaciones de Borde

%%writefile EP08_03.py
# Código Python

Overwriting EP08_03.py

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

✔️ EP08_03.cases ya existe en casos/
📋 6 caso(s) cargado(s) de casos/EP08_03.cases

🔍 Probando Python: EP08_03.py
⚠️ EP08_03.py: archivo vacío (menos de 3 líneas). Pruebas omitidas.