Content deleted Content added
No edit summary |
general cleanup |
||
| (4 intermediate revisions by 2 users not shown) | |||
Line 1:
In the practice of [[digital image processing]] Alexandre X. Falcao, Jorge Stolfi, and Roberto de Alencar Lotufo have created and proven that the '''Image Foresting Transform''' (IFT) can be used as a time saver in processing 2-D, 3-D images, and moving images.<ref name="Falcao">Falcao, A.X. Stolfi, J. de Alencar Lotufo, R. : "[https://www.researchgate.net/profile/Roberto_Lotufo/publication/8331682_The_image_foresting_transform_theory_algorithms_and_applications/links/0912f50b724229bf0d000000.pdf The image foresting transform: theory, algorithms, and applications]", In IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 26, NO. 1, JANUARY 2004</ref> ▼
==History==
In 1959 Dijkstra used a [[Heap (data structure)|balanced heap data structure]]<ref name="Falcao"/><ref name="Dij">E.W. Dijkstra,
▲In the practice of [[digital image processing]] Alexandre X. Falcao, Jorge Stolfi, and Roberto de Alencar Lotufo have created and proven that the '''Image Foresting Transform''' (IFT) can be used as a time saver in processing 2-D, 3-D images, and moving images.<ref name="Falcao">Falcao, A.X. Stolfi, J. de Alencar Lotufo, R. : "The image foresting transform: theory, algorithms, and applications", In IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 26, NO. 1, JANUARY 2004</ref>
==Definition==
The transform is a tweaked version of Dijkstra’s shortest-path algorithm that is optimized for using more than one input and the maximization of digital image processing operators.<ref name="Falcao"/><ref name="Dij"/> The transform makes a graph of the pixels in an image and the connections between these points are the "cost" of the path portrayed. The cost is calculated by inspecting the characteristics, for example, grey scale, color, gradient among many others, of the path between pixels. Trees are made by connecting the pixels that have the same or close cost for applying the operator decided upon. The robustness of the transform does come at a cost and uses a lot of storage space for the code and the data being processed. When the transform is through, the predecessor, cost, and label are returned. Most of the operators that are used for digital image processing can use these three pieces of information to be optimized.▼
▲In 1959 Dijkstra used a [[Heap (data structure)|balanced heap data structure]]<ref name="Falcao"/><ref name="Dij">E.W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, vol. 1, pp. 269-271, 1959</ref> to improve upon an algorithm presented by Moore in 1957<ref name="Falcao"/><ref name="Moo">E.F. Moore, “The Shortest Path through a Maze,” Proc. Int’l Symp. Theory of Switching, pp. 285-292, Apr. 1959</ref> and Bellman in 1958<ref name="Falcao"/><ref name="Bell">R. Bellman, “On a Routing Problem,” Quarterly of Applied Math., vol. 16, pp. 87-90, 1958</ref> that computed the cost of the paths in a general graph. The [[Bucket sort]]ing technique is how Dial improved on the algorithm a decade later.<ref name="Falcao"/><ref name="Dial">R.B. Dial, “Shortest-Path Forest with Topological Ordering,” Comm. ACM, vol. 12, no. 11, pp. 632-633, Nov. 1969</ref> The algorithm has been tweaked and modified in many ways since then. It is on this version that Falcao, Stolfi, and Lotufo improved upon.<ref name="Falcao"/>
Depending on which digital image processing operator
▲The transform is a tweaked version of Dijkstra’s shortest-path algorithm that is optimized for using more than one input and the maximization of digital image processing operators.<ref name="Falcao"/><ref name="Dij"/> The transform makes a graph of the pixels in an image and the connections between these points are the "cost" of the path portrayed. The cost is calculated by inspecting the characteristics, for example grey scale, color, gradient among many others, of the path between pixels. Trees are made by connecting the pixels that have the same or close cost for applying the operator decided upon. The robustness of the transform does come at a cost and uses a lot of storage space for the code and the data being processed. When the transform is through, the predecessor, cost, and label are returned. Most of the operators that are used for digital image processing can use these three pieces of information to be optimized.
▲==Optimization <ref name="Falcao"/>==
▲Depending on which digital image processing operator that has been decided upon the algorithm can be further tweaked for optimization depending upon what that operator uses. The algorithm can also be optimized by cutting out the recalculation of paths. This is accomplished by using an external reference table to keep track of the calculated paths. "Backward Arcs" can be eliminated by comparing the cost of the path in both directions and eliminating the more expensive path. There is also a case where the algorithm returns infinity for some of the paths. In this case a threshold number can be set to replace infinity, or the path will be eliminated and not used in further calculations.
==See also==
Line 22 ⟶ 19:
== References ==
{{reflist}}
| |||