| 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) |