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
|
%global _empty_manifest_terminate_build 0
Name: python-fill-voids
Version: 2.0.4
Release: 1
Summary: Fill voids in 3D binary images fast.
License: GPLv3+
URL: https://github.com/seung-lab/fill_voids/
Source0: https://mirrors.nju.edu.cn/pypi/web/packages/74/fd/8de036e87e2bf9c1c890d26bc76bd7455866d1131f29b796dc424dfb192d/fill_voids-2.0.4.tar.gz
Requires: python3-numpy
Requires: python3-fastremap
%description
[](https://badge.fury.io/py/fill-voids)
# Fill Voids
```python
# PYTHON
import fill_voids
img = ... # 2d or 3d binary image
filled_image = fill_voids.fill(img, in_place=False) # in_place allows editing of original image
filled_image, N = fill_voids.fill(img, return_fill_count=True) # returns number of voxels filled in
```
```cpp
// C++
#include "fill_voids.hpp"
size_t sx, sy, sz;
sx = sy = sz = 512;
uint8_t* labels = ...; // 512x512x512 binary image
// modifies labels as a side effect, returns number of voxels filled in
size_t fill_ct = fill_voids::binary_fill_holes<uint8_t>(labels, sx, sy, sz); // 3D
// let labels now represent a 512x512 2D image
size_t fill_ct = fill_voids::binary_fill_holes<uint8_t>(labels, sx, sy); // 2D
```
<p style="font-style: italics;" align="center">
<img height=384 src="https://raw.githubusercontent.com/seung-lab/fill_voids/master/comparison.png" alt="Filling five labels using SciPy binary_fill_holes vs fill_voids from a 512x512x512 densely labeled connectomics segmentation. (black) fill_voids 1.1.0 (blue) fill_voids 1.1.0 with `in_place=True` (red) scipy 1.4.1" /><br>
Fig. 1: Filling five labels using SciPy binary_fill_holes vs fill_voids from a 512x512x512 densely labeled connectomics segmentation. (black) fill_voids 1.1.0 (blue) fill_voids 1.1.0 with `in_place=True` (red) scipy 1.4.1. In this test, fill_voids (`in_place=False`) is significantly faster than scipy with lower memory usage.
</p>
This library contains both 2D and 3D void filling algorithms, similar in function to [`scipy.ndimage.morphology.binary_fill_holes`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.ndimage.binary_fill_holes.html), but with an eye towards higher performance. The SciPy hole filling algorithm uses slow serial dilations.
The current version of this library uses a scan line flood fill of the background labels and then labels everything not filled as foreground.
### pip Installation
```bash
pip install fill-voids
```
If there's no binary for your platform and you have a C++ compiler try:
```bash
sudo apt-get install python3-dev # This is for Ubuntu, but whatever is appropriate for you
pip install numpy
pip install fill-voids --no-binary :all:
```
### Current Algorithm
1. Raster scan and mark every foreground voxel `2` for pre-existing foreground.
2. Raster scan each face of the current image and the first time a black pixel (`0`) is encountered after either starting or enountering a foreground pixel, add that location to a stack.
3. Flood fill (six connected) with the visited background color (`1`) in sequence from each location in the stack that is not already foreground.
4. Write out a binary image the same size as the input mapped as buffer != 1 (i.e. 0 or 2). This means non-visited holes and foreground will be marked as `1` for foreground and the visited background will be marked as `0`.
We improve performance significantly by using libdivide to make computing x,y,z coordinates from array index faster, by scanning right and left to take advantage of machine memory speed, by only placing a neighbor on the stack when we've either just started a scan or just passed a foreground pixel while scanning.
### Multi-Label Concept
Similarly to the [connected-components-3d](https://github.com/seung-lab/connected-components-3d) and [euclidean-distance-3d](https://github.com/seung-lab/euclidean-distance-transform-3d) projects, in connectomics, it can be common to want to apply void filling algorithms to all labels within a densely packed volume. A multi-label algorithm can be much faster than even the fastest serial application of a binary algorithm. Here's how this might go given an input image I:
1. Compute M = max(I)
2. Perform the fill as in the binary algorithm labeling the surrounding void as M+1. This means all voids are now either legitimate and can be filled or holes in-between labels.
3. Raster scan through the volume. If a new void is encountered, we must determine if it is fillable or an in-between one which will not be filled.
4. On encountering the void, record the last label seen and contour trace around it. If only that label is encountered during contour tracing, it is fillable. If another label is encountered, it is not fillable.
5. During the contour trace, mark the trace using an integer not already used, such as M+2. If that label is encountered in the future, you'll know what to fill between it and the next label encountered based on the fillable determination. This phase stops when either the twin of the first M+2 label is encountered or when futher contour tracing isn't possible (in the case of single voxel gaps).
6. (Inner Labels) If another label is encountered in the middle of a void, contour trace around it and mark the boundary with the same M+2 label that started the current fill.
%package -n python3-fill-voids
Summary: Fill voids in 3D binary images fast.
Provides: python-fill-voids
BuildRequires: python3-devel
BuildRequires: python3-setuptools
BuildRequires: python3-pip
BuildRequires: python3-cffi
BuildRequires: gcc
BuildRequires: gdb
%description -n python3-fill-voids
[](https://badge.fury.io/py/fill-voids)
# Fill Voids
```python
# PYTHON
import fill_voids
img = ... # 2d or 3d binary image
filled_image = fill_voids.fill(img, in_place=False) # in_place allows editing of original image
filled_image, N = fill_voids.fill(img, return_fill_count=True) # returns number of voxels filled in
```
```cpp
// C++
#include "fill_voids.hpp"
size_t sx, sy, sz;
sx = sy = sz = 512;
uint8_t* labels = ...; // 512x512x512 binary image
// modifies labels as a side effect, returns number of voxels filled in
size_t fill_ct = fill_voids::binary_fill_holes<uint8_t>(labels, sx, sy, sz); // 3D
// let labels now represent a 512x512 2D image
size_t fill_ct = fill_voids::binary_fill_holes<uint8_t>(labels, sx, sy); // 2D
```
<p style="font-style: italics;" align="center">
<img height=384 src="https://raw.githubusercontent.com/seung-lab/fill_voids/master/comparison.png" alt="Filling five labels using SciPy binary_fill_holes vs fill_voids from a 512x512x512 densely labeled connectomics segmentation. (black) fill_voids 1.1.0 (blue) fill_voids 1.1.0 with `in_place=True` (red) scipy 1.4.1" /><br>
Fig. 1: Filling five labels using SciPy binary_fill_holes vs fill_voids from a 512x512x512 densely labeled connectomics segmentation. (black) fill_voids 1.1.0 (blue) fill_voids 1.1.0 with `in_place=True` (red) scipy 1.4.1. In this test, fill_voids (`in_place=False`) is significantly faster than scipy with lower memory usage.
</p>
This library contains both 2D and 3D void filling algorithms, similar in function to [`scipy.ndimage.morphology.binary_fill_holes`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.ndimage.binary_fill_holes.html), but with an eye towards higher performance. The SciPy hole filling algorithm uses slow serial dilations.
The current version of this library uses a scan line flood fill of the background labels and then labels everything not filled as foreground.
### pip Installation
```bash
pip install fill-voids
```
If there's no binary for your platform and you have a C++ compiler try:
```bash
sudo apt-get install python3-dev # This is for Ubuntu, but whatever is appropriate for you
pip install numpy
pip install fill-voids --no-binary :all:
```
### Current Algorithm
1. Raster scan and mark every foreground voxel `2` for pre-existing foreground.
2. Raster scan each face of the current image and the first time a black pixel (`0`) is encountered after either starting or enountering a foreground pixel, add that location to a stack.
3. Flood fill (six connected) with the visited background color (`1`) in sequence from each location in the stack that is not already foreground.
4. Write out a binary image the same size as the input mapped as buffer != 1 (i.e. 0 or 2). This means non-visited holes and foreground will be marked as `1` for foreground and the visited background will be marked as `0`.
We improve performance significantly by using libdivide to make computing x,y,z coordinates from array index faster, by scanning right and left to take advantage of machine memory speed, by only placing a neighbor on the stack when we've either just started a scan or just passed a foreground pixel while scanning.
### Multi-Label Concept
Similarly to the [connected-components-3d](https://github.com/seung-lab/connected-components-3d) and [euclidean-distance-3d](https://github.com/seung-lab/euclidean-distance-transform-3d) projects, in connectomics, it can be common to want to apply void filling algorithms to all labels within a densely packed volume. A multi-label algorithm can be much faster than even the fastest serial application of a binary algorithm. Here's how this might go given an input image I:
1. Compute M = max(I)
2. Perform the fill as in the binary algorithm labeling the surrounding void as M+1. This means all voids are now either legitimate and can be filled or holes in-between labels.
3. Raster scan through the volume. If a new void is encountered, we must determine if it is fillable or an in-between one which will not be filled.
4. On encountering the void, record the last label seen and contour trace around it. If only that label is encountered during contour tracing, it is fillable. If another label is encountered, it is not fillable.
5. During the contour trace, mark the trace using an integer not already used, such as M+2. If that label is encountered in the future, you'll know what to fill between it and the next label encountered based on the fillable determination. This phase stops when either the twin of the first M+2 label is encountered or when futher contour tracing isn't possible (in the case of single voxel gaps).
6. (Inner Labels) If another label is encountered in the middle of a void, contour trace around it and mark the boundary with the same M+2 label that started the current fill.
%package help
Summary: Development documents and examples for fill-voids
Provides: python3-fill-voids-doc
%description help
[](https://badge.fury.io/py/fill-voids)
# Fill Voids
```python
# PYTHON
import fill_voids
img = ... # 2d or 3d binary image
filled_image = fill_voids.fill(img, in_place=False) # in_place allows editing of original image
filled_image, N = fill_voids.fill(img, return_fill_count=True) # returns number of voxels filled in
```
```cpp
// C++
#include "fill_voids.hpp"
size_t sx, sy, sz;
sx = sy = sz = 512;
uint8_t* labels = ...; // 512x512x512 binary image
// modifies labels as a side effect, returns number of voxels filled in
size_t fill_ct = fill_voids::binary_fill_holes<uint8_t>(labels, sx, sy, sz); // 3D
// let labels now represent a 512x512 2D image
size_t fill_ct = fill_voids::binary_fill_holes<uint8_t>(labels, sx, sy); // 2D
```
<p style="font-style: italics;" align="center">
<img height=384 src="https://raw.githubusercontent.com/seung-lab/fill_voids/master/comparison.png" alt="Filling five labels using SciPy binary_fill_holes vs fill_voids from a 512x512x512 densely labeled connectomics segmentation. (black) fill_voids 1.1.0 (blue) fill_voids 1.1.0 with `in_place=True` (red) scipy 1.4.1" /><br>
Fig. 1: Filling five labels using SciPy binary_fill_holes vs fill_voids from a 512x512x512 densely labeled connectomics segmentation. (black) fill_voids 1.1.0 (blue) fill_voids 1.1.0 with `in_place=True` (red) scipy 1.4.1. In this test, fill_voids (`in_place=False`) is significantly faster than scipy with lower memory usage.
</p>
This library contains both 2D and 3D void filling algorithms, similar in function to [`scipy.ndimage.morphology.binary_fill_holes`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.ndimage.binary_fill_holes.html), but with an eye towards higher performance. The SciPy hole filling algorithm uses slow serial dilations.
The current version of this library uses a scan line flood fill of the background labels and then labels everything not filled as foreground.
### pip Installation
```bash
pip install fill-voids
```
If there's no binary for your platform and you have a C++ compiler try:
```bash
sudo apt-get install python3-dev # This is for Ubuntu, but whatever is appropriate for you
pip install numpy
pip install fill-voids --no-binary :all:
```
### Current Algorithm
1. Raster scan and mark every foreground voxel `2` for pre-existing foreground.
2. Raster scan each face of the current image and the first time a black pixel (`0`) is encountered after either starting or enountering a foreground pixel, add that location to a stack.
3. Flood fill (six connected) with the visited background color (`1`) in sequence from each location in the stack that is not already foreground.
4. Write out a binary image the same size as the input mapped as buffer != 1 (i.e. 0 or 2). This means non-visited holes and foreground will be marked as `1` for foreground and the visited background will be marked as `0`.
We improve performance significantly by using libdivide to make computing x,y,z coordinates from array index faster, by scanning right and left to take advantage of machine memory speed, by only placing a neighbor on the stack when we've either just started a scan or just passed a foreground pixel while scanning.
### Multi-Label Concept
Similarly to the [connected-components-3d](https://github.com/seung-lab/connected-components-3d) and [euclidean-distance-3d](https://github.com/seung-lab/euclidean-distance-transform-3d) projects, in connectomics, it can be common to want to apply void filling algorithms to all labels within a densely packed volume. A multi-label algorithm can be much faster than even the fastest serial application of a binary algorithm. Here's how this might go given an input image I:
1. Compute M = max(I)
2. Perform the fill as in the binary algorithm labeling the surrounding void as M+1. This means all voids are now either legitimate and can be filled or holes in-between labels.
3. Raster scan through the volume. If a new void is encountered, we must determine if it is fillable or an in-between one which will not be filled.
4. On encountering the void, record the last label seen and contour trace around it. If only that label is encountered during contour tracing, it is fillable. If another label is encountered, it is not fillable.
5. During the contour trace, mark the trace using an integer not already used, such as M+2. If that label is encountered in the future, you'll know what to fill between it and the next label encountered based on the fillable determination. This phase stops when either the twin of the first M+2 label is encountered or when futher contour tracing isn't possible (in the case of single voxel gaps).
6. (Inner Labels) If another label is encountered in the middle of a void, contour trace around it and mark the boundary with the same M+2 label that started the current fill.
%prep
%autosetup -n fill-voids-2.0.4
%build
%py3_build
%install
%py3_install
install -d -m755 %{buildroot}/%{_pkgdocdir}
if [ -d doc ]; then cp -arf doc %{buildroot}/%{_pkgdocdir}; fi
if [ -d docs ]; then cp -arf docs %{buildroot}/%{_pkgdocdir}; fi
if [ -d example ]; then cp -arf example %{buildroot}/%{_pkgdocdir}; fi
if [ -d examples ]; then cp -arf examples %{buildroot}/%{_pkgdocdir}; fi
pushd %{buildroot}
if [ -d usr/lib ]; then
find usr/lib -type f -printf "/%h/%f\n" >> filelist.lst
fi
if [ -d usr/lib64 ]; then
find usr/lib64 -type f -printf "/%h/%f\n" >> filelist.lst
fi
if [ -d usr/bin ]; then
find usr/bin -type f -printf "/%h/%f\n" >> filelist.lst
fi
if [ -d usr/sbin ]; then
find usr/sbin -type f -printf "/%h/%f\n" >> filelist.lst
fi
touch doclist.lst
if [ -d usr/share/man ]; then
find usr/share/man -type f -printf "/%h/%f.gz\n" >> doclist.lst
fi
popd
mv %{buildroot}/filelist.lst .
mv %{buildroot}/doclist.lst .
%files -n python3-fill-voids -f filelist.lst
%dir %{python3_sitearch}/*
%files help -f doclist.lst
%{_docdir}/*
%changelog
* Wed May 10 2023 Python_Bot <Python_Bot@openeuler.org> - 2.0.4-1
- Package Spec generated
|
