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
45	using 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
54	static 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
57	CV_IMPL void
58	cvStartReadChainPoints( 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 */
80	CV_IMPL CvPoint
81	cvReadChainPoint( 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
114	typedef 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	*/
131	typedef 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	*/
178	static CvContourScanner
179	cvStartFindContours_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
310	CV_IMPL CvContourScanner
311	cvStartFindContours( 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	*/
454	static void
455	icvEndProcessContour( 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 */
485	CV_IMPL void
486	cvSubstituteContour( 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
501	static 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	*/
510	static void
511	icvFetchContour( 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	*/
629	static int
630	icvTraceContour( 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
706	static void
707	icvFetchContourEx( 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
839	static int
840	icvTraceContour_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
894	static void
895	icvFetchContourEx_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
1029	CvSeq *
1030	cvFindNextContour( 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 */
1310	CV_IMPL CvSeq *
1311	cvEndFindContours( 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
1344	typedef struct CvLinkedRunPoint
1345	{
1346	struct CvLinkedRunPoint* link;
1347	struct CvLinkedRunPoint* next;
1348	CvPoint pt;
1349	}
1350	CvLinkedRunPoint;
1351
1352	inline 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
1371	inline 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
1398	static int
1399	icvFindContoursInInterval( 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
1738	static int
1739	cvFindContours_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*/
1808	CV_IMPL int
1809	cvFindContours( 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
1817	void 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
1882	void 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