Add a new function that approximates the polygon bounding a convex hull with a certain number of sides by Napkin-AI · Pull Request #25607 · opencv/opencv

Napkin-AI · 2024-05-19T15:45:56Z

This PR is based on the paper View Frustum Optimization To Maximize Object’s Image Area.

Problem

I needed to reduce the number of vertices of the convex hull so that the additional area was minimal, andall vertices of the original contour enter the new contour.

Description

Initially in the contour of n vertices, at each stage we consider the intersection points of the lines formed by each adjacent edges. Each of these intersection points will form a triangle with vertices through which lines pass. Let's choose a triangle with the minimum area and merge the two vertices at the intersection point. We continue until there are more vertices than the specified number of sides of the approximated polygon.

Complexity:

Using a std::priority_queue or std::set time complexity is (O(n*ln(n)), memory O(n),
n - number of vertices in convex hull.

count of sides - the number of points by which we must reduce.

Comment

If epsilon_percentage more 0, algorithm can return more values than side.
Algorithm returns OutputArray. If OutputArray.type() equals 0, algorithm returns values with InputArray.type().
New test uses image which are not in opencv_extra, needs to be added.

Pull Request Readiness Checklist

See details at https://github.com/opencv/opencv/wiki/How_to_contribute#making-a-good-pull-request

I agree to contribute to the project under Apache 2 License.
To the best of my knowledge, the proposed patch is not based on a code under GPL or another license that is incompatible with OpenCV
The PR is proposed to the proper branch
There is a reference to the original bug report and related work
There is accuracy test, performance test and test data in opencv_extra repository, if applicable
Patch to opencv_extra has the same branch name.
The feature is well documented and sample code can be built with the project CMake

asmorkalov · 2024-05-20T12:14:27Z

2024-05-20T07:02:31.6292590Z /usr/bin/ccache /usr/bin/c++  -DCVAPI_EXPORTS -D_USE_MATH_DEFINES -D__OPENCV_BUILD=1 -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -I/home/ci/opencv/modules/imgproc/include -Imodules/imgproc -I/home/ci/opencv/modules/core/include -isystem . -isystem /usr/include/eigen3 -fsigned-char -W -Wall -Wreturn-type -Wnon-virtual-dtor -Waddress -Wsequence-point -Wformat -Wformat-security -Wmissing-declarations -Wundef -Winit-self -Wpointer-arith -Wshadow -Wsign-promo -Wuninitialized -Wsuggest-override -Wno-delete-non-virtual-dtor -Wno-comment -Wimplicit-fallthrough=3 -Wno-strict-overflow -fdiagnostics-show-option -pthread -fomit-frame-pointer -ffunction-sections -fdata-sections    -fvisibility=hidden -fvisibility-inlines-hidden -O3 -DNDEBUG  -DNDEBUG -fPIC   -std=c++11 -MD -MT modules/imgproc/CMakeFiles/opencv_imgproc.dir/src/approx.cpp.o -MF modules/imgproc/CMakeFiles/opencv_imgproc.dir/src/approx.cpp.o.d -o modules/imgproc/CMakeFiles/opencv_imgproc.dir/src/approx.cpp.o -c /home/ci/opencv/modules/imgproc/src/approx.cpp
2024-05-20T07:02:31.6304361Z /home/ci/opencv/modules/imgproc/src/approx.cpp:911:5: warning: no previous declaration for 'int recalculation(std::vector<neighbours>&, int, float&, float&, float&)' [-Wmissing-declarations]
2024-05-20T07:02:31.6306865Z   911 | int recalculation(std::vector<neighbours>& hull, int vertex_id, float& area_, float& x, float& y)
2024-05-20T07:02:31.6308049Z       |     ^~~~~~~~~~~~~
2024-05-20T07:02:31.6309995Z /home/ci/opencv/modules/imgproc/src/approx.cpp:937:6: warning: no previous declaration for 'void update(std::vector<neighbours>&, int)' [-Wmissing-declarations]
2024-05-20T07:02:31.6311937Z   937 | void update(std::vector<neighbours>& hull, int vertex_id)
2024-05-20T07:02:31.6312786Z       |      ^~~~~~
2024-05-20T07:02:31.6314499Z /home/ci/opencv/modules/imgproc/src/approx.cpp: In function 'void cv::approxBoundingPoly(cv::InputArray, cv::OutputArray, int, float, bool)':
2024-05-20T07:02:31.6316797Z /home/ci/opencv/modules/imgproc/src/approx.cpp:982:68: error: wrong number of template arguments (0, should be 1)
2024-05-20T07:02:31.6318495Z   982 |     std::priority_queue<changes, std::vector<changes>, std::greater<>> areas;
2024-05-20T07:02:31.6319575Z       |                                                                    ^
2024-05-20T07:02:31.6320448Z In file included from /usr/include/c++/9/string:48,
2024-05-20T07:02:31.6321542Z                  from /home/ci/opencv/modules/core/include/opencv2/core/cvstd.hpp:56,
2024-05-20T07:02:31.6322846Z                  from /home/ci/opencv/modules/core/include/opencv2/core/base.hpp:58,
2024-05-20T07:02:31.6324092Z                  from /home/ci/opencv/modules/core/include/opencv2/core.hpp:53,
2024-05-20T07:02:31.6325320Z                  from /home/ci/opencv/modules/imgproc/include/opencv2/imgproc.hpp:46,
2024-05-20T07:02:31.6326962Z                  from /home/ci/opencv/modules/imgproc/src/precomp.hpp:46,
2024-05-20T07:02:31.6328036Z                  from /home/ci/opencv/modules/imgproc/src/approx.cpp:41:
2024-05-20T07:02:31.6329752Z /usr/include/c++/9/bits/stl_function.h:371:12: note: provided for 'template<class _Tp> struct std::greater'
2024-05-20T07:02:31.6331199Z   371 |     struct greater : public binary_function<_Tp, _Tp, bool>
2024-05-20T07:02:31.6332062Z       |            ^~~~~~~
2024-05-20T07:02:31.6333159Z /home/ci/opencv/modules/imgproc/src/approx.cpp:982:69: error: template argument 3 is invalid
2024-05-20T07:02:31.6334653Z   982 |     std::priority_queue<changes, std::vector<changes>, std::greater<>> areas;
2024-05-20T07:02:31.6335715Z       |                                                                     ^~
2024-05-20T07:02:31.6337626Z /home/ci/opencv/modules/imgproc/src/approx.cpp:1016:19: error: request for member 'push' in 'areas', which is of non-class type 'int'
2024-05-20T07:02:31.6339419Z  1016 |             areas.push(changes(area, vertex_id, Point2f(new_x, new_y)));
2024-05-20T07:02:31.6340356Z       |                   ^~~~
2024-05-20T07:02:31.6341978Z /home/ci/opencv/modules/imgproc/src/approx.cpp:1022:30: error: request for member 'top' in 'areas', which is of non-class type 'int'
2024-05-20T07:02:31.6343539Z  1022 |         changes base = areas.top();
2024-05-20T07:02:31.6344259Z       |                              ^~~
2024-05-20T07:02:31.6345922Z /home/ci/opencv/modules/imgproc/src/approx.cpp:1027:19: error: request for member 'pop' in 'areas', which is of non-class type 'int'
2024-05-20T07:02:31.6347456Z  1027 |             areas.pop();
2024-05-20T07:02:31.6348355Z       |                   ^~~
2024-05-20T07:02:31.6350005Z /home/ci/opencv/modules/imgproc/src/approx.cpp:1032:19: error: request for member 'pop' in 'areas', which is of non-class type 'int'
2024-05-20T07:02:31.6351520Z  1032 |             areas.pop();
2024-05-20T07:02:31.6352145Z       |                   ^~~
2024-05-20T07:02:31.6353772Z /home/ci/opencv/modules/imgproc/src/approx.cpp:1040:19: error: request for member 'push' in 'areas', which is of non-class type 'int'
2024-05-20T07:02:31.6355556Z  1040 |             areas.push(changes(area, vertex_id, Point2f(new_x, new_y)));
2024-05-20T07:02:31.6356470Z       |                   ^~~~

asmorkalov · 2024-05-21T08:14:00Z

Run cd c:\GHA-OCV-2\_work\opencv\opencv\build && python %CI_SCRIPTS%\warnings-handling.py
C:\GHA-OCV-2\_work\opencv\opencv\opencv\modules\imgproc\src\approx.cpp(989): warning C4244: 'initializing': conversion from 'double' to 'float', possible loss of data

C:\GHA-OCV-2\_work\opencv\opencv\opencv\modules\imgproc\src\approx.cpp(996): warning C4244: 'argument': conversion from '_Tp' to '_Tp', possible loss of data

C:\GHA-OCV-2\_work\opencv\opencv\opencv\modules\imgproc\src\approx.cpp(996): warning C4244: 'argument': conversion from '_Tp' to '_Tp', possible loss of data

C:\GHA-OCV-2\_work\opencv\opencv\opencv\modules\imgproc\src\approx.cpp(1075): warning C4244: 'argument': conversion from 'float' to '_Tp', possible loss of data

C:\GHA-OCV-2\_work\opencv\opencv\opencv\modules\imgproc\src\approx.cpp(1075): warning C4244: 'argument': conversion from 'float' to '_Tp', possible loss of data

modules/imgproc/src/approx.cpp

modules/imgproc/include/opencv2/imgproc.hpp

modules/imgproc/src/approx.cpp

modules/imgproc/include/opencv2/imgproc.hpp

modules/imgproc/src/approx.cpp

modules/imgproc/test/test_approxpoly.cpp

asmorkalov

👍

modules/imgproc/include/opencv2/imgproc.hpp

added ApproxBoundingPoly

d5664d7

Napkin-AI mentioned this pull request May 19, 2024

Added extra image for PR approxBoundingPoly opencv/opencv_extra#1179

Closed

asmorkalov added this to the 4.11.0 milestone May 20, 2024

asmorkalov added feature category: imgproc labels May 20, 2024

Napkin-AI added 2 commits May 20, 2024 19:10

add template and change assert

bafcfd6

type conversion

812623d

asmorkalov self-requested a review May 21, 2024 08:14

AleksandrPanov self-requested a review May 28, 2024 09:39

AleksandrPanov reviewed May 28, 2024

View reviewed changes

modules/imgproc/src/approx.cpp Outdated Show resolved Hide resolved

add enum instead of int

47663df

asmorkalov reviewed Jun 4, 2024

View reviewed changes

add doc and use reshape

ff0c92a

asmorkalov reviewed Jun 6, 2024

View reviewed changes

modules/imgproc/include/opencv2/imgproc.hpp Outdated Show resolved Hide resolved

add Tex reference, remove trailing whitespace

799d548

asmorkalov reviewed Jul 2, 2024

View reviewed changes

modules/imgproc/src/approx.cpp Outdated Show resolved Hide resolved

modules/imgproc/test/test_approxpoly.cpp Outdated Show resolved Hide resolved

Napkin-AI and others added 3 commits July 6, 2024 12:21

add synthetic test

793f248

Optimized OutputArray copy and added test for float output.

5e8be82

Test refactoring.

b8f3fe5

asmorkalov approved these changes Jul 9, 2024

View reviewed changes

vpisarev reviewed Jul 9, 2024

View reviewed changes

modules/imgproc/include/opencv2/imgproc.hpp Outdated Show resolved Hide resolved

Code review fixes.

37b0470

vpisarev self-requested a review July 9, 2024 12:02

vpisarev approved these changes Jul 9, 2024

View reviewed changes

asmorkalov assigned vpisarev Jul 9, 2024

asmorkalov merged commit b964943 into opencv:4.x Jul 9, 2024

asmorkalov mentioned this pull request Jul 16, 2024

(5.x) Merge 4.x #25915

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Add a new function that approximates the polygon bounding a convex hull with a certain number of sides#25607

Add a new function that approximates the polygon bounding a convex hull with a certain number of sides#25607
asmorkalov merged 10 commits intoopencv:4.xfrom
Napkin-AI:imgproc_approx_bounding_poly

Napkin-AI commented May 19, 2024 •

edited by AleksandrPanov

Loading

Uh oh!

asmorkalov commented May 20, 2024

Uh oh!

asmorkalov commented May 21, 2024

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!

asmorkalov left a comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

Uh oh!

Conversation

Napkin-AI commented May 19, 2024 • edited by AleksandrPanov Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Problem

Description

Complexity:

Comment

Pull Request Readiness Checklist

Uh oh!

asmorkalov commented May 20, 2024

Uh oh!

asmorkalov commented May 21, 2024

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!

asmorkalov left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

Napkin-AI commented May 19, 2024 •

edited by AleksandrPanov

Loading