Gräseldsförvandling
I bildbehandling är gräseldstransformen beräkningen av avståndet från en pixel till gränsen för en region . Det kan beskrivas som att "sätta eld" på gränserna för en bildregion för att ge deskriptorer som regionens skelett eller mediala axel . Harry Blum introducerade konceptet 1967.
Motivering
En regions skelett kan vara en användbar deskriptor, eftersom det beskriver saker som regionens symmetri såväl som underdelar, fördjupningar och utsprång. Det ger också ett sätt att relatera det inre av en region till formen på gränsen. I gräseldstransformationen bildas skelettet vid de punkter i regionen där "bränderna" möts. I litteraturen beskrivs detta som platsen för att möta vågformer.
En annan fördel med att använda resultatet av gräseldsomvandlingen som en deskriptor är att den är inverterbar. Förutsatt att information om när den mediala axeln eller skelettet skapas genom att möta vågformer behålls, då kan skelettet återställas genom att stråla utåt.
Exempel på algoritm
Algoritmen nedan är en enkel tvåpasseringsmetod för att beräkna Manhattan-avståndet från en regions gräns. Naturligtvis finns det flera andra algoritmer för att utföra gräseldsomvandlingen.
för varje rad i bilden från vänster till höger för varje kolumn i bilden uppifrån och ned om ( pixel är i regionen ) { ställ in pixel till 1 + minsta värdet för de norra och västra grannarna } annars { ställ pixel till noll } } } för varje rad höger till vänster för varje kolumn från botten till toppen om ( pixel är i regionen ) { ställ pixel till min ( värde på pixel , 1 + lägsta värde för grannarna i söder och öster ) } annars { ställ pixel till noll } } }
Nedan är resultatet av denna transformation. Det är viktigt att notera att de mest intensiva linjerna utgör skelettet.
Ansökningar
Gräseldstransformen kan abstraheras för att passa en mängd olika datorproblem. Det har visat sig att det kan utvidgas bortom bildkontexten till godtyckliga funktioner. Detta inkluderar applikationer i energiminimeringsproblem som de som hanteras av Viterbi-algoritmen , max-produktförökning, resursallokering och i optimala kontrollmetoder.
Den kan också användas för att beräkna avståndet mellan regioner genom att ställa in bakgrunden som en region.