Debian Codegraph @

dask_image/ndinterp/_map_coordinates.py

raw
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