git.maemo.org Git - opencv/blob - cv/src/cvcontours.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 #include "_cv.h"
  42
  43 /* initializes 8-element array for fast access to 3x3 neighborhood of a pixel */
  44 #define  CV_INIT_3X3_DELTAS( deltas, step, nch )            \
  45     ((deltas)[0] =  (nch),  (deltas)[1] = -(step) + (nch),  \
  46      (deltas)[2] = -(step), (deltas)[3] = -(step) - (nch),  \
  47      (deltas)[4] = -(nch),  (deltas)[5] =  (step) - (nch),  \
  48      (deltas)[6] =  (step), (deltas)[7] =  (step) + (nch))
  49
  50 static const CvPoint icvCodeDeltas[8] =
  51     { {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1} };
  52
  53 CV_IMPL void
  54 cvStartReadChainPoints( CvChain * chain, CvChainPtReader * reader )
  55 {
  56     int i;
  57
  58     CV_FUNCNAME( "cvStartReadChainPoints" );
  59
  60     __BEGIN__;
  61
  62     if( !chain || !reader )
  63         CV_ERROR( CV_StsNullPtr, "" );
  64
  65     if( chain->elem_size != 1 || chain->header_size < (int)sizeof(CvChain))
  66         CV_ERROR_FROM_STATUS( CV_BADSIZE_ERR );
  67
  68     cvStartReadSeq( (CvSeq *) chain, (CvSeqReader *) reader, 0 );
  69     CV_CHECK();
  70
  71     reader->pt = chain->origin;
  72
  73     for( i = 0; i < 8; i++ )
  74     {
  75         reader->deltas[i][0] = (char) icvCodeDeltas[i].x;
  76         reader->deltas[i][1] = (char) icvCodeDeltas[i].y;
  77     }
  78
  79     __END__;
  80 }
  81
  82
  83 /* retrieves next point of the chain curve and updates reader */
  84 CV_IMPL CvPoint
  85 cvReadChainPoint( CvChainPtReader * reader )
  86 {
  87     char *ptr;
  88     int code;
  89     CvPoint pt = { 0, 0 };
  90
  91     CV_FUNCNAME( "cvReadChainPoint" );
  92
  93     __BEGIN__;
  94
  95     if( !reader )
  96         CV_ERROR( CV_StsNullPtr, "" );
  97
  98     pt = reader->pt;
  99
 100     ptr = reader->ptr;
 101     if( ptr )
 102     {
 103         code = *ptr++;
 104
 105         if( ptr >= reader->block_max )
 106         {
 107             cvChangeSeqBlock( (CvSeqReader *) reader, 1 );
 108             ptr = reader->ptr;
 109         }
 110
 111         reader->ptr = ptr;
 112         reader->code = (char)code;
 113         assert( (code & ~7) == 0 );
 114         reader->pt.x = pt.x + icvCodeDeltas[code].x;
 115         reader->pt.y = pt.y + icvCodeDeltas[code].y;
 116     }
 117
 118     __END__;
 119
 120     return pt;
 121 }
 122
 123
 124 /****************************************************************************************\
 125 *                         Raster->Chain Tree (Suzuki algorithms)                         *
 126 \****************************************************************************************/
 127
 128 typedef struct _CvContourInfo
 129 {
 130     int flags;
 131     struct _CvContourInfo *next;        /* next contour with the same mark value */
 132     struct _CvContourInfo *parent;      /* information about parent contour */
 133     CvSeq *contour;             /* corresponding contour (may be 0, if rejected) */
 134     CvRect rect;                /* bounding rectangle */
 135     CvPoint origin;             /* origin point (where the contour was traced from) */
 136     int is_hole;                /* hole flag */
 137 }
 138 _CvContourInfo;
 139
 140
 141 /*
 142   Structure that is used for sequental retrieving contours from the image.
 143   It supports both hierarchical and plane variants of Suzuki algorithm.
 144 */
 145 typedef struct _CvContourScanner
 146 {
 147     CvMemStorage *storage1;     /* contains fetched contours */
 148     CvMemStorage *storage2;     /* contains approximated contours
 149                                    (!=storage1 if approx_method2 != approx_method1) */
 150     CvMemStorage *cinfo_storage;        /* contains _CvContourInfo nodes */
 151     CvSet *cinfo_set;           /* set of _CvContourInfo nodes */
 152     CvMemStoragePos initial_pos;        /* starting storage pos */
 153     CvMemStoragePos backup_pos; /* beginning of the latest approx. contour */
 154     CvMemStoragePos backup_pos2;        /* ending of the latest approx. contour */
 155     char *img0;                 /* image origin */
 156     char *img;                  /* current image row */
 157     int img_step;               /* image step */
 158     CvSize img_size;            /* ROI size */
 159     CvPoint offset;             /* ROI offset: coordinates, added to each contour point */
 160     CvPoint pt;                 /* current scanner position */
 161     CvPoint lnbd;               /* position of the last met contour */
 162     int nbd;                    /* current mark val */
 163     _CvContourInfo *l_cinfo;    /* information about latest approx. contour */
 164     _CvContourInfo cinfo_temp;  /* temporary var which is used in simple modes */
 165     _CvContourInfo frame_info;  /* information about frame */
 166     CvSeq frame;                /* frame itself */
 167     int approx_method1;         /* approx method when tracing */
 168     int approx_method2;         /* final approx method */
 169     int mode;                   /* contour scanning mode:
 170                                    0 - external only
 171                                    1 - all the contours w/o any hierarchy
 172                                    2 - connected components (i.e. two-level structure -
 173                                    external contours and holes) */
 174     int subst_flag;
 175     int seq_type1;              /* type of fetched contours */
 176     int header_size1;           /* hdr size of fetched contours */
 177     int elem_size1;             /* elem size of fetched contours */
 178     int seq_type2;              /*                                       */
 179     int header_size2;           /*        the same for approx. contours  */
 180     int elem_size2;             /*                                       */
 181     _CvContourInfo *cinfo_table[126];
 182 }
 183 _CvContourScanner;
 184
 185 #define _CV_FIND_CONTOURS_FLAGS_EXTERNAL_ONLY    1
 186 #define _CV_FIND_CONTOURS_FLAGS_HIERARCHIC       2
 187
 188 /*
 189    Initializes scanner structure.
 190    Prepare image for scanning ( clear borders and convert all pixels to 0-1.
 191 */
 192 CV_IMPL CvContourScanner
 193 cvStartFindContours( void* _img, CvMemStorage* storage,
 194                      int  header_size, int mode,
 195                      int  method, CvPoint offset )
 196 {
 197     int y;
 198     int step;
 199     CvSize size;
 200     uchar *img = 0;
 201     CvContourScanner scanner = 0;
 202     CvMat stub, *mat = (CvMat*)_img;
 203
 204     CV_FUNCNAME( "cvStartFindContours" );
 205
 206     __BEGIN__;
 207
 208     if( !storage )
 209         CV_ERROR( CV_StsNullPtr, "" );
 210
 211     CV_CALL( mat = cvGetMat( mat, &stub ));
 212
 213     if( !CV_IS_MASK_ARR( mat ))
 214         CV_ERROR( CV_StsUnsupportedFormat, "[Start]FindContours support only 8uC1 images" );
 215
 216     size = cvSize( mat->width, mat->height );
 217     step = mat->step;
 218     img = (uchar*)(mat->data.ptr);
 219
 220     if( method < 0 || method > CV_CHAIN_APPROX_TC89_KCOS )
 221         CV_ERROR_FROM_STATUS( CV_BADRANGE_ERR );
 222
 223     if( header_size < (int) (method == CV_CHAIN_CODE ? sizeof( CvChain ) : sizeof( CvContour )))
 224         CV_ERROR_FROM_STATUS( CV_BADSIZE_ERR );
 225
 226     scanner = (CvContourScanner)cvAlloc( sizeof( *scanner ));
 227     if( !scanner )
 228         CV_ERROR_FROM_STATUS( CV_OUTOFMEM_ERR );
 229
 230     memset( scanner, 0, sizeof( *scanner ));
 231
 232     scanner->storage1 = scanner->storage2 = storage;
 233     scanner->img0 = (char *) img;
 234     scanner->img = (char *) (img + step);
 235     scanner->img_step = step;
 236     scanner->img_size.width = size.width - 1;   /* exclude rightest column */
 237     scanner->img_size.height = size.height - 1; /* exclude bottomost row */
 238     scanner->mode = mode;
 239     scanner->offset = offset;
 240     scanner->pt.x = scanner->pt.y = 1;
 241     scanner->lnbd.x = 0;
 242     scanner->lnbd.y = 1;
 243     scanner->nbd = 2;
 244     scanner->mode = (int) mode;
 245     scanner->frame_info.contour = &(scanner->frame);
 246     scanner->frame_info.is_hole = 1;
 247     scanner->frame_info.next = 0;
 248     scanner->frame_info.parent = 0;
 249     scanner->frame_info.rect = cvRect( 0, 0, size.width, size.height );
 250     scanner->l_cinfo = 0;
 251     scanner->subst_flag = 0;
 252
 253     scanner->frame.flags = CV_SEQ_FLAG_HOLE;
 254
 255     scanner->approx_method2 = scanner->approx_method1 = method;
 256
 257     if( method == CV_CHAIN_APPROX_TC89_L1 || method == CV_CHAIN_APPROX_TC89_KCOS )
 258         scanner->approx_method1 = CV_CHAIN_CODE;
 259
 260     if( scanner->approx_method1 == CV_CHAIN_CODE )
 261     {
 262         scanner->seq_type1 = CV_SEQ_CHAIN_CONTOUR;
 263         scanner->header_size1 = scanner->approx_method1 == scanner->approx_method2 ?
 264             header_size : sizeof( CvChain );
 265         scanner->elem_size1 = sizeof( char );
 266     }
 267     else
 268     {
 269         scanner->seq_type1 = CV_SEQ_POLYGON;
 270         scanner->header_size1 = scanner->approx_method1 == scanner->approx_method2 ?
 271             header_size : sizeof( CvContour );
 272         scanner->elem_size1 = sizeof( CvPoint );
 273     }
 274
 275     scanner->header_size2 = header_size;
 276
 277     if( scanner->approx_method2 == CV_CHAIN_CODE )
 278     {
 279         scanner->seq_type2 = scanner->seq_type1;
 280         scanner->elem_size2 = scanner->elem_size1;
 281     }
 282     else
 283     {
 284         scanner->seq_type2 = CV_SEQ_POLYGON;
 285         scanner->elem_size2 = sizeof( CvPoint );
 286     }
 287
 288     scanner->seq_type1 = scanner->approx_method1 == CV_CHAIN_CODE ?
 289         CV_SEQ_CHAIN_CONTOUR : CV_SEQ_POLYGON;
 290
 291     scanner->seq_type2 = scanner->approx_method2 == CV_CHAIN_CODE ?
 292         CV_SEQ_CHAIN_CONTOUR : CV_SEQ_POLYGON;
 293
 294     cvSaveMemStoragePos( storage, &(scanner->initial_pos) );
 295
 296     if( method > CV_CHAIN_APPROX_SIMPLE )
 297     {
 298         scanner->storage1 = cvCreateChildMemStorage( scanner->storage2 );
 299     }
 300
 301     if( mode > CV_RETR_LIST )
 302     {
 303         scanner->cinfo_storage = cvCreateChildMemStorage( scanner->storage2 );
 304         scanner->cinfo_set = cvCreateSet( 0, sizeof( CvSet ), sizeof( _CvContourInfo ),
 305                                           scanner->cinfo_storage );
 306         if( scanner->cinfo_storage == 0 || scanner->cinfo_set == 0 )
 307             CV_ERROR_FROM_STATUS( CV_OUTOFMEM_ERR );
 308     }
 309
 310     /* make zero borders */
 311     memset( img, 0, size.width );
 312     memset( img + step * (size.height - 1), 0, size.width );
 313
 314     for( y = 1, img += step; y < size.height - 1; y++, img += step )
 315     {
 316         img[0] = img[size.width - 1] = 0;
 317     }
 318
 319     /* converts all pixels to 0 or 1 */
 320     cvThreshold( mat, mat, 0, 1, CV_THRESH_BINARY );
 321     CV_CHECK();
 322
 323     __END__;
 324
 325     if( cvGetErrStatus() < 0 )
 326         cvFree( &scanner );
 327
 328     return scanner;
 329 }
 330
 331 /*
 332    Final stage of contour processing.
 333    Three variants possible:
 334       1. Contour, which was retrieved using border following, is added to
 335          the contour tree. It is the case when the icvSubstituteContour function
 336          was not called after retrieving the contour.
 337
 338       2. New contour, assigned by icvSubstituteContour function, is added to the
 339          tree. The retrieved contour itself is removed from the storage.
 340          Here two cases are possible:
 341             2a. If one deals with plane variant of algorithm
 342                 (hierarchical strucutre is not reconstructed),
 343                 the contour is removed completely.
 344             2b. In hierarchical case, the header of the contour is not removed.
 345                 It's marked as "link to contour" and h_next pointer of it is set to
 346                 new, substituting contour.
 347
 348       3. The similar to 2, but when NULL pointer was assigned by
 349          icvSubstituteContour function. In this case, the function removes
 350          retrieved contour completely if plane case and
 351          leaves header if hierarchical (but doesn't mark header as "link").
 352       ------------------------------------------------------------------------
 353       The 1st variant can be used to retrieve and store all the contours from the image
 354       (with optional convertion from chains to contours using some approximation from
 355       restriced set of methods). Some characteristics of contour can be computed in the
 356       same pass.
 357
 358       The usage scheme can look like:
 359
 360       icvContourScanner scanner;
 361       CvMemStorage*  contour_storage;
 362       CvSeq*  first_contour;
 363       CvStatus  result;
 364
 365       ...
 366
 367       icvCreateMemStorage( &contour_storage, block_size/0 );
 368
 369       ...
 370
 371       cvStartFindContours
 372               ( img, contour_storage,
 373                 header_size, approx_method,
 374                 [external_only,]
 375                 &scanner );
 376
 377       for(;;)
 378       {
 379           [CvSeq* contour;]
 380           result = icvFindNextContour( &scanner, &contour/0 );
 381
 382           if( result != CV_OK ) break;
 383
 384           // calculate some characteristics
 385           ...
 386       }
 387
 388       if( result < 0 ) goto error_processing;
 389
 390       cvEndFindContours( &scanner, &first_contour );
 391       ...
 392
 393       -----------------------------------------------------------------
 394
 395       Second variant is more complex and can be used when someone wants store not
 396       the retrieved contours but transformed ones. (e.g. approximated with some
 397       non-default algorithm ).
 398
 399       The scheme can be the as following:
 400
 401       icvContourScanner scanner;
 402       CvMemStorage*  contour_storage;
 403       CvMemStorage*  temp_storage;
 404       CvSeq*  first_contour;
 405       CvStatus  result;
 406
 407       ...
 408
 409       icvCreateMemStorage( &contour_storage, block_size/0 );
 410       icvCreateMemStorage( &temp_storage, block_size/0 );
 411
 412       ...
 413
 414       icvStartFindContours8uC1R
 415               ( <img_params>, temp_storage,
 416                 header_size, approx_method,
 417                 [retrival_mode],
 418                 &scanner );
 419
 420       for(;;)
 421       {
 422           CvSeq* temp_contour;
 423           CvSeq* new_contour;
 424           result = icvFindNextContour( scanner, &temp_contour );
 425
 426           if( result != CV_OK ) break;
 427
 428           <approximation_function>( temp_contour, contour_storage,
 429                                     &new_contour, <parameters...> );
 430
 431           icvSubstituteContour( scanner, new_contour );
 432           ...
 433       }
 434
 435       if( result < 0 ) goto error_processing;
 436
 437       cvEndFindContours( &scanner, &first_contour );
 438       ...
 439
 440       ----------------------------------------------------------------------------
 441       Third method to retrieve contours may be applied if contours are irrelevant
 442       themselves but some characteristics of them are used only.
 443       The usage is similar to second except slightly different internal loop
 444
 445       for(;;)
 446       {
 447           CvSeq* temp_contour;
 448           result = icvFindNextContour( &scanner, &temp_contour );
 449
 450           if( result != CV_OK ) break;
 451
 452           // calculate some characteristics of temp_contour
 453
 454           icvSubstituteContour( scanner, 0 );
 455           ...
 456       }
 457
 458       new_storage variable is not needed here.
 459
 460       Two notes.
 461       1. Second and third method can interleave. I.e. it is possible to
 462          remain contours that satisfy with some criteria and reject others.
 463          In hierarchic case the resulting tree is the part of original tree with
 464          some nodes absent. But in the resulting tree the contour1 is a child
 465          (may be indirect) of contour2 iff in the original tree the contour1
 466          is a child (may be indirect) of contour2.
 467 */
 468 static void
 469 icvEndProcessContour( CvContourScanner scanner )
 470 {
 471     _CvContourInfo *l_cinfo = scanner->l_cinfo;
 472
 473     if( l_cinfo )
 474     {
 475         if( scanner->subst_flag )
 476         {
 477             CvMemStoragePos temp;
 478
 479             cvSaveMemStoragePos( scanner->storage2, &temp );
 480
 481             if( temp.top == scanner->backup_pos2.top &&
 482                 temp.free_space == scanner->backup_pos2.free_space )
 483             {
 484                 cvRestoreMemStoragePos( scanner->storage2, &scanner->backup_pos );
 485             }
 486             scanner->subst_flag = 0;
 487         }
 488
 489         if( l_cinfo->contour )
 490         {
 491             cvInsertNodeIntoTree( l_cinfo->contour, l_cinfo->parent->contour,
 492                                   &(scanner->frame) );
 493         }
 494         scanner->l_cinfo = 0;
 495     }
 496 }
 497
 498 /* replaces one contour with another */
 499 CV_IMPL void
 500 cvSubstituteContour( CvContourScanner scanner, CvSeq * new_contour )
 501 {
 502     _CvContourInfo *l_cinfo;
 503
 504     CV_FUNCNAME( "cvSubstituteContour" );
 505
 506     __BEGIN__;
 507
 508     if( !scanner )
 509         CV_ERROR( CV_StsNullPtr, "" );
 510
 511     l_cinfo = scanner->l_cinfo;
 512     if( l_cinfo && l_cinfo->contour && l_cinfo->contour != new_contour )
 513     {
 514         l_cinfo->contour = new_contour;
 515         scanner->subst_flag = 1;
 516     }
 517
 518     __END__;
 519 }
 520
 521
 522 /*
 523     marks domain border with +/-<constant> and stores the contour into CvSeq.
 524         method:
 525             <0  - chain
 526             ==0 - direct
 527             >0  - simple approximation
 528 */
 529 static CvStatus
 530 icvFetchContour( char                   *ptr,
 531                  int                    step,
 532                  CvPoint                pt,
 533                  CvSeq*                 contour,
 534                  int    _method )
 535 {
 536     const char      nbd = 2;
 537     int             deltas[16];
 538     CvSeqWriter     writer;
 539     char            *i0 = ptr, *i1, *i3, *i4 = 0;
 540     int             prev_s = -1, s, s_end;
 541     int             method = _method - 1;
 542
 543     assert( (unsigned) _method <= CV_CHAIN_APPROX_SIMPLE );
 544
 545     /* initialize local state */
 546     CV_INIT_3X3_DELTAS( deltas, step, 1 );
 547     memcpy( deltas + 8, deltas, 8 * sizeof( deltas[0] ));
 548
 549     /* initialize writer */
 550     cvStartAppendToSeq( contour, &writer );
 551
 552     if( method < 0 )
 553         ((CvChain *) contour)->origin = pt;
 554
 555     s_end = s = CV_IS_SEQ_HOLE( contour ) ? 0 : 4;
 556
 557     do
 558     {
 559         s = (s - 1) & 7;
 560         i1 = i0 + deltas[s];
 561         if( *i1 != 0 )
 562             break;
 563     }
 564     while( s != s_end );
 565
 566     if( s == s_end )            /* single pixel domain */
 567     {
 568         *i0 = (char) (nbd | -128);
 569         if( method >= 0 )
 570         {
 571             CV_WRITE_SEQ_ELEM( pt, writer );
 572         }
 573     }
 574     else
 575     {
 576         i3 = i0;
 577         prev_s = s ^ 4;
 578
 579         /* follow border */
 580         for( ;; )
 581         {
 582             s_end = s;
 583
 584             for( ;; )
 585             {
 586                 i4 = i3 + deltas[++s];
 587                 if( *i4 != 0 )
 588                     break;
 589             }
 590             s &= 7;
 591
 592             /* check "right" bound */
 593             if( (unsigned) (s - 1) < (unsigned) s_end )
 594             {
 595                 *i3 = (char) (nbd | -128);
 596             }
 597             else if( *i3 == 1 )
 598             {
 599                 *i3 = nbd;
 600             }
 601
 602             if( method < 0 )
 603             {
 604                 char _s = (char) s;
 605
 606                 CV_WRITE_SEQ_ELEM( _s, writer );
 607             }
 608             else
 609             {
 610                 if( s != prev_s || method == 0 )
 611                 {
 612                     CV_WRITE_SEQ_ELEM( pt, writer );
 613                     prev_s = s;
 614                 }
 615
 616                 pt.x += icvCodeDeltas[s].x;
 617                 pt.y += icvCodeDeltas[s].y;
 618
 619             }
 620
 621             if( i4 == i0 && i3 == i1 )
 622                 break;
 623
 624             i3 = i4;
 625             s = (s + 4) & 7;
 626         }                       /* end of border following loop */
 627     }
 628
 629     cvEndWriteSeq( &writer );
 630
 631     if( _method != CV_CHAIN_CODE )
 632         cvBoundingRect( contour, 1 );
 633
 634     assert( writer.seq->total == 0 && writer.seq->first == 0 ||
 635             writer.seq->total > writer.seq->first->count ||
 636             (writer.seq->first->prev == writer.seq->first &&
 637              writer.seq->first->next == writer.seq->first) );
 638
 639     return CV_OK;
 640 }
 641
 642
 643
 644 /*
 645    trace contour until certain point is met.
 646    returns 1 if met, 0 else.
 647 */
 648 static int
 649 icvTraceContour( char *ptr, int step, char *stop_ptr, int is_hole )
 650 {
 651     int deltas[16];
 652     char *i0 = ptr, *i1, *i3, *i4;
 653     int s, s_end;
 654
 655     /* initialize local state */
 656     CV_INIT_3X3_DELTAS( deltas, step, 1 );
 657     memcpy( deltas + 8, deltas, 8 * sizeof( deltas[0] ));
 658
 659     assert( (*i0 & -2) != 0 );
 660
 661     s_end = s = is_hole ? 0 : 4;
 662
 663     do
 664     {
 665         s = (s - 1) & 7;
 666         i1 = i0 + deltas[s];
 667         if( *i1 != 0 )
 668             break;
 669     }
 670     while( s != s_end );
 671
 672     i3 = i0;
 673
 674     /* check single pixel domain */
 675     if( s != s_end )
 676     {
 677         /* follow border */
 678         for( ;; )
 679         {
 680             s_end = s;
 681
 682             for( ;; )
 683             {
 684                 i4 = i3 + deltas[++s];
 685                 if( *i4 != 0 )
 686                     break;
 687             }
 688
 689             if( i3 == stop_ptr || (i4 == i0 && i3 == i1) )
 690                 break;
 691
 692             i3 = i4;
 693             s = (s + 4) & 7;
 694         }                       /* end of border following loop */
 695     }
 696     return i3 == stop_ptr;
 697 }
 698
 699
 700 static CvStatus
 701 icvFetchContourEx( char*                ptr,
 702                    int                  step,
 703                    CvPoint              pt,
 704                    CvSeq*               contour,
 705                    int  _method,
 706                    int                  nbd,
 707                    CvRect*              _rect )
 708 {
 709     int         deltas[16];
 710     CvSeqWriter writer;
 711     char        *i0 = ptr, *i1, *i3, *i4;
 712     CvRect      rect;
 713     int         prev_s = -1, s, s_end;
 714     int         method = _method - 1;
 715
 716     assert( (unsigned) _method <= CV_CHAIN_APPROX_SIMPLE );
 717     assert( 1 < nbd && nbd < 128 );
 718
 719     /* initialize local state */
 720     CV_INIT_3X3_DELTAS( deltas, step, 1 );
 721     memcpy( deltas + 8, deltas, 8 * sizeof( deltas[0] ));
 722
 723     /* initialize writer */
 724     cvStartAppendToSeq( contour, &writer );
 725
 726     if( method < 0 )
 727         ((CvChain *)contour)->origin = pt;
 728
 729     rect.x = rect.width = pt.x;
 730     rect.y = rect.height = pt.y;
 731
 732     s_end = s = CV_IS_SEQ_HOLE( contour ) ? 0 : 4;
 733
 734     do
 735     {
 736         s = (s - 1) & 7;
 737         i1 = i0 + deltas[s];
 738         if( *i1 != 0 )
 739             break;
 740     }
 741     while( s != s_end );
 742
 743     if( s == s_end )            /* single pixel domain */
 744     {
 745         *i0 = (char) (nbd | 0x80);
 746         if( method >= 0 )
 747         {
 748             CV_WRITE_SEQ_ELEM( pt, writer );
 749         }
 750     }
 751     else
 752     {
 753         i3 = i0;
 754
 755         prev_s = s ^ 4;
 756
 757         /* follow border */
 758         for( ;; )
 759         {
 760             s_end = s;
 761
 762             for( ;; )
 763             {
 764                 i4 = i3 + deltas[++s];
 765                 if( *i4 != 0 )
 766                     break;
 767             }
 768             s &= 7;
 769
 770             /* check "right" bound */
 771             if( (unsigned) (s - 1) < (unsigned) s_end )
 772             {
 773                 *i3 = (char) (nbd | 0x80);
 774             }
 775             else if( *i3 == 1 )
 776             {
 777                 *i3 = (char) nbd;
 778             }
 779
 780             if( method < 0 )
 781             {
 782                 char _s = (char) s;
 783                 CV_WRITE_SEQ_ELEM( _s, writer );
 784             }
 785             else if( s != prev_s || method == 0 )
 786             {
 787                 CV_WRITE_SEQ_ELEM( pt, writer );
 788             }
 789
 790             if( s != prev_s )
 791             {
 792                 /* update bounds */
 793                 if( pt.x < rect.x )
 794                     rect.x = pt.x;
 795                 else if( pt.x > rect.width )
 796                     rect.width = pt.x;
 797
 798                 if( pt.y < rect.y )
 799                     rect.y = pt.y;
 800                 else if( pt.y > rect.height )
 801                     rect.height = pt.y;
 802             }
 803
 804             prev_s = s;
 805             pt.x += icvCodeDeltas[s].x;
 806             pt.y += icvCodeDeltas[s].y;
 807
 808             if( i4 == i0 && i3 == i1 )  break;
 809
 810             i3 = i4;
 811             s = (s + 4) & 7;
 812         }                       /* end of border following loop */
 813     }
 814
 815     rect.width -= rect.x - 1;
 816     rect.height -= rect.y - 1;
 817
 818     cvEndWriteSeq( &writer );
 819
 820     if( _method != CV_CHAIN_CODE )
 821         ((CvContour*)contour)->rect = rect;
 822
 823     assert( writer.seq->total == 0 && writer.seq->first == 0 ||
 824             writer.seq->total > writer.seq->first->count ||
 825             (writer.seq->first->prev == writer.seq->first &&
 826              writer.seq->first->next == writer.seq->first) );
 827
 828     if( _rect )  *_rect = rect;
 829
 830     return CV_OK;
 831 }
 832
 833
 834 CvSeq *
 835 cvFindNextContour( CvContourScanner scanner )
 836 {
 837     char *img0;
 838     char *img;
 839     int step;
 840     int width, height;
 841     int x, y;
 842     int prev;
 843     CvPoint lnbd;
 844     CvSeq *contour = 0;
 845     int nbd;
 846     int mode;
 847     CvStatus result = (CvStatus) 1;
 848
 849     CV_FUNCNAME( "cvFindNextContour" );
 850
 851     __BEGIN__;
 852
 853     if( !scanner )
 854         CV_ERROR( CV_StsNullPtr, "" );
 855     icvEndProcessContour( scanner );
 856
 857     /* initialize local state */
 858     img0 = scanner->img0;
 859     img = scanner->img;
 860     step = scanner->img_step;
 861     x = scanner->pt.x;
 862     y = scanner->pt.y;
 863     width = scanner->img_size.width;
 864     height = scanner->img_size.height;
 865     mode = scanner->mode;
 866     lnbd = scanner->lnbd;
 867     nbd = scanner->nbd;
 868
 869     prev = img[x - 1];
 870
 871     for( ; y < height; y++, img += step )
 872     {
 873         for( ; x < width; x++ )
 874         {
 875             int p = img[x];
 876
 877             if( p != prev )
 878             {
 879                 _CvContourInfo *par_info = 0;
 880                 _CvContourInfo *l_cinfo = 0;
 881                 CvSeq *seq = 0;
 882                 int is_hole = 0;
 883                 CvPoint origin;
 884
 885                 if( !(prev == 0 && p == 1) )    /* if not external contour */
 886                 {
 887                     /* check hole */
 888                     if( p != 0 || prev < 1 )
 889                         goto resume_scan;
 890
 891                     if( prev & -2 )
 892                     {
 893                         lnbd.x = x - 1;
 894                     }
 895                     is_hole = 1;
 896                 }
 897
 898                 if( mode == 0 && (is_hole || img0[lnbd.y * step + lnbd.x] > 0) )
 899                     goto resume_scan;
 900
 901                 origin.y = y;
 902                 origin.x = x - is_hole;
 903
 904                 /* find contour parent */
 905                 if( mode <= 1 || (!is_hole && mode == 2) || lnbd.x <= 0 )
 906                 {
 907                     par_info = &(scanner->frame_info);
 908                 }
 909                 else
 910                 {
 911                     int lval = img0[lnbd.y * step + lnbd.x] & 0x7f;
 912                     _CvContourInfo *cur = scanner->cinfo_table[lval - 2];
 913
 914                     assert( lval >= 2 );
 915
 916                     /* find the first bounding contour */
 917                     while( cur )
 918                     {
 919                         if( (unsigned) (lnbd.x - cur->rect.x) < (unsigned) cur->rect.width &&
 920                             (unsigned) (lnbd.y - cur->rect.y) < (unsigned) cur->rect.height )
 921                         {
 922                             if( par_info )
 923                             {
 924                                 if( icvTraceContour( scanner->img0 +
 925                                                      par_info->origin.y * step +
 926                                                      par_info->origin.x, step, img + lnbd.x,
 927                                                      par_info->is_hole ) > 0 )
 928                                     break;
 929                             }
 930                             par_info = cur;
 931                         }
 932                         cur = cur->next;
 933                     }
 934
 935                     assert( par_info != 0 );
 936
 937                     /* if current contour is a hole and previous contour is a hole or
 938                        current contour is external and previous contour is external then
 939                        the parent of the contour is the parent of the previous contour else
 940                        the parent is the previous contour itself. */
 941                     if( par_info->is_hole == is_hole )
 942                     {
 943                         par_info = par_info->parent;
 944                         /* every contour must have a parent
 945                            (at least, the frame of the image) */
 946                         if( !par_info )
 947                             par_info = &(scanner->frame_info);
 948                     }
 949
 950                     /* hole flag of the parent must differ from the flag of the contour */
 951                     assert( par_info->is_hole != is_hole );
 952                     if( par_info->contour == 0 )        /* removed contour */
 953                         goto resume_scan;
 954                 }
 955
 956                 lnbd.x = x - is_hole;
 957
 958                 cvSaveMemStoragePos( scanner->storage2, &(scanner->backup_pos) );
 959
 960                 seq = cvCreateSeq( scanner->seq_type1, scanner->header_size1,
 961                                    scanner->elem_size1, scanner->storage1 );
 962                 if( !seq )
 963                 {
 964                     result = CV_OUTOFMEM_ERR;
 965                     goto exit_func;
 966                 }
 967                 seq->flags |= is_hole ? CV_SEQ_FLAG_HOLE : 0;
 968
 969                 /* initialize header */
 970                 if( mode <= 1 )
 971                 {
 972                     l_cinfo = &(scanner->cinfo_temp);
 973                     result = icvFetchContour( img + x - is_hole, step,
 974                                               cvPoint( origin.x + scanner->offset.x,
 975                                                        origin.y + scanner->offset.y),
 976                                               seq, scanner->approx_method1 );
 977                     if( result < 0 )
 978                         goto exit_func;
 979                 }
 980                 else
 981                 {
 982                     union { _CvContourInfo* ci; CvSetElem* se; } v;
 983                     v.ci = l_cinfo;
 984                     cvSetAdd( scanner->cinfo_set, 0, &v.se );
 985                     l_cinfo = v.ci;
 986
 987                     result = icvFetchContourEx( img + x - is_hole, step,
 988                                                 cvPoint( origin.x + scanner->offset.x,
 989                                                          origin.y + scanner->offset.y),
 990                                                 seq, scanner->approx_method1,
 991                                                 nbd, &(l_cinfo->rect) );
 992                     if( result < 0 )
 993                         goto exit_func;
 994                     l_cinfo->rect.x -= scanner->offset.x;
 995                     l_cinfo->rect.y -= scanner->offset.y;
 996
 997                     l_cinfo->next = scanner->cinfo_table[nbd - 2];
 998                     scanner->cinfo_table[nbd - 2] = l_cinfo;
 999
1000                     /* change nbd */
1001                     nbd = (nbd + 1) & 127;
1002                     nbd += nbd == 0 ? 3 : 0;
1003                 }
1004
1005                 l_cinfo->is_hole = is_hole;
1006                 l_cinfo->contour = seq;
1007                 l_cinfo->origin = origin;
1008                 l_cinfo->parent = par_info;
1009
1010                 if( scanner->approx_method1 != scanner->approx_method2 )
1011                 {
1012                     result = icvApproximateChainTC89( (CvChain *) seq,
1013                                                       scanner->header_size2,
1014                                                       scanner->storage2,
1015                                                       &(l_cinfo->contour),
1016                                                       scanner->approx_method2 );
1017                     if( result < 0 )
1018                         goto exit_func;
1019                     cvClearMemStorage( scanner->storage1 );
1020                 }
1021
1022                 l_cinfo->contour->v_prev = l_cinfo->parent->contour;
1023
1024                 if( par_info->contour == 0 )
1025                 {
1026                     l_cinfo->contour = 0;
1027                     if( scanner->storage1 == scanner->storage2 )
1028                     {
1029                         cvRestoreMemStoragePos( scanner->storage1, &(scanner->backup_pos) );
1030                     }
1031                     else
1032                     {
1033                         cvClearMemStorage( scanner->storage1 );
1034                     }
1035                     p = img[x];
1036                     goto resume_scan;
1037                 }
1038
1039                 cvSaveMemStoragePos( scanner->storage2, &(scanner->backup_pos2) );
1040                 scanner->l_cinfo = l_cinfo;
1041                 scanner->pt.x = x + 1;
1042                 scanner->pt.y = y;
1043                 scanner->lnbd = lnbd;
1044                 scanner->img = (char *) img;
1045                 scanner->nbd = nbd;
1046                 contour = l_cinfo->contour;
1047
1048                 result = CV_OK;
1049                 goto exit_func;
1050               resume_scan:
1051                 prev = p;
1052                 /* update lnbd */
1053                 if( prev & -2 )
1054                 {
1055                     lnbd.x = x;
1056                 }
1057             }                   /* end of prev != p */
1058         }                       /* end of loop on x */
1059
1060         lnbd.x = 0;
1061         lnbd.y = y + 1;
1062         x = 1;
1063         prev = 0;
1064
1065     }                           /* end of loop on y */
1066
1067   exit_func:
1068
1069     if( result != 0 )
1070         contour = 0;
1071     if( result < 0 )
1072         CV_ERROR_FROM_STATUS( result );
1073
1074     __END__;
1075
1076     return contour;
1077 }
1078
1079
1080 /*
1081    The function add to tree the last retrieved/substituted contour,
1082    releases temp_storage, restores state of dst_storage (if needed), and
1083    returns pointer to root of the contour tree */
1084 CV_IMPL CvSeq *
1085 cvEndFindContours( CvContourScanner * _scanner )
1086 {
1087     CvContourScanner scanner;
1088     CvSeq *first = 0;
1089
1090     CV_FUNCNAME( "cvFindNextContour" );
1091
1092     __BEGIN__;
1093
1094     if( !_scanner )
1095         CV_ERROR( CV_StsNullPtr, "" );
1096     scanner = *_scanner;
1097
1098     if( scanner )
1099     {
1100         icvEndProcessContour( scanner );
1101
1102         if( scanner->storage1 != scanner->storage2 )
1103             cvReleaseMemStorage( &(scanner->storage1) );
1104
1105         if( scanner->cinfo_storage )
1106             cvReleaseMemStorage( &(scanner->cinfo_storage) );
1107
1108         first = scanner->frame.v_next;
1109         cvFree( _scanner );
1110     }
1111
1112     __END__;
1113
1114     return first;
1115 }
1116
1117
1118 #define ICV_SINGLE                  0
1119 #define ICV_CONNECTING_ABOVE        1
1120 #define ICV_CONNECTING_BELOW        -1
1121 #define ICV_IS_COMPONENT_POINT(val) ((val) != 0)
1122
1123 #define CV_GET_WRITTEN_ELEM( writer ) ((writer).ptr - (writer).seq->elem_size)
1124
1125 typedef  struct CvLinkedRunPoint
1126 {
1127     struct CvLinkedRunPoint* link;
1128     struct CvLinkedRunPoint* next;
1129     CvPoint pt;
1130 }
1131 CvLinkedRunPoint;
1132
1133
1134 static int
1135 icvFindContoursInInterval( const CvArr* src,
1136                            /*int minValue, int maxValue,*/
1137                            CvMemStorage* storage,
1138                            CvSeq** result,
1139                            int contourHeaderSize )
1140 {
1141     int count = 0;
1142     CvMemStorage* storage00 = 0;
1143     CvMemStorage* storage01 = 0;
1144     CvSeq* first = 0;
1145
1146     CV_FUNCNAME( "icvFindContoursInInterval" );
1147
1148     __BEGIN__;
1149
1150     int i, j, k, n;
1151
1152     uchar*  src_data = 0;
1153     int  img_step = 0;
1154     CvSize  img_size;
1155
1156     int  connect_flag;
1157     int  lower_total;
1158     int  upper_total;
1159     int  all_total;
1160
1161     CvSeq*  runs;
1162     CvLinkedRunPoint  tmp;
1163     CvLinkedRunPoint*  tmp_prev;
1164     CvLinkedRunPoint*  upper_line = 0;
1165     CvLinkedRunPoint*  lower_line = 0;
1166     CvLinkedRunPoint*  last_elem;
1167
1168     CvLinkedRunPoint*  upper_run = 0;
1169     CvLinkedRunPoint*  lower_run = 0;
1170     CvLinkedRunPoint*  prev_point = 0;
1171
1172     CvSeqWriter  writer_ext;
1173     CvSeqWriter  writer_int;
1174     CvSeqWriter  writer;
1175     CvSeqReader  reader;
1176
1177     CvSeq* external_contours;
1178     CvSeq* internal_contours;
1179     CvSeq* prev = 0;
1180
1181     if( !storage )
1182         CV_ERROR( CV_StsNullPtr, "NULL storage pointer" );
1183
1184     if( !result )
1185         CV_ERROR( CV_StsNullPtr, "NULL double CvSeq pointer" );
1186
1187     if( contourHeaderSize < (int)sizeof(CvContour))
1188         CV_ERROR( CV_StsBadSize, "Contour header size must be >= sizeof(CvContour)" );
1189
1190     CV_CALL( storage00 = cvCreateChildMemStorage(storage));
1191     CV_CALL( storage01 = cvCreateChildMemStorage(storage));
1192
1193     {
1194         CvMat stub, *mat;
1195
1196         CV_CALL( mat = cvGetMat( src, &stub ));
1197         if( !CV_IS_MASK_ARR(mat))
1198             CV_ERROR( CV_StsBadArg, "Input array must be 8uC1 or 8sC1" );
1199         src_data = mat->data.ptr;
1200         img_step = mat->step;
1201         img_size = cvGetMatSize( mat );
1202     }
1203
1204     // Create temporary sequences
1205     runs = cvCreateSeq(0, sizeof(CvSeq), sizeof(CvLinkedRunPoint), storage00 );
1206     cvStartAppendToSeq( runs, &writer );
1207
1208     cvStartWriteSeq( 0, sizeof(CvSeq), sizeof(CvLinkedRunPoint*), storage01, &writer_ext );
1209     cvStartWriteSeq( 0, sizeof(CvSeq), sizeof(CvLinkedRunPoint*), storage01, &writer_int );
1210
1211     tmp_prev = &(tmp);
1212     tmp_prev->next = 0;
1213     tmp_prev->link = 0;
1214
1215     // First line. None of runs is binded
1216     tmp.pt.y = 0;
1217     i = 0;
1218     CV_WRITE_SEQ_ELEM( tmp, writer );
1219     upper_line = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer );
1220
1221     tmp_prev = upper_line;
1222     for( j = 0; j < img_size.width; )
1223     {
1224         for( ; j < img_size.width && !ICV_IS_COMPONENT_POINT(src_data[j]); j++ )
1225             ;
1226         if( j == img_size.width )
1227             break;
1228
1229         tmp.pt.x = j;
1230         CV_WRITE_SEQ_ELEM( tmp, writer );
1231         tmp_prev->next = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer );
1232         tmp_prev = tmp_prev->next;
1233
1234         for( ; j < img_size.width && ICV_IS_COMPONENT_POINT(src_data[j]); j++ )
1235             ;
1236
1237         tmp.pt.x = j-1;
1238         CV_WRITE_SEQ_ELEM( tmp, writer );
1239         tmp_prev->next = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer );
1240         tmp_prev->link = tmp_prev->next;
1241         // First point of contour
1242         CV_WRITE_SEQ_ELEM( tmp_prev, writer_ext );
1243         tmp_prev = tmp_prev->next;
1244     }
1245     cvFlushSeqWriter( &writer );
1246     upper_line = upper_line->next;
1247     upper_total = runs->total - 1;
1248     last_elem = tmp_prev;
1249     tmp_prev->next = 0;
1250
1251     for( i = 1; i < img_size.height; i++ )
1252     {
1253 //------// Find runs in next line
1254         src_data += img_step;
1255         tmp.pt.y = i;
1256         all_total = runs->total;
1257         for( j = 0; j < img_size.width; )
1258         {
1259             for( ; j < img_size.width && !ICV_IS_COMPONENT_POINT(src_data[j]); j++ )
1260                 ;
1261             if( j == img_size.width ) break;
1262
1263             tmp.pt.x = j;
1264             CV_WRITE_SEQ_ELEM( tmp, writer );
1265             tmp_prev->next = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer );
1266             tmp_prev = tmp_prev->next;
1267
1268             for( ; j < img_size.width && ICV_IS_COMPONENT_POINT(src_data[j]); j++ )
1269                 ;
1270
1271             tmp.pt.x = j-1;
1272             CV_WRITE_SEQ_ELEM( tmp, writer );
1273             tmp_prev = tmp_prev->next = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer );
1274         }//j
1275         cvFlushSeqWriter( &writer );
1276         lower_line = last_elem->next;
1277         lower_total = runs->total - all_total;
1278         last_elem = tmp_prev;
1279         tmp_prev->next = 0;
1280 //------//
1281 //------// Find links between runs of lower_line and upper_line
1282         upper_run = upper_line;
1283         lower_run = lower_line;
1284         connect_flag = ICV_SINGLE;
1285
1286         for( k = 0, n = 0; k < upper_total/2 && n < lower_total/2; )
1287         {
1288             switch( connect_flag )
1289             {
1290             case ICV_SINGLE:
1291                 if( upper_run->next->pt.x < lower_run->next->pt.x )
1292                 {
1293                     if( upper_run->next->pt.x >= lower_run->pt.x  -1 )
1294                     {
1295                         lower_run->link = upper_run;
1296                         connect_flag = ICV_CONNECTING_ABOVE;
1297                         prev_point = upper_run->next;
1298                     }
1299                     else
1300                         upper_run->next->link = upper_run;
1301                     k++;
1302                     upper_run = upper_run->next->next;
1303                 }
1304                 else
1305                 {
1306                     if( upper_run->pt.x <= lower_run->next->pt.x  +1 )
1307                     {
1308                         lower_run->link = upper_run;
1309                         connect_flag = ICV_CONNECTING_BELOW;
1310                         prev_point = lower_run->next;
1311                     }
1312                     else
1313                     {
1314                         lower_run->link = lower_run->next;
1315                         // First point of contour
1316                         CV_WRITE_SEQ_ELEM( lower_run, writer_ext );
1317                     }
1318                     n++;
1319                     lower_run = lower_run->next->next;
1320                 }
1321                 break;
1322             case ICV_CONNECTING_ABOVE:
1323                 if( upper_run->pt.x > lower_run->next->pt.x +1 )
1324                 {
1325                     prev_point->link = lower_run->next;
1326                     connect_flag = ICV_SINGLE;
1327                     n++;
1328                     lower_run = lower_run->next->next;
1329                 }
1330                 else
1331                 {
1332                     prev_point->link = upper_run;
1333                     if( upper_run->next->pt.x < lower_run->next->pt.x )
1334                     {
1335                         k++;
1336                         prev_point = upper_run->next;
1337                         upper_run = upper_run->next->next;
1338                     }
1339                     else
1340                     {
1341                         connect_flag = ICV_CONNECTING_BELOW;
1342                         prev_point = lower_run->next;
1343                         n++;
1344                         lower_run = lower_run->next->next;
1345                     }
1346                 }
1347                 break;
1348             case ICV_CONNECTING_BELOW:
1349                 if( lower_run->pt.x > upper_run->next->pt.x +1 )
1350                 {
1351                     upper_run->next->link = prev_point;
1352                     connect_flag = ICV_SINGLE;
1353                     k++;
1354                     upper_run = upper_run->next->next;
1355                 }
1356                 else
1357                 {
1358                     // First point of contour
1359                     CV_WRITE_SEQ_ELEM( lower_run, writer_int );
1360
1361                     lower_run->link = prev_point;
1362                     if( lower_run->next->pt.x < upper_run->next->pt.x )
1363                     {
1364                         n++;
1365                         prev_point = lower_run->next;
1366                         lower_run = lower_run->next->next;
1367                     }
1368                     else
1369                     {
1370                         connect_flag = ICV_CONNECTING_ABOVE;
1371                         k++;
1372                         prev_point = upper_run->next;
1373                         upper_run = upper_run->next->next;
1374                     }
1375                 }
1376                 break;
1377             }
1378         }// k, n
1379
1380         for( ; n < lower_total/2; n++ )
1381         {
1382             if( connect_flag != ICV_SINGLE )
1383             {
1384                 prev_point->link = lower_run->next;
1385                 connect_flag = ICV_SINGLE;
1386                 lower_run = lower_run->next->next;
1387                 continue;
1388             }
1389             lower_run->link = lower_run->next;
1390
1391             //First point of contour
1392             CV_WRITE_SEQ_ELEM( lower_run, writer_ext );
1393
1394             lower_run = lower_run->next->next;
1395         }
1396
1397         for( ; k < upper_total/2; k++ )
1398         {
1399             if( connect_flag != ICV_SINGLE )
1400             {
1401                 upper_run->next->link = prev_point;
1402                 connect_flag = ICV_SINGLE;
1403                 upper_run = upper_run->next->next;
1404                 continue;
1405             }
1406             upper_run->next->link = upper_run;
1407             upper_run = upper_run->next->next;
1408         }
1409         upper_line = lower_line;
1410         upper_total = lower_total;
1411     }//i
1412
1413     upper_run = upper_line;
1414
1415     //the last line of image
1416     for( k = 0; k < upper_total/2; k++ )
1417     {
1418         upper_run->next->link = upper_run;
1419         upper_run = upper_run->next->next;
1420     }
1421
1422 //------//
1423 //------//Find end read contours
1424     external_contours = cvEndWriteSeq( &writer_ext );
1425     internal_contours = cvEndWriteSeq( &writer_int );
1426
1427     for( k = 0; k < 2; k++ )
1428     {
1429         CvSeq* contours = k == 0 ? external_contours : internal_contours;
1430
1431         cvStartReadSeq( contours, &reader );
1432
1433         for( j = 0; j < contours->total; j++, count++ )
1434         {
1435             CvLinkedRunPoint* p_temp;
1436             CvLinkedRunPoint* p00;
1437             CvLinkedRunPoint* p01;
1438             CvSeq* contour;
1439
1440             CV_READ_SEQ_ELEM( p00, reader );
1441             p01 = p00;
1442
1443             if( !p00->link )
1444                 continue;
1445
1446             cvStartWriteSeq( CV_SEQ_ELTYPE_POINT | CV_SEQ_POLYLINE | CV_SEQ_FLAG_CLOSED,
1447                              contourHeaderSize, sizeof(CvPoint), storage, &writer );
1448             do
1449             {
1450                 CV_WRITE_SEQ_ELEM( p00->pt, writer );
1451                 p_temp = p00;
1452                 p00 = p00->link;
1453                 p_temp->link = 0;
1454             }
1455             while( p00 != p01 );
1456
1457             contour = cvEndWriteSeq( &writer );
1458             cvBoundingRect( contour, 1 );
1459
1460             if( k != 0 )
1461                 contour->flags |= CV_SEQ_FLAG_HOLE;
1462
1463             if( !first )
1464                 prev = first = contour;
1465             else
1466             {
1467                 contour->h_prev = prev;
1468                 prev = prev->h_next = contour;
1469             }
1470         }
1471     }
1472
1473     __END__;
1474
1475     if( !first )
1476         count = -1;
1477
1478     if( result )
1479         *result = first;
1480
1481     cvReleaseMemStorage(&storage00);
1482     cvReleaseMemStorage(&storage01);
1483
1484     return count;
1485 }
1486
1487
1488
1489 /*F///////////////////////////////////////////////////////////////////////////////////////
1490 //    Name: cvFindContours
1491 //    Purpose:
1492 //      Finds all the contours on the bi-level image.
1493 //    Context:
1494 //    Parameters:
1495 //      img  - source image.
1496 //             Non-zero pixels are considered as 1-pixels
1497 //             and zero pixels as 0-pixels.
1498 //      step - full width of source image in bytes.
1499 //      size - width and height of the image in pixels
1500 //      storage - pointer to storage where will the output contours be placed.
1501 //      header_size - header size of resulting contours
1502 //      mode - mode of contour retrieval.
1503 //      method - method of approximation that is applied to contours
1504 //      first_contour - pointer to first contour pointer
1505 //    Returns:
1506 //      CV_OK or error code
1507 //    Notes:
1508 //F*/
1509 CV_IMPL int
1510 cvFindContours( void*  img,  CvMemStorage*  storage,
1511                 CvSeq**  firstContour, int  cntHeaderSize,
1512                 int  mode,
1513                 int  method, CvPoint offset )
1514 {
1515     CvContourScanner scanner = 0;
1516     CvSeq *contour = 0;
1517     int count = -1;
1518
1519     CV_FUNCNAME( "cvFindContours" );
1520
1521     __BEGIN__;
1522
1523     if( !firstContour )
1524         CV_ERROR( CV_StsNullPtr, "NULL double CvSeq pointer" );
1525
1526     if( method == CV_LINK_RUNS )
1527     {
1528         if( offset.x != 0 || offset.y != 0 )
1529             CV_ERROR( CV_StsOutOfRange,
1530             "Nonzero offset is not supported in CV_LINK_RUNS yet" );
1531
1532         CV_CALL( count = icvFindContoursInInterval( img, storage,
1533                                     firstContour, cntHeaderSize ));
1534     }
1535     else
1536     {
1537         CV_CALL( scanner = cvStartFindContours( img, storage,
1538                         cntHeaderSize, mode, method, offset ));
1539         assert( scanner );
1540
1541         do
1542         {
1543             count++;
1544             contour = cvFindNextContour( scanner );
1545         }
1546         while( contour != 0 );
1547
1548         *firstContour = cvEndFindContours( &scanner );
1549     }
1550
1551     __END__;
1552
1553     return count;
1554 }
1555
1556
1557 /* End of file. */