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// License Agreement 11// For Open Source Computer Vision Library 12// 13// Copyright (C) 2000, Intel Corporation, all rights reserved. 14// Copyright (C) 2013, OpenCV Foundation, all rights reserved. 15// Third party copyrights are property of their respective owners. 16// 17// Redistribution and use in source and binary forms, with or without modification, 18// are permitted provided that the following conditions are met: 19// 20// * Redistribution's of source code must retain the above copyright notice, 21// this list of conditions and the following disclaimer. 22// 23// * Redistribution's in binary form must reproduce the above copyright notice, 24// this list of conditions and the following disclaimer in the documentation 25// and/or other materials provided with the distribution. 26// 27// * The name of the copyright holders may not be used to endorse or promote products 28// derived from this software without specific prior written permission. 29// 30// This software is provided by the copyright holders and contributors "as is" and 31// any express or implied warranties, including, but not limited to, the implied 32// warranties of merchantability and fitness for a particular purpose are disclaimed. 33// In no event shall the Intel Corporation or contributors be liable for any direct, 34// indirect, incidental, special, exemplary, or consequential damages 35// (including, but not limited to, procurement of substitute goods or services; 36// loss of use, data, or profits; or business interruption) however caused 37// and on any theory of liability, whether in contract, strict liability, 38// or tort (including negligence or otherwise) arising in any way out of 39// the use of this software, even if advised of the possibility of such damage. 40// 41//M*/ 42 43#include "precomp.hpp" 44 45#if defined(__GNUC__) && (__GNUC__ == 4) && (__GNUC_MINOR__ == 8) 46# pragma GCC diagnostic ignored "-Warray-bounds" 47#endif 48 49namespace cv 50{ 51 52struct FFillSegment 53{ 54 ushort y; 55 ushort l; 56 ushort r; 57 ushort prevl; 58 ushort prevr; 59 short dir; 60}; 61 62enum 63{ 64 UP = 1, 65 DOWN = -1 66}; 67 68#define ICV_PUSH( Y, L, R, PREV_L, PREV_R, DIR ) \ 69{ \ 70 tail->y = (ushort)(Y); \ 71 tail->l = (ushort)(L); \ 72 tail->r = (ushort)(R); \ 73 tail->prevl = (ushort)(PREV_L); \ 74 tail->prevr = (ushort)(PREV_R); \ 75 tail->dir = (short)(DIR); \ 76 if( ++tail == buffer_end ) \ 77 { \ 78 buffer->resize(buffer->size() * 3/2); \ 79 tail = &buffer->front() + (tail - head); \ 80 head = &buffer->front(); \ 81 buffer_end = head + buffer->size(); \ 82 } \ 83} 84 85#define ICV_POP( Y, L, R, PREV_L, PREV_R, DIR ) \ 86{ \ 87 --tail; \ 88 Y = tail->y; \ 89 L = tail->l; \ 90 R = tail->r; \ 91 PREV_L = tail->prevl; \ 92 PREV_R = tail->prevr; \ 93 DIR = tail->dir; \ 94} 95 96struct ConnectedComp 97{ 98 ConnectedComp(); 99 Rect rect; 100 Point pt; 101 int threshold; 102 int label; 103 int area; 104 int harea; 105 int carea; 106 int perimeter; 107 int nholes; 108 int ninflections; 109 double mx; 110 double my; 111 Scalar avg; 112 Scalar sdv; 113}; 114 115ConnectedComp::ConnectedComp() 116{ 117 rect = Rect(0, 0, 0, 0); 118 pt = Point(-1, -1); 119 threshold = -1; 120 label = -1; 121 area = harea = carea = perimeter = nholes = ninflections = 0; 122 mx = my = 0; 123 avg = sdv = Scalar::all(0); 124} 125 126// Simple Floodfill (repainting single-color connected component) 127 128template<typename _Tp> 129static void 130floodFill_CnIR( Mat& image, Point seed, 131 _Tp newVal, ConnectedComp* region, int flags, 132 std::vector<FFillSegment>* buffer ) 133{ 134 _Tp* img = image.ptr<_Tp>(seed.y); 135 Size roi = image.size(); 136 int i, L, R; 137 int area = 0; 138 int XMin, XMax, YMin = seed.y, YMax = seed.y; 139 int _8_connectivity = (flags & 255) == 8; 140 FFillSegment* buffer_end = &buffer->front() + buffer->size(), *head = &buffer->front(), *tail = &buffer->front(); 141 142 L = R = XMin = XMax = seed.x; 143 144 _Tp val0 = img[L]; 145 img[L] = newVal; 146 147 while( ++R < roi.width && img[R] == val0 ) 148 img[R] = newVal; 149 150 while( --L >= 0 && img[L] == val0 ) 151 img[L] = newVal; 152 153 XMax = --R; 154 XMin = ++L; 155 156 ICV_PUSH( seed.y, L, R, R + 1, R, UP ); 157 158 while( head != tail ) 159 { 160 int k, YC, PL, PR, dir; 161 ICV_POP( YC, L, R, PL, PR, dir ); 162 163 int data[][3] = 164 { 165 {-dir, L - _8_connectivity, R + _8_connectivity}, 166 {dir, L - _8_connectivity, PL - 1}, 167 {dir, PR + 1, R + _8_connectivity} 168 }; 169 170 if( region ) 171 { 172 area += R - L + 1; 173 174 if( XMax < R ) XMax = R; 175 if( XMin > L ) XMin = L; 176 if( YMax < YC ) YMax = YC; 177 if( YMin > YC ) YMin = YC; 178 } 179 180 for( k = 0; k < 3; k++ ) 181 { 182 dir = data[k][0]; 183 184 if( (unsigned)(YC + dir) >= (unsigned)roi.height ) 185 continue; 186 187 img = image.ptr<_Tp>(YC + dir); 188 int left = data[k][1]; 189 int right = data[k][2]; 190 191 for( i = left; i <= right; i++ ) 192 { 193 if( (unsigned)i < (unsigned)roi.width && img[i] == val0 ) 194 { 195 int j = i; 196 img[i] = newVal; 197 while( --j >= 0 && img[j] == val0 ) 198 img[j] = newVal; 199 200 while( ++i < roi.width && img[i] == val0 ) 201 img[i] = 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->pt = seed; 212 region->area = area; 213 region->rect.x = XMin; 214 region->rect.y = YMin; 215 region->rect.width = XMax - XMin + 1; 216 region->rect.height = YMax - YMin + 1; 217 } 218} 219 220/****************************************************************************************\ 221* Gradient Floodfill * 222\****************************************************************************************/ 223 224struct Diff8uC1 225{ 226 Diff8uC1(uchar _lo, uchar _up) : lo(_lo), interval(_lo + _up) {} 227 bool operator()(const uchar* a, const uchar* b) const 228 { return (unsigned)(a[0] - b[0] + lo) <= interval; } 229 unsigned lo, interval; 230}; 231 232struct Diff8uC3 233{ 234 Diff8uC3(Vec3b _lo, Vec3b _up) 235 { 236 for( int k = 0; k < 3; k++ ) 237 lo[k] = _lo[k], interval[k] = _lo[k] + _up[k]; 238 } 239 bool operator()(const Vec3b* a, const Vec3b* b) const 240 { 241 return (unsigned)(a[0][0] - b[0][0] + lo[0]) <= interval[0] && 242 (unsigned)(a[0][1] - b[0][1] + lo[1]) <= interval[1] && 243 (unsigned)(a[0][2] - b[0][2] + lo[2]) <= interval[2]; 244 } 245 unsigned lo[3], interval[3]; 246}; 247 248template<typename _Tp> 249struct DiffC1 250{ 251 DiffC1(_Tp _lo, _Tp _up) : lo(-_lo), up(_up) {} 252 bool operator()(const _Tp* a, const _Tp* b) const 253 { 254 _Tp d = a[0] - b[0]; 255 return lo <= d && d <= up; 256 } 257 _Tp lo, up; 258}; 259 260template<typename _Tp> 261struct DiffC3 262{ 263 DiffC3(_Tp _lo, _Tp _up) : lo(-_lo), up(_up) {} 264 bool operator()(const _Tp* a, const _Tp* b) const 265 { 266 _Tp d = *a - *b; 267 return lo[0] <= d[0] && d[0] <= up[0] && 268 lo[1] <= d[1] && d[1] <= up[1] && 269 lo[2] <= d[2] && d[2] <= up[2]; 270 } 271 _Tp lo, up; 272}; 273 274typedef DiffC1<int> Diff32sC1; 275typedef DiffC3<Vec3i> Diff32sC3; 276typedef DiffC1<float> Diff32fC1; 277typedef DiffC3<Vec3f> Diff32fC3; 278 279template<typename _Tp, typename _MTp, typename _WTp, class Diff> 280static void 281floodFillGrad_CnIR( Mat& image, Mat& msk, 282 Point seed, _Tp newVal, _MTp newMaskVal, 283 Diff diff, ConnectedComp* region, int flags, 284 std::vector<FFillSegment>* buffer ) 285{ 286 int step = (int)image.step, maskStep = (int)msk.step; 287 uchar* pImage = image.ptr(); 288 _Tp* img = (_Tp*)(pImage + step*seed.y); 289 uchar* pMask = msk.ptr() + maskStep + sizeof(_MTp); 290 _MTp* mask = (_MTp*)(pMask + maskStep*seed.y); 291 int i, L, R; 292 int area = 0; 293 int XMin, XMax, YMin = seed.y, YMax = seed.y; 294 int _8_connectivity = (flags & 255) == 8; 295 int fixedRange = flags & FLOODFILL_FIXED_RANGE; 296 int fillImage = (flags & FLOODFILL_MASK_ONLY) == 0; 297 FFillSegment* buffer_end = &buffer->front() + buffer->size(), *head = &buffer->front(), *tail = &buffer->front(); 298 299 L = R = seed.x; 300 if( mask[L] ) 301 return; 302 303 mask[L] = newMaskVal; 304 _Tp val0 = img[L]; 305 306 if( fixedRange ) 307 { 308 while( !mask[R + 1] && diff( img + (R+1), &val0 )) 309 mask[++R] = newMaskVal; 310 311 while( !mask[L - 1] && diff( img + (L-1), &val0 )) 312 mask[--L] = newMaskVal; 313 } 314 else 315 { 316 while( !mask[R + 1] && diff( img + (R+1), img + R )) 317 mask[++R] = newMaskVal; 318 319 while( !mask[L - 1] && diff( img + (L-1), img + L )) 320 mask[--L] = newMaskVal; 321 } 322 323 XMax = R; 324 XMin = L; 325 326 ICV_PUSH( seed.y, L, R, R + 1, R, UP ); 327 328 while( head != tail ) 329 { 330 int k, YC, PL, PR, dir; 331 ICV_POP( YC, L, R, PL, PR, dir ); 332 333 int data[][3] = 334 { 335 {-dir, L - _8_connectivity, R + _8_connectivity}, 336 {dir, L - _8_connectivity, PL - 1}, 337 {dir, PR + 1, R + _8_connectivity} 338 }; 339 340 unsigned length = (unsigned)(R-L); 341 342 if( region ) 343 { 344 area += (int)length + 1; 345 346 if( XMax < R ) XMax = R; 347 if( XMin > L ) XMin = L; 348 if( YMax < YC ) YMax = YC; 349 if( YMin > YC ) YMin = YC; 350 } 351 352 for( k = 0; k < 3; k++ ) 353 { 354 dir = data[k][0]; 355 img = (_Tp*)(pImage + (YC + dir) * step); 356 _Tp* img1 = (_Tp*)(pImage + YC * step); 357 mask = (_MTp*)(pMask + (YC + dir) * maskStep); 358 int left = data[k][1]; 359 int right = data[k][2]; 360 361 if( fixedRange ) 362 for( i = left; i <= right; i++ ) 363 { 364 if( !mask[i] && diff( img + i, &val0 )) 365 { 366 int j = i; 367 mask[i] = newMaskVal; 368 while( !mask[--j] && diff( img + j, &val0 )) 369 mask[j] = newMaskVal; 370 371 while( !mask[++i] && diff( img + i, &val0 )) 372 mask[i] = newMaskVal; 373 374 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir ); 375 } 376 } 377 else if( !_8_connectivity ) 378 for( i = left; i <= right; i++ ) 379 { 380 if( !mask[i] && diff( img + i, img1 + i )) 381 { 382 int j = i; 383 mask[i] = newMaskVal; 384 while( !mask[--j] && diff( img + j, img + (j+1) )) 385 mask[j] = newMaskVal; 386 387 while( !mask[++i] && 388 (diff( img + i, img + (i-1) ) || 389 (diff( img + i, img1 + i) && i <= R))) 390 mask[i] = newMaskVal; 391 392 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir ); 393 } 394 } 395 else 396 for( i = left; i <= right; i++ ) 397 { 398 int idx; 399 _Tp val; 400 401 if( !mask[i] && 402 (((val = img[i], 403 (unsigned)(idx = i-L-1) <= length) && 404 diff( &val, img1 + (i-1))) || 405 ((unsigned)(++idx) <= length && 406 diff( &val, img1 + i )) || 407 ((unsigned)(++idx) <= length && 408 diff( &val, img1 + (i+1) )))) 409 { 410 int j = i; 411 mask[i] = newMaskVal; 412 while( !mask[--j] && diff( img + j, img + (j+1) )) 413 mask[j] = newMaskVal; 414 415 while( !mask[++i] && 416 ((val = img[i], 417 diff( &val, img + (i-1) )) || 418 (((unsigned)(idx = i-L-1) <= length && 419 diff( &val, img1 + (i-1) ))) || 420 ((unsigned)(++idx) <= length && 421 diff( &val, img1 + i )) || 422 ((unsigned)(++idx) <= length && 423 diff( &val, img1 + (i+1) )))) 424 mask[i] = newMaskVal; 425 426 ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir ); 427 } 428 } 429 } 430 431 img = (_Tp*)(pImage + YC * step); 432 if( fillImage ) 433 for( i = L; i <= R; i++ ) 434 img[i] = newVal; 435 /*else if( region ) 436 for( i = L; i <= R; i++ ) 437 sum += img[i];*/ 438 } 439 440 if( region ) 441 { 442 region->pt = seed; 443 region->label = saturate_cast<int>(newMaskVal); 444 region->area = area; 445 region->rect.x = XMin; 446 region->rect.y = YMin; 447 region->rect.width = XMax - XMin + 1; 448 region->rect.height = YMax - YMin + 1; 449 } 450} 451 452} 453 454/****************************************************************************************\ 455* External Functions * 456\****************************************************************************************/ 457 458int cv::floodFill( InputOutputArray _image, InputOutputArray _mask, 459 Point seedPoint, Scalar newVal, Rect* rect, 460 Scalar loDiff, Scalar upDiff, int flags ) 461{ 462 ConnectedComp comp; 463 std::vector<FFillSegment> buffer; 464 465 if( rect ) 466 *rect = Rect(); 467 468 int i, connectivity = flags & 255; 469 union { 470 uchar b[4]; 471 int i[4]; 472 float f[4]; 473 double _[4]; 474 } nv_buf; 475 nv_buf._[0] = nv_buf._[1] = nv_buf._[2] = nv_buf._[3] = 0; 476 477 struct { Vec3b b; Vec3i i; Vec3f f; } ld_buf, ud_buf; 478 Mat img = _image.getMat(), mask; 479 if( !_mask.empty() ) 480 mask = _mask.getMat(); 481 Size size = img.size(); 482 483 int type = img.type(); 484 int depth = img.depth(); 485 int cn = img.channels(); 486 487 if ( (cn != 1) && (cn != 3) ) 488 { 489 CV_Error( CV_StsBadArg, "Number of channels in input image must be 1 or 3" ); 490 } 491 492 if( connectivity == 0 ) 493 connectivity = 4; 494 else if( connectivity != 4 && connectivity != 8 ) 495 CV_Error( CV_StsBadFlag, "Connectivity must be 4, 0(=4) or 8" ); 496 497 bool is_simple = mask.empty() && (flags & FLOODFILL_MASK_ONLY) == 0; 498 499 for( i = 0; i < cn; i++ ) 500 { 501 if( loDiff[i] < 0 || upDiff[i] < 0 ) 502 CV_Error( CV_StsBadArg, "lo_diff and up_diff must be non-negative" ); 503 is_simple = is_simple && fabs(loDiff[i]) < DBL_EPSILON && fabs(upDiff[i]) < DBL_EPSILON; 504 } 505 506 if( (unsigned)seedPoint.x >= (unsigned)size.width || 507 (unsigned)seedPoint.y >= (unsigned)size.height ) 508 CV_Error( CV_StsOutOfRange, "Seed point is outside of image" ); 509 510 scalarToRawData( newVal, &nv_buf, type, 0); 511 size_t buffer_size = MAX( size.width, size.height ) * 2; 512 buffer.resize( buffer_size ); 513 514 if( is_simple ) 515 { 516 size_t elem_size = img.elemSize(); 517 const uchar* seed_ptr = img.ptr(seedPoint.y) + elem_size*seedPoint.x; 518 519 size_t k = 0; 520 for(; k < elem_size; k++) 521 if (seed_ptr[k] != nv_buf.b[k]) 522 break; 523 524 if( k != elem_size ) 525 { 526 if( type == CV_8UC1 ) 527 floodFill_CnIR(img, seedPoint, nv_buf.b[0], &comp, flags, &buffer); 528 else if( type == CV_8UC3 ) 529 floodFill_CnIR(img, seedPoint, Vec3b(nv_buf.b), &comp, flags, &buffer); 530 else if( type == CV_32SC1 ) 531 floodFill_CnIR(img, seedPoint, nv_buf.i[0], &comp, flags, &buffer); 532 else if( type == CV_32FC1 ) 533 floodFill_CnIR(img, seedPoint, nv_buf.f[0], &comp, flags, &buffer); 534 else if( type == CV_32SC3 ) 535 floodFill_CnIR(img, seedPoint, Vec3i(nv_buf.i), &comp, flags, &buffer); 536 else if( type == CV_32FC3 ) 537 floodFill_CnIR(img, seedPoint, Vec3f(nv_buf.f), &comp, flags, &buffer); 538 else 539 CV_Error( CV_StsUnsupportedFormat, "" ); 540 if( rect ) 541 *rect = comp.rect; 542 return comp.area; 543 } 544 } 545 546 if( mask.empty() ) 547 { 548 Mat tempMask( size.height + 2, size.width + 2, CV_8UC1 ); 549 tempMask.setTo(Scalar::all(0)); 550 mask = tempMask; 551 } 552 else 553 { 554 CV_Assert( mask.rows == size.height+2 && mask.cols == size.width+2 ); 555 CV_Assert( mask.type() == CV_8U ); 556 } 557 558 memset( mask.ptr(), 1, mask.cols ); 559 memset( mask.ptr(mask.rows-1), 1, mask.cols ); 560 561 for( i = 1; i <= size.height; i++ ) 562 { 563 mask.at<uchar>(i, 0) = mask.at<uchar>(i, mask.cols-1) = (uchar)1; 564 } 565 566 if( depth == CV_8U ) 567 for( i = 0; i < cn; i++ ) 568 { 569 ld_buf.b[i] = saturate_cast<uchar>(cvFloor(loDiff[i])); 570 ud_buf.b[i] = saturate_cast<uchar>(cvFloor(upDiff[i])); 571 } 572 else if( depth == CV_32S ) 573 for( i = 0; i < cn; i++ ) 574 { 575 ld_buf.i[i] = cvFloor(loDiff[i]); 576 ud_buf.i[i] = cvFloor(upDiff[i]); 577 } 578 else if( depth == CV_32F ) 579 for( i = 0; i < cn; i++ ) 580 { 581 ld_buf.f[i] = (float)loDiff[i]; 582 ud_buf.f[i] = (float)upDiff[i]; 583 } 584 else 585 CV_Error( CV_StsUnsupportedFormat, "" ); 586 587 uchar newMaskVal = (uchar)((flags & ~0xff) == 0 ? 1 : ((flags >> 8) & 255)); 588 589 if( type == CV_8UC1 ) 590 floodFillGrad_CnIR<uchar, uchar, int, Diff8uC1>( 591 img, mask, seedPoint, nv_buf.b[0], newMaskVal, 592 Diff8uC1(ld_buf.b[0], ud_buf.b[0]), 593 &comp, flags, &buffer); 594 else if( type == CV_8UC3 ) 595 floodFillGrad_CnIR<Vec3b, uchar, Vec3i, Diff8uC3>( 596 img, mask, seedPoint, Vec3b(nv_buf.b), newMaskVal, 597 Diff8uC3(ld_buf.b, ud_buf.b), 598 &comp, flags, &buffer); 599 else if( type == CV_32SC1 ) 600 floodFillGrad_CnIR<int, uchar, int, Diff32sC1>( 601 img, mask, seedPoint, nv_buf.i[0], newMaskVal, 602 Diff32sC1(ld_buf.i[0], ud_buf.i[0]), 603 &comp, flags, &buffer); 604 else if( type == CV_32SC3 ) 605 floodFillGrad_CnIR<Vec3i, uchar, Vec3i, Diff32sC3>( 606 img, mask, seedPoint, Vec3i(nv_buf.i), newMaskVal, 607 Diff32sC3(ld_buf.i, ud_buf.i), 608 &comp, flags, &buffer); 609 else if( type == CV_32FC1 ) 610 floodFillGrad_CnIR<float, uchar, float, Diff32fC1>( 611 img, mask, seedPoint, nv_buf.f[0], newMaskVal, 612 Diff32fC1(ld_buf.f[0], ud_buf.f[0]), 613 &comp, flags, &buffer); 614 else if( type == CV_32FC3 ) 615 floodFillGrad_CnIR<Vec3f, uchar, Vec3f, Diff32fC3>( 616 img, mask, seedPoint, Vec3f(nv_buf.f), newMaskVal, 617 Diff32fC3(ld_buf.f, ud_buf.f), 618 &comp, flags, &buffer); 619 else 620 CV_Error(CV_StsUnsupportedFormat, ""); 621 622 if( rect ) 623 *rect = comp.rect; 624 return comp.area; 625} 626 627 628int cv::floodFill( InputOutputArray _image, Point seedPoint, 629 Scalar newVal, Rect* rect, 630 Scalar loDiff, Scalar upDiff, int flags ) 631{ 632 return floodFill(_image, Mat(), seedPoint, newVal, rect, loDiff, upDiff, flags); 633} 634 635 636CV_IMPL void 637cvFloodFill( CvArr* arr, CvPoint seed_point, 638 CvScalar newVal, CvScalar lo_diff, CvScalar up_diff, 639 CvConnectedComp* comp, int flags, CvArr* maskarr ) 640{ 641 if( comp ) 642 memset( comp, 0, sizeof(*comp) ); 643 644 cv::Mat img = cv::cvarrToMat(arr), mask = cv::cvarrToMat(maskarr); 645 int area = cv::floodFill(img, mask, seed_point, newVal, 646 comp ? (cv::Rect*)&comp->rect : 0, 647 lo_diff, up_diff, flags ); 648 if( comp ) 649 { 650 comp->area = area; 651 comp->value = newVal; 652 } 653} 654 655/* End of file. */ 656