| 1 |
# -*- coding: utf-8 -*- |
| 2 |
|
| 3 |
from dask import delayed |
| 4 |
import dask.array as da |
| 5 |
import numpy as np |
| 6 |
from dask.base import tokenize |
| 7 |
from scipy.ndimage import map_coordinates as ndimage_map_coordinates |
| 8 |
from scipy.ndimage import labeled_comprehension as\ |
| 9 |
ndimage_labeled_comprehension |
| 10 |
|
| 11 |
from ..dispatch._utils import get_type |
| 12 |
|
| 13 |
|
| 14 |
def _map_single_coordinates_array_chunk( |
| 15 |
input, coordinates, order=3, mode='constant', |
| 16 |
cval=0.0, prefilter=False): |
| 17 |
""" |
| 18 |
Central helper function for implementing map_coordinates. |
| 19 |
|
| 20 |
Receives 'input' as a dask array and computed coordinates. |
| 21 |
|
| 22 |
Implementation details and steps: |
| 23 |
1) associate each coordinate in coordinates with the chunk |
| 24 |
it maps to in the input |
| 25 |
2) for each input chunk that has been associated to at least one |
| 26 |
coordinate, calculate the minimal slice required to map |
| 27 |
all coordinates that are associated to it (note that resulting slice |
| 28 |
coordinates can lie outside of the coordinate's chunk) |
| 29 |
3) for each previously obtained slice and its associated coordinates, |
| 30 |
define a dask task and apply ndimage.map_coordinates |
| 31 |
4) outputs of ndimage.map_coordinates are rearranged to match input order |
| 32 |
""" |
| 33 |
|
| 34 |
# STEP 1: Associate each coordinate in coordinates with |
| 35 |
# the chunk it maps to in the input array |
| 36 |
|
| 37 |
# get the input chunks each coordinate maps onto |
| 38 |
coords_input_chunk_locations = coordinates.T // np.array(input.chunksize) |
| 39 |
|
| 40 |
# map out-of-bounds chunk locations to valid input chunks |
| 41 |
coords_input_chunk_locations = np.clip( |
| 42 |
coords_input_chunk_locations, 0, np.array(input.numblocks) - 1 |
| 43 |
) |
| 44 |
|
| 45 |
# all input chunk locations |
| 46 |
input_chunk_locations = np.array([i for i in np.ndindex(input.numblocks)]) |
| 47 |
|
| 48 |
# linearize input chunk locations |
| 49 |
coords_input_chunk_locations_linear = np.sum( |
| 50 |
coords_input_chunk_locations * np.array( |
| 51 |
[np.prod(input.numblocks[:dim]) |
| 52 |
for dim in range(input.ndim)])[::-1], |
| 53 |
axis=1, dtype=np.int64) |
| 54 |
|
| 55 |
# determine the input chunks that have coords associated and |
| 56 |
# count how many coords map onto each input chunk |
| 57 |
chunk_indices_count = np.bincount(coords_input_chunk_locations_linear, |
| 58 |
minlength=np.prod(input.numblocks)) |
| 59 |
required_input_chunk_indices = np.where(chunk_indices_count > 0)[0] |
| 60 |
required_input_chunks = input_chunk_locations[required_input_chunk_indices] |
| 61 |
coord_rc_count = chunk_indices_count[required_input_chunk_indices] |
| 62 |
|
| 63 |
# inverse mapping: input chunks to coordinates |
| 64 |
required_input_chunk_coords_indices = \ |
| 65 |
[np.where(coords_input_chunk_locations_linear == irc)[0] |
| 66 |
for irc in required_input_chunk_indices] |
| 67 |
|
| 68 |
# STEP 2: for each input chunk that has been associated to at least |
| 69 |
# one coordinate, calculate the minimal slice required to map all |
| 70 |
# coordinates that are associated to it (note that resulting slice |
| 71 |
# coordinates can lie outside of the coordinate's chunk) |
| 72 |
|
| 73 |
# determine the slices of the input array that are required for |
| 74 |
# mapping all coordinates associated to a given input chunk. |
| 75 |
# Note that this slice can be larger than the given chunk when coords |
| 76 |
# lie at chunk borders. |
| 77 |
# (probably there's a more efficient way to do this) |
| 78 |
input_slices_lower = np.array([np.clip( |
| 79 |
ndimage_labeled_comprehension( |
| 80 |
np.floor(coordinates[dim] - order // 2), |
| 81 |
coords_input_chunk_locations_linear, |
| 82 |
required_input_chunk_indices, |
| 83 |
np.min, np.int64, 0), |
| 84 |
0, input.shape[dim] - 1) |
| 85 |
for dim in range(input.ndim)]) |
| 86 |
|
| 87 |
input_slices_upper = np.array([np.clip( |
| 88 |
ndimage_labeled_comprehension( |
| 89 |
np.ceil(coordinates[dim] + order // 2) + 1, |
| 90 |
coords_input_chunk_locations_linear, |
| 91 |
required_input_chunk_indices, |
| 92 |
np.max, np.int64, 0), |
| 93 |
0, input.shape[dim]) |
| 94 |
for dim in range(input.ndim)]) |
| 95 |
|
| 96 |
input_slices = np.array([input_slices_lower, input_slices_upper])\ |
| 97 |
.swapaxes(1, 2) |
| 98 |
|
| 99 |
# STEP 3: For each previously obtained slice and its associated |
| 100 |
# coordinates, define a dask task and apply ndimage.map_coordinates |
| 101 |
|
| 102 |
# prepare building dask graph |
| 103 |
# define one task per associated input chunk |
| 104 |
name = "map_coordinates_chunk-%s" % tokenize( |
| 105 |
input, |
| 106 |
coordinates, |
| 107 |
order, |
| 108 |
mode, |
| 109 |
cval, |
| 110 |
prefilter |
| 111 |
) |
| 112 |
|
| 113 |
keys = [(name, i) for i in range(len(required_input_chunks))] |
| 114 |
|
| 115 |
# pair map_coordinates calls with input slices and mapped coordinates |
| 116 |
values = [] |
| 117 |
for irc in range(len(required_input_chunks)): |
| 118 |
|
| 119 |
ric_slice = [slice( |
| 120 |
input_slices[0][irc][dim], |
| 121 |
input_slices[1][irc][dim]) |
| 122 |
for dim in range(input.ndim)] |
| 123 |
ric_offset = input_slices[0][irc] |
| 124 |
|
| 125 |
values.append(( |
| 126 |
ndimage_map_coordinates, |
| 127 |
input[tuple(ric_slice)], |
| 128 |
coordinates[:, required_input_chunk_coords_indices[irc]] |
| 129 |
- ric_offset[:, None], |
| 130 |
None, |
| 131 |
order, |
| 132 |
mode, |
| 133 |
cval, |
| 134 |
prefilter |
| 135 |
)) |
| 136 |
|
| 137 |
# build dask graph |
| 138 |
dsk = dict(zip(keys, values)) |
| 139 |
ar = da.Array(dsk, name, tuple([list(coord_rc_count)]), input.dtype) |
| 140 |
|
| 141 |
# STEP 4: rearrange outputs of ndimage.map_coordinates |
| 142 |
# to match input order |
| 143 |
orig_order = np.argsort( |
| 144 |
[ic for ric_ci in required_input_chunk_coords_indices |
| 145 |
for ic in ric_ci]) |
| 146 |
|
| 147 |
# compute result and reorder |
| 148 |
# (ordering first would probably unnecessarily inflate the task graph) |
| 149 |
return ar.compute()[orig_order] |
| 150 |
|
| 151 |
|
| 152 |
def map_coordinates(input, coordinates, order=3, |
| 153 |
mode='constant', cval=0.0, prefilter=False): |
| 154 |
""" |
| 155 |
Wraps ndimage.map_coordinates. |
| 156 |
|
| 157 |
Both the input and coordinate arrays can be dask arrays. |
| 158 |
GPU arrays are not supported. |
| 159 |
|
| 160 |
For each chunk in the coordinates array, the coordinates are computed |
| 161 |
and mapped onto the required slices of the input array. One task is |
| 162 |
is defined for each input array chunk that has been associated to at |
| 163 |
least one coordinate. The outputs of the tasks are then rearranged to |
| 164 |
match the input order. For more details see the docstring of |
| 165 |
'_map_single_coordinates_array_chunk'. |
| 166 |
|
| 167 |
Using this function together with schedulers that support |
| 168 |
parallelism (threads, processes, distributed) makes sense in the |
| 169 |
case of either a large input array or a large coordinates array. |
| 170 |
When both arrays are large, it is recommended to use the |
| 171 |
single-threaded scheduler. A scheduler can be specified using e.g. |
| 172 |
`with dask.config.set(scheduler='threads'): ...`. |
| 173 |
|
| 174 |
input : array_like |
| 175 |
The input array. |
| 176 |
coordinates : array_like |
| 177 |
The coordinates at which to sample the input. |
| 178 |
order : int, optional |
| 179 |
The order of the spline interpolation, default is 3. The order has to |
| 180 |
be in the range 0-5. |
| 181 |
mode : boundary behavior mode, optional |
| 182 |
cval : float, optional |
| 183 |
Value to fill past edges of input if mode is 'constant'. Default is 0.0 |
| 184 |
prefilter : bool, optional |
| 185 |
If True, prefilter the input before interpolation. Default is False. |
| 186 |
Warning: prefilter is True by default in |
| 187 |
`scipy.ndimage.map_coordinates`. Prefiltering here is performed on a |
| 188 |
chunk-by-chunk basis, which may lead to different results than |
| 189 |
`scipy.ndimage.map_coordinates` in case of chunked input arrays |
| 190 |
and order > 1. |
| 191 |
Note: prefilter is not necessary when: |
| 192 |
- You are using nearest neighbour interpolation, by setting order=0 |
| 193 |
- You are using linear interpolation, by setting order=1, or |
| 194 |
- You have already prefiltered the input array, |
| 195 |
using the spline_filter or spline_filter1d functions. |
| 196 |
|
| 197 |
Comments: |
| 198 |
- in case of a small coordinate array, it might make sense to rechunk |
| 199 |
it into a single chunk |
| 200 |
- note the different default for `prefilter` compared to |
| 201 |
`scipy.ndimage.map_coordinates`, which is True by default. |
| 202 |
""" |
| 203 |
if "cupy" in str(get_type(input)) or "cupy" in str(get_type(coordinates)): |
| 204 |
raise NotImplementedError( |
| 205 |
"GPU cupy arrays are not supported by " |
| 206 |
"dask_image.ndinterp.map_overlap") |
| 207 |
|
| 208 |
# if coordinate array is not a dask array, convert it into one |
| 209 |
if type(coordinates) is not da.Array: |
| 210 |
coordinates = da.from_array(coordinates, chunks=coordinates.shape) |
| 211 |
else: |
| 212 |
# make sure indices are not split across chunks, i.e. that there's |
| 213 |
# no chunking along the first dimension |
| 214 |
if len(coordinates.chunks[0]) > 1: |
| 215 |
coordinates = da.rechunk( |
| 216 |
coordinates, |
| 217 |
(-1,) + coordinates.chunks[1:]) |
| 218 |
|
| 219 |
# if the input array is not a dask array, convert it into one |
| 220 |
if type(input) is not da.Array: |
| 221 |
input = da.from_array(input, chunks=input.shape) |
| 222 |
|
| 223 |
# Map each chunk of the coordinates array onto the entire input array. |
| 224 |
# 'input' is passed to `_map_single_coordinates_array_chunk` using a bit of |
| 225 |
# a dirty trick: it is split into its components and passed as a delayed |
| 226 |
# object, which reconstructs the original array when the task is |
| 227 |
# executed. Therefore two `compute` calls are required to obtain the |
| 228 |
# final result, one of which is peformed by |
| 229 |
# `_map_single_coordinates_array_chunk` |
| 230 |
# Discussion https://dask.discourse.group/t/passing-dask-objects-to-delayed-computations-without-triggering-compute/1441 # noqa: E501 |
| 231 |
output = da.map_blocks( |
| 232 |
_map_single_coordinates_array_chunk, |
| 233 |
delayed(da.Array)(input.dask, input.name, input.chunks, input.dtype), |
| 234 |
coordinates, |
| 235 |
order=order, |
| 236 |
mode=mode, |
| 237 |
cval=cval, |
| 238 |
prefilter=prefilter, |
| 239 |
dtype=input.dtype, |
| 240 |
chunks=coordinates.chunks[1:], |
| 241 |
drop_axis=0, |
| 242 |
) |
| 243 |
|
| 244 |
return output |