Bildsegmentering

Modell av ett segmenterat vänster mänskligt lårben . Den visar den yttre ytan (röd), ytan mellan kompakt ben och svampigt ben (grön) och ytan av benmärgen (blå).

Inom digital bildbehandling och datorseende är bildsegmentering processen att dela upp en digital bild i flera bildsegment , även kända som bildregioner eller bildobjekt ( uppsättningar av pixlar ). Målet med segmentering är att förenkla och/eller förändra representationen av en bild till något som är mer meningsfullt och lättare att analysera. Bildsegmentering används vanligtvis för att lokalisera objekt och gränser (linjer, kurvor, etc.) i bilder. Mer exakt är bildsegmentering processen att tilldela en etikett till varje pixel i en bild så att pixlar med samma etikett delar vissa egenskaper.

Resultatet av bildsegmentering är en uppsättning segment som samlat täcker hela bilden, eller en uppsättning konturer som extraherats från bilden (se kantdetektering ) . Var och en av pixlarna i en region är lika med avseende på någon karakteristisk eller beräknad egenskap, såsom färg , intensitet eller struktur . Närliggande regioner har signifikant olika färg med avseende på samma egenskap(er). När de appliceras på en hög med bilder, typiskt för medicinsk bildbehandling, kan de resulterande konturerna efter bildsegmentering användas för att skapa 3D-rekonstruktioner med hjälp av interpolationsalgoritmer som marschkuber .

Ansökningar

Volymsegmentering av en 3D-renderad CT-skanning av bröstkorgen : Den främre bröstväggen, luftvägarna och lungkärlen framför lungroten har tagits bort digitalt för att visualisera bröstkorgsinnehållet: – blått : lungartärerna – röda : lungvener (och även bukväggen ) – gult : mediastinum – violett : diafragman

Några av de praktiska tillämpningarna av bildsegmentering är:

Innehållsbaserad bildhämtning
Maskinseende
Medicinsk avbildning , inklusive volymrenderade bilder från datortomografi och magnetisk resonanstomografi .
- Lokalisera tumörer och andra patologier
- Mät vävnadsvolymer
- Diagnostik, studie av anatomisk struktur
- Operationsplanering
- Virtuell kirurgi simulering
- Navigering inom kirurgi
Objektdetektion
- Detektering av fotgängare
- Ansiktsigenkänning
- Bromsljusdetektering
- Lokalisera objekt i satellitbilder (vägar, skogar, grödor, etc.)
Erkännande uppgifter
Trafikledningssystem
Videoövervakning
Samsegmentering av videoobjekt och handlingslokalisering

Flera allmänna algoritmer och tekniker har utvecklats för bildsegmentering. För att vara användbara måste dessa tekniker vanligtvis kombineras med en domäns specifika kunskap för att effektivt lösa domänens segmenteringsproblem.

Klasser av segmenteringstekniker

Det finns två klasser av segmenteringstekniker.

Klassisk datorseende närmar sig
AI-baserade tekniker

Grupper av bildsegmentering

Semantisk segmentering är ett tillvägagångssätt som detekterar, för varje pixel, tillhörande klass av objektet. Till exempel när alla personer i en figur är segmenterade som ett objekt och bakgrund som ett objekt.
Instanssegmentering är ett tillvägagångssätt som identifierar, för varje pixel, en tillhörande instans av objektet. Den upptäcker varje distinkt föremål av intresse i bilden. Till exempel när varje person i en figur är segmenterad som ett individuellt objekt.
Panoptisk segmentering kombinerar semantisk segmentering och instanssegmentering. Precis som semantisk segmentering är panoptisk segmentering ett tillvägagångssätt som identifierar, för varje pixel, tillhörande klass. Till skillnad från semantisk segmentering särskiljer panoptisk segmentering olika instanser av samma klass.

Tröskelvärde

Den enklaste metoden för bildsegmentering kallas tröskelmetoden . Denna metod är baserad på en klippnivå (eller ett tröskelvärde) för att förvandla en gråskalebild till en binär bild.

Nyckeln med denna metod är att välja tröskelvärdet (eller värden när flera nivåer är valda). Flera populära metoder används inom industrin, inklusive den maximala entropimetoden, balanserad histogramtröskelvärde , Otsus metod (maximal varians) och k-means klustring .

Nyligen har metoder utvecklats för tröskelvärde för datortomografi (CT) bilder. Nyckeltanken är att, till skillnad från Otsus metod, härleds tröskelvärdena från röntgenbilderna istället för den (rekonstruerade) bilden.

Nya metoder föreslog användning av flerdimensionella luddiga regelbaserade icke-linjära trösklar. I dessa verk baseras beslutet om varje pixels medlemskap i ett segment på flerdimensionella regler härledda från luddig logik och evolutionära algoritmer baserade på bildbelysningsmiljö och applikation.

Klustringsmetoder

Källbild.

Bild efter körning av k - betyder med k = 16 . Observera att en vanlig teknik för att förbättra prestanda för stora bilder är att nedsampla bilden, beräkna klustren och sedan tilldela om värdena till den större bilden om det behövs.

K -means-algoritmen är en iterativ teknik som används för att dela upp en bild i K -kluster. Den grundläggande algoritmen är

