scikit-image

1
"""flood_fill.py - in place flood fill algorithm
2

3
This module provides a function to fill all equal (or within tolerance) values
4
connected to a given seed point with a different value.
5
"""
6

7
import numpy as np
8

9
from ..util import crop
10
from ._flood_fill_cy import _flood_fill_equal, _flood_fill_tolerance
11
from ._util import (
12
    _offsets_to_raveled_neighbors,
13
    _resolve_neighborhood,
14
    _set_border_values,
15
)
16
from .._shared.dtype import numeric_dtype_min_max
17

18

19
def flood_fill(
20
    image,
21
    seed_point,
22
    new_value,
23
    *,
24
    footprint=None,
25
    connectivity=None,
26
    tolerance=None,
27
    in_place=False,
28
):
29
    """Perform flood filling on an image.
30

31
    Starting at a specific `seed_point`, connected points equal or within
32
    `tolerance` of the seed value are found, then set to `new_value`.
33

34
    Parameters
35
    ----------
36
    image : ndarray
37
        An n-dimensional array.
38
    seed_point : tuple or int
39
        The point in `image` used as the starting point for the flood fill.  If
40
        the image is 1D, this point may be given as an integer.
41
    new_value : `image` type
42
        New value to set the entire fill.  This must be chosen in agreement
43
        with the dtype of `image`.
44
    footprint : ndarray, optional
45
        The footprint (structuring element) used to determine the neighborhood
46
        of each evaluated pixel. It must contain only 1's and 0's, have the
47
        same number of dimensions as `image`. If not given, all adjacent pixels
48
        are considered as part of the neighborhood (fully connected).
49
    connectivity : int, optional
50
        A number used to determine the neighborhood of each evaluated pixel.
51
        Adjacent pixels whose squared distance from the center is less than or
52
        equal to `connectivity` are considered neighbors. Ignored if
53
        `footprint` is not None.
54
    tolerance : float or int, optional
55
        If None (default), adjacent values must be strictly equal to the
56
        value of `image` at `seed_point` to be filled.  This is fastest.
57
        If a tolerance is provided, adjacent points with values within plus or
58
        minus tolerance from the seed point are filled (inclusive).
59
    in_place : bool, optional
60
        If True, flood filling is applied to `image` in place.  If False, the
61
        flood filled result is returned without modifying the input `image`
62
        (default).
63

64
    Returns
65
    -------
66
    filled : ndarray
67
        An array with the same shape as `image` is returned, with values in
68
        areas connected to and equal (or within tolerance of) the seed point
69
        replaced with `new_value`.
70

71
    Notes
72
    -----
73
    The conceptual analogy of this operation is the 'paint bucket' tool in many
74
    raster graphics programs.
75

76
    Examples
77
    --------
78
    >>> from skimage.morphology import flood_fill
79
    >>> image = np.zeros((4, 7), dtype=int)
80
    >>> image[1:3, 1:3] = 1
81
    >>> image[3, 0] = 1
82
    >>> image[1:3, 4:6] = 2
83
    >>> image[3, 6] = 3
84
    >>> image
85
    array([[0, 0, 0, 0, 0, 0, 0],
86
           [0, 1, 1, 0, 2, 2, 0],
87
           [0, 1, 1, 0, 2, 2, 0],
88
           [1, 0, 0, 0, 0, 0, 3]])
89

90
    Fill connected ones with 5, with full connectivity (diagonals included):
91

92
    >>> flood_fill(image, (1, 1), 5)
93
    array([[0, 0, 0, 0, 0, 0, 0],
94
           [0, 5, 5, 0, 2, 2, 0],
95
           [0, 5, 5, 0, 2, 2, 0],
96
           [5, 0, 0, 0, 0, 0, 3]])
97

98
    Fill connected ones with 5, excluding diagonal points (connectivity 1):
99

100
    >>> flood_fill(image, (1, 1), 5, connectivity=1)
101
    array([[0, 0, 0, 0, 0, 0, 0],
102
           [0, 5, 5, 0, 2, 2, 0],
103
           [0, 5, 5, 0, 2, 2, 0],
104
           [1, 0, 0, 0, 0, 0, 3]])
105

106
    Fill with a tolerance:
107

108
    >>> flood_fill(image, (0, 0), 5, tolerance=1)
109
    array([[5, 5, 5, 5, 5, 5, 5],
110
           [5, 5, 5, 5, 2, 2, 5],
111
           [5, 5, 5, 5, 2, 2, 5],
112
           [5, 5, 5, 5, 5, 5, 3]])
113
    """
