/
_flood_fill_cy.pyx
141 lines (123 loc) · 4.75 KB
/
_flood_fill_cy.pyx
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
#cython: cdivision=True
#cython: boundscheck=False
#cython: nonecheck=False
#cython: wraparound=False
"""Cython code used in _flood_fill.py."""
cimport numpy as cnp
cnp.import_array()
# Must be defined to use QueueWithHistory
ctypedef Py_ssize_t QueueItem
include "../morphology/_queue_with_history.pxi"
ctypedef fused dtype_t:
cnp.uint8_t
cnp.uint16_t
cnp.uint32_t
cnp.uint64_t
cnp.int8_t
cnp.int16_t
cnp.int32_t
cnp.int64_t
cnp.float32_t
cnp.float64_t
# Definition of flag values used for `flags` in _flood_fill & _fill_plateau
cdef:
# Border value - do not cross!
unsigned char BORDER = 2
# Part of the flood fill
unsigned char FILL = 1
# Not checked yet
unsigned char UNKNOWN = 0
cpdef inline void _flood_fill_equal(dtype_t[::1] image,
unsigned char[::1] flags,
Py_ssize_t[::1] neighbor_offsets,
Py_ssize_t start_index,
dtype_t seed_value):
"""Find connected areas to fill, requiring strict equality.
Parameters
----------
image : ndarray, one-dimensional
The raveled view of a n-dimensional array.
flags : ndarray, one-dimensional
An array of flags that is used to store the state of each pixel during
evaluation.
neighbor_offsets : ndarray
A one-dimensional array that contains the offsets to find the
connected neighbors for any index in `image`.
start_index : int
Start position for the flood-fill.
seed_value :
Value of ``image[start_index]``.
"""
cdef:
QueueWithHistory queue
QueueItem current_index, neighbor
with nogil:
# Initialize the queue
queue_init(&queue, 64)
try:
queue_push(&queue, &start_index)
flags[start_index] = FILL
# Break loop if all queued positions were evaluated
while queue_pop(&queue, ¤t_index):
# Look at all neighboring samples
for i in range(neighbor_offsets.shape[0]):
neighbor = current_index + neighbor_offsets[i]
# Shortcut if neighbor is already part of fill
if flags[neighbor] == UNKNOWN:
if image[neighbor] == seed_value:
# Neighbor is in fill; check its neighbors too.
flags[neighbor] = FILL
queue_push(&queue, &neighbor)
finally:
# Ensure memory released
queue_exit(&queue)
cpdef inline void _flood_fill_tolerance(dtype_t[::1] image,
unsigned char[::1] flags,
Py_ssize_t[::1] neighbor_offsets,
Py_ssize_t start_index,
dtype_t seed_value,
dtype_t low_tol,
dtype_t high_tol):
"""Find connected areas to fill, within a tolerance.
Parameters
----------
image : ndarray, one-dimensional
The raveled view of a n-dimensional array.
flags : ndarray, one-dimensional
An array of flags that is used to store the state of each pixel during
evaluation.
neighbor_offsets : ndarray
A one-dimensional array that contains the offsets to find the
connected neighbors for any index in `image`.
start_index : int
Start position for the flood-fill.
seed_value :
Value of ``image[start_index]``.
low_tol :
Lower limit for tolerance comparison.
high_tol :
Upper limit for tolerance comparison.
"""
cdef:
QueueWithHistory queue
QueueItem current_index, neighbor
with nogil:
# Initialize the queue and push start position
queue_init(&queue, 64)
try:
queue_push(&queue, &start_index)
flags[start_index] = FILL
# Break loop if all queued positions were evaluated
while queue_pop(&queue, ¤t_index):
# Look at all neighboring samples
for i in range(neighbor_offsets.shape[0]):
neighbor = current_index + neighbor_offsets[i]
# Only do comparisons on points not (yet) part of fill
if flags[neighbor] == UNKNOWN:
if low_tol <= image[neighbor] <= high_tol:
# Neighbor is in fill; check its neighbors too.
flags[neighbor] = FILL
queue_push(&queue, &neighbor)
finally:
# Ensure memory released
queue_exit(&queue)