Debian Codegraph @

dask_image/ndmeasure/_utils/_label.py

raw
1 # -*- coding: utf-8 -*-
2
3 import operator
4
5 import dask
6 import dask.array as da
7 import numpy as np
8 import scipy.ndimage
9 import scipy.sparse
10 import scipy.sparse.csgraph
11
12
13 def _get_ndimage_label_dtype():
14 return scipy.ndimage.label([1, 0, 1])[0].dtype
15
16
17 LABEL_DTYPE = _get_ndimage_label_dtype()
18
19
20 def _get_connected_components_dtype():
21 a = np.empty((0, 0), dtype=int)
22 return scipy.sparse.csgraph.connected_components(a)[1].dtype
23
24
25 CONN_COMP_DTYPE = _get_connected_components_dtype()
26
27
28 def relabel_blocks(block_labeled, new_labeling):
29 """
30 Relabel a block-labeled array based on ``new_labeling``.
31
32 Parameters
33 ----------
34 block_labeled : array of int
35 The input label array.
36 new_labeling : 1D array of int
37 A new labeling, such that ``labeling[i] = j`` implies that
38 any element in ``array`` valued ``i`` should be relabeled to ``j``.
39
40 Returns
41 -------
42 relabeled : array of int, same shape as ``array``
43 The relabeled input array.
44 """
45 new_labeling = new_labeling.astype(LABEL_DTYPE)
46 relabeled = da.map_blocks(operator.getitem,
47 new_labeling,
48 block_labeled,
49 dtype=LABEL_DTYPE,
50 chunks=block_labeled.chunks)
51 return relabeled
52
53
54 def _unique_axis(a, axis=0):
55 """Find unique subarrays in axis in N-D array."""
56 at = np.ascontiguousarray(a.swapaxes(0, axis))
57 dt = np.dtype([("values", at.dtype, at.shape[1:])])
58 atv = at.view(dt)
59 r = np.unique(atv)["values"].swapaxes(0, axis)
60 return r
61
62
63 def _across_block_label_grouping(face, structure):
64 """
65 Find a grouping of labels across block faces.
66
67 We assume that the labels on either side of the block face are unique to
68 that block. This is enforced elsewhere.
69
70 Parameters
71 ----------
72 face : array-like
73 This is the boundary, of thickness (2,), between two blocks.
74 structure : array-like
75 Structuring element for the labeling of the face. This should have
76 length 3 along each axis and have the same number of dimensions as
77 ``face``.
78
79 Returns
80 -------
81 grouped : array of int, shape (2, M)
82 If a column of ``grouped`` contains the values ``i`` and ``j``, it
83 implies that labels ``i`` and ``j`` belong in the same group. These
84 are edges in a global label connectivity graph.
85
86 Examples
87 --------
88 >>> face = np.array([[1, 1, 0, 2, 2, 0, 8],
89 ... [0, 7, 7, 7, 7, 0, 9]])
90 >>> structure = np.ones((3, 3), dtype=bool)
91 >>> _across_block_label_grouping(face, structure)
92 array([[1, 2, 8],
93 [2, 7, 9]], dtype=np.int32)
94
95 This shows that 1-2 are connected, 2-7 are connected, and 8-9 are
96 connected. The resulting graph is (1-2-7), (8-9).
97 """
98 common_labels = scipy.ndimage.label(face, structure)[0]
99 matching = np.stack((common_labels.ravel(), face.ravel()), axis=1)
100 unique_matching = _unique_axis(matching)
101 valid = np.all(unique_matching, axis=1)
102 unique_valid_matching = unique_matching[valid]
103 common_labels, labels = unique_valid_matching.T
104 in_group = np.flatnonzero(np.diff(common_labels) == 0)
105 i = np.take(labels, in_group)
106 j = np.take(labels, in_group + 1)
107 grouped = np.stack((i, j), axis=0)
108 return grouped
109
110
111 def _across_block_label_grouping_delayed(face, structure):
112 """Delayed version of :func:`_across_block_label_grouping`."""
113 _across_block_label_grouping_ = dask.delayed(_across_block_label_grouping)
114 grouped = _across_block_label_grouping_(face, structure)
115 return da.from_delayed(grouped, shape=(2, np.nan), dtype=LABEL_DTYPE)
116
117
118 @dask.delayed
119 def _to_csr_matrix(i, j, n):
120 """Using i and j as coo-format coordinates, return csr matrix."""
121 v = np.ones_like(i)
122 mat = scipy.sparse.coo_matrix((v, (i, j)), shape=(n, n))
123 return mat.tocsr()
124
125
126 def label_adjacency_graph(labels, structure, nlabels, wrap_axes=None):
127 """
128 Adjacency graph of labels between chunks of ``labels``.
129
130 Each chunk in ``labels`` has been labeled independently, and the labels
131 in different chunks are guaranteed to be unique.
132
133 Here we construct a graph connecting labels in different chunks that
134 correspond to the same logical label in the global volume. This is true
135 if the two labels "touch" across the block face as defined by the input
136 ``structure``.
137
138 Parameters
139 ----------
140 labels : dask array of int
141 The input labeled array, where each chunk is independently labeled.
142 structure : array of bool
143 Structuring element, shape (3,) * labels.ndim.
144 nlabels : delayed int
145 The total number of labels in ``labels`` *before* correcting for
146 global consistency.
147 wrap_axes : tuple of int, optional
148 Should labels be wrapped across array boundaries, and if so which axes.
149 - (0,) only wrap over the 0th axis.
150 - (0, 1) wrap over the 0th and 1st axis.
151 - (0, 1, 3) wrap over 0th, 1st and 3rd axis.
152
153 Returns
154 -------
155 mat : delayed scipy.sparse.csr_matrix
156 This matrix has value 1 at (i, j) if label i is connected to
157 label j in the global volume, 0 everywhere else.
158 """
159
160 if structure is None:
161 structure = scipy.ndimage.generate_binary_structure(labels.ndim, 1)
162
163 face_slices = _chunk_faces(
164 labels.chunks, labels.shape, structure, wrap_axes=wrap_axes
165 )
166 all_mappings = [da.empty((2, 0), dtype=LABEL_DTYPE, chunks=1)]
167
168 for face_slice in face_slices:
169 face = labels[face_slice]
170 mapped = _across_block_label_grouping_delayed(face, structure)
171 all_mappings.append(mapped)
172
173 all_mappings = da.concatenate(all_mappings, axis=1)
174 i, j = all_mappings
175 mat = _to_csr_matrix(i, j, nlabels + 1)
176
177 return mat
178
179
180 def _chunk_faces(chunks, shape, structure, wrap_axes=None):
181 """
182 Return slices for two-pixel-wide boundaries between chunks.
183
184 Parameters
185 ----------
186 chunks : tuple of tuple of int
187 The chunk specification of the array.
188 shape : tuple of int
189 The shape of the array.
190 structure: array of bool
191 Structuring element, shape (3,) * ndim.
192 wrap_axes : tuple of int, optional
193 Should labels be wrapped across array boundaries, and if so which axes.
194 - (0,) only wrap over the 0th axis.
195 - (0, 1) wrap over the 0th and 1st axis.
196 - (0, 1, 3) wrap over 0th, 1st and 3rd axis.
197
198 Yields
199 -------
200 tuple of slices
201 Each element indexes a face between two chunks.
202
203 Examples
204 --------
205 >>> import dask.array as da
206 >>> import scipy.ndimage as ndi
207 >>> a = da.arange(110, chunks=110).reshape((10, 11)).rechunk(5)
208 >>> structure = ndi.generate_binary_structure(2, 1)
209 >>> list(chunk_faces(a.chunks, a.shape, structure))
210 [(slice(4, 6, None), slice(0, 5, None)),
211 (slice(4, 6, None), slice(5, 10, None)),
212 (slice(4, 6, None), slice(10, 11, None)),
213 (slice(0, 5, None), slice(4, 6, None)),
214 (slice(0, 5, None), slice(9, 11, None)),
215 (slice(5, 10, None), slice(4, 6, None)),
216 (slice(5, 10, None), slice(9, 11, None))]
217 """
218
219 ndim = len(shape)
220
221 slices = da.core.slices_from_chunks(chunks)
222
223 # arrange block/chunk indices on grid
224 block_summary = np.arange(len(slices)).reshape(
225 [len(c) for c in chunks])
226
227 # Iterate over all blocks and use the structuring element
228 # to determine which blocks should be connected.
229 # For wrappped axes, we need to consider the block
230 # before the current block with index -1 as well.
231 numblocks = [len(c) if wrap_axes is None or ax not in wrap_axes
232 else len(c) + 1 for ax, c in enumerate(chunks)]
233 for curr_block in np.ndindex(tuple(numblocks)):
234
235 curr_block = list(curr_block)
236
237 if wrap_axes is not None:
238 # start at -1 indices for wrapped axes
239 for wrap_axis in wrap_axes:
240 curr_block[wrap_axis] = curr_block[wrap_axis] - 1
241
242 # iterate over neighbors of the current block
243 for pos_structure_coord in np.array(np.where(structure)).T:
244
245 # only consider forward neighbors
246 if min(pos_structure_coord) < 1 or max(pos_structure_coord) < 2:
247 continue
248
249 neigh_block = [
250 curr_block[dim] + pos_structure_coord[dim] - 1
251 for dim in range(ndim)
252 ]
253
254 if max([neigh_block[dim] >= block_summary.shape[dim]
255 for dim in range(ndim)]):
256 continue
257
258 # get current slice index
259 ind_curr_block = block_summary[tuple(curr_block)]
260
261 curr_slice = []
262 for dim in range(ndim):
263 # keep slice if not on boundary
264 if neigh_block[dim] == curr_block[dim]:
265 curr_slice.append(slices[ind_curr_block][dim])
266 # otherwise, add two-pixel-wide boundary
267 else:
268 if slices[ind_curr_block][dim].stop == shape[dim]:
269 curr_slice.append(slice(None, None, shape[dim] - 1))
270 else:
271 curr_slice.append(slice(
272 slices[ind_curr_block][dim].stop - 1,
273 slices[ind_curr_block][dim].stop + 1))
274
275 yield tuple(curr_slice)
276
277
278 def block_ndi_label_delayed(block, structure):
279 """
280 Delayed version of ``scipy.ndimage.label``.
281
282 Parameters
283 ----------
284 block : dask array (single chunk)
285 The input array to be labeled.
286 structure : array of bool
287 Structure defining the connectivity of the labeling.
288
289 Returns
290 -------
291 labeled : dask array, same shape as ``block``.
292 The labeled array.
293 n : delayed int
294 The number of labels in ``labeled``.
295 """
296 label = dask.delayed(scipy.ndimage.label, nout=2)
297 labeled_block, n = label(block, structure=structure)
298 n = dask.delayed(LABEL_DTYPE.type)(n)
299 labeled = da.from_delayed(labeled_block, shape=block.shape,
300 dtype=LABEL_DTYPE)
301 n = da.from_delayed(n, shape=(), dtype=LABEL_DTYPE)
302 return labeled, n
303
304
305 def connected_components_delayed(csr_matrix):
306 """
307 Delayed version of scipy.sparse.csgraph.connected_components.
308
309 This version only returns the (delayed) connected component labelling, not
310 the number of components.
311 """
312 conn_comp = dask.delayed(scipy.sparse.csgraph.connected_components, nout=2)
313 return da.from_delayed(conn_comp(csr_matrix, directed=False)[1],
314 shape=(np.nan,), dtype=CONN_COMP_DTYPE)