1 /*M///////////////////////////////////////////////////////////////////////////////////////
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
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.
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
14 // Third party copyrights are property of their respective owners.
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
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.
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.
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.
41 #include "precomp.hpp"
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 */
48 typedef struct _CvTrianAttr
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 */
59 #define CV_MATCH_CHECK( status, cvFun ) \
62 if( status != CV_OK ) \
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 );
71 /*F///////////////////////////////////////////////////////////////////////////////////////
72 // Name: icvCreateContourTree
74 // Create binary tree representation for the contour
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
84 icvCreateContourTree( const CvSeq * contour, CvMemStorage * storage,
85 CvContourTree ** tree, double threshold )
87 CvPoint *pt_p; /* pointer to previos points */
88 CvPoint *pt_n; /* pointer to next points */
89 CvPoint *pt1, *pt2; /* pointer to current points */
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;
97 _CvTrianAttr **ptr_p, **ptr_n, **ptr1, **ptr2; /* pointers to pointers of triangles */
98 _CvTrianAttr *cur_adr;
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;
108 _CvTrianAttr tree_one, tree_two, *tree_end, *tree_root;
112 assert( contour != NULL && contour->total >= 4 );
115 if( contour == NULL )
116 return CV_NULLPTR_ERR;
117 if( contour->total < 4 )
118 return CV_BADSIZE_ERR;
120 if( !CV_IS_SEQ_POINT_SET( contour ))
121 return CV_BADFLAG_ERR;
124 /* Convert Sequence to array */
125 lpt = contour->total;
127 num_p = num_n = NULL;
128 ptr_p = ptr_n = ptr1 = ptr2 = NULL;
131 pt_p = (CvPoint *) cvAlloc( lpt * sizeof( CvPoint ));
132 pt_n = (CvPoint *) cvAlloc( lpt * sizeof( CvPoint ));
134 num_p = (int *) cvAlloc( lpt * sizeof( int ));
135 num_n = (int *) cvAlloc( lpt * sizeof( int ));
137 hearder_size = sizeof( CvContourTree );
138 seq_flags = CV_SEQ_POLYGON_TREE;
139 cvStartWriteSeq( seq_flags, hearder_size, sizeof( _CvTrianAttr ), storage, &writer );
141 ptr_p = (_CvTrianAttr **) cvAlloc( lpt * sizeof( _CvTrianAttr * ));
142 ptr_n = (_CvTrianAttr **) cvAlloc( lpt * sizeof( _CvTrianAttr * ));
144 memset( ptr_p, 0, lpt * sizeof( _CvTrianAttr * ));
145 memset( ptr_n, 0, lpt * sizeof( _CvTrianAttr * ));
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;
152 /* write fild for the binary tree root */
153 /* start_writer = writer; */
155 tree_one.pt.x = tree_one.pt.y = 0;
158 tree_one.r1 = tree_one.r2 = 0;
159 tree_one.next_v1 = tree_one.next_v2 = tree_one.prev_v = NULL;
161 CV_WRITE_SEQ_ELEM( tree_one, writer );
162 tree_root = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
164 if( cvCvtSeqToArray( contour, (char *) pt_p ) == (char *) contour )
165 return CV_BADPOINT_ERR;
167 for( i = 0; i < lpt; i++ )
173 e = 20.; /* initial threshold value */
180 /* binary tree constraction */
218 CV_MATCH_CHECK( status,
219 icvCalcTriAttr( contour, t, tp1, nmp1, tn1, nmn1, &s, &s_c, &h, &a,
221 CV_MATCH_CHECK( status,
222 icvCalcTriAttr( contour, tp1, tp2, nmp2, t, nm, &sp1, &sp1_c, &hp1,
224 CV_MATCH_CHECK( status,
225 icvCalcTriAttr( contour, tp2, tp3, nmp3, tp1, nmp1, &sp2, &sp2_c, &hp2,
227 CV_MATCH_CHECK( status,
228 icvCalcTriAttr( contour, tn1, t, nm, tn2, nmn2, &sn1, &sn1_c, &hn1,
233 prev_null = prev2_null = 0;
234 for( j = 0; j < i; j++ )
243 CV_MATCH_CHECK( status, icvCalcTriAttr( contour, tn2, tn1, nmn1, tn3, nmn3,
244 &sn2, &sn2_c, &hn2, &an2, &bn2 ));
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) )
251 prev_null = prev2_null = 1;
252 if( s_c < threshold )
254 if( ptr1[j_1] == NULL && ptr1[j] == NULL )
257 ptr2[i_buf - 1] = NULL;
263 /* form next vertex */
265 tree_one.sign = (char) (CV_SIGN( s ));
268 tree_one.area = fabs( s );
269 tree_one.next_v1 = ptr1[j_1];
270 tree_one.next_v2 = ptr1[j];
272 CV_WRITE_SEQ_ELEM( tree_one, writer );
273 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
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;
281 ptr2[i_buf - 1] = cur_adr;
284 tree_end = (_CvTrianAttr *) writer.ptr;
291 /* form next vertex */
294 tree_one.sign = (char) (CV_SIGN( s ));
295 tree_one.area = fabs( s );
298 tree_one.next_v1 = ptr1[j_1];
299 tree_one.next_v2 = ptr1[j];
301 CV_WRITE_SEQ_ELEM( tree_one, writer );
302 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
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;
310 ptr2[i_buf - 1] = cur_adr;
320 /* the current triangle is'not LMIAT */
338 if( j != i - 1 || i_end == -1 )
339 ptr2[i_buf] = ptr1[j];
340 else if( i_end == 0 )
343 ptr2[i_buf] = tree_end;
345 num2[i_buf] = num1[j];
348 /* go to next vertex */
392 /* constract tree root */
394 return CV_BADFACTOR_ERR;
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,
410 /* second pair of the triangles */
411 CV_MATCH_CHECK( status,
412 icvCalcTriAttr( contour, tn1, t, nm, tn2, nmn2, &sn1, &sn1_c, &hn1, &an1,
414 CV_MATCH_CHECK( status,
415 icvCalcTriAttr( contour, tp1, tn2, nmn2, t, nm, &sp1, &sp1_c, &hp1, &ap1,
418 a_s_c = fabs( s_c - sn2_c );
419 a_sp1_c = fabs( sp1_c - sn1_c );
421 if( a_s_c > a_sp1_c )
422 /* form child vertexs for the root */
425 tree_one.sign = (char) (CV_SIGN( s ));
426 tree_one.area = fabs( s );
429 tree_one.next_v1 = ptr2[3];
430 tree_one.next_v2 = ptr2[0];
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];
440 CV_WRITE_SEQ_ELEM( tree_one, writer );
441 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
445 if( ptr2[3] != NULL )
446 ptr2[3]->prev_v = cur_adr;
447 if( ptr2[0] != NULL )
448 ptr2[0]->prev_v = cur_adr;
453 CV_WRITE_SEQ_ELEM( tree_two, writer );
454 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
456 if( ptr2[1] != NULL )
457 ptr2[1]->prev_v = cur_adr;
458 if( ptr2[2] != NULL )
459 ptr2[2]->prev_v = cur_adr;
469 CV_WRITE_SEQ_ELEM( tree_two, writer );
470 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
472 if( ptr2[1] != NULL )
473 ptr2[1]->prev_v = cur_adr;
474 if( ptr2[2] != NULL )
475 ptr2[2]->prev_v = cur_adr;
480 CV_WRITE_SEQ_ELEM( tree_one, writer );
481 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
483 if( ptr2[3] != NULL )
484 ptr2[3]->prev_v = cur_adr;
485 if( ptr2[0] != NULL )
486 ptr2[0]->prev_v = cur_adr;
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];
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];
513 CV_WRITE_SEQ_ELEM( tree_one, writer );
514 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
518 if( ptr2[2] != NULL )
519 ptr2[2]->prev_v = cur_adr;
520 if( ptr2[3] != NULL )
521 ptr2[3]->prev_v = cur_adr;
526 CV_WRITE_SEQ_ELEM( tree_two, writer );
527 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
529 if( ptr2[0] != NULL )
530 ptr2[0]->prev_v = cur_adr;
531 if( ptr2[1] != NULL )
532 ptr2[1]->prev_v = cur_adr;
542 CV_WRITE_SEQ_ELEM( tree_two, writer );
543 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
545 if( ptr2[0] != NULL )
546 ptr2[0]->prev_v = cur_adr;
547 if( ptr2[1] != NULL )
548 ptr2[1]->prev_v = cur_adr;
553 CV_WRITE_SEQ_ELEM( tree_one, writer );
554 cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
556 if( ptr2[2] != NULL )
557 ptr2[2]->prev_v = cur_adr;
558 if( ptr2[3] != NULL )
559 ptr2[3]->prev_v = cur_adr;
571 s = cvContourArea( contour );
573 tree_root->pt = pt1[1];
575 tree_root->area = fabs( s );
578 tree_root->next_v1 = ptr1[0];
579 tree_root->next_v2 = ptr1[1];
580 tree_root->prev_v = NULL;
582 ptr1[0]->prev_v = (_CvTrianAttr *) tree_root;
583 ptr1[1]->prev_v = (_CvTrianAttr *) tree_root;
585 /* write binary tree root */
586 /* CV_WRITE_SEQ_ELEM (tree_one, start_writer); */
588 /* create Sequence hearder */
589 *tree = (CvContourTree*)cvEndWriteSeq( &writer );
590 /* write points for the main segment into sequence header */
591 (*tree)->p1 = pt1[0];
605 /****************************************************************************************\
607 triangle attributes calculations
609 \****************************************************************************************/
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 )
615 double x13, y13, x12, y12, l_base, nx, ny, qq;
622 qq = x13 * x13 + y13 * y13;
623 l_base = cvSqrt( (float) (qq) );
629 *h = nx * x12 + ny * y12;
631 *s = (*h) * l_base / 2.;
633 *b = nx * y12 - ny * x12;
636 /* calculate interceptive area */
637 *s_c = cvContourArea( contour, cvSlice(n1, n3+1));
651 /*F///////////////////////////////////////////////////////////////////////////////////////
652 // Name: cvCreateContourTree
654 // Create binary tree representation for the contour
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
663 CV_IMPL CvContourTree*
664 cvCreateContourTree( const CvSeq* contour, CvMemStorage* storage, double threshold )
666 CvContourTree* tree = 0;
668 IPPI_CALL( icvCreateContourTree( contour, storage, &tree, threshold ));
674 /*F///////////////////////////////////////////////////////////////////////////////////////
675 // Name: icvContourFromContourTree
677 // reconstracts contour from binary tree representation
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)
687 cvContourFromContourTree( const CvContourTree* tree,
688 CvMemStorage* storage,
689 CvTermCriteria criteria )
692 cv::AutoBuffer<_CvTrianAttr*> ptr_buf; /* pointer to the pointer's buffer */
693 cv::AutoBuffer<int> level_buf;
702 char log_iter, log_eps;
703 int out_hearder_size;
704 _CvTrianAttr *tree_one = 0, tree_root; /* current vertex */
710 CV_Error( CV_StsNullPtr, "" );
712 if( !CV_IS_SEQ_POLYGON_TREE( tree ))
713 CV_Error( CV_StsBadArg, "" );
715 criteria = cvCheckTermCriteria( criteria, 0., 100 );
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));
725 cvStartReadSeq( (CvSeq *) tree, &reader, 0 );
727 out_hearder_size = sizeof( CvContour );
729 seq_flags = CV_SEQ_POLYGON;
730 cvStartWriteSeq( seq_flags, out_hearder_size, sizeof( CvPoint ), storage, &writer );
732 ptr_buf.allocate(lpt);
734 level_buf.allocate(lpt);
736 memset( ptr_buf, 0, lpt * sizeof( _CvTrianAttr * ));
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 */
742 /* read the root of the tree */
743 CV_READ_SEQ_ELEM( tree_root, reader );
745 tree_one = &tree_root;
746 area_all = tree_one->area;
749 threshold = criteria.epsilon * area_all;
751 threshold = 10 * area_all;
754 level = criteria.max_iter;
758 /* contour from binary tree constraction */
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 */
765 ptr_buf[i_buf] = tree_one;
768 level_buf[i_buf] = cur_level;
772 tree_one = tree_one->next_v1;
779 CvPoint pt = ptr_buf[i_buf]->pt;
780 CV_WRITE_SEQ_ELEM( pt, writer );
781 tree_one = ptr_buf[i_buf]->next_v2;
784 cur_level = level_buf[i_buf] + 1;
790 contour = cvEndWriteSeq( &writer );
791 cvBoundingRect( contour, 1 );
796 /*F///////////////////////////////////////////////////////////////////////////////////////
797 // Name: icvMatchContourTrees
799 // Calculates matching of the two contour trees
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
810 cvMatchContourTrees( const CvContourTree* tree1, const CvContourTree* tree2,
811 int method, double threshold )
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;
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;
822 _CvTrianAttr tree_1, tree_2; /*current vertex 1 and 2 tree */
823 CvSeqReader reader1, reader2;
825 if( !tree1 || !tree2 )
826 CV_Error( CV_StsNullPtr, "" );
828 if( method != CV_CONTOUR_TREES_MATCH_I1 )
829 CV_Error( CV_StsBadArg, "Unknown/unsupported comparison method" );
831 if( !CV_IS_SEQ_POLYGON_TREE( tree1 ))
832 CV_Error( CV_StsBadArg, "The first argument is not a valid contour tree" );
834 if( !CV_IS_SEQ_POLYGON_TREE( tree2 ))
835 CV_Error( CV_StsBadArg, "The second argument is not a valid contour tree" );
839 lpt = lpt1 > lpt2 ? lpt1 : lpt2;
841 ptr_p1 = ptr_n1 = ptr_p2 = ptr_n2 = NULL;
844 ptr_p2 = ptr_p1 + lpt;
845 ptr_n1 = ptr_p2 + lpt;
846 ptr_n2 = ptr_n1 + lpt;
848 cvStartReadSeq( (CvSeq *) tree1, &reader1, 0 );
849 cvStartReadSeq( (CvSeq *) tree2, &reader2, 0 );
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 );
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;
865 if( area1 < eps || area2 < eps || lpt < 4 )
866 CV_Error( CV_StsBadSize, "" );
868 r11 = r12 = r21 = r22 = w1 = w2 = d12 = 0;
890 for( j = 0; j < i; j++ )
893 if( ptr11[j] != NULL )
898 w1 = ptr11[j]->area / area1;
905 if( ptr21[j] != NULL )
910 w2 = ptr21[j]->area / area2;
918 /* calculate node distance */
927 t0 = fabs( r11 * w1 + r21 * w2 );
928 t1 = fabs( r12 * w1 + r22 * w2 );
932 t0 = fabs( r11 * w1 - r21 * w2 );
933 t1 = fabs( r12 * w1 - r22 * w2 );
941 /*write to buffer the pointer to child vertexes*/
942 if( ptr11[j] != NULL )
944 ptr12[ibuf] = ptr11[j]->next_v1;
945 ptr12[ibuf1] = ptr11[j]->next_v2;
952 if( ptr21[j] != NULL )
954 ptr22[ibuf] = ptr21[j]->next_v1;
955 ptr22[ibuf1] = ptr21[j]->next_v2;
967 while( i > 0 && match_v < threshold );