New findContours finds different results

vrabaud commented 1 month ago

System Information

OpenCV .4x at HEAD

Detailed description

findContours has been upgraded in 4.10 but the results are different from findContours_legacy. Is that intended ? BTW, I believe https://github.com/opencv/opencv/blob/d9421ac148f3ad4878b3a75c58da58c24f19ed01/modules/imgproc/src/contours.cpp#L1887 should call findContours_legacy

Steps to reproduce

Here is the test to add to test_contours_new.cpp that fails.

TEST(Imgproc_FindContours, special) {
    uint8_t data[]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,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,1,1,1,1,1,1,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,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,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,1,1,1,1,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,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
    Mat1b img(32,32,data);
    vector<vector<Point>> contours;
    vector<Vec4i> hierarchy;
    findContours(img, contours, RETR_EXTERNAL, CHAIN_APPROX_TC89_L1);
  for (auto V : contours) {
    for (auto P : V) std::cout << P;
    std::cout << "\n";
  }
#if CHECK_OLD
    vector<vector<Point>> contours_o;
    findContours_legacy(img, contours_o, RETR_EXTERNAL, CHAIN_APPROX_TC89_L1);
    ASSERT_EQ(contours_o.size(), contours.size());
    std::cout << "\n";
  for (auto V : contours_o) {
    for (auto P : V) std::cout << P;
    std::cout << "\n";
  }
    for (size_t i = 0; i < contours_o.size(); ++i)
    {
        SCOPED_TRACE(format("contour = %zu", i));
        EXPECT_MAT_NEAR(Mat(contours_o[i]), Mat(contours[i]), 0);
    }
#endif
}

Issue submission checklist

[X] I report the issue, it's not a question
[X] I checked the problem with documentation, FAQ, open issues, forum.opencv.org, Stack Overflow, etc and have not found any solution
[X] I updated to the latest OpenCV version and the issue is still there
[X] There is reproducer code and related data files (videos, images, onnx, etc)

mshabunin commented 1 month ago

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?

vrabaud commented 1 month ago

Thx @mshabunin for the quick response. Did you patch https://github.com/opencv/opencv/blob/d9421ac148f3ad4878b3a75c58da58c24f19ed01/modules/imgproc/src/contours.cpp#L1887 like I mentioned ? (so that it calls findContours_legacy). I get:

[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]

mshabunin commented 1 month ago

No I didn't :confused:

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

vrabaud commented 1 month ago

I fixed the overload bug in https://github.com/opencv/opencv/pull/25668.

mshabunin commented 1 month ago

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

vrabaud commented 4 weeks ago

@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.

mshabunin commented 4 weeks ago

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 (https://github.com/opencv/opencv/compare/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. old_version Refactored:

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

new_version

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: https://github.com/opencv/opencv/blob/f4ebf7c0a6b2ee845a395ae3dac59927eb862894/modules/imgproc/src/approx.cpp#L330-L359

vrabaud commented 4 weeks ago

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.

mshabunin commented 4 weeks ago

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.

vrabaud commented 4 weeks ago

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

mshabunin commented 4 weeks ago

Technically they are public, but somewhat hidden :slightly_smiling_face: 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>)

opencv / opencv