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
icvCreateContourTree(const CvSeq * contour,CvMemStorage * storage,CvContourTree ** tree,double threshold)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
icvCalcTriAttr(const CvSeq * contour,CvPoint t2,CvPoint t1,int n1,CvPoint t3,int n3,double * s,double * s_c,double * h,double * a,double * b)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*
cvCreateContourTree(const CvSeq * contour,CvMemStorage * storage,double threshold)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*
cvContourFromContourTree(const CvContourTree * tree,CvMemStorage * storage,CvTermCriteria criteria)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