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

Technische Samenvatting: Een Dynamisch-Programmeringskader voor het Ontdekken van Aantal en Waarden van Meervoudige Beelddemping

Probleemstelling
Meervoudige beelddemping is een fundamentele voorverwerkingsstap in computerzicht, vaak geformuleerd als een clusteringprobleem waarbij pixelintensiteiten worden gescheiden in distincte groepen. Hoewel state-of-the-art methoden doorgaans vertrouwen op een objectieve functie (bijv. Otsu, Kapur, Kittler) en een zoekstrategie om optimale drempels te vinden, blijft een kritieke beperking bestaan: de meeste methoden vereisen dat de gebruiker het aantal drempels ($n$) handmatig specificeert als invoer. Het bepalen van het geschikte $n$ is niet triviaal, aangezien vergelijkingsmaten zoals SSIM en PSNR inherent de voorkeur geven aan hogere aantallen drempels om beeldtrouw te maximaliseren, waardoor ze ongeschikt zijn voor het automatisch selecteren van de optimale $n$. Bovendien, terwijl exacte zoekstrategieën zoals Dynamische Programmering (DP) optimale oplossingen garanderen voor een vaste $n$, lijden ze onder exponentiële groei van de runtime wanneer de gebruiker probeert de beste $n$ te vinden door te itereren door meerdere kandidaatwaarden. Omgekeerd bieden benaderende metaheuristische methoden snelheid, maar missen ze betrouwbaarheid door stochasticiteit en het risico op lokale optimums.

Methodologie
De auteurs stellen een nieuwe methode voor, MET-DP, die een gewijzigd Minimum Error Thresholding (MET)-criterium integreert met een specifieke variant van het Dynamisch-Programmeringsalgoritme. De kernbijdragen van de methodologie zijn:

1. Gewijzigd MET-criterium: De auteurs observeren dat traditionele objectieve functies (Otsu, Kapur) een monotoon toenemende waarde vertonen naarmate het aantal drempels toeneemt, waardoor ze inefficiënt zijn voor automatische selectie van het drempelaantal. Daarentegen neemt het Kittler (MET)-criterium niet strikt af met toenemende drempels. De auteurs wijzigen het MET-criterium zodat drempelwaarden tijdens de kostenberekening in zowel de lagere als de hogere klassen kunnen worden opgenomen (een "overlappende" formulering), terwijl de conventionele disjuncte toewijzing voor de uiteindelijke beeldsegmentatie behouden blijft. Deze wijziging creëert een kostenlandschap waarbij de minimale waarde een optimaal aantal drempels kan aangeven zonder bias naar hogere aantallen.

2. Variant van Dynamische Programmering: In tegenstelling tot de traditionele DP-aanpak (Algoritme 1), die $n$ als invoer neemt en een tabel $dp[i][j]$ berekent voor de $i$-de drempel op positie $j$, werkt het voorgestelde algoritme (Algoritme 2) recursief op intervallen $[i, j]$. Het bepaalt de minimale kosten om een interval te segmenteren als een enkele klasse of door het te splitsen op een optimaal punt $k$. De recurrente relatie wordt gedefinieerd als:
   $$J(i, j) = \min \left( Q(i, j), \min_{k=i+1}^{j-1} \{ Q(i, k) + J(k, j) \} \right)$$
   waarbij $Q$ de kosten van een enkele klasse zijn en $J$ de totale kosten. Deze structuur stelt het algoritme in staat om in één doorgang zowel de optimale set drempelwaarden als het optimale aantal drempels te ontdekken.

3. Complexiteit: Het voorgestelde algoritme heeft een tijdscomplexiteit van $O(L^3)$ en een ruimtecomplexiteit van $O(L^2)$, waarbij $L$ het aantal intensiteitsniveaus is (bijv. 256). De auteurs merken op dat, terwijl traditionele DP een complexiteit heeft van $O(n \cdot L^2)$ voor een vaste $n$, de runtime van de voorgestelde methode effectief constant is ten opzichte van het aantal drempels, omdat het geen iteratieve runs vereist voor verschillende $n$-waarden.

Belangrijkste Resultaten
De MET-DP-methode werd geëvalueerd op een divers dataset van 15 afbeeldingen (natuurlijk, satelliet en medisch) en een grotere set van 718 afbeeldingen voor statistische analyse.

• Automatische Drempelselectie: MET-DP bepaalde succesvol geschikte drempelaantallen voor verschillende beeldtypes. Bijvoorbeeld, het identificeerde correct 3 drempels voor een trimodaal histogram (Afbeelding 326085) waar traditionele methoden faalden om de modi correct te scheiden. De methode vertoonde echter gevoeligheid voor kleine histogramfluctuaties, wat leidde tot "over-demping" in sommige medische afbeeldingen (bijv. 25 drempels voor afbeelding 007-Flair-60) en "onder-demping" in andere (bijv. het samenvoegen van distincte pieken in Tile-8-Part-008).
• Runtime-efficiëntie: In vergelijkende tests waarbij traditionele methoden iteratief werden uitgevoerd voor drempelaantallen van 1 tot 15, vertoonde MET-DP een aanzienlijk lagere totale CPU-runtime. Waar de runtime van traditionele methoden polynomiaal groeit met het aantal geteste aantallen ($O(m^2 \cdot L^2)$), behoudt MET-DP een vaste runtime die uitsluitend afhankelijk is van $L$.
• Segmentatiekwaliteit:
  • SSIM: MET-DP behaalde concurrerende Structural Similarity Index Measure (SSIM)-waarden, en presteerde vaak beter dan traditionele methoden op afbeeldingen met complexe multimodale histogrammen (bijv. natuurlijke afbeeldingen 147091 en 77200701).
  • PSNR: De methode produceerde over het algemeen lagere Peak Signal-to-Noise Ratio (PSNR)-waarden in vergelijking met Otsu en Kapur. De auteurs schrijven dit toe aan de neiging van de methode om fijne fluctuaties te scheiden, wat de pixelniveau-trouw verlaagt in vergelijking met de gladdere segmentaties die door traditionele methoden worden geproduceerd.

Betekenis en Claims
Het artikel claimt dat MET-DP een computatie-efficiënt, adaptief kader biedt voor automatische meervoudige beelddemping. De primaire betekenis ligt in het elimineren van de behoefte aan door de gebruiker gedefinieerde drempelaantallen, een veelvoorkomende bottleneck in geautomatiseerde visiepijplijnen. De auteurs benadrukken dat het gewijzigde MET-criterium uniek geschikt is voor deze taak, omdat, in tegenstelling tot Otsu of Kapur, de waarde niet monotoon toeneemt met het aantal drempels, waardoor identificatie van een "sweet spot" in de kostenfunctie mogelijk is.

De auteurs concluderen bescheiden dat, hoewel MET-DP superieur is wat betreft computatie-efficiëntie en automatische parameterselectie, het niet universeel traditionele methoden overtreft wat betreft ruwe beeldreconstruktiekwaliteit (PSNR). Zij suggereren dat de methode bijzonder goed geschikt is voor toepassingen die automatische drempelselectie vereisen en waarbij het scheiden van subtiele intensiteitsvariaties kritiek is, terwijl traditionele methoden mogelijk de voorkeur blijven genieten voor taken die prioriteit geven aan hoge PSNR of ruis-tolerante, grove segmentatie. Het artikel stelt geen nieuwe toepassingen voor, maar positioneert MET-DP als een robuust alternatief voor het specifieke probleem van ongesuperviseerde drempelaantalsbepaling.