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.
43 /* initializes 8-element array for fast access to 3x3 neighborhood of a pixel */
44 #define CV_INIT_3X3_DELTAS( deltas, step, nch ) \
45 ((deltas)[0] = (nch), (deltas)[1] = -(step) + (nch), \
46 (deltas)[2] = -(step), (deltas)[3] = -(step) - (nch), \
47 (deltas)[4] = -(nch), (deltas)[5] = (step) - (nch), \
48 (deltas)[6] = (step), (deltas)[7] = (step) + (nch))
50 static const CvPoint icvCodeDeltas[8] =
51 { {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1} };
54 cvStartReadChainPoints( CvChain * chain, CvChainPtReader * reader )
58 CV_FUNCNAME( "cvStartReadChainPoints" );
62 if( !chain || !reader )
63 CV_ERROR( CV_StsNullPtr, "" );
65 if( chain->elem_size != 1 || chain->header_size < (int)sizeof(CvChain))
66 CV_ERROR_FROM_STATUS( CV_BADSIZE_ERR );
68 cvStartReadSeq( (CvSeq *) chain, (CvSeqReader *) reader, 0 );
71 reader->pt = chain->origin;
73 for( i = 0; i < 8; i++ )
75 reader->deltas[i][0] = (schar) icvCodeDeltas[i].x;
76 reader->deltas[i][1] = (schar) icvCodeDeltas[i].y;
83 /* retrieves next point of the chain curve and updates reader */
85 cvReadChainPoint( CvChainPtReader * reader )
89 CvPoint pt = { 0, 0 };
91 CV_FUNCNAME( "cvReadChainPoint" );
96 CV_ERROR( CV_StsNullPtr, "" );
105 if( ptr >= reader->block_max )
107 cvChangeSeqBlock( (CvSeqReader *) reader, 1 );
112 reader->code = (schar)code;
113 assert( (code & ~7) == 0 );
114 reader->pt.x = pt.x + icvCodeDeltas[code].x;
115 reader->pt.y = pt.y + icvCodeDeltas[code].y;
124 /****************************************************************************************\
125 * Raster->Chain Tree (Suzuki algorithms) *
126 \****************************************************************************************/
128 typedef struct _CvContourInfo
131 struct _CvContourInfo *next; /* next contour with the same mark value */
132 struct _CvContourInfo *parent; /* information about parent contour */
133 CvSeq *contour; /* corresponding contour (may be 0, if rejected) */
134 CvRect rect; /* bounding rectangle */
135 CvPoint origin; /* origin point (where the contour was traced from) */
136 int is_hole; /* hole flag */
142 Structure that is used for sequental retrieving contours from the image.
143 It supports both hierarchical and plane variants of Suzuki algorithm.
145 typedef struct _CvContourScanner
147 CvMemStorage *storage1; /* contains fetched contours */
148 CvMemStorage *storage2; /* contains approximated contours
149 (!=storage1 if approx_method2 != approx_method1) */
150 CvMemStorage *cinfo_storage; /* contains _CvContourInfo nodes */
151 CvSet *cinfo_set; /* set of _CvContourInfo nodes */
152 CvMemStoragePos initial_pos; /* starting storage pos */
153 CvMemStoragePos backup_pos; /* beginning of the latest approx. contour */
154 CvMemStoragePos backup_pos2; /* ending of the latest approx. contour */
155 schar *img0; /* image origin */
156 schar *img; /* current image row */
157 int img_step; /* image step */
158 CvSize img_size; /* ROI size */
159 CvPoint offset; /* ROI offset: coordinates, added to each contour point */
160 CvPoint pt; /* current scanner position */
161 CvPoint lnbd; /* position of the last met contour */
162 int nbd; /* current mark val */
163 _CvContourInfo *l_cinfo; /* information about latest approx. contour */
164 _CvContourInfo cinfo_temp; /* temporary var which is used in simple modes */
165 _CvContourInfo frame_info; /* information about frame */
166 CvSeq frame; /* frame itself */
167 int approx_method1; /* approx method when tracing */
168 int approx_method2; /* final approx method */
169 int mode; /* contour scanning mode:
171 1 - all the contours w/o any hierarchy
172 2 - connected components (i.e. two-level structure -
173 external contours and holes) */
175 int seq_type1; /* type of fetched contours */
176 int header_size1; /* hdr size of fetched contours */
177 int elem_size1; /* elem size of fetched contours */
179 int header_size2; /* the same for approx. contours */
180 int elem_size2; /* */
181 _CvContourInfo *cinfo_table[126];
185 #define _CV_FIND_CONTOURS_FLAGS_EXTERNAL_ONLY 1
186 #define _CV_FIND_CONTOURS_FLAGS_HIERARCHIC 2
189 Initializes scanner structure.
190 Prepare image for scanning ( clear borders and convert all pixels to 0-1.
192 CV_IMPL CvContourScanner
193 cvStartFindContours( void* _img, CvMemStorage* storage,
194 int header_size, int mode,
195 int method, CvPoint offset )
201 CvContourScanner scanner = 0;
202 CvMat stub, *mat = (CvMat*)_img;
204 CV_FUNCNAME( "cvStartFindContours" );
209 CV_ERROR( CV_StsNullPtr, "" );
211 CV_CALL( mat = cvGetMat( mat, &stub ));
213 if( !CV_IS_MASK_ARR( mat ))
214 CV_ERROR( CV_StsUnsupportedFormat, "[Start]FindContours support only 8uC1 images" );
216 size = cvSize( mat->width, mat->height );
218 img = (uchar*)(mat->data.ptr);
220 if( method < 0 || method > CV_CHAIN_APPROX_TC89_KCOS )
221 CV_ERROR_FROM_STATUS( CV_BADRANGE_ERR );
223 if( header_size < (int) (method == CV_CHAIN_CODE ? sizeof( CvChain ) : sizeof( CvContour )))
224 CV_ERROR_FROM_STATUS( CV_BADSIZE_ERR );
226 scanner = (CvContourScanner)cvAlloc( sizeof( *scanner ));
228 CV_ERROR_FROM_STATUS( CV_OUTOFMEM_ERR );
230 memset( scanner, 0, sizeof( *scanner ));
232 scanner->storage1 = scanner->storage2 = storage;
233 scanner->img0 = (schar *) img;
234 scanner->img = (schar *) (img + step);
235 scanner->img_step = step;
236 scanner->img_size.width = size.width - 1; /* exclude rightest column */
237 scanner->img_size.height = size.height - 1; /* exclude bottomost row */
238 scanner->mode = mode;
239 scanner->offset = offset;
240 scanner->pt.x = scanner->pt.y = 1;
244 scanner->mode = (int) mode;
245 scanner->frame_info.contour = &(scanner->frame);
246 scanner->frame_info.is_hole = 1;
247 scanner->frame_info.next = 0;
248 scanner->frame_info.parent = 0;
249 scanner->frame_info.rect = cvRect( 0, 0, size.width, size.height );
250 scanner->l_cinfo = 0;
251 scanner->subst_flag = 0;
253 scanner->frame.flags = CV_SEQ_FLAG_HOLE;
255 scanner->approx_method2 = scanner->approx_method1 = method;
257 if( method == CV_CHAIN_APPROX_TC89_L1 || method == CV_CHAIN_APPROX_TC89_KCOS )
258 scanner->approx_method1 = CV_CHAIN_CODE;
260 if( scanner->approx_method1 == CV_CHAIN_CODE )
262 scanner->seq_type1 = CV_SEQ_CHAIN_CONTOUR;
263 scanner->header_size1 = scanner->approx_method1 == scanner->approx_method2 ?
264 header_size : sizeof( CvChain );
265 scanner->elem_size1 = sizeof( char );
269 scanner->seq_type1 = CV_SEQ_POLYGON;
270 scanner->header_size1 = scanner->approx_method1 == scanner->approx_method2 ?
271 header_size : sizeof( CvContour );
272 scanner->elem_size1 = sizeof( CvPoint );
275 scanner->header_size2 = header_size;
277 if( scanner->approx_method2 == CV_CHAIN_CODE )
279 scanner->seq_type2 = scanner->seq_type1;
280 scanner->elem_size2 = scanner->elem_size1;
284 scanner->seq_type2 = CV_SEQ_POLYGON;
285 scanner->elem_size2 = sizeof( CvPoint );
288 scanner->seq_type1 = scanner->approx_method1 == CV_CHAIN_CODE ?
289 CV_SEQ_CHAIN_CONTOUR : CV_SEQ_POLYGON;
291 scanner->seq_type2 = scanner->approx_method2 == CV_CHAIN_CODE ?
292 CV_SEQ_CHAIN_CONTOUR : CV_SEQ_POLYGON;
294 cvSaveMemStoragePos( storage, &(scanner->initial_pos) );
296 if( method > CV_CHAIN_APPROX_SIMPLE )
298 scanner->storage1 = cvCreateChildMemStorage( scanner->storage2 );
301 if( mode > CV_RETR_LIST )
303 scanner->cinfo_storage = cvCreateChildMemStorage( scanner->storage2 );
304 scanner->cinfo_set = cvCreateSet( 0, sizeof( CvSet ), sizeof( _CvContourInfo ),
305 scanner->cinfo_storage );
306 if( scanner->cinfo_storage == 0 || scanner->cinfo_set == 0 )
307 CV_ERROR_FROM_STATUS( CV_OUTOFMEM_ERR );
310 /* make zero borders */
311 memset( img, 0, size.width );
312 memset( img + step * (size.height - 1), 0, size.width );
314 for( y = 1, img += step; y < size.height - 1; y++, img += step )
316 img[0] = img[size.width - 1] = 0;
319 /* converts all pixels to 0 or 1 */
320 cvThreshold( mat, mat, 0, 1, CV_THRESH_BINARY );
325 if( cvGetErrStatus() < 0 )
332 Final stage of contour processing.
333 Three variants possible:
334 1. Contour, which was retrieved using border following, is added to
335 the contour tree. It is the case when the icvSubstituteContour function
336 was not called after retrieving the contour.
338 2. New contour, assigned by icvSubstituteContour function, is added to the
339 tree. The retrieved contour itself is removed from the storage.
340 Here two cases are possible:
341 2a. If one deals with plane variant of algorithm
342 (hierarchical strucutre is not reconstructed),
343 the contour is removed completely.
344 2b. In hierarchical case, the header of the contour is not removed.
345 It's marked as "link to contour" and h_next pointer of it is set to
346 new, substituting contour.
348 3. The similar to 2, but when NULL pointer was assigned by
349 icvSubstituteContour function. In this case, the function removes
350 retrieved contour completely if plane case and
351 leaves header if hierarchical (but doesn't mark header as "link").
352 ------------------------------------------------------------------------
353 The 1st variant can be used to retrieve and store all the contours from the image
354 (with optional convertion from chains to contours using some approximation from
355 restriced set of methods). Some characteristics of contour can be computed in the
358 The usage scheme can look like:
360 icvContourScanner scanner;
361 CvMemStorage* contour_storage;
362 CvSeq* first_contour;
367 icvCreateMemStorage( &contour_storage, block_size/0 );
372 ( img, contour_storage,
373 header_size, approx_method,
380 result = icvFindNextContour( &scanner, &contour/0 );
382 if( result != CV_OK ) break;
384 // calculate some characteristics
388 if( result < 0 ) goto error_processing;
390 cvEndFindContours( &scanner, &first_contour );
393 -----------------------------------------------------------------
395 Second variant is more complex and can be used when someone wants store not
396 the retrieved contours but transformed ones. (e.g. approximated with some
397 non-default algorithm ).
399 The scheme can be the as following:
401 icvContourScanner scanner;
402 CvMemStorage* contour_storage;
403 CvMemStorage* temp_storage;
404 CvSeq* first_contour;
409 icvCreateMemStorage( &contour_storage, block_size/0 );
410 icvCreateMemStorage( &temp_storage, block_size/0 );
414 icvStartFindContours8uC1R
415 ( <img_params>, temp_storage,
416 header_size, approx_method,
424 result = icvFindNextContour( scanner, &temp_contour );
426 if( result != CV_OK ) break;
428 <approximation_function>( temp_contour, contour_storage,
429 &new_contour, <parameters...> );
431 icvSubstituteContour( scanner, new_contour );
435 if( result < 0 ) goto error_processing;
437 cvEndFindContours( &scanner, &first_contour );
440 ----------------------------------------------------------------------------
441 Third method to retrieve contours may be applied if contours are irrelevant
442 themselves but some characteristics of them are used only.
443 The usage is similar to second except slightly different internal loop
448 result = icvFindNextContour( &scanner, &temp_contour );
450 if( result != CV_OK ) break;
452 // calculate some characteristics of temp_contour
454 icvSubstituteContour( scanner, 0 );
458 new_storage variable is not needed here.
461 1. Second and third method can interleave. I.e. it is possible to
462 remain contours that satisfy with some criteria and reject others.
463 In hierarchic case the resulting tree is the part of original tree with
464 some nodes absent. But in the resulting tree the contour1 is a child
465 (may be indirect) of contour2 iff in the original tree the contour1
466 is a child (may be indirect) of contour2.
469 icvEndProcessContour( CvContourScanner scanner )
471 _CvContourInfo *l_cinfo = scanner->l_cinfo;
475 if( scanner->subst_flag )
477 CvMemStoragePos temp;
479 cvSaveMemStoragePos( scanner->storage2, &temp );
481 if( temp.top == scanner->backup_pos2.top &&
482 temp.free_space == scanner->backup_pos2.free_space )
484 cvRestoreMemStoragePos( scanner->storage2, &scanner->backup_pos );
486 scanner->subst_flag = 0;
489 if( l_cinfo->contour )
491 cvInsertNodeIntoTree( l_cinfo->contour, l_cinfo->parent->contour,
494 scanner->l_cinfo = 0;
498 /* replaces one contour with another */
500 cvSubstituteContour( CvContourScanner scanner, CvSeq * new_contour )
502 _CvContourInfo *l_cinfo;
504 CV_FUNCNAME( "cvSubstituteContour" );
509 CV_ERROR( CV_StsNullPtr, "" );
511 l_cinfo = scanner->l_cinfo;
512 if( l_cinfo && l_cinfo->contour && l_cinfo->contour != new_contour )
514 l_cinfo->contour = new_contour;
515 scanner->subst_flag = 1;
523 marks domain border with +/-<constant> and stores the contour into CvSeq.
527 >0 - simple approximation
530 icvFetchContour( schar *ptr,
539 schar *i0 = ptr, *i1, *i3, *i4 = 0;
540 int prev_s = -1, s, s_end;
541 int method = _method - 1;
543 assert( (unsigned) _method <= CV_CHAIN_APPROX_SIMPLE );
545 /* initialize local state */
546 CV_INIT_3X3_DELTAS( deltas, step, 1 );
547 memcpy( deltas + 8, deltas, 8 * sizeof( deltas[0] ));
549 /* initialize writer */
550 cvStartAppendToSeq( contour, &writer );
553 ((CvChain *) contour)->origin = pt;
555 s_end = s = CV_IS_SEQ_HOLE( contour ) ? 0 : 4;
566 if( s == s_end ) /* single pixel domain */
568 *i0 = (schar) (nbd | -128);
571 CV_WRITE_SEQ_ELEM( pt, writer );
586 i4 = i3 + deltas[++s];
592 /* check "right" bound */
593 if( (unsigned) (s - 1) < (unsigned) s_end )
595 *i3 = (schar) (nbd | -128);
604 schar _s = (schar) s;
606 CV_WRITE_SEQ_ELEM( _s, writer );
610 if( s != prev_s || method == 0 )
612 CV_WRITE_SEQ_ELEM( pt, writer );
616 pt.x += icvCodeDeltas[s].x;
617 pt.y += icvCodeDeltas[s].y;
621 if( i4 == i0 && i3 == i1 )
626 } /* end of border following loop */
629 cvEndWriteSeq( &writer );
631 if( _method != CV_CHAIN_CODE )
632 cvBoundingRect( contour, 1 );
634 assert( writer.seq->total == 0 && writer.seq->first == 0 ||
635 writer.seq->total > writer.seq->first->count ||
636 (writer.seq->first->prev == writer.seq->first &&
637 writer.seq->first->next == writer.seq->first) );
645 trace contour until certain point is met.
646 returns 1 if met, 0 else.
649 icvTraceContour( schar *ptr, int step, schar *stop_ptr, int is_hole )
652 schar *i0 = ptr, *i1, *i3, *i4;
655 /* initialize local state */
656 CV_INIT_3X3_DELTAS( deltas, step, 1 );
657 memcpy( deltas + 8, deltas, 8 * sizeof( deltas[0] ));
659 assert( (*i0 & -2) != 0 );
661 s_end = s = is_hole ? 0 : 4;
674 /* check single pixel domain */
684 i4 = i3 + deltas[++s];
689 if( i3 == stop_ptr || (i4 == i0 && i3 == i1) )
694 } /* end of border following loop */
696 return i3 == stop_ptr;
701 icvFetchContourEx( schar* ptr,
711 schar *i0 = ptr, *i1, *i3, *i4;
713 int prev_s = -1, s, s_end;
714 int method = _method - 1;
716 assert( (unsigned) _method <= CV_CHAIN_APPROX_SIMPLE );
717 assert( 1 < nbd && nbd < 128 );
719 /* initialize local state */
720 CV_INIT_3X3_DELTAS( deltas, step, 1 );
721 memcpy( deltas + 8, deltas, 8 * sizeof( deltas[0] ));
723 /* initialize writer */
724 cvStartAppendToSeq( contour, &writer );
727 ((CvChain *)contour)->origin = pt;
729 rect.x = rect.width = pt.x;
730 rect.y = rect.height = pt.y;
732 s_end = s = CV_IS_SEQ_HOLE( contour ) ? 0 : 4;
743 if( s == s_end ) /* single pixel domain */
745 *i0 = (schar) (nbd | 0x80);
748 CV_WRITE_SEQ_ELEM( pt, writer );
764 i4 = i3 + deltas[++s];
770 /* check "right" bound */
771 if( (unsigned) (s - 1) < (unsigned) s_end )
773 *i3 = (schar) (nbd | 0x80);
782 schar _s = (schar) s;
783 CV_WRITE_SEQ_ELEM( _s, writer );
785 else if( s != prev_s || method == 0 )
787 CV_WRITE_SEQ_ELEM( pt, writer );
795 else if( pt.x > rect.width )
800 else if( pt.y > rect.height )
805 pt.x += icvCodeDeltas[s].x;
806 pt.y += icvCodeDeltas[s].y;
808 if( i4 == i0 && i3 == i1 ) break;
812 } /* end of border following loop */
815 rect.width -= rect.x - 1;
816 rect.height -= rect.y - 1;
818 cvEndWriteSeq( &writer );
820 if( _method != CV_CHAIN_CODE )
821 ((CvContour*)contour)->rect = rect;
823 assert( writer.seq->total == 0 && writer.seq->first == 0 ||
824 writer.seq->total > writer.seq->first->count ||
825 (writer.seq->first->prev == writer.seq->first &&
826 writer.seq->first->next == writer.seq->first) );
828 if( _rect ) *_rect = rect;
835 cvFindNextContour( CvContourScanner scanner )
847 CvStatus result = (CvStatus) 1;
849 CV_FUNCNAME( "cvFindNextContour" );
854 CV_ERROR( CV_StsNullPtr, "" );
855 icvEndProcessContour( scanner );
857 /* initialize local state */
858 img0 = scanner->img0;
860 step = scanner->img_step;
863 width = scanner->img_size.width;
864 height = scanner->img_size.height;
865 mode = scanner->mode;
866 lnbd = scanner->lnbd;
871 for( ; y < height; y++, img += step )
873 for( ; x < width; x++ )
879 _CvContourInfo *par_info = 0;
880 _CvContourInfo *l_cinfo = 0;
885 if( !(prev == 0 && p == 1) ) /* if not external contour */
888 if( p != 0 || prev < 1 )
898 if( mode == 0 && (is_hole || img0[lnbd.y * step + lnbd.x] > 0) )
902 origin.x = x - is_hole;
904 /* find contour parent */
905 if( mode <= 1 || (!is_hole && mode == 2) || lnbd.x <= 0 )
907 par_info = &(scanner->frame_info);
911 int lval = img0[lnbd.y * step + lnbd.x] & 0x7f;
912 _CvContourInfo *cur = scanner->cinfo_table[lval - 2];
916 /* find the first bounding contour */
919 if( (unsigned) (lnbd.x - cur->rect.x) < (unsigned) cur->rect.width &&
920 (unsigned) (lnbd.y - cur->rect.y) < (unsigned) cur->rect.height )
924 if( icvTraceContour( scanner->img0 +
925 par_info->origin.y * step +
926 par_info->origin.x, step, img + lnbd.x,
927 par_info->is_hole ) > 0 )
935 assert( par_info != 0 );
937 /* if current contour is a hole and previous contour is a hole or
938 current contour is external and previous contour is external then
939 the parent of the contour is the parent of the previous contour else
940 the parent is the previous contour itself. */
941 if( par_info->is_hole == is_hole )
943 par_info = par_info->parent;
944 /* every contour must have a parent
945 (at least, the frame of the image) */
947 par_info = &(scanner->frame_info);
950 /* hole flag of the parent must differ from the flag of the contour */
951 assert( par_info->is_hole != is_hole );
952 if( par_info->contour == 0 ) /* removed contour */
956 lnbd.x = x - is_hole;
958 cvSaveMemStoragePos( scanner->storage2, &(scanner->backup_pos) );
960 seq = cvCreateSeq( scanner->seq_type1, scanner->header_size1,
961 scanner->elem_size1, scanner->storage1 );
964 result = CV_OUTOFMEM_ERR;
967 seq->flags |= is_hole ? CV_SEQ_FLAG_HOLE : 0;
969 /* initialize header */
972 l_cinfo = &(scanner->cinfo_temp);
973 result = icvFetchContour( img + x - is_hole, step,
974 cvPoint( origin.x + scanner->offset.x,
975 origin.y + scanner->offset.y),
976 seq, scanner->approx_method1 );
982 union { _CvContourInfo* ci; CvSetElem* se; } v;
984 cvSetAdd( scanner->cinfo_set, 0, &v.se );
987 result = icvFetchContourEx( img + x - is_hole, step,
988 cvPoint( origin.x + scanner->offset.x,
989 origin.y + scanner->offset.y),
990 seq, scanner->approx_method1,
991 nbd, &(l_cinfo->rect) );
994 l_cinfo->rect.x -= scanner->offset.x;
995 l_cinfo->rect.y -= scanner->offset.y;
997 l_cinfo->next = scanner->cinfo_table[nbd - 2];
998 scanner->cinfo_table[nbd - 2] = l_cinfo;
1001 nbd = (nbd + 1) & 127;
1002 nbd += nbd == 0 ? 3 : 0;
1005 l_cinfo->is_hole = is_hole;
1006 l_cinfo->contour = seq;
1007 l_cinfo->origin = origin;
1008 l_cinfo->parent = par_info;
1010 if( scanner->approx_method1 != scanner->approx_method2 )
1012 result = icvApproximateChainTC89( (CvChain *) seq,
1013 scanner->header_size2,
1015 &(l_cinfo->contour),
1016 scanner->approx_method2 );
1019 cvClearMemStorage( scanner->storage1 );
1022 l_cinfo->contour->v_prev = l_cinfo->parent->contour;
1024 if( par_info->contour == 0 )
1026 l_cinfo->contour = 0;
1027 if( scanner->storage1 == scanner->storage2 )
1029 cvRestoreMemStoragePos( scanner->storage1, &(scanner->backup_pos) );
1033 cvClearMemStorage( scanner->storage1 );
1039 cvSaveMemStoragePos( scanner->storage2, &(scanner->backup_pos2) );
1040 scanner->l_cinfo = l_cinfo;
1041 scanner->pt.x = x + 1;
1043 scanner->lnbd = lnbd;
1044 scanner->img = (schar *) img;
1046 contour = l_cinfo->contour;
1057 } /* end of prev != p */
1058 } /* end of loop on x */
1065 } /* end of loop on y */
1072 CV_ERROR_FROM_STATUS( result );
1081 The function add to tree the last retrieved/substituted contour,
1082 releases temp_storage, restores state of dst_storage (if needed), and
1083 returns pointer to root of the contour tree */
1085 cvEndFindContours( CvContourScanner * _scanner )
1087 CvContourScanner scanner;
1090 CV_FUNCNAME( "cvFindNextContour" );
1095 CV_ERROR( CV_StsNullPtr, "" );
1096 scanner = *_scanner;
1100 icvEndProcessContour( scanner );
1102 if( scanner->storage1 != scanner->storage2 )
1103 cvReleaseMemStorage( &(scanner->storage1) );
1105 if( scanner->cinfo_storage )
1106 cvReleaseMemStorage( &(scanner->cinfo_storage) );
1108 first = scanner->frame.v_next;
1118 #define ICV_SINGLE 0
1119 #define ICV_CONNECTING_ABOVE 1
1120 #define ICV_CONNECTING_BELOW -1
1121 #define ICV_IS_COMPONENT_POINT(val) ((val) != 0)
1123 #define CV_GET_WRITTEN_ELEM( writer ) ((writer).ptr - (writer).seq->elem_size)
1125 typedef struct CvLinkedRunPoint
1127 struct CvLinkedRunPoint* link;
1128 struct CvLinkedRunPoint* next;
1135 icvFindContoursInInterval( const CvArr* src,
1136 /*int minValue, int maxValue,*/
1137 CvMemStorage* storage,
1139 int contourHeaderSize )
1142 CvMemStorage* storage00 = 0;
1143 CvMemStorage* storage01 = 0;
1146 CV_FUNCNAME( "icvFindContoursInInterval" );
1152 uchar* src_data = 0;
1162 CvLinkedRunPoint tmp;
1163 CvLinkedRunPoint* tmp_prev;
1164 CvLinkedRunPoint* upper_line = 0;
1165 CvLinkedRunPoint* lower_line = 0;
1166 CvLinkedRunPoint* last_elem;
1168 CvLinkedRunPoint* upper_run = 0;
1169 CvLinkedRunPoint* lower_run = 0;
1170 CvLinkedRunPoint* prev_point = 0;
1172 CvSeqWriter writer_ext;
1173 CvSeqWriter writer_int;
1177 CvSeq* external_contours;
1178 CvSeq* internal_contours;
1182 CV_ERROR( CV_StsNullPtr, "NULL storage pointer" );
1185 CV_ERROR( CV_StsNullPtr, "NULL double CvSeq pointer" );
1187 if( contourHeaderSize < (int)sizeof(CvContour))
1188 CV_ERROR( CV_StsBadSize, "Contour header size must be >= sizeof(CvContour)" );
1190 CV_CALL( storage00 = cvCreateChildMemStorage(storage));
1191 CV_CALL( storage01 = cvCreateChildMemStorage(storage));
1196 CV_CALL( mat = cvGetMat( src, &stub ));
1197 if( !CV_IS_MASK_ARR(mat))
1198 CV_ERROR( CV_StsBadArg, "Input array must be 8uC1 or 8sC1" );
1199 src_data = mat->data.ptr;
1200 img_step = mat->step;
1201 img_size = cvGetMatSize( mat );
1204 // Create temporary sequences
1205 runs = cvCreateSeq(0, sizeof(CvSeq), sizeof(CvLinkedRunPoint), storage00 );
1206 cvStartAppendToSeq( runs, &writer );
1208 cvStartWriteSeq( 0, sizeof(CvSeq), sizeof(CvLinkedRunPoint*), storage01, &writer_ext );
1209 cvStartWriteSeq( 0, sizeof(CvSeq), sizeof(CvLinkedRunPoint*), storage01, &writer_int );
1215 // First line. None of runs is binded
1218 CV_WRITE_SEQ_ELEM( tmp, writer );
1219 upper_line = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer );
1221 tmp_prev = upper_line;
1222 for( j = 0; j < img_size.width; )
1224 for( ; j < img_size.width && !ICV_IS_COMPONENT_POINT(src_data[j]); j++ )
1226 if( j == img_size.width )
1230 CV_WRITE_SEQ_ELEM( tmp, writer );
1231 tmp_prev->next = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer );
1232 tmp_prev = tmp_prev->next;
1234 for( ; j < img_size.width && ICV_IS_COMPONENT_POINT(src_data[j]); j++ )
1238 CV_WRITE_SEQ_ELEM( tmp, writer );
1239 tmp_prev->next = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer );
1240 tmp_prev->link = tmp_prev->next;
1241 // First point of contour
1242 CV_WRITE_SEQ_ELEM( tmp_prev, writer_ext );
1243 tmp_prev = tmp_prev->next;
1245 cvFlushSeqWriter( &writer );
1246 upper_line = upper_line->next;
1247 upper_total = runs->total - 1;
1248 last_elem = tmp_prev;
1251 for( i = 1; i < img_size.height; i++ )
1253 //------// Find runs in next line
1254 src_data += img_step;
1256 all_total = runs->total;
1257 for( j = 0; j < img_size.width; )
1259 for( ; j < img_size.width && !ICV_IS_COMPONENT_POINT(src_data[j]); j++ )
1261 if( j == img_size.width ) break;
1264 CV_WRITE_SEQ_ELEM( tmp, writer );
1265 tmp_prev->next = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer );
1266 tmp_prev = tmp_prev->next;
1268 for( ; j < img_size.width && ICV_IS_COMPONENT_POINT(src_data[j]); j++ )
1272 CV_WRITE_SEQ_ELEM( tmp, writer );
1273 tmp_prev = tmp_prev->next = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer );
1275 cvFlushSeqWriter( &writer );
1276 lower_line = last_elem->next;
1277 lower_total = runs->total - all_total;
1278 last_elem = tmp_prev;
1281 //------// Find links between runs of lower_line and upper_line
1282 upper_run = upper_line;
1283 lower_run = lower_line;
1284 connect_flag = ICV_SINGLE;
1286 for( k = 0, n = 0; k < upper_total/2 && n < lower_total/2; )
1288 switch( connect_flag )
1291 if( upper_run->next->pt.x < lower_run->next->pt.x )
1293 if( upper_run->next->pt.x >= lower_run->pt.x -1 )
1295 lower_run->link = upper_run;
1296 connect_flag = ICV_CONNECTING_ABOVE;
1297 prev_point = upper_run->next;
1300 upper_run->next->link = upper_run;
1302 upper_run = upper_run->next->next;
1306 if( upper_run->pt.x <= lower_run->next->pt.x +1 )
1308 lower_run->link = upper_run;
1309 connect_flag = ICV_CONNECTING_BELOW;
1310 prev_point = lower_run->next;
1314 lower_run->link = lower_run->next;
1315 // First point of contour
1316 CV_WRITE_SEQ_ELEM( lower_run, writer_ext );
1319 lower_run = lower_run->next->next;
1322 case ICV_CONNECTING_ABOVE:
1323 if( upper_run->pt.x > lower_run->next->pt.x +1 )
1325 prev_point->link = lower_run->next;
1326 connect_flag = ICV_SINGLE;
1328 lower_run = lower_run->next->next;
1332 prev_point->link = upper_run;
1333 if( upper_run->next->pt.x < lower_run->next->pt.x )
1336 prev_point = upper_run->next;
1337 upper_run = upper_run->next->next;
1341 connect_flag = ICV_CONNECTING_BELOW;
1342 prev_point = lower_run->next;
1344 lower_run = lower_run->next->next;
1348 case ICV_CONNECTING_BELOW:
1349 if( lower_run->pt.x > upper_run->next->pt.x +1 )
1351 upper_run->next->link = prev_point;
1352 connect_flag = ICV_SINGLE;
1354 upper_run = upper_run->next->next;
1358 // First point of contour
1359 CV_WRITE_SEQ_ELEM( lower_run, writer_int );
1361 lower_run->link = prev_point;
1362 if( lower_run->next->pt.x < upper_run->next->pt.x )
1365 prev_point = lower_run->next;
1366 lower_run = lower_run->next->next;
1370 connect_flag = ICV_CONNECTING_ABOVE;
1372 prev_point = upper_run->next;
1373 upper_run = upper_run->next->next;
1380 for( ; n < lower_total/2; n++ )
1382 if( connect_flag != ICV_SINGLE )
1384 prev_point->link = lower_run->next;
1385 connect_flag = ICV_SINGLE;
1386 lower_run = lower_run->next->next;
1389 lower_run->link = lower_run->next;
1391 //First point of contour
1392 CV_WRITE_SEQ_ELEM( lower_run, writer_ext );
1394 lower_run = lower_run->next->next;
1397 for( ; k < upper_total/2; k++ )
1399 if( connect_flag != ICV_SINGLE )
1401 upper_run->next->link = prev_point;
1402 connect_flag = ICV_SINGLE;
1403 upper_run = upper_run->next->next;
1406 upper_run->next->link = upper_run;
1407 upper_run = upper_run->next->next;
1409 upper_line = lower_line;
1410 upper_total = lower_total;
1413 upper_run = upper_line;
1415 //the last line of image
1416 for( k = 0; k < upper_total/2; k++ )
1418 upper_run->next->link = upper_run;
1419 upper_run = upper_run->next->next;
1423 //------//Find end read contours
1424 external_contours = cvEndWriteSeq( &writer_ext );
1425 internal_contours = cvEndWriteSeq( &writer_int );
1427 for( k = 0; k < 2; k++ )
1429 CvSeq* contours = k == 0 ? external_contours : internal_contours;
1431 cvStartReadSeq( contours, &reader );
1433 for( j = 0; j < contours->total; j++, count++ )
1435 CvLinkedRunPoint* p_temp;
1436 CvLinkedRunPoint* p00;
1437 CvLinkedRunPoint* p01;
1440 CV_READ_SEQ_ELEM( p00, reader );
1446 cvStartWriteSeq( CV_SEQ_ELTYPE_POINT | CV_SEQ_POLYLINE | CV_SEQ_FLAG_CLOSED,
1447 contourHeaderSize, sizeof(CvPoint), storage, &writer );
1450 CV_WRITE_SEQ_ELEM( p00->pt, writer );
1455 while( p00 != p01 );
1457 contour = cvEndWriteSeq( &writer );
1458 cvBoundingRect( contour, 1 );
1461 contour->flags |= CV_SEQ_FLAG_HOLE;
1464 prev = first = contour;
1467 contour->h_prev = prev;
1468 prev = prev->h_next = contour;
1481 cvReleaseMemStorage(&storage00);
1482 cvReleaseMemStorage(&storage01);
1489 /*F///////////////////////////////////////////////////////////////////////////////////////
1490 // Name: cvFindContours
1492 // Finds all the contours on the bi-level image.
1495 // img - source image.
1496 // Non-zero pixels are considered as 1-pixels
1497 // and zero pixels as 0-pixels.
1498 // step - full width of source image in bytes.
1499 // size - width and height of the image in pixels
1500 // storage - pointer to storage where will the output contours be placed.
1501 // header_size - header size of resulting contours
1502 // mode - mode of contour retrieval.
1503 // method - method of approximation that is applied to contours
1504 // first_contour - pointer to first contour pointer
1506 // CV_OK or error code
1510 cvFindContours( void* img, CvMemStorage* storage,
1511 CvSeq** firstContour, int cntHeaderSize,
1513 int method, CvPoint offset )
1515 CvContourScanner scanner = 0;
1519 CV_FUNCNAME( "cvFindContours" );
1524 CV_ERROR( CV_StsNullPtr, "NULL double CvSeq pointer" );
1526 if( method == CV_LINK_RUNS )
1528 if( offset.x != 0 || offset.y != 0 )
1529 CV_ERROR( CV_StsOutOfRange,
1530 "Nonzero offset is not supported in CV_LINK_RUNS yet" );
1532 CV_CALL( count = icvFindContoursInInterval( img, storage,
1533 firstContour, cntHeaderSize ));
1537 CV_CALL( scanner = cvStartFindContours( img, storage,
1538 cntHeaderSize, mode, method, offset ));
1544 contour = cvFindNextContour( scanner );
1546 while( contour != 0 );
1548 *firstContour = cvEndFindContours( &scanner );