imsegm.graph_cuts module

Framework for GraphCut

Copyright (C) 2014-2018 Jiri Borovec <jiri.borovec@fel.cvut.cz>

imsegm.graph_cuts.compute_edge_model(edges, proba, metric='l_T')

compute the edge weight from the feature space

small differences are large weights, diff close 0 appears to be 1

setting min weight ~ max difference in proba as weight meaning if two vertexes have same proba to all classes the diff is 0 and weights are 1 on the other hand if there is [0.7, 0.1, 0.2] and [0.2, 0.7, 0.1] gives large diff [0.5, 0.6, 0.1] in 1. and 2. diff and zero in 3 leading to weights [0.5, 0.4, 0.9] and so we take the min values

Parameters

• int)] edges ([(int,) – edges

• proba ([[float]]) – probablilitirs

• metric (str) – define metric

Return list(float)

>>> segments = np.array([[0] * 3 + [1] * 5 + [2] * 4,
...                      [4] * 4 + [5] * 5 + [6] * 3])
>>> edges = np.array(get_vertexes_edges(segments)[1], dtype=int)
>>> np.random.seed(0)
>>> img = np.random.random(segments.shape + (3,)) * 255
>>> proba = np.random.random((segments.max() + 1, 2))
>>> weights = compute_edge_model(edges, proba, metric='l1')
>>> np.round(weights, 3).tolist()
[0.002, 0.015, 0.001, 0.002, 0.0, 0.002, 0.015, 0.034, 0.001]
>>> weights = compute_edge_model(edges, proba, metric='l2')
>>> np.round(weights, 3).tolist()
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.002, 0.005, 0.0]
>>> weights = compute_edge_model(edges, proba, metric='lT')
>>> np.round(weights, 3).tolist()
[0.0, 0.002, 0.0, 0.005, 0.0, 0.0, 0.101, 0.092, 0.001]

imsegm.graph_cuts.compute_edge_weights(segments, image=None, features=None, proba=None, edge_type='')

pp 32, http://www.coe.utah.edu/~cs7640/readings/graph_cuts_intro.pdf exp(- norm value diff) * (geom dist vertex)**-1

Parameters

• segments (ndarry) – superpixels

• image (ndarry) – input image

• features (ndarry) – features for each segment (superpixel)

• proba (ndarry) – probability of each superpixel and class

• edge_type (str) – contains edge type, if ‘model’, after ‘_’ you can specify the metric, eg. ‘model_l2’

Return [[int, int]], [float]

>>> segments = np.array([[0] * 3 + [1] * 5 + [2] * 4,
...                      [4] * 4 + [5] * 5 + [6] * 3])
>>> np.random.seed(0)
>>> img = np.random.random(segments.shape + (3,)) * 255
>>> features = np.random.random((segments.max() + 1, 15)) * 10
>>> proba = np.random.random((segments.max() + 1, 2))
>>> edges, weights = compute_edge_weights(segments)
>>> edges.tolist()
[[0, 1], [1, 2], [0, 4], [1, 4], [1, 5], [2, 5], [4, 5], [2, 6], [5, 6]]
>>> np.round(weights, 2).tolist()
[1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0]
>>> edges, weights = compute_edge_weights(segments, image=img,
...                                        edge_type='spatial')
>>> np.round(weights, 3).tolist()
[0.776, 0.69, 2.776, 0.853, 2.194, 0.853, 0.69, 2.776, 0.776]
>>> edges, weights = compute_edge_weights(segments, image=img,
...                                        edge_type='color')
>>> np.round(weights, 3).tolist()
[0.06, 0.002, 0.001, 0.001, 0.001, 0.009, 0.001, 0.019, 0.044]
>>> edges, weights = compute_edge_weights(segments, features=features,
...                                        edge_type='features')
>>> np.round(weights, 3).tolist()
[0.031, 0.005, 0.051, 0.032, 0.096, 0.013, 0.018, 0.033, 0.013]
>>> edges, weights = compute_edge_weights(segments, proba=proba,
...                                        edge_type='model')
>>> np.round(weights, 3).tolist()
[0.001, 0.028, 1.122, 0.038, 0.117, 0.688, 0.487, 1.152, 0.282]

imsegm.graph_cuts.compute_multivarian_otsu(features)

compute otsu individually over each sample dimension WARNING: this compute only localy and since it does compare all combinations of orienting the asign for tight cases it may not decide

Parameters

features (ndarray) –

Return list(bool)

>>> np.random.seed(0)
>>> fts = np.row_stack([np.random.random((5, 3)) - 1,
...                     np.random.random((5, 3)) + 1])
>>> fts[:, 1] = - fts[:, 1]
>>> compute_multivarian_otsu(fts).astype(int)
array([0, 0, 0, 0, 0, 1, 1, 1, 1, 1])

imsegm.graph_cuts.compute_pairwise_cost(gc_regul, proba_shape, max_pairwise_cost=100000.0)

wrapper for creating GC pairwise cost

Parameters

• gc_regul –

• proba_shape (tuple(int,int)) –

• max_pairwise_cost (float) –

Return ndarray

imsegm.graph_cuts.compute_pairwise_cost_from_transitions(trans, min_prob=1e-09)

compute pairwise cost from segments-label transitions

Parameters

• trans (ndarray) –

• min_prob (float) – minimal probability

Return ndarray

>>> trans = np.array([[ 25.,   5.,  0.],
...                   [  5.,  10.,  8.],
...                   [  0.,   8.,  30.]])
>>> np.round(compute_pairwise_cost_from_transitions(trans), 3)
array([[  0.182,   1.526,  20.723],
       [  1.526,   0.833,   1.056],
       [ 20.723,   1.056,   0.236]])
>>> np.round(compute_pairwise_cost_from_transitions(np.ones(3)), 2)
array([[ 1.1,  1.1,  1.1],
       [ 1.1,  1.1,  1.1],
       [ 1.1,  1.1,  1.1]])
>>> np.round(compute_pairwise_cost_from_transitions(np.eye(3)), 2)
array([[  0.  ,  20.72,  20.72],
       [ 20.72,   0.  ,  20.72],
       [ 20.72,  20.72,   0.  ]])

imsegm.graph_cuts.compute_spatial_dist(centres, edges, relative=False)

compute spatial distance between all neighbouring segments

Parameters

• int]] centres ([[int,) – superpixel centres

• int]] edges ([[int,) –

• relative (bool) – normalise the distances to mean distance

Returns

>>> from imsegm.superpixels import superpixel_centers
>>> segments = np.array([[0] * 3 + [1] * 2 + [2] * 5,
...                      [4] * 4 + [5] * 2 + [6] * 4])
>>> centres = superpixel_centers(segments)
>>> edges = [[0, 1], [1, 2], [4, 5], [5, 6], [0, 4], [1, 5], [2, 6]]
>>> np.round(compute_spatial_dist(centres, edges), 2)
array([ 2.5 ,  3.5 ,  3.  ,  3.  ,  1.12,  1.41,  1.12])
>>> np.round(compute_spatial_dist(centres, edges, relative=True), 2)
array([ 1.12,  1.57,  1.34,  1.34,  0.5 ,  0.63,  0.5 ])

imsegm.graph_cuts.compute_unary_cost(proba, min_prob=0.01)

compute the GC unary cost with some threshold on minimal values

Parameters

• proba (ndarray) –

• min_prob (float) –

Return ndarray

>>> compute_unary_cost(np.random.random((50, 2))).shape
(50, 2)

imsegm.graph_cuts.count_label_transitions_connected_segments(dict_slics, dict_labels, nb_labels=None)

count transitions among labeled segment in between connected segments

Parameters

• dict_slics (dict(list(list(int)))) – image name: ndarray

• dict_labels (dict(list(int))) – image name: ndarray

• nb_labels (int) –

Return ndarray

matrix of shape nb_labels x nb_labels

>>> dict_slics = {'a':
...        np.array([[0] * 3 + [1] * 3 + [2] * 3 + [3] * 3 + [4] * 3,
...                  [5] * 3 + [6] * 3 + [7] * 3 + [8] * 3 + [9] * 3])}
>>> dict_labels = {'a': np.array([0, 0, 1, 1, 2, 0, 1, 1, 0, 2])}
>>> dict_slics['a']
array([[0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4],
       [5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]])
>>> dict_labels['a'][dict_slics['a']]
array([[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2],
       [0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 2, 2, 2]])
>>> count_label_transitions_connected_segments(dict_slics, dict_labels)
array([[ 2.,  5.,  1.],
       [ 5.,  3.,  1.],
       [ 1.,  1.,  1.]])

imsegm.graph_cuts.create_pairwise_matrix(gc_regul, nb_classes)

wrapper for create pairwise matrix - uniform or specific

Parameters

• gc_regul –

• nb_classes (int) –

Returns

np.array<nb_classes, nb_classes>

>>> create_pairwise_matrix(0.6, 3)
array([[ 0. ,  0.6,  0.6],
       [ 0.6,  0. ,  0.6],
       [ 0.6,  0.6,  0. ]])
>>> create_pairwise_matrix([((1, 2), 0.5), ((0, 2), 0.7)], 3)
array([[ 0. ,  1. ,  0.7],
       [ 1. ,  0. ,  0.5],
       [ 0.7,  0.5,  0. ]])
>>> trans = np.array([[ 341.,   31.,   22.],
...                   [  31.,   12.,   21.],
...                   [  22.,   21.,   44.]])
>>> gc_regul = compute_pairwise_cost_from_transitions(trans)
>>> np.round(create_pairwise_matrix(gc_regul, len(gc_regul)), 2)
array([[ 0.  ,  0.58,  1.23],
       [ 0.58,  1.53,  0.97],
       [ 1.23,  0.97,  0.54]])

imsegm.graph_cuts.create_pairwise_matrix_specif(pos_weights, nb_classes=None)

create GC pairwise matrix wih specific values on particular positions

Parameters

• int), float)] pos_weights ([((int,) – pair of coord in matrix and values

• nb_classes (int) – initialise as empty matrix

Returns

np.array<nb_classes, nb_classes>

>>> create_pairwise_matrix_specif([((1, 2), 0.5), ((1, 0), 0.7)], 4)
array([[ 0. ,  0.7,  1. ,  1. ],
       [ 0.7,  0. ,  0.5,  1. ],
       [ 1. ,  0.5,  0. ,  1. ],
       [ 1. ,  1. ,  1. ,  0. ]])
>>> create_pairwise_matrix_specif([((1, 2), 0.5), ((0, 2), 0.7)])
array([[ 0. ,  1. ,  0.7],
       [ 1. ,  0. ,  0.5],
       [ 0.7,  0.5,  0. ]])

imsegm.graph_cuts.create_pairwise_matrix_uniform(gc_reg, nb_classes)

create GC pairwise matrix - uniform with zeros on diagonal

Parameters

• gc_reg (float) –

• nb_classes (int) –

Return ndarray

>>> create_pairwise_matrix_uniform(0.2, 3)
array([[ 0. ,  0.2,  0.2],
       [ 0.2,  0. ,  0.2],
       [ 0.2,  0.2,  0. ]])

imsegm.graph_cuts.estim_class_model(features, nb_classes, estim_model='GMM', pca_coef=None, use_scaler=True, max_iter=99)

create pipeline (scaler, PCA, model) over several options how to cluster samples and fit it on data

Parameters

• features (ndarray) –

• nb_classes (int) – number of expected classes

• pca_coef (float) – range (0, 1) or None

• use_scaler (bool) – whether use a scaler

• estim_model (str) – used model

• max_iter (int) –

Returns

>>> np.random.seed(0)
>>> fts = np.row_stack([np.random.random((50, 3)) - 1,
...                     np.random.random((50, 3)) + 1])
>>> mm = estim_class_model(fts, 2)
>>> mm.predict_proba(fts).shape
(100, 2)
>>> mm = estim_class_model(fts, 2, estim_model='GMM_kmeans',
...                         pca_coef=0.95, max_iter=3)
>>> mm.predict_proba(fts).shape
(100, 2)
>>> mm = estim_class_model(fts, 2, estim_model='GMM_Otsu', max_iter=3)
>>> mm.predict_proba(fts).shape
(100, 2)
>>> mm = estim_class_model(fts, 2, estim_model='kmeans_quantiles',
...                         use_scaler=False, max_iter=3)
>>> mm.predict_proba(fts).shape
(100, 2)
>>> mm = estim_class_model(fts, 2, estim_model='BGM', max_iter=3)
>>> mm.predict_proba(fts).shape
(100, 2)
>>> mm = estim_class_model(fts, 2, estim_model='Otsu', max_iter=3)
>>> mm.predict_proba(fts).shape
(100, 2)

imsegm.graph_cuts.estim_class_model_gmm(features, nb_classes, init='kmeans')

from all features estimate Gaussian Mixture Model and assuming each cluster is a single class compute probability that each feature belongs to each class

Parameters

• features ([[float]]) – list of features per segment

• nb_classes (int) – number of classes

• init (int) – initialisation

Return [[float]]

probabilities that each feature belongs to each class

>>> np.random.seed(0)
>>> fts = np.row_stack([np.random.random((50, 3)) - 1,
...                     np.random.random((50, 3)) + 1])
>>> mm = estim_class_model_gmm(fts, 2)
>>> mm.predict_proba(fts).shape
(100, 2)

imsegm.graph_cuts.estim_class_model_kmeans(features, nb_classes, init_type='k-means++', max_iter=99)

from all features estimate Gaussian from k-means clustering

Parameters

• features ([[float]]) – list of features per segment

• nb_classes (int) – number of classes

• init_type (str) – initialization

• max_iter (int) – maximal number of iterations

Return [[float]]

probabilities that each feature belongs to each class

>>> np.random.seed(0)
>>> fts = np.row_stack([np.random.random((50, 3)) - 1,
...                     np.random.random((50, 3)) + 1])
>>> mm, y = estim_class_model_kmeans(fts, 2, max_iter=9)
>>> y.shape
(100,)
>>> mm.predict_proba(fts).shape
(100, 2)

imsegm.graph_cuts.estim_gmm_params(features, prob)

with given soft labeling (take the maxim) get the GMM parameters

Parameters

• features (ndarray) –

• prob (ndarray) –

Returns

>>> np.random.seed(0)
>>> prob = np.array([[1, 0]] * 30 + [[0, 1]] * 40)
>>> fts = prob + np.random.random(prob.shape)
>>> mm = estim_gmm_params(fts, prob)
>>> mm['weights']
[0.42857142857142855, 0.5714285714285714]
>>> mm['means']
array([[ 1.49537196,  0.53745455],
       [ 0.54199936,  1.42606497]])

imsegm.graph_cuts.get_vertexes_edges(segments)

wrapper - get list of vertexes edges for 2D / 3D images

Parameters

segments (ndarray) –

Returns

imsegm.graph_cuts.insert_gc_debug_images(debug_visual, segments, graph_labels, unary_cost, edges, edge_weights)

wrapper for placing intermediate variable to a dictionary

imsegm.graph_cuts.segment_graph_cut_general(segments, proba, image=None, features=None, gc_regul=1.0, edge_type='model', edge_cost=1.0, debug_visual=None)

segment the image segmented via superpixels and estimated features

Parameters

• features (ndarray) – features sor each instance

• segments (ndarray) – segmentation mapping each pixel into a class

• image (ndarray) – image

• proba (ndarray) – probabilities that each feature belongs to each class

• edge_type (str) –

• edge_cost (str) –

• gc_regul – regularisation for GrphCut

• debug_visual (dict) –

Return list(int)

labelling by resulting classes

>>> np.random.seed(0)
>>> segments = np.array([[0] * 3 + [2] * 3 + [4] * 3 + [6] * 3 + [8] * 3,
...                      [1] * 3 + [3] * 3 + [5] * 3 + [7] * 3 + [9] * 3])
>>> proba = np.array([[0.1] * 6 + [0.9] * 4,
...                   [0.9] * 6 + [0.1] * 4], dtype=float).T
>>> proba += (0.5 - np.random.random(proba.shape)) * 0.2
>>> compute_unary_cost(proba)
array([[ 2.40531242,  0.15436155],
       [ 2.53266106,  0.11538463],
       [ 2.1604864 ,  0.13831863],
       [ 2.18495711,  0.19644636],
       [ 4.60517019,  0.0797884 ],
       [ 3.17833405,  0.11180231],
       [ 0.12059702,  4.20769207],
       [ 0.0143091 ,  1.70059894],
       [ 0.01005034,  3.39692559],
       [ 0.16916609,  3.64975219]])
>>> segment_graph_cut_general(segments, proba, gc_regul=0., edge_type='')
array([1, 1, 1, 1, 1, 1, 0, 0, 0, 0], dtype=int32)
>>> labels = segment_graph_cut_general(segments, proba, gc_regul=1.,
...                                    edge_type='spatial')
>>> labels[segments]
array([[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
       [1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]], dtype=int32)
>>> slic = np.array([[0] * 4 + [1] * 6 + [2] * 4,
...                  [3] * 5 + [4] * 4 + [5] * 5])
>>> proba = np.array([[1] * 3 + [0] * 3, [0] * 3 + [1] * 3], dtype=float).T
>>> proba += np.random.random(proba.shape) / 2.
>>> np.argmax(proba, axis=1)
array([0, 0, 0, 1, 1, 1])
>>> debug_visual = dict()
>>> segment_graph_cut_general(slic, proba, gc_regul=0., edge_type='',
...                           debug_visual=debug_visual)
array([0, 0, 0, 1, 1, 1], dtype=int32)
>>> sorted(debug_visual.keys())  
['edge_weights', 'edges', 'img_graph_edges', 'img_graph_segm',
 'imgs_unary_cost', 'segments']

imsegm.graph_cuts.DEFAULT_GC_ITERATIONS = 25

define munber of iteration in Grap-Cut optimization

imsegm.graph_cuts.MAX_PAIRWISE_COST = 100000.0

define maximal value of parwise (smoothness) term in Graph-Cut

imsegm.graph_cuts.MIN_MAX_EDGE_WEIGHT = 1000.0

max is this value and min is inverse (1 / val)

imsegm.graph_cuts.MIN_UNARY_PROB = 0.01

define minimal value of unary (being a class) term in Graph-Cut