Grassfire transformace - Grassfire transform

v zpracování obrazu, transformace trávy je výpočet vzdálenosti od pixelu k hranici oblasti. Lze jej popsat jako „zapálení“ hranic obrazové oblasti, aby se získaly deskriptory, jako je oblast kostra nebo mediální osa. Harry Blum představil koncept v roce 1967.^[1]

Motivace

Kostra regionu může být užitečným deskriptorem, protože popisuje věci, jako je symetrie regionu, stejně jako jeho části, prohlubně a výčnělky.^[2] Poskytuje také způsob, jak spojit vnitřek oblasti s tvarem hranice. Při transformaci trávy se kostra formuje v místech v oblasti, kde se „ohně“ setkávají. V literatuře je to popsáno jako místo setkávání vln.^[2]

Další výhodou použití výsledku transformace trávy jako deskriptoru je, že je invertibilní. Za předpokladu, že jsou zachovány informace o tom, kdy je mediální osa nebo kostra vytvořena setkáním s křivkami, je možné kostru obnovit vyzařováním ven.^[1]

Příklad algoritmu

Níže uvedený algoritmus je jednoduchý dvouprůchodový způsob výpočtu Vzdálenost na Manhattanu od hranice regionu. Samozřejmě existuje několik dalších algoritmů pro provedení transformace trávy.

  pro každý řádek v obraz vlevo, odjet na že jo    pro každý sloupec v obraz horní na dno      -li (pixel je v kraj) {        soubor pixel na 1 + minimální hodnota z the severní a Západ sousedé      } jiný {        soubor pixel na nula      }    }  }  pro každý řádek že jo na vlevo, odjet    pro každý sloupec dno na horní      -li (pixel je v kraj) {        soubor pixel na min(hodnota z the pixel,1 + minimální hodnota z the jižní a východní sousedé)      } jiný {        soubor pixel na nula      }    }  }

Níže je výsledek této transformace. Je důležité si uvědomit, že nejintenzivnější linie tvoří kostru.

Zdrojový obrázek

Výsledný obrázek

Aplikace

Transformaci trávníku lze abstrahovat tak, aby vyhovovala různým problémům s výpočtem. Ukázalo se, že jej lze rozšířit nad rámec obrázků na libovolné funkce.^[3] To zahrnuje aplikace při problémech s minimalizací energie, jako jsou ty, které řeší Viterbiho algoritmus, šíření víry v maximální produkt, přidělování zdrojů a v optimálních metodách řízení.^[3]

Lze jej také použít k výpočtu vzdálenosti mezi oblastmi nastavením pozadí jako oblasti.

Viz také

• Topologická kostra
• Transformace vzdálenosti

Reference