forked from daviddaiweizhang/istar
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathconnected_components.py
122 lines (104 loc) · 3.87 KB
/
connected_components.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
import numpy as np
from scipy.ndimage import label as label_connected
from utils import sort_labels, get_most_frequent
def get_largest_connected(labels):
labels = label_connected(labels)[0]
labels -= 1
labels = sort_labels(labels)[0]
labels = labels == 0
return labels
def get_adjacent(ind):
# return the eight adjacent indices
adj = np.meshgrid([-1, 0, 1], [-1, 0, 1], indexing='ij')
adj = np.stack(adj, -1)
adj = adj.reshape(-1, adj.shape[-1])
adj = adj[(adj != 0).any(-1)]
adj += ind
return adj
def split_by_connected_size_single(labels, min_size):
# return labels of small and large connected components
# labels are binary
labels = label_connected(labels)[0]
labels -= 1
labels = sort_labels(labels)[0]
counts = np.unique(labels[labels >= 0], return_counts=True)[1]
cut = np.sum(counts >= min_size)
small = labels - cut
small[small < 0] = -1
large = labels.copy()
large[labels >= cut] = -1
return small, large
def split_by_connected_size(labels, min_size):
# return labels of small and large connected components
# labels can be multi-categorical
labs_uniq = np.unique(labels[labels >= 0])
small = np.full_like(labels, -1)
large = np.full_like(labels, -1)
for lab in labs_uniq:
isin = labels == lab
sma, lar = split_by_connected_size_single(isin, min_size)
issma = sma >= 0
islar = lar >= 0
small[issma] = sma[issma] + small.max() + 1
large[islar] = lar[islar] + large.max() + 1
return small, large
def relabel_small_connected(labels, min_size):
# reassign labels of small connected components
labels = labels.copy()
small, __ = split_by_connected_size(labels, min_size)
small = sort_labels(small, descending=False)[0]
small_uniq = np.unique(small[small >= 0])
lab_na = min(-1, labels.min() - 1)
for lab_small in small_uniq:
isin = small == lab_small
lab = labels[isin][0]
# find adjacent labels
indices = np.stack(np.where(isin), -1)
labs_adj = []
labs_small_adj = []
for ind in indices:
adj = get_adjacent(ind)
is_within = np.logical_and(
(adj < labels.shape).all(-1),
(adj >= 0).all(-1))
adj[~is_within] = 0 # dummy index for out-of-bound
la = labels[adj[:, 0], adj[:, 1]]
lsa = small[adj[:, 0], adj[:, 1]]
la[~is_within] = lab_na
lsa[~is_within] = lab_na
labs_adj.append(la)
labs_small_adj.append(lsa)
labs_adj = np.stack(labs_adj)
labs_small_adj = np.stack(labs_small_adj)
# eliminate background and identical labels
is_other = (labs_adj >= 0) * (labs_adj != lab)
if is_other.any():
# find most frequent adjacent labels
lab_new = get_most_frequent(labs_adj[is_other])
# get location of new label
i_new, i_adj_new = np.stack(
np.where(labs_adj == lab_new), -1)[0]
ind_new = get_adjacent(indices[i_new])[i_adj_new]
# update small components
lab_small_new = small[ind_new[0], ind_new[1]]
else:
lab_new = lab
lab_small_new = lab_small
# relabel to most frequent neighboring label
labels[isin] = lab_new
small[isin] = lab_small_new
return labels
def cluster_connected(labels):
# subcluster labels by connectedness
labels = labels.copy()
isfg = labels >= 0
labels_sub = np.full_like(labels, -1)
labels_sub[~isfg] = labels[~isfg]
labs_uniq = np.unique(labels[isfg])
for lab in labs_uniq:
isin = labels == lab
sublabs = label_connected(isin)[0] - 1
sublabs = sort_labels(sublabs)[0]
labels_sub[isin] = sublabs[isin]
labels_sub[~isfg] = labels[~isfg]
return labels_sub