Transformacja Grassfire
W przetwarzaniu obrazu transformacja pożaru trawy polega na obliczeniu odległości od piksela do granicy regionu. Można to opisać jako „podpalenie” granic obszaru obrazu w celu uzyskania deskryptorów, takich jak szkielet regionu lub oś środkowa . Harry Blum wprowadził tę koncepcję w 1967 roku.
Motywacja
Szkielet regionu może być użytecznym deskryptorem, ponieważ opisuje takie rzeczy, jak symetria regionu, a także podczęści, zagłębienia i wypukłości. Zapewnia również sposób powiązania wnętrza regionu z kształtem granicy. W transformacji pożaru trawy szkielet tworzy się w miejscach w regionie, w którym spotykają się „pożary”. W literaturze jest to określane jako miejsce spotkania przebiegów fal.
Kolejną zaletą wykorzystania wyniku transformacji pożaru trawy jako deskryptora jest to, że jest ona odwracalna. Zakładając, że zachowana jest informacja o tym, kiedy oś przyśrodkowa lub szkielet jest tworzony przez stykające się przebiegi, wówczas szkielet można odtworzyć poprzez promieniowanie na zewnątrz.
Przykładowy algorytm
Poniższy algorytm to prosta dwuprzebiegowa metoda obliczania odległości Manhattanu od granicy regionu. Oczywiście istnieje kilka innych algorytmów przeprowadzania transformacji pożaru trawy.
dla każdego wiersza obrazu od lewej do prawej dla każdej kolumny obrazu od góry do dołu if ( piksel jest w regionie ) { ustaw piksel na 1 + minimalna wartość północnych i zachodnich sąsiadów } else { ustaw piksel na zero } _ _
} } dla każdego wiersza od prawej do lewej dla każdej kolumny od dołu do góry if ( piksel jest w regionie ) { ustaw piksel na min ( wartość piksela , 1 + minimalna wartość południowych i wschodnich sąsiadów ) } else { _ _
ustaw piksel na zero } } }
Poniżej znajduje się wynik tej transformacji. Należy zauważyć, że najbardziej intensywne linie tworzą szkielet.
Aplikacje
Transformację pożaru trawy można wyabstrahować, aby pasowała do różnych problemów obliczeniowych. Wykazano, że można ją rozszerzyć poza kontekst obrazów do dowolnych funkcji. Obejmuje to zastosowania w problemach minimalizacji energii, takich jak te obsługiwane przez algorytm Viterbiego , propagacji przekonania o maksymalnym produkcie, alokacji zasobów oraz w optymalnych metodach sterowania.
Można go również użyć do obliczenia odległości między regionami, ustawiając tło jako region.