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.[1]
History
editIn 1959 Dijkstra used a balanced heap data structure[1][2] to improve upon an algorithm presented by Moore in 1957[1][3] and Bellman in 1958[1][4] 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.[1][5] The algorithm has been tweaked and modified in many ways since then. It is on this version that Falcao, Stolfi, and Lotufo improved.[1]
Definition
editThe 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.[1][2] 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
editDepending on which digital image processing operator 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
editReferences
edit- ^ a b c d e f g 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
- ^ a b E.W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, vol. 1, pp. 269-271, 1959
- ^ E.F. Moore, “The Shortest Path through a Maze,” Proc. Int’l Symp. Theory of Switching, pp. 285-292, Apr. 1959
- ^ R. Bellman, “On a Routing Problem,” Quarterly of Applied Math., vol. 16, pp. 87-90, 1958
- ^ R.B. Dial, “Shortest-Path Forest with Topological Ordering,” Comm. ACM, vol. 12, no. 11, pp. 632-633, Nov. 1969