Välj K- klustercentra, antingen slumpmässigt eller baserat på någon heuristisk metod, till exempel K-means++
Tilldela varje pixel i bilden till klustret som minimerar avståndet mellan pixeln och klustrets mitt
Beräkna om klustrets centra genom att beräkna ett genomsnitt av alla pixlar i klustret
Upprepa steg 2 och 3 tills konvergens uppnås (dvs inga pixlar byter kluster)

I det här fallet är avståndet den kvadratiska eller absoluta skillnaden mellan en pixel och ett klustercentrum. Skillnaden baseras vanligtvis på pixelfärg , intensitet , struktur och plats, eller en viktad kombination av dessa faktorer. K kan väljas manuellt, slumpmässigt eller med en heuristik . Denna algoritm kommer garanterat att konvergera, men den kanske inte ger den optimala lösningen. Kvaliteten på lösningen beror på den initiala uppsättningen av kluster och värdet på K .

Mean Shift -algoritmen är en teknik som används för att partitionera en bild i ett okänt apriori nr. av kluster. Detta har fördelen av att inte behöva börja med en första gissning av en sådan parameter, vilket gör det till en bättre generell lösning för mer olika fall.

Rörelse och interaktiv segmentering

Rörelsebaserad segmentering är en teknik som förlitar sig på rörelse i bilden för att utföra segmentering.

Tanken är enkel: titta på skillnaderna mellan ett par bilder. Förutsatt att objektet av intresse rör sig, blir skillnaden exakt det objektet.

För att förbättra denna idé, Kenney et al. föreslagen interaktiv segmentering [2] . De använder en robot för att peta in föremål för att generera den rörelsesignal som krävs för rörelsebaserad segmentering.

Interaktiv segmentering följer det interaktiva perceptionsramverket som föreslagits av Dov Katz [3] och Oliver Brock [4] .

En annan teknik som är baserad på rörelse är stel rörelsesegmentering .

Kompressionsbaserade metoder

Kompressionsbaserade metoder postulerar att den optimala segmenteringen är den som minimerar, över alla möjliga segmentering, kodningslängden på datan. Kopplingen mellan dessa två begrepp är att segmentering försöker hitta mönster i en bild och vilken regelbundenhet som helst i bilden kan användas för att komprimera den. Metoden beskriver varje segment genom dess struktur och gränsform. Var och en av dessa komponenter modelleras av en sannolikhetsfördelningsfunktion och dess kodningslängd beräknas enligt följande:

Gränskodningen utnyttjar det faktum att regioner i naturliga bilder tenderar att ha en jämn kontur. Denna prior används av Huffman-kodning för att koda skillnadskedjekoden för konturerna i en bild. Således, ju jämnare en gräns är, desto kortare kodningslängd får den.
Textur kodas genom förlustkompression på ett sätt som liknar principen om minimum beskrivningslängd (MDL), men här uppskattas längden på data som ges av modellen med antalet sampel gånger modellens entropi . Texturen i varje region modelleras av en multivariat normalfördelning vars entropi har ett slutet formuttryck. En intressant egenskap hos denna modell är att den uppskattade entropin begränsar den sanna entropin för data från ovan. Detta beror på att bland alla distributioner med ett givet medelvärde och kovarians har normalfördelning den största entropin. Den sanna kodningslängden kan alltså inte vara mer än vad algoritmen försöker minimera.

För varje given segmentering av en bild, ger detta schema antalet bitar som krävs för att koda den bilden baserat på den givna segmenteringen. Således, bland alla möjliga segmentering av en bild, är målet att hitta den segmentering som ger den kortaste kodningslängden. Detta kan uppnås genom en enkel agglomerativ klustringsmetod. Förvrängningen i den förlustgivande komprimeringen bestämmer segmenteringens grovhet och dess optimala värde kan skilja sig åt för varje bild. Denna parameter kan uppskattas heuristiskt från kontrasten av texturer i en bild. Till exempel när texturerna i en bild är likartade, som i kamouflagebilder, krävs starkare känslighet och därmed lägre kvantisering.

Histogrambaserade metoder

Histogrambaserade metoder är mycket effektiva jämfört med andra bildsegmenteringsmetoder eftersom de vanligtvis bara kräver en passage genom pixlarna . I denna teknik beräknas ett histogram från alla pixlar i bilden, och topparna och dalarna i histogrammet används för att lokalisera klustren i bilden. Färg eller intensitet kan användas som mått.

En förfining av denna teknik är att rekursivt tillämpa histogramsökningsmetoden på kluster i bilden för att dela upp dem i mindre kluster. Denna operation upprepas med mindre och mindre kluster tills inga fler kluster bildas.

En nackdel med histogramsökningsmetoden är att det kan vara svårt att identifiera signifikanta toppar och dalar i bilden.

Histogrambaserade tillvägagångssätt kan också snabbt anpassas för att tillämpas på flera bildrutor, samtidigt som de bibehåller effektiviteten i ett pass. Histogrammet kan göras på flera sätt när flera bildrutor beaktas. Samma tillvägagångssätt som används med en bildruta kan tillämpas på flera, och efter att resultaten har slagits samman är det mer sannolikt att toppar och dalar som tidigare var svåra att identifiera är urskiljbara. Histogrammet kan också appliceras per pixel där den resulterande informationen används för att bestämma den vanligaste färgen för pixelplatsen. Detta tillvägagångssätt segmenterar baserat på aktiva objekt och en statisk miljö, vilket resulterar i en annan typ av segmentering som är användbar vid videospårning .

Kantdetektering

