Reworked findContours to reduce C-API usage #25146

mshabunin · 2024-03-04T07:21:24Z

What is done:

rewritten findContours and icvApproximateChainTC89 using C++ data structures
extracted LINK_RUNS mode to separate new public functions - findContoursLinkRuns (it uses completely different algorithm)
~~added new public cv::approximateChainTC89~~ - ❌ decided to hide it
enabled chain code output (method = 0, no public enum value for this in C++ yet)
kept old function as findContours_old (exported, but not exposed to user)
added more tests for findContours (test_contours_new.cpp), some tests compare results of old function with new one. Following tests have been added:
- contours of random rectangle
- contours of many small (1-2px) blobs
- contours of random noise
- backport of old accuracy test
- separate test for LINK RUNS variant

What is left to be done (can be done now or later):

improve tests:
- some tests have limited verification (e.g. only verify contour sizes)
- perhaps reference data can be collected and stored
- maybe more test variants can be added (?)
add enum value for chain code output and a method of returning starting points (e.g. first 8 elements of returned vector<uchar> can represent 2 int point coordinates)
add documentation for new functions - ✔️ DONE
check and improve performance (my experiment showed 0.7x-1.1x some time ago)
remove old functions completely (?)
change contour return order (BFS) or allow to select it (?)
return result tree as-is (?) (new data structures should be exposed, bindings should adapt)

modules/imgproc/src/approx.cpp

modules/imgproc/src/contour_approx.cpp

modules/imgproc/include/opencv2/imgproc.hpp

modules/imgproc/src/contours_common.cpp

modules/imgproc/src/contours_common.hpp

modules/imgproc/include/opencv2/imgproc.hpp

modules/imgproc/src/contour_approx.cpp

modules/imgproc/include/opencv2/imgproc.hpp

modules/imgproc/src/contours_approx.cpp

modules/imgproc/src/contours_common.cpp

modules/imgproc/src/contours_link.cpp

modules/imgproc/src/contours_new.cpp

mshabunin · 2024-03-10T15:28:45Z

@asmorkalov , I've addressed some of the comments, but still not sure what to do with others:

can I use clang-format from our wiki for consistent formatting?
do we choose to export contourApprox function and chain code output for findContours or hide them?

asmorkalov

👍

AleksandrPanov · 2024-03-29T07:31:12Z

@mshabunin

could you add info which paper describes findContoursLinkRuns() (if you know)?
the performance of findContours() is very important, this function used in findChessboardCorners, SimpleBlobDetector, findCircleGrid, ArucoDetector, CCheckerDetector, ... and findContours() may take up to 50% of the execution time in some cases. Do you have any simple suggestions on how to improve performance?

mshabunin · 2024-03-29T08:55:53Z

I haven't find the paper for link runs approach, all hopes on @vpisarev 🙂
I did some basic optimizations by reserving internal vector sizes with assumption that contours are not very small. Further optimization can be done by using single large vector for all points and only storing ranges in it in each contour record. Additionally we can think about more efficient public interface, e.g. findContours could return an object of some new type which would allow users to iterate over contours and access data in each of them.

modules/imgproc/src/contours_approx.cpp

opencv-alalek · 2024-03-30T06:00:44Z

modules/imgproc/src/contours_new.cpp

 static const int MASK_FLAGS = 0xC0000000; // right + new
-static const int MASK_VAL   = 0x3FFFFFFF; // ~flags - pixel label
+static const int MASK_VAL = 0x3FFFFFFF; // ~flags - pixel label


Is there clang-format option 'do not touch'?

We can enclosure a block of code between // clang-format on - // clang-format off comments to ignore it.

