scikit-image

1
#cython: cdivision=True
2
#cython: boundscheck=False
3
#cython: nonecheck=False
4
#cython: wraparound=False
5

6
"""Cython code used in _flood_fill.py."""
7

8
cimport numpy as cnp
9
cnp.import_array()
10

11
# Must be defined to use QueueWithHistory
12
ctypedef Py_ssize_t QueueItem
13

14
include "../morphology/_queue_with_history.pxi"
15

16

17
ctypedef fused dtype_t:
18
    cnp.uint8_t
19
    cnp.uint16_t
20
    cnp.uint32_t
21
    cnp.uint64_t
22
    cnp.int8_t
23
    cnp.int16_t
24
    cnp.int32_t
25
    cnp.int64_t
26
    cnp.float32_t
27
    cnp.float64_t
28

29

30
# Definition of flag values used for `flags` in _flood_fill & _fill_plateau
31
cdef:
32
    # Border value - do not cross!
33
    unsigned char BORDER = 2
34
    # Part of the flood fill
35
    unsigned char FILL = 1
36
    # Not checked yet
37
    unsigned char UNKNOWN = 0
38

39

40
cpdef inline void _flood_fill_equal(dtype_t[::1] image,
41
                                    unsigned char[::1] flags,
42
                                    Py_ssize_t[::1] neighbor_offsets,
43
                                    Py_ssize_t start_index,
44
                                    dtype_t seed_value):
45
    """Find connected areas to fill, requiring strict equality.
46

47
    Parameters
48
    ----------
49
    image : ndarray, one-dimensional
50
        The raveled view of a n-dimensional array.
51
    flags : ndarray, one-dimensional
52
        An array of flags that is used to store the state of each pixel during
53
        evaluation.
54
    neighbor_offsets : ndarray
55
        A one-dimensional array that contains the offsets to find the
56
        connected neighbors for any index in `image`.
57
    start_index : int
58
        Start position for the flood-fill.
59
    seed_value :
60
        Value of ``image[start_index]``.
61
    """
62
    cdef:
63
        QueueWithHistory queue
64
        QueueItem current_index, neighbor
65

66
    with nogil:
67
        # Initialize the queue
68
        queue_init(&queue, 64)
69
        try:
70
            queue_push(&queue, &start_index)
71
            flags[start_index] = FILL
72
            # Break loop if all queued positions were evaluated
73
            while queue_pop(&queue, &current_index):
74
                # Look at all neighboring samples
75
                for i in range(neighbor_offsets.shape[0]):
76
                    neighbor = current_index + neighbor_offsets[i]
77

78
                    # Shortcut if neighbor is already part of fill
79
                    if flags[neighbor] == UNKNOWN:
80
                        if image[neighbor] == seed_value:
81
                            # Neighbor is in fill; check its neighbors too.
82
                            flags[neighbor] = FILL
83
                            queue_push(&queue, &neighbor)
84
        finally:
85
            # Ensure memory released
86
            queue_exit(&queue)
87

88

89
cpdef inline void _flood_fill_tolerance(dtype_t[::1] image,
90
                                        unsigned char[::1] flags,
91
                                        Py_ssize_t[::1] neighbor_offsets,
92
                                        Py_ssize_t start_index,
93
                                        dtype_t seed_value,
94
                                        dtype_t low_tol,
95
                                        dtype_t high_tol):
96
    """Find connected areas to fill, within a tolerance.
97

98
    Parameters
99
    ----------
100
    image : ndarray, one-dimensional
101
        The raveled view of a n-dimensional array.
102
    flags : ndarray, one-dimensional
103
        An array of flags that is used to store the state of each pixel during
104
        evaluation.
105
    neighbor_offsets : ndarray
106
        A one-dimensional array that contains the offsets to find the
107
        connected neighbors for any index in `image`.
108
    start_index : int
109
        Start position for the flood-fill.
110
    seed_value :
111
        Value of ``image[start_index]``.
112
    low_tol :
113
        Lower limit for tolerance comparison.
114
    high_tol :
115
        Upper limit for tolerance comparison.
116
    """
117
    cdef:
118
        QueueWithHistory queue
119
        QueueItem current_index, neighbor
120

121
    with nogil:
122
        # Initialize the queue and push start position
123
        queue_init(&queue, 64)
124
        try:
125
            queue_push(&queue, &start_index)
126
            flags[start_index] = FILL
127
            # Break loop if all queued positions were evaluated
128
            while queue_pop(&queue, &current_index):
129
                # Look at all neighboring samples
130
                for i in range(neighbor_offsets.shape[0]):
131
                    neighbor = current_index + neighbor_offsets[i]
132

133
                    # Only do comparisons on points not (yet) part of fill
134
                    if flags[neighbor] == UNKNOWN:
135
                        if low_tol <= image[neighbor] <= high_tol:
136
                            # Neighbor is in fill; check its neighbors too.
137
                            flags[neighbor] = FILL
138
                            queue_push(&queue, &neighbor)
139
        finally:
140
            # Ensure memory released
141
            queue_exit(&queue)
142