1 // Copyright (C) 1999 Andy Adler <adler@sce.carleton.ca>
2 //
3 // This program is free software; you can redistribute it and/or modify it under
4 // the terms of the GNU General Public License as published by the Free Software
5 // Foundation; either version 3 of the License, or (at your option) any later
6 // version.
7 //
8 // This program is distributed in the hope that it will be useful, but WITHOUT
9 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
11 // details.
12 //
13 // You should have received a copy of the GNU General Public License along with
14 // this program; if not, see <http://www.gnu.org/licenses/>.
15
16 #include <vector>
17
18 #include <octave/oct.h>
19
20 #define ptUP (-1)
21 #define ptDN (+1)
22 #define ptRT (+ioM)
23 #define ptLF (-ioM)
24
25 /*
26 * check if the point needs to be filled, if so
27 * fill it and change the appropriate variables
28 */
checkpoint(int pt,unsigned char * imo,int * ptstack,int * npoints)29 void checkpoint (int pt, unsigned char *imo, int *ptstack, int *npoints)
30 {
31 // printf("filling %d np=%d fill=%d\n",pt,*npoints, *(imo+pt)==0 );
32 if (*(imo+pt) != 0) return;
33
34 *(imo+pt) = 2;
35 *(ptstack + (*npoints))= pt;
36 (*npoints)++;
37 }
38
39 DEFUN_DLD (bwfill, args, ,"\
40 -*- texinfo -*-\n\
41 @deftypefn {Loadable Function} {[@var{bw2}, @var{idx}] =} bwfill(@var{bw1}, @var{c}, @var{r}, @var{n})\n\
42 Perform a flood-fill operation on the binary image @var{bw1}.\n\
43 \n\
44 The flood-filling starts in the pixel (@var{r}, @var{c}). If @var{r} and @var{c}\n\
45 are vectors of the same length, each pixel pair (@var{r}(i), @var{c}(i)) will\n\
46 be a starting point for a flood-fill operation.\n\
47 The argument @var{n} changes the neighborhood connectivity (of the holes) for the flood-fill\n\
48 operation. @var{n} can be either 4 or 8, and has a default value of 8.\n\
49 \n\
50 Note that @var{n} is the connectivity of the foreground, and not of the background,\n\
51 even though the function acts on the background.\n\
52 \n\
53 The output is the processed image @var{bw2} and the indexes of the filled\n\
54 pixels @var{idx}\n\
55 \n\
56 @end deftypefn\n\
57 @deftypefn {Loadable Function} {[@var{bw2}, @var{idx}] =} bwfill(@var{bw1}, \"holes\", @var{n})\n\
58 If the string \"holes\" is given instead of starting points for the flood-fill\n\
59 operation, the function finds interior holes in @var{bw1} and fills them.\n\
60 \n\
61 Note: bwfill is not recommended. Please use \"imfill\" instead.\n\
62 @seealso{imfill}\n\
63 @end deftypefn\n\
64 ")
65 {
66 octave_value_list retval;
67 octave_value tmp;
68 ColumnVector xseed, yseed ;
69 const int nargin = args.length ();
70
71 if (nargin < 2 || nargin > 4)
72 print_usage ();
73
74 const Matrix im = args (0).matrix_value ();
75 const int imM = im.rows ();
76 const int imN = im.columns ();
77
78 if (imM == 1 || imN == 1) // check for vector inputs.
79 {
80 retval (0) = im;
81 retval (1) = ColumnVector (0);
82 return retval;
83 }
84
85 int nb = 8;
86 int npoints = 0;
87 bool fillmode = false;
88 if (args (1).is_string () && args (1).string_value () == "holes")
89 {
90 // usage: bwfill (A, "holes", [N])
91 if (nargin > 3)
92 print_usage ();
93 fillmode = true;
94
95 npoints = 2 * (imM + imN - 4); // don't start fill from corners
96
97 xseed = ColumnVector (npoints);
98 yseed = ColumnVector (npoints);
99 int idx = 0;
100 for (int j = 2; j <= imN-1; j++)
101 {
102 xseed (idx) = j;
103 yseed (idx++) = 1;
104 xseed (idx) = j;
105 yseed (idx++) = imM;
106 }
107
108 for (int i = 2; i <= imM-1; i++)
109 {
110 yseed (idx) = i;
111 xseed (idx++) = 1;
112 yseed (idx) = i;
113 xseed (idx++) = imN;
114 }
115
116 if (nargin >= 3)
117 nb = (int)args (2).double_value ();
118 }
119 else
120 {
121 // usage: bwfill (A, C, R, [N])
122 if (nargin < 3)
123 print_usage ();
124
125 {
126 ColumnVector tmp (args (1).vector_value ());
127 xseed = tmp;
128 }
129 {
130 ColumnVector tmp (args (2).vector_value ());
131 yseed = tmp;
132 }
133 npoints= xseed.numel ();
134 if (nargin >= 4)
135 nb = (int)args (3).double_value ();
136 }
137
138 if (nb != 4 && nb != 8)
139 error ("bwfill: connectivity must be 4 or 8");
140
141 /*
142 * put a one pixel thick boundary around the image
143 * so that we can be more efficient in the main loop
144 */
145 int ioM = imM + 2;
146 std::vector<unsigned char> imo ((imM+2) * (imN+2));
147
148 for (int i = 0; i < imM; i++)
149 for (int j = 0; j < imN; j++)
150 imo[(i+1) + ioM*(j+1)] = (im (i, j) > 0);
151
152 for (int i = 0; i < ioM; i++)
153 imo[i]= imo[i + ioM*(imN+1)] = 3;
154
155 for (int j = 1; j < imN+1; j++)
156 imo[ioM*j]= imo[imM+1 + ioM*j] = 3;
157
158 // This is obviously big enough for the point stack, but I'm
159 // sure it can be smaller.
160 std::vector<int> ptstack (ioM*imN);
161
162 int seedidx = npoints;
163 npoints = 0;
164 while ((--seedidx) >= 0)
165 {
166 // no need to add 1 to convert indexing style because we're adding a boundary
167 const int x = xseed (seedidx);
168 const int y = yseed (seedidx);
169 if (x < 1 || y < 1 || x > imN || y > imM)
170 {
171 warning ("bwfill: (%d, %d) out of bounds", x, y);
172 continue;
173 }
174 const int pt = x * ioM + y;
175 checkpoint (pt , imo.data (), ptstack.data (), &npoints);
176 }
177
178 while (npoints > 0)
179 {
180 npoints--;
181 int pt = ptstack[npoints];
182
183 checkpoint (pt + ptLF, imo.data (), ptstack.data (), &npoints);
184 checkpoint (pt + ptRT, imo.data (), ptstack.data (), &npoints);
185 checkpoint (pt + ptUP, imo.data (), ptstack.data (), &npoints);
186 checkpoint (pt + ptDN, imo.data (), ptstack.data (), &npoints);
187
188 if (nb==4)
189 {
190 checkpoint (pt + ptLF + ptUP, imo.data (), ptstack.data (), &npoints);
191 checkpoint (pt + ptRT + ptUP, imo.data (), ptstack.data (), &npoints);
192 checkpoint (pt + ptLF + ptDN, imo.data (), ptstack.data (), &npoints);
193 checkpoint (pt + ptRT + ptDN, imo.data (), ptstack.data (), &npoints);
194 }
195 } // while ( npoints > 0)
196
197 boolNDArray imout (dim_vector (imM, imN));
198 ColumnVector idxout (imM*imN);
199 int idx = 0;
200
201 int notvalidpt = 0;
202 int idxpoint = 2;
203 if (fillmode)
204 {
205 notvalidpt = 2;
206 idxpoint = 0;
207 }
208
209 for (int i = 0; i < imM; i++)
210 for (int j = 0; j < imN; j++)
211 {
212 imout (i, j) = imo[(i+1) + ioM*(j+1)] != notvalidpt;
213 if (imo[(i+1) + ioM*(j+1)] == idxpoint)
214 idxout (idx++) = (double) (i + j*imM + 1);
215 }
216
217 /*
218 Matrix imout( imM+2, imN+2 );
219 for (int i=0; i<imM+2; i++)
220 for (int j=0; j<imN+2; j++)
221 imout(i,j) = (double) imo[i + ioM*j];
222 */
223
224 retval (0) = imout;
225 // we need to do this to be able to return a proper empty vector
226 if (idx > 0)
227 retval (1) = idxout.extract (0, idx-1);
228 else
229 retval (1) = ColumnVector (0);
230 return retval;
231 }
232
233 /*
234 %!test
235 %! A = [0 1 0 0 1; 1 0 1 0 0; 1 0 1 1 0; 1 1 1 0 0; 1 0 0 1 0];
236 %! R4 = logical(ones(5));
237 %! R8 = logical([1 1 0 0 1; 1 0 1 0 0; 1 0 1 1 0; 1 1 1 0 0; 1 0 0 1 0]);
238 %! assert (bwfill (A,1,1,4), R4)
239 %! assert (bwfill (A,1,1,8), R8)
240 %! assert (bwfill (A,1,1), R8)
241 %! B = logical([0 1 0 0 1; 1 0 1 0 0; 1 0 1 1 0; 1 1 1 0 0; 1 0 0 1 0]);
242 %! assert (bwfill (A,3,3,4), B)
243 %! assert (bwfill (A,3,3,8), B)
244 %! assert (bwfill (A,3,3), B)
245 %! C = logical ([0 1 1 1 1; 1 0 1 1 1; 1 0 1 1 1; 1 1 1 1 1; 1 0 0 1 1]);
246 %! assert (bwfill (A,3,1,8), C)
247 %! assert (bwfill (A,3,1,4), R4)
248 %! assert (bwfill (A, [3 1], [1 3], 4), R4);
249 %! D = logical([0 1 1 1 1; 1 0 1 1 1; 1 0 1 1 1; 1 1 1 1 1; 1 0 0 1 1]);
250 %! assert (bwfill (A, [3 1], [1 3], 8), D);
251 %! assert (bwfill (A, [3 1], [1 3]), D);
252 %! E = logical ([0 1 0 0 1; 1 0 1 0 0; 1 0 1 1 0; 1 1 1 0 0; 1 0 0 1 0]);
253 %! assert (bwfill (A, "holes", 4), E);
254 %! F = logical ([1 1 0 0 1; 1 1 1 0 0; 1 1 1 1 0; 1 1 1 0 0; 1 0 0 1 0]);
255 %! assert (bwfill (A, "holes", 8), F);
256 %! assert (bwfill (A, "holes"), F);
257
258 %!error id=Octave:invalid-fun-call bwfill ()
259 %!error id=Octave:invalid-fun-call bwfill ("aaa")
260 %!error id=Octave:invalid-fun-call bwfill (rand (5) > 0.5)
261 %!error id=Octave:invalid-fun-call bwfill (rand (5) > 0.5, 2)
262 %!error <bwfill: connectivity must be 4 or 8> bwfill (rand (5) > 0.5, "holes", 1)
263 %!error <bwfill: connectivity must be 4 or 8> bwfill (rand (5) > 0.5, 2, 2, 5)
264 %!error id=Octave:invalid-fun-call bwfill (rand (5) > 0.5, "xxx")
265 %!error id=Octave:invalid-fun-call bwfill (rand (5) > 0.5, 2, 2, 4, 5)
266 %!error id=Octave:invalid-fun-call bwfill (rand (5) > 0.5, "holes", 4, 2)
267 */
268