Lägsta spännande trädbaserad segmentering
Bildsegmentering strävar efter att dela upp en digital bild i områden med pixlar med liknande egenskaper, t.ex. homogenitet. Regionrepresentationen på högre nivå förenklar bildanalysuppgifter som att räkna objekt eller detektera förändringar, eftersom regionattribut (t.ex. genomsnittlig intensitet eller form) lättare kan jämföras än råa pixlar.
Motivation för grafbaserade metoder
För att påskynda segmenteringen av stora bilder kunde arbetet delas upp på flera processorer . Ett sätt att åstadkomma detta är att dela upp bilder i brickor som bearbetas oberoende. Däremot kan regioner som går över en brickkant delas upp eller gå förlorade om fragmenten inte uppfyller segmenteringsalgoritmens minimistorlekskrav. En trivial lösning innebär överlappande brickor, det vill säga att låta varje processor överväga ytterligare pixlar runt sin bricks kant. Tyvärr ökar detta beräkningsbelastningen, eftersom processorerna på båda sidor om en rutgräns utför redundant arbete. Dessutom är det garanterat att endast föremål som är mindre än kakelöverlappningen kommer att bevaras, vilket innebär att långa föremål som floder i flygbilder fortfarande kommer att delas. I vissa fall kan de oberoende brickornas resultat smältas samman för att approximera de verkliga resultaten. Ett alternativ finns i form av grafbaserade segmenteringsmetoder. Anslutningsinformationen som är inneboende i grafer gör det möjligt att utföra oberoende arbete på delar av originalbilden och återansluta dem för att ge ett exakt resultat som om bearbetning hade skett globalt.
Från bilder till grafer
Möjligheten att sammanfoga oberoende underbilder motiverar att lägga till anslutningsinformation till pixlarna. Detta kan ses som en graf, vars noder är pixlar och kanter representerar kopplingar mellan pixlar. En enkel och jämförelsevis utrymmeseffektiv variant av detta är ett rutnätsdiagram , där varje pixel är kopplad till sina grannar i de fyra kardinalriktningarna . Eftersom pixelgrannskapsrelationen är symmetrisk, är den resulterande grafen oriktad och endast halva dess kanter (t.ex. varje pixels östra och södra granne) behöver lagras. Det sista steget kräver kodning av pixellikhetsinformation i kantvikter, så att originalbilden inte längre behövs. I det enklaste fallet beräknas kantvikter som skillnaden mellan pixelintensiteter.
Algoritmer för segmentering av minsta spännträd
Ett minimum spanningsträd (MST) är en minimivikt, cykelfri delmängd av en grafs kanter så att alla noder är anslutna. 2004 introducerade Felzenszwalb en segmenteringsmetod baserad på Kruskals MST-algoritm . Kanter betraktas i ökande viktordning; deras ändpunktspixlar slås samman till en region om detta inte orsakar en cykel i grafen, och om pixlarna är "lika" de befintliga regionernas pixlar. Detektering av cykler är möjlig i nästan konstant tid med hjälp av en disjunkt-uppsättning datastruktur . Pixellikhet bedöms av en heuristik, som jämför vikten med en tröskel per segment. Algoritmen matar ut flera disjunkta MST:er, dvs en skog; varje träd motsvarar ett segment. Algoritmens komplexitet är kvasilinjär eftersom sorteringskanter är möjliga i linjär tid via räknesortering .
2009, Wassenberg et al. utvecklat en algoritm som beräknar flera oberoende skogar med minsta spännvidd och sedan syr ihop dem. Detta möjliggör parallell bearbetning utan att dela objekt på brickkanter. Istället för en fast vikttröskel används en initial märkning av anslutna komponenter för att uppskatta en nedre gräns för tröskeln, vilket kan minska både över- och undersegmentering. Mätningar visar att implementeringen överträffar Felzenszwalbs sekventiella algoritm med en storleksordning.
Under 2017 använde Saglam och Baykan Prims sekventiella representation av minsta spännträd och föreslog ett nytt skärkriterium för bildsegmentering. De konstruerar MST med Prims MST-algoritm med hjälp av Fibonacci Heap-datastrukturen. Metoden når en viktig framgång på testbilderna i snabb exekveringstid.