New findContours finds different results about opencv HOT 11 CLOSED

@mshabunin , it is still not working exactly the same for me. Here is a new rows=12,cols=16 example:

0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,
0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,
0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,
0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,
0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,
0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

There are 7 old contours, 8 new ones.

from opencv.

I think the wrong behavior should not be forward ported, let's keep the bugfix for 4.10.
BTW, as the old contours.cpp will be removed at some point, how about renaming contours.cpp to contours_old.cppright now and havecontours.cpp` be the new code ? It will make things easier to kill old code for 4.11.

from opencv.

This test passes for me on Linux, GCC 12, current 4.x branch:

[ RUN      ] Imgproc_FindContours.regression
[16, 0][15, 3][14, 6][15, 10][13, 12][10, 12][8, 9][5, 7][2, 4][0, 4][0, 31][31, 31][31, 0]

[16, 0][15, 3][14, 6][15, 10][13, 12][10, 12][8, 9][5, 7][2, 4][0, 4][0, 31][31, 31][31, 0]
[       OK ] Imgproc_FindContours.regression (0 ms)

What is your platform?

from opencv.

Thx @mshabunin for the quick response. Did you patch

[16, 0][15, 3][14, 6][15, 10][13, 12][10, 12][8, 9][5, 7][2, 4][0, 4][0, 31][31, 31][31, 0]

[16, 0][16, 2][15, 5][14, 6][15, 10][13, 12][10, 12][8, 9][5, 7][2, 4][0, 4][0, 31][31, 31][31, 0]

from opencv.

No I didn't 😕

With this patch I've reproduced this issue. You're right, findContours_legacy should call findContours_legacy. I'll take closer look.

from opencv.

I fixed the overload bug in #25668.

from opencv.

@vrabaud , could you please take a look at the fix in #25672?

from opencv.

I took another look at the code and came to conclusion that there is an issue in the original implementation which has been fixed in refactored function. I'm not sure if we should try to port this behavior to new function or leave it as-is (revert #25672), i.e. different. @vrabaud , @asmorkalov , what do you think?

Details

Issue lies in the last, 4-th pass of the algorithm (page 685). Basically we check all groups of consecutive elements (groups) and remove:

• first or second element (for groups with 2 elements)
• all elements between first and last (for groups with > 2 elements)

I reverted changes from my previous PR and took original example from this ticket (32x32), also added some logging (4.x...mshabunin:fix-approx-2)

Results

Original implementation returns following result (element indexes):

Result: 0, 2, 5, 6, 10, 12, 15, 18, 21, 25, 27, 54, 85, 116, 

Note consecutive elements 5, 6 being left after last pass - it should not happen.

Refactored:

Result: 0, 2, 6, 10, 12, 15, 18, 21, 25, 27, 54, 85, 116, 

Explanation

Log from the original implementation:

first = 0, prev = 2, curr = 3, next = 5
** remove (=2i) 3
first = 3, prev = 3, curr = 5, next = 6
first = 3, prev = 5, curr = 6, next = 10
** remove (=2e) 5

Elements are stored in a linked list, removed element should not be in the list (but are kept in the array which stores list elements). prev and curr are two elements being checked (for groups of 2), first is an element before current group, next is element after group. Here we first process group of 2 elements 2, 3 and remove 3 by changing pointer in linked list 2 -> 5. Also we change first to 3 which is wrong. Then we meet group of 2 elements 5, 6 and need to remove 5 - in order to do it we set pointer 3 -> 6, but 3 is not in the list anymore, so it does not take effect. Thus element 5 stays in the list.

Refactored implementation does not use linked list, but sets flags in the array, so it does not have this issue.

Original code:

from opencv.

I believe we do not plan to remove old implementation in 4.11, only in 5.x. Do you think we should drop it?

Originally I moved new function to a new file in order to simplify 4.x->5.x merges. Theoretically we can rename contours.cpp->contours_old.cpp and contours_new.cpp->contours.cpp and git should be able to handle it, but I'm not sure. Let's leave this decision to @asmorkalov.

from opencv.

Well, the functions are not public anymore so we might as well drop them at some point in 4.x no ?

from opencv.

Technically they are public, but somewhat hidden 🙂 https://github.com/opencv/opencv/blob/4.x/modules/imgproc/include/opencv2/imgproc/detail/legacy.hpp

We can remove #ifdef __OPENCV_BUILD guard to simplify access, I added it with assumption that those who really need old functions can define this macro and include legacy header.

objdump -TC ./lib/libopencv_imgproc.so | grep legacy
00000000001a9630 g    DF .text	0000000000000b65  Base        cv::findContours_legacy(cv::_InputArray const&, cv::_OutputArray const&, cv::_OutputArray const&, int, int, cv::Point_<int>)
00000000001e1930 g    DF .text	000000000000050e  Base        cv::EMD_legacy(cv::_InputArray const&, cv::_InputArray const&, int, cv::_InputArray const&, float*, cv::_OutputArray const&)
00000000001e1e40 g    DF .text	000000000000000c  Base        cv::wrapperEMD_legacy(cv::_InputArray const&, cv::_InputArray const&, int, cv::_InputArray const&, cv::Ptr<float>, cv::_OutputArray const&)
00000000001aa1a0 g    DF .text	00000000000000a3  Base        cv::findContours_legacy(cv::_InputArray const&, cv::_OutputArray const&, int, int, cv::Point_<int>)

from opencv.