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

Resumen Técnico: Un Marco de Programación Dinámica para Descubrir la Cantidad y los Valores de la Umbralización de Imágenes Multinivel

Enunciado del Problema
La umbralización de imágenes multinivel es un paso fundamental de preprocesamiento en visión por computadora, a menudo planteado como un problema de agrupamiento donde las intensidades de los píxeles se separan en grupos distintos. Si bien los métodos más avanzados suelen basarse en una función objetivo (por ejemplo, Otsu, Kapur, Kittler) y una estrategia de búsqueda para encontrar umbrales óptimos, persiste una limitación crítica: la mayoría de los métodos requieren que el usuario especifique manualmente el número de umbrales ($n$) como entrada. Determinar el $n$ apropiado no es trivial, ya que las métricas de similitud como SSIM y PSNR favorecen inherentemente conteos más altos de umbrales para maximizar la fidelidad de la imagen, lo que las hace inadecuadas para seleccionar automáticamente el $n$ óptimo. Además, aunque las estrategias de búsqueda exactas como la Programación Dinámica (DP) garantizan soluciones óptimas para un $n$ fijo, sufren un crecimiento exponencial del tiempo de ejecución cuando el usuario intenta buscar el mejor $n$ iterando a través de múltiples valores candidatos. Por el contrario, los métodos metaheurísticos aproximados ofrecen velocidad pero carecen de fiabilidad debido a la estocasticidad y al riesgo de óptimos locales.

Metodología
Los autores proponen un nuevo método, MET-DP, que integra un criterio de Umbralización de Error Mínimo (MET) modificado con una variante específica del algoritmo de Programación Dinámica. Las contribuciones centrales de la metodología son:

1. Criterio MET Modificado: Los autores observan que las funciones objetivo tradicionales (Otsu, Kapur) exhiben un aumento monótono en el valor a medida que aumenta el número de umbrales, volviéndolas ineficaces para la selección automática de la cantidad de umbrales. En contraste, el criterio de Kittler (MET) no disminuye estrictamente con el aumento de umbrales. Los autores modifican el criterio MET para permitir que los valores umbral se incluyan tanto en las clases inferiores como en las superiores (una formulación "superpuesta") durante el cálculo del costo, manteniendo la asignación disjunta convencional para la segmentación final de la imagen. Esta modificación crea un paisaje de costos donde el valor mínimo puede indicar un número óptimo de umbrales sin sesgo hacia conteos más altos.

2. Variante de Programación Dinámica: A diferencia del enfoque DP tradicional (Algoritmo 1) que toma $n$ como entrada y calcula una tabla $dp[i][j]$ para el $i$-ésimo umbral en la posición $j$, el algoritmo propuesto (Algoritmo 2) opera recursivamente sobre intervalos $[i, j]$. Determina el costo mínimo para segmentar un intervalo ya sea como una sola clase o dividiéndolo en un punto óptimo $k$. La relación de recurrencia se define como:
   $$J(i, j) = \min \left( Q(i, j), \min_{k=i+1}^{j-1} \{ Q(i, k) + J(k, j) \} \right)$$
   donde $Q$ es el costo de una sola clase y $J$ es el costo total. Esta estructura permite que el algoritmo descubra simultáneamente el conjunto óptimo de valores umbral y la cantidad óptima de umbrales en un solo pase.

3. Complejidad: El algoritmo propuesto tiene una complejidad temporal de $O(L^3)$ y una complejidad espacial de $O(L^2)$, donde $L$ es el número de niveles de intensidad (por ejemplo, 256). Los autores señalan que, si bien la DP tradicional tiene una complejidad de $O(n \cdot L^2)$ para un $n$ fijo, el tiempo de ejecución del método propuesto es efectivamente constante con respecto al número de umbrales, ya que no requiere ejecuciones iterativas para diferentes valores de $n$.

Resultados Clave
El método MET-DP fue evaluado en un conjunto de datos diverso de 15 imágenes (naturales, satelitales y médicas) y un conjunto más grande de 718 imágenes para el análisis estadístico.

• Selección Automática de Umbrales: MET-DP determinó con éxito conteos de umbrales adecuados para varios tipos de imágenes. Por ejemplo, identificó correctamente 3 umbrales para un histograma trimodal (Imagen 326085) donde los métodos tradicionales no lograron separar los modos correctamente. Sin embargo, el método mostró sensibilidad a fluctuaciones menores del histograma, lo que llevó a una "sobre-umbralización" en algunas imágenes médicas (por ejemplo, 25 umbrales para la imagen 007-Flair-60) y una "sub-umbralización" en otras (por ejemplo, fusionando picos distintos en Tile-8-Part-008).
• Eficiencia de Tiempo de Ejecución: En pruebas comparativas donde los métodos tradicionales se ejecutaron iterativamente para conteos de umbrales de 1 a 15, MET-DP demostró un tiempo total de ejecución de CPU significativamente menor. Mientras que el tiempo de ejecución de los métodos tradicionales crece polinomialmente con el número de conteos probados ($O(m^2 \cdot L^2)$), MET-DP mantiene un tiempo de ejecución fijo que depende únicamente de $L$.
• Calidad de Segmentación:
  • SSIM: MET-DP logró valores competitivos de la Medida de Similitud Estructural (SSIM), superando a menudo a los métodos tradicionales en imágenes con histogramas multimodales complejos (por ejemplo, imágenes naturales 147091 y 77200701).
  • PSNR: El método generalmente produjo valores de Relación Señal-Ruido de Pico (PSNR) más bajos en comparación con Otsu y Kapur. Los autores atribuyen esto a la tendencia del método a separar fluctuaciones finas, lo que reduce la fidelidad a nivel de píxel en comparación con las segmentaciones más suaves producidas por los métodos tradicionales.

Significado y Afirmaciones
El artículo afirma que MET-DP ofrece un marco computacionalmente eficiente y adaptativo para la umbralización multinivel automática. Su principal significado radica en eliminar la necesidad de conteos de umbrales definidos por el usuario, un cuello de botella común en las pipelines de visión automatizada. Los autores enfatizan que el criterio MET modificado es particularmente adecuado para esta tarea porque, a diferencia de Otsu o Kapur, su valor no aumenta monótonamente con el número de umbrales, lo que permite la identificación de un "punto óptimo" en la función de costo.

Los autores concluyen modestamente que, si bien MET-DP es superior en términos de eficiencia computacional y selección automática de parámetros, no supera universalmente a los métodos tradicionales en términos de calidad de reconstrucción de imagen cruda (PSNR). Sugieren que el método es particularmente adecuado para aplicaciones que requieren selección automática de umbrales y donde separar variaciones sutiles de intensidad es crítico, mientras que los métodos tradicionales pueden seguir siendo preferibles para tareas que priorizan un alto PSNR o una segmentación gruesa tolerante al ruido. El artículo no propone nuevas aplicaciones, sino que posiciona a MET-DP como una alternativa robusta para el problema específico de la determinación no supervisada del conteo de umbrales.