-
-
Notifications
You must be signed in to change notification settings - Fork 2.2k
/
_flood_fill.py
313 lines (271 loc) · 10.5 KB
/
_flood_fill.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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
"""flood_fill.py - in place flood fill algorithm
This module provides a function to fill all equal (or within tolerance) values
connected to a given seed point with a different value.
"""
import numpy as np
from ..util import crop
from ._flood_fill_cy import _flood_fill_equal, _flood_fill_tolerance
from ._util import (
_offsets_to_raveled_neighbors,
_resolve_neighborhood,
_set_border_values,
)
def flood_fill(
image,
seed_point,
new_value,
*,
footprint=None,
connectivity=None,
tolerance=None,
in_place=False,
):
"""Perform flood filling on an image.
Starting at a specific `seed_point`, connected points equal or within
`tolerance` of the seed value are found, then set to `new_value`.
Parameters
----------
image : ndarray
An n-dimensional array.
seed_point : tuple or int
The point in `image` used as the starting point for the flood fill. If
the image is 1D, this point may be given as an integer.
new_value : `image` type
New value to set the entire fill. This must be chosen in agreement
with the dtype of `image`.
footprint : ndarray, optional
The footprint (structuring element) used to determine the neighborhood
of each evaluated pixel. It must contain only 1's and 0's, have the
same number of dimensions as `image`. If not given, all adjacent pixels
are considered as part of the neighborhood (fully connected).
connectivity : int, optional
A number used to determine the neighborhood of each evaluated pixel.
Adjacent pixels whose squared distance from the center is less than or
equal to `connectivity` are considered neighbors. Ignored if
`footprint` is not None.
tolerance : float or int, optional
If None (default), adjacent values must be strictly equal to the
value of `image` at `seed_point` to be filled. This is fastest.
If a tolerance is provided, adjacent points with values within plus or
minus tolerance from the seed point are filled (inclusive).
in_place : bool, optional
If True, flood filling is applied to `image` in place. If False, the
flood filled result is returned without modifying the input `image`
(default).
Returns
-------
filled : ndarray
An array with the same shape as `image` is returned, with values in
areas connected to and equal (or within tolerance of) the seed point
replaced with `new_value`.
Notes
-----
The conceptual analogy of this operation is the 'paint bucket' tool in many
raster graphics programs.
Examples
--------
>>> from skimage.morphology import flood_fill
>>> image = np.zeros((4, 7), dtype=int)
>>> image[1:3, 1:3] = 1
>>> image[3, 0] = 1
>>> image[1:3, 4:6] = 2
>>> image[3, 6] = 3
>>> image
array([[0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 2, 2, 0],
[0, 1, 1, 0, 2, 2, 0],
[1, 0, 0, 0, 0, 0, 3]])
Fill connected ones with 5, with full connectivity (diagonals included):
>>> flood_fill(image, (1, 1), 5)
array([[0, 0, 0, 0, 0, 0, 0],
[0, 5, 5, 0, 2, 2, 0],
[0, 5, 5, 0, 2, 2, 0],
[5, 0, 0, 0, 0, 0, 3]])
Fill connected ones with 5, excluding diagonal points (connectivity 1):
>>> flood_fill(image, (1, 1), 5, connectivity=1)
array([[0, 0, 0, 0, 0, 0, 0],
[0, 5, 5, 0, 2, 2, 0],
[0, 5, 5, 0, 2, 2, 0],
[1, 0, 0, 0, 0, 0, 3]])
Fill with a tolerance:
>>> flood_fill(image, (0, 0), 5, tolerance=1)
array([[5, 5, 5, 5, 5, 5, 5],
[5, 5, 5, 5, 2, 2, 5],
[5, 5, 5, 5, 2, 2, 5],
[5, 5, 5, 5, 5, 5, 3]])
"""
mask = flood(
image,
seed_point,
footprint=footprint,
connectivity=connectivity,
tolerance=tolerance,
)
if not in_place:
image = image.copy()
image[mask] = new_value
return image
def flood(image, seed_point, *, footprint=None, connectivity=None, tolerance=None):
"""Mask corresponding to a flood fill.
Starting at a specific `seed_point`, connected points equal or within
`tolerance` of the seed value are found.
Parameters
----------
image : ndarray
An n-dimensional array.
seed_point : tuple or int
The point in `image` used as the starting point for the flood fill. If
the image is 1D, this point may be given as an integer.
footprint : ndarray, optional
The footprint (structuring element) used to determine the neighborhood
of each evaluated pixel. It must contain only 1's and 0's, have the
same number of dimensions as `image`. If not given, all adjacent pixels
are considered as part of the neighborhood (fully connected).
connectivity : int, optional
A number used to determine the neighborhood of each evaluated pixel.
Adjacent pixels whose squared distance from the center is less than or
equal to `connectivity` are considered neighbors. Ignored if
`footprint` is not None.
tolerance : float or int, optional
If None (default), adjacent values must be strictly equal to the
initial value of `image` at `seed_point`. This is fastest. If a value
is given, a comparison will be done at every point and if within
tolerance of the initial value will also be filled (inclusive).
Returns
-------
mask : ndarray
A Boolean array with the same shape as `image` is returned, with True
values for areas connected to and equal (or within tolerance of) the
seed point. All other values are False.
Notes
-----
The conceptual analogy of this operation is the 'paint bucket' tool in many
raster graphics programs. This function returns just the mask
representing the fill.
If indices are desired rather than masks for memory reasons, the user can
simply run `numpy.nonzero` on the result, save the indices, and discard
this mask.
Examples
--------
>>> from skimage.morphology import flood
>>> image = np.zeros((4, 7), dtype=int)
>>> image[1:3, 1:3] = 1
>>> image[3, 0] = 1
>>> image[1:3, 4:6] = 2
>>> image[3, 6] = 3
>>> image
array([[0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 2, 2, 0],
[0, 1, 1, 0, 2, 2, 0],
[1, 0, 0, 0, 0, 0, 3]])
Fill connected ones with 5, with full connectivity (diagonals included):
>>> mask = flood(image, (1, 1))
>>> image_flooded = image.copy()
>>> image_flooded[mask] = 5
>>> image_flooded
array([[0, 0, 0, 0, 0, 0, 0],
[0, 5, 5, 0, 2, 2, 0],
[0, 5, 5, 0, 2, 2, 0],
[5, 0, 0, 0, 0, 0, 3]])
Fill connected ones with 5, excluding diagonal points (connectivity 1):
>>> mask = flood(image, (1, 1), connectivity=1)
>>> image_flooded = image.copy()
>>> image_flooded[mask] = 5
>>> image_flooded
array([[0, 0, 0, 0, 0, 0, 0],
[0, 5, 5, 0, 2, 2, 0],
[0, 5, 5, 0, 2, 2, 0],
[1, 0, 0, 0, 0, 0, 3]])
Fill with a tolerance:
>>> mask = flood(image, (0, 0), tolerance=1)
>>> image_flooded = image.copy()
>>> image_flooded[mask] = 5
>>> image_flooded
array([[5, 5, 5, 5, 5, 5, 5],
[5, 5, 5, 5, 2, 2, 5],
[5, 5, 5, 5, 2, 2, 5],
[5, 5, 5, 5, 5, 5, 3]])
"""
# Correct start point in ravelled image - only copy if non-contiguous
image = np.asarray(image)
if image.flags.f_contiguous is True:
order = 'F'
elif image.flags.c_contiguous is True:
order = 'C'
else:
image = np.ascontiguousarray(image)
order = 'C'
# Shortcut for rank zero
if 0 in image.shape:
return np.zeros(image.shape, dtype=bool)
# Convenience for 1d input
try:
iter(seed_point)
except TypeError:
seed_point = (seed_point,)
seed_value = image[seed_point]
seed_point = tuple(np.asarray(seed_point) % image.shape)
footprint = _resolve_neighborhood(
footprint, connectivity, image.ndim, enforce_adjacency=False
)
center = tuple(s // 2 for s in footprint.shape)
# Compute padding width as the maximum offset to neighbors on each axis.
# Generates a 2-tuple of (pad_start, pad_end) for each axis.
pad_width = [
(np.max(np.abs(idx - c)),) * 2 for idx, c in zip(np.nonzero(footprint), center)
]
# Must annotate borders
working_image = np.pad(
image, pad_width, mode='constant', constant_values=image.min()
)
# Stride-aware neighbors - works for both C- and Fortran-contiguity
ravelled_seed_idx = np.ravel_multi_index(
[i + pad_start for i, (pad_start, pad_end) in zip(seed_point, pad_width)],
working_image.shape,
order=order,
)
neighbor_offsets = _offsets_to_raveled_neighbors(
working_image.shape, footprint, center=center, order=order
)
# Use a set of flags; see _flood_fill_cy.pyx for meanings
flags = np.zeros(working_image.shape, dtype=np.uint8, order=order)
_set_border_values(flags, value=2, border_width=pad_width)
try:
if tolerance is not None:
# Check if tolerance could create overflow problems
try:
max_value = np.finfo(working_image.dtype).max
min_value = np.finfo(working_image.dtype).min
except ValueError:
max_value = np.iinfo(working_image.dtype).max
min_value = np.iinfo(working_image.dtype).min
high_tol = min(max_value, seed_value + tolerance)
low_tol = max(min_value, seed_value - tolerance)
_flood_fill_tolerance(
working_image.ravel(order),
flags.ravel(order),
neighbor_offsets,
ravelled_seed_idx,
seed_value,
low_tol,
high_tol,
)
else:
_flood_fill_equal(
working_image.ravel(order),
flags.ravel(order),
neighbor_offsets,
ravelled_seed_idx,
seed_value,
)
except TypeError:
if working_image.dtype == np.float16:
# Provide the user with clearer error message
raise TypeError(
"dtype of `image` is float16 which is not "
"supported, try upcasting to float32"
)
else:
raise
# Output what the user requested; view does not create a new copy.
return crop(flags, pad_width, copy=False).view(bool)