Shortest-paths algorithms

seed_competition(seeds[, image, graph, image_3d])

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

dynamic_arc_weight(seeds, image[, image_3d, …])

Performs the image foresting transform classification from the seeds nodes with dynamic arc-weights 2.

distance_transform_edt(mask[, scales])

Computes the euclidean distance transform using the IFT algorithm 3.

watershed_from_minima(image[, mask, …])

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

oriented_seed_competition(seeds, image, …)

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

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

2(1,2)

Bragantini, Jordão, et al. “Graph-based image segmentation using dynamic trees.” Iberoamerican Congress on Pattern Recognition. Springer, Cham, 2018.

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

3(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.watershed_from_minima(image: numpy.ndarray, mask: Optional[numpy.ndarray] = None, H_minima: Union[float, numpy.ndarray] = 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

6(1,2)

Miranda, Paulo AV, and Lucy AC Mansilla. “Oriented image foresting transform segmentation by seed competition.” IEEE Transactions on Image Processing 23, no. 1 (2013): 389-398.