Kantdetektering är ett välutvecklat område i sig inom bildbehandling. Regiongränser och kanter är nära besläktade, eftersom det ofta sker en kraftig justering av intensiteten vid regiongränserna. Kantdetekteringstekniker har därför använts som basen för en annan segmenteringsteknik.

De kanter som identifieras av kantdetektering är ofta bortkopplade. För att segmentera ett objekt från en bild behöver man dock slutna regiongränser. De önskade kanterna är gränserna mellan sådana objekt eller rumsliga taxoner.

Spatial-taxoner är informationsgranuler, bestående av ett skarpt pixelområde, stationerat på abstraktionsnivåer inom en hierarkisk kapslad scenarkitektur. De liknar den gestaltpsykologiska beteckningen figur-grund, men utvidgas till att omfatta förgrund, objektgrupper, objekt och framträdande objektdelar. Kantdetekteringsmetoder kan tillämpas på den rumsliga taxonregionen, på samma sätt som de skulle tillämpas på en siluett. Denna metod är särskilt användbar när den frånkopplade kanten är en del av en illusorisk kontur

Segmenteringsmetoder kan också tillämpas på kanter erhållna från kantdetektorer. Lindeberg och Li utvecklade en integrerad metod som segmenterar kanter till raka och krökta kantsegment för delarbaserad objektigenkänning, baserat på ett kriterium för minsta beskrivningslängd (M DL ) som optimerades med en _split -and-merge-liknande metod med kandidatbrytpunkter erhållna från komplementära kopplingssignaler för att erhålla mer sannolika punkter där man kan överväga partitioner i olika segment.

Dubbel klustringsmetod

Denna metod är en kombination av tre egenskaper hos bilden: uppdelning av bilden baserad på histogramanalys kontrolleras av hög kompakthet hos klustren (objekt) och höga gradienter av deras gränser. För detta ändamål måste två utrymmen införas: ett utrymme är det endimensionella histogrammet för ljusstyrkan H = H ( B ); det andra utrymmet är det dubbla 3-dimensionella utrymmet för själva originalbilden B = B ( x , y ). Det första utrymmet gör det möjligt att mäta hur kompakt ljusstyrkan i bilden är fördelad genom att beräkna en minimal klustring kmin. Tröskelljusstyrka T som motsvarar kmin definierar den binära (svart-vita) bilden – bitmapp b = φ ( x , y ), där φ ( x , y ) = 0, om B ( x , y ) < T , och φ ( x , y ) = 1, om B ( x , y ) ≥ T . Bitmappen b är ett objekt i dubbelrum. På den bitmappen måste ett mått definieras som återspeglar hur kompakta distribuerade svarta (eller vita) pixlar är. Så målet är att hitta föremål med bra gränser. För alla T måste måttet M _DC = G /( k × L ) beräknas (där k är skillnaden i ljusstyrka mellan objektet och bakgrunden, L är längden på alla gränser och G är medelgradienten på gränserna). Maximum of MDC definierar segmenteringen.

Regionodlingsmetoder

Regionodlande metoder bygger huvudsakligen på antagandet att de angränsande pixlarna inom en region har liknande värden. Den vanliga proceduren är att jämföra en pixel med dess grannar. Om ett likhetskriterium är uppfyllt kan pixeln ställas in att tillhöra samma kluster som en eller flera av dess grannar. Valet av likhetskriteriet är betydande och resultaten påverkas av brus i alla fall.

Metoden för Statistical Region Merging (SRM) börjar med att bygga grafen över pixlar med 4-kopplingar med kanter viktade med det absoluta värdet av intensitetsskillnaden. Initialt bildar varje pixel ett enda pixelområde. SRM sorterar sedan dessa kanter i en prioritetskö och bestämmer om de nuvarande regionerna som tillhör kantpixlarna ska slås samman eller inte med hjälp av ett statistiskt predikat.

En regionsodlingsmetod är seeded region-odlingsmetoden. Denna metod tar en uppsättning frön som indata tillsammans med bilden. Fröna markerar vart och ett av objekten som ska segmenteras. Regionerna odlas iterativt genom jämförelse av alla icke-allokerade angränsande pixlar till regionerna. Skillnaden mellan en pixels intensitetsvärde och regionens medelvärde, $\delta$ , används som ett mått på likhet . Pixeln med den minsta skillnaden mätt på detta sätt tilldelas respektive region. Denna process fortsätter tills alla pixlar har tilldelats en region. Eftersom odling av fröområden kräver frön som ytterligare input, är segmenteringsresultaten beroende av valet av frön, och brus i bilden kan göra att fröna blir dåligt placerade.

En annan regionsodlingsmetod är den unseeded region-odlingsmetoden. Det är en modifierad algoritm som inte kräver explicita frön. Det börjar med en enda region $A_{1}$ — den pixel som väljs här påverkar inte den slutliga segmenteringen nämnvärt. Vid varje iteration tar den hänsyn till närliggande pixlar på samma sätt som den seedade regionen växer. Den skiljer sig från seedad region som växer genom att om minimivärdet $\delta$ är mindre än ett fördefinierat tröskelvärde $T$ så läggs det till respektive region $A_{j}$ . Om inte, så anses pixeln vara annorlunda än alla nuvarande regioner $A_{i}$ och en ny region $A_{n+1}$ skapas med denna pixel.

