1// This file is part of OpenCV project.
2// It is subject to the license terms in the LICENSE file found in the top-level directory
3// of this distribution and at http://opencv.org/license.html
4
5#include "opencv2/imgproc.hpp"
6#include "precomp.hpp"
7#include "opencv2/core/hal/intrin.hpp"
8#include "opencv2/core/check.hpp"
9#include "opencv2/core/utils/logger.hpp"
10#include <iostream>
11#include <array>
12#include <limits>
13#include <map>
14
15#include "contours_common.hpp"
16
17using namespace std;
18using namespace cv;
19
20//==============================================================================
21
22namespace {
23
24template <typename T>
25struct Trait
26{
27};
28
29static const schar MASK8_RIGHT = '\x80'; // 1000 0000
30static const schar MASK8_NEW = '\x02'; // 0000 0010 (+2)
31static const schar MASK8_FLAGS = '\xFE'; // 1111 1110 (-2)
32static const schar MASK8_BLACK = '\x01'; // 0000 0001 - black pixel
33
34static const schar MASK8_LVAL = '\x7F'; // 0111 1111 (for table)
35
36template <>
37struct Trait<schar>
38{
39 static inline bool checkValue(const schar* elem, const schar*)
40 {
41 return *elem != 0;
42 }
43 static inline bool isVal(const schar* elem, const schar*)
44 {
45 return *elem == MASK8_BLACK;
46 }
47 static inline bool isRight(const schar* elem, const schar*)
48 {
49 return (*elem & MASK8_RIGHT) != 0;
50 }
51 static inline void setRightFlag(schar* elem, const schar*, schar nbd)
52 {
53 *elem = nbd | MASK8_RIGHT;
54 }
55 static inline void setNewFlag(schar* elem, const schar*, schar nbd)
56 {
57 *elem = nbd;
58 }
59};
60
61static const int MASK_RIGHT = 0x80000000; // 100..000
62static const int MASK_NEW = 0x40000000; // 010..000
63static const int MASK_FLAGS = 0xC0000000; // right + new
64static const int MASK_VAL = 0x3FFFFFFF; // ~flags - pixel label
65
66template <>
67struct Trait<int>
68{
69 static inline bool checkValue(const int* elem, const int* elem0)
70 {
71 return (*elem & MASK_VAL) == (*elem0 & MASK_VAL);
72 }
73 static inline bool isVal(const int* elem, const int* elem0)
74 {
75 return *elem == (*elem0 & MASK_VAL);
76 }
77 static inline bool isRight(const int* elem, const int* elem0)
78 {
79 return (*elem & MASK_RIGHT) == (*elem0 & MASK8_RIGHT);
80 }
81 static inline void setRightFlag(int* elem, const int* elem0, int)
82 {
83 *elem = (*elem0 & MASK_VAL) | MASK_NEW | MASK_RIGHT;
84 }
85 static inline void setNewFlag(int* elem, const int* elem0, int)
86 {
87 *elem = (*elem0 & MASK_VAL) | MASK_NEW;
88 }
89};
90
91} // namespace
92
93
94//==============================================================================
95
96
97namespace {
98
99template <typename T>
100static bool icvTraceContour(Mat& image, const Point& start, const Point& end, bool isHole)
101{
102 const T* stop_ptr = image.ptr<T>(end.y, end.x);
103 const size_t step = image.step1();
104 const T *i0 = image.ptr<T>(start.y, start.x), *i1, *i3, *i4 = NULL;
105 const schar s_end = isHole ? 0 : 4;
106
107 schar s = s_end;
108 do
109 {
110 s = (s - 1) & 7;
111 i1 = i0 + getDelta(s, step);
112 }
113 while (!Trait<T>::checkValue(i1, i0) && s != s_end);
114
115 i3 = i0;
116
117 // check single pixel domain
118 if (s != s_end)
119 {
120 // follow border
121 for (;;)
122 {
123 CV_Assert(i3 != NULL);
124 s = clamp_direction(dir: s);
125 while (s < MAX_SIZE - 1)
126 {
127 ++s;
128 i4 = i3 + getDelta(s, step);
129 CV_Assert(i4 != NULL);
130 if (Trait<T>::checkValue(i4, i0))
131 break;
132 }
133
134 if (i3 == stop_ptr)
135 {
136 if (!Trait<T>::isRight(i3, i0))
137 {
138 // it's the only contour
139 return true;
140 }
141
142 // check if this is the last contour
143 // encountered during a raster scan
144 const T* i5;
145 schar t = s;
146 while (true)
147 {
148 t = (t - 1) & 7;
149 i5 = i3 + getDelta(s: t, step);
150 if (*i5 != 0)
151 break;
152 if (t == 0)
153 return true;
154 }
155 }
156
157 if ((i4 == i0 && i3 == i1))
158 break;
159
160 i3 = i4;
161 s = (s + 4) & 7;
162 } // end of border following loop
163 }
164 else
165 {
166 return i3 == stop_ptr;
167 }
168
169 return false;
170}
171
172template <typename T>
173static void icvFetchContourEx(Mat& image,
174 const Point& start,
175 T nbd,
176 Contour& res_contour,
177 const bool isDirect)
178{
179 const size_t step = image.step1();
180 T *i0 = image.ptr<T>(start.y, start.x), *i1, *i3, *i4 = NULL;
181
182 Point pt = res_contour.origin;
183
184 cv::Rect rect(pt.x, pt.y, pt.x, pt.y);
185
186 schar s_end = res_contour.isHole ? 0 : 4;
187 schar s = s_end;
188 do
189 {
190 s = (s - 1) & 7;
191 i1 = i0 + getDelta(s, step);
192 }
193 while (!Trait<T>::checkValue(i1, i0) && s != s_end);
194
195 if (s == s_end)
196 {
197 Trait<T>::setRightFlag(i0, i0, nbd);
198 if (!res_contour.isChain)
199 {
200 res_contour.pts.push_back(x: pt);
201 }
202 }
203 else
204 {
205 i3 = i0;
206 schar prev_s = s ^ 4;
207
208 // follow border
209 for (;;)
210 {
211 s_end = s;
212 s = clamp_direction(dir: s);
213 while (s < MAX_SIZE - 1)
214 {
215 ++s;
216 i4 = i3 + getDelta(s, step);
217 CV_Assert(i4 != NULL);
218 if (Trait<T>::checkValue(i4, i0))
219 break;
220 }
221 s &= 7;
222
223 // check "right" bound
224 if ((unsigned)(s - 1) < (unsigned)s_end)
225 {
226 Trait<T>::setRightFlag(i3, i0, nbd);
227 }
228 else if (Trait<T>::isVal(i3, i0))
229 {
230 Trait<T>::setNewFlag(i3, i0, nbd);
231 }
232
233 if (res_contour.isChain)
234 {
235 res_contour.codes.push_back(x: s);
236 }
237 else if (s != prev_s || isDirect)
238 {
239 res_contour.pts.push_back(x: pt);
240 }
241
242 if (s != prev_s)
243 {
244 // update bounds
245 if (pt.x < rect.x)
246 rect.x = pt.x;
247 else if (pt.x > rect.width)
248 rect.width = pt.x;
249
250 if (pt.y < rect.y)
251 rect.y = pt.y;
252 else if (pt.y > rect.height)
253 rect.height = pt.y;
254 }
255
256 prev_s = s;
257 pt += chainCodeDeltas[s];
258
259 if (i4 == i0 && i3 == i1)
260 break;
261
262 i3 = i4;
263 s = (s + 4) & 7;
264 }
265 }
266 rect.width -= rect.x - 1;
267 rect.height -= rect.y - 1;
268 res_contour.brect = rect;
269}
270
271} // namespace
272
273
274//==============================================================================
275
276//
277// Raster->Chain Tree (Suzuki algorithms)
278//
279
280// Structure that is used for sequential retrieving contours from the image.
281// It supports both hierarchical and plane variants of Suzuki algorithm.
282struct ContourScanner_
283{
284 Mat image;
285 Point offset; // ROI offset: coordinates, added to each contour point
286 Point pt; // current scanner position
287 Point lnbd; // position of the last met contour
288 schar nbd; // current mark val
289 int approx_method1; // approx method when tracing
290 int approx_method2; // final approx method
291 int mode;
292 CTree tree;
293 array<int, 128> ctable;
294
295public:
296 ContourScanner_() {}
297 ~ContourScanner_() {}
298 inline bool isInt() const
299 {
300 return (this->mode == RETR_FLOODFILL);
301 }
302 inline bool isSimple() const
303 {
304 return (this->mode == RETR_EXTERNAL || this->mode == RETR_LIST);
305 }
306
307 CNode& makeContour(schar& nbd_, const bool is_hole, const int x, const int y);
308 bool contourScan(const int prev, int& p, Point& last_pos, const int x, const int y);
309 int findFirstBoundingContour(const Point& last_pos, const int y, const int lval, int par);
310 int findNextX(int x, int y, int& prev, int& p);
311 bool findNext();
312
313 static shared_ptr<ContourScanner_> create(Mat img, int mode, int method, Point offset);
314}; // class ContourScanner_
315
316typedef shared_ptr<ContourScanner_> ContourScanner;
317
318
319shared_ptr<ContourScanner_> ContourScanner_::create(Mat img, int mode, int method, Point offset)
320{
321 if (mode == RETR_CCOMP && img.type() == CV_32SC1)
322 mode = RETR_FLOODFILL;
323
324 if (mode == RETR_FLOODFILL)
325 CV_CheckTypeEQ(img.type(), CV_32SC1, "RETR_FLOODFILL mode supports only CV_32SC1 images");
326 else
327 CV_CheckTypeEQ(img.type(),
328 CV_8UC1,
329 "Modes other than RETR_FLOODFILL and RETR_CCOMP support only CV_8UC1 "
330 "images");
331
332 CV_Check(mode,
333 mode == RETR_EXTERNAL || mode == RETR_LIST || mode == RETR_CCOMP ||
334 mode == RETR_TREE || mode == RETR_FLOODFILL,
335 "Wrong extraction mode");
336
337 CV_Check(method,
338 method == 0 || method == CHAIN_APPROX_NONE || method == CHAIN_APPROX_SIMPLE ||
339 method == CHAIN_APPROX_TC89_L1 || method == CHAIN_APPROX_TC89_KCOS,
340 "Wrong approximation method");
341
342 Size size = img.size();
343 CV_Assert(size.height >= 1);
344
345 shared_ptr<ContourScanner_> scanner = make_shared<ContourScanner_>();
346 scanner->image = img;
347 scanner->mode = mode;
348 scanner->offset = offset;
349 scanner->pt = Point(1, 1);
350 scanner->lnbd = Point(0, 1);
351 scanner->nbd = 2;
352 CNode& root = scanner->tree.newElem();
353 CV_Assert(root.self() == 0);
354 root.body.isHole = true;
355 root.body.brect = Rect(Point(0, 0), size);
356 scanner->ctable.fill(u: -1);
357 scanner->approx_method2 = scanner->approx_method1 = method;
358 if (method == CHAIN_APPROX_TC89_L1 || method == CHAIN_APPROX_TC89_KCOS)
359 scanner->approx_method1 = CV_CHAIN_CODE;
360 return scanner;
361}
362
363CNode& ContourScanner_::makeContour(schar& nbd_, const bool is_hole, const int x, const int y)
364{
365 const bool isChain = (this->approx_method1 == CV_CHAIN_CODE); // TODO: get rid of old constant
366 const bool isDirect = (this->approx_method1 == CHAIN_APPROX_NONE);
367
368 const Point start_pt(x - (is_hole ? 1 : 0), y);
369
370 CNode& res = tree.newElem();
371 res.body.isHole = is_hole;
372 res.body.isChain = isChain;
373 res.body.origin = start_pt + offset;
374 if (isSimple())
375 {
376 icvFetchContourEx<schar>(image&: this->image, start: start_pt, nbd: MASK8_NEW, res_contour&: res.body, isDirect);
377 }
378 else
379 {
380 schar lval;
381 if (isInt())
382 {
383 const int start_val = this->image.at<int>(pt: start_pt);
384 lval = start_val & MASK8_LVAL;
385 icvFetchContourEx<int>(image&: this->image, start: start_pt, nbd: 0, res_contour&: res.body, isDirect);
386 }
387 else
388 {
389 lval = nbd_;
390 // change nbd
391 nbd_ = (nbd_ + 1) & MASK8_LVAL;
392 if (nbd_ == 0)
393 nbd_ = MASK8_BLACK | MASK8_NEW;
394 icvFetchContourEx<schar>(image&: this->image, start: start_pt, nbd: lval, res_contour&: res.body, isDirect);
395 }
396 res.body.brect.x -= this->offset.x;
397 res.body.brect.y -= this->offset.y;
398 res.ctable_next = this->ctable[lval];
399 this->ctable[lval] = res.self();
400 }
401 const Point prev_origin = res.body.origin;
402 res.body.origin = start_pt;
403 if (this->approx_method1 != this->approx_method2)
404 {
405 CV_Assert(res.body.isChain);
406 res.body.pts = approximateChainTC89(chain: res.body.codes, origin: prev_origin, method: this->approx_method2);
407 res.body.isChain = false;
408 }
409 return res;
410}
411
412bool ContourScanner_::contourScan(const int prev, int& p, Point& last_pos, const int x, const int y)
413{
414 bool is_hole = false;
415
416 /* if not external contour */
417 if (isInt())
418 {
419 if (!(((prev & MASK_FLAGS) != 0 || prev == 0) && (p & MASK_FLAGS) == 0))
420 {
421 if ((prev & MASK_FLAGS) != 0 || ((p & MASK_FLAGS) != 0))
422 return false;
423
424 if (prev & MASK_FLAGS)
425 {
426 last_pos.x = x - 1;
427 }
428 is_hole = true;
429 }
430 }
431 else
432 {
433 if (!(prev == 0 && p == 1))
434 {
435 if (p != 0 || prev < 1)
436 return false;
437
438 if (prev & MASK8_FLAGS)
439 {
440 last_pos.x = x - 1;
441 }
442 is_hole = true;
443 }
444 }
445
446 if (mode == RETR_EXTERNAL && (is_hole || this->image.at<schar>(pt: last_pos) > 0))
447 {
448 return false;
449 }
450
451 /* find contour parent */
452 int main_parent = -1;
453 if (isSimple() || (!is_hole && (mode == RETR_CCOMP || mode == RETR_FLOODFILL)) ||
454 last_pos.x <= 0)
455 {
456 main_parent = 0;
457 }
458 else
459 {
460 int lval;
461 if (isInt())
462 lval = this->image.at<int>(i0: last_pos.y, i1: last_pos.x) & MASK8_LVAL;
463 else
464 lval = this->image.at<schar>(i0: last_pos.y, i1: last_pos.x) & MASK8_LVAL;
465
466 main_parent = findFirstBoundingContour(last_pos, y, lval, par: main_parent);
467
468 // if current contour is a hole and previous contour is a hole or
469 // current contour is external and previous contour is external then
470 // the parent of the contour is the parent of the previous contour else
471 // the parent is the previous contour itself.
472 {
473 CNode& main_parent_elem = tree.elem(idx: main_parent);
474 if (main_parent_elem.body.isHole == is_hole)
475 {
476 if (main_parent_elem.parent != -1)
477 {
478 main_parent = main_parent_elem.parent;
479 }
480 else
481 {
482 main_parent = 0;
483 }
484 }
485 }
486
487 // hole flag of the parent must differ from the flag of the contour
488 {
489 CNode& main_parent_elem = tree.elem(idx: main_parent);
490 CV_Assert(main_parent_elem.body.isHole != is_hole);
491 }
492 }
493
494 last_pos.x = x - (is_hole ? 1 : 0);
495
496 schar nbd_ = this->nbd;
497 CNode& new_contour = makeContour(nbd_, is_hole, x, y);
498 if (new_contour.parent == -1)
499 {
500 tree.addChild(parent_idx: main_parent, child_idx: new_contour.self());
501 }
502 this->pt.x = !isInt() ? (x + 1) : (x + 1 - (is_hole ? 1 : 0));
503 this->pt.y = y;
504 this->nbd = nbd_;
505 return true;
506}
507
508int ContourScanner_::findFirstBoundingContour(const Point& last_pos,
509 const int y,
510 const int lval,
511 int par)
512{
513 const Point end_point(last_pos.x, y);
514 int res = par;
515 int cur = ctable[lval];
516 while (cur != -1)
517 {
518 CNode& cur_elem = tree.elem(idx: cur);
519 if (((last_pos.x - cur_elem.body.brect.x) < cur_elem.body.brect.width) &&
520 ((last_pos.y - cur_elem.body.brect.y) < cur_elem.body.brect.height))
521 {
522 if (res != -1)
523 {
524 CNode& res_elem = tree.elem(idx: res);
525 const Point origin = res_elem.body.origin;
526 const bool isHole = res_elem.body.isHole;
527 if (isInt())
528 {
529 if (icvTraceContour<int>(image&: this->image, start: origin, end: end_point, isHole))
530 break;
531 }
532 else
533 {
534 if (icvTraceContour<schar>(image&: this->image, start: origin, end: end_point, isHole))
535 break;
536 }
537 }
538 res = cur;
539 }
540 cur = cur_elem.ctable_next;
541 }
542 return res;
543}
544
545int ContourScanner_::findNextX(int x, int y, int& prev, int& p)
546{
547 const int width = this->image.size().width - 1;
548 if (isInt())
549 {
550 for (; x < width &&
551 ((p = this->image.at<int>(i0: y, i1: x)) == prev || (p & MASK_VAL) == (prev & MASK_VAL));
552 x++)
553 prev = p;
554 }
555 else
556 {
557#if (CV_SIMD || CV_SIMD_SCALABLE)
558 if ((p = this->image.at<schar>(i0: y, i1: x)) != prev)
559 {
560 return x;
561 }
562 else
563 {
564 v_uint8 v_prev = vx_setall_u8(v: (uchar)prev);
565 for (; x <= width - VTraits<v_uint8>::vlanes(); x += VTraits<v_uint8>::vlanes())
566 {
567 v_uint8 vmask = (v_ne(a: vx_load(ptr: this->image.ptr<uchar>(i0: y, i1: x)), b: v_prev));
568 if (v_check_any(a: vmask))
569 {
570 x += v_scan_forward(a: vmask);
571 p = this->image.at<schar>(i0: y, i1: x);
572 return x;
573 }
574 }
575 }
576#endif
577 for (; x < width && (p = this->image.at<schar>(i0: y, i1: x)) == prev; x++)
578 ;
579 }
580 return x;
581}
582
583bool ContourScanner_::findNext()
584{
585 int x = this->pt.x;
586 int y = this->pt.y;
587 int width = this->image.size().width - 1;
588 int height = this->image.size().height - 1;
589 Point last_pos = this->lnbd;
590 int prev = isInt() ? this->image.at<int>(i0: y, i1: x - 1) : this->image.at<schar>(i0: y, i1: x - 1);
591
592 for (; y < height; y++)
593 {
594 int p = 0;
595 for (; x < width; x++)
596 {
597 x = findNextX(x, y, prev, p);
598 if (x >= width)
599 break;
600 if (contourScan(prev, p, last_pos, x, y))
601 {
602 this->lnbd = last_pos;
603 return true;
604 }
605 else
606 {
607 prev = p;
608 if ((isInt() && (prev & MASK_FLAGS)) || (!isInt() && (prev & MASK8_FLAGS)))
609 {
610 last_pos.x = x;
611 }
612 }
613 }
614 last_pos = Point(0, y + 1);
615 x = 1;
616 prev = 0;
617 }
618
619 return false;
620}
621
622//==============================================================================
623
624void cv::findContours(InputArray _image,
625 OutputArrayOfArrays _contours,
626 OutputArray _hierarchy,
627 int mode,
628 int method,
629 Point offset)
630{
631 CV_INSTRUMENT_REGION();
632
633 // TODO: remove this block in future
634 if (method == 5 /*CV_LINK_RUNS*/)
635 {
636 CV_LOG_ONCE_WARNING(NULL,
637 "LINK_RUNS mode has been extracted to separate function: "
638 "cv::findContoursLinkRuns. "
639 "Calling through cv::findContours will be removed in future.");
640 CV_CheckTrue(!_hierarchy.needed() || mode == RETR_CCOMP,
641 "LINK_RUNS mode supports only simplified hierarchy output (mode=RETR_CCOMP)");
642 findContoursLinkRuns(image: _image, contours: _contours, hierarchy: _hierarchy);
643 return;
644 }
645
646 // TODO: need enum value, need way to return contour starting points with chain codes
647 if (method == 0 /*CV_CHAIN_CODE*/)
648 {
649 CV_LOG_ONCE_WARNING(NULL,
650 "Chain code output is an experimental feature and might change in "
651 "future!");
652 }
653
654 // Sanity check: output must be of type vector<vector<Point>>
655 CV_Assert((_contours.kind() == _InputArray::STD_VECTOR_VECTOR) ||
656 (_contours.kind() == _InputArray::STD_VECTOR_MAT) ||
657 (_contours.kind() == _InputArray::STD_VECTOR_UMAT));
658
659 const int res_type = (method == 0 /*CV_CHAIN_CODE*/) ? CV_8SC1 : CV_32SC2;
660 if (!_contours.empty())
661 {
662 CV_CheckTypeEQ(_contours.type(),
663 res_type,
664 "Contours must have type CV_8SC1 (chain code) or CV_32SC2 (other methods)");
665 }
666
667 if (_hierarchy.needed())
668 _hierarchy.clear();
669
670 // preprocess
671 Mat image;
672 copyMakeBorder(src: _image, dst: image, top: 1, bottom: 1, left: 1, right: 1, borderType: BORDER_CONSTANT | BORDER_ISOLATED, value: Scalar(0));
673 if (image.type() != CV_32SC1)
674 threshold(src: image, dst: image, thresh: 0, maxval: 1, type: THRESH_BINARY);
675
676 // find contours
677 ContourScanner scanner = ContourScanner_::create(img: image, mode, method, offset: offset + Point(-1, -1));
678 while (scanner->findNext())
679 {
680 }
681
682 contourTreeToResults(tree&: scanner->tree, res_type, _contours, _hierarchy);
683}
684
685void cv::findContours(InputArray _image,
686 OutputArrayOfArrays _contours,
687 int mode,
688 int method,
689 Point offset)
690{
691 CV_INSTRUMENT_REGION();
692 findContours(_image, _contours, hierarchy: noArray(), mode, method, offset);
693}
694

Provided by KDAB

Privacy Policy
Update your C++ knowledge – Modern C++11/14/17 Training
Find out more

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