But I believe in general it is better to avoid alignment of values or comments in such blocks to simplify future merges. Thus I chose to disable these rules: AlignConsecutiveAssignments: None and other AlignConsecutive* options (see https://releases.llvm.org/12.0.0/tools/clang/docs/ClangFormatStyleOptions.html for details)

modules/imgproc/src/contours_new.cpp

modules/imgproc/test/test_contours_new.cpp

- added new tests for findContours - rewritten findContours and TC89 approximation without using C-API data structures - enabled chain code output (method=0) - moved link runs algorithm to separate function (does not copy image, limited hierarchy) - temporarily added findContours_old function to test accuracy

sn4k3 · 2024-04-08T05:46:24Z

Would also be nice to have 4 connected and 8 connected contour detection...

Reworked findContours to reduce C-API usage opencv#25146 What is done: * rewritten `findContours` and `icvApproximateChainTC89` using C++ data structures * extracted LINK_RUNS mode to separate new public functions - `findContoursLinkRuns` (it uses completely different algorithm) * ~added new public `cv::approximateChainTC89`~ - **:x: decided to hide it** * enabled chain code output (method = 0, no public enum value for this in C++ yet) * kept old function as `findContours_old` (exported, but not exposed to user) * added more tests for findContours (`test_contours_new.cpp`), some tests compare results of old function with new one. Following tests have been added: * contours of random rectangle * contours of many small (1-2px) blobs * contours of random noise * backport of old accuracy test * separate test for LINK RUNS variant What is left to be done (can be done now or later): * improve tests: * some tests have limited verification (e.g. only verify contour sizes) * perhaps reference data can be collected and stored * maybe more test variants can be added (?) * add enum value for chain code output and a method of returning starting points (e.g. first 8 elements of returned `vector<uchar>` can represent 2 int point coordinates) * add documentation for new functions - **:heavy_check_mark: DONE** * check and improve performance (my experiment showed 0.7x-1.1x some time ago) * remove old functions completely (?) * change contour return order (BFS) or allow to select it (?) * return result tree as-is (?) (new data structures should be exposed, bindings should adapt)

vrabaud · 2024-05-30T11:50:54Z

modules/imgproc/src/contours_link.cpp

+            lower_run = rns[rns[lower_run].next].next;
+            continue;
+        }
+        rns[rns[lower_run].next] = rns[rns[lower_run].next];


@mshabunin , why assign it to itself? Is it a bug?

Yes, this is a problem, but not serious - there should be no operation, like in the original code:

opencv/modules/imgproc/src/contours.cpp

Lines 1636 to 1664 in f4ebf7c

for( ; n < lower_total/2; n++ )

{

if( connect_flag != ICV_SINGLE )

{

prev_point->link = lower_run->next;

connect_flag = ICV_SINGLE;

lower_run = lower_run->next->next;

continue;

}

lower_run->link = lower_run->next;

//First point of contour

CV_WRITE_SEQ_ELEM( lower_run, writer_ext );

lower_run = lower_run->next->next;

}

for( ; k < upper_total/2; k++ )

{

if( connect_flag != ICV_SINGLE )

{

upper_run->next->link = prev_point;

connect_flag = ICV_SINGLE;

upper_run = upper_run->next->next;

continue;

}

upper_run->next->link = upper_run;

upper_run = upper_run->next->next;

}

I'll fix it soon.

Reworked findContours to reduce C-API usage opencv#25146 What is done: * rewritten `findContours` and `icvApproximateChainTC89` using C++ data structures * extracted LINK_RUNS mode to separate new public functions - `findContoursLinkRuns` (it uses completely different algorithm) * ~added new public `cv::approximateChainTC89`~ - **:x: decided to hide it** * enabled chain code output (method = 0, no public enum value for this in C++ yet) * kept old function as `findContours_old` (exported, but not exposed to user) * added more tests for findContours (`test_contours_new.cpp`), some tests compare results of old function with new one. Following tests have been added: * contours of random rectangle * contours of many small (1-2px) blobs * contours of random noise * backport of old accuracy test * separate test for LINK RUNS variant What is left to be done (can be done now or later): * improve tests: * some tests have limited verification (e.g. only verify contour sizes) * perhaps reference data can be collected and stored * maybe more test variants can be added (?) * add enum value for chain code output and a method of returning starting points (e.g. first 8 elements of returned `vector<uchar>` can represent 2 int point coordinates) * add documentation for new functions - **:heavy_check_mark: DONE** * check and improve performance (my experiment showed 0.7x-1.1x some time ago) * remove old functions completely (?) * change contour return order (BFS) or allow to select it (?) * return result tree as-is (?) (new data structures should be exposed, bindings should adapt)

