EP08_03 — 🟢 Imagem Integral: Somas Retangulares em Tempo Constante

8.14.3 EP08_03 🟢 Imagem Integral: Somas Retangulares em Tempo Constante

Imagine uma câmera de segurança processando 30 quadros por segundo, e para cada quadro o sistema precisa varrer a imagem em dezenas de posições e escalas diferentes, testando em cada uma um conjunto de características retangulares para decidir “há um rosto aqui?”. Se calcular a soma de intensidades de cada retângulo exigisse somar pixel a pixel, o sistema não teria a menor chance de avaliar em tempo real — o gargalo estaria justamente na parte mais repetida do algoritmo. É exatamente esse gargalo que a imagem integral elimina.

O Haar Cascade avalia milhares de características retangulares por janela, em múltiplas posições e escalas — algo inviável em tempo real se cada retângulo exigisse somar seus pixels um a um. A imagem integral, definida na seção sobre Haar Cascade, resolve esse problema: uma vez pré-computada, a soma de intensidades de qualquer região retangular é obtida com apenas quatro consultas e três operações aritméticas, independentemente do tamanho do retângulo.

Você foi encarregado de implementar essa estrutura do zero: primeiro, calcular a imagem integral a partir da imagem original; em seguida, respondê-la para consultas retangulares arbitrárias.

8.14.3.1 📋 Diretrizes de Implementação

Entrada: Ler as dimensões \(H \times W\) da imagem e seus \(H \times W\) valores inteiros de intensidade.
Imagem integral: Calcular, para cada posição \((i,j)\) (indexação a partir de \(0\), [linha][coluna]), \[ II(i,j) = \sum_{i' \le i,\ j' \le j} I(i', j'), \] ou seja, a soma de todos os pixels acima e à esquerda de \((i,j)\), incluindo a própria posição.
Consultas: Ler o inteiro \(Q\) e, em seguida, \(Q\) linhas, cada uma com quatro inteiros \(x_1\ y_1\ x_2\ y_2\) — os cantos superior-esquerdo e inferior-direito de um retângulo, ambos inclusivos, com \(0 \le x_1 \le x_2 < W\) e \(0 \le y_1 \le y_2 < H\).
Soma retangular em O(1): Para cada consulta, calcular a soma de intensidades dentro do retângulo usando exclusivamente valores já presentes em \(II\) (sem percorrer os pixels originais): \[ 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 qualquer termo com índice de linha ou coluna igual a \(-1\) como \(0\).
Saída: Primeiro, imprimir a imagem integral completa — \(H\) linhas com \(W\) inteiros cada. Em seguida, para cada consulta, imprimir um único inteiro: a soma da região correspondente.

8.14.3.2 📌 Restrições Computacionais

Não recalcule por força bruta: a resposta a cada consulta deve usar a fórmula de quatro termos sobre \(II\), não uma soma direta dos pixels do retângulo (ainda que o resultado numérico seja o mesmo, o objetivo do exercício é justamente essa técnica).
Retângulos com coordenadas inclusivas: \((x_1,y_1)\) e \((x_2,y_2)\) pertencem à região somada.
Tratamento de borda: ao consultar \(II\) com índice \(-1\) (quando \(x_1=0\) ou \(y_1=0\)), utilize o valor \(0\).

8.14.3.3 🧠 Fundamentação Teórica

Elemento	Papel no Haar Cascade
Imagem integral \(II\)	Pré-computada uma única vez por imagem, em tempo \(O(HW)\)
Consulta em O(1)	Cada característica Haar (diferença entre somas de regiões retangulares) é avaliada com poucas operações, independentemente da área do retângulo
Escalabilidade	É essa constância que viabiliza avaliar milhares de características, em múltiplas posições e escalas, em tempo real
Princípio de inclusão-exclusão	Os quatro termos da fórmula somam a região desejada e subtraem exatamente as áreas contadas em excesso

8.14.3.4 📦 Especificação de Entrada e Saída (VPL)

Entrada:

Linha 1: Inteiros \(H\) e \(W\).
Próximas \(H\) linhas: \(W\) inteiros cada (imagem original).
Próxima linha: Inteiro \(Q\).
Próximas \(Q\) linhas: quatro inteiros \(x_1\ y_1\ x_2\ y_2\).

Saída:

\(H\) linhas com \(W\) inteiros cada (a imagem integral).
\(Q\) linhas, uma por consulta, com a soma da região correspondente.

8.14.3.5 📌 Exemplos

Entrada	Saída	Observação
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	A consulta cobre a imagem inteira; a soma coincide com \(II(2,2)\) e com a soma de todos os 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	A primeira consulta usa os quatro termos da fórmula; a segunda coincide diretamente com \(II(1,1)\), pois começa na origem.

🎮 Simulador EP08_03: Soma Retangular com Imagem Integral Interno

Escolha um retângulo (x₁, y₁) – (x₂, y₂). A imagem integral II inclui borda virtual (−1) com zeros para validação sem exceções.

Canto Superior-Esquerdo (x₁, y₁) = (1,1)

x₁

y₁

Canto Inferior-Direito (x₂, y₂) = (2,2)

x₂

y₂

Imagem Original I (4×4)

Imagem Integral II (Com Borda 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 Retangular em O(1) — Múltiplas Situações de Borda

%%writefile EP08_03.py
# Código Python

Writing EP08_03.py

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

✔️ EP08_03.cases já existe em casos/
📋 6 caso(s) carregado(s) de casos/EP08_03.cases

🔍 Testando Python: EP08_03.py
⚠️ EP08_03.py: Arquivo sem conteúdo (menos de 3 linhas). Testes ignorados.