114
    mask = flood(
115
        image,
116
        seed_point,
117
        footprint=footprint,
118
        connectivity=connectivity,
119
        tolerance=tolerance,
120
    )
121

122
    if not in_place:
123
        image = image.copy()
124

125
    image[mask] = new_value
126
    return image
127

128

129
def flood(image, seed_point, *, footprint=None, connectivity=None, tolerance=None):
130
    """Mask corresponding to a flood fill.
131

132
    Starting at a specific `seed_point`, connected points equal or within
133
    `tolerance` of the seed value are found.
134

135
    Parameters
136
    ----------
137
    image : ndarray
138
        An n-dimensional array.
139
    seed_point : tuple or int
140
        The point in `image` used as the starting point for the flood fill.  If
141
        the image is 1D, this point may be given as an integer.
142
    footprint : ndarray, optional
143
        The footprint (structuring element) used to determine the neighborhood
144
        of each evaluated pixel. It must contain only 1's and 0's, have the
145
        same number of dimensions as `image`. If not given, all adjacent pixels
146
        are considered as part of the neighborhood (fully connected).
147
    connectivity : int, optional
148
        A number used to determine the neighborhood of each evaluated pixel.
149
        Adjacent pixels whose squared distance from the center is less than or
150
        equal to `connectivity` are considered neighbors. Ignored if
151
        `footprint` is not None.
152
    tolerance : float or int, optional
153
        If None (default), adjacent values must be strictly equal to the
154
        initial value of `image` at `seed_point`.  This is fastest.  If a value
155
        is given, a comparison will be done at every point and if within
156
        tolerance of the initial value will also be filled (inclusive).
157

158
    Returns
159
    -------
160
    mask : ndarray
161
        A Boolean array with the same shape as `image` is returned, with True
162
        values for areas connected to and equal (or within tolerance of) the
163
        seed point.  All other values are False.
164

165
    Notes
166
    -----
167
    The conceptual analogy of this operation is the 'paint bucket' tool in many
168
    raster graphics programs.  This function returns just the mask
169
    representing the fill.
170

171
    If indices are desired rather than masks for memory reasons, the user can
172
    simply run `numpy.nonzero` on the result, save the indices, and discard
173
    this mask.
174

175
    Examples
176
    --------
177
    >>> from skimage.morphology import flood
178
    >>> image = np.zeros((4, 7), dtype=int)
179
    >>> image[1:3, 1:3] = 1
180
    >>> image[3, 0] = 1
181
    >>> image[1:3, 4:6] = 2
182
    >>> image[3, 6] = 3
183
    >>> image
184
    array([[0, 0, 0, 0, 0, 0, 0],
185
           [0, 1, 1, 0, 2, 2, 0],
186
           [0, 1, 1, 0, 2, 2, 0],
187
           [1, 0, 0, 0, 0, 0, 3]])
188

189
    Fill connected ones with 5, with full connectivity (diagonals included):
190

191
    >>> mask = flood(image, (1, 1))
192
    >>> image_flooded = image.copy()
193
    >>> image_flooded[mask] = 5
194
    >>> image_flooded
195
    array([[0, 0, 0, 0, 0, 0, 0],
196
           [0, 5, 5, 0, 2, 2, 0],
197
           [0, 5, 5, 0, 2, 2, 0],
198
           [5, 0, 0, 0, 0, 0, 3]])
199

200
    Fill connected ones with 5, excluding diagonal points (connectivity 1):
201

202
    >>> mask = flood(image, (1, 1), connectivity=1)
203
    >>> image_flooded = image.copy()
204
    >>> image_flooded[mask] = 5
205
    >>> image_flooded
206
    array([[0, 0, 0, 0, 0, 0, 0],
207
           [0, 5, 5, 0, 2, 2, 0],
208
           [0, 5, 5, 0, 2, 2, 0],
209
           [1, 0, 0, 0, 0, 0, 3]])
210

211
    Fill with a tolerance:
212

213
    >>> mask = flood(image, (0, 0), tolerance=1)
214
    >>> image_flooded = image.copy()
215
    >>> image_flooded[mask] = 5
216
    >>> image_flooded
217
    array([[5, 5, 5, 5, 5, 5, 5],
218
           [5, 5, 5, 5, 2, 2, 5],
219
           [5, 5, 5, 5, 2, 2, 5],
220
           [5, 5, 5, 5, 5, 5, 3]])
221
    """
