In the practice of

digital image processing Digital image processing is the use of a digital computer to process digital images through an algorithm. As a subcategory or field of digital signal processing, digital image processing has many advantages over analog image processing. It allo ...

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.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

History

In 1959 Dijkstra used a balanced heap data structureE.W. Dijkstra, �
A Note on Two Problems in Connexion with Graphs
” Numerische Mathematik, vol. 1, pp. 269-271, 1959 to improve upon an algorithm presented by Moore in 1957E.F. Moore, “The Shortest Path through a Maze,” Proc. Int’l Symp. Theory of Switching, pp. 285-292, Apr. 1959 and Bellman in 1958R. Bellman, �
On a Routing Problem
” Quarterly of Applied Math., vol. 16, pp. 87-90, 1958 that computed the cost of the paths in a general graph. The

Bucket sort Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the b ...

ing technique is how Dial improved on the algorithm a decade later.R.B. Dial, �
Shortest-Path Forest with Topological Ordering
” Comm. ACM, vol. 12, no. 11, pp. 632-633, Nov. 1969 The algorithm has been tweaked and modified in many ways since then. It is on this version that Falcao, Stolfi, and Lotufo improved.

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. 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

Depending 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.

References

{{reflist Image processing

History

Definition

Optimization

See also

References