Image foresting transform: Difference between revisions

Revision as of 00:12, 27 April 2018

Revision as of 04:04, 1 May 2018

Line 1:

__FORCETOC__

In the practice of [[Image processing]] Alexandre X. Falca˜ o, 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>. The transform uses a method borrowed from machine learning that is known as [[Random forest]] which finds the "cheapest" way to go about applying image operators.

==<big>History</big> <ref name="Falcao"/>==

In 1959 Dijkstra used a 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 sorting 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"/>.

==<big>Definition</big> <ref name="Falcao"/>==

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.

==<big>Optimization</big> <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.

==<big>Related topics</big>==

[[Image processing]], [[Watershed (image processing)]], [[Random forest|Random forest]]

==See also==

[[Image processing]], [[Watershed (image processing)]], [[Random forest|Random forest]]

== References ==

<!-- Inline citations added to your article will automatically display here. See https://en.wikipedia.org/wiki/WP:REFB for instructions on how to add citations. -->

{{reflist}}

{{uncategorized|date=May 2018}}