En variant av denna teknik, föreslagen av Haralick och Shapiro (1985), är baserad på pixelintensiteter . Medelvärdet och spridningen av regionen och intensiteten hos kandidatpixeln används för att beräkna en teststatistik. Om teststatistiken är tillräckligt liten läggs pixeln till regionen och regionens medelvärde och spridning beräknas om. Annars avvisas pixeln och används för att bilda en ny region.

En speciell regionsodlingsmetod kallas $\lambda$ -ansluten segmentering (se även lambda-anslutning ) . Den är baserad på pixelintensiteter och stadslänkande vägar. En grad av anslutning (connectedness) beräknas baserat på en väg som bildas av pixlar. För ett visst värde på $\lambda$ kallas två pixlar $\lambda$ -anslutna om det finns en sökväg som länkar dessa två pixlar och kopplingen till denna sökväg är minst $\lambda$ . $\lambda$ -anslutningen är en ekvivalensrelation.

Dela och slå samman segmentering baseras på en quadtree- partition av en bild. Det kallas ibland quadtree-segmentering.

Denna metod börjar vid roten av trädet som representerar hela bilden. Om den upptäcks som olikformig (inte homogen) delas den upp i fyra underordnade rutor (delningsprocessen) och så vidare. Om fyra underordnade rutor däremot är homogena, slås de samman som flera sammankopplade komponenter (sammanslagningsprocessen). Noden i trädet är en segmenterad nod. Denna process fortsätter rekursivt tills inga ytterligare splittringar eller sammanslagningar är möjliga. När en speciell datastruktur är involverad i implementeringen av metodens algoritm kan dess tidskomplexitet nå ${\displaystyle O(n\log n)} ,$ en optimal algoritm för metoden.

Partiella differentialekvationsbaserade metoder

Genom att använda en partiell differentialekvation (PDE)-baserad metod och lösa PDE-ekvationen med ett numeriskt schema, kan man segmentera bilden. Kurvutbredning är en populär teknik i denna kategori, med många tillämpningar för objektextraktion, objektspårning, stereorekonstruktion, etc. Den centrala idén är att utveckla en initial kurva mot den lägsta potentialen för en kostnadsfunktion, där dess definition återspeglar uppgiften att åtgärdas. Som för de flesta omvända problem är minimeringen av kostnadsfunktionen icke-trivial och lägger vissa jämnhetsbegränsningar på lösningen, vilket i det aktuella fallet kan uttryckas som geometriska begränsningar på den utvecklande kurvan.

Parametriska metoder

Lagrangiska tekniker bygger på att parametrisera konturen enligt någon samplingsstrategi och sedan utveckla varje element enligt bild och interna termer. Sådana tekniker är snabba och effektiva, men den ursprungliga "rent parametriska" formuleringen (på grund av Kass, Witkin och Terzopoulos 1987 och känd som " ormar "), kritiseras generellt för sina begränsningar när det gäller valet av provtagningsstrategi, de interna geometriska egenskaperna av kurvan, topologiförändringar (kurvuppdelning och sammanslagning), hantering av problem i högre dimensioner, etc. Nuförtiden har effektiva "diskretiserade" formuleringar utvecklats för att hantera dessa begränsningar samtidigt som hög effektivitet bibehålls. I båda fallen utförs energiminimering i allmänhet med en nedstigning med brantast gradient, varvid derivator beräknas med t.ex. ändliga skillnader.

Nivåbestämda metoder

Nivåuppsättningsmetoden föreslogs ursprungligen för att spåra rörliga gränssnitt av Dervieux och Thomasset 1979 och 1981 och uppfanns senare av Osher och Sethian 1988. Detta har spridit sig över olika avbildningsdomäner i slutet av 1990-talet . Den kan användas för att effektivt lösa problemet med kurva/yta/etc. spridning på ett implicit sätt. Den centrala idén är att representera den utvecklande konturen med hjälp av en teckenfunktion vars nolla motsvarar den faktiska konturen. Sedan, enligt konturens rörelseekvation, kan man enkelt härleda ett liknande flöde för den implicita ytan som när den appliceras på nollnivån kommer att återspegla konturens utbredning. Nivåuppsättningsmetoden ger många fördelar: den är implicit, är parameterfri, ger ett direkt sätt att uppskatta de geometriska egenskaperna hos den utvecklande strukturen, tillåter förändring av topologi och är inneboende. Det kan användas för att definiera ett optimeringsramverk, som föreslogs av Zhao, Merriman och Osher 1996. Man kan dra slutsatsen att det är ett mycket bekvämt ramverk för att hantera många tillämpningar av datorseende och medicinsk bildanalys. Forskning om olika nivåsatta datastrukturer har lett till mycket effektiva implementeringar av denna metod.

Snabba marschmetoder

Den snabba marschmetoden har använts i bildsegmentering, och denna modell har förbättrats (som tillåter både positiva och negativa fortplantningshastigheter) i ett tillvägagångssätt som kallas den generaliserade snabbmarschmetoden.

Varierande metoder

Målet med variationsmetoder är att hitta en segmentering som är optimal med avseende på en specifik energifunktion. Funktionalerna består av en dataanpassningsterm och en regulariserande term. En klassisk representant är Potts-modellen definierad för en bild $f$ av

\operatorname {argmin} _{u}\gamma \|\nabla u\|_{0}+\int (uf)^{2}\,dx.

