git.maemo.org Git - opencv/blob - cv/src/cvfloodfill.cpp

   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
  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
 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
 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
 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
 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
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         CvFloodFillFunc func = (CvFloodFillFunc)ffill_tab[idx];
1080         if( !func )
1081             CV_ERROR( CV_StsUnsupportedFormat, "" );
1082
1083         IPPI_CALL( func( img->data.ptr, img->step, size,
1084                          seed_point, &nv_buf, comp, flags,
1085                          buffer, buffer_size, cn ));
1086     }
1087     else
1088     {
1089         CvFloodFillGradFunc func = (CvFloodFillGradFunc)ffillgrad_tab[idx];
1090         if( !func )
1091             CV_ERROR( CV_StsUnsupportedFormat, "" );
1092
1093         if( !mask )
1094         {
1095             /* created mask will be 8-byte aligned */
1096             tempMask = cvCreateMat( size.height + 2, (size.width + 9) & -8, CV_8UC1 );
1097             mask = tempMask;
1098         }
1099         else
1100         {
1101             CV_CALL( mask = cvGetMat( mask, &maskstub ));
1102             if( !CV_IS_MASK_ARR( mask ))
1103                 CV_ERROR( CV_StsBadMask, "" );
1104
1105             if( mask->width != size.width + 2 || mask->height != size.height + 2 )
1106                 CV_ERROR( CV_StsUnmatchedSizes, "mask must be 2 pixel wider "
1107                                        "and 2 pixel taller than filled image" );
1108         }
1109
1110         {
1111             int width = tempMask ? mask->step : size.width + 2;
1112             uchar* mask_row = mask->data.ptr + mask->step;
1113             memset( mask_row - mask->step, 1, width );
1114
1115             for( i = 1; i <= size.height; i++, mask_row += mask->step )
1116             {
1117                 if( tempMask )
1118                     memset( mask_row, 0, width );
1119                 mask_row[0] = mask_row[size.width+1] = (uchar)1;
1120             }
1121             memset( mask_row, 1, width );
1122         }
1123
1124         if( depth == CV_8U )
1125             for( i = 0; i < cn; i++ )
1126             {
1127                 int t = cvFloor(lo_diff.val[i]);
1128                 ld_buf.b[i] = CV_CAST_8U(t);
1129                 t = cvFloor(up_diff.val[i]);
1130                 ud_buf.b[i] = CV_CAST_8U(t);
1131             }
1132         else
1133             for( i = 0; i < cn; i++ )
1134             {
1135                 ld_buf.f[i] = (float)lo_diff.val[i];
1136                 ud_buf.f[i] = (float)up_diff.val[i];
1137             }
1138
1139         IPPI_CALL( func( img->data.ptr, img->step, mask->data.ptr, mask->step,
1140                          size, seed_point, &nv_buf, ld_buf.f, ud_buf.f,
1141                          comp, flags, buffer, buffer_size, cn ));
1142     }
1143
1144     __END__;
1145
1146     cvFree( &buffer );
1147     cvReleaseMat( &tempMask );
1148 }
1149
1150 /* End of file. */