PDI+VC · Exercício de Programação

EP09_04 — 🟡 Interseção sobre União (IoU) e Supressão de Não-Máximos (NMS)

9.10.4 EP09_04 🟡 Interseção sobre União (IoU) e Supressão de Não-Máximos (NMS)

Modelos de detecção de objetos podem produzir várias caixas delimitadoras candidatas para um mesmo objeto, com diferentes posições e pontuações de confiança. A etapa de pós-processamento responsável por eliminar essas detecções redundantes é a Supressão de Não-Máximos (NMS), cuja operação fundamental utiliza a métrica de Interseção sobre União (IoU).

A NMS utiliza essa medida para decidir quais caixas devem ser mantidas. Em geral, a caixa com maior confiança é selecionada primeiro; em seguida, caixas que apresentam IoU acima de um determinado limiar com a caixa selecionada são consideradas redundantes e removidas. O processo é repetido até que não restem caixas candidatas.

Neste exercício, você deverá implementar o algoritmo de NMS do zero, calculando a IoU entre caixas e aplicando sucessivamente o critério de seleção e supressão para produzir o conjunto final de detecções.

9.10.4.1 📋 Diretrizes de Implementação

  1. Entrada: Ler o inteiro \(N\) (número de caixas candidatas) e o limiar real \(\tau\) (limiar de IoU para supressão), na mesma linha.

  2. Caixas: Ler \(N\) linhas, cada uma com cinco valores reais:

    x1 y1 x2 y2 score

    em que \((x_1,y_1)\) representa o canto superior esquerdo, \((x_2,y_2)\) o canto inferior direito e score a pontuação de confiança.

  3. Interseção sobre União: Para duas caixas \(A\) e \(B\),

    \[ IoU(A,B)= \frac{\operatorname{Área}(A\cap B)} {\operatorname{Área}(A\cup B)}. \]

    A área de interseção deve ser calculada a partir da sobreposição dos intervalos em \(x\) e \(y\). Se não houver sobreposição, a área de interseção é zero.

  4. Algoritmo guloso de NMS:

    1. Ordene as caixas por score decrescente. Em caso de empate, mantenha a ordem original de leitura.

    2. Selecione a caixa de maior pontuação entre as caixas restantes e adicione-a ao conjunto de saída.

    3. Calcule o IoU entre a caixa selecionada e todas as caixas ainda restantes. Suprima as caixas para as quais

    \[ \text{IoU} > \tau. \]

    1. Repita os passos (b) e (c) até que não restem caixas.

  5. Saída: Para cada caixa mantida, na ordem em que foi selecionada, imprimir seu índice original (posição de leitura, começando em \(0\)) e seu score, formatado com 4 casas decimais. Ao final, imprimir:

    Total mantidas: X

9.10.4.2 📌 Restrições Computacionais

  • Supressão estrita: apenas caixas com \(\text{IoU} > \tau\) são suprimidas. Caixas com \(\text{IoU}=\tau\) são mantidas.
  • Índices originais: a saída referencia a posição em que cada caixa foi lida na entrada (começando em \(0\)), e não sua posição após a ordenação.
  • Ordenação estável: em caso de score iguais, deve ser preservada a ordem original de leitura.
  • Retângulos alinhados aos eixos: todas as caixas são especificadas por dois cantos, com \(x_1 < x_2\) e \(y_1 < y_2\) garantidos na entrada.
  • Coordenadas e pontuações: os valores reais podem ser positivos ou negativos, conforme os limites definidos pela entrada, mas as dimensões das caixas são sempre positivas.

9.10.4.3 🧠 Fundamentação Teórica

Elemento Papel no pós-processamento de detecção
IoU Quantifica a sobreposição espacial entre duas caixas; \(\text{IoU}=1\) para caixas idênticas e \(\text{IoU}=0\) para caixas sem sobreposição
Ordenação por confiança Faz com que a caixa de maior score seja analisada primeiro
Limiar \(\tau\) Define a quantidade de sobreposição necessária para que uma caixa seja considerada redundante
Supressão Remove caixas que apresentam grande sobreposição com uma caixa já selecionada
Caixas distantes Possuem IoU próximo de zero e, em geral, não são suprimidas por essa regra

9.10.4.4 🧩 Métodos do morph.py que podem ajudar

  • mm.IoU(boxA, boxB) — calcula a métrica de IoU, mas espera as caixas no formato \((x,y,w,h)\), isto é, canto superior esquerdo, largura e altura. A entrada deste exercício utiliza o formato \((x_1,y_1,x_2,y_2)\). A conversão é direta:

    \[ w=x_2-x_1,\qquad h=y_2-y_1. \]

    O uso dessa função é opcional. O objetivo principal do exercício é implementar corretamente o processo de seleção e supressão da NMS.

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

Entrada:

  • Linha 1: inteiro \(N\) e real \(\tau\).
  • Próximas \(N\) linhas: \(x_1\ y_1\ x_2\ y_2\ \text{score}\).

Saída:

  • Uma linha por caixa mantida, na ordem de seleção: índice score.
  • Última linha: Total mantidas: X.
🎮 Simulador: IoU e Supressão de Não-Máximos 🟡 NMS
Caixa selecionada Caixa mantida Caixa suprimida Caixa candidata
5
0.50
Padrão
🎯 Visualização das Caixas
📋 Passo a Passo da NMS
Figura 9.46: Simulador EP09_04: IoU e Supressão de Não-Máximos (NMS) 
%%writefile EP09_04.py
# Código Python
Writing EP09_04.py
TestSuite("EP09_04.py").run()
✔️ EP09_04.cases já existe em casos/
📋 3 caso(s) carregado(s) de casos/EP09_04.cases

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