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 44typedef struct CvFFillSegment 45{ 46 ushort y; 47 ushort l; 48 ushort r; 49 ushort prevl; 50 ushort prevr; 51 short dir; 52} 53CvFFillSegment; 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 94static CvStatus 95icvFloodFill_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 */ 226static CvStatus 227icvFloodFill_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 372static CvStatus 373icvFloodFill_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 678static CvStatus 679icvFloodFill_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 990typedef 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 994typedef 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 999static 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 1010CV_IMPL void 1011cvFloodFill( 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