1 /*M///////////////////////////////////////////////////////////////////////////////////////
2 //
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
4 //
5 // By downloading, copying, installing or using the software you agree to this license.
6 // If you do not agree to this license, do not download, install,
7 // copy or use the software.
8 //
9 //
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
12 //
13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
14 // Third party copyrights are property of their respective owners.
15 //
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
18 //
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
21 //
22 // * Redistribution's in binary form must reproduce the above copyright notice,
23 // this list of conditions and the following disclaimer in the documentation
24 // and/or other materials provided with the distribution.
25 //
26 // * The name of Intel Corporation may not be used to endorse or promote products
27 // derived from this software without specific prior written permission.
28 //
29 // This software is provided by the copyright holders and contributors "as is" and
30 // any express or implied warranties, including, but not limited to, the implied
31 // warranties of merchantability and fitness for a particular purpose are disclaimed.
32 // In no event shall the Intel Corporation or contributors be liable for any direct,
33 // indirect, incidental, special, exemplary, or consequential damages
34 // (including, but not limited to, procurement of substitute goods or services;
35 // loss of use, data, or profits; or business interruption) however caused
36 // and on any theory of liability, whether in contract, strict liability,
37 // or tort (including negligence or otherwise) arising in any way out of
38 // the use of this software, even if advised of the possibility of such damage.
39 //
40 //M*/
41
42 #include "_cv.h"
43
44 typedef struct CvFFillSegment
45 {
46 ushort y;
47 ushort l;
48 ushort r;
49 ushort prevl;
50 ushort prevr;
51 short dir;
52 }
53 CvFFillSegment;
54
55 #define UP 1
56 #define DOWN -1
57
58 #define ICV_PUSH( Y, L, R, PREV_L, PREV_R, DIR )\
59 { \
60 tail->y = (ushort)(Y); \
61 tail->l = (ushort)(L); \
62 tail->r = (ushort)(R); \
63 tail->prevl = (ushort)(PREV_L); \
64 tail->prevr = (ushort)(PREV_R); \
65 tail->dir = (short)(DIR); \
66 if( ++tail >= buffer_end ) \
67 tail = buffer; \
68 }
69
70
71 #define ICV_POP( Y, L, R, PREV_L, PREV_R, DIR ) \
72 { \
73 Y = head->y; \
74 L = head->l; \
75 R = head->r; \
76 PREV_L = head->prevl; \
77 PREV_R = head->prevr; \
78 DIR = head->dir; \
79 if( ++head >= buffer_end ) \
80 head = buffer; \
81 }
82
83
84 #define ICV_EQ_C3( p1, p2 ) \
85 ((p1)[0] == (p2)[0] && (p1)[1] == (p2)[1] && (p1)[2] == (p2)[2])
86
87 #define ICV_SET_C3( p, q ) \
88 ((p)[0] = (q)[0], (p)[1] = (q)[1], (p)[2] = (q)[2])
89
90 /****************************************************************************************\
91 * Simple Floodfill (repainting single-color connected component) *
92 \****************************************************************************************/
93
94 static CvStatus
icvFloodFill_8u_CnIR(uchar * pImage,int step,CvSize roi,CvPoint seed,uchar * _newVal,CvConnectedComp * region,int flags,CvFFillSegment * buffer,int buffer_size,int cn)95 icvFloodFill_8u_CnIR( uchar* pImage, int step, CvSize roi, CvPoint seed,
96 uchar* _newVal, CvConnectedComp* region, int flags,
97 CvFFillSegment* buffer, int buffer_size, int cn )
98 {
99 uchar* img = pImage + step * seed.y;
100 int i, L, R;
101 int area = 0;
102 int val0[] = {0,0,0};
103 uchar newVal[] = {0,0,0};
104 int XMin, XMax, YMin = seed.y, YMax = seed.y;
105 int _8_connectivity = (flags & 255) == 8;
106 CvFFillSegment* buffer_end = buffer + buffer_size, *head = buffer, *tail = buffer;
107
108 L = R = XMin = XMax = seed.x;
109
110 if( cn == 1 )
111 {
112 val0[0] = img[L];
113 newVal[0] = _newVal[0];
114
115 img[L] = newVal[0];
116
117 while( ++R < roi.width && img[R] == val0[0] )
118 img[R] = newVal[0];
119
120 while( --L >= 0 && img[L] == val0[0] )
121 img[L] = newVal[0];
122 }
123 else
124 {
125 assert( cn == 3 );
126 ICV_SET_C3( val0, img + L*3 );
127 ICV_SET_C3( newVal, _newVal );
128
129 ICV_SET_C3( img + L*3, newVal );
130
131 while( --L >= 0 && ICV_EQ_C3( img + L*3, val0 ))
132 ICV_SET_C3( img + L*3, newVal );
133
134 while( ++R < roi.width && ICV_EQ_C3( img + R*3, val0 ))
135 ICV_SET_C3( img + R*3, newVal );
136 }
137
138 XMax = --R;
139 XMin = ++L;
140 ICV_PUSH( seed.y, L, R, R + 1, R, UP );
141
142 while( head != tail )
143 {
144 int k, YC, PL, PR, dir;
145 ICV_POP( YC, L, R, PL, PR, dir );
146
147 int data[][3] =
148 {
149 {-dir, L - _8_connectivity, R + _8_connectivity},
150 {dir, L - _8_connectivity, PL - 1},
151 {dir, PR + 1, R + _8_connectivity}
152 };
153
154 if( region )
155 {
156 area += R - L + 1;
157
158 if( XMax < R ) XMax = R;
159 if( XMin > L ) XMin = L;
160 if( YMax < YC ) YMax = YC;
161 if( YMin > YC ) YMin = YC;
162 }
163
164 for( k = 0/*(unsigned)(YC - dir) >= (unsigned)roi.height*/; k < 3; k++ )
165 {
166 dir = data[k][0];
167 img = pImage + (YC + dir) * step;
168 int left = data[k][1];
169 int right = data[k][2];
170
171 if( (unsigned)(YC + dir) >= (unsigned)roi.height )
172 continue;
173
174 if( cn == 1 )
175 for( i = left; i <= right; i++ )
176 {
177 if( (unsigned)i < (unsigned)roi.width && img[i] == val0[0] )
178 {
179 int j = i;
180 img[i] = newVal[0];
181 while( --j >= 0 && img[j] == val0[0] )
182 img[j] = newVal[0];
183
184 while( ++i < roi.width && img[i] == val0[0] )
185 img[i] = newVal[0];
186
187 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
188 }
189 }
190 else
191 for( i = left; i <= right; i++ )
192 {
193 if( (unsigned)i < (unsigned)roi.width && ICV_EQ_C3( img + i*3, val0 ))
194 {
195 int j = i;
196 ICV_SET_C3( img + i*3, newVal );
197 while( --j >= 0 && ICV_EQ_C3( img + j*3, val0 ))
198 ICV_SET_C3( img + j*3, newVal );
199
200 while( ++i < roi.width && ICV_EQ_C3( img + i*3, val0 ))
201 ICV_SET_C3( img + i*3, newVal );
202
203 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
204 }
205 }
206 }
207 }
208
209 if( region )
210 {
211 region->area = area;
212 region->rect.x = XMin;
213 region->rect.y = YMin;
214 region->rect.width = XMax - XMin + 1;
215 region->rect.height = YMax - YMin + 1;
216 region->value = cvScalar(newVal[0], newVal[1], newVal[2], 0);
217 }
218
219 return CV_NO_ERR;
220 }
221
222
223 /* because all the operations on floats that are done during non-gradient floodfill
224 are just copying and comparison on equality,
225 we can do the whole op on 32-bit integers instead */
226 static CvStatus
icvFloodFill_32f_CnIR(int * pImage,int step,CvSize roi,CvPoint seed,int * _newVal,CvConnectedComp * region,int flags,CvFFillSegment * buffer,int buffer_size,int cn)227 icvFloodFill_32f_CnIR( int* pImage, int step, CvSize roi, CvPoint seed,
228 int* _newVal, CvConnectedComp* region, int flags,
229 CvFFillSegment* buffer, int buffer_size, int cn )
230 {
231 int* img = pImage + (step /= sizeof(pImage[0])) * seed.y;
232 int i, L, R;
233 int area = 0;
234 int val0[] = {0,0,0};
235 int newVal[] = {0,0,0};
236 int XMin, XMax, YMin = seed.y, YMax = seed.y;
237 int _8_connectivity = (flags & 255) == 8;
238 CvFFillSegment* buffer_end = buffer + buffer_size, *head = buffer, *tail = buffer;
239
240 L = R = XMin = XMax = seed.x;
241
242 if( cn == 1 )
243 {
244 val0[0] = img[L];
245 newVal[0] = _newVal[0];
246
247 img[L] = newVal[0];
248
249 while( ++R < roi.width && img[R] == val0[0] )
250 img[R] = newVal[0];
251
252 while( --L >= 0 && img[L] == val0[0] )
253 img[L] = newVal[0];
254 }
255 else
256 {
257 assert( cn == 3 );
258 ICV_SET_C3( val0, img + L*3 );
259 ICV_SET_C3( newVal, _newVal );
260
261 ICV_SET_C3( img + L*3, newVal );
262
263 while( --L >= 0 && ICV_EQ_C3( img + L*3, val0 ))
264 ICV_SET_C3( img + L*3, newVal );
265
266 while( ++R < roi.width && ICV_EQ_C3( img + R*3, val0 ))
267 ICV_SET_C3( img + R*3, newVal );
268 }
269
270 XMax = --R;
271 XMin = ++L;
272 ICV_PUSH( seed.y, L, R, R + 1, R, UP );
273
274 while( head != tail )
275 {
276 int k, YC, PL, PR, dir;
277 ICV_POP( YC, L, R, PL, PR, dir );
278
279 int data[][3] =
280 {
281 {-dir, L - _8_connectivity, R + _8_connectivity},
282 {dir, L - _8_connectivity, PL - 1},
283 {dir, PR + 1, R + _8_connectivity}
284 };
285
286 if( region )
287 {
288 area += R - L + 1;
289
290 if( XMax < R ) XMax = R;
291 if( XMin > L ) XMin = L;
292 if( YMax < YC ) YMax = YC;
293 if( YMin > YC ) YMin = YC;
294 }
295
296 for( k = 0/*(unsigned)(YC - dir) >= (unsigned)roi.height*/; k < 3; k++ )
297 {
298 dir = data[k][0];
299 img = pImage + (YC + dir) * step;
300 int left = data[k][1];
301 int right = data[k][2];
302
303 if( (unsigned)(YC + dir) >= (unsigned)roi.height )
304 continue;
305
306 if( cn == 1 )
307 for( i = left; i <= right; i++ )
308 {
309 if( (unsigned)i < (unsigned)roi.width && img[i] == val0[0] )
310 {
311 int j = i;
312 img[i] = newVal[0];
313 while( --j >= 0 && img[j] == val0[0] )
314 img[j] = newVal[0];
315
316 while( ++i < roi.width && img[i] == val0[0] )
317 img[i] = newVal[0];
318
319 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
320 }
321 }
322 else
323 for( i = left; i <= right; i++ )
324 {
325 if( (unsigned)i < (unsigned)roi.width && ICV_EQ_C3( img + i*3, val0 ))
326 {
327 int j = i;
328 ICV_SET_C3( img + i*3, newVal );
329 while( --j >= 0 && ICV_EQ_C3( img + j*3, val0 ))
330 ICV_SET_C3( img + j*3, newVal );
331
332 while( ++i < roi.width && ICV_EQ_C3( img + i*3, val0 ))
333 ICV_SET_C3( img + i*3, newVal );
334
335 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
336 }
337 }
338 }
339 }
340
341 if( region )
342 {
343 Cv32suf v0, v1, v2;
344 region->area = area;
345 region->rect.x = XMin;
346 region->rect.y = YMin;
347 region->rect.width = XMax - XMin + 1;
348 region->rect.height = YMax - YMin + 1;
349 v0.i = newVal[0]; v1.i = newVal[1]; v2.i = newVal[2];
350 region->value = cvScalar( v0.f, v1.f, v2.f );
351 }
352
353 return CV_NO_ERR;
354 }
355
356 /****************************************************************************************\
357 * Gradient Floodfill *
358 \****************************************************************************************/
359
360 #define DIFF_INT_C1(p1,p2) ((unsigned)((p1)[0] - (p2)[0] + d_lw[0]) <= interval[0])
361
362 #define DIFF_INT_C3(p1,p2) ((unsigned)((p1)[0] - (p2)[0] + d_lw[0])<= interval[0] && \
363 (unsigned)((p1)[1] - (p2)[1] + d_lw[1])<= interval[1] && \
364 (unsigned)((p1)[2] - (p2)[2] + d_lw[2])<= interval[2])
365
366 #define DIFF_FLT_C1(p1,p2) (fabs((p1)[0] - (p2)[0] + d_lw[0]) <= interval[0])
367
368 #define DIFF_FLT_C3(p1,p2) (fabs((p1)[0] - (p2)[0] + d_lw[0]) <= interval[0] && \
369 fabs((p1)[1] - (p2)[1] + d_lw[1]) <= interval[1] && \
370 fabs((p1)[2] - (p2)[2] + d_lw[2]) <= interval[2])
371
372 static CvStatus
icvFloodFill_Grad_8u_CnIR(uchar * pImage,int step,uchar * pMask,int maskStep,CvSize,CvPoint seed,uchar * _newVal,uchar * _d_lw,uchar * _d_up,CvConnectedComp * region,int flags,CvFFillSegment * buffer,int buffer_size,int cn)373 icvFloodFill_Grad_8u_CnIR( uchar* pImage, int step, uchar* pMask, int maskStep,
374 CvSize /*roi*/, CvPoint seed, uchar* _newVal, uchar* _d_lw,
375 uchar* _d_up, CvConnectedComp* region, int flags,
376 CvFFillSegment* buffer, int buffer_size, int cn )
377 {
378 uchar* img = pImage + step*seed.y;
379 uchar* mask = (pMask += maskStep + 1) + maskStep*seed.y;
380 int i, L, R;
381 int area = 0;
382 int sum[] = {0,0,0}, val0[] = {0,0,0};
383 uchar newVal[] = {0,0,0};
384 int d_lw[] = {0,0,0};
385 unsigned interval[] = {0,0,0};
386 int XMin, XMax, YMin = seed.y, YMax = seed.y;
387 int _8_connectivity = (flags & 255) == 8;
388 int fixedRange = flags & CV_FLOODFILL_FIXED_RANGE;
389 int fillImage = (flags & CV_FLOODFILL_MASK_ONLY) == 0;
390 uchar newMaskVal = (uchar)(flags & 0xff00 ? flags >> 8 : 1);
391 CvFFillSegment* buffer_end = buffer + buffer_size, *head = buffer, *tail = buffer;
392
393 L = R = seed.x;
394 if( mask[L] )
395 return CV_OK;
396
397 mask[L] = newMaskVal;
398
399 for( i = 0; i < cn; i++ )
400 {
401 newVal[i] = _newVal[i];
402 d_lw[i] = _d_lw[i];
403 interval[i] = (unsigned)(_d_up[i] + _d_lw[i]);
404 if( fixedRange )
405 val0[i] = img[L*cn+i];
406 }
407
408 if( cn == 1 )
409 {
410 if( fixedRange )
411 {
412 while( !mask[R + 1] && DIFF_INT_C1( img + (R+1), val0 ))
413 mask[++R] = newMaskVal;
414
415 while( !mask[L - 1] && DIFF_INT_C1( img + (L-1), val0 ))
416 mask[--L] = newMaskVal;
417 }
418 else
419 {
420 while( !mask[R + 1] && DIFF_INT_C1( img + (R+1), img + R ))
421 mask[++R] = newMaskVal;
422
423 while( !mask[L - 1] && DIFF_INT_C1( img + (L-1), img + L ))
424 mask[--L] = newMaskVal;
425 }
426 }
427 else
428 {
429 if( fixedRange )
430 {
431 while( !mask[R + 1] && DIFF_INT_C3( img + (R+1)*3, val0 ))
432 mask[++R] = newMaskVal;
433
434 while( !mask[L - 1] && DIFF_INT_C3( img + (L-1)*3, val0 ))
435 mask[--L] = newMaskVal;
436 }
437 else
438 {
439 while( !mask[R + 1] && DIFF_INT_C3( img + (R+1)*3, img + R*3 ))
440 mask[++R] = newMaskVal;
441
442 while( !mask[L - 1] && DIFF_INT_C3( img + (L-1)*3, img + L*3 ))
443 mask[--L] = newMaskVal;
444 }
445 }
446
447 XMax = R;
448 XMin = L;
449 ICV_PUSH( seed.y, L, R, R + 1, R, UP );
450
451 while( head != tail )
452 {
453 int k, YC, PL, PR, dir, curstep;
454 ICV_POP( YC, L, R, PL, PR, dir );
455
456 int data[][3] =
457 {
458 {-dir, L - _8_connectivity, R + _8_connectivity},
459 {dir, L - _8_connectivity, PL - 1},
460 {dir, PR + 1, R + _8_connectivity}
461 };
462
463 unsigned length = (unsigned)(R-L);
464
465 if( region )
466 {
467 area += (int)length + 1;
468
469 if( XMax < R ) XMax = R;
470 if( XMin > L ) XMin = L;
471 if( YMax < YC ) YMax = YC;
472 if( YMin > YC ) YMin = YC;
473 }
474
475 if( cn == 1 )
476 {
477 for( k = 0; k < 3; k++ )
478 {
479 dir = data[k][0];
480 curstep = dir * step;
481 img = pImage + (YC + dir) * step;
482 mask = pMask + (YC + dir) * maskStep;
483 int left = data[k][1];
484 int right = data[k][2];
485
486 if( fixedRange )
487 for( i = left; i <= right; i++ )
488 {
489 if( !mask[i] && DIFF_INT_C1( img + i, val0 ))
490 {
491 int j = i;
492 mask[i] = newMaskVal;
493 while( !mask[--j] && DIFF_INT_C1( img + j, val0 ))
494 mask[j] = newMaskVal;
495
496 while( !mask[++i] && DIFF_INT_C1( img + i, val0 ))
497 mask[i] = newMaskVal;
498
499 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
500 }
501 }
502 else if( !_8_connectivity )
503 for( i = left; i <= right; i++ )
504 {
505 if( !mask[i] && DIFF_INT_C1( img + i, img - curstep + i ))
506 {
507 int j = i;
508 mask[i] = newMaskVal;
509 while( !mask[--j] && DIFF_INT_C1( img + j, img + (j+1) ))
510 mask[j] = newMaskVal;
511
512 while( !mask[++i] &&
513 (DIFF_INT_C1( img + i, img + (i-1) ) ||
514 (DIFF_INT_C1( img + i, img + i - curstep) && i <= R)))
515 mask[i] = newMaskVal;
516
517 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
518 }
519 }
520 else
521 for( i = left; i <= right; i++ )
522 {
523 int idx, val[1];
524
525 if( !mask[i] &&
526 (((val[0] = img[i],
527 (unsigned)(idx = i-L-1) <= length) &&
528 DIFF_INT_C1( val, img - curstep + (i-1))) ||
529 ((unsigned)(++idx) <= length &&
530 DIFF_INT_C1( val, img - curstep + i )) ||
531 ((unsigned)(++idx) <= length &&
532 DIFF_INT_C1( val, img - curstep + (i+1) ))))
533 {
534 int j = i;
535 mask[i] = newMaskVal;
536 while( !mask[--j] && DIFF_INT_C1( img + j, img + (j+1) ))
537 mask[j] = newMaskVal;
538
539 while( !mask[++i] &&
540 ((val[0] = img[i],
541 DIFF_INT_C1( val, img + (i-1) )) ||
542 (((unsigned)(idx = i-L-1) <= length &&
543 DIFF_INT_C1( val, img - curstep + (i-1) ))) ||
544 ((unsigned)(++idx) <= length &&
545 DIFF_INT_C1( val, img - curstep + i )) ||
546 ((unsigned)(++idx) <= length &&
547 DIFF_INT_C1( val, img - curstep + (i+1) ))))
548 mask[i] = newMaskVal;
549
550 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
551 }
552 }
553 }
554
555 img = pImage + YC * step;
556 if( fillImage )
557 for( i = L; i <= R; i++ )
558 img[i] = newVal[0];
559 else if( region )
560 for( i = L; i <= R; i++ )
561 sum[0] += img[i];
562 }
563 else
564 {
565 for( k = 0; k < 3; k++ )
566 {
567 dir = data[k][0];
568 curstep = dir * step;
569 img = pImage + (YC + dir) * step;
570 mask = pMask + (YC + dir) * maskStep;
571 int left = data[k][1];
572 int right = data[k][2];
573
574 if( fixedRange )
575 for( i = left; i <= right; i++ )
576 {
577 if( !mask[i] && DIFF_INT_C3( img + i*3, val0 ))
578 {
579 int j = i;
580 mask[i] = newMaskVal;
581 while( !mask[--j] && DIFF_INT_C3( img + j*3, val0 ))
582 mask[j] = newMaskVal;
583
584 while( !mask[++i] && DIFF_INT_C3( img + i*3, val0 ))
585 mask[i] = newMaskVal;
586
587 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
588 }
589 }
590 else if( !_8_connectivity )
591 for( i = left; i <= right; i++ )
592 {
593 if( !mask[i] && DIFF_INT_C3( img + i*3, img - curstep + i*3 ))
594 {
595 int j = i;
596 mask[i] = newMaskVal;
597 while( !mask[--j] && DIFF_INT_C3( img + j*3, img + (j+1)*3 ))
598 mask[j] = newMaskVal;
599
600 while( !mask[++i] &&
601 (DIFF_INT_C3( img + i*3, img + (i-1)*3 ) ||
602 (DIFF_INT_C3( img + i*3, img + i*3 - curstep) && i <= R)))
603 mask[i] = newMaskVal;
604
605 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
606 }
607 }
608 else
609 for( i = left; i <= right; i++ )
610 {
611 int idx, val[3];
612
613 if( !mask[i] &&
614 (((ICV_SET_C3( val, img+i*3 ),
615 (unsigned)(idx = i-L-1) <= length) &&
616 DIFF_INT_C3( val, img - curstep + (i-1)*3 )) ||
617 ((unsigned)(++idx) <= length &&
618 DIFF_INT_C3( val, img - curstep + i*3 )) ||
619 ((unsigned)(++idx) <= length &&
620 DIFF_INT_C3( val, img - curstep + (i+1)*3 ))))
621 {
622 int j = i;
623 mask[i] = newMaskVal;
624 while( !mask[--j] && DIFF_INT_C3( img + j*3, img + (j+1)*3 ))
625 mask[j] = newMaskVal;
626
627 while( !mask[++i] &&
628 ((ICV_SET_C3( val, img + i*3 ),
629 DIFF_INT_C3( val, img + (i-1)*3 )) ||
630 (((unsigned)(idx = i-L-1) <= length &&
631 DIFF_INT_C3( val, img - curstep + (i-1)*3 ))) ||
632 ((unsigned)(++idx) <= length &&
633 DIFF_INT_C3( val, img - curstep + i*3 )) ||
634 ((unsigned)(++idx) <= length &&
635 DIFF_INT_C3( val, img - curstep + (i+1)*3 ))))
636 mask[i] = newMaskVal;
637
638 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
639 }
640 }
641 }
642
643 img = pImage + YC * step;
644 if( fillImage )
645 for( i = L; i <= R; i++ )
646 ICV_SET_C3( img + i*3, newVal );
647 else if( region )
648 for( i = L; i <= R; i++ )
649 {
650 sum[0] += img[i*3];
651 sum[1] += img[i*3+1];
652 sum[2] += img[i*3+2];
653 }
654 }
655 }
656
657 if( region )
658 {
659 region->area = area;
660 region->rect.x = XMin;
661 region->rect.y = YMin;
662 region->rect.width = XMax - XMin + 1;
663 region->rect.height = YMax - YMin + 1;
664
665 if( fillImage )
666 region->value = cvScalar(newVal[0], newVal[1], newVal[2]);
667 else
668 {
669 double iarea = area ? 1./area : 0;
670 region->value = cvScalar(sum[0]*iarea, sum[1]*iarea, sum[2]*iarea);
671 }
672 }
673
674 return CV_NO_ERR;
675 }
676
677
678 static CvStatus
icvFloodFill_Grad_32f_CnIR(float * pImage,int step,uchar * pMask,int maskStep,CvSize,CvPoint seed,float * _newVal,float * _d_lw,float * _d_up,CvConnectedComp * region,int flags,CvFFillSegment * buffer,int buffer_size,int cn)679 icvFloodFill_Grad_32f_CnIR( float* pImage, int step, uchar* pMask, int maskStep,
680 CvSize /*roi*/, CvPoint seed, float* _newVal, float* _d_lw,
681 float* _d_up, CvConnectedComp* region, int flags,
682 CvFFillSegment* buffer, int buffer_size, int cn )
683 {
684 float* img = pImage + (step /= sizeof(float))*seed.y;
685 uchar* mask = (pMask += maskStep + 1) + maskStep*seed.y;
686 int i, L, R;
687 int area = 0;
688 double sum[] = {0,0,0}, val0[] = {0,0,0};
689 float newVal[] = {0,0,0};
690 float d_lw[] = {0,0,0};
691 float interval[] = {0,0,0};
692 int XMin, XMax, YMin = seed.y, YMax = seed.y;
693 int _8_connectivity = (flags & 255) == 8;
694 int fixedRange = flags & CV_FLOODFILL_FIXED_RANGE;
695 int fillImage = (flags & CV_FLOODFILL_MASK_ONLY) == 0;
696 uchar newMaskVal = (uchar)(flags & 0xff00 ? flags >> 8 : 1);
697 CvFFillSegment* buffer_end = buffer + buffer_size, *head = buffer, *tail = buffer;
698
699 L = R = seed.x;
700 if( mask[L] )
701 return CV_OK;
702
703 mask[L] = newMaskVal;
704
705 for( i = 0; i < cn; i++ )
706 {
707 newVal[i] = _newVal[i];
708 d_lw[i] = 0.5f*(_d_lw[i] - _d_up[i]);
709 interval[i] = 0.5f*(_d_lw[i] + _d_up[i]);
710 if( fixedRange )
711 val0[i] = img[L*cn+i];
712 }
713
714 if( cn == 1 )
715 {
716 if( fixedRange )
717 {
718 while( !mask[R + 1] && DIFF_FLT_C1( img + (R+1), val0 ))
719 mask[++R] = newMaskVal;
720
721 while( !mask[L - 1] && DIFF_FLT_C1( img + (L-1), val0 ))
722 mask[--L] = newMaskVal;
723 }
724 else
725 {
726 while( !mask[R + 1] && DIFF_FLT_C1( img + (R+1), img + R ))
727 mask[++R] = newMaskVal;
728
729 while( !mask[L - 1] && DIFF_FLT_C1( img + (L-1), img + L ))
730 mask[--L] = newMaskVal;
731 }
732 }
733 else
734 {
735 if( fixedRange )
736 {
737 while( !mask[R + 1] && DIFF_FLT_C3( img + (R+1)*3, val0 ))
738 mask[++R] = newMaskVal;
739
740 while( !mask[L - 1] && DIFF_FLT_C3( img + (L-1)*3, val0 ))
741 mask[--L] = newMaskVal;
742 }
743 else
744 {
745 while( !mask[R + 1] && DIFF_FLT_C3( img + (R+1)*3, img + R*3 ))
746 mask[++R] = newMaskVal;
747
748 while( !mask[L - 1] && DIFF_FLT_C3( img + (L-1)*3, img + L*3 ))
749 mask[--L] = newMaskVal;
750 }
751 }
752
753 XMax = R;
754 XMin = L;
755 ICV_PUSH( seed.y, L, R, R + 1, R, UP );
756
757 while( head != tail )
758 {
759 int k, YC, PL, PR, dir, curstep;
760 ICV_POP( YC, L, R, PL, PR, dir );
761
762 int data[][3] =
763 {
764 {-dir, L - _8_connectivity, R + _8_connectivity},
765 {dir, L - _8_connectivity, PL - 1},
766 {dir, PR + 1, R + _8_connectivity}
767 };
768
769 unsigned length = (unsigned)(R-L);
770
771 if( region )
772 {
773 area += (int)length + 1;
774
775 if( XMax < R ) XMax = R;
776 if( XMin > L ) XMin = L;
777 if( YMax < YC ) YMax = YC;
778 if( YMin > YC ) YMin = YC;
779 }
780
781 if( cn == 1 )
782 {
783 for( k = 0; k < 3; k++ )
784 {
785 dir = data[k][0];
786 curstep = dir * step;
787 img = pImage + (YC + dir) * step;
788 mask = pMask + (YC + dir) * maskStep;
789 int left = data[k][1];
790 int right = data[k][2];
791
792 if( fixedRange )
793 for( i = left; i <= right; i++ )
794 {
795 if( !mask[i] && DIFF_FLT_C1( img + i, val0 ))
796 {
797 int j = i;
798 mask[i] = newMaskVal;
799 while( !mask[--j] && DIFF_FLT_C1( img + j, val0 ))
800 mask[j] = newMaskVal;
801
802 while( !mask[++i] && DIFF_FLT_C1( img + i, val0 ))
803 mask[i] = newMaskVal;
804
805 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
806 }
807 }
808 else if( !_8_connectivity )
809 for( i = left; i <= right; i++ )
810 {
811 if( !mask[i] && DIFF_FLT_C1( img + i, img - curstep + i ))
812 {
813 int j = i;
814 mask[i] = newMaskVal;
815 while( !mask[--j] && DIFF_FLT_C1( img + j, img + (j+1) ))
816 mask[j] = newMaskVal;
817
818 while( !mask[++i] &&
819 (DIFF_FLT_C1( img + i, img + (i-1) ) ||
820 (DIFF_FLT_C1( img + i, img + i - curstep) && i <= R)))
821 mask[i] = newMaskVal;
822
823 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
824 }
825 }
826 else
827 for( i = left; i <= right; i++ )
828 {
829 int idx;
830 float val[1];
831
832 if( !mask[i] &&
833 (((val[0] = img[i],
834 (unsigned)(idx = i-L-1) <= length) &&
835 DIFF_FLT_C1( val, img - curstep + (i-1) )) ||
836 ((unsigned)(++idx) <= length &&
837 DIFF_FLT_C1( val, img - curstep + i )) ||
838 ((unsigned)(++idx) <= length &&
839 DIFF_FLT_C1( val, img - curstep + (i+1) ))))
840 {
841 int j = i;
842 mask[i] = newMaskVal;
843 while( !mask[--j] && DIFF_FLT_C1( img + j, img + (j+1) ))
844 mask[j] = newMaskVal;
845
846 while( !mask[++i] &&
847 ((val[0] = img[i],
848 DIFF_FLT_C1( val, img + (i-1) )) ||
849 (((unsigned)(idx = i-L-1) <= length &&
850 DIFF_FLT_C1( val, img - curstep + (i-1) ))) ||
851 ((unsigned)(++idx) <= length &&
852 DIFF_FLT_C1( val, img - curstep + i )) ||
853 ((unsigned)(++idx) <= length &&
854 DIFF_FLT_C1( val, img - curstep + (i+1) ))))
855 mask[i] = newMaskVal;
856
857 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
858 }
859 }
860 }
861
862 img = pImage + YC * step;
863 if( fillImage )
864 for( i = L; i <= R; i++ )
865 img[i] = newVal[0];
866 else if( region )
867 for( i = L; i <= R; i++ )
868 sum[0] += img[i];
869 }
870 else
871 {
872 for( k = 0; k < 3; k++ )
873 {
874 dir = data[k][0];
875 curstep = dir * step;
876 img = pImage + (YC + dir) * step;
877 mask = pMask + (YC + dir) * maskStep;
878 int left = data[k][1];
879 int right = data[k][2];
880
881 if( fixedRange )
882 for( i = left; i <= right; i++ )
883 {
884 if( !mask[i] && DIFF_FLT_C3( img + i*3, val0 ))
885 {
886 int j = i;
887 mask[i] = newMaskVal;
888 while( !mask[--j] && DIFF_FLT_C3( img + j*3, val0 ))
889 mask[j] = newMaskVal;
890
891 while( !mask[++i] && DIFF_FLT_C3( img + i*3, val0 ))
892 mask[i] = newMaskVal;
893
894 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
895 }
896 }
897 else if( !_8_connectivity )
898 for( i = left; i <= right; i++ )
899 {
900 if( !mask[i] && DIFF_FLT_C3( img + i*3, img - curstep + i*3 ))
901 {
902 int j = i;
903 mask[i] = newMaskVal;
904 while( !mask[--j] && DIFF_FLT_C3( img + j*3, img + (j+1)*3 ))
905 mask[j] = newMaskVal;
906
907 while( !mask[++i] &&
908 (DIFF_FLT_C3( img + i*3, img + (i-1)*3 ) ||
909 (DIFF_FLT_C3( img + i*3, img + i*3 - curstep) && i <= R)))
910 mask[i] = newMaskVal;
911
912 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
913 }
914 }
915 else
916 for( i = left; i <= right; i++ )
917 {
918 int idx;
919 float val[3];
920
921 if( !mask[i] &&
922 (((ICV_SET_C3( val, img+i*3 ),
923 (unsigned)(idx = i-L-1) <= length) &&
924 DIFF_FLT_C3( val, img - curstep + (i-1)*3 )) ||
925 ((unsigned)(++idx) <= length &&
926 DIFF_FLT_C3( val, img - curstep + i*3 )) ||
927 ((unsigned)(++idx) <= length &&
928 DIFF_FLT_C3( val, img - curstep + (i+1)*3 ))))
929 {
930 int j = i;
931 mask[i] = newMaskVal;
932 while( !mask[--j] && DIFF_FLT_C3( img + j*3, img + (j+1)*3 ))
933 mask[j] = newMaskVal;
934
935 while( !mask[++i] &&
936 ((ICV_SET_C3( val, img + i*3 ),
937 DIFF_FLT_C3( val, img + (i-1)*3 )) ||
938 (((unsigned)(idx = i-L-1) <= length &&
939 DIFF_FLT_C3( val, img - curstep + (i-1)*3 ))) ||
940 ((unsigned)(++idx) <= length &&
941 DIFF_FLT_C3( val, img - curstep + i*3 )) ||
942 ((unsigned)(++idx) <= length &&
943 DIFF_FLT_C3( val, img - curstep + (i+1)*3 ))))
944 mask[i] = newMaskVal;
945
946 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
947 }
948 }
949 }
950
951 img = pImage + YC * step;
952 if( fillImage )
953 for( i = L; i <= R; i++ )
954 ICV_SET_C3( img + i*3, newVal );
955 else if( region )
956 for( i = L; i <= R; i++ )
957 {
958 sum[0] += img[i*3];
959 sum[1] += img[i*3+1];
960 sum[2] += img[i*3+2];
961 }
962 }
963 }
964
965 if( region )
966 {
967 region->area = area;
968 region->rect.x = XMin;
969 region->rect.y = YMin;
970 region->rect.width = XMax - XMin + 1;
971 region->rect.height = YMax - YMin + 1;
972
973 if( fillImage )
974 region->value = cvScalar(newVal[0], newVal[1], newVal[2]);
975 else
976 {
977 double iarea = area ? 1./area : 0;
978 region->value = cvScalar(sum[0]*iarea, sum[1]*iarea, sum[2]*iarea);
979 }
980 }
981
982 return CV_NO_ERR;
983 }
984
985
986 /****************************************************************************************\
987 * External Functions *
988 \****************************************************************************************/
989
990 typedef CvStatus (CV_CDECL* CvFloodFillFunc)(
991 void* img, int step, CvSize size, CvPoint seed, void* newval,
992 CvConnectedComp* comp, int flags, void* buffer, int buffer_size, int cn );
993
994 typedef CvStatus (CV_CDECL* CvFloodFillGradFunc)(
995 void* img, int step, uchar* mask, int maskStep, CvSize size,
996 CvPoint seed, void* newval, void* d_lw, void* d_up, void* ccomp,
997 int flags, void* buffer, int buffer_size, int cn );
998
icvInitFloodFill(void ** ffill_tab,void ** ffillgrad_tab)999 static void icvInitFloodFill( void** ffill_tab,
1000 void** ffillgrad_tab )
1001 {
1002 ffill_tab[0] = (void*)icvFloodFill_8u_CnIR;
1003 ffill_tab[1] = (void*)icvFloodFill_32f_CnIR;
1004
1005 ffillgrad_tab[0] = (void*)icvFloodFill_Grad_8u_CnIR;
1006 ffillgrad_tab[1] = (void*)icvFloodFill_Grad_32f_CnIR;
1007 }
1008
1009
1010 CV_IMPL void
cvFloodFill(CvArr * arr,CvPoint seed_point,CvScalar newVal,CvScalar lo_diff,CvScalar up_diff,CvConnectedComp * comp,int flags,CvArr * maskarr)1011 cvFloodFill( CvArr* arr, CvPoint seed_point,
1012 CvScalar newVal, CvScalar lo_diff, CvScalar up_diff,
1013 CvConnectedComp* comp, int flags, CvArr* maskarr )
1014 {
1015 static void* ffill_tab[4];
1016 static void* ffillgrad_tab[4];
1017 static int inittab = 0;
1018
1019 CvMat* tempMask = 0;
1020 CvFFillSegment* buffer = 0;
1021 CV_FUNCNAME( "cvFloodFill" );
1022
1023 if( comp )
1024 memset( comp, 0, sizeof(*comp) );
1025
1026 __BEGIN__;
1027
1028 int i, type, depth, cn, is_simple, idx;
1029 int buffer_size, connectivity = flags & 255;
1030 double nv_buf[4] = {0,0,0,0};
1031 union { uchar b[4]; float f[4]; } ld_buf, ud_buf;
1032 CvMat stub, *img = (CvMat*)arr;
1033 CvMat maskstub, *mask = (CvMat*)maskarr;
1034 CvSize size;
1035
1036 if( !inittab )
1037 {
1038 icvInitFloodFill( ffill_tab, ffillgrad_tab );
1039 inittab = 1;
1040 }
1041
1042 CV_CALL( img = cvGetMat( img, &stub ));
1043 type = CV_MAT_TYPE( img->type );
1044 depth = CV_MAT_DEPTH(type);
1045 cn = CV_MAT_CN(type);
1046
1047 idx = type == CV_8UC1 || type == CV_8UC3 ? 0 :
1048 type == CV_32FC1 || type == CV_32FC3 ? 1 : -1;
1049
1050 if( idx < 0 )
1051 CV_ERROR( CV_StsUnsupportedFormat, "" );
1052
1053 if( connectivity == 0 )
1054 connectivity = 4;
1055 else if( connectivity != 4 && connectivity != 8 )
1056 CV_ERROR( CV_StsBadFlag, "Connectivity must be 4, 0(=4) or 8" );
1057
1058 is_simple = mask == 0 && (flags & CV_FLOODFILL_MASK_ONLY) == 0;
1059
1060 for( i = 0; i < cn; i++ )
1061 {
1062 if( lo_diff.val[i] < 0 || up_diff.val[i] < 0 )
1063 CV_ERROR( CV_StsBadArg, "lo_diff and up_diff must be non-negative" );
1064 is_simple &= fabs(lo_diff.val[i]) < DBL_EPSILON && fabs(up_diff.val[i]) < DBL_EPSILON;
1065 }
1066
1067 size = cvGetMatSize( img );
1068
1069 if( (unsigned)seed_point.x >= (unsigned)size.width ||
1070 (unsigned)seed_point.y >= (unsigned)size.height )
1071 CV_ERROR( CV_StsOutOfRange, "Seed point is outside of image" );
1072
1073 cvScalarToRawData( &newVal, &nv_buf, type, 0 );
1074 buffer_size = MAX( size.width, size.height )*2;
1075 CV_CALL( buffer = (CvFFillSegment*)cvAlloc( buffer_size*sizeof(buffer[0])));
1076
1077 if( is_simple )
1078 {
1079 int elem_size = CV_ELEM_SIZE(type);
1080 const uchar* seed_ptr = img->data.ptr + img->step*seed_point.y + elem_size*seed_point.x;
1081 CvFloodFillFunc func = (CvFloodFillFunc)ffill_tab[idx];
1082 if( !func )
1083 CV_ERROR( CV_StsUnsupportedFormat, "" );
1084 // check if the new value is different from the current value at the seed point.
1085 // if they are exactly the same, use the generic version with mask to avoid infinite loops.
1086 for( i = 0; i < elem_size; i++ )
1087 if( seed_ptr[i] != ((uchar*)nv_buf)[i] )
1088 break;
1089 if( i < elem_size )
1090 {
1091 IPPI_CALL( func( img->data.ptr, img->step, size,
1092 seed_point, &nv_buf, comp, flags,
1093 buffer, buffer_size, cn ));
1094 EXIT;
1095 }
1096 }
1097
1098 {
1099 CvFloodFillGradFunc func = (CvFloodFillGradFunc)ffillgrad_tab[idx];
1100 if( !func )
1101 CV_ERROR( CV_StsUnsupportedFormat, "" );
1102
1103 if( !mask )
1104 {
1105 /* created mask will be 8-byte aligned */
1106 tempMask = cvCreateMat( size.height + 2, (size.width + 9) & -8, CV_8UC1 );
1107 mask = tempMask;
1108 }
1109 else
1110 {
1111 CV_CALL( mask = cvGetMat( mask, &maskstub ));
1112 if( !CV_IS_MASK_ARR( mask ))
1113 CV_ERROR( CV_StsBadMask, "" );
1114
1115 if( mask->width != size.width + 2 || mask->height != size.height + 2 )
1116 CV_ERROR( CV_StsUnmatchedSizes, "mask must be 2 pixel wider "
1117 "and 2 pixel taller than filled image" );
1118 }
1119
1120 {
1121 int width = tempMask ? mask->step : size.width + 2;
1122 uchar* mask_row = mask->data.ptr + mask->step;
1123 memset( mask_row - mask->step, 1, width );
1124
1125 for( i = 1; i <= size.height; i++, mask_row += mask->step )
1126 {
1127 if( tempMask )
1128 memset( mask_row, 0, width );
1129 mask_row[0] = mask_row[size.width+1] = (uchar)1;
1130 }
1131 memset( mask_row, 1, width );
1132 }
1133
1134 if( depth == CV_8U )
1135 for( i = 0; i < cn; i++ )
1136 {
1137 int t = cvFloor(lo_diff.val[i]);
1138 ld_buf.b[i] = CV_CAST_8U(t);
1139 t = cvFloor(up_diff.val[i]);
1140 ud_buf.b[i] = CV_CAST_8U(t);
1141 }
1142 else
1143 for( i = 0; i < cn; i++ )
1144 {
1145 ld_buf.f[i] = (float)lo_diff.val[i];
1146 ud_buf.f[i] = (float)up_diff.val[i];
1147 }
1148
1149 IPPI_CALL( func( img->data.ptr, img->step, mask->data.ptr, mask->step,
1150 size, seed_point, &nv_buf, ld_buf.f, ud_buf.f,
1151 comp, flags, buffer, buffer_size, cn ));
1152 }
1153
1154 __END__;
1155
1156 cvFree( &buffer );
1157 cvReleaseMat( &tempMask );
1158 }
1159
1160 /* End of file. */
1161