Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Open
wants to merge 4 commits into
base: 4.x
Choose a base branch
from
Open

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

wants to merge 4 commits into from

Conversation

Fest1veNapkin
Copy link

@Fest1veNapkin Fest1veNapkin commented May 19, 2024 •
edited by AleksandrPanov

merge PR with opencv/opencv_extra#1179

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.

image

image

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

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

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

@Fest1veNapkin Fest1veNapkin mentioned this pull request May 19, 2024
Open
@asmorkalov asmorkalov added this to the 4.11.0 milestone May 20, 2024
@asmorkalov
Copy link
Contributor 

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
Copy link
Contributor 

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

@asmorkalov asmorkalov self-requested a review May 21, 2024 08:14
@AleksandrPanov AleksandrPanov self-requested a review May 28, 2024 09:39
AleksandrPanov
AleksandrPanov reviewed May 28, 2024
View reviewed changes
modules/imgproc/src/approx.cpp Outdated
if relevant = 0, the intersection in the heap must be recalculated
if relevant = 1, intersection has been calculated
*/
short relevant;
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

use int8_t instead of short or use enum class

Also suggest to rename relevant to pointStatus

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@AleksandrPanov AleksandrPanov AleksandrPanov left review comments

@asmorkalov asmorkalov Awaiting requested review from asmorkalov

Assignees
No one assigned
Labels
category: imgproc feature
Projects
None yet
Milestone
4.11.0
Development

Successfully merging this pull request may close these issues.

None yet
3 participants
@Fest1veNapkin @asmorkalov @AleksandrPanov