222
    # Correct start point in ravelled image - only copy if non-contiguous
223
    image = np.asarray(image)
224
    if image.flags.f_contiguous is True:
225
        order = 'F'
226
    elif image.flags.c_contiguous is True:
227
        order = 'C'
228
    else:
229
        image = np.ascontiguousarray(image)
230
        order = 'C'
231

232
    # Shortcut for rank zero
233
    if 0 in image.shape:
234
        return np.zeros(image.shape, dtype=bool)
235

236
    # Convenience for 1d input
237
    try:
238
        iter(seed_point)
239
    except TypeError:
240
        seed_point = (seed_point,)
241

242
    seed_value = image[seed_point]
243
    seed_point = tuple(np.asarray(seed_point) % image.shape)
244

245
    footprint = _resolve_neighborhood(
246
        footprint, connectivity, image.ndim, enforce_adjacency=False
247
    )
248
    center = tuple(s // 2 for s in footprint.shape)
249
    # Compute padding width as the maximum offset to neighbors on each axis.
250
    # Generates a 2-tuple of (pad_start, pad_end) for each axis.
251
    pad_width = [
252
        (np.max(np.abs(idx - c)),) * 2 for idx, c in zip(np.nonzero(footprint), center)
253
    ]
254

255
    # Must annotate borders
256
    working_image = np.pad(
257
        image, pad_width, mode='constant', constant_values=image.min()
258
    )
259
    # Stride-aware neighbors - works for both C- and Fortran-contiguity
260
    ravelled_seed_idx = np.ravel_multi_index(
261
        [i + pad_start for i, (pad_start, pad_end) in zip(seed_point, pad_width)],
262
        working_image.shape,
263
        order=order,
264
    )
265
    neighbor_offsets = _offsets_to_raveled_neighbors(
266
        working_image.shape, footprint, center=center, order=order
267
    )
268

269
    # Use a set of flags; see _flood_fill_cy.pyx for meanings
270
    flags = np.zeros(working_image.shape, dtype=np.uint8, order=order)
271
    _set_border_values(flags, value=2, border_width=pad_width)
272

273
    try:
274
        if tolerance is not None:
275
            tolerance = abs(tolerance)
276
            # Account for over- & underflow problems with seed_value ± tolerance
277
            # in a way that works with NumPy 1 & 2
278
            min_value, max_value = numeric_dtype_min_max(seed_value.dtype)
279
            low_tol = max(min_value.item(), seed_value.item() - tolerance)
280
            high_tol = min(max_value.item(), seed_value.item() + tolerance)
281

282
            _flood_fill_tolerance(
283
                working_image.ravel(order),
284
                flags.ravel(order),
285
                neighbor_offsets,
286
                ravelled_seed_idx,
287
                seed_value,
288
                low_tol,
289
                high_tol,
290
            )
291
        else:
292
            _flood_fill_equal(
293
                working_image.ravel(order),
294
                flags.ravel(order),
295
                neighbor_offsets,
296
                ravelled_seed_idx,
297
                seed_value,
298
            )
299
    except TypeError:
300
        if working_image.dtype == np.float16:
301
            # Provide the user with clearer error message
302
            raise TypeError(
303
                "dtype of `image` is float16 which is not "
304
                "supported, try upcasting to float32"
305
            )
306
        else:
307
            raise
308

309
    # Output what the user requested; view does not create a new copy.
310
    return crop(flags, pad_width, copy=False).view(bool)
311