Transformace zalesňování obrázků - Image foresting transform


V praxi digitální zpracování obrazu Alexandre X. Falcao, Jorge Stolfi a Roberto de Alencar Lotufo vytvořili a prokázali, že Transformace zalesňování obrázků (IFT) lze použít jako šetřič času při zpracování 2D, 3D obrázků a pohyblivých obrázků.[1]

Dějiny [1]

V roce 1959 Dijkstra použil a vyvážená halda datová struktura[1][2] vylepšit algoritmus představený Moorem v roce 1957[1][3] a Bellman v roce 1958[1][4] který vypočítal náklady na cesty v obecném grafu. The Třídění lopaty technika je, jak Dial vylepšil algoritmus o deset let později.[1][5] Algoritmus byl od té doby vylepšen a upraven mnoha způsoby. Právě v této verzi Falcao, Stolfi a Lotufo vylepšili.[1]

Definice [1]

Transformace je vylepšená verze Dijkstrova algoritmu nejkratší cesty, který je optimalizován pro použití více než jednoho vstupu a pro maximalizaci operátorů zpracování digitálního obrazu.[1][2] Transformace vytvoří graf pixelů v obrázku a spojení mezi těmito body jsou „cenou“ zobrazené cesty. Cena se vypočítá kontrolou vlastností, například stupnice šedé, barvy, přechodu mezi mnoha dalšími, cesty mezi pixely. Stromy jsou vytvářeny spojením pixelů, které mají stejnou nebo blízkou cenu za použití operátoru, o kterém bylo rozhodnuto. Robustnost transformace je nákladná a využívá spoustu úložného prostoru pro kód a zpracovávaná data. Když transformace proběhne, vrátí se předchůdce, cena a štítek. Většina operátorů, kteří se používají pro digitální zpracování obrazu, může tyto tři informace využít k optimalizaci.

Optimalizace [1]

V závislosti na tom, který operátor zpracování digitálního obrazu, o kterém byl rozhodnut algoritmus, lze dále vyladit pro optimalizaci v závislosti na tom, co tento operátor používá. Algoritmus lze také optimalizovat vyříznutím přepočtu cest. Toho lze dosáhnout pomocí externí referenční tabulky pro sledování vypočítaných cest. „Zpětné oblouky“ lze eliminovat porovnáním nákladů na cestu v obou směrech a vyloučením dražší cesty. Existuje také případ, kdy algoritmus vrací pro některé cesty nekonečno. V tomto případě lze nastavit prahové číslo, které nahradí nekonečno, nebo bude cesta vyloučena a nebude použita v dalších výpočtech.

Viz také

Reference

  1. ^ A b C d E F G h i j Falcao, A.X. Stolfi, J. de Alencar Lotufo, R.: "Transformace zalesňování obrazu: teorie, algoritmy a aplikace ", V IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 26, NO. 1, JANUARY 2004
  2. ^ A b E.W. Dijkstra, “Poznámka ke dvěma problémům v souvislosti s grafy, “Numerische Mathematik, sv. 1, str. 269-271, 1959
  3. ^ E.F. Moore, „Nejkratší cesta bludištěm“, Proc. Int’l Symp. Theory of Switching, str. 285-292, duben 1959
  4. ^ R. Bellman, “Na problému se směrováním „Quarterly of Applied Math., Sv. 16, str. 87-90, 1958
  5. ^ R.B. Dial, “Les s nejkratší cestou s topologickým uspořádáním „Komunikace ACM, sv. 12, č. 11, str. 632-633, listopad 1969