ift

Synopsis

Prototype:
y = ift(f, offsets)
Description:
The ift function implements the watershed transform using the image-foresting transform. It uses a max path cost function to calculate a shortest path forest with a generalization of Dijkstra's algorithm. The algorithm was proposed by Lotufo and Falcão [LotufoFalcaoISMM2000].
Definition:
IFT-WT
Exploration:
Breadth-First

Algorithm

\begin{algorithmic}[1]

\In{$im$: Grey level image with domain $D$, $S$: markers}
\Out{$lab$: Labels image}


\Statex

\Initialise
    \State $\forall p \in D, \; \done{p} \atr\ \KwFalse$
    \State $\forall p \not\in S, \; \data{$C_1$(p)} \atr\ \infty, \; \lab{p} \atr\ \mask, \; \parent{p} \atr\ \mask$
    \State $\forall p \in S, \; \data{$C_1$(p)} \atr\ \im{p}, \; \lab{p} \atr\ \lambda(p), \; \parent{p} \atr\ p$, \HeapQueuePush{p, \im{p}}
\End

\Statex

\While{\HeapQueueEmpty{} = \KwFalse}
    \State p \atr\ \HeapQueuePop{}
    \State \done{p} \atr\ \KwTrue
    \ForAll{$q \in N(p) \; | \; \done{q} = \KwFalse$}
        \State c \atr\ $max(\data{$C_1$(p)}, \im{q})$
        \If{$c < \data{$C_1$(q)}$}
            \If{\HeapQueueContains{q}}
                \State \HeapQueueRemove{q}
            \EndIf
            \State $\data{$C_1$(q)} \atr\ c$
            \State \lab{q} \atr\ \lab{p}
            \State \parent{q} \atr\ p
            \State \HeapQueuePush{q, $\data{$C_1$(q)}$}
        \EndIf
    \EndFor
\EndWhile

\end{algorithmic}

Algoritmo 1: IFT for watershed

References

Source Code

 1 from ipdp.common import *
 2 from watershed.ift_k_py import ift_k
 3 
 4 def ift(im, offsets):
 5 
 6     # initialise variables
 7     ws = wsImage(im)
 8     N, im, lab, D = ws.begin(offsets)
 9 
10     # find minima
11     M = findMinima(im, N, D)
12 
13     ift_k(ws, im, M, N, D, lab)
14 
15     return ws.end()

References

[LotufoFalcaoISMM2000]===> R. Lotufo and A. Falcão, ``The ordered queue and the optimality of the watershed approaches,'' in Proceedings of the 5th International Symposium on Mathematical Morphology and its Applications to Image and Signal Processing, vol. 18. Kluwer Academic Publishers, June 2000, pp. 341–350. doi 10.1007/0-306-47025-X_37
[FalcaoStolfiLotufoPAMI2004]===> A. X. Falcão, J. Stolfi and R. A. Lotufo, ``The image foresting transform: theory, algorithms, and applications,'' Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 26, no. 1, pp. 19–29, 2004.