scikit-image

1
import networkx as nx
2
import numpy as np
3
from scipy import sparse
4
from . import _ncut_cy
5

6

7
def DW_matrices(graph):
8
    """Returns the diagonal and weight matrices of a graph.
9

10
    Parameters
11
    ----------
12
    graph : RAG
13
        A Region Adjacency Graph.
14

15
    Returns
16
    -------
17
    D : csc_matrix
18
        The diagonal matrix of the graph. ``D[i, i]`` is the sum of weights of
19
        all edges incident on `i`. All other entries are `0`.
20
    W : csc_matrix
21
        The weight matrix of the graph. ``W[i, j]`` is the weight of the edge
22
        joining `i` to `j`.
23
    """
24
    # sparse.eighsh is most efficient with CSC-formatted input
25
    W = nx.to_scipy_sparse_array(graph, format='csc')
26
    entries = W.sum(axis=0)
27
    D = sparse.dia_matrix((entries, 0), shape=W.shape).tocsc()
28

29
    return D, W
30

31

32
def ncut_cost(cut, D, W):
33
    """Returns the N-cut cost of a bi-partition of a graph.
34

35
    Parameters
36
    ----------
37
    cut : ndarray
38
        The mask for the nodes in the graph. Nodes corresponding to a `True`
39
        value are in one set.
40
    D : csc_matrix
41
        The diagonal matrix of the graph.
42
    W : csc_matrix
43
        The weight matrix of the graph.
44

45
    Returns
46
    -------
47
    cost : float
48
        The cost of performing the N-cut.
49

50
    References
51
    ----------
52
    .. [1] Normalized Cuts and Image Segmentation, Jianbo Shi and
53
           Jitendra Malik, IEEE Transactions on Pattern Analysis and Machine
54
           Intelligence, Page 889, Equation 2.
55
    """
56
    cut = np.array(cut)
57
    cut_cost = _ncut_cy.cut_cost(cut, W.data, W.indices, W.indptr, num_cols=W.shape[0])
58

59
    # D has elements only along the diagonal, one per node, so we can directly
60
    # index the data attribute with cut.
61
    assoc_a = D.data[cut].sum()
62
    assoc_b = D.data[~cut].sum()
63

64
    return (cut_cost / assoc_a) + (cut_cost / assoc_b)
65