git.maemo.org Git - opencv/blob - cvaux/src/cvsegment.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 "_cvaux.h"
  43
  44 typedef struct Seg
  45 {
  46     ushort y;
  47     ushort l;
  48     ushort r;
  49     ushort Prevl;
  50     ushort Prevr;
  51     short  fl;
  52 }
  53 Seg;
  54
  55 #define UP 1
  56 #define DOWN -1
  57
  58 #define PUSH(Y,IL,IR,IPL,IPR,FL) {  stack[StIn].y=(ushort)(Y); \
  59                                     stack[StIn].l=(ushort)(IL); \
  60                                     stack[StIn].r=(ushort)(IR); \
  61                                     stack[StIn].Prevl=(ushort)(IPL); \
  62                                     stack[StIn].Prevr=(ushort)(IPR); \
  63                                     stack[StIn].fl=(short)(FL); \
  64                                     StIn++; }
  65
  66 #define POP(Y,IL,IR,IPL,IPR,FL)  {  StIn--; \
  67                                     Y=stack[StIn].y; \
  68                                     IL=stack[StIn].l; \
  69                                     IR=stack[StIn].r;\
  70                                     IPL=stack[StIn].Prevl; \
  71                                     IPR=stack[StIn].Prevr; \
  72                                     FL=stack[StIn].fl; }
  73
  74
  75 #define DIFF(p1,p2) ((unsigned)((p1)[0] - (p2)[0] + d_lw)<=Interval && \
  76                      (unsigned)((p1)[1] - (p2)[1] + d_lw)<=Interval && \
  77                      (unsigned)((p1)[2] - (p2)[2] + d_lw)<=Interval)
  78
  79 /*#define DIFF(p1,p2) (CV_IABS((p1)[0] - (p2)[0]) + \
  80                      CV_IABS((p1)[1] - (p2)[1]) + \
  81                      CV_IABS((p1)[2] - (p2)[2]) <=Interval )*/
  82
  83 static CvStatus
  84 icvSegmFloodFill_Stage1( uchar* pImage, int step,
  85                          uchar* pMask, int maskStep,
  86                          CvSize /*roi*/, CvPoint seed,
  87                          int* newVal, int d_lw, int d_up,
  88                          CvConnectedComp * region,
  89                          void *pStack )
  90 {
  91     uchar* img = pImage + step * seed.y;
  92     uchar* mask = pMask + maskStep * (seed.y + 1);
  93     unsigned Interval = (unsigned) (d_up + d_lw);
  94     Seg *stack = (Seg*)pStack;
  95     int StIn = 0;
  96     int i, L, R;
  97     int area = 0;
  98     int sum[] = { 0, 0, 0 };
  99     int XMin, XMax, YMin = seed.y, YMax = seed.y;
 100     int val0[3];
 101
 102     L = R = seed.x;
 103     img = pImage + seed.y*step;
 104     mask = pMask + seed.y*maskStep;
 105     mask[L] = 1;
 106
 107     val0[0] = img[seed.x*3];
 108     val0[1] = img[seed.x*3 + 1];
 109     val0[2] = img[seed.x*3 + 2];
 110
 111     while( DIFF( img + (R+1)*3, /*img + R*3*/val0 ) && !mask[R + 1] )
 112         mask[++R] = 2;
 113
 114     while( DIFF( img + (L-1)*3, /*img + L*3*/val0 ) && !mask[L - 1] )
 115         mask[--L] = 2;
 116
 117     XMax = R;
 118     XMin = L;
 119     PUSH( seed.y, L, R, R + 1, R, UP );
 120
 121     while( StIn )
 122     {
 123         int k, YC, PL, PR, flag/*, curstep*/;
 124
 125         POP( YC, L, R, PL, PR, flag );
 126
 127         int data[][3] = { {-flag, L, R}, {flag, L, PL-1}, {flag,PR+1,R}};
 128
 129         if( XMax < R )
 130             XMax = R;
 131
 132         if( XMin > L )
 133             XMin = L;
 134
 135         if( YMax < YC )
 136             YMax = YC;
 137
 138         if( YMin > YC )
 139             YMin = YC;
 140
 141         for( k = 0; k < 3; k++ )
 142         {
 143             flag = data[k][0];
 144             /*curstep = flag * step;*/
 145             img = pImage + (YC + flag) * step;
 146             mask = pMask + (YC + flag) * maskStep;
 147             int left = data[k][1];
 148             int right = data[k][2];
 149
 150             for( i = left; i <= right; i++ )
 151             {
 152                 if( !mask[i] && DIFF( img + i*3, /*img - curstep + i*3*/val0 ))
 153                 {
 154                     int j = i;
 155                     mask[i] = 2;
 156                     while( !mask[j - 1] && DIFF( img + (j - 1)*3, /*img + j*3*/val0 ))
 157                         mask[--j] = 2;
 158
 159                     while( !mask[i + 1] &&
 160                            (DIFF( img + (i+1)*3, /*img + i*3*/val0 ) ||
 161                            (DIFF( img + (i+1)*3, /*img + (i+1)*3 - curstep*/val0) && i < R)))
 162                         mask[++i] = 2;
 163
 164                     PUSH( YC + flag, j, i, L, R, -flag );
 165                     i++;
 166                 }
 167             }
 168         }
 169
 170         img = pImage + YC * step;
 171
 172         for( i = L; i <= R; i++ )
 173         {
 174             sum[0] += img[i*3];
 175             sum[1] += img[i*3 + 1];
 176             sum[2] += img[i*3 + 2];
 177         }
 178
 179         area += R - L + 1;
 180     }
 181
 182     region->area = area;
 183     region->rect.x = XMin;
 184     region->rect.y = YMin;
 185     region->rect.width = XMax - XMin + 1;
 186     region->rect.height = YMax - YMin + 1;
 187     region->value = cvScalarAll(0);
 188
 189     {
 190         double inv_area = area ? 1./area : 0;
 191         newVal[0] = cvRound( sum[0] * inv_area );
 192         newVal[1] = cvRound( sum[1] * inv_area );
 193         newVal[2] = cvRound( sum[2] * inv_area );
 194     }
 195
 196     return CV_NO_ERR;
 197 }
 198
 199
 200 #undef PUSH
 201 #undef POP
 202 #undef DIFF
 203
 204
 205 static CvStatus
 206 icvSegmFloodFill_Stage2( uchar* pImage, int step,
 207                          uchar* pMask, int maskStep,
 208                          CvSize /*roi*/, int* newVal,
 209                          CvRect rect )
 210 {
 211     uchar* img = pImage + step * rect.y + rect.x * 3;
 212     uchar* mask = pMask + maskStep * rect.y + rect.x;
 213     uchar uv[] = { (uchar)newVal[0], (uchar)newVal[1], (uchar)newVal[2] };
 214     int x, y;
 215
 216     for( y = 0; y < rect.height; y++, img += step, mask += maskStep )
 217         for( x = 0; x < rect.width; x++ )
 218             if( mask[x] == 2 )
 219             {
 220                 mask[x] = 1;
 221                 img[x*3] = uv[0];
 222                 img[x*3+1] = uv[1];
 223                 img[x*3+2] = uv[2];
 224             }
 225
 226     return CV_OK;
 227 }
 228
 229 #if 0
 230 static void color_derv( const CvArr* srcArr, CvArr* dstArr, int thresh )
 231 {
 232     static int tab[] = { 0, 2, 2, 1 };
 233
 234     uchar *src = 0, *dst = 0;
 235     int dst_step, src_step;
 236     int x, y;
 237     CvSize size;
 238
 239     cvGetRawData( srcArr, (uchar**)&src, &src_step, &size );
 240     cvGetRawData( dstArr, (uchar**)&dst, &dst_step, 0 );
 241
 242     memset( dst, 0, size.width*sizeof(dst[0]));
 243     memset( (uchar*)dst + dst_step*(size.height-1), 0, size.width*sizeof(dst[0]));
 244     src += 3;
 245
 246     #define  CV_IABS(a)     (((a) ^ ((a) < 0 ? -1 : 0)) - ((a) < 0 ? -1 : 0))
 247
 248     for( y = 1; y < size.height - 1; y++ )
 249     {
 250         src += src_step;
 251         dst += dst_step;
 252         uchar* src0 = src;
 253
 254         dst[0] = dst[size.width - 1] = 0;
 255
 256         for( x = 1; x < size.width - 1; x++, src += 3 )
 257         {
 258             /*int d[3];
 259             int ad[3];
 260             int f0, f1;
 261             int val;*/
 262             int m[3];
 263             double val;
 264             //double xx, yy;
 265             int dh[3];
 266             int dv[3];
 267             dh[0] = src[0] - src[-3];
 268             dv[0] = src[0] - src[-src_step];
 269             dh[1] = src[1] - src[-2];
 270             dv[1] = src[1] - src[1-src_step];
 271             dh[2] = src[2] - src[-1];
 272             dv[2] = src[2] - src[2-src_step];
 273
 274             m[0] = dh[0]*dh[0] + dh[1]*dh[1] + dh[2]*dh[2];
 275             m[2] = dh[0]*dv[0] + dh[1]*dv[1] + dh[2]*dv[2];
 276             m[1] = dv[0]*dv[0] + dv[1]*dv[1] + dh[2]*dh[2];
 277
 278             val = (m[0] + m[2]) +
 279                 sqrt(((double)((double)m[0] - m[2]))*(m[0] - m[2]) + (4.*m[1])*m[1]);
 280
 281             /*
 282
 283             xx = m[1];
 284             yy = v - m[0];
 285             v /= sqrt(xx*xx + yy*yy) + 1e-7;
 286             xx *= v;
 287             yy *= v;
 288
 289             dx[x] = (short)cvRound(xx);
 290             dy[x] = (short)cvRound(yy);
 291
 292             //dx[x] = (short)cvRound(v);
 293
 294             //dx[x] = dy[x] = (short)v;
 295             d[0] = src[0] - src[-3];
 296             ad[0] = CV_IABS(d[0]);
 297
 298             d[1] = src[1] - src[-2];
 299             ad[1] = CV_IABS(d[1]);
 300
 301             d[2] = src[2] - src[-1];
 302             ad[2] = CV_IABS(d[2]);
 303
 304             f0 = ad[1] > ad[0];
 305             f1 = ad[2] > ad[f0];
 306
 307             val = d[tab[f0*2 + f1]];
 308
 309             d[0] = src[0] - src[-src_step];
 310             ad[0] = CV_IABS(d[0]);
 311
 312             d[1] = src[1] - src[1-src_step];
 313             ad[1] = CV_IABS(d[1]);
 314
 315             d[2] = src[2] - src[2-src_step];
 316             ad[2] = CV_IABS(d[2]);
 317
 318             f0 = ad[1] > ad[0];
 319             f1 = ad[2] > ad[f0];
 320
 321             dst[x] = (uchar)(val + d[tab[f0*2 + f1]] > thresh ? 255 : 0);*/
 322             dst[x] = (uchar)(val > thresh);
 323         }
 324
 325         src = src0;
 326     }
 327
 328 }
 329 #endif
 330
 331 const CvPoint icvCodeDeltas[8] =
 332     { {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1} };
 333
 334 static CvSeq*
 335 icvGetComponent( uchar* img, int step, CvRect rect,
 336                  CvMemStorage* storage )
 337 {
 338     const char nbd = 4;
 339     int  deltas[16];
 340     int  x, y;
 341     CvSeq* exterior = 0;
 342     char* ptr;
 343
 344     /* initialize local state */
 345     CV_INIT_3X3_DELTAS( deltas, step, 1 );
 346     memcpy( deltas + 8, deltas, 8 * sizeof( deltas[0] ));
 347
 348     ptr = (char*)(img + step*rect.y);
 349     rect.width += rect.x;
 350     rect.height += rect.y;
 351
 352     for( y = rect.y; y < rect.height; y++, ptr += step )
 353     {
 354         int prev = ptr[rect.x - 1] & -2;
 355
 356         for( x = rect.x; x < rect.width; x++ )
 357         {
 358             int p = ptr[x] & -2;
 359
 360             //assert( exterior || ((p | prev) & -4) == 0 );
 361
 362             if( p != prev )
 363             {
 364                 CvSeq *seq = 0;
 365                 int is_hole = 0;
 366                 CvSeqWriter  writer;
 367                 char  *i0, *i1, *i3, *i4 = 0;
 368                 int  prev_s = -1, s, s_end;
 369                 CvPoint pt = { x, y };
 370
 371                 if( !(prev == 0 && p == 2) )    /* if not external contour */
 372                 {
 373                     /* check hole */
 374                     if( p != 0 || prev < 1 )
 375                     {
 376                         prev = p;
 377                         continue;
 378                     }
 379
 380                     is_hole = 1;
 381                     if( !exterior )
 382                     {
 383                         assert(0);
 384                         return 0;
 385                     }
 386                 }
 387
 388                 cvStartWriteSeq( CV_SEQ_CONTOUR | (is_hole ? CV_SEQ_FLAG_HOLE : 0),
 389                                  sizeof(CvContour), sizeof(CvPoint), storage, &writer );
 390                 s_end = s = is_hole ? 0 : 4;
 391                 i0 = ptr + x - is_hole;
 392
 393                 do
 394                 {
 395                     s = (s - 1) & 7;
 396                     i1 = i0 + deltas[s];
 397                     if( (*i1 & -2) != 0 )
 398                         break;
 399                 }
 400                 while( s != s_end );
 401
 402                 if( s == s_end )            /* single pixel domain */
 403                 {
 404                     *i0 = (char) (nbd | -128);
 405                     CV_WRITE_SEQ_ELEM( pt, writer );
 406                 }
 407                 else
 408                 {
 409                     i3 = i0;
 410                     prev_s = s ^ 4;
 411
 412                     /* follow border */
 413                     for( ;; )
 414                     {
 415                         s_end = s;
 416
 417                         for( ;; )
 418                         {
 419                             i4 = i3 + deltas[++s];
 420                             if( (*i4 & -2) != 0 )
 421                                 break;
 422                         }
 423                         s &= 7;
 424
 425                         /* check "right" bound */
 426                         if( (unsigned) (s - 1) < (unsigned) s_end )
 427                         {
 428                             *i3 = (char) (nbd | -128);
 429                         }
 430                         else if( *i3 > 0 )
 431                         {
 432                             *i3 = nbd;
 433                         }
 434
 435                         if( s != prev_s )
 436                         {
 437                             CV_WRITE_SEQ_ELEM( pt, writer );
 438                             prev_s = s;
 439                         }
 440
 441                         pt.x += icvCodeDeltas[s].x;
 442                         pt.y += icvCodeDeltas[s].y;
 443
 444                         if( i4 == i0 && i3 == i1 )
 445                             break;
 446
 447                         i3 = i4;
 448                         s = (s + 4) & 7;
 449                     }                       /* end of border following loop */
 450                 }
 451
 452                 seq = cvEndWriteSeq( &writer );
 453                 cvContourBoundingRect( seq, 1 );
 454
 455                 if( !is_hole )
 456                     exterior = seq;
 457                 else
 458                 {
 459                     seq->v_prev = exterior;
 460                     seq->h_next = exterior->v_next;
 461                     if( seq->h_next )
 462                         seq->h_next->h_prev = seq;
 463                     exterior->v_next = seq;
 464                 }
 465
 466                 prev = ptr[x] & -2;
 467             }
 468         }
 469     }
 470
 471     return exterior;
 472 }
 473
 474
 475
 476 CV_IMPL CvSeq*
 477 cvSegmentImage( const CvArr* srcarr, CvArr* dstarr,
 478                 double canny_threshold,
 479                 double ffill_threshold,
 480                 CvMemStorage* storage )
 481 {
 482     CvSeq* root = 0;
 483     CvMat* gray = 0;
 484     CvMat* canny = 0;
 485     //CvMat* temp = 0;
 486     void* stack = 0;
 487
 488     CV_FUNCNAME( "cvSegmentImage" );
 489
 490     __BEGIN__;
 491
 492     CvMat srcstub, *src;
 493     CvMat dststub, *dst;
 494     CvMat* mask;
 495     CvSize size;
 496     CvPoint pt;
 497     int ffill_lw_up = cvRound( fabs(ffill_threshold) );
 498     CvSeq* prev_seq = 0;
 499
 500     CV_CALL( src = cvGetMat( srcarr, &srcstub ));
 501     CV_CALL( dst = cvGetMat( dstarr, &dststub ));
 502
 503     size = cvGetSize( src );
 504
 505     CV_CALL( gray = cvCreateMat( size.height, size.width, CV_8UC1 ));
 506     CV_CALL( canny = cvCreateMat( size.height, size.width, CV_8UC1 ));
 507     //CV_CALL( temp = cvCreateMat( size.height/2, size.width/2, CV_8UC3 ));
 508
 509     CV_CALL( stack = cvAlloc( size.width * size.height * sizeof(Seg)));
 510
 511     cvCvtColor( src, gray, CV_BGR2GRAY );
 512     cvCanny( gray, canny, 0/*canny_threshold*0.4*/, canny_threshold, 3 );
 513     cvThreshold( canny, canny, 1, 1, CV_THRESH_BINARY );
 514     //cvZero( canny );
 515     //color_derv( src, canny, canny_threshold );
 516
 517     //cvPyrDown( src, temp );
 518     //cvPyrUp( temp, dst );
 519
 520     //src = dst;
 521     mask = canny; // a new name for new role
 522
 523     // make a non-zero border.
 524     cvRectangle( mask, cvPoint(0,0), cvPoint(size.width-1,size.height-1), cvScalarAll(1), 1 );
 525
 526     for( pt.y = 0; pt.y < size.height; pt.y++ )
 527     {
 528         for( pt.x = 0; pt.x < size.width; pt.x++ )
 529         {
 530             if( mask->data.ptr[mask->step*pt.y + pt.x] == 0 )
 531             {
 532                 CvConnectedComp region;
 533                 int avgVal[3] = { 0, 0, 0 };
 534
 535                 icvSegmFloodFill_Stage1( src->data.ptr, src->step,
 536                                          mask->data.ptr, mask->step,
 537                                          size, pt, avgVal,
 538                                          ffill_lw_up, ffill_lw_up,
 539                                          &region, stack );
 540
 541                 /*avgVal[0] = (avgVal[0] + 15) & -32;
 542                 if( avgVal[0] > 255 )
 543                     avgVal[0] = 255;
 544                 avgVal[1] = (avgVal[1] + 15) & -32;
 545                 if( avgVal[1] > 255 )
 546                     avgVal[1] = 255;
 547                 avgVal[2] = (avgVal[2] + 15) & -32;
 548                 if( avgVal[2] > 255 )
 549                     avgVal[2] = 255;*/
 550
 551                 if( storage )
 552                 {
 553                     CvSeq* tmpseq = icvGetComponent( mask->data.ptr, mask->step,
 554                                                      region.rect, storage );
 555                     if( tmpseq != 0 )
 556                     {
 557                         ((CvContour*)tmpseq)->color = avgVal[0] + (avgVal[1] << 8) + (avgVal[2] << 16);
 558                         tmpseq->h_prev = prev_seq;
 559                         if( prev_seq )
 560                             prev_seq->h_next = tmpseq;
 561                         else
 562                             root = tmpseq;
 563                         prev_seq = tmpseq;
 564                     }
 565                 }
 566
 567                 icvSegmFloodFill_Stage2( dst->data.ptr, dst->step,
 568                                          mask->data.ptr, mask->step,
 569                                          size, avgVal,
 570                                          region.rect );
 571             }
 572         }
 573     }
 574
 575     __END__;
 576
 577     //cvReleaseMat( &temp );
 578     cvReleaseMat( &gray );
 579     cvReleaseMat( &canny );
 580     cvFree( &stack );
 581
 582     return root;
 583 }
 584
 585 /* End of file. */