Shortestpaths algorithms¶

Performs the shortest path classification from the seeds nodes using the image foresting transform algorithm 1. 

Performs the image foresting transform classification from the seeds nodes with dynamic arcweights 2. 

Computes the euclidean distance transform using the IFT algorithm 3. 

Computes the watershed transform on grayscales images from minimum using the IFT algorithm 5. 

Performs the orinted imageforesting transform described in 6. 

pyift.shortestpath.
seed_competition
(seeds: numpy.ndarray, image: Optional[numpy.ndarray] = None, graph: Optional[scipy.sparse.csr.csr_matrix] = None, image_3d: bool = False) → Tuple[numpy.ndarray, numpy.ndarray, numpy.ndarray, numpy.ndarray][source]¶ Performs the shortest path classification from the seeds nodes using the image foresting transform algorithm 1.
 Parameters
seeds (array_like) – Positive values are the labels and shortest path sources, nonpositives are ignored.
image (array_like, optional) – Image data, seed competition is performed in the image grid graph, mutual exclusive with graph.
graph (csr_matrix, optional) – Sparse graph, seed competition is performed in the given graph, mutual exclusive with image.
image_3d (bool, optional) – Indicates if it is a 3D image or a 2D image with multiple bands, by default ‘False’
 Returns
Image foresting transform costs, roots, predecessors and labels maps.
 Return type
array_like, array_like, array_like, array_like
Examples
Image grid:
>>> import numpy as np >>> from pyift.shortestpath import seed_competition >>> >>> seeds = np.array([[1, 0, 0], >>> [0, 0, 0], >>> [0, 2, 0]]) >>> image = np.empty((3, 3, 2)) >>> image[:, :, 0] = np.array([[1, 2, 3], >>> [2, 3, 4], >>> [2, 2, 3]]) >>> image[:, :, 1] = np.array([[5, 6, 8], >>> [6, 8, 9], >>> [8, 9, 9]]) >>> seed_competition(seeds, image=image)
Sparse graph:
>>> import numpy as np >>> from scipy.sparse import csgraph >>> from pyift.shortestpath import seed_competition >>> >>> seeds = np.array([1, 0, 0, 0, 2]) >>> graph = csgraph.csgraph_from_dense([[0, 3, 2, 0, 0], >>> [3, 0, 0, 3, 1], >>> [2, 0, 0, 3, 0], >>> [0, 3, 3, 0, 2], >>> [0, 1, 0, 2, 0]]) >>> seed_competition(seeds, graph=graph)
References

pyift.shortestpath.
dynamic_arc_weight
(seeds: numpy.ndarray, image: numpy.ndarray, image_3d: bool = False, mode: str = 'root', alpha: float = 0.5) → Tuple[numpy.ndarray, numpy.ndarray, numpy.ndarray, numpy.ndarray, Dict[Tuple, numpy.ndarray]][source]¶ Performs the image foresting transform classification from the seeds nodes with dynamic arcweights 2.
 Parameters
seeds (array_like) – Positive values are the labels and shortest path sources, nonpositives are ignored.
image (array_like, optional) – Image data, seed competition is performed in the image grid graph.
image_3d (bool, optional) – Indicates if it is a 3D image or a 2D image with multiple bands, by default ‘False’.
mode ({'root', 'label', 'exp'}, default='root') – Indicates the average computation policy.
alpha (float, optional) – Parameter of weight decay for exponential averaging, only valid when mode == ‘exp’.
 Returns
Image foresting transform costs, roots, predecessors, labels maps and a dictionary containing the average and size of each optimumpath tree.
 Return type
array_like, array_like, array_like, array_like, Union[array_like, dict]
Examples
>>> import numpy as np >>> from pyift.shortestpath import dynamic_arc_weight >>> >>> seeds = np.array([[1, 0, 0], >>> [0, 0, 0], >>> [0, 2, 0]]) >>> image = np.empty((3, 3, 2)) >>> image[:, :, 0] = np.array([[1, 2, 3], >>> [2, 3, 4], >>> [2, 2, 3]]) >>> image[:, :, 1] = np.array([[5, 6, 8], >>> [6, 8, 9], >>> [8, 9, 9]]) >>> dynamic_arc_weight(seeds, image)
References

pyift.shortestpath.
distance_transform_edt
(mask: numpy.ndarray, scales: Optional[numpy.ndarray] = None) → Tuple[numpy.ndarray, numpy.ndarray][source]¶ Computes the euclidean distance transform using the IFT algorithm 3.
 Parameters
mask (array_like) – Binary mask of regions to compute the EDT from border.
scales (array_like, optional) – Distance scale for each image axis.
 Returns