mshabunin force-pushed the cpp-contours branch from d964d59 to 1e5f8f7 Compare March 4, 2024 11:54

mshabunin marked this pull request as ready for review March 4, 2024 11:54

asmorkalov requested review from asmorkalov and vpisarev March 4, 2024 16:53

asmorkalov added the category: imgproc label Mar 4, 2024

asmorkalov added this to the 4.10.0 milestone Mar 4, 2024

mshabunin force-pushed the cpp-contours branch from 1e5f8f7 to 8f478d4 Compare March 4, 2024 18:49

asmorkalov reviewed Mar 5, 2024

View reviewed changes

mshabunin force-pushed the cpp-contours branch 5 times, most recently from 24b2a2e to 82f0b1d Compare March 5, 2024 15:15

asmorkalov reviewed Mar 6, 2024

View reviewed changes

mshabunin force-pushed the cpp-contours branch 7 times, most recently from 2609d74 to ae87c6e Compare March 22, 2024 08:49

asmorkalov approved these changes Mar 27, 2024

View reviewed changes

asmorkalov self-assigned this Mar 29, 2024

mshabunin force-pushed the cpp-contours branch from ae87c6e to e9557eb Compare March 29, 2024 08:46

opencv-alalek reviewed Mar 30, 2024

View reviewed changes

mshabunin force-pushed the cpp-contours branch from e9557eb to 1fbacec Compare April 2, 2024 22:02

Address comments

8d8915f

mshabunin force-pushed the cpp-contours branch from 1fbacec to 505030c Compare April 2, 2024 22:11

formatting # 3

a32727f

asmorkalov merged commit a251329 into opencv:4.x Apr 9, 2024

mshabunin deleted the cpp-contours branch April 9, 2024 10:05

This was referenced Apr 10, 2024

(5.x) Merge 4.x #25384

Merged

Removed old C API usage in new findContours implementation #25385

Merged

This was referenced Apr 17, 2024

imgproc: contours C-API cleanup #25431

Merged

imgproc: approx C-API cleanup #25438

Merged

vrabaud reviewed May 30, 2024

View reviewed changes

	for( ; n < lower_total/2; n++ )
	{
	if( connect_flag != ICV_SINGLE )
	{
	prev_point->link = lower_run->next;
	connect_flag = ICV_SINGLE;
	lower_run = lower_run->next->next;
	continue;
	}
	lower_run->link = lower_run->next;

	//First point of contour
	CV_WRITE_SEQ_ELEM( lower_run, writer_ext );

	lower_run = lower_run->next->next;
	}

	for( ; k < upper_total/2; k++ )
	{
	if( connect_flag != ICV_SINGLE )
	{
	upper_run->next->link = prev_point;
	connect_flag = ICV_SINGLE;
	upper_run = upper_run->next->next;
	continue;
	}
	upper_run->next->link = upper_run;
	upper_run = upper_run->next->next;
	}

Uh oh!

Reworked findContours to reduce C-API usage #25146

Reworked findContours to reduce C-API usage #25146

Uh oh!

Conversation

mshabunin commented Mar 4, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

mshabunin commented Mar 10, 2024

Uh oh!

asmorkalov left a comment

Choose a reason for hiding this comment

Uh oh!

AleksandrPanov commented Mar 29, 2024

Uh oh!

mshabunin commented Mar 29, 2024

Uh oh!

Uh oh!

Uh oh!

opencv-alalek Mar 30, 2024

Choose a reason for hiding this comment

Uh oh!

mshabunin Apr 2, 2024

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

sn4k3 commented Apr 8, 2024

Uh oh!

vrabaud May 30, 2024

Choose a reason for hiding this comment

Uh oh!

mshabunin May 31, 2024

Choose a reason for hiding this comment

Uh oh!

Uh oh!

mshabunin commented Mar 4, 2024 •

edited

Loading