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

Sintesi Tecnica: Un Framework di Programmazione Dinamica per la Scoperta del Numero e dei Valori della Soglia Multilivello nelle Immagini

Enunciato del Problema
La soglia multilivello nelle immagini è un passo fondamentale di pre-elaborazione nella visione artificiale, spesso inquadrato come un problema di clustering in cui le intensità dei pixel vengono separate in gruppi distinti. Sebbene i metodi all'avanguardia facciano tipicamente affidamento su una funzione obiettivo (ad esempio Otsu, Kapur, Kittler) e su una strategia di ricerca per trovare le soglie ottimali, persiste una limitazione critica: la maggior parte dei metodi richiede all'utente di specificare manualmente il numero di soglie ($n$) come input. Determinare l'appropriatezza di $n$ non è banale, poiché metriche di similarità come SSIM e PSNR favoriscono intrinsecamente un numero più elevato di soglie per massimizzare la fedeltà dell'immagine, rendendole inadatte alla selezione automatica del $n$ ottimale. Inoltre, mentre strategie di ricerca esatte come la Programmazione Dinamica (DP) garantiscono soluzioni ottimali per un $n$ fisso, soffrono di una crescita esponenziale del tempo di esecuzione quando l'utente tenta di cercare il miglior $n$ iterando attraverso molteplici valori candidati. Al contrario, i metodi meta-euristici approssimati offrono velocità ma mancano di affidabilità a causa della stocasticità e del rischio di ottimi locali.

Metodologia
Gli autori propongono un nuovo metodo, MET-DP, che integra un criterio MET (Minimum Error Thresholding) modificato con una variante specifica dell'algoritmo di Programmazione Dinamica. I contributi fondamentali della metodologia sono:

1. Criterio MET Modificato: Gli autori osservano che le funzioni obiettivo tradizionali (Otsu, Kapur) mostrano un aumento monotono del valore all'aumentare del numero di soglie, rendendole inefficaci per la selezione automatica del numero di soglie. Al contrario, il criterio Kittler (MET) non diminuisce strettamente all'aumentare delle soglie. Gli autori modificano il criterio MET per permettere ai valori di soglia di essere inclusi sia nella classe inferiore che in quella superiore (una formulazione "sovrapposta") durante il calcolo del costo, mantenendo al contempo l'assegnazione disgiunta convenzionale per la segmentazione finale dell'immagine. Questa modifica crea un paesaggio di costi in cui il valore minimo può indicare un numero ottimale di soglie senza un pregiudizio verso conteggi più elevati.

2. Variante di Programmazione Dinamica: A differenza dell'approccio DP tradizionale (Algoritmo 1) che prende $n$ come input e calcola una tabella $dp[i][j]$ per la $i$-esima soglia alla posizione $j$, l'algoritmo proposto (Algoritmo 2) opera ricorsivamente sugli intervalli $[i, j]$. Determina il costo minimo per segmentare un intervallo sia come una singola classe che dividendo lo stesso in un punto ottimale $k$. La relazione di ricorrenza è definita come:
   $$J(i, j) = \min \left( Q(i, j), \min_{k=i+1}^{j-1} \{ Q(i, k) + J(k, j) \} \right)$$
   dove $Q$ è il costo di una singola classe e $J$ è il costo totale. Questa struttura permette all'algoritmo di scoprire simultaneamente l'insieme ottimale dei valori di soglia e il numero ottimale di soglie in un'unica passata.

3. Complessità: L'algoritmo proposto ha una complessità temporale di $O(L^3)$ e una complessità spaziale di $O(L^2)$, dove $L$ è il numero di livelli di intensità (ad esempio 256). Gli autori notano che, mentre la DP tradizionale ha una complessità di $O(n \cdot L^2)$ per un $n$ fisso, il tempo di esecuzione del metodo proposto è effettivamente costante rispetto al numero di soglie, poiché non richiede esecuzioni iterative per diversi valori di $n$.

Risultati Chiave
Il metodo MET-DP è stato valutato su un dataset diversificato di 15 immagini (naturali, satellitari e mediche) e su un insieme più ampio di 718 immagini per l'analisi statistica.

• Selezione Automatica delle Soglie: MET-DP ha determinato con successo conteggi di soglie adatti per vari tipi di immagini. Ad esempio, ha correttamente identificato 3 soglie per un istogramma trimodale (Immagine 326085) dove i metodi tradizionali non sono riusciti a separare correttamente le modalità. Tuttavia, il metodo ha mostrato sensibilità a lievi fluttuazioni dell'istogramma, portando a una "soglia eccessiva" in alcune immagini mediche (ad esempio, 25 soglie per l'immagine 007-Flair-60) e a una "soglia insufficiente" in altre (ad esempio, fondendo picchi distinti in Tile-8-Part-008).
• Efficienza del Tempo di Esecuzione: Nei test comparativi in cui i metodi tradizionali sono stati eseguiti iterativamente per conteggi di soglie da 1 a 15, MET-DP ha dimostrato un tempo totale di esecuzione della CPU significativamente inferiore. Mentre il tempo di esecuzione dei metodi tradizionali cresce polinomialmente con il numero di conteggi testati ($O(m^2 \cdot L^2)$), MET-DP mantiene un tempo di esecuzione fisso dipendente solo da $L$.
• Qualità della Segmentazione:
  • SSIM: MET-DP ha raggiunto valori competitivi per la Misura dell'Indice di Similarità Strutturale (SSIM), superando spesso i metodi tradizionali su immagini con istogrammi multimodali complessi (ad esempio, immagini naturali 147091 e 77200701).
  • PSNR: Il metodo ha generalmente prodotto valori di Rapporto Segnale-Rumore di Picco (PSNR) più bassi rispetto a Otsu e Kapur. Gli autori attribuiscono ciò alla tendenza del metodo a separare fluttuazioni fini, il che riduce la fedeltà a livello di pixel rispetto alle segmentazioni più lisce prodotte dai metodi tradizionali.

Significato e Affermazioni
Il documento afferma che MET-DP offre un framework adattivo ed efficiente dal punto di vista computazionale per la soglia multilivello automatica. Il suo significato principale risiede nell'eliminare la necessità di conteggi di soglie definiti dall'utente, un collo di bottiglia comune nelle pipeline di visione automatizzate. Gli autori sottolineano che il criterio MET modificato è particolarmente adatto a questo compito perché, a differenza di Otsu o Kapur, il suo valore non aumenta monotonicamente con il numero di soglie, permettendo l'identificazione di un "punto dolce" nella funzione di costo.

Gli autori concludono con modestia che, sebbene MET-DP sia superiore in termini di efficienza computazionale e selezione automatica dei parametri, non supera universalmente i metodi tradizionali in termini di qualità di ricostruzione grezza dell'immagine (PSNR). Suggeriscono che il metodo è particolarmente adatto per applicazioni che richiedono la selezione automatica delle soglie e in cui la separazione di sottili variazioni di intensità è critica, mentre i metodi tradizionali possono rimanere preferibili per compiti che danno priorità all'alto PSNR o a una segmentazione grossolana e tollerante al rumore. Il documento non propone nuove applicazioni, ma posiziona MET-DP come un'alternativa robusta per il problema specifico della determinazione non supervisionata del numero di soglie.