Euclidean distance transform mapping from boundaries.
 Return type
array_like
Examples
>>> import numpy as np >>> from pyift.shortestpath import distance_transform_edt >>> >>> mask = np.array([[0, 0, 0, 0, 0, 0], >>> [0, 1, 0, 1, 0, 0], >>> [0, 1, 1, 1, 1, 0], >>> [0, 1, 1, 1, 1, 0], >>> [0, 1, 1, 0, 1, 0], >>> [0, 0, 0, 0, 0, 0]], dtype=bool) >>> >>> distance_transform_edt(mask)
References

pyift.shortestpath.
watershed_from_minima
(image: numpy.ndarray, mask: Optional[numpy.ndarray] = None, H_minima: float = 1.0, compactness: float = 0.0, scales: Optional[numpy.ndarray] = None) → Tuple[numpy.ndarray, numpy.ndarray][source]¶ Computes the watershed transform on grayscales images from minimum using the IFT algorithm 5.
 Parameters
image (array_like) – Grayscale 2D or 3D image.
mask (array_like, optional) – Binary mask of regions to compute the watershed transform.
H_minima (array_like, float) – Dynamics threshold for watershed from minima as described in 4. The greater the value the more the neighboring minima will merge into a single region.
compactness (float, optional) – Optional parameter to adjust tradeoff between distancing from minimum (compact segment) and following the image topology.
scales (array_like, optional) – Scales of image dimensions, useful for anisotropic data.
 Returns
Optimumpath costs and roots (minima) from watershed basins.
 Return type
array_like, array_like
Examples
>>> import numpy as np >>> from pyift.shortestpath import watershed_from_minima >>> >>> image = np.array([[7, 8, 9, 8, 8, 8], >>> [6, 3, 9, 0, 9, 8], >>> [4, 1, 6, 1, 1, 8], >>> [3, 3, 5, 4, 4, 8], >>> [1, 0, 7, 2, 2, 8], >>> [6, 8, 9, 8, 9, 9]]) >>> >>> watershed_from_minima(image)
References
 4
Najman, Laurent, and Michel Schmitt. “Geodesic saliency of watershed contours and hierarchical segmentation.” IEEE Transactions on pattern analysis and machine intelligence 18, no. 12 (1996): 11631173.
 5(1,2)
Falcão, Alexandre X., Jorge Stolfi, and Roberto de Alencar Lotufo. “The image foresting transform: Theory, algorithms, and applications.” IEEE transactions on pattern analysis and machine intelligence 26.1 (2004): 1929.

pyift.shortestpath.
oriented_seed_competition
(seeds: numpy.ndarray, image: numpy.ndarray, alpha: float, background_label: int, handicap: float = 0.0, mask: Optional[numpy.ndarray] = None) → Tuple[numpy.ndarray, numpy.ndarray, numpy.ndarray, numpy.ndarray][source]¶ Performs the orinted imageforesting transform described in 6.
 Parameters
seeds (array_like) – Positive values are the labels and shortest path sources, nonpositives are ignored.
image (array_like) – Image data, seed competition is performed in the image grid graph, mutual exclusive with graph.
alpha (float) – Parameter for controling path orientation, must be between 1 and 1. A negative alpha benefits transitions from brighter to darker regions for nonbackground labels. A positive alpha benefits transitions from darker to brighter regions for nonbackground labels. The opposite is valid for the background label. If alpha is zero no transitions benefits.
background_label (int) – Indicates the background label, it can a negative value to avoid inverted orientations for the background.
handicap (float) – Similar to hbasins penalization, it allows seeds (minima) with small differences to be conquered.
 Returns
Oriented image foresting transform costs, roots, predecessors and labels maps.
 Return type
array_like, array_like, array_like, array_like
Examples
>>> image = np.array([[18, 17, 16, 15, 14], >>> [19, 21, 19, 17, 13], >>> [20, 21, 22, 15, 12], >>> [9, 9, 11, 13, 11], >>> [6, 7, 8, 9, 10]]) >>> >>> seeds = np.array([[0, 0, 0, 0, 0], >>> [0, 0, 0, 0, 0], >>> [2, 0, 0, 0, 0], >>> [1, 1, 0, 0, 0], >>> [0, 0, 0, 0, 0]]) >>> >>> mask = np.ones(seeds.shape, dtype=bool) >>> mask[2, 1:3] = False >>> alpha = 0.9 >>> >>> costs, roots, preds, labels = sp.oriented_seed_competition(seeds, image, background_label=1, >>> alpha=alpha, handicap=0.1, mask=mask)
References