modules/legacy/src/contourtree.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 "precomp.hpp"
  42
  43 #define _CV_BINTREE_LIST()                                          \
  44 struct _CvTrianAttr* prev_v;   /* pointer to the parent  element on the previous level of the tree  */    \
  45 struct _CvTrianAttr* next_v1;   /* pointer to the child  element on the next level of the tree  */        \
  46 struct _CvTrianAttr* next_v2;   /* pointer to the child  element on the next level of the tree  */
  47
  48 typedef struct _CvTrianAttr
  49 {
  50     CvPoint pt;    /* Coordinates x and y of the vertex  which don't lie on the base line LMIAT  */
  51     char sign;             /*  sign of the triangle   */
  52     double area;       /*   area of the triangle    */
  53     double r1;   /*  The ratio of the height of triangle to the base of the triangle  */
  54     double r2;  /*   The ratio of the projection of the left side of the triangle on the base to the base */
  55     _CV_BINTREE_LIST()    /* structure double list   */
  56 }
  57 _CvTrianAttr;
  58
  59 #define CV_MATCH_CHECK( status, cvFun )                                    \
  60   {                                                                        \
  61     status = cvFun;                                                        \
  62     if( status != CV_OK )                                                  \
  63      goto M_END;                                                           \
  64   }
  65
  66 static CvStatus
  67 icvCalcTriAttr( const CvSeq * contour, CvPoint t2, CvPoint t1, int n1,
  68                 CvPoint t3, int n3, double *s, double *s_c,
  69                 double *h, double *a, double *b );
  70
  71 /*F///////////////////////////////////////////////////////////////////////////////////////
  72 //    Name: icvCreateContourTree
  73 //    Purpose:
  74 //    Create binary tree representation for the contour
  75 //    Context:
  76 //    Parameters:
  77 //      contour - pointer to input contour object.
  78 //      storage - pointer to the current storage block
  79 //      tree   -  output pointer to the binary tree representation
  80 //      threshold - threshold for the binary tree building
  81 //
  82 //F*/
  83 static CvStatus
  84 icvCreateContourTree( const CvSeq * contour, CvMemStorage * storage,
  85                       CvContourTree ** tree, double threshold )
  86 {
  87     CvPoint *pt_p;              /*  pointer to previos points   */
  88     CvPoint *pt_n;              /*  pointer to next points      */
  89     CvPoint *pt1, *pt2;         /*  pointer to current points   */
  90
  91     CvPoint t, tp1, tp2, tp3, tn1, tn2, tn3;
  92     int lpt, flag, i, j, i_tree, j_1, j_3, i_buf;
  93     double s, sp1, sp2, sn1, sn2, s_c, sp1_c, sp2_c, sn1_c, sn2_c, h, hp1, hp2, hn1, hn2,
  94         a, ap1, ap2, an1, an2, b, bp1, bp2, bn1, bn2;
  95     double a_s_c, a_sp1_c;
  96
  97     _CvTrianAttr **ptr_p, **ptr_n, **ptr1, **ptr2;      /*  pointers to pointers of triangles  */
  98     _CvTrianAttr *cur_adr;
  99
 100     int *num_p, *num_n, *num1, *num2;   /*   numbers of input contour points   */
 101     int nm, nmp1, nmp2, nmp3, nmn1, nmn2, nmn3;
 102     int seq_flags = 1, i_end, prev_null, prev2_null;
 103     double koef = 1.5;
 104     double eps = 1.e-7;
 105     double e;
 106     CvStatus status;
 107     int hearder_size;
 108     _CvTrianAttr tree_one, tree_two, *tree_end, *tree_root;
 109
 110     CvSeqWriter writer;
 111
 112     assert( contour != NULL && contour->total >= 4 );
 113     status = CV_OK;
 114
 115     if( contour == NULL )
 116         return CV_NULLPTR_ERR;
 117     if( contour->total < 4 )
 118         return CV_BADSIZE_ERR;
 119
 120     if( !CV_IS_SEQ_POINT_SET( contour ))
 121         return CV_BADFLAG_ERR;
 122
 123
 124 /*   Convert Sequence to array    */
 125     lpt = contour->total;
 126     pt_p = pt_n = NULL;
 127     num_p = num_n = NULL;
 128     ptr_p = ptr_n = ptr1 = ptr2 = NULL;
 129     tree_end = NULL;
 130
 131     pt_p = (CvPoint *) cvAlloc( lpt * sizeof( CvPoint ));
 132     pt_n = (CvPoint *) cvAlloc( lpt * sizeof( CvPoint ));
 133
 134     num_p = (int *) cvAlloc( lpt * sizeof( int ));
 135     num_n = (int *) cvAlloc( lpt * sizeof( int ));
 136
 137     hearder_size = sizeof( CvContourTree );
 138     seq_flags = CV_SEQ_POLYGON_TREE;
 139     cvStartWriteSeq( seq_flags, hearder_size, sizeof( _CvTrianAttr ), storage, &writer );
 140
 141     ptr_p = (_CvTrianAttr **) cvAlloc( lpt * sizeof( _CvTrianAttr * ));
 142     ptr_n = (_CvTrianAttr **) cvAlloc( lpt * sizeof( _CvTrianAttr * ));
 143
 144     memset( ptr_p, 0, lpt * sizeof( _CvTrianAttr * ));
 145     memset( ptr_n, 0, lpt * sizeof( _CvTrianAttr * ));
 146
 147     if( pt_p == NULL || pt_n == NULL )
 148         return CV_OUTOFMEM_ERR;
 149     if( ptr_p == NULL || ptr_n == NULL )
 150         return CV_OUTOFMEM_ERR;
 151
 152 /*     write fild for the binary tree root   */
 153 /*  start_writer = writer;   */
 154
 155     tree_one.pt.x = tree_one.pt.y = 0;
 156     tree_one.sign = 0;
 157     tree_one.area = 0;
 158     tree_one.r1 = tree_one.r2 = 0;
 159     tree_one.next_v1 = tree_one.next_v2 = tree_one.prev_v = NULL;
 160
 161     CV_WRITE_SEQ_ELEM( tree_one, writer );
 162     tree_root = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 163
 164     if( cvCvtSeqToArray( contour, (char *) pt_p ) == (char *) contour )
 165         return CV_BADPOINT_ERR;
 166
 167     for( i = 0; i < lpt; i++ )
 168         num_p[i] = i;
 169
 170     i = lpt;
 171     flag = 0;
 172     i_tree = 0;
 173     e = 20.;                    /*  initial threshold value   */
 174     ptr1 = ptr_p;
 175     ptr2 = ptr_n;
 176     pt1 = pt_p;
 177     pt2 = pt_n;
 178     num1 = num_p;
 179     num2 = num_n;
 180 /*  binary tree constraction    */
 181     while( i > 4 )
 182     {
 183         if( flag == 0 )
 184         {
 185             ptr1 = ptr_p;
 186             ptr2 = ptr_n;
 187             pt1 = pt_p;
 188             pt2 = pt_n;
 189             num1 = num_p;
 190             num2 = num_n;
 191             flag = 1;
 192         }
 193         else
 194         {
 195             ptr1 = ptr_n;
 196             ptr2 = ptr_p;
 197             pt1 = pt_n;
 198             pt2 = pt_p;
 199             num1 = num_n;
 200             num2 = num_p;
 201             flag = 0;
 202         }
 203         t = pt1[0];
 204         nm = num1[0];
 205         tp1 = pt1[i - 1];
 206         nmp1 = num1[i - 1];
 207         tp2 = pt1[i - 2];
 208         nmp2 = num1[i - 2];
 209         tp3 = pt1[i - 3];
 210         nmp3 = num1[i - 3];
 211         tn1 = pt1[1];
 212         nmn1 = num1[1];
 213         tn2 = pt1[2];
 214         nmn2 = num1[2];
 215
 216         i_buf = 0;
 217         i_end = -1;
 218         CV_MATCH_CHECK( status,
 219                         icvCalcTriAttr( contour, t, tp1, nmp1, tn1, nmn1, &s, &s_c, &h, &a,
 220                                         &b ));
 221         CV_MATCH_CHECK( status,
 222                         icvCalcTriAttr( contour, tp1, tp2, nmp2, t, nm, &sp1, &sp1_c, &hp1,
 223                                         &ap1, &bp1 ));
 224         CV_MATCH_CHECK( status,
 225                         icvCalcTriAttr( contour, tp2, tp3, nmp3, tp1, nmp1, &sp2, &sp2_c, &hp2,
 226                                         &ap2, &bp2 ));
 227         CV_MATCH_CHECK( status,
 228                         icvCalcTriAttr( contour, tn1, t, nm, tn2, nmn2, &sn1, &sn1_c, &hn1,
 229                                         &an1, &bn1 ));
 230
 231
 232         j_3 = 3;
 233         prev_null = prev2_null = 0;
 234         for( j = 0; j < i; j++ )
 235         {
 236             tn3 = pt1[j_3];
 237             nmn3 = num1[j_3];
 238             if( j == 0 )
 239                 j_1 = i - 1;
 240             else
 241                 j_1 = j - 1;
 242
 243             CV_MATCH_CHECK( status, icvCalcTriAttr( contour, tn2, tn1, nmn1, tn3, nmn3,
 244                                                     &sn2, &sn2_c, &hn2, &an2, &bn2 ));
 245
 246             if( (s_c < sp1_c && s_c < sp2_c && s_c <= sn1_c && s_c <= sn2_c && s_c < e) ||
 247                 (((s_c == sp1_c && s_c <= sp2_c) || (s_c == sp2_c && s_c <= sp1_c)) &&
 248                 s_c <= sn1_c && s_c <= sn2_c && s_c < e && j > 1 && prev2_null == 0) ||
 249                 (s_c < eps && j > 0 && prev_null == 0) )
 250             {
 251                 prev_null = prev2_null = 1;
 252                 if( s_c < threshold )
 253                 {
 254                     if( ptr1[j_1] == NULL && ptr1[j] == NULL )
 255                     {
 256                         if( i_buf > 0 )
 257                             ptr2[i_buf - 1] = NULL;
 258                         else
 259                             i_end = 0;
 260                     }
 261                     else
 262                     {
 263 /*   form next vertex  */
 264                         tree_one.pt = t;
 265                         tree_one.sign = (char) (CV_SIGN( s ));
 266                         tree_one.r1 = h / a;
 267                         tree_one.r2 = b / a;
 268                         tree_one.area = fabs( s );
 269                         tree_one.next_v1 = ptr1[j_1];
 270                         tree_one.next_v2 = ptr1[j];
 271
 272                         CV_WRITE_SEQ_ELEM( tree_one, writer );
 273                         cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 274
 275                         if( ptr1[j_1] != NULL )
 276                             ptr1[j_1]->prev_v = cur_adr;
 277                         if( ptr1[j] != NULL )
 278                             ptr1[j]->prev_v = cur_adr;
 279
 280                         if( i_buf > 0 )
 281                             ptr2[i_buf - 1] = cur_adr;
 282                         else
 283                         {
 284                             tree_end = (_CvTrianAttr *) writer.ptr;
 285                             i_end = 1;
 286                         }
 287                         i_tree++;
 288                     }
 289                 }
 290                 else
 291 /*   form next vertex    */
 292                 {
 293                     tree_one.pt = t;
 294                     tree_one.sign = (char) (CV_SIGN( s ));
 295                     tree_one.area = fabs( s );
 296                     tree_one.r1 = h / a;
 297                     tree_one.r2 = b / a;
 298                     tree_one.next_v1 = ptr1[j_1];
 299                     tree_one.next_v2 = ptr1[j];
 300
 301                     CV_WRITE_SEQ_ELEM( tree_one, writer );
 302                     cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 303
 304                     if( ptr1[j_1] != NULL )
 305                         ptr1[j_1]->prev_v = cur_adr;
 306                     if( ptr1[j] != NULL )
 307                         ptr1[j]->prev_v = cur_adr;
 308
 309                     if( i_buf > 0 )
 310                         ptr2[i_buf - 1] = cur_adr;
 311                     else
 312                     {
 313                         tree_end = cur_adr;
 314                         i_end = 1;
 315                     }
 316                     i_tree++;
 317                 }
 318             }
 319             else
 320 /*   the current triangle is'not LMIAT    */
 321             {
 322                 prev_null = 0;
 323                 switch (prev2_null)
 324                 {
 325                 case 0:
 326                     break;
 327                 case 1:
 328                     {
 329                         prev2_null = 2;
 330                         break;
 331                     }
 332                 case 2:
 333                     {
 334                         prev2_null = 0;
 335                         break;
 336                     }
 337                 }
 338                 if( j != i - 1 || i_end == -1 )
 339                     ptr2[i_buf] = ptr1[j];
 340                 else if( i_end == 0 )
 341                     ptr2[i_buf] = NULL;
 342                 else
 343                     ptr2[i_buf] = tree_end;
 344                 pt2[i_buf] = t;
 345                 num2[i_buf] = num1[j];
 346                 i_buf++;
 347             }
 348 /*    go to next vertex    */
 349             tp3 = tp2;
 350             tp2 = tp1;
 351             tp1 = t;
 352             t = tn1;
 353             tn1 = tn2;
 354             tn2 = tn3;
 355             nmp3 = nmp2;
 356             nmp2 = nmp1;
 357             nmp1 = nm;
 358             nm = nmn1;
 359             nmn1 = nmn2;
 360             nmn2 = nmn3;
 361
 362             sp2 = sp1;
 363             sp1 = s;
 364             s = sn1;
 365             sn1 = sn2;
 366             sp2_c = sp1_c;
 367             sp1_c = s_c;
 368             s_c = sn1_c;
 369             sn1_c = sn2_c;
 370
 371             ap2 = ap1;
 372             ap1 = a;
 373             a = an1;
 374             an1 = an2;
 375             bp2 = bp1;
 376             bp1 = b;
 377             b = bn1;
 378             bn1 = bn2;
 379             hp2 = hp1;
 380             hp1 = h;
 381             h = hn1;
 382             hn1 = hn2;
 383             j_3++;
 384             if( j_3 >= i )
 385                 j_3 = 0;
 386         }
 387
 388         i = i_buf;
 389         e = e * koef;
 390     }
 391
 392 /*  constract tree root  */
 393     if( i != 4 )
 394         return CV_BADFACTOR_ERR;
 395
 396     t = pt2[0];
 397     tn1 = pt2[1];
 398     tn2 = pt2[2];
 399     tp1 = pt2[3];
 400     nm = num2[0];
 401     nmn1 = num2[1];
 402     nmn2 = num2[2];
 403     nmp1 = num2[3];
 404 /*   first pair of the triangles   */
 405     CV_MATCH_CHECK( status,
 406                     icvCalcTriAttr( contour, t, tp1, nmp1, tn1, nmn1, &s, &s_c, &h, &a, &b ));
 407     CV_MATCH_CHECK( status,
 408                     icvCalcTriAttr( contour, tn2, tn1, nmn1, tp1, nmp1, &sn2, &sn2_c, &hn2,
 409                                     &an2, &bn2 ));
 410 /*   second pair of the triangles   */
 411     CV_MATCH_CHECK( status,
 412                     icvCalcTriAttr( contour, tn1, t, nm, tn2, nmn2, &sn1, &sn1_c, &hn1, &an1,
 413                                     &bn1 ));
 414     CV_MATCH_CHECK( status,
 415                     icvCalcTriAttr( contour, tp1, tn2, nmn2, t, nm, &sp1, &sp1_c, &hp1, &ap1,
 416                                     &bp1 ));
 417
 418     a_s_c = fabs( s_c - sn2_c );
 419     a_sp1_c = fabs( sp1_c - sn1_c );
 420
 421     if( a_s_c > a_sp1_c )
 422 /*   form child vertexs for the root     */
 423     {
 424         tree_one.pt = t;
 425         tree_one.sign = (char) (CV_SIGN( s ));
 426         tree_one.area = fabs( s );
 427         tree_one.r1 = h / a;
 428         tree_one.r2 = b / a;
 429         tree_one.next_v1 = ptr2[3];
 430         tree_one.next_v2 = ptr2[0];
 431
 432         tree_two.pt = tn2;
 433         tree_two.sign = (char) (CV_SIGN( sn2 ));
 434         tree_two.area = fabs( sn2 );
 435         tree_two.r1 = hn2 / an2;
 436         tree_two.r2 = bn2 / an2;
 437         tree_two.next_v1 = ptr2[1];
 438         tree_two.next_v2 = ptr2[2];
 439
 440         CV_WRITE_SEQ_ELEM( tree_one, writer );
 441         cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 442
 443         if( s_c > sn2_c )
 444         {
 445             if( ptr2[3] != NULL )
 446                 ptr2[3]->prev_v = cur_adr;
 447             if( ptr2[0] != NULL )
 448                 ptr2[0]->prev_v = cur_adr;
 449             ptr1[0] = cur_adr;
 450
 451             i_tree++;
 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[1] = cur_adr;
 461
 462             i_tree++;
 463
 464             pt1[0] = tp1;
 465             pt1[1] = tn1;
 466         }
 467         else
 468         {
 469             CV_WRITE_SEQ_ELEM( tree_two, writer );
 470             cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 471
 472             if( ptr2[1] != NULL )
 473                 ptr2[1]->prev_v = cur_adr;
 474             if( ptr2[2] != NULL )
 475                 ptr2[2]->prev_v = cur_adr;
 476             ptr1[0] = cur_adr;
 477
 478             i_tree++;
 479
 480             CV_WRITE_SEQ_ELEM( tree_one, writer );
 481             cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 482
 483             if( ptr2[3] != NULL )
 484                 ptr2[3]->prev_v = cur_adr;
 485             if( ptr2[0] != NULL )
 486                 ptr2[0]->prev_v = cur_adr;
 487             ptr1[1] = cur_adr;
 488
 489             i_tree++;
 490
 491             pt1[0] = tn1;
 492             pt1[1] = tp1;
 493         }
 494     }
 495     else
 496     {
 497         tree_one.pt = tp1;
 498         tree_one.sign = (char) (CV_SIGN( sp1 ));
 499         tree_one.area = fabs( sp1 );
 500         tree_one.r1 = hp1 / ap1;
 501         tree_one.r2 = bp1 / ap1;
 502         tree_one.next_v1 = ptr2[2];
 503         tree_one.next_v2 = ptr2[3];
 504
 505         tree_two.pt = tn1;
 506         tree_two.sign = (char) (CV_SIGN( sn1 ));
 507         tree_two.area = fabs( sn1 );
 508         tree_two.r1 = hn1 / an1;
 509         tree_two.r2 = bn1 / an1;
 510         tree_two.next_v1 = ptr2[0];
 511         tree_two.next_v2 = ptr2[1];
 512
 513         CV_WRITE_SEQ_ELEM( tree_one, writer );
 514         cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 515
 516         if( sp1_c > sn1_c )
 517         {
 518             if( ptr2[2] != NULL )
 519                 ptr2[2]->prev_v = cur_adr;
 520             if( ptr2[3] != NULL )
 521                 ptr2[3]->prev_v = cur_adr;
 522             ptr1[0] = cur_adr;
 523
 524             i_tree++;
 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[1] = cur_adr;
 534
 535             i_tree++;
 536
 537             pt1[0] = tn2;
 538             pt1[1] = t;
 539         }
 540         else
 541         {
 542             CV_WRITE_SEQ_ELEM( tree_two, writer );
 543             cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 544
 545             if( ptr2[0] != NULL )
 546                 ptr2[0]->prev_v = cur_adr;
 547             if( ptr2[1] != NULL )
 548                 ptr2[1]->prev_v = cur_adr;
 549             ptr1[0] = cur_adr;
 550
 551             i_tree++;
 552
 553             CV_WRITE_SEQ_ELEM( tree_one, writer );
 554             cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 555
 556             if( ptr2[2] != NULL )
 557                 ptr2[2]->prev_v = cur_adr;
 558             if( ptr2[3] != NULL )
 559                 ptr2[3]->prev_v = cur_adr;
 560             ptr1[1] = cur_adr;
 561
 562             i_tree++;
 563
 564             pt1[0] = t;
 565             pt1[1] = tn2;
 566
 567         }
 568     }
 569
 570 /*    form root   */
 571     s = cvContourArea( contour );
 572
 573     tree_root->pt = pt1[1];
 574     tree_root->sign = 0;
 575     tree_root->area = fabs( s );
 576     tree_root->r1 = 0;
 577     tree_root->r2 = 0;
 578     tree_root->next_v1 = ptr1[0];
 579     tree_root->next_v2 = ptr1[1];
 580     tree_root->prev_v = NULL;
 581
 582     ptr1[0]->prev_v = (_CvTrianAttr *) tree_root;
 583     ptr1[1]->prev_v = (_CvTrianAttr *) tree_root;
 584
 585 /*     write binary tree root   */
 586 /*    CV_WRITE_SEQ_ELEM (tree_one, start_writer);   */
 587     i_tree++;
 588 /*  create Sequence hearder     */
 589     *tree = (CvContourTree*)cvEndWriteSeq( &writer );
 590 /*   write points for the main segment into sequence header   */
 591     (*tree)->p1 = pt1[0];
 592
 593   M_END:
 594
 595     cvFree( &ptr_n );
 596     cvFree( &ptr_p );
 597     cvFree( &num_n );
 598     cvFree( &num_p );
 599     cvFree( &pt_n );
 600     cvFree( &pt_p );
 601
 602     return status;
 603 }
 604
 605 /****************************************************************************************\
 606
 607  triangle attributes calculations
 608
 609 \****************************************************************************************/
 610 static CvStatus
 611 icvCalcTriAttr( const CvSeq * contour, CvPoint t2, CvPoint t1, int n1,
 612                 CvPoint t3, int n3, double *s, double *s_c,
 613                 double *h, double *a, double *b )
 614 {
 615     double x13, y13, x12, y12, l_base, nx, ny, qq;
 616     double eps = 1.e-5;
 617
 618     x13 = t3.x - t1.x;
 619     y13 = t3.y - t1.y;
 620     x12 = t2.x - t1.x;
 621     y12 = t2.y - t1.y;
 622     qq = x13 * x13 + y13 * y13;
 623     l_base = cvSqrt( (float) (qq) );
 624     if( l_base > eps )
 625     {
 626         nx = y13 / l_base;
 627         ny = -x13 / l_base;
 628
 629         *h = nx * x12 + ny * y12;
 630
 631         *s = (*h) * l_base / 2.;
 632
 633         *b = nx * y12 - ny * x12;
 634
 635         *a = l_base;
 636 /*   calculate interceptive area   */
 637         *s_c = cvContourArea( contour, cvSlice(n1, n3+1));
 638     }
 639     else
 640     {
 641         *h = 0;
 642         *s = 0;
 643         *s_c = 0;
 644         *b = 0;
 645         *a = 0;
 646     }
 647
 648     return CV_OK;
 649 }
 650
 651 /*F///////////////////////////////////////////////////////////////////////////////////////
 652 //    Name: cvCreateContourTree
 653 //    Purpose:
 654 //    Create binary tree representation for the contour
 655 //    Context:
 656 //    Parameters:
 657 //      contour - pointer to input contour object.
 658 //      storage - pointer to the current storage block
 659 //      tree   -  output pointer to the binary tree representation
 660 //      threshold - threshold for the binary tree building
 661 //
 662 //F*/
 663 CV_IMPL CvContourTree*
 664 cvCreateContourTree( const CvSeq* contour, CvMemStorage* storage, double threshold )
 665 {
 666     CvContourTree* tree = 0;
 667
 668     IPPI_CALL( icvCreateContourTree( contour, storage, &tree, threshold ));
 669
 670     return tree;
 671 }
 672
 673
 674 /*F///////////////////////////////////////////////////////////////////////////////////////
 675 //    Name: icvContourFromContourTree
 676 //    Purpose:
 677 //    reconstracts contour from binary tree representation
 678 //    Context:
 679 //    Parameters:
 680 //      tree   -  pointer to the input binary tree representation
 681 //      storage - pointer to the current storage block
 682 //      contour - pointer to output contour object.
 683 //      criteria - criteria for the definition threshold value
 684 //                 for the contour reconstracting (level or precision)
 685 //F*/
 686 CV_IMPL CvSeq*
 687 cvContourFromContourTree( const CvContourTree*  tree,
 688                           CvMemStorage*  storage,
 689                           CvTermCriteria  criteria )
 690 {
 691     CvSeq* contour = 0;
 692     cv::AutoBuffer<_CvTrianAttr*> ptr_buf;     /*  pointer to the pointer's buffer  */
 693     cv::AutoBuffer<int> level_buf;
 694     int i_buf;
 695
 696     int lpt;
 697     double area_all;
 698     double threshold;
 699     int cur_level;
 700     int level;
 701     int seq_flags;
 702     char log_iter, log_eps;
 703     int out_hearder_size;
 704     _CvTrianAttr *tree_one = 0, tree_root;  /*  current vertex  */
 705
 706     CvSeqReader reader;
 707     CvSeqWriter writer;
 708
 709     if( !tree )
 710         CV_Error( CV_StsNullPtr, "" );
 711
 712     if( !CV_IS_SEQ_POLYGON_TREE( tree ))
 713         CV_Error( CV_StsBadArg, "" );
 714
 715     criteria = cvCheckTermCriteria( criteria, 0., 100 );
 716
 717     lpt = tree->total;
 718     i_buf = 0;
 719     cur_level = 0;
 720     log_iter = (char) (criteria.type == CV_TERMCRIT_ITER ||
 721                        (criteria.type == CV_TERMCRIT_ITER + CV_TERMCRIT_EPS));
 722     log_eps = (char) (criteria.type == CV_TERMCRIT_EPS ||
 723                       (criteria.type == CV_TERMCRIT_ITER + CV_TERMCRIT_EPS));
 724
 725     cvStartReadSeq( (CvSeq *) tree, &reader, 0 );
 726
 727     out_hearder_size = sizeof( CvContour );
 728
 729     seq_flags = CV_SEQ_POLYGON;
 730     cvStartWriteSeq( seq_flags, out_hearder_size, sizeof( CvPoint ), storage, &writer );
 731
 732     ptr_buf.allocate(lpt);
 733     if( log_iter )
 734         level_buf.allocate(lpt);
 735
 736     memset( ptr_buf, 0, lpt * sizeof( _CvTrianAttr * ));
 737
 738 /*     write the first tree root's point as a start point of the result contour  */
 739     CV_WRITE_SEQ_ELEM( tree->p1, writer );
 740 /*     write the second tree root"s point into buffer    */
 741
 742 /*     read the root of the tree   */
 743     CV_READ_SEQ_ELEM( tree_root, reader );
 744
 745     tree_one = &tree_root;
 746     area_all = tree_one->area;
 747
 748     if( log_eps )
 749         threshold = criteria.epsilon * area_all;
 750     else
 751         threshold = 10 * area_all;
 752
 753     if( log_iter )
 754         level = criteria.max_iter;
 755     else
 756         level = -1;
 757
 758 /*  contour from binary tree constraction    */
 759     while( i_buf >= 0 )
 760     {
 761         if( tree_one != NULL && (cur_level <= level || tree_one->area >= threshold) )
 762 /*   go to left sub tree for the vertex and save pointer to the right vertex   */
 763 /*   into the buffer     */
 764         {
 765             ptr_buf[i_buf] = tree_one;
 766             if( log_iter )
 767             {
 768                 level_buf[i_buf] = cur_level;
 769                 cur_level++;
 770             }
 771             i_buf++;
 772             tree_one = tree_one->next_v1;
 773         }
 774         else
 775         {
 776             i_buf--;
 777             if( i_buf >= 0 )
 778             {
 779                 CvPoint pt = ptr_buf[i_buf]->pt;
 780                 CV_WRITE_SEQ_ELEM( pt, writer );
 781                 tree_one = ptr_buf[i_buf]->next_v2;
 782                 if( log_iter )
 783                 {
 784                     cur_level = level_buf[i_buf] + 1;
 785                 }
 786             }
 787         }
 788     }
 789
 790     contour = cvEndWriteSeq( &writer );
 791     cvBoundingRect( contour, 1 );
 792
 793     return contour;
 794 }
 795
 796 /*F///////////////////////////////////////////////////////////////////////////////////////
 797 //    Name: icvMatchContourTrees
 798 //    Purpose:
 799 //      Calculates matching of the two contour trees
 800 //    Context:
 801 //    Parameters:
 802 //      tree1 - pointer to the first input contour tree object.
 803 //      tree2 - pointer to the second input contour tree object.
 804 //      method - method for the matching calculation
 805 //      (now CV_CONTOUR_TREES_MATCH_I1 only  )
 806 //      threshold - threshold for the contour trees matching
 807 //      result - output calculated measure
 808 //F*/
 809 CV_IMPL  double
 810 cvMatchContourTrees( const CvContourTree* tree1, const CvContourTree* tree2,
 811                      int method, double threshold )
 812 {
 813     cv::AutoBuffer<_CvTrianAttr*> buf;
 814     _CvTrianAttr **ptr_p1 = 0, **ptr_p2 = 0;    /*pointers to the pointer's buffer */
 815     _CvTrianAttr **ptr_n1 = 0, **ptr_n2 = 0;    /*pointers to the pointer's buffer */
 816     _CvTrianAttr **ptr11, **ptr12, **ptr21, **ptr22;
 817
 818     int lpt1, lpt2, lpt, flag, flag_n, i, j, ibuf, ibuf1;
 819     double match_v, d12, area1, area2, r11, r12, r21, r22, w1, w2;
 820     double eps = 1.e-5;
 821     char s1, s2;
 822     _CvTrianAttr tree_1, tree_2;        /*current vertex 1 and 2 tree */
 823     CvSeqReader reader1, reader2;
 824
 825     if( !tree1 || !tree2 )
 826         CV_Error( CV_StsNullPtr, "" );
 827
 828     if( method != CV_CONTOUR_TREES_MATCH_I1 )
 829         CV_Error( CV_StsBadArg, "Unknown/unsupported comparison method" );
 830
 831     if( !CV_IS_SEQ_POLYGON_TREE( tree1 ))
 832         CV_Error( CV_StsBadArg, "The first argument is not a valid contour tree" );
 833
 834     if( !CV_IS_SEQ_POLYGON_TREE( tree2 ))
 835         CV_Error( CV_StsBadArg, "The second argument is not a valid contour tree" );
 836
 837     lpt1 = tree1->total;
 838     lpt2 = tree2->total;
 839     lpt = lpt1 > lpt2 ? lpt1 : lpt2;
 840
 841     ptr_p1 = ptr_n1 = ptr_p2 = ptr_n2 = NULL;
 842     buf.allocate(lpt*4);
 843     ptr_p1 = buf;
 844     ptr_p2 = ptr_p1 + lpt;
 845     ptr_n1 = ptr_p2 + lpt;
 846     ptr_n2 = ptr_n1 + lpt;
 847
 848     cvStartReadSeq( (CvSeq *) tree1, &reader1, 0 );
 849     cvStartReadSeq( (CvSeq *) tree2, &reader2, 0 );
 850
 851 /*read the root of the first and second tree*/
 852     CV_READ_SEQ_ELEM( tree_1, reader1 );
 853     CV_READ_SEQ_ELEM( tree_2, reader2 );
 854
 855 /*write to buffer pointers to root's childs vertexs*/
 856     ptr_p1[0] = tree_1.next_v1;
 857     ptr_p1[1] = tree_1.next_v2;
 858     ptr_p2[0] = tree_2.next_v1;
 859     ptr_p2[1] = tree_2.next_v2;
 860     i = 2;
 861     match_v = 0.;
 862     area1 = tree_1.area;
 863     area2 = tree_2.area;
 864
 865     if( area1 < eps || area2 < eps || lpt < 4 )
 866         CV_Error( CV_StsBadSize, "" );
 867
 868     r11 = r12 = r21 = r22 = w1 = w2 = d12 = 0;
 869     flag = 0;
 870     s1 = s2 = 0;
 871     do
 872     {
 873         if( flag == 0 )
 874         {
 875             ptr11 = ptr_p1;
 876             ptr12 = ptr_n1;
 877             ptr21 = ptr_p2;
 878             ptr22 = ptr_n2;
 879             flag = 1;
 880         }
 881         else
 882         {
 883             ptr11 = ptr_n1;
 884             ptr12 = ptr_p1;
 885             ptr21 = ptr_n2;
 886             ptr22 = ptr_p2;
 887             flag = 0;
 888         }
 889         ibuf = 0;
 890         for( j = 0; j < i; j++ )
 891         {
 892             flag_n = 0;
 893             if( ptr11[j] != NULL )
 894             {
 895                 r11 = ptr11[j]->r1;
 896                 r12 = ptr11[j]->r2;
 897                 flag_n = 1;
 898                 w1 = ptr11[j]->area / area1;
 899                 s1 = ptr11[j]->sign;
 900             }
 901             else
 902             {
 903                 r11 = r21 = 0;
 904             }
 905             if( ptr21[j] != NULL )
 906             {
 907                 r21 = ptr21[j]->r1;
 908                 r22 = ptr21[j]->r2;
 909                 flag_n = 1;
 910                 w2 = ptr21[j]->area / area2;
 911                 s2 = ptr21[j]->sign;
 912             }
 913             else
 914             {
 915                 r21 = r22 = 0;
 916             }
 917             if( flag_n != 0 )
 918 /* calculate node distance */
 919             {
 920                 switch (method)
 921                 {
 922                 case 1:
 923                     {
 924                         double t0, t1;
 925                         if( s1 != s2 )
 926                         {
 927                             t0 = fabs( r11 * w1 + r21 * w2 );
 928                             t1 = fabs( r12 * w1 + r22 * w2 );
 929                         }
 930                         else
 931                         {
 932                             t0 = fabs( r11 * w1 - r21 * w2 );
 933                             t1 = fabs( r12 * w1 - r22 * w2 );
 934                         }
 935                         d12 = t0 + t1;
 936                         break;
 937                     }
 938                 }
 939                 match_v += d12;
 940                 ibuf1 = ibuf + 1;
 941 /*write to buffer the pointer to child vertexes*/
 942                 if( ptr11[j] != NULL )
 943                 {
 944                     ptr12[ibuf] = ptr11[j]->next_v1;
 945                     ptr12[ibuf1] = ptr11[j]->next_v2;
 946                 }
 947                 else
 948                 {
 949                     ptr12[ibuf] = NULL;
 950                     ptr12[ibuf1] = NULL;
 951                 }
 952                 if( ptr21[j] != NULL )
 953                 {
 954                     ptr22[ibuf] = ptr21[j]->next_v1;
 955                     ptr22[ibuf1] = ptr21[j]->next_v2;
 956                 }
 957                 else
 958                 {
 959                     ptr22[ibuf] = NULL;
 960                     ptr22[ibuf1] = NULL;
 961                 }
 962                 ibuf += 2;
 963             }
 964         }
 965         i = ibuf;
 966     }
 967     while( i > 0 && match_v < threshold );
 968
 969     return match_v;
 970 }