scikit-image

1
import numpy as np
2
import heapq
3

4

5
def _revalidate_node_edges(rag, node, heap_list):
6
    """Handles validation and invalidation of edges incident to a node.
7

8
    This function invalidates all existing edges incident on `node` and inserts
9
    new items in `heap_list` updated with the valid weights.
10

11
    rag : RAG
12
        The Region Adjacency Graph.
13
    node : int
14
        The id of the node whose incident edges are to be validated/invalidated
15
        .
16
    heap_list : list
17
        The list containing the existing heap of edges.
18
    """
19
    # networkx updates data dictionary if edge exists
20
    # this would mean we have to reposition these edges in
21
    # heap if their weight is updated.
22
    # instead we invalidate them
23

24
    for nbr in rag.neighbors(node):
25
        data = rag[node][nbr]
26
        try:
27
            # invalidate edges incident on `dst`, they have new weights
28
            data['heap item'][3] = False
29
            _invalidate_edge(rag, node, nbr)
30
        except KeyError:
31
            # will handle the case where the edge did not exist in the existing
32
            # graph
33
            pass
34

35
        wt = data['weight']
36
        heap_item = [wt, node, nbr, True]
37
        data['heap item'] = heap_item
38
        heapq.heappush(heap_list, heap_item)
39

40

41
def _rename_node(graph, node_id, copy_id):
42
    """Rename `node_id` in `graph` to `copy_id`."""
43

44
    graph._add_node_silent(copy_id)
45
    graph.nodes[copy_id].update(graph.nodes[node_id])
46

47
    for nbr in graph.neighbors(node_id):
48
        wt = graph[node_id][nbr]['weight']
49
        graph.add_edge(nbr, copy_id, {'weight': wt})
50

51
    graph.remove_node(node_id)
52

53

54
def _invalidate_edge(graph, n1, n2):
55
    """Invalidates the edge (n1, n2) in the heap."""
56
    graph[n1][n2]['heap item'][3] = False
57

58

59
def merge_hierarchical(
60
    labels, rag, thresh, rag_copy, in_place_merge, merge_func, weight_func
61
):
62
    """Perform hierarchical merging of a RAG.
63

64
    Greedily merges the most similar pair of nodes until no edges lower than
65
    `thresh` remain.
66

67
    Parameters
68
    ----------
69
    labels : ndarray
70
        The array of labels.
71
    rag : RAG
72
        The Region Adjacency Graph.
73
    thresh : float
74
        Regions connected by an edge with weight smaller than `thresh` are
75
        merged.
76
    rag_copy : bool
77
        If set, the RAG copied before modifying.
78
    in_place_merge : bool
79
        If set, the nodes are merged in place. Otherwise, a new node is
80
        created for each merge..
81
    merge_func : callable
82
        This function is called before merging two nodes. For the RAG `graph`
83
        while merging `src` and `dst`, it is called as follows
84
        ``merge_func(graph, src, dst)``.
85
    weight_func : callable
86
        The function to compute the new weights of the nodes adjacent to the
87
        merged node. This is directly supplied as the argument `weight_func`
88
        to `merge_nodes`.
89

90
    Returns
91
    -------
92
    out : ndarray
93
        The new labeled array.
94

95
    """
96
    if rag_copy:
97
        rag = rag.copy()
98

99
    edge_heap = []
100
    for n1, n2, data in rag.edges(data=True):
101
        # Push a valid edge in the heap
102
        wt = data['weight']
103
        heap_item = [wt, n1, n2, True]
104
        heapq.heappush(edge_heap, heap_item)
105

106
        # Reference to the heap item in the graph
107
        data['heap item'] = heap_item
108

109
    while len(edge_heap) > 0 and edge_heap[0][0] < thresh:
110
        _, n1, n2, valid = heapq.heappop(edge_heap)
111

112
        # Ensure popped edge is valid, if not, the edge is discarded
113
        if valid:
114
            # Invalidate all neighbors of `src` before its deleted
115

116
            for nbr in rag.neighbors(n1):
117
                _invalidate_edge(rag, n1, nbr)
118

119
            for nbr in rag.neighbors(n2):
120
                _invalidate_edge(rag, n2, nbr)
121

122
            if not in_place_merge:
123
                next_id = rag.next_id()
124
                _rename_node(rag, n2, next_id)
125
                src, dst = n1, next_id
126
            else:
127
                src, dst = n1, n2
128

129
            merge_func(rag, src, dst)
130
            new_id = rag.merge_nodes(src, dst, weight_func)
131
            _revalidate_node_edges(rag, new_id, edge_heap)
132

133
    label_map = np.arange(labels.max() + 1)
134
    for ix, (n, d) in enumerate(rag.nodes(data=True)):
135
        for label in d['labels']:
136
            label_map[label] = ix
137

138
    return label_map[labels]
139