A Dynamic Programming Framework for Discovering Count and Values of Multilevel Image Thresholding

Resumo Técnico: Uma Estrutura de Programação Dinâmica para Descobrir a Quantidade e os Valores de Limiarização de Imagem Multinível

Declaração do Problema
A limiarização de imagem multinível é uma etapa fundamental de pré-processamento em visão computacional, frequentemente enquadrada como um problema de agrupamento onde as intensidades dos pixels são separadas em grupos distintos. Embora os métodos mais avançados geralmente dependam de uma função objetivo (por exemplo, Otsu, Kapur, Kittler) e de uma estratégia de busca para encontrar limiares ótimos, uma limitação crítica persiste: a maioria dos métodos exige que o usuário especifique manualmente o número de limiares ($n$) como entrada. Determinar o $n$ apropriado não é trivial, pois métricas de similaridade como SSIM e PSNR favorecem inerentemente contagens mais altas de limiares para maximizar a fidelidade da imagem, tornando-as inadequadas para selecionar automaticamente o $n$ ótimo. Além disso, embora estratégias de busca exatas como a Programação Dinâmica (DP) garantam soluções ótimas para um $n$ fixo, elas sofrem com um crescimento exponencial do tempo de execução quando o usuário tenta buscar o melhor $n$ iterando através de múltiplos valores candidatos. Por outro lado, métodos metaheurísticos aproximados oferecem velocidade, mas carecem de confiabilidade devido à estocasticidade e ao risco de ótimos locais.

Metodologia
Os autores propõem um novo método, MET-DP, que integra um critério de Limiarização de Erro Mínimo (MET) modificado com uma variante específica do algoritmo de Programação Dinâmica. As contribuições centrais da metodologia são:

1. Critério MET Modificado: Os autores observam que as funções objetivo tradicionais (Otsu, Kapur) exibem um aumento monótono no valor à medida que o número de limiares aumenta, tornando-as ineficazes para a seleção automática da quantidade de limiares. Em contraste, o critério Kittler (MET) não diminui estritamente com o aumento dos limiares. Os autores modificam o critério MET para permitir que os valores de limiar sejam incluídos tanto nas classes inferiores quanto nas superiores (uma formulação "sobreposta") durante o cálculo do custo, mantendo a atribuição disjunta convencional para a segmentação final da imagem. Essa modificação cria uma paisagem de custos onde o valor mínimo pode indicar um número ótimo de limiares sem viés para contagens mais altas.

2. Variante de Programação Dinâmica: Diferentemente da abordagem de DP tradicional (Algoritmo 1) que toma $n$ como entrada e calcula uma tabela $dp[i][j]$ para o $i$-ésimo limiar na posição $j$, o algoritmo proposto (Algoritmo 2) opera recursivamente sobre intervalos $[i, j]$. Ele determina o custo mínimo para segmentar um intervalo como uma única classe ou dividindo-o em um ponto ótimo $k$. A relação de recorrência é definida como:
   $$J(i, j) = \min \left( Q(i, j), \min_{k=i+1}^{j-1} \{ Q(i, k) + J(k, j) \} \right)$$
   onde $Q$ é o custo de uma única classe e $J$ é o custo total. Essa estrutura permite que o algoritmo descubra simultaneamente o conjunto ótimo de valores de limiar e a quantidade ótima de limiares em uma única passagem.

3. Complexidade: O algoritmo proposto possui uma complexidade de tempo de $O(L^3)$ e uma complexidade de espaço de $O(L^2)$, onde $L$ é o número de níveis de intensidade (por exemplo, 256). Os autores observam que, embora a DP tradicional tenha uma complexidade de $O(n \cdot L^2)$ para um $n$ fixo, o tempo de execução do método proposto é efetivamente constante em relação ao número de limiares, pois não requer execuções iterativas para diferentes valores de $n$.

Resultados Principais
O método MET-DP foi avaliado em um conjunto de dados diversificado de 15 imagens (naturais, de satélite e médicas) e em um conjunto maior de 718 imagens para análise estatística.

• Seleção Automática de Limiares: O MET-DP determinou com sucesso contagens de limiares adequadas para vários tipos de imagem. Por exemplo, identificou corretamente 3 limiares para um histograma trimodal (Imagem 326085) onde os métodos tradicionais falharam em separar corretamente os modos. No entanto, o método exibiu sensibilidade a flutuações menores do histograma, levando a "super-limiarização" em algumas imagens médicas (por exemplo, 25 limiares para a imagem 007-Flair-60) e "sub-limiarização" em outras (por exemplo, fundindo picos distintos em Tile-8-Part-008).
• Eficiência de Tempo de Execução: Em testes comparativos onde os métodos tradicionais foram executados iterativamente para contagens de limiares de 1 a 15, o MET-DP demonstrou um tempo total de execução de CPU significativamente menor. Enquanto o tempo de execução dos métodos tradicionais cresce polinomialmente com o número de contagens testadas ($O(m^2 \cdot L^2)$), o MET-DP mantém um tempo de execução fixo dependente apenas de $L$.
• Qualidade de Segmentação:
  • SSIM: O MET-DP alcançou valores competitivos de Medida de Similaridade Estrutural (SSIM), frequentemente superando os métodos tradicionais em imagens com histogramas multimodais complexos (por exemplo, imagens naturais 147091 e 77200701).
  • PSNR: O método geralmente produziu valores de Relação Sinal-Ruído de Pico (PSNR) mais baixos em comparação com Otsu e Kapur. Os autores atribuem isso à tendência do método de separar flutuações finas, o que reduz a fidelidade ao nível de pixel em comparação com as segmentações mais suaves produzidas pelos métodos tradicionais.

Significado e Alegações
O artigo afirma que o MET-DP oferece uma estrutura adaptativa e computacionalmente eficiente para limiarização multinível automática. Seu significado principal reside na eliminação da necessidade de contagens de limiares definidas pelo usuário, um gargalo comum em pipelines de visão automatizada. Os autores enfatizam que o critério MET modificado é singularmente adequado para esta tarefa porque, ao contrário de Otsu ou Kapur, seu valor não aumenta monotonamente com o número de limiares, permitindo a identificação de um "ponto ideal" na função de custo.

Os autores concluem modestamente que, embora o MET-DP seja superior em termos de eficiência computacional e seleção automática de parâmetros, ele não supera universalmente os métodos tradicionais em termos de qualidade bruta de reconstrução de imagem (PSNR). Eles sugerem que o método é particularmente adequado para aplicações que exigem seleção automática de limiares e onde a separação de variações sutis de intensidade é crítica, enquanto os métodos tradicionais podem permanecer preferíveis para tarefas que priorizam alto PSNR ou segmentação grosseira tolerante a ruído. O artigo não propõe novas aplicações, mas posiciona o MET-DP como uma alternativa robusta para o problema específico da determinação não supervisionada da quantidade de limiares.