We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
`segmentation.watershed` returns wrong data type
### Description:

The documentation of `segmentation.watershed` says that:

> ### Returns
>   **out**: ndarray
>   A labeled matrix of the same type and shape as markers

[[0.18.x]](https://scikit-image.org/docs/0.18.x/api/skimage.segmentation.html#skimage.segmentation.watershed) [[0.19.x]](https://scikit-image.org/docs/0.19.x/api/skimage.segmentation.html#skimage.segmentation.watershed)

I have tested this with 0.18.1:

```python
import skimage.segmentation
import numpy as np
print(skimage.segmentation.watershed(np.zeros((100, 100)), np.zeros((100, 100), np.uint16)).dtype)
```

Gives `int32` but `uint16` is expected.

### Way to reproduce:

```Python
import skimage.segmentation
import numpy as np
print(skimage.segmentation.watershed(np.zeros((100, 100)), np.zeros((100, 100), np.uint16)).dtype)
```


### Traceback or output:

```Shell
int32
```


### Version information:

```Shell
3.8.5 (default, Sep  4 2020, 07:30:14) 
[GCC 7.3.0]
Linux-5.8.0-36-generic-x86_64-with-glibc2.10
scikit-image version: 0.18.1
numpy version: 1.20.3
```


--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `skimage/segmentation/_watershed.py`
Content:
```
1 """watershed.py - watershed algorithm
2 
3 This module implements a watershed algorithm that apportions pixels into
4 marked basins. The algorithm uses a priority queue to hold the pixels
5 with the metric for the priority queue being pixel value, then the time
6 of entry into the queue - this settles ties in favor of the closest marker.
7 
8 Some ideas taken from
9 Soille, "Automated Basin Delineation from Digital Elevation Models Using
10 Mathematical Morphology", Signal Processing 20 (1990) 171-182.
11 
12 The most important insight in the paper is that entry time onto the queue
13 solves two problems: a pixel should be assigned to the neighbor with the
14 largest gradient or, if there is no gradient, pixels on a plateau should
15 be split between markers on opposite sides.
16 """
17 
18 import numpy as np
19 from scipy import ndimage as ndi
20 
21 from . import _watershed_cy
22 from ..morphology.extrema import local_minima
23 from ..morphology._util import (_validate_connectivity,
24                                 _offsets_to_raveled_neighbors)
25 from ..util import crop, regular_seeds
26 
27 
28 def _validate_inputs(image, markers, mask, connectivity):
29     """Ensure that all inputs to watershed have matching shapes and types.
30 
31     Parameters
32     ----------
33     image : array
34         The input image.
35     markers : int or array of int
36         The marker image.
37     mask : array, or None
38         A boolean mask, True where we want to compute the watershed.
39     connectivity : int in {1, ..., image.ndim}
40         The connectivity of the neighborhood of a pixel.
41 
42     Returns
43     -------
44     image, markers, mask : arrays
45         The validated and formatted arrays. Image will have dtype float64,
46         markers int32, and mask int8. If ``None`` was given for the mask,
47         it is a volume of all 1s.
48 
49     Raises
50     ------
51     ValueError
52         If the shapes of the given arrays don't match.
53     """
54     n_pixels = image.size
55     if mask is None:
56         # Use a complete `True` mask if none is provided
57         mask = np.ones(image.shape, bool)
58     else:
59         mask = np.asanyarray(mask, dtype=bool)
60         n_pixels = np.sum(mask)
61         if mask.shape != image.shape:
62             message = (f'`mask` (shape {mask.shape}) must have same shape '
63                        f'as `image` (shape {image.shape})')
64             raise ValueError(message)
65     if markers is None:
66         markers_bool = local_minima(image, connectivity=connectivity) * mask
67         footprint = ndi.generate_binary_structure(markers_bool.ndim, connectivity)
68         markers = ndi.label(markers_bool, structure=footprint)[0]
69     elif not isinstance(markers, (np.ndarray, list, tuple)):
70         # not array-like, assume int
71         # given int, assume that number of markers *within mask*.
72         markers = regular_seeds(image.shape,
73                                 int(markers / (n_pixels / image.size)))
74         markers *= mask
75     else:
76         markers = np.asanyarray(markers) * mask
77         if markers.shape != image.shape:
78             message = (f'`markers` (shape {markers.shape}) must have same '
79                        f'shape as `image` (shape {image.shape})')
80             raise ValueError(message)
81     return (image.astype(np.float64),
82             markers.astype(np.int32),
83             mask.astype(np.int8))
84 
85 
86 def watershed(image, markers=None, connectivity=1, offset=None, mask=None,
87               compactness=0, watershed_line=False):
88     """Find watershed basins in `image` flooded from given `markers`.
89 
90     Parameters
91     ----------
92     image : ndarray (2-D, 3-D, ...)
93         Data array where the lowest value points are labeled first.
94     markers : int, or ndarray of int, same shape as `image`, optional
95         The desired number of markers, or an array marking the basins with the
96         values to be assigned in the label matrix. Zero means not a marker. If
97         ``None`` (no markers given), the local minima of the image are used as
98         markers.
99     connectivity : ndarray, optional
100         An array with the same number of dimensions as `image` whose
101         non-zero elements indicate neighbors for connection.
102         Following the scipy convention, default is a one-connected array of
103         the dimension of the image.
104     offset : array_like of shape image.ndim, optional
105         offset of the connectivity (one offset per dimension)
106     mask : ndarray of bools or 0s and 1s, optional
107         Array of same shape as `image`. Only points at which mask == True
108         will be labeled.
109     compactness : float, optional
110         Use compact watershed [3]_ with given compactness parameter.
111         Higher values result in more regularly-shaped watershed basins.
112     watershed_line : bool, optional
113         If watershed_line is True, a one-pixel wide line separates the regions
114         obtained by the watershed algorithm. The line has the label 0.
115         Note that the method used for adding this line expects that
116         marker regions are not adjacent; the watershed line may not catch
117         borders between adjacent marker regions.
118 
119     Returns
120     -------
121     out : ndarray
122         A labeled matrix of the same type and shape as markers
123 
124     See Also
125     --------
126     skimage.segmentation.random_walker : random walker segmentation
127         A segmentation algorithm based on anisotropic diffusion, usually
128         slower than the watershed but with good results on noisy data and
129         boundaries with holes.
130 
131     Notes
132     -----
133     This function implements a watershed algorithm [1]_ [2]_ that apportions
134     pixels into marked basins. The algorithm uses a priority queue to hold
135     the pixels with the metric for the priority queue being pixel value, then
136     the time of entry into the queue - this settles ties in favor of the
137     closest marker.
138 
139     Some ideas taken from
140     Soille, "Automated Basin Delineation from Digital Elevation Models Using
141     Mathematical Morphology", Signal Processing 20 (1990) 171-182
142 
143     The most important insight in the paper is that entry time onto the queue
144     solves two problems: a pixel should be assigned to the neighbor with the
145     largest gradient or, if there is no gradient, pixels on a plateau should
146     be split between markers on opposite sides.
147 
148     This implementation converts all arguments to specific, lowest common
149     denominator types, then passes these to a C algorithm.
150 
151     Markers can be determined manually, or automatically using for example
152     the local minima of the gradient of the image, or the local maxima of the
153     distance function to the background for separating overlapping objects
154     (see example).
155 
156     References
157     ----------
158     .. [1] https://en.wikipedia.org/wiki/Watershed_%28image_processing%29
159 
160     .. [2] http://cmm.ensmp.fr/~beucher/wtshed.html
161 
162     .. [3] Peer Neubert & Peter Protzel (2014). Compact Watershed and
163            Preemptive SLIC: On Improving Trade-offs of Superpixel Segmentation
164            Algorithms. ICPR 2014, pp 996-1001. :DOI:`10.1109/ICPR.2014.181`
165            https://www.tu-chemnitz.de/etit/proaut/publications/cws_pSLIC_ICPR.pdf
166 
167     Examples
168     --------
169     The watershed algorithm is useful to separate overlapping objects.
170 
171     We first generate an initial image with two overlapping circles:
172 
173     >>> x, y = np.indices((80, 80))
174     >>> x1, y1, x2, y2 = 28, 28, 44, 52
175     >>> r1, r2 = 16, 20
176     >>> mask_circle1 = (x - x1)**2 + (y - y1)**2 < r1**2
177     >>> mask_circle2 = (x - x2)**2 + (y - y2)**2 < r2**2
178     >>> image = np.logical_or(mask_circle1, mask_circle2)
179 
180     Next, we want to separate the two circles. We generate markers at the
181     maxima of the distance to the background:
182 
183     >>> from scipy import ndimage as ndi
184     >>> distance = ndi.distance_transform_edt(image)
185     >>> from skimage.feature import peak_local_max
186     >>> max_coords = peak_local_max(distance, labels=image,
187     ...                             footprint=np.ones((3, 3)))
188     >>> local_maxima = np.zeros_like(image, dtype=bool)
189     >>> local_maxima[tuple(max_coords.T)] = True
190     >>> markers = ndi.label(local_maxima)[0]
191 
192     Finally, we run the watershed on the image and markers:
193 
194     >>> labels = watershed(-distance, markers, mask=image)
195 
196     The algorithm works also for 3-D images, and can be used for example to
197     separate overlapping spheres.
198     """
199     image, markers, mask = _validate_inputs(image, markers, mask, connectivity)
200     connectivity, offset = _validate_connectivity(image.ndim, connectivity,
201                                                   offset)
202 
203     # pad the image, markers, and mask so that we can use the mask to
204     # keep from running off the edges
205     pad_width = [(p, p) for p in offset]
206     image = np.pad(image, pad_width, mode='constant')
207     mask = np.pad(mask, pad_width, mode='constant').ravel()
208     output = np.pad(markers, pad_width, mode='constant')
209 
210     flat_neighborhood = _offsets_to_raveled_neighbors(
211         image.shape, connectivity, center=offset)
212     marker_locations = np.flatnonzero(output)
213     image_strides = np.array(image.strides, dtype=np.intp) // image.itemsize
214 
215     _watershed_cy.watershed_raveled(image.ravel(),
216                                     marker_locations, flat_neighborhood,
217                                     mask, image_strides, compactness,
218                                     output.ravel(),
219                                     watershed_line)
220 
221     output = crop(output, pad_width, copy=True)
222 
223     return output
224
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/skimage/segmentation/_watershed.py b/skimage/segmentation/_watershed.py
--- a/skimage/segmentation/_watershed.py
+++ b/skimage/segmentation/_watershed.py
@@ -79,7 +79,7 @@
                        f'shape as `image` (shape {image.shape})')
             raise ValueError(message)
     return (image.astype(np.float64),
-            markers.astype(np.int32),
+            markers,
             mask.astype(np.int8))

{"golden_diff": "diff --git a/skimage/segmentation/_watershed.py b/skimage/segmentation/_watershed.py\n--- a/skimage/segmentation/_watershed.py\n+++ b/skimage/segmentation/_watershed.py\n@@ -79,7 +79,7 @@\n                        f'shape as `image` (shape {image.shape})')\n             raise ValueError(message)\n     return (image.astype(np.float64),\n-            markers.astype(np.int32),\n+            markers,\n             mask.astype(np.int8))\n", "issue": "`segmentation.watershed` returns wrong data type\n### Description:\n\nThe documentation of `segmentation.watershed` says that:\r\n\r\n> ### Returns\r\n>   **out**: ndarray\r\n>   A labeled matrix of the same type and shape as markers\r\n\r\n[[0.18.x]](https://scikit-image.org/docs/0.18.x/api/skimage.segmentation.html#skimage.segmentation.watershed) [[0.19.x]](https://scikit-image.org/docs/0.19.x/api/skimage.segmentation.html#skimage.segmentation.watershed)\r\n\r\nI have tested this with 0.18.1:\r\n\r\n```python\r\nimport skimage.segmentation\r\nimport numpy as np\r\nprint(skimage.segmentation.watershed(np.zeros((100, 100)), np.zeros((100, 100), np.uint16)).dtype)\r\n```\r\n\r\nGives `int32` but `uint16` is expected.\n\n### Way to reproduce:\n\n```Python\nimport skimage.segmentation\r\nimport numpy as np\r\nprint(skimage.segmentation.watershed(np.zeros((100, 100)), np.zeros((100, 100), np.uint16)).dtype)\n```\n\n\n### Traceback or output:\n\n```Shell\nint32\n```\n\n\n### Version information:\n\n```Shell\n3.8.5 (default, Sep  4 2020, 07:30:14) \r\n[GCC 7.3.0]\r\nLinux-5.8.0-36-generic-x86_64-with-glibc2.10\r\nscikit-image version: 0.18.1\r\nnumpy version: 1.20.3\n```\n\n", "before_files": [{"content": "\"\"\"watershed.py - watershed algorithm\n\nThis module implements a watershed algorithm that apportions pixels into\nmarked basins. The algorithm uses a priority queue to hold the pixels\nwith the metric for the priority queue being pixel value, then the time\nof entry into the queue - this settles ties in favor of the closest marker.\n\nSome ideas taken from\nSoille, \"Automated Basin Delineation from Digital Elevation Models Using\nMathematical Morphology\", Signal Processing 20 (1990) 171-182.\n\nThe most important insight in the paper is that entry time onto the queue\nsolves two problems: a pixel should be assigned to the neighbor with the\nlargest gradient or, if there is no gradient, pixels on a plateau should\nbe split between markers on opposite sides.\n\"\"\"\n\nimport numpy as np\nfrom scipy import ndimage as ndi\n\nfrom . import _watershed_cy\nfrom ..morphology.extrema import local_minima\nfrom ..morphology._util import (_validate_connectivity,\n                                _offsets_to_raveled_neighbors)\nfrom ..util import crop, regular_seeds\n\n\ndef _validate_inputs(image, markers, mask, connectivity):\n    \"\"\"Ensure that all inputs to watershed have matching shapes and types.\n\n    Parameters\n    ----------\n    image : array\n        The input image.\n    markers : int or array of int\n        The marker image.\n    mask : array, or None\n        A boolean mask, True where we want to compute the watershed.\n    connectivity : int in {1, ..., image.ndim}\n        The connectivity of the neighborhood of a pixel.\n\n    Returns\n    -------\n    image, markers, mask : arrays\n        The validated and formatted arrays. Image will have dtype float64,\n        markers int32, and mask int8. If ``None`` was given for the mask,\n        it is a volume of all 1s.\n\n    Raises\n    ------\n    ValueError\n        If the shapes of the given arrays don't match.\n    \"\"\"\n    n_pixels = image.size\n    if mask is None:\n        # Use a complete `True` mask if none is provided\n        mask = np.ones(image.shape, bool)\n    else:\n        mask = np.asanyarray(mask, dtype=bool)\n        n_pixels = np.sum(mask)\n        if mask.shape != image.shape:\n            message = (f'`mask` (shape {mask.shape}) must have same shape '\n                       f'as `image` (shape {image.shape})')\n            raise ValueError(message)\n    if markers is None:\n        markers_bool = local_minima(image, connectivity=connectivity) * mask\n        footprint = ndi.generate_binary_structure(markers_bool.ndim, connectivity)\n        markers = ndi.label(markers_bool, structure=footprint)[0]\n    elif not isinstance(markers, (np.ndarray, list, tuple)):\n        # not array-like, assume int\n        # given int, assume that number of markers *within mask*.\n        markers = regular_seeds(image.shape,\n                                int(markers / (n_pixels / image.size)))\n        markers *= mask\n    else:\n        markers = np.asanyarray(markers) * mask\n        if markers.shape != image.shape:\n            message = (f'`markers` (shape {markers.shape}) must have same '\n                       f'shape as `image` (shape {image.shape})')\n            raise ValueError(message)\n    return (image.astype(np.float64),\n            markers.astype(np.int32),\n            mask.astype(np.int8))\n\n\ndef watershed(image, markers=None, connectivity=1, offset=None, mask=None,\n              compactness=0, watershed_line=False):\n    \"\"\"Find watershed basins in `image` flooded from given `markers`.\n\n    Parameters\n    ----------\n    image : ndarray (2-D, 3-D, ...)\n        Data array where the lowest value points are labeled first.\n    markers : int, or ndarray of int, same shape as `image`, optional\n        The desired number of markers, or an array marking the basins with the\n        values to be assigned in the label matrix. Zero means not a marker. If\n        ``None`` (no markers given), the local minima of the image are used as\n        markers.\n    connectivity : ndarray, optional\n        An array with the same number of dimensions as `image` whose\n        non-zero elements indicate neighbors for connection.\n        Following the scipy convention, default is a one-connected array of\n        the dimension of the image.\n    offset : array_like of shape image.ndim, optional\n        offset of the connectivity (one offset per dimension)\n    mask : ndarray of bools or 0s and 1s, optional\n        Array of same shape as `image`. Only points at which mask == True\n        will be labeled.\n    compactness : float, optional\n        Use compact watershed [3]_ with given compactness parameter.\n        Higher values result in more regularly-shaped watershed basins.\n    watershed_line : bool, optional\n        If watershed_line is True, a one-pixel wide line separates the regions\n        obtained by the watershed algorithm. The line has the label 0.\n        Note that the method used for adding this line expects that\n        marker regions are not adjacent; the watershed line may not catch\n        borders between adjacent marker regions.\n\n    Returns\n    -------\n    out : ndarray\n        A labeled matrix of the same type and shape as markers\n\n    See Also\n    --------\n    skimage.segmentation.random_walker : random walker segmentation\n        A segmentation algorithm based on anisotropic diffusion, usually\n        slower than the watershed but with good results on noisy data and\n        boundaries with holes.\n\n    Notes\n    -----\n    This function implements a watershed algorithm [1]_ [2]_ that apportions\n    pixels into marked basins. The algorithm uses a priority queue to hold\n    the pixels with the metric for the priority queue being pixel value, then\n    the time of entry into the queue - this settles ties in favor of the\n    closest marker.\n\n    Some ideas taken from\n    Soille, \"Automated Basin Delineation from Digital Elevation Models Using\n    Mathematical Morphology\", Signal Processing 20 (1990) 171-182\n\n    The most important insight in the paper is that entry time onto the queue\n    solves two problems: a pixel should be assigned to the neighbor with the\n    largest gradient or, if there is no gradient, pixels on a plateau should\n    be split between markers on opposite sides.\n\n    This implementation converts all arguments to specific, lowest common\n    denominator types, then passes these to a C algorithm.\n\n    Markers can be determined manually, or automatically using for example\n    the local minima of the gradient of the image, or the local maxima of the\n    distance function to the background for separating overlapping objects\n    (see example).\n\n    References\n    ----------\n    .. [1] https://en.wikipedia.org/wiki/Watershed_%28image_processing%29\n\n    .. [2] http://cmm.ensmp.fr/~beucher/wtshed.html\n\n    .. [3] Peer Neubert & Peter Protzel (2014). Compact Watershed and\n           Preemptive SLIC: On Improving Trade-offs of Superpixel Segmentation\n           Algorithms. ICPR 2014, pp 996-1001. :DOI:`10.1109/ICPR.2014.181`\n           https://www.tu-chemnitz.de/etit/proaut/publications/cws_pSLIC_ICPR.pdf\n\n    Examples\n    --------\n    The watershed algorithm is useful to separate overlapping objects.\n\n    We first generate an initial image with two overlapping circles:\n\n    >>> x, y = np.indices((80, 80))\n    >>> x1, y1, x2, y2 = 28, 28, 44, 52\n    >>> r1, r2 = 16, 20\n    >>> mask_circle1 = (x - x1)**2 + (y - y1)**2 < r1**2\n    >>> mask_circle2 = (x - x2)**2 + (y - y2)**2 < r2**2\n    >>> image = np.logical_or(mask_circle1, mask_circle2)\n\n    Next, we want to separate the two circles. We generate markers at the\n    maxima of the distance to the background:\n\n    >>> from scipy import ndimage as ndi\n    >>> distance = ndi.distance_transform_edt(image)\n    >>> from skimage.feature import peak_local_max\n    >>> max_coords = peak_local_max(distance, labels=image,\n    ...                             footprint=np.ones((3, 3)))\n    >>> local_maxima = np.zeros_like(image, dtype=bool)\n    >>> local_maxima[tuple(max_coords.T)] = True\n    >>> markers = ndi.label(local_maxima)[0]\n\n    Finally, we run the watershed on the image and markers:\n\n    >>> labels = watershed(-distance, markers, mask=image)\n\n    The algorithm works also for 3-D images, and can be used for example to\n    separate overlapping spheres.\n    \"\"\"\n    image, markers, mask = _validate_inputs(image, markers, mask, connectivity)\n    connectivity, offset = _validate_connectivity(image.ndim, connectivity,\n                                                  offset)\n\n    # pad the image, markers, and mask so that we can use the mask to\n    # keep from running off the edges\n    pad_width = [(p, p) for p in offset]\n    image = np.pad(image, pad_width, mode='constant')\n    mask = np.pad(mask, pad_width, mode='constant').ravel()\n    output = np.pad(markers, pad_width, mode='constant')\n\n    flat_neighborhood = _offsets_to_raveled_neighbors(\n        image.shape, connectivity, center=offset)\n    marker_locations = np.flatnonzero(output)\n    image_strides = np.array(image.strides, dtype=np.intp) // image.itemsize\n\n    _watershed_cy.watershed_raveled(image.ravel(),\n                                    marker_locations, flat_neighborhood,\n                                    mask, image_strides, compactness,\n                                    output.ravel(),\n                                    watershed_line)\n\n    output = crop(output, pad_width, copy=True)\n\n    return output\n", "path": "skimage/segmentation/_watershed.py"}], "after_files": [{"content": "\"\"\"watershed.py - watershed algorithm\n\nThis module implements a watershed algorithm that apportions pixels into\nmarked basins. The algorithm uses a priority queue to hold the pixels\nwith the metric for the priority queue being pixel value, then the time\nof entry into the queue - this settles ties in favor of the closest marker.\n\nSome ideas taken from\nSoille, \"Automated Basin Delineation from Digital Elevation Models Using\nMathematical Morphology\", Signal Processing 20 (1990) 171-182.\n\nThe most important insight in the paper is that entry time onto the queue\nsolves two problems: a pixel should be assigned to the neighbor with the\nlargest gradient or, if there is no gradient, pixels on a plateau should\nbe split between markers on opposite sides.\n\"\"\"\n\nimport numpy as np\nfrom scipy import ndimage as ndi\n\nfrom . import _watershed_cy\nfrom ..morphology.extrema import local_minima\nfrom ..morphology._util import (_validate_connectivity,\n                                _offsets_to_raveled_neighbors)\nfrom ..util import crop, regular_seeds\n\n\ndef _validate_inputs(image, markers, mask, connectivity):\n    \"\"\"Ensure that all inputs to watershed have matching shapes and types.\n\n    Parameters\n    ----------\n    image : array\n        The input image.\n    markers : int or array of int\n        The marker image.\n    mask : array, or None\n        A boolean mask, True where we want to compute the watershed.\n    connectivity : int in {1, ..., image.ndim}\n        The connectivity of the neighborhood of a pixel.\n\n    Returns\n    -------\n    image, markers, mask : arrays\n        The validated and formatted arrays. Image will have dtype float64,\n        markers int32, and mask int8. If ``None`` was given for the mask,\n        it is a volume of all 1s.\n\n    Raises\n    ------\n    ValueError\n        If the shapes of the given arrays don't match.\n    \"\"\"\n    n_pixels = image.size\n    if mask is None:\n        # Use a complete `True` mask if none is provided\n        mask = np.ones(image.shape, bool)\n    else:\n        mask = np.asanyarray(mask, dtype=bool)\n        n_pixels = np.sum(mask)\n        if mask.shape != image.shape:\n            message = (f'`mask` (shape {mask.shape}) must have same shape '\n                       f'as `image` (shape {image.shape})')\n            raise ValueError(message)\n    if markers is None:\n        markers_bool = local_minima(image, connectivity=connectivity) * mask\n        footprint = ndi.generate_binary_structure(markers_bool.ndim, connectivity)\n        markers = ndi.label(markers_bool, structure=footprint)[0]\n    elif not isinstance(markers, (np.ndarray, list, tuple)):\n        # not array-like, assume int\n        # given int, assume that number of markers *within mask*.\n        markers = regular_seeds(image.shape,\n                                int(markers / (n_pixels / image.size)))\n        markers *= mask\n    else:\n        markers = np.asanyarray(markers) * mask\n        if markers.shape != image.shape:\n            message = (f'`markers` (shape {markers.shape}) must have same '\n                       f'shape as `image` (shape {image.shape})')\n            raise ValueError(message)\n    return (image.astype(np.float64),\n            markers,\n            mask.astype(np.int8))\n\n\ndef watershed(image, markers=None, connectivity=1, offset=None, mask=None,\n              compactness=0, watershed_line=False):\n    \"\"\"Find watershed basins in `image` flooded from given `markers`.\n\n    Parameters\n    ----------\n    image : ndarray (2-D, 3-D, ...)\n        Data array where the lowest value points are labeled first.\n    markers : int, or ndarray of int, same shape as `image`, optional\n        The desired number of markers, or an array marking the basins with the\n        values to be assigned in the label matrix. Zero means not a marker. If\n        ``None`` (no markers given), the local minima of the image are used as\n        markers.\n    connectivity : ndarray, optional\n        An array with the same number of dimensions as `image` whose\n        non-zero elements indicate neighbors for connection.\n        Following the scipy convention, default is a one-connected array of\n        the dimension of the image.\n    offset : array_like of shape image.ndim, optional\n        offset of the connectivity (one offset per dimension)\n    mask : ndarray of bools or 0s and 1s, optional\n        Array of same shape as `image`. Only points at which mask == True\n        will be labeled.\n    compactness : float, optional\n        Use compact watershed [3]_ with given compactness parameter.\n        Higher values result in more regularly-shaped watershed basins.\n    watershed_line : bool, optional\n        If watershed_line is True, a one-pixel wide line separates the regions\n        obtained by the watershed algorithm. The line has the label 0.\n        Note that the method used for adding this line expects that\n        marker regions are not adjacent; the watershed line may not catch\n        borders between adjacent marker regions.\n\n    Returns\n    -------\n    out : ndarray\n        A labeled matrix of the same type and shape as markers\n\n    See Also\n    --------\n    skimage.segmentation.random_walker : random walker segmentation\n        A segmentation algorithm based on anisotropic diffusion, usually\n        slower than the watershed but with good results on noisy data and\n        boundaries with holes.\n\n    Notes\n    -----\n    This function implements a watershed algorithm [1]_ [2]_ that apportions\n    pixels into marked basins. The algorithm uses a priority queue to hold\n    the pixels with the metric for the priority queue being pixel value, then\n    the time of entry into the queue - this settles ties in favor of the\n    closest marker.\n\n    Some ideas taken from\n    Soille, \"Automated Basin Delineation from Digital Elevation Models Using\n    Mathematical Morphology\", Signal Processing 20 (1990) 171-182\n\n    The most important insight in the paper is that entry time onto the queue\n    solves two problems: a pixel should be assigned to the neighbor with the\n    largest gradient or, if there is no gradient, pixels on a plateau should\n    be split between markers on opposite sides.\n\n    This implementation converts all arguments to specific, lowest common\n    denominator types, then passes these to a C algorithm.\n\n    Markers can be determined manually, or automatically using for example\n    the local minima of the gradient of the image, or the local maxima of the\n    distance function to the background for separating overlapping objects\n    (see example).\n\n    References\n    ----------\n    .. [1] https://en.wikipedia.org/wiki/Watershed_%28image_processing%29\n\n    .. [2] http://cmm.ensmp.fr/~beucher/wtshed.html\n\n    .. [3] Peer Neubert & Peter Protzel (2014). Compact Watershed and\n           Preemptive SLIC: On Improving Trade-offs of Superpixel Segmentation\n           Algorithms. ICPR 2014, pp 996-1001. :DOI:`10.1109/ICPR.2014.181`\n           https://www.tu-chemnitz.de/etit/proaut/publications/cws_pSLIC_ICPR.pdf\n\n    Examples\n    --------\n    The watershed algorithm is useful to separate overlapping objects.\n\n    We first generate an initial image with two overlapping circles:\n\n    >>> x, y = np.indices((80, 80))\n    >>> x1, y1, x2, y2 = 28, 28, 44, 52\n    >>> r1, r2 = 16, 20\n    >>> mask_circle1 = (x - x1)**2 + (y - y1)**2 < r1**2\n    >>> mask_circle2 = (x - x2)**2 + (y - y2)**2 < r2**2\n    >>> image = np.logical_or(mask_circle1, mask_circle2)\n\n    Next, we want to separate the two circles. We generate markers at the\n    maxima of the distance to the background:\n\n    >>> from scipy import ndimage as ndi\n    >>> distance = ndi.distance_transform_edt(image)\n    >>> from skimage.feature import peak_local_max\n    >>> max_coords = peak_local_max(distance, labels=image,\n    ...                             footprint=np.ones((3, 3)))\n    >>> local_maxima = np.zeros_like(image, dtype=bool)\n    >>> local_maxima[tuple(max_coords.T)] = True\n    >>> markers = ndi.label(local_maxima)[0]\n\n    Finally, we run the watershed on the image and markers:\n\n    >>> labels = watershed(-distance, markers, mask=image)\n\n    The algorithm works also for 3-D images, and can be used for example to\n    separate overlapping spheres.\n    \"\"\"\n    image, markers, mask = _validate_inputs(image, markers, mask, connectivity)\n    connectivity, offset = _validate_connectivity(image.ndim, connectivity,\n                                                  offset)\n\n    # pad the image, markers, and mask so that we can use the mask to\n    # keep from running off the edges\n    pad_width = [(p, p) for p in offset]\n    image = np.pad(image, pad_width, mode='constant')\n    mask = np.pad(mask, pad_width, mode='constant').ravel()\n    output = np.pad(markers, pad_width, mode='constant')\n\n    flat_neighborhood = _offsets_to_raveled_neighbors(\n        image.shape, connectivity, center=offset)\n    marker_locations = np.flatnonzero(output)\n    image_strides = np.array(image.strides, dtype=np.intp) // image.itemsize\n\n    _watershed_cy.watershed_raveled(image.ravel(),\n                                    marker_locations, flat_neighborhood,\n                                    mask, image_strides, compactness,\n                                    output.ravel(),\n                                    watershed_line)\n\n    output = crop(output, pad_width, copy=True)\n\n    return output\n", "path": "skimage/segmentation/_watershed.py"}]}