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#include "opencv2/core/hal/intrin.hpp"
43#include "opencv2/imgproc/detail/legacy.hpp"
44
45using namespace cv;
46
47/* initializes 8-element array for fast access to 3x3 neighborhood of a pixel */
48#define CV_INIT_3X3_DELTAS( deltas, step, nch ) \
49 ((deltas)[0] = (nch), (deltas)[1] = -(step) + (nch), \
50 (deltas)[2] = -(step), (deltas)[3] = -(step) - (nch), \
51 (deltas)[4] = -(nch), (deltas)[5] = (step) - (nch), \
52 (deltas)[6] = (step), (deltas)[7] = (step) + (nch))
53
54static const CvPoint icvCodeDeltas[8] =
55 { {.x: 1, .y: 0}, {.x: 1, .y: -1}, {.x: 0, .y: -1}, {.x: -1, .y: -1}, {.x: -1, .y: 0}, {.x: -1, .y: 1}, {.x: 0, .y: 1}, {.x: 1, .y: 1} };
56
57CV_IMPL void
58cvStartReadChainPoints( CvChain * chain, CvChainPtReader * reader )
59{
60 int i;
61
62 if( !chain || !reader )
63 CV_Error( cv::Error::StsNullPtr, "" );
64
65 if( chain->elem_size != 1 || chain->header_size < (int)sizeof(CvChain))
66 CV_Error( cv::Error::StsBadSize, "" );
67
68 cvStartReadSeq( seq: (CvSeq *) chain, reader: (CvSeqReader *) reader, reverse: 0 );
69
70 reader->pt = chain->origin;
71 for( i = 0; i < 8; i++ )
72 {
73 reader->deltas[i][0] = (schar) icvCodeDeltas[i].x;
74 reader->deltas[i][1] = (schar) icvCodeDeltas[i].y;
75 }
76}
77
78
79/* retrieves next point of the chain curve and updates reader */
80CV_IMPL CvPoint
81cvReadChainPoint( CvChainPtReader * reader )
82{
83 if( !reader )
84 CV_Error( cv::Error::StsNullPtr, "" );
85
86 cv::Point2i pt = reader->pt;
87
88 schar *ptr = reader->ptr;
89 if (ptr)
90 {
91 int code = *ptr++;
92
93 if( ptr >= reader->block_max )
94 {
95 cvChangeSeqBlock( reader: (CvSeqReader *) reader, direction: 1 );
96 ptr = reader->ptr;
97 }
98
99 reader->ptr = ptr;
100 reader->code = (schar)code;
101 CV_Assert( (code & ~7) == 0 );
102 reader->pt.x = pt.x + icvCodeDeltas[code].x;
103 reader->pt.y = pt.y + icvCodeDeltas[code].y;
104 }
105
106 return cvPoint(pt);
107}
108
109
110/****************************************************************************************\
111* Raster->Chain Tree (Suzuki algorithms) *
112\****************************************************************************************/
113
114typedef struct _CvContourInfo
115{
116 int flags;
117 struct _CvContourInfo *next; /* next contour with the same mark value */
118 struct _CvContourInfo *parent; /* information about parent contour */
119 CvSeq *contour; /* corresponding contour (may be 0, if rejected) */
120 CvRect rect; /* bounding rectangle */
121 CvPoint origin; /* origin point (where the contour was traced from) */
122 int is_hole; /* hole flag */
123}
124_CvContourInfo;
125
126
127/*
128 Structure that is used for sequential retrieving contours from the image.
129 It supports both hierarchical and plane variants of Suzuki algorithm.
130*/
131typedef struct _CvContourScanner
132{
133 CvMemStorage *storage1; /* contains fetched contours */
134 CvMemStorage *storage2; /* contains approximated contours
135 (!=storage1 if approx_method2 != approx_method1) */
136 CvMemStorage *cinfo_storage; /* contains _CvContourInfo nodes */
137 CvSet *cinfo_set; /* set of _CvContourInfo nodes */
138 CvMemStoragePos initial_pos; /* starting storage pos */
139 CvMemStoragePos backup_pos; /* beginning of the latest approx. contour */
140 CvMemStoragePos backup_pos2; /* ending of the latest approx. contour */
141 schar *img0; /* image origin */
142 schar *img; /* current image row */
143 int img_step; /* image step */
144 CvSize img_size; /* ROI size */
145 CvPoint offset; /* ROI offset: coordinates, added to each contour point */
146 CvPoint pt; /* current scanner position */
147 CvPoint lnbd; /* position of the last met contour */
148 int nbd; /* current mark val */
149 _CvContourInfo *l_cinfo; /* information about latest approx. contour */
150 _CvContourInfo cinfo_temp; /* temporary var which is used in simple modes */
151 _CvContourInfo frame_info; /* information about frame */
152 CvSeq frame; /* frame itself */
153 int approx_method1; /* approx method when tracing */
154 int approx_method2; /* final approx method */
155 int mode; /* contour scanning mode:
156 0 - external only
157 1 - all the contours w/o any hierarchy
158 2 - connected components (i.e. two-level structure -
159 external contours and holes),
160 3 - full hierarchy;
161 4 - connected components of a multi-level image
162 */
163 int subst_flag;
164 int seq_type1; /* type of fetched contours */
165 int header_size1; /* hdr size of fetched contours */
166 int elem_size1; /* elem size of fetched contours */
167 int seq_type2; /* */
168 int header_size2; /* the same for approx. contours */
169 int elem_size2; /* */
170 _CvContourInfo *cinfo_table[128];
171}
172_CvContourScanner;
173
174/*
175 Initializes scanner structure.
176 Prepare image for scanning ( clear borders and convert all pixels to 0-1 ).
177*/
178static CvContourScanner
179cvStartFindContours_Impl( void* _img, CvMemStorage* storage,
180 int header_size, int mode,
181 int method, CvPoint offset, int needFillBorder )
182{
183 if( !storage )
184 CV_Error( cv::Error::StsNullPtr, "" );
185
186 CvMat stub, *mat = cvGetMat( arr: _img, header: &stub );
187
188 if( CV_MAT_TYPE(mat->type) == CV_32SC1 && mode == CV_RETR_CCOMP )
189 mode = CV_RETR_FLOODFILL;
190
191 if( !((CV_IS_MASK_ARR( mat ) && mode < CV_RETR_FLOODFILL) ||
192 (CV_MAT_TYPE(mat->type) == CV_32SC1 && mode == CV_RETR_FLOODFILL)) )
193 CV_Error( cv::Error::StsUnsupportedFormat,
194 "[Start]FindContours supports only CV_8UC1 images when mode != CV_RETR_FLOODFILL "
195 "otherwise supports CV_32SC1 images only" );
196
197 CvSize size = cvSize( width: mat->width, height: mat->height );
198 int step = mat->step;
199 uchar* img = (uchar*)(mat->data.ptr);
200
201 if( method < 0 || method > CV_CHAIN_APPROX_TC89_KCOS )
202 CV_Error( cv::Error::StsOutOfRange, "" );
203
204 if( header_size < (int) (method == CV_CHAIN_CODE ? sizeof( CvChain ) : sizeof( CvContour )))
205 CV_Error( cv::Error::StsBadSize, "" );
206
207 CvContourScanner scanner = (CvContourScanner)cvAlloc( size: sizeof( *scanner ));
208 memset( s: scanner, c: 0, n: sizeof(*scanner) );
209
210 scanner->storage1 = scanner->storage2 = storage;
211 scanner->img0 = (schar *) img;
212 scanner->img = (schar *) (img + step);
213 scanner->img_step = step;
214 scanner->img_size.width = size.width - 1; /* exclude rightest column */
215 scanner->img_size.height = size.height - 1; /* exclude bottommost row */
216 scanner->mode = mode;
217 scanner->offset = offset;
218 scanner->pt.x = scanner->pt.y = 1;
219 scanner->lnbd.x = 0;
220 scanner->lnbd.y = 1;
221 scanner->nbd = 2;
222 scanner->frame_info.contour = &(scanner->frame);
223 scanner->frame_info.is_hole = 1;
224 scanner->frame_info.next = 0;
225 scanner->frame_info.parent = 0;
226 scanner->frame_info.rect = cvRect( x: 0, y: 0, width: size.width, height: size.height );
227 scanner->l_cinfo = 0;
228 scanner->subst_flag = 0;
229
230 scanner->frame.flags = CV_SEQ_FLAG_HOLE;
231
232 scanner->approx_method2 = scanner->approx_method1 = method;
233
234 if( method == CV_CHAIN_APPROX_TC89_L1 || method == CV_CHAIN_APPROX_TC89_KCOS )
235 scanner->approx_method1 = CV_CHAIN_CODE;
236
237 if( scanner->approx_method1 == CV_CHAIN_CODE )
238 {
239 scanner->seq_type1 = CV_SEQ_CHAIN_CONTOUR;
240 scanner->header_size1 = scanner->approx_method1 == scanner->approx_method2 ?
241 header_size : sizeof( CvChain );
242 scanner->elem_size1 = sizeof( char );
243 }
244 else
245 {
246 scanner->seq_type1 = CV_SEQ_POLYGON;
247 scanner->header_size1 = scanner->approx_method1 == scanner->approx_method2 ?
248 header_size : sizeof( CvContour );
249 scanner->elem_size1 = sizeof( CvPoint );
250 }
251
252 scanner->header_size2 = header_size;
253
254 if( scanner->approx_method2 == CV_CHAIN_CODE )
255 {
256 scanner->seq_type2 = scanner->seq_type1;
257 scanner->elem_size2 = scanner->elem_size1;
258 }
259 else
260 {
261 scanner->seq_type2 = CV_SEQ_POLYGON;
262 scanner->elem_size2 = sizeof( CvPoint );
263 }
264
265 scanner->seq_type1 = scanner->approx_method1 == CV_CHAIN_CODE ?
266 CV_SEQ_CHAIN_CONTOUR : CV_SEQ_POLYGON;
267
268 scanner->seq_type2 = scanner->approx_method2 == CV_CHAIN_CODE ?
269 CV_SEQ_CHAIN_CONTOUR : CV_SEQ_POLYGON;
270
271 cvSaveMemStoragePos( storage, pos: &(scanner->initial_pos) );
272
273 if( method > CV_CHAIN_APPROX_SIMPLE )
274 {
275 scanner->storage1 = cvCreateChildMemStorage( parent: scanner->storage2 );
276 }
277
278 if( mode > CV_RETR_LIST )
279 {
280 scanner->cinfo_storage = cvCreateChildMemStorage( parent: scanner->storage2 );
281 scanner->cinfo_set = cvCreateSet( set_flags: 0, header_size: sizeof( CvSet ), elem_size: sizeof( _CvContourInfo ),
282 storage: scanner->cinfo_storage );
283 }
284
285 CV_Assert(step >= 0);
286 CV_Assert(size.height >= 1);
287
288 /* make zero borders */
289 if(needFillBorder)
290 {
291 int esz = CV_ELEM_SIZE(mat->type);
292 memset( s: img, c: 0, n: size.width*esz );
293 memset( s: img + static_cast<size_t>(step) * (size.height - 1), c: 0, n: size.width*esz );
294
295 img += step;
296 for( int y = 1; y < size.height - 1; y++, img += step )
297 {
298 for( int k = 0; k < esz; k++ )
299 img[k] = img[(size.width - 1)*esz + k] = (schar)0;
300 }
301 }
302
303 /* converts all pixels to 0 or 1 */
304 if( CV_MAT_TYPE(mat->type) != CV_32S )
305 cvThreshold( src: mat, dst: mat, threshold: 0, max_value: 1, threshold_type: cv::THRESH_BINARY );
306
307 return scanner;
308}
309
310CV_IMPL CvContourScanner
311cvStartFindContours( void* _img, CvMemStorage* storage,
312 int header_size, int mode,
313 int method, CvPoint offset )
314{
315 return cvStartFindContours_Impl(_img, storage, header_size, mode, method, offset, needFillBorder: 1);
316}
317
318/*
319 Final stage of contour processing.
320 Three variants possible:
321 1. Contour, which was retrieved using border following, is added to
322 the contour tree. It is the case when the icvSubstituteContour function
323 was not called after retrieving the contour.
324
325 2. New contour, assigned by icvSubstituteContour function, is added to the
326 tree. The retrieved contour itself is removed from the storage.
327 Here two cases are possible:
328 2a. If one deals with plane variant of algorithm
329 (hierarchical structure is not reconstructed),
330 the contour is removed completely.
331 2b. In hierarchical case, the header of the contour is not removed.
332 It's marked as "link to contour" and h_next pointer of it is set to
333 new, substituting contour.
334
335 3. The similar to 2, but when NULL pointer was assigned by
336 icvSubstituteContour function. In this case, the function removes
337 retrieved contour completely if plane case and
338 leaves header if hierarchical (but doesn't mark header as "link").
339 ------------------------------------------------------------------------
340 The 1st variant can be used to retrieve and store all the contours from the image
341 (with optional conversion from chains to contours using some approximation from
342 restricted set of methods). Some characteristics of contour can be computed in the
343 same pass.
344
345 The usage scheme can look like:
346
347 icvContourScanner scanner;
348 CvMemStorage* contour_storage;
349 CvSeq* first_contour;
350 CvStatus result;
351
352 ...
353
354 icvCreateMemStorage( &contour_storage, block_size/0 );
355
356 ...
357
358 cvStartFindContours
359 ( img, contour_storage,
360 header_size, approx_method,
361 [external_only,]
362 &scanner );
363
364 for(;;)
365 {
366 [CvSeq* contour;]
367 result = icvFindNextContour( &scanner, &contour/0 );
368
369 if( result != CV_OK ) break;
370
371 // calculate some characteristics
372 ...
373 }
374
375 if( result < 0 ) goto error_processing;
376
377 cvEndFindContours( &scanner, &first_contour );
378 ...
379
380 -----------------------------------------------------------------
381
382 Second variant is more complex and can be used when someone wants store not
383 the retrieved contours but transformed ones. (e.g. approximated with some
384 non-default algorithm ).
385
386 The scheme can be the as following:
387
388 icvContourScanner scanner;
389 CvMemStorage* contour_storage;
390 CvMemStorage* temp_storage;
391 CvSeq* first_contour;
392 CvStatus result;
393
394 ...
395
396 icvCreateMemStorage( &contour_storage, block_size/0 );
397 icvCreateMemStorage( &temp_storage, block_size/0 );
398
399 ...
400
401 icvStartFindContours8uC1R
402 ( <img_params>, temp_storage,
403 header_size, approx_method,
404 [retrival_mode],
405 &scanner );
406
407 for(;;)
408 {
409 CvSeq* temp_contour;
410 CvSeq* new_contour;
411 result = icvFindNextContour( scanner, &temp_contour );
412
413 if( result != CV_OK ) break;
414
415 <approximation_function>( temp_contour, contour_storage,
416 &new_contour, <parameters...> );
417
418 icvSubstituteContour( scanner, new_contour );
419 ...
420 }
421
422 if( result < 0 ) goto error_processing;
423
424 cvEndFindContours( &scanner, &first_contour );
425 ...
426
427 ----------------------------------------------------------------------------
428 Third method to retrieve contours may be applied if contours are irrelevant
429 themselves but some characteristics of them are used only.
430 The usage is similar to second except slightly different internal loop
431
432 for(;;)
433 {
434 CvSeq* temp_contour;
435 result = icvFindNextContour( &scanner, &temp_contour );
436
437 if( result != CV_OK ) break;
438
439 // calculate some characteristics of temp_contour
440
441 icvSubstituteContour( scanner, 0 );
442 ...
443 }
444
445 new_storage variable is not needed here.
446
447 Note, that the second and the third methods can interleave. I.e. it is possible to
448 retain contours that satisfy with some criteria and reject others.
449 In hierarchic case the resulting tree is the part of original tree with
450 some nodes absent. But in the resulting tree the contour1 is a child
451 (may be indirect) of contour2 iff in the original tree the contour1
452 is a child (may be indirect) of contour2.
453*/
454static void
455icvEndProcessContour( CvContourScanner scanner )
456{
457 _CvContourInfo *l_cinfo = scanner->l_cinfo;
458
459 if( l_cinfo )
460 {
461 if( scanner->subst_flag )
462 {
463 CvMemStoragePos temp;
464
465 cvSaveMemStoragePos( storage: scanner->storage2, pos: &temp );
466
467 if( temp.top == scanner->backup_pos2.top &&
468 temp.free_space == scanner->backup_pos2.free_space )
469 {
470 cvRestoreMemStoragePos( storage: scanner->storage2, pos: &scanner->backup_pos );
471 }
472 scanner->subst_flag = 0;
473 }
474
475 if( l_cinfo->contour )
476 {
477 cvInsertNodeIntoTree( node: l_cinfo->contour, parent: l_cinfo->parent->contour,
478 frame: &(scanner->frame) );
479 }
480 scanner->l_cinfo = 0;
481 }
482}
483
484/* replaces one contour with another */
485CV_IMPL void
486cvSubstituteContour( CvContourScanner scanner, CvSeq * new_contour )
487{
488 _CvContourInfo *l_cinfo;
489
490 if( !scanner )
491 CV_Error( cv::Error::StsNullPtr, "" );
492
493 l_cinfo = scanner->l_cinfo;
494 if( l_cinfo && l_cinfo->contour && l_cinfo->contour != new_contour )
495 {
496 l_cinfo->contour = new_contour;
497 scanner->subst_flag = 1;
498 }
499}
500
501static const int MAX_SIZE = 16;
502
503/*
504 marks domain border with +/-<constant> and stores the contour into CvSeq.
505 method:
506 <0 - chain
507 ==0 - direct
508 >0 - simple approximation
509*/
510static void
511icvFetchContour( schar *ptr,
512 int step,
513 CvPoint pt,
514 CvSeq* contour,
515 int _method )
516{
517 const schar nbd = 2;
518 int deltas[MAX_SIZE];
519 CvSeqWriter writer;
520 schar *i0 = ptr, *i1, *i3, *i4 = 0;
521 int prev_s = -1, s, s_end;
522 int method = _method - 1;
523
524 CV_DbgAssert( (unsigned) _method <= CV_CHAIN_APPROX_SIMPLE );
525
526 /* initialize local state */
527 CV_INIT_3X3_DELTAS( deltas, step, 1 );
528 memcpy( dest: deltas + 8, src: deltas, n: 8 * sizeof( deltas[0] ));
529
530 /* initialize writer */
531 cvStartAppendToSeq( seq: contour, writer: &writer );
532
533 if( method < 0 )
534 ((CvChain *) contour)->origin = pt;
535
536 s_end = s = CV_IS_SEQ_HOLE( contour ) ? 0 : 4;
537
538 do
539 {
540 s = (s - 1) & 7;
541 i1 = i0 + deltas[s];
542 }
543 while( *i1 == 0 && s != s_end );
544
545 if( s == s_end ) /* single pixel domain */
546 {
547 *i0 = (schar) (nbd | -128);
548 if( method >= 0 )
549 {
550 CV_WRITE_SEQ_ELEM( pt, writer );
551 }
552 }
553 else
554 {
555 i3 = i0;
556 prev_s = s ^ 4;
557
558 /* follow border */
559 for( ;; )
560 {
561 CV_Assert(i3 != NULL);
562 s_end = s;
563 s = std::min(a: s, b: MAX_SIZE - 1);
564
565 while( s < MAX_SIZE - 1 )
566 {
567 i4 = i3 + deltas[++s];
568 CV_Assert(i4 != NULL);
569 if( *i4 != 0 )
570 break;
571 }
572 s &= 7;
573
574 /* check "right" bound */
575 if( (unsigned) (s - 1) < (unsigned) s_end )
576 {
577 *i3 = (schar) (nbd | -128);
578 }
579 else if( *i3 == 1 )
580 {
581 *i3 = nbd;
582 }
583
584 if( method < 0 )
585 {
586 schar _s = (schar) s;
587
588 CV_WRITE_SEQ_ELEM( _s, writer );
589 }
590 else
591 {
592 if( s != prev_s || method == 0 )
593 {
594 CV_WRITE_SEQ_ELEM( pt, writer );
595 prev_s = s;
596 }
597
598 pt.x += icvCodeDeltas[s].x;
599 pt.y += icvCodeDeltas[s].y;
600
601 }
602
603 if( i4 == i0 && i3 == i1 )
604 break;
605
606 i3 = i4;
607 s = (s + 4) & 7;
608 } /* end of border following loop */
609 }
610
611 cvEndWriteSeq( writer: &writer );
612
613 if( _method != CV_CHAIN_CODE )
614 cvBoundingRect( points: contour, update: 1 );
615
616 CV_DbgAssert( (writer.seq->total == 0 && writer.seq->first == 0) ||
617 writer.seq->total > writer.seq->first->count ||
618 (writer.seq->first->prev == writer.seq->first &&
619 writer.seq->first->next == writer.seq->first) );
620}
621
622
623
624/*
625 trace contour until certain point is met.
626 returns 1 if met and this is the last contour
627 encountered by a raster scan reaching the point, 0 else.
628*/
629static int
630icvTraceContour( schar *ptr, int step, schar *stop_ptr, int is_hole )
631{
632 int deltas[MAX_SIZE];
633 schar *i0 = ptr, *i1, *i3, *i4 = NULL;
634 int s, s_end;
635
636 /* initialize local state */
637 CV_INIT_3X3_DELTAS( deltas, step, 1 );
638 memcpy( dest: deltas + 8, src: deltas, n: 8 * sizeof( deltas[0] ));
639
640 CV_DbgAssert( (*i0 & -2) != 0 );
641
642 s_end = s = is_hole ? 0 : 4;
643
644 do
645 {
646 s = (s - 1) & 7;
647 i1 = i0 + deltas[s];
648 }
649 while( *i1 == 0 && s != s_end );
650
651 i3 = i0;
652
653 /* check single pixel domain */
654 if( s != s_end )
655 {
656 /* follow border */
657 for( ;; )
658 {
659 CV_Assert(i3 != NULL);
660
661 s = std::min(a: s, b: MAX_SIZE - 1);
662 while( s < MAX_SIZE - 1 )
663 {
664 i4 = i3 + deltas[++s];
665 CV_Assert(i4 != NULL);
666 if( *i4 != 0 )
667 break;
668 }
669
670 if (i3 == stop_ptr) {
671 if (!(*i3 & 0x80)) {
672 /* it's the only contour */
673 return 1;
674 }
675
676 /* check if this is the last contour */
677 /* encountered during a raster scan */
678 schar *i5;
679 int t = s;
680 while (true)
681 {
682 t = (t - 1) & 7;
683 i5 = i3 + deltas[t];
684 if (*i5 != 0)
685 break;
686 if (t == 0)
687 return 1;
688 }
689 }
690
691 if( (i4 == i0 && i3 == i1) )
692 break;
693
694 i3 = i4;
695 s = (s + 4) & 7;
696 } /* end of border following loop */
697 }
698 else {
699 return i3 == stop_ptr;
700 }
701
702 return 0;
703}
704
705
706static void
707icvFetchContourEx( schar* ptr,
708 int step,
709 CvPoint pt,
710 CvSeq* contour,
711 int _method,
712 int nbd,
713 CvRect* _rect )
714{
715 int deltas[MAX_SIZE];
716 CvSeqWriter writer;
717 schar *i0 = ptr, *i1, *i3, *i4 = NULL;
718 cv::Rect rect;
719 int prev_s = -1, s, s_end;
720 int method = _method - 1;
721
722 CV_DbgAssert( (unsigned) _method <= CV_CHAIN_APPROX_SIMPLE );
723 CV_DbgAssert( 1 < nbd && nbd < 128 );
724
725 /* initialize local state */
726 CV_INIT_3X3_DELTAS( deltas, step, 1 );
727 memcpy( dest: deltas + 8, src: deltas, n: 8 * sizeof( deltas[0] ));
728
729 /* initialize writer */
730 cvStartAppendToSeq( seq: contour, writer: &writer );
731
732 if( method < 0 )
733 ((CvChain *)contour)->origin = pt;
734
735 rect.x = rect.width = pt.x;
736 rect.y = rect.height = pt.y;
737
738 s_end = s = CV_IS_SEQ_HOLE( contour ) ? 0 : 4;
739
740 do
741 {
742 s = (s - 1) & 7;
743 i1 = i0 + deltas[s];
744 }
745 while( *i1 == 0 && s != s_end );
746
747 if( s == s_end ) /* single pixel domain */
748 {
749 *i0 = (schar) (nbd | 0x80);
750 if( method >= 0 )
751 {
752 CV_WRITE_SEQ_ELEM( pt, writer );
753 }
754 }
755 else
756 {
757 i3 = i0;
758
759 prev_s = s ^ 4;
760
761 /* follow border */
762 for( ;; )
763 {
764 CV_Assert(i3 != NULL);
765 s_end = s;
766 s = std::min(a: s, b: MAX_SIZE - 1);
767
768 while( s < MAX_SIZE - 1 )
769 {
770 i4 = i3 + deltas[++s];
771 CV_Assert(i4 != NULL);
772 if( *i4 != 0 )
773 break;
774 }
775 s &= 7;
776
777 /* check "right" bound */
778 if( (unsigned) (s - 1) < (unsigned) s_end )
779 {
780 *i3 = (schar) (nbd | 0x80);
781 }
782 else if( *i3 == 1 )
783 {
784 *i3 = (schar) nbd;
785 }
786
787 if( method < 0 )
788 {
789 schar _s = (schar) s;
790 CV_WRITE_SEQ_ELEM( _s, writer );
791 }
792 else if( s != prev_s || method == 0 )
793 {
794 CV_WRITE_SEQ_ELEM( pt, writer );
795 }
796
797 if( s != prev_s )
798 {
799 /* update bounds */
800 if( pt.x < rect.x )
801 rect.x = pt.x;
802 else if( pt.x > rect.width )
803 rect.width = pt.x;
804
805 if( pt.y < rect.y )
806 rect.y = pt.y;
807 else if( pt.y > rect.height )
808 rect.height = pt.y;
809 }
810
811 prev_s = s;
812 pt.x += icvCodeDeltas[s].x;
813 pt.y += icvCodeDeltas[s].y;
814
815 if( i4 == i0 && i3 == i1 ) break;
816
817 i3 = i4;
818 s = (s + 4) & 7;
819 } /* end of border following loop */
820 }
821
822 rect.width -= rect.x - 1;
823 rect.height -= rect.y - 1;
824
825 cvEndWriteSeq( writer: &writer );
826
827 if( _method != CV_CHAIN_CODE )
828 ((CvContour*)contour)->rect = cvRect(rc: rect);
829
830 CV_DbgAssert( (writer.seq->total == 0 && writer.seq->first == 0) ||
831 writer.seq->total > writer.seq->first->count ||
832 (writer.seq->first->prev == writer.seq->first &&
833 writer.seq->first->next == writer.seq->first) );
834
835 if( _rect ) *_rect = cvRect(rc: rect);
836}
837
838
839static int
840icvTraceContour_32s( int *ptr, int step, int *stop_ptr, int is_hole )
841{
842 CV_Assert(ptr != NULL);
843 int deltas[MAX_SIZE];
844 int *i0 = ptr, *i1, *i3, *i4 = NULL;
845 int s, s_end;
846 const int right_flag = INT_MIN;
847 const int new_flag = (int)((unsigned)INT_MIN >> 1);
848 const int value_mask = ~(right_flag | new_flag);
849 const int ccomp_val = *i0 & value_mask;
850
851 /* initialize local state */
852 CV_INIT_3X3_DELTAS( deltas, step, 1 );
853 memcpy( dest: deltas + 8, src: deltas, n: 8 * sizeof( deltas[0] ));
854
855 s_end = s = is_hole ? 0 : 4;
856
857 do
858 {
859 s = (s - 1) & 7;
860 i1 = i0 + deltas[s];
861 }
862 while( (*i1 & value_mask) != ccomp_val && s != s_end );
863
864 i3 = i0;
865
866 /* check single pixel domain */
867 if( s != s_end )
868 {
869 /* follow border */
870 for( ;; )
871 {
872 CV_Assert(i3 != NULL);
873 s = std::min(a: s, b: MAX_SIZE - 1);
874
875 while( s < MAX_SIZE - 1 )
876 {
877 i4 = i3 + deltas[++s];
878 CV_Assert(i4 != NULL);
879 if( (*i4 & value_mask) == ccomp_val )
880 break;
881 }
882
883 if( i3 == stop_ptr || (i4 == i0 && i3 == i1) )
884 break;
885
886 i3 = i4;
887 s = (s + 4) & 7;
888 } /* end of border following loop */
889 }
890 return i3 == stop_ptr;
891}
892
893
894static void
895icvFetchContourEx_32s( int* ptr,
896 int step,
897 CvPoint pt,
898 CvSeq* contour,
899 int _method,
900 CvRect* _rect )
901{
902 CV_Assert(ptr != NULL);
903 int deltas[MAX_SIZE];
904 CvSeqWriter writer;
905 int *i0 = ptr, *i1, *i3, *i4;
906 cv::Rect rect;
907 int prev_s = -1, s, s_end;
908 int method = _method - 1;
909 const int right_flag = INT_MIN;
910 const int new_flag = (int)((unsigned)INT_MIN >> 1);
911 const int value_mask = ~(right_flag | new_flag);
912 const int ccomp_val = *i0 & value_mask;
913 const int nbd0 = ccomp_val | new_flag;
914 const int nbd1 = nbd0 | right_flag;
915
916 CV_DbgAssert( (unsigned) _method <= CV_CHAIN_APPROX_SIMPLE );
917
918 /* initialize local state */
919 CV_INIT_3X3_DELTAS( deltas, step, 1 );
920 memcpy( dest: deltas + 8, src: deltas, n: 8 * sizeof( deltas[0] ));
921
922 /* initialize writer */
923 cvStartAppendToSeq( seq: contour, writer: &writer );
924
925 if( method < 0 )
926 ((CvChain *)contour)->origin = pt;
927
928 rect.x = rect.width = pt.x;
929 rect.y = rect.height = pt.y;
930
931 s_end = s = CV_IS_SEQ_HOLE( contour ) ? 0 : 4;
932
933 do
934 {
935 s = (s - 1) & 7;
936 i1 = i0 + deltas[s];
937 }
938 while( (*i1 & value_mask) != ccomp_val && s != s_end && ( s < MAX_SIZE - 1 ) );
939
940 if( s == s_end ) /* single pixel domain */
941 {
942 *i0 = nbd1;
943 if( method >= 0 )
944 {
945 CV_WRITE_SEQ_ELEM( pt, writer );
946 }
947 }
948 else
949 {
950 i3 = i0;
951 prev_s = s ^ 4;
952
953 /* follow border */
954 for( ;; )
955 {
956 CV_Assert(i3 != NULL);
957 s_end = s;
958
959 do
960 {
961 i4 = i3 + deltas[++s];
962 CV_Assert(i4 != NULL);
963 }
964 while( (*i4 & value_mask) != ccomp_val && ( s < MAX_SIZE - 1 ) );
965 s &= 7;
966
967 /* check "right" bound */
968 if( (unsigned) (s - 1) < (unsigned) s_end )
969 {
970 *i3 = nbd1;
971 }
972 else if( *i3 == ccomp_val )
973 {
974 *i3 = nbd0;
975 }
976
977 if( method < 0 )
978 {
979 schar _s = (schar) s;
980 CV_WRITE_SEQ_ELEM( _s, writer );
981 }
982 else if( s != prev_s || method == 0 )
983 {
984 CV_WRITE_SEQ_ELEM( pt, writer );
985 }
986
987 if( s != prev_s )
988 {
989 /* update bounds */
990 if( pt.x < rect.x )
991 rect.x = pt.x;
992 else if( pt.x > rect.width )
993 rect.width = pt.x;
994
995 if( pt.y < rect.y )
996 rect.y = pt.y;
997 else if( pt.y > rect.height )
998 rect.height = pt.y;
999 }
1000
1001 prev_s = s;
1002 pt.x += icvCodeDeltas[s].x;
1003 pt.y += icvCodeDeltas[s].y;
1004
1005 if( i4 == i0 && i3 == i1 ) break;
1006
1007 i3 = i4;
1008 s = (s + 4) & 7;
1009 } /* end of border following loop */
1010 }
1011
1012 rect.width -= rect.x - 1;
1013 rect.height -= rect.y - 1;
1014
1015 cvEndWriteSeq( writer: &writer );
1016
1017 if( _method != CV_CHAIN_CODE )
1018 ((CvContour*)contour)->rect = cvRect(rc: rect);
1019
1020 CV_DbgAssert( (writer.seq->total == 0 && writer.seq->first == 0) ||
1021 writer.seq->total > writer.seq->first->count ||
1022 (writer.seq->first->prev == writer.seq->first &&
1023 writer.seq->first->next == writer.seq->first) );
1024
1025 if (_rect) *_rect = cvRect(rc: rect);
1026}
1027
1028
1029CvSeq *
1030cvFindNextContour( CvContourScanner scanner )
1031{
1032 if( !scanner )
1033 CV_Error( cv::Error::StsNullPtr, "" );
1034
1035 CV_Assert(scanner->img_step >= 0);
1036
1037 icvEndProcessContour( scanner );
1038
1039 /* initialize local state */
1040 schar* img0 = scanner->img0;
1041 schar* img = scanner->img;
1042 int step = scanner->img_step;
1043 int step_i = step / sizeof(int);
1044 int x = scanner->pt.x;
1045 int y = scanner->pt.y;
1046 int width = scanner->img_size.width;
1047 int height = scanner->img_size.height;
1048 int mode = scanner->mode;
1049 cv::Point2i lnbd = scanner->lnbd;
1050 int nbd = scanner->nbd;
1051 int prev = img[x - 1];
1052 int new_mask = -2;
1053
1054 if( mode == CV_RETR_FLOODFILL )
1055 {
1056 prev = ((int*)img)[x - 1];
1057 new_mask = INT_MIN / 2;
1058 }
1059
1060 for( ; y < height; y++, img += step )
1061 {
1062 int* img0_i = 0;
1063 int* img_i = 0;
1064 int p = 0;
1065
1066 if( mode == CV_RETR_FLOODFILL )
1067 {
1068 img0_i = (int*)img0;
1069 img_i = (int*)img;
1070 }
1071
1072 for( ; x < width; x++ )
1073 {
1074 if( img_i )
1075 {
1076 for( ; x < width && ((p = img_i[x]) == prev || (p & ~new_mask) == (prev & ~new_mask)); x++ )
1077 prev = p;
1078 }
1079 else
1080 {
1081#if (CV_SIMD || CV_SIMD_SCALABLE)
1082 if ((p = img[x]) != prev)
1083 {
1084 goto _next_contour;
1085 }
1086 else
1087 {
1088 v_uint8 v_prev = vx_setall_u8(v: (uchar)prev);
1089 for (; x <= width - VTraits<v_uint8>::vlanes(); x += VTraits<v_uint8>::vlanes())
1090 {
1091 v_uint8 vmask = (v_ne(a: vx_load(ptr: (uchar *)(img + x)), b: v_prev));
1092 if (v_check_any(a: vmask))
1093 {
1094 p = img[(x += v_scan_forward(a: vmask))];
1095 goto _next_contour;
1096 }
1097 }
1098 }
1099#endif
1100 for( ; x < width && (p = img[x]) == prev; x++ )
1101 ;
1102 }
1103
1104 if( x >= width )
1105 break;
1106#if (CV_SIMD || CV_SIMD_SCALABLE)
1107 _next_contour:
1108#endif
1109 {
1110 _CvContourInfo *par_info = 0;
1111 CvSeq *seq = 0;
1112 int is_hole = 0;
1113 cv::Point2i origin;
1114
1115 /* if not external contour */
1116 if( (!img_i && !(prev == 0 && p == 1)) ||
1117 (img_i && !(((prev & new_mask) != 0 || prev == 0) && (p & new_mask) == 0)) )
1118 {
1119 /* check hole */
1120 if( (!img_i && (p != 0 || prev < 1)) ||
1121 (img_i && ((prev & new_mask) != 0 || (p & new_mask) != 0)))
1122 goto resume_scan;
1123
1124 if( prev & new_mask )
1125 {
1126 lnbd.x = x - 1;
1127 }
1128 is_hole = 1;
1129 }
1130
1131 if( mode == 0 && (is_hole || img0[lnbd.y * static_cast<size_t>(step) + lnbd.x] > 0) )
1132 goto resume_scan;
1133
1134 origin.y = y;
1135 origin.x = x - is_hole;
1136
1137 /* find contour parent */
1138 if( mode <= 1 || (!is_hole && (mode == CV_RETR_CCOMP || mode == CV_RETR_FLOODFILL)) || lnbd.x <= 0 )
1139 {
1140 par_info = &(scanner->frame_info);
1141 }
1142 else
1143 {
1144 int lval = (img0_i ?
1145 img0_i[lnbd.y * static_cast<size_t>(step_i) + lnbd.x] :
1146 (int)img0[lnbd.y * static_cast<size_t>(step) + lnbd.x]) & 0x7f;
1147 _CvContourInfo *cur = scanner->cinfo_table[lval];
1148
1149 /* find the first bounding contour */
1150 while( cur )
1151 {
1152 if( (unsigned) (lnbd.x - cur->rect.x) < (unsigned) cur->rect.width &&
1153 (unsigned) (lnbd.y - cur->rect.y) < (unsigned) cur->rect.height )
1154 {
1155 if( par_info )
1156 {
1157 if( (img0_i &&
1158 icvTraceContour_32s( ptr: img0_i + par_info->origin.y * static_cast<size_t>(step_i) +
1159 par_info->origin.x, step: step_i, stop_ptr: img_i + lnbd.x,
1160 is_hole: par_info->is_hole ) > 0) ||
1161 (!img0_i &&
1162 icvTraceContour( ptr: img0 + par_info->origin.y * static_cast<size_t>(step) +
1163 par_info->origin.x, step, stop_ptr: img + lnbd.x,
1164 is_hole: par_info->is_hole ) > 0) )
1165 break;
1166 }
1167 par_info = cur;
1168 }
1169 cur = cur->next;
1170 }
1171
1172 CV_Assert( par_info != 0 );
1173
1174 /* if current contour is a hole and previous contour is a hole or
1175 current contour is external and previous contour is external then
1176 the parent of the contour is the parent of the previous contour else
1177 the parent is the previous contour itself. */
1178 if( par_info->is_hole == is_hole )
1179 {
1180 par_info = par_info->parent;
1181 /* every contour must have a parent
1182 (at least, the frame of the image) */
1183 if( !par_info )
1184 par_info = &(scanner->frame_info);
1185 }
1186
1187 /* hole flag of the parent must differ from the flag of the contour */
1188 CV_Assert( par_info->is_hole != is_hole );
1189 if( par_info->contour == 0 ) /* removed contour */
1190 goto resume_scan;
1191 }
1192
1193 lnbd.x = x - is_hole;
1194
1195 cvSaveMemStoragePos( storage: scanner->storage2, pos: &(scanner->backup_pos) );
1196
1197 seq = cvCreateSeq( seq_flags: scanner->seq_type1, header_size: scanner->header_size1,
1198 elem_size: scanner->elem_size1, storage: scanner->storage1 );
1199 seq->flags |= is_hole ? CV_SEQ_FLAG_HOLE : 0;
1200
1201 /* initialize header */
1202 _CvContourInfo *l_cinfo = 0;
1203 if( mode <= 1 )
1204 {
1205 l_cinfo = &(scanner->cinfo_temp);
1206 icvFetchContour( ptr: img + x - is_hole, step,
1207 pt: cvPoint( x: origin.x + scanner->offset.x,
1208 y: origin.y + scanner->offset.y),
1209 contour: seq, method: scanner->approx_method1 );
1210 }
1211 else
1212 {
1213 cvSetAdd(set_header: scanner->cinfo_set, elem: 0, inserted_elem: (CvSetElem**)&l_cinfo);
1214 CV_Assert(l_cinfo);
1215 int lval;
1216
1217 if( img_i )
1218 {
1219 lval = img_i[x - is_hole] & 127;
1220 icvFetchContourEx_32s(ptr: img_i + x - is_hole, step: step_i,
1221 pt: cvPoint( x: origin.x + scanner->offset.x,
1222 y: origin.y + scanner->offset.y),
1223 contour: seq, method: scanner->approx_method1,
1224 rect: &(l_cinfo->rect) );
1225 }
1226 else
1227 {
1228 lval = nbd;
1229 // change nbd
1230 nbd = (nbd + 1) & 127;
1231 nbd += nbd == 0 ? 3 : 0;
1232 icvFetchContourEx( ptr: img + x - is_hole, step,
1233 pt: cvPoint( x: origin.x + scanner->offset.x,
1234 y: origin.y + scanner->offset.y),
1235 contour: seq, method: scanner->approx_method1,
1236 nbd: lval, rect: &(l_cinfo->rect) );
1237 }
1238 l_cinfo->rect.x -= scanner->offset.x;
1239 l_cinfo->rect.y -= scanner->offset.y;
1240
1241 l_cinfo->next = scanner->cinfo_table[lval];
1242 scanner->cinfo_table[lval] = l_cinfo;
1243 }
1244
1245 l_cinfo->is_hole = is_hole;
1246 l_cinfo->contour = seq;
1247 l_cinfo->origin = cvPoint(pt: origin);
1248 l_cinfo->parent = par_info;
1249
1250 if( scanner->approx_method1 != scanner->approx_method2 )
1251 {
1252 l_cinfo->contour = icvApproximateChainTC89( chain: (CvChain *) seq,
1253 header_size: scanner->header_size2,
1254 storage: scanner->storage2,
1255 method: scanner->approx_method2 );
1256 cvClearMemStorage( storage: scanner->storage1 );
1257 }
1258
1259 l_cinfo->contour->v_prev = l_cinfo->parent->contour;
1260
1261 if( par_info->contour == 0 )
1262 {
1263 l_cinfo->contour = 0;
1264 if( scanner->storage1 == scanner->storage2 )
1265 {
1266 cvRestoreMemStoragePos( storage: scanner->storage1, pos: &(scanner->backup_pos) );
1267 }
1268 else
1269 {
1270 cvClearMemStorage( storage: scanner->storage1 );
1271 }
1272 p = img[x];
1273 goto resume_scan;
1274 }
1275
1276 cvSaveMemStoragePos( storage: scanner->storage2, pos: &(scanner->backup_pos2) );
1277 scanner->l_cinfo = l_cinfo;
1278 scanner->pt.x = !img_i ? x + 1 : x + 1 - is_hole;
1279 scanner->pt.y = y;
1280 scanner->lnbd = cvPoint(pt: lnbd);
1281 scanner->img = (schar *) img;
1282 scanner->nbd = nbd;
1283 return l_cinfo->contour;
1284 }
1285 resume_scan:
1286 {
1287 prev = p;
1288 /* update lnbd */
1289 if( prev & -2 )
1290 {
1291 lnbd.x = x;
1292 }
1293 }
1294 } /* end of loop on x */
1295
1296 lnbd.x = 0;
1297 lnbd.y = y + 1;
1298 x = 1;
1299 prev = 0;
1300 } /* end of loop on y */
1301
1302 return 0;
1303}
1304
1305
1306/*
1307 The function add to tree the last retrieved/substituted contour,
1308 releases temp_storage, restores state of dst_storage (if needed), and
1309 returns pointer to root of the contour tree */
1310CV_IMPL CvSeq *
1311cvEndFindContours( CvContourScanner * _scanner )
1312{
1313 CvContourScanner scanner;
1314 CvSeq *first = 0;
1315
1316 if( !_scanner )
1317 CV_Error( cv::Error::StsNullPtr, "" );
1318 scanner = *_scanner;
1319
1320 if( scanner )
1321 {
1322 icvEndProcessContour( scanner );
1323
1324 if( scanner->storage1 != scanner->storage2 )
1325 cvReleaseMemStorage( storage: &(scanner->storage1) );
1326
1327 if( scanner->cinfo_storage )
1328 cvReleaseMemStorage( storage: &(scanner->cinfo_storage) );
1329
1330 first = scanner->frame.v_next;
1331 cvFree( _scanner );
1332 }
1333
1334 return first;
1335}
1336
1337
1338#define ICV_SINGLE 0
1339#define ICV_CONNECTING_ABOVE 1
1340#define ICV_CONNECTING_BELOW -1
1341
1342#define CV_GET_WRITTEN_ELEM( writer ) ((writer).ptr - (writer).seq->elem_size)
1343
1344typedef struct CvLinkedRunPoint
1345{
1346 struct CvLinkedRunPoint* link;
1347 struct CvLinkedRunPoint* next;
1348 CvPoint pt;
1349}
1350CvLinkedRunPoint;
1351
1352inline int findStartContourPoint(uchar *src_data, CvSize img_size, int j)
1353{
1354#if (CV_SIMD || CV_SIMD_SCALABLE)
1355 v_uint8 v_zero = vx_setzero_u8();
1356 for (; j <= img_size.width - VTraits<v_uint8>::vlanes(); j += VTraits<v_uint8>::vlanes())
1357 {
1358 v_uint8 vmask = (v_ne(a: vx_load(ptr: (uchar *)(src_data + j)), b: v_zero));
1359 if (v_check_any(a: vmask))
1360 {
1361 j += v_scan_forward(a: vmask);
1362 return j;
1363 }
1364 }
1365#endif
1366 for (; j < img_size.width && !src_data[j]; ++j)
1367 ;
1368 return j;
1369}
1370
1371inline int findEndContourPoint(uchar *src_data, CvSize img_size, int j)
1372{
1373#if (CV_SIMD || CV_SIMD_SCALABLE)
1374 if (j < img_size.width && !src_data[j])
1375 {
1376 return j;
1377 }
1378 else
1379 {
1380 v_uint8 v_zero = vx_setzero_u8();
1381 for (; j <= img_size.width - VTraits<v_uint8>::vlanes(); j += VTraits<v_uint8>::vlanes())
1382 {
1383 v_uint8 vmask = (v_eq(a: vx_load(ptr: (uchar *)(src_data + j)), b: v_zero));
1384 if (v_check_any(a: vmask))
1385 {
1386 j += v_scan_forward(a: vmask);
1387 return j;
1388 }
1389 }
1390 }
1391#endif
1392 for (; j < img_size.width && src_data[j]; ++j)
1393 ;
1394
1395 return j;
1396}
1397
1398static int
1399icvFindContoursInInterval( const CvArr* src,
1400 /*int minValue, int maxValue,*/
1401 CvMemStorage* storage,
1402 CvSeq** result,
1403 int contourHeaderSize )
1404{
1405 int count = 0;
1406 cv::Ptr<CvMemStorage> storage00;
1407 cv::Ptr<CvMemStorage> storage01;
1408 CvSeq* first = 0;
1409
1410 int j, k, n;
1411
1412 uchar* src_data = 0;
1413 int img_step = 0;
1414 cv::Size img_size;
1415
1416 int connect_flag;
1417 int lower_total;
1418 int upper_total;
1419 int all_total;
1420
1421 CvSeq* runs;
1422 CvLinkedRunPoint tmp;
1423 CvLinkedRunPoint* tmp_prev;
1424 CvLinkedRunPoint* upper_line = 0;
1425 CvLinkedRunPoint* lower_line = 0;
1426 CvLinkedRunPoint* last_elem;
1427
1428 CvLinkedRunPoint* upper_run = 0;
1429 CvLinkedRunPoint* lower_run = 0;
1430 CvLinkedRunPoint* prev_point = 0;
1431
1432 CvSeqWriter writer_ext;
1433 CvSeqWriter writer_int;
1434 CvSeqWriter writer;
1435 CvSeqReader reader;
1436
1437 CvSeq* external_contours;
1438 CvSeq* internal_contours;
1439 CvSeq* prev = 0;
1440
1441 if( !storage )
1442 CV_Error( cv::Error::StsNullPtr, "NULL storage pointer" );
1443
1444 if( !result )
1445 CV_Error( cv::Error::StsNullPtr, "NULL double CvSeq pointer" );
1446
1447 if( contourHeaderSize < (int)sizeof(CvContour))
1448 CV_Error( cv::Error::StsBadSize, "Contour header size must be >= sizeof(CvContour)" );
1449
1450 storage00.reset(ptr: cvCreateChildMemStorage(parent: storage));
1451 storage01.reset(ptr: cvCreateChildMemStorage(parent: storage));
1452
1453 CvMat stub, *mat;
1454
1455 mat = cvGetMat( arr: src, header: &stub );
1456 if( !CV_IS_MASK_ARR(mat))
1457 CV_Error( cv::Error::StsBadArg, "Input array must be 8uC1 or 8sC1" );
1458 src_data = mat->data.ptr;
1459 img_step = mat->step;
1460 img_size = cvGetMatSize(mat);
1461
1462 // Create temporary sequences
1463 runs = cvCreateSeq(seq_flags: 0, header_size: sizeof(CvSeq), elem_size: sizeof(CvLinkedRunPoint), storage: storage00 );
1464 cvStartAppendToSeq( seq: runs, writer: &writer );
1465
1466 cvStartWriteSeq( seq_flags: 0, header_size: sizeof(CvSeq), elem_size: sizeof(CvLinkedRunPoint*), storage: storage01, writer: &writer_ext );
1467 cvStartWriteSeq( seq_flags: 0, header_size: sizeof(CvSeq), elem_size: sizeof(CvLinkedRunPoint*), storage: storage01, writer: &writer_int );
1468
1469 tmp_prev = &(tmp);
1470 tmp_prev->next = 0;
1471 tmp_prev->link = 0;
1472
1473 // First line. None of runs is binded
1474 tmp.pt.x = 0;
1475 tmp.pt.y = 0;
1476 CV_WRITE_SEQ_ELEM( tmp, writer );
1477 upper_line = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer );
1478
1479 tmp_prev = upper_line;
1480 for( j = 0; j < img_size.width; )
1481 {
1482 j = findStartContourPoint(src_data, img_size: cvSize(sz: img_size), j);
1483
1484 if( j == img_size.width )
1485 break;
1486
1487 tmp.pt.x = j;
1488 CV_WRITE_SEQ_ELEM( tmp, writer );
1489 tmp_prev->next = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer );
1490 tmp_prev = tmp_prev->next;
1491
1492 j = findEndContourPoint(src_data, img_size: cvSize(sz: img_size), j: j + 1);
1493
1494 tmp.pt.x = j - 1;
1495 CV_WRITE_SEQ_ELEM( tmp, writer );
1496 tmp_prev->next = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer );
1497 tmp_prev->link = tmp_prev->next;
1498 // First point of contour
1499 CV_WRITE_SEQ_ELEM( tmp_prev, writer_ext );
1500 tmp_prev = tmp_prev->next;
1501 }
1502 cvFlushSeqWriter( writer: &writer );
1503 upper_line = upper_line->next;
1504 upper_total = runs->total - 1;
1505 last_elem = tmp_prev;
1506 tmp_prev->next = 0;
1507
1508 for( int i = 1; i < img_size.height; i++ )
1509 {
1510//------// Find runs in next line
1511 src_data += img_step;
1512 tmp.pt.y = i;
1513 all_total = runs->total;
1514 for( j = 0; j < img_size.width; )
1515 {
1516 j = findStartContourPoint(src_data, img_size: cvSize(sz: img_size), j);
1517
1518 if( j == img_size.width ) break;
1519
1520 tmp.pt.x = j;
1521 CV_WRITE_SEQ_ELEM( tmp, writer );
1522 tmp_prev->next = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer );
1523 tmp_prev = tmp_prev->next;
1524
1525 j = findEndContourPoint(src_data, img_size: cvSize(sz: img_size), j: j + 1);
1526
1527 tmp.pt.x = j - 1;
1528 CV_WRITE_SEQ_ELEM( tmp, writer );
1529 tmp_prev = tmp_prev->next = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer );
1530 }//j
1531 cvFlushSeqWriter( writer: &writer );
1532 lower_line = last_elem->next;
1533 lower_total = runs->total - all_total;
1534 last_elem = tmp_prev;
1535 tmp_prev->next = 0;
1536//------//
1537//------// Find links between runs of lower_line and upper_line
1538 upper_run = upper_line;
1539 lower_run = lower_line;
1540 connect_flag = ICV_SINGLE;
1541
1542 for( k = 0, n = 0; k < upper_total/2 && n < lower_total/2; )
1543 {
1544 switch( connect_flag )
1545 {
1546 case ICV_SINGLE:
1547 if( upper_run->next->pt.x < lower_run->next->pt.x )
1548 {
1549 if( upper_run->next->pt.x >= lower_run->pt.x -1 )
1550 {
1551 lower_run->link = upper_run;
1552 connect_flag = ICV_CONNECTING_ABOVE;
1553 prev_point = upper_run->next;
1554 }
1555 else
1556 upper_run->next->link = upper_run;
1557 k++;
1558 upper_run = upper_run->next->next;
1559 }
1560 else
1561 {
1562 if( upper_run->pt.x <= lower_run->next->pt.x +1 )
1563 {
1564 lower_run->link = upper_run;
1565 connect_flag = ICV_CONNECTING_BELOW;
1566 prev_point = lower_run->next;
1567 }
1568 else
1569 {
1570 lower_run->link = lower_run->next;
1571 // First point of contour
1572 CV_WRITE_SEQ_ELEM( lower_run, writer_ext );
1573 }
1574 n++;
1575 lower_run = lower_run->next->next;
1576 }
1577 break;
1578 case ICV_CONNECTING_ABOVE:
1579 if( upper_run->pt.x > lower_run->next->pt.x +1 )
1580 {
1581 prev_point->link = lower_run->next;
1582 connect_flag = ICV_SINGLE;
1583 n++;
1584 lower_run = lower_run->next->next;
1585 }
1586 else
1587 {
1588 prev_point->link = upper_run;
1589 if( upper_run->next->pt.x < lower_run->next->pt.x )
1590 {
1591 k++;
1592 prev_point = upper_run->next;
1593 upper_run = upper_run->next->next;
1594 }
1595 else
1596 {
1597 connect_flag = ICV_CONNECTING_BELOW;
1598 prev_point = lower_run->next;
1599 n++;
1600 lower_run = lower_run->next->next;
1601 }
1602 }
1603 break;
1604 case ICV_CONNECTING_BELOW:
1605 if( lower_run->pt.x > upper_run->next->pt.x +1 )
1606 {
1607 upper_run->next->link = prev_point;
1608 connect_flag = ICV_SINGLE;
1609 k++;
1610 upper_run = upper_run->next->next;
1611 }
1612 else
1613 {
1614 // First point of contour
1615 CV_WRITE_SEQ_ELEM( lower_run, writer_int );
1616
1617 lower_run->link = prev_point;
1618 if( lower_run->next->pt.x < upper_run->next->pt.x )
1619 {
1620 n++;
1621 prev_point = lower_run->next;
1622 lower_run = lower_run->next->next;
1623 }
1624 else
1625 {
1626 connect_flag = ICV_CONNECTING_ABOVE;
1627 k++;
1628 prev_point = upper_run->next;
1629 upper_run = upper_run->next->next;
1630 }
1631 }
1632 break;
1633 }
1634 }// k, n
1635
1636 for( ; n < lower_total/2; n++ )
1637 {
1638 if( connect_flag != ICV_SINGLE )
1639 {
1640 prev_point->link = lower_run->next;
1641 connect_flag = ICV_SINGLE;
1642 lower_run = lower_run->next->next;
1643 continue;
1644 }
1645 lower_run->link = lower_run->next;
1646
1647 //First point of contour
1648 CV_WRITE_SEQ_ELEM( lower_run, writer_ext );
1649
1650 lower_run = lower_run->next->next;
1651 }
1652
1653 for( ; k < upper_total/2; k++ )
1654 {
1655 if( connect_flag != ICV_SINGLE )
1656 {
1657 upper_run->next->link = prev_point;
1658 connect_flag = ICV_SINGLE;
1659 upper_run = upper_run->next->next;
1660 continue;
1661 }
1662 upper_run->next->link = upper_run;
1663 upper_run = upper_run->next->next;
1664 }
1665 upper_line = lower_line;
1666 upper_total = lower_total;
1667 }//i
1668
1669 upper_run = upper_line;
1670
1671 //the last line of image
1672 for( k = 0; k < upper_total/2; k++ )
1673 {
1674 upper_run->next->link = upper_run;
1675 upper_run = upper_run->next->next;
1676 }
1677
1678//------//
1679//------//Find end read contours
1680 external_contours = cvEndWriteSeq( writer: &writer_ext );
1681 internal_contours = cvEndWriteSeq( writer: &writer_int );
1682
1683 for( k = 0; k < 2; k++ )
1684 {
1685 CvSeq* contours = k == 0 ? external_contours : internal_contours;
1686
1687 cvStartReadSeq( seq: contours, reader: &reader );
1688
1689 for( j = 0; j < contours->total; j++, count++ )
1690 {
1691 CvLinkedRunPoint* p_temp;
1692 CvLinkedRunPoint* p00;
1693 CvLinkedRunPoint* p01;
1694 CvSeq* contour;
1695
1696 CV_READ_SEQ_ELEM( p00, reader );
1697 p01 = p00;
1698
1699 if( !p00->link )
1700 continue;
1701
1702 cvStartWriteSeq( CV_SEQ_ELTYPE_POINT | CV_SEQ_POLYLINE | CV_SEQ_FLAG_CLOSED,
1703 header_size: contourHeaderSize, elem_size: sizeof(CvPoint), storage, writer: &writer );
1704 do
1705 {
1706 CV_WRITE_SEQ_ELEM( p00->pt, writer );
1707 p_temp = p00;
1708 p00 = p00->link;
1709 p_temp->link = 0;
1710 }
1711 while( p00 != p01 );
1712
1713 contour = cvEndWriteSeq( writer: &writer );
1714 cvBoundingRect( points: contour, update: 1 );
1715
1716 if( k != 0 )
1717 contour->flags |= CV_SEQ_FLAG_HOLE;
1718
1719 if( !first )
1720 prev = first = contour;
1721 else
1722 {
1723 contour->h_prev = prev;
1724 prev = prev->h_next = contour;
1725 }
1726 }
1727 }
1728
1729 if( !first )
1730 count = -1;
1731
1732 if( result )
1733 *result = first;
1734
1735 return count;
1736}
1737
1738static int
1739cvFindContours_Impl( void* img, CvMemStorage* storage,
1740 CvSeq** firstContour, int cntHeaderSize,
1741 int mode,
1742 int method, CvPoint offset, int needFillBorder )
1743{
1744 CvContourScanner scanner = 0;
1745 CvSeq *contour = 0;
1746 int count = -1;
1747
1748 if( !firstContour )
1749 CV_Error( cv::Error::StsNullPtr, "NULL double CvSeq pointer" );
1750
1751 *firstContour = 0;
1752
1753 if( method == CV_LINK_RUNS )
1754 {
1755 if( offset.x != 0 || offset.y != 0 )
1756 CV_Error( cv::Error::StsOutOfRange,
1757 "Nonzero offset is not supported in CV_LINK_RUNS yet" );
1758
1759 count = icvFindContoursInInterval( src: img, storage, result: firstContour, contourHeaderSize: cntHeaderSize );
1760 }
1761 else
1762 {
1763 try
1764 {
1765 scanner = cvStartFindContours_Impl( img: img, storage, header_size: cntHeaderSize, mode, method, offset,
1766 needFillBorder);
1767
1768 do
1769 {
1770 count++;
1771 contour = cvFindNextContour( scanner );
1772 }
1773 while( contour != 0 );
1774 }
1775 catch(...)
1776 {
1777 if( scanner )
1778 cvEndFindContours(scanner: &scanner);
1779 throw;
1780 }
1781
1782 *firstContour = cvEndFindContours( scanner: &scanner );
1783 }
1784
1785 return count;
1786}
1787
1788/*F///////////////////////////////////////////////////////////////////////////////////////
1789// Name: cvFindContours
1790// Purpose:
1791// Finds all the contours on the bi-level image.
1792// Context:
1793// Parameters:
1794// img - source image.
1795// Non-zero pixels are considered as 1-pixels
1796// and zero pixels as 0-pixels.
1797// step - full width of source image in bytes.
1798// size - width and height of the image in pixels
1799// storage - pointer to storage where will the output contours be placed.
1800// header_size - header size of resulting contours
1801// mode - mode of contour retrieval.
1802// method - method of approximation that is applied to contours
1803// first_contour - pointer to first contour pointer
1804// Returns:
1805// CV_OK or error code
1806// Notes:
1807//F*/
1808CV_IMPL int
1809cvFindContours( void* img, CvMemStorage* storage,
1810 CvSeq** firstContour, int cntHeaderSize,
1811 int mode,
1812 int method, CvPoint offset )
1813{
1814 return cvFindContours_Impl(img, storage, firstContour, cntHeaderSize, mode, method, offset, needFillBorder: 1);
1815}
1816
1817void cv::findContours_legacy( InputArray _image, OutputArrayOfArrays _contours,
1818 OutputArray _hierarchy, int mode, int method, Point offset )
1819{
1820 CV_INSTRUMENT_REGION();
1821
1822 // Sanity check: output must be of type vector<vector<Point>>
1823 CV_Assert((_contours.kind() == _InputArray::STD_VECTOR_VECTOR || _contours.kind() == _InputArray::STD_VECTOR_MAT ||
1824 _contours.kind() == _InputArray::STD_VECTOR_UMAT));
1825
1826 CV_Assert(_contours.empty() || (_contours.channels() == 2 && _contours.depth() == CV_32S));
1827
1828 Mat image0 = _image.getMat(), image;
1829 Point offset0(0, 0);
1830 if(method != CV_LINK_RUNS)
1831 {
1832 offset0 = Point(-1, -1);
1833 copyMakeBorder(src: image0, dst: image, top: 1, bottom: 1, left: 1, right: 1, borderType: BORDER_CONSTANT | BORDER_ISOLATED, value: Scalar(0));
1834 }
1835 else
1836 {
1837 image = image0;
1838 }
1839 MemStorage storage(cvCreateMemStorage());
1840 CvMat _cimage = cvMat(m: image);
1841 CvSeq* _ccontours = 0;
1842 if( _hierarchy.needed() )
1843 _hierarchy.clear();
1844 cvFindContours_Impl(img: &_cimage, storage, firstContour: &_ccontours, cntHeaderSize: sizeof(CvContour), mode, method, offset: cvPoint(pt: offset0 + offset), needFillBorder: 0);
1845 if( !_ccontours )
1846 {
1847 _contours.clear();
1848 return;
1849 }
1850 Seq<CvSeq*> all_contours(cvTreeToNodeSeq( first: _ccontours, header_size: sizeof(CvSeq), storage ));
1851 int i, total = (int)all_contours.size();
1852 _contours.create(rows: total, cols: 1, type: 0, i: -1, allowTransposed: true);
1853 SeqIterator<CvSeq*> it = all_contours.begin();
1854 for( i = 0; i < total; i++, ++it )
1855 {
1856 CvSeq* c = *it;
1857 ((CvContour*)c)->color = (int)i;
1858 _contours.create(rows: (int)c->total, cols: 1, CV_32SC2, i, allowTransposed: true);
1859 Mat ci = _contours.getMat(i);
1860 CV_Assert( ci.isContinuous() );
1861 cvCvtSeqToArray(seq: c, elements: ci.ptr());
1862 }
1863
1864 if( _hierarchy.needed() )
1865 {
1866 _hierarchy.create(rows: 1, cols: total, CV_32SC4, i: -1, allowTransposed: true);
1867 Vec4i* hierarchy = _hierarchy.getMat().ptr<Vec4i>();
1868
1869 it = all_contours.begin();
1870 for( i = 0; i < total; i++, ++it )
1871 {
1872 CvSeq* c = *it;
1873 int h_next = c->h_next ? ((CvContour*)c->h_next)->color : -1;
1874 int h_prev = c->h_prev ? ((CvContour*)c->h_prev)->color : -1;
1875 int v_next = c->v_next ? ((CvContour*)c->v_next)->color : -1;
1876 int v_prev = c->v_prev ? ((CvContour*)c->v_prev)->color : -1;
1877 hierarchy[i] = Vec4i(h_next, h_prev, v_next, v_prev);
1878 }
1879 }
1880}
1881
1882void cv::findContours_legacy( InputArray _image, OutputArrayOfArrays _contours,
1883 int mode, int method, Point offset)
1884{
1885 CV_INSTRUMENT_REGION();
1886
1887 findContours_legacy(_image, _contours, hierarchy: noArray(), mode, method, offset);
1888}
1889
1890/* End of file. */
1891

Provided by KDAB

Privacy Policy
Improve your Profiling and Debugging skills
Find out more

source code of opencv/modules/imgproc/src/contours.cpp