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