En minimerare $u^{*}$ är en bitvis konstant bild som har en optimal kompromiss mellan det kvadratiska L2-avståndet till den givna bilden $f$ och den totala längden av dess hoppuppsättning. Hoppuppsättningen av $u^{*}$ definierar en segmentering. Den relativa vikten av energierna ställs in med parametern $\gamma >0$ . Den binära varianten av Potts-modellen, dvs om intervallet för $u$ är begränsat till två värden, kallas ofta ChanVese- modellen . En viktig generalisering är Mumford-Shah-modellen som ges av

\operatorname {argmin} _{u,K}\gamma |K|+\mu \int _{K^{C}}|\nabla u|^{2}\,dx+\int (uf)^ {2}\,dx.

Det funktionella värdet är summan av den totala längden av segmenteringskurvan $K$ , jämnheten för approximationen $u$ , och dess avstånd till originalbilden $f$ . Vikten på jämnhetsstraffet justeras med $\mu >0$ . Potts-modellen kallas ofta styckvis konstant Mumford-Shah-modell då den kan ses som det degenererade fallet $\mu \to \infty$ . Optimeringsproblemen är kända för att vara NP-hårda i allmänhet men nära-minimerande strategier fungerar bra i praktiken. Klassiska algoritmer är graderad icke-konvexitet och Ambrosio-Tortorelli approximation .

Grafpartitioneringsmetoder

Grafpartitioneringsmetoder är ett effektivt verktyg för bildsegmentering eftersom de modellerar effekten av pixelkvarter på ett givet kluster av pixlar eller pixlar, under antagandet om homogenitet i bilder. I dessa metoder modelleras bilden som en viktad, oriktad graf . Vanligtvis är en pixel eller en grupp av pixlar associerade med noder och kantvikter definierar (o)likheten mellan grannskapspixlarna. Grafen (bilden) delas sedan upp enligt ett kriterium utformat för att modellera "bra" kluster. Varje partition av noderna (pixlarna) som matas ut från dessa algoritmer anses vara ett objektsegment i bilden; se Segmenteringsbaserad objektkategorisering . Några populära algoritmer i den här kategorin är normaliserade snitt, slumpmässiga rullare , minimum snitt, isoperimetrisk partitionering, minimum spännande trädbaserad segmentering och segmenteringsbaserad objektkategorisering .

Markov slumpmässiga fält

Tillämpningen av Markov slumpfält (MRF) för bilder föreslogs i början av 1984 av Geman och Geman. Deras starka matematiska grund och förmåga att ge ett globalt optimum även när de definieras på lokala egenskaper visade sig vara grunden för ny forskning inom området bildanalys, brusreducering och segmentering. MRF:er kännetecknas helt av sina tidigare sannolikhetsfördelningar, marginella sannolikhetsfördelningar, klick , utjämningsrestriktioner samt kriterium för uppdatering av värden. Kriteriet för bildsegmentering med användning av MRF:er återges som att hitta märkningsschemat som har maximal sannolikhet för en given uppsättning funktioner. De breda kategorierna av bildsegmentering som använder MRF är övervakad och oövervakad segmentering.

Övervakad bildsegmentering med hjälp av MRF och MAP

När det gäller bildsegmentering är funktionen som MRF:er försöker maximera sannolikheten för att identifiera ett märkningsschema förutsatt att en viss uppsättning funktioner detekteras i bilden. Detta är en omräkning av den maximala a posteriori-uppskattningsmetoden .

MRF-kvarter för en vald pixel

Den generiska algoritmen för bildsegmentering med MAP ges nedan:

Definiera grannskapet för varje funktion (slumpvariabel i MRF-termer). I allmänhet inkluderar detta 1:a ordningens eller 2:a ordningens grannar.
Ange initiala sannolikheter $P (f i)$ > för varje funktion som 0 eller
där $f i \in Σ$ är den uppsättning som innehåller funktioner som extraherats för pixel $i$ och definierar en initial uppsättning kluster.
Använd träningsdata för att beräkna medelvärdet ( $μ ℓ i$ ) och variansen ( $σ ℓ i$ ) för varje etikett. Detta kallas klassstatistik.
Beräkna marginalfördelningen för det givna märkningsschemat $. P (fi | ℓ i)$ med hjälp av Bayes sats och klassstatistiken som beräknats tidigare En Gaussisk modell används för marginalfördelningen.
${\frac {1}{\sigma (\ell _ {i}){\sqrt {2\pi }}}}e^{-(f_{i}-\mu (\ell _{i}))^{2}/(2\sigma (\ell _{ i})^{2})}\,d\ell _{i}$
Beräkna sannolikheten för varje klassetikett givet det område som definierats tidigare. Klickpotentialer används för att modellera den sociala påverkan vid märkning.
Iterera över nya tidigare sannolikheter och omdefiniera kluster så att dessa sannolikheter maximeras. Detta görs med hjälp av en mängd olika optimeringsalgoritmer som beskrivs nedan.
Stoppa när sannolikheten är maximerad och märkningsschemat inte ändras. Beräkningarna kan också implementeras i log-sannolikhetstermer .

Optimeringsalgoritmer

Varje optimeringsalgoritm är en anpassning av modeller från en mängd olika områden och de skiljer sig från sina unika kostnadsfunktioner. Det gemensamma för kostnadsfunktioner är att straffa förändringar i pixelvärde såväl som skillnader i pixeletikett jämfört med etiketter för angränsande pixlar.

Itererade villkorade lägen/gradientnedstigning

