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 #define CV_MATCH_CHECK( status, cvFun ) \ 44 { \ 45 status = cvFun; \ 46 if( status != CV_OK ) \ 47 goto M_END; \ 48 } 49 50 static CvStatus 51 icvCalcTriAttr( const CvSeq * contour, CvPoint t2, CvPoint t1, int n1, 52 CvPoint t3, int n3, double *s, double *s_c, 53 double *h, double *a, double *b ); 54 55 /*F/////////////////////////////////////////////////////////////////////////////////////// 56 // Name: icvCreateContourTree 57 // Purpose: 58 // Create binary tree representation for the contour 59 // Context: 60 // Parameters: 61 // contour - pointer to input contour object. 62 // storage - pointer to the current storage block 63 // tree - output pointer to the binary tree representation 64 // threshold - threshold for the binary tree building 65 // 66 //F*/ 67 static CvStatus 68 icvCreateContourTree( const CvSeq * contour, CvMemStorage * storage, 69 CvContourTree ** tree, double threshold ) 70 { 71 CvPoint *pt_p; /* pointer to previos points */ 72 CvPoint *pt_n; /* pointer to next points */ 73 CvPoint *pt1, *pt2; /* pointer to current points */ 74 75 CvPoint t, tp1, tp2, tp3, tn1, tn2, tn3; 76 int lpt, flag, i, j, i_tree, j_1, j_3, i_buf; 77 double s, sp1, sp2, sn1, sn2, s_c, sp1_c, sp2_c, sn1_c, sn2_c, h, hp1, hp2, hn1, hn2, 78 a, ap1, ap2, an1, an2, b, bp1, bp2, bn1, bn2; 79 double a_s_c, a_sp1_c; 80 81 _CvTrianAttr **ptr_p, **ptr_n, **ptr1, **ptr2; /* pointers to pointers of triangles */ 82 _CvTrianAttr *cur_adr; 83 84 int *num_p, *num_n, *num1, *num2; /* numbers of input contour points */ 85 int nm, nmp1, nmp2, nmp3, nmn1, nmn2, nmn3; 86 int seq_flags = 1, i_end, prev_null, prev2_null; 87 double koef = 1.5; 88 double eps = 1.e-7; 89 double e; 90 CvStatus status; 91 int hearder_size; 92 _CvTrianAttr tree_one, tree_two, *tree_end, *tree_root; 93 94 CvSeqWriter writer; 95 96 assert( contour != NULL && contour->total >= 4 ); 97 status = CV_OK; 98 99 if( contour == NULL ) 100 return CV_NULLPTR_ERR; 101 if( contour->total < 4 ) 102 return CV_BADSIZE_ERR; 103 104 if( !CV_IS_SEQ_POLYGON( contour )) 105 return CV_BADFLAG_ERR; 106 107 108 /* Convert Sequence to array */ 109 lpt = contour->total; 110 pt_p = pt_n = NULL; 111 num_p = num_n = NULL; 112 ptr_p = ptr_n = ptr1 = ptr2 = NULL; 113 tree_end = NULL; 114 115 pt_p = (CvPoint *) cvAlloc( lpt * sizeof( CvPoint )); 116 pt_n = (CvPoint *) cvAlloc( lpt * sizeof( CvPoint )); 117 118 num_p = (int *) cvAlloc( lpt * sizeof( int )); 119 num_n = (int *) cvAlloc( lpt * sizeof( int )); 120 121 hearder_size = sizeof( CvContourTree ); 122 seq_flags = CV_SEQ_POLYGON_TREE; 123 cvStartWriteSeq( seq_flags, hearder_size, sizeof( _CvTrianAttr ), storage, &writer ); 124 125 ptr_p = (_CvTrianAttr **) cvAlloc( lpt * sizeof( _CvTrianAttr * )); 126 ptr_n = (_CvTrianAttr **) cvAlloc( lpt * sizeof( _CvTrianAttr * )); 127 128 memset( ptr_p, 0, lpt * sizeof( _CvTrianAttr * )); 129 memset( ptr_n, 0, lpt * sizeof( _CvTrianAttr * )); 130 131 if( pt_p == NULL || pt_n == NULL ) 132 return CV_OUTOFMEM_ERR; 133 if( ptr_p == NULL || ptr_n == NULL ) 134 return CV_OUTOFMEM_ERR; 135 136 /* write fild for the binary tree root */ 137 /* start_writer = writer; */ 138 139 tree_one.pt.x = tree_one.pt.y = 0; 140 tree_one.sign = 0; 141 tree_one.area = 0; 142 tree_one.r1 = tree_one.r2 = 0; 143 tree_one.next_v1 = tree_one.next_v2 = tree_one.prev_v = NULL; 144 145 CV_WRITE_SEQ_ELEM( tree_one, writer ); 146 tree_root = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 147 148 if( cvCvtSeqToArray( contour, (char *) pt_p ) == (char *) contour ) 149 return CV_BADPOINT_ERR; 150 151 for( i = 0; i < lpt; i++ ) 152 num_p[i] = i; 153 154 i = lpt; 155 flag = 0; 156 i_tree = 0; 157 e = 20.; /* initial threshold value */ 158 ptr1 = ptr_p; 159 ptr2 = ptr_n; 160 pt1 = pt_p; 161 pt2 = pt_n; 162 num1 = num_p; 163 num2 = num_n; 164 /* binary tree constraction */ 165 while( i > 4 ) 166 { 167 if( flag == 0 ) 168 { 169 ptr1 = ptr_p; 170 ptr2 = ptr_n; 171 pt1 = pt_p; 172 pt2 = pt_n; 173 num1 = num_p; 174 num2 = num_n; 175 flag = 1; 176 } 177 else 178 { 179 ptr1 = ptr_n; 180 ptr2 = ptr_p; 181 pt1 = pt_n; 182 pt2 = pt_p; 183 num1 = num_n; 184 num2 = num_p; 185 flag = 0; 186 } 187 t = pt1[0]; 188 nm = num1[0]; 189 tp1 = pt1[i - 1]; 190 nmp1 = num1[i - 1]; 191 tp2 = pt1[i - 2]; 192 nmp2 = num1[i - 2]; 193 tp3 = pt1[i - 3]; 194 nmp3 = num1[i - 3]; 195 tn1 = pt1[1]; 196 nmn1 = num1[1]; 197 tn2 = pt1[2]; 198 nmn2 = num1[2]; 199 200 i_buf = 0; 201 i_end = -1; 202 CV_MATCH_CHECK( status, 203 icvCalcTriAttr( contour, t, tp1, nmp1, tn1, nmn1, &s, &s_c, &h, &a, 204 &b )); 205 CV_MATCH_CHECK( status, 206 icvCalcTriAttr( contour, tp1, tp2, nmp2, t, nm, &sp1, &sp1_c, &hp1, 207 &ap1, &bp1 )); 208 CV_MATCH_CHECK( status, 209 icvCalcTriAttr( contour, tp2, tp3, nmp3, tp1, nmp1, &sp2, &sp2_c, &hp2, 210 &ap2, &bp2 )); 211 CV_MATCH_CHECK( status, 212 icvCalcTriAttr( contour, tn1, t, nm, tn2, nmn2, &sn1, &sn1_c, &hn1, 213 &an1, &bn1 )); 214 215 216 j_3 = 3; 217 prev_null = prev2_null = 0; 218 for( j = 0; j < i; j++ ) 219 { 220 tn3 = pt1[j_3]; 221 nmn3 = num1[j_3]; 222 if( j == 0 ) 223 j_1 = i - 1; 224 else 225 j_1 = j - 1; 226 227 CV_MATCH_CHECK( status, icvCalcTriAttr( contour, tn2, tn1, nmn1, tn3, nmn3, 228 &sn2, &sn2_c, &hn2, &an2, &bn2 )); 229 230 if( (s_c < sp1_c && s_c < sp2_c && s_c <= sn1_c && s_c <= sn2_c && s_c < e) || 231 (((s_c == sp1_c && s_c <= sp2_c) || (s_c == sp2_c && s_c <= sp1_c)) && 232 s_c <= sn1_c && s_c <= sn2_c && s_c < e && j > 1 && prev2_null == 0) || 233 (s_c < eps && j > 0 && prev_null == 0) ) 234 { 235 prev_null = prev2_null = 1; 236 if( s_c < threshold ) 237 { 238 if( ptr1[j_1] == NULL && ptr1[j] == NULL ) 239 { 240 if( i_buf > 0 ) 241 ptr2[i_buf - 1] = NULL; 242 else 243 i_end = 0; 244 } 245 else 246 { 247 /* form next vertex */ 248 tree_one.pt = t; 249 tree_one.sign = (char) (CV_SIGN( s )); 250 tree_one.r1 = h / a; 251 tree_one.r2 = b / a; 252 tree_one.area = fabs( s ); 253 tree_one.next_v1 = ptr1[j_1]; 254 tree_one.next_v2 = ptr1[j]; 255 256 CV_WRITE_SEQ_ELEM( tree_one, writer ); 257 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 258 259 if( ptr1[j_1] != NULL ) 260 ptr1[j_1]->prev_v = cur_adr; 261 if( ptr1[j] != NULL ) 262 ptr1[j]->prev_v = cur_adr; 263 264 if( i_buf > 0 ) 265 ptr2[i_buf - 1] = cur_adr; 266 else 267 { 268 tree_end = (_CvTrianAttr *) writer.ptr; 269 i_end = 1; 270 } 271 i_tree++; 272 } 273 } 274 else 275 /* form next vertex */ 276 { 277 tree_one.pt = t; 278 tree_one.sign = (char) (CV_SIGN( s )); 279 tree_one.area = fabs( s ); 280 tree_one.r1 = h / a; 281 tree_one.r2 = b / a; 282 tree_one.next_v1 = ptr1[j_1]; 283 tree_one.next_v2 = ptr1[j]; 284 285 CV_WRITE_SEQ_ELEM( tree_one, writer ); 286 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 287 288 if( ptr1[j_1] != NULL ) 289 ptr1[j_1]->prev_v = cur_adr; 290 if( ptr1[j] != NULL ) 291 ptr1[j]->prev_v = cur_adr; 292 293 if( i_buf > 0 ) 294 ptr2[i_buf - 1] = cur_adr; 295 else 296 { 297 tree_end = cur_adr; 298 i_end = 1; 299 } 300 i_tree++; 301 } 302 } 303 else 304 /* the current triangle is'not LMIAT */ 305 { 306 prev_null = 0; 307 switch (prev2_null) 308 { 309 case 0: 310 break; 311 case 1: 312 { 313 prev2_null = 2; 314 break; 315 } 316 case 2: 317 { 318 prev2_null = 0; 319 break; 320 } 321 } 322 if( j != i - 1 || i_end == -1 ) 323 ptr2[i_buf] = ptr1[j]; 324 else if( i_end == 0 ) 325 ptr2[i_buf] = NULL; 326 else 327 ptr2[i_buf] = tree_end; 328 pt2[i_buf] = t; 329 num2[i_buf] = num1[j]; 330 i_buf++; 331 } 332 /* go to next vertex */ 333 tp3 = tp2; 334 tp2 = tp1; 335 tp1 = t; 336 t = tn1; 337 tn1 = tn2; 338 tn2 = tn3; 339 nmp3 = nmp2; 340 nmp2 = nmp1; 341 nmp1 = nm; 342 nm = nmn1; 343 nmn1 = nmn2; 344 nmn2 = nmn3; 345 346 sp2 = sp1; 347 sp1 = s; 348 s = sn1; 349 sn1 = sn2; 350 sp2_c = sp1_c; 351 sp1_c = s_c; 352 s_c = sn1_c; 353 sn1_c = sn2_c; 354 355 ap2 = ap1; 356 ap1 = a; 357 a = an1; 358 an1 = an2; 359 bp2 = bp1; 360 bp1 = b; 361 b = bn1; 362 bn1 = bn2; 363 hp2 = hp1; 364 hp1 = h; 365 h = hn1; 366 hn1 = hn2; 367 j_3++; 368 if( j_3 >= i ) 369 j_3 = 0; 370 } 371 372 i = i_buf; 373 e = e * koef; 374 } 375 376 /* constract tree root */ 377 if( i != 4 ) 378 return CV_BADFACTOR_ERR; 379 380 t = pt2[0]; 381 tn1 = pt2[1]; 382 tn2 = pt2[2]; 383 tp1 = pt2[3]; 384 nm = num2[0]; 385 nmn1 = num2[1]; 386 nmn2 = num2[2]; 387 nmp1 = num2[3]; 388 /* first pair of the triangles */ 389 CV_MATCH_CHECK( status, 390 icvCalcTriAttr( contour, t, tp1, nmp1, tn1, nmn1, &s, &s_c, &h, &a, &b )); 391 CV_MATCH_CHECK( status, 392 icvCalcTriAttr( contour, tn2, tn1, nmn1, tp1, nmp1, &sn2, &sn2_c, &hn2, 393 &an2, &bn2 )); 394 /* second pair of the triangles */ 395 CV_MATCH_CHECK( status, 396 icvCalcTriAttr( contour, tn1, t, nm, tn2, nmn2, &sn1, &sn1_c, &hn1, &an1, 397 &bn1 )); 398 CV_MATCH_CHECK( status, 399 icvCalcTriAttr( contour, tp1, tn2, nmn2, t, nm, &sp1, &sp1_c, &hp1, &ap1, 400 &bp1 )); 401 402 a_s_c = fabs( s_c - sn2_c ); 403 a_sp1_c = fabs( sp1_c - sn1_c ); 404 405 if( a_s_c > a_sp1_c ) 406 /* form child vertexs for the root */ 407 { 408 tree_one.pt = t; 409 tree_one.sign = (char) (CV_SIGN( s )); 410 tree_one.area = fabs( s ); 411 tree_one.r1 = h / a; 412 tree_one.r2 = b / a; 413 tree_one.next_v1 = ptr2[3]; 414 tree_one.next_v2 = ptr2[0]; 415 416 tree_two.pt = tn2; 417 tree_two.sign = (char) (CV_SIGN( sn2 )); 418 tree_two.area = fabs( sn2 ); 419 tree_two.r1 = hn2 / an2; 420 tree_two.r2 = bn2 / an2; 421 tree_two.next_v1 = ptr2[1]; 422 tree_two.next_v2 = ptr2[2]; 423 424 CV_WRITE_SEQ_ELEM( tree_one, writer ); 425 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 426 427 if( s_c > sn2_c ) 428 { 429 if( ptr2[3] != NULL ) 430 ptr2[3]->prev_v = cur_adr; 431 if( ptr2[0] != NULL ) 432 ptr2[0]->prev_v = cur_adr; 433 ptr1[0] = cur_adr; 434 435 i_tree++; 436 437 CV_WRITE_SEQ_ELEM( tree_two, writer ); 438 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 439 440 if( ptr2[1] != NULL ) 441 ptr2[1]->prev_v = cur_adr; 442 if( ptr2[2] != NULL ) 443 ptr2[2]->prev_v = cur_adr; 444 ptr1[1] = cur_adr; 445 446 i_tree++; 447 448 pt1[0] = tp1; 449 pt1[1] = tn1; 450 } 451 else 452 { 453 CV_WRITE_SEQ_ELEM( tree_two, writer ); 454 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 455 456 if( ptr2[1] != NULL ) 457 ptr2[1]->prev_v = cur_adr; 458 if( ptr2[2] != NULL ) 459 ptr2[2]->prev_v = cur_adr; 460 ptr1[0] = cur_adr; 461 462 i_tree++; 463 464 CV_WRITE_SEQ_ELEM( tree_one, writer ); 465 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 466 467 if( ptr2[3] != NULL ) 468 ptr2[3]->prev_v = cur_adr; 469 if( ptr2[0] != NULL ) 470 ptr2[0]->prev_v = cur_adr; 471 ptr1[1] = cur_adr; 472 473 i_tree++; 474 475 pt1[0] = tn1; 476 pt1[1] = tp1; 477 } 478 } 479 else 480 { 481 tree_one.pt = tp1; 482 tree_one.sign = (char) (CV_SIGN( sp1 )); 483 tree_one.area = fabs( sp1 ); 484 tree_one.r1 = hp1 / ap1; 485 tree_one.r2 = bp1 / ap1; 486 tree_one.next_v1 = ptr2[2]; 487 tree_one.next_v2 = ptr2[3]; 488 489 tree_two.pt = tn1; 490 tree_two.sign = (char) (CV_SIGN( sn1 )); 491 tree_two.area = fabs( sn1 ); 492 tree_two.r1 = hn1 / an1; 493 tree_two.r2 = bn1 / an1; 494 tree_two.next_v1 = ptr2[0]; 495 tree_two.next_v2 = ptr2[1]; 496 497 CV_WRITE_SEQ_ELEM( tree_one, writer ); 498 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 499 500 if( sp1_c > sn1_c ) 501 { 502 if( ptr2[2] != NULL ) 503 ptr2[2]->prev_v = cur_adr; 504 if( ptr2[3] != NULL ) 505 ptr2[3]->prev_v = cur_adr; 506 ptr1[0] = cur_adr; 507 508 i_tree++; 509 510 CV_WRITE_SEQ_ELEM( tree_two, writer ); 511 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 512 513 if( ptr2[0] != NULL ) 514 ptr2[0]->prev_v = cur_adr; 515 if( ptr2[1] != NULL ) 516 ptr2[1]->prev_v = cur_adr; 517 ptr1[1] = cur_adr; 518 519 i_tree++; 520 521 pt1[0] = tn2; 522 pt1[1] = t; 523 } 524 else 525 { 526 CV_WRITE_SEQ_ELEM( tree_two, writer ); 527 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 528 529 if( ptr2[0] != NULL ) 530 ptr2[0]->prev_v = cur_adr; 531 if( ptr2[1] != NULL ) 532 ptr2[1]->prev_v = cur_adr; 533 ptr1[0] = cur_adr; 534 535 i_tree++; 536 537 CV_WRITE_SEQ_ELEM( tree_one, writer ); 538 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 539 540 if( ptr2[2] != NULL ) 541 ptr2[2]->prev_v = cur_adr; 542 if( ptr2[3] != NULL ) 543 ptr2[3]->prev_v = cur_adr; 544 ptr1[1] = cur_adr; 545 546 i_tree++; 547 548 pt1[0] = t; 549 pt1[1] = tn2; 550 551 } 552 } 553 554 /* form root */ 555 s = cvContourArea( contour ); 556 557 tree_root->pt = pt1[1]; 558 tree_root->sign = 0; 559 tree_root->area = fabs( s ); 560 tree_root->r1 = 0; 561 tree_root->r2 = 0; 562 tree_root->next_v1 = ptr1[0]; 563 tree_root->next_v2 = ptr1[1]; 564 tree_root->prev_v = NULL; 565 566 ptr1[0]->prev_v = (_CvTrianAttr *) tree_root; 567 ptr1[1]->prev_v = (_CvTrianAttr *) tree_root; 568 569 /* write binary tree root */ 570 /* CV_WRITE_SEQ_ELEM (tree_one, start_writer); */ 571 i_tree++; 572 /* create Sequence hearder */ 573 *((CvSeq **) tree) = cvEndWriteSeq( &writer ); 574 /* write points for the main segment into sequence header */ 575 (*tree)->p1 = pt1[0]; 576 577 M_END: 578 579 cvFree( &ptr_n ); 580 cvFree( &ptr_p ); 581 cvFree( &num_n ); 582 cvFree( &num_p ); 583 cvFree( &pt_n ); 584 cvFree( &pt_p ); 585 586 return status; 587 } 588 589 /****************************************************************************************\ 590 591 triangle attributes calculations 592 593 \****************************************************************************************/ 594 static CvStatus 595 icvCalcTriAttr( const CvSeq * contour, CvPoint t2, CvPoint t1, int n1, 596 CvPoint t3, int n3, double *s, double *s_c, 597 double *h, double *a, double *b ) 598 { 599 double x13, y13, x12, y12, l_base, nx, ny, qq; 600 double eps = 1.e-5; 601 602 x13 = t3.x - t1.x; 603 y13 = t3.y - t1.y; 604 x12 = t2.x - t1.x; 605 y12 = t2.y - t1.y; 606 qq = x13 * x13 + y13 * y13; 607 l_base = cvSqrt( (float) (qq) ); 608 if( l_base > eps ) 609 { 610 nx = y13 / l_base; 611 ny = -x13 / l_base; 612 613 *h = nx * x12 + ny * y12; 614 615 *s = (*h) * l_base / 2.; 616 617 *b = nx * y12 - ny * x12; 618 619 *a = l_base; 620 /* calculate interceptive area */ 621 *s_c = cvContourArea( contour, cvSlice(n1, n3+1)); 622 } 623 else 624 { 625 *h = 0; 626 *s = 0; 627 *s_c = 0; 628 *b = 0; 629 *a = 0; 630 } 631 632 return CV_OK; 633 } 634 635 /*F/////////////////////////////////////////////////////////////////////////////////////// 636 // Name: cvCreateContourTree 637 // Purpose: 638 // Create binary tree representation for the contour 639 // Context: 640 // Parameters: 641 // contour - pointer to input contour object. 642 // storage - pointer to the current storage block 643 // tree - output pointer to the binary tree representation 644 // threshold - threshold for the binary tree building 645 // 646 //F*/ 647 CV_IMPL CvContourTree* 648 cvCreateContourTree( const CvSeq* contour, CvMemStorage* storage, double threshold ) 649 { 650 CvContourTree* tree = 0; 651 652 CV_FUNCNAME( "cvCreateContourTree" ); 653 __BEGIN__; 654 655 IPPI_CALL( icvCreateContourTree( contour, storage, &tree, threshold )); 656 657 __CLEANUP__; 658 __END__; 659 660 return tree; 661 } 662 663 664 /*F/////////////////////////////////////////////////////////////////////////////////////// 665 // Name: icvContourFromContourTree 666 // Purpose: 667 // reconstracts contour from binary tree representation 668 // Context: 669 // Parameters: 670 // tree - pointer to the input binary tree representation 671 // storage - pointer to the current storage block 672 // contour - pointer to output contour object. 673 // criteria - criteria for the definition threshold value 674 // for the contour reconstracting (level or precision) 675 //F*/ 676 CV_IMPL CvSeq* 677 cvContourFromContourTree( const CvContourTree* tree, 678 CvMemStorage* storage, 679 CvTermCriteria criteria ) 680 { 681 CvSeq* contour = 0; 682 _CvTrianAttr **ptr_buf = 0; /* pointer to the pointer's buffer */ 683 int *level_buf = 0; 684 int i_buf; 685 686 int lpt; 687 double area_all; 688 double threshold; 689 int cur_level; 690 int level; 691 int seq_flags; 692 char log_iter, log_eps; 693 int out_hearder_size; 694 _CvTrianAttr *tree_one = 0, tree_root; /* current vertex */ 695 696 CvSeqReader reader; 697 CvSeqWriter writer; 698 699 CV_FUNCNAME("cvContourFromContourTree"); 700 701 __BEGIN__; 702 703 if( !tree ) 704 CV_ERROR( CV_StsNullPtr, "" ); 705 706 if( !CV_IS_SEQ_POLYGON_TREE( tree )) 707 CV_ERROR_FROM_STATUS( CV_BADFLAG_ERR ); 708 709 criteria = cvCheckTermCriteria( criteria, 0., 100 ); 710 711 lpt = tree->total; 712 ptr_buf = NULL; 713 level_buf = NULL; 714 i_buf = 0; 715 cur_level = 0; 716 log_iter = (char) (criteria.type == CV_TERMCRIT_ITER || 717 (criteria.type == CV_TERMCRIT_ITER + CV_TERMCRIT_EPS)); 718 log_eps = (char) (criteria.type == CV_TERMCRIT_EPS || 719 (criteria.type == CV_TERMCRIT_ITER + CV_TERMCRIT_EPS)); 720 721 cvStartReadSeq( (CvSeq *) tree, &reader, 0 ); 722 723 out_hearder_size = sizeof( CvContour ); 724 725 seq_flags = CV_SEQ_POLYGON; 726 cvStartWriteSeq( seq_flags, out_hearder_size, sizeof( CvPoint ), storage, &writer ); 727 728 ptr_buf = (_CvTrianAttr **) cvAlloc( lpt * sizeof( _CvTrianAttr * )); 729 if( ptr_buf == NULL ) 730 CV_ERROR_FROM_STATUS( CV_OUTOFMEM_ERR ); 731 if( log_iter ) 732 { 733 level_buf = (int *) cvAlloc( lpt * (sizeof( int ))); 734 735 if( level_buf == NULL ) 736 CV_ERROR_FROM_STATUS( CV_OUTOFMEM_ERR ); 737 } 738 739 memset( ptr_buf, 0, lpt * sizeof( _CvTrianAttr * )); 740 741 /* write the first tree root's point as a start point of the result contour */ 742 CV_WRITE_SEQ_ELEM( tree->p1, writer ); 743 /* write the second tree root"s point into buffer */ 744 745 /* read the root of the tree */ 746 CV_READ_SEQ_ELEM( tree_root, reader ); 747 748 tree_one = &tree_root; 749 area_all = tree_one->area; 750 751 if( log_eps ) 752 threshold = criteria.epsilon * area_all; 753 else 754 threshold = 10 * area_all; 755 756 if( log_iter ) 757 level = criteria.max_iter; 758 else 759 level = -1; 760 761 /* contour from binary tree constraction */ 762 while( i_buf >= 0 ) 763 { 764 if( tree_one != NULL && (cur_level <= level || tree_one->area >= threshold) ) 765 /* go to left sub tree for the vertex and save pointer to the right vertex */ 766 /* into the buffer */ 767 { 768 ptr_buf[i_buf] = tree_one; 769 if( log_iter ) 770 { 771 level_buf[i_buf] = cur_level; 772 cur_level++; 773 } 774 i_buf++; 775 tree_one = tree_one->next_v1; 776 } 777 else 778 { 779 i_buf--; 780 if( i_buf >= 0 ) 781 { 782 CvPoint pt = ptr_buf[i_buf]->pt; 783 CV_WRITE_SEQ_ELEM( pt, writer ); 784 tree_one = ptr_buf[i_buf]->next_v2; 785 if( log_iter ) 786 { 787 cur_level = level_buf[i_buf] + 1; 788 } 789 } 790 } 791 } 792 793 contour = cvEndWriteSeq( &writer ); 794 cvBoundingRect( contour, 1 ); 795 796 __CLEANUP__; 797 __END__; 798 799 cvFree( &level_buf ); 800 cvFree( &ptr_buf ); 801 802 return contour; 803 } 804 805
