Shortest-paths 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 arc-weights 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 image-foresting 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, non-positives 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 arc-weights 2.
- Parameters
seeds (array_like) – Positive values are the labels and shortest path sources, non-positives 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 optimum-path 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 trade-off between distancing from minimum (compact segment) and following the image topology.
scales (array_like, optional) – Scales of image dimensions, useful for anisotropic data.
- Returns
Optimum-path 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): 1163-1173.
- 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): 19-29.
-
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 image-foresting transform described in 6.
- Parameters
seeds (array_like) – Positive values are the labels and shortest path sources, non-positives 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 non-background labels. A positive alpha benefits transitions from darker to brighter regions for non-background 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 h-basins 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