itererade villkorade lägen (ICM) försöker rekonstruera det ideala märkningsschemat genom att ändra värdena för varje pixel över varje iteration och utvärdera energin i det nya märkningsschemat med hjälp av kostnadsfunktionen nedan,

\alpha (1-\delta (\ ell _{i}-\ell _{{\text{initial }}i})+\beta \Sigma _{q\in N(i)}(1-\delta (\ell _{i},\ell _{q(i)})).

där $a$ är straffvärdet för förändring i pixeletikett och $β$ är straffet för skillnad i etikett mellan angränsande pixlar och vald pixel. Här är $N(i)$ grannskapet till pixel i och $δ$ är Kronecker deltafunktionen. Ett stort problem med ICM är att den, i likhet med gradientnedstigning, har en tendens att vila över lokala maxima och därmed inte få ett globalt optimalt märkningsschema.

Simulerad glödgning (SA)

Härledd som en analog av glödgning inom metallurgi, använder simulerad glödgning (SA) förändring i pixeletikett över iterationer och uppskattar skillnaden i energi för varje nybildad graf till de initiala data. Om den nybildade grafen är mer lönsam, i termer av låg energikostnad, givet av:

\Delta U=U^{\text{ny}}-U^{\text{gammal}}

\ell _{i}={\begin{cases}\ell _{i}^{\text{new}}, &{\text{if }}\Delta U\leq 0,\\\ell _{i}^{\text{ny}},&{\text{if }}\Delta U>0{\text{ och }}\delta <e^{-\Delta U/T},\ell _{i}^{\text{old}}\end{cases}}

Algoritmen väljer den nybildade grafen. Simulerad glödgning kräver inmatning av temperaturscheman som direkt påverkar systemets konvergenshastighet, såväl som energitröskeln för att minimering ska ske.

Alternativa algoritmer

En rad andra metoder finns för att lösa enkla såväl som högre ordnings MRF. De inkluderar maximering av posterior marginal, flerskalig MAP-uppskattning, segmentering med flera upplösningar och mer. Bortsett från sannolikhetsuppskattningar finns det grafklipp med maximalt flöde och andra mycket begränsade grafbaserade metoder för att lösa MRF.

Bildsegmentering med MRF och förväntningsmaximering

Förväntningsmaximeringsalgoritmen används för att iterativt uppskatta de a posteriora sannolikheterna och fördelningarna av märkning när inga träningsdata finns tillgängliga och ingen uppskattning av segmenteringsmodellen kan bildas . Ett allmänt tillvägagångssätt är att använda histogram för att representera egenskaperna hos en bild och fortsätt som beskrivs kortfattat i denna trestegsalgoritm:

1. En slumpmässig uppskattning av modellparametrarna används.

2. E-steg: Uppskatta klassstatistik baserad på den definierade slumpmässiga segmenteringsmodellen. Använd dessa, beräkna den villkorade sannolikheten för att tillhöra en etikett förutsatt att egenskapsuppsättningen beräknas med naiva Bayes teorem .

P(\lambda \mid f_{i})={ \frac {P(f_{i}\mid \lambda )P(\lambda )}{\Sigma _{\lambda \in \Lambda }P(f_{i}\mid \lambda )P(\lambda )}}

Här $\lambda \in \Lambda$ , uppsättningen av alla möjliga etiketter.

3. M-steg: Den etablerade relevansen av en given funktionsuppsättning för ett märkningsschema används nu för att beräkna a priori-uppskattningen av en given etikett i den andra delen av algoritmen. Eftersom det faktiska antalet totala etiketter är okänt (från en träningsdatauppsättning), används en dold uppskattning av antalet etiketter som ges av användaren i beräkningar.

P(\lambda )={\frac {\Sigma _{\lambda \in \Lambda }P(\lambda \mid f_{i})}{|\Omega |}}

där $\Omega$ är mängden av alla möjliga funktioner.

Segmentering av färgbild med HMRF-EM-modell

Nackdelar med MAP- och EM-baserad bildsegmentering

Exakta MAP-uppskattningar kan inte lätt beräknas.
Ungefärliga MAP-uppskattningar är beräkningsmässigt dyra att beräkna.
Utvidgning till flerklassmärkning försämrar prestandan och ökar lagringsbehovet.
Tillförlitlig uppskattning av parametrar för EM krävs för att globala optima ska uppnås.
Baserat på optimeringsmetod kan segmentering klusteras till lokala minima.

Vattendelare transformation

Vattendelaretransformationen betraktar en bilds gradientstorlek som en topografisk yta . Pixlar som har den högsta gradient magnitude intensities (GMI) motsvarar vattendelare, som representerar regiongränserna. Vatten placerat på vilken pixel som helst som omges av en gemensam vattendelare rinner nedför till ett gemensamt lokalt intensitetsminimum (LIM). Pixlar som dräneras till ett gemensamt minimum bildar en fångstbassäng, som representerar ett segment.

Modellbaserad segmentering

Det centrala antagandet för modellbaserade tillvägagångssätt är att strukturerna av intresse har en tendens till en viss form. Därför kan man söka en probabilistisk modell som kännetecknar formen och dess variation. När du segmenterar en bild kan begränsningar införas med den här modellen som tidigare. En sådan uppgift kan innefatta (i) registrering av träningsexemplen till en gemensam ställning, (ii) probabilistisk representation av variationen av de registrerade proverna och (iii) statistisk slutledning mellan modellen och bilden. Andra viktiga metoder i litteraturen för modellbaserad segmentering inkluderar aktiva formmodeller och aktiva utseendemodeller .

Flerskalig segmentering

Bildsegmentering beräknas på flera skalor i skalutrymme och sprids ibland från grova till fina skalor; se skala-rymdsegmentering .

Segmenteringskriterier kan vara godtyckligt komplexa och kan ta hänsyn till såväl globala som lokala kriterier. Ett vanligt krav är att varje region ska vara sammankopplad i någon mening.

Endimensionell hierarkisk signalsegmentering

Witkins framträdande arbete i skalrymden inkluderade föreställningen att en endimensionell signal otvetydigt kunde segmenteras i regioner, med en skalparameter som styr segmenteringens skala.

En viktig observation är att nollgenomgångarna för andraderivatan (minima och maxima för förstaderivatan eller lutningen) av flerskaleutjämnade versioner av en signal bildar ett häckande träd, som definierar hierarkiska relationer mellan segment i olika skalor. Specifikt kan sluttningsextrema vid grova skalor spåras tillbaka till motsvarande egenskaper vid fina skalor. När ett lutningsmaximum och ett lutningsminimum utplånar varandra i en större skala, smälter de tre segmenten som de separerade samman till ett segment, vilket definierar segmenthierarkin.

Bildsegmentering och primalskiss

Det har gjorts många forskningsarbeten inom detta område, av vilka ett fåtal nu har nått ett tillstånd där de kan tillämpas antingen med interaktiv manuell intervention (vanligtvis med tillämpning på medicinsk bildbehandling) eller helt automatiskt. Följande är en kort översikt över några av de huvudsakliga forskningsidéer som nuvarande tillvägagångssätt bygger på.

Den häckande strukturen som Witkin beskrev är dock specifik för endimensionella signaler och överförs inte trivialt till högre dimensionella bilder. Ändå har denna allmänna idé inspirerat flera andra författare att undersöka grov-till-fin-scheman för bildsegmentering. Koenderink föreslog att studera hur iso-intensitetskonturer utvecklas över skalor och detta tillvägagångssätt undersöktes mer i detalj av Lifshitz och Pizer. Tyvärr ändras dock intensiteten hos bildegenskaper över skalor, vilket innebär att det är svårt att spåra bildegenskaper i grova skalor till finare skalor med hjälp av iso-intensitetsinformation.

Lindeberg studerade problemet med att länka lokala extrema och sadelpunkter över skalor, och föreslog en bildrepresentation som kallas scale-space primal sketch som expliciterar relationerna mellan strukturer i olika skalor, och även expliciterar vilka bildegenskaper som är stabila över stora intervall av skala inklusive lokalt lämpliga skalor för dessa. Bergholm föreslog att detektera kanter vid grova skalor i skalrymd och sedan spåra dem tillbaka till finare skalor med manuellt val av både den grova detekteringsskalan och den fina lokaliseringsskalan.

Gauch och Pizer studerade det komplementära problemet med åsar och dalar i flera skalor och utvecklade ett verktyg för interaktiv bildsegmentering baserat på flerskaliga vattendelar. Användningen av flerskalig vattendelare med tillämpning på gradientkartan har också undersökts av Olsen och Nielsen och överförts till klinisk användning av Dam. Vincken et al. föreslog en hyperstack för att definiera probabilistiska relationer mellan bildstrukturer i olika skalor. Användningen av stabila bildstrukturer över skalor har utvecklats av Ahuja och hans medarbetare till ett helt automatiserat system. En helautomatisk hjärnsegmenteringsalgoritm baserad på närbesläktade idéer om flerskaliga vattendelar har presenterats av Undeman och Lindeberg och testats omfattande i hjärndatabaser.

Dessa idéer för flerskalig bildsegmentering genom att länka bildstrukturer över skalor har också tagits upp av Florack och Kuijper. Bijaoui och Rué associerar strukturer som upptäcks i skalutrymme över en lägsta bruströskel till ett objektträd som sträcker sig över flera skalor och motsvarar ett slags särdrag i den ursprungliga signalen. Extraherade egenskaper rekonstrueras noggrant med hjälp av en iterativ konjugatgradientmatrismetod.

Halvautomatisk segmentering

I en typ av segmentering skisserar användaren området av intresse med musklicken och algoritmer tillämpas så att den väg som bäst passar kanten på bilden visas.

Tekniker som SIOX , Livewire , Intelligent Scissors eller IT-SNAPS används i denna typ av segmentering. I en alternativ typ av halvautomatisk segmentering returnerar algoritmerna ett rumsligt taxon (dvs. förgrund, objektgrupp, objekt eller objektdel) som valts av användaren eller utsetts via tidigare sannolikheter.

Träningsbar segmentering

De flesta av de tidigare nämnda segmenteringsmetoderna baseras endast på färginformation för pixlar i bilden. Människor använder mycket mer kunskap när de utför bildsegmentering, men att implementera denna kunskap skulle kosta avsevärd mänsklig ingenjörs- och beräkningstid, och skulle kräva en enorm domänkunskapsdatabas som för närvarande inte finns. Träningsbara segmenteringsmetoder, såsom av neurala nätverk , övervinner dessa problem genom att modellera domänkunskapen från en datauppsättning av märkta pixlar.

neuralt nätverk för bildsegmentering kan bearbeta små områden av en bild för att extrahera enkla funktioner som kanter. Ett annat neuralt nätverk, eller vilken beslutsfattande mekanism som helst, kan sedan kombinera dessa funktioner för att märka områdena i en bild därefter. En typ av nätverk designad på detta sätt är Kohonen-kartan .

Pulskopplade neurala nätverk (PCNN) är neurala modeller som föreslagits genom att modellera en katts visuella cortex och utvecklade för högpresterande biomimetisk bildbehandling . 1989 introducerade Reinhard Eckhorn en neural modell för att efterlikna mekanismen för en katts visuella cortex. Eckhorn-modellen gav ett enkelt och effektivt verktyg för att studera den visuella cortexen hos små däggdjur och upptäcktes snart som en betydande tillämpningspotential inom bildbehandling. 1994 anpassades Eckhorn-modellen för att vara en bildbehandlingsalgoritm av John L. Johnson, som kallade denna algoritm för Pulse-Coupled Neural Network. Under det senaste decenniet har PCNN använts för en mängd olika bildbehandlingstillämpningar, inklusive: bildsegmentering, funktionsgenerering, ansiktsextraktion, rörelsedetektering, regiontillväxt, brusreducering och så vidare. En PCNN är ett tvådimensionellt neuralt nätverk. Varje neuron i nätverket motsvarar en pixel i en ingångsbild, som tar emot sin motsvarande pixels färginformation (t.ex. intensitet) som en extern stimulans. Varje neuron ansluter också till sina närliggande neuroner och tar emot lokala stimuli från dem. De externa och lokala stimulierna kombineras i ett internt aktiveringssystem, som ackumulerar stimuli tills det överskrider en dynamisk tröskel, vilket resulterar i en pulsutgång. Genom iterativ beräkning producerar PCNN-neuroner tidsserier av pulsutgångar. Den tidsmässiga serien av pulsutgångar innehåller information om ingångsbilder och kan användas för olika bildbehandlingstillämpningar, såsom bildsegmentering och funktionsgenerering. Jämfört med konventionella bildbehandlingsmedel har PCNN:er flera betydande fördelar, inklusive robusthet mot brus, oberoende av geometriska variationer i inmatningsmönster, förmåga att överbrygga mindre intensitetsvariationer i ingångsmönster, etc.

U-Net är ett konvolutionellt neuralt nätverk som tar en bild som input och matar ut en etikett för varje pixel. U-Net utvecklades ursprungligen för att upptäcka cellgränser i biomedicinska bilder. U-Net följer klassisk autoencoder- arkitektur, som sådan innehåller den två understrukturer. Kodarstrukturen följer den traditionella stapeln av faltnings- och maxpoolande lager för att öka det receptiva fältet när det går genom lagren. Den används för att fånga sammanhanget i bilden. Avkodarstrukturen använder transponerade faltningslager för uppsampling så att änddimensionerna är nära ingångsbildens. Skip-kopplingar placeras mellan faltning och transponerade faltningslager av samma form för att bevara detaljer som annars skulle ha gått förlorade.

Förutom semantiska segmenteringsuppgifter på pixelnivå som tilldelar en given kategori till varje pixel, inkluderar moderna segmenteringsapplikationer semantiska segmenteringsuppgifter på instansnivå där varje individ i en given kategori måste identifieras unikt, såväl som panoptiska segmenteringsuppgifter som kombinerar dessa två uppgifter för att ge en mer komplett scensegmentering.

Segmentering av relaterade bilder och videor

Relaterade bilder som ett fotoalbum eller en sekvens av videoramar innehåller ofta semantiskt liknande objekt och scener, därför är det ofta fördelaktigt att utnyttja sådana samband. Uppgiften att samtidigt segmentera scener från relaterade bilder eller videorutor kallas för co-segmentering, som vanligtvis används i lokalisering av mänsklig handling . Till skillnad från konventionell begränsningsrutabaserad objektdetektering ger lokaliseringsmetoder för mänsklig åtgärd finare resultat, typiskt segmenteringsmasker per bild som avgränsar det mänskliga objektet av intresse och dess åtgärdskategori (t.ex. Segment -Tube ). Tekniker som dynamiska Markov Networks , CNN och LSTM används ofta för att utnyttja korrelationerna mellan ramarna.

Andra metoder

Det finns många andra metoder för segmentering som multispektral segmentering eller anslutningsbaserad segmentering baserad på DTI-bilder .

Se även

Anteckningar

3D-entropibaserad bildsegmentering
Frucci, Maria; Sanniti di Baja, Gabriella (2008). "Från segmentering till binarisering av bilder på grånivå". Journal of Pattern Recognition Research . 3 (1): 1–13. doi : 10.13176/11.54 .

externa länkar

Lite exempelkod som utför grundläggande segmentering , av Syed Zainudeen. University Technology of Malaysia.
Generalized Fast Marching-metod av Forcadel et al. [2008] för applikationer inom bildsegmentering.
Bildbehandlingsforskningsgruppen arkiverad 2020-12-28 på Wayback Machine An Online Open Image Processing Research Community.
Segmenteringsmetoder i bildbehandling och analys och Minimering av energi för att segmentera bilder av Mathworks
Fler bildsegmenteringsmetoder med detaljerade algoritmer av Yu-Hsiang Wang (王昱翔), National Taiwan University, Taipei, Taiwan, ROC
Online demonstration av bitvis linjär bildsegmentering av IPOL Journal