Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb964943

Browse files
authored
Merge pull request#25607 from Fest1veNapkin:imgproc_approx_bounding_poly
Add a new function that approximates the polygon bounding a convex hull with a certain number of sides#25607merge PR with <opencv/opencv_extra#1179>This PR is based on the paper [View Frustum Optimization To Maximize Object’s Image Area](https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=1fbd43f3827fffeb76641a9c5ab5b625eb5a75ba).# ProblemI 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](https://github.com/Fest1veNapkin/opencv/assets/98156294/efac35f6-b8f0-46ec-91e4-60800432620c)![image](https://github.com/Fest1veNapkin/opencv/assets/98156294/2292d9d7-1c10-49c9-8489-23221b4b28f7)# DescriptionInitially 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](https://github.com/Fest1veNapkin/opencv/assets/98156294/b87b21c4-112e-450d-a776-2a120048ca30)# 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](https://github.com/Fest1veNapkin/opencv/assets/98156294/31ad5562-a67d-4e3c-bdc2-29f8b52caf88)## CommentIf 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 ChecklistSee details athttps://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
1 parent8d935e2 commitb964943

File tree

4 files changed

+343
-0
lines changed

4 files changed

+343
-0
lines changed

‎doc/opencv.bib‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1467,3 +1467,12 @@ @article{SteweniusRecent
14671467
volume ={60},
14681468
journal ={ISPRS Journal of Photogrammetry and Remote Sensing}
14691469
}
1470+
@article{LowIlie2003,
1471+
author ={Kok-Lim Low, Adrian Ilie},
1472+
year ={2003},
1473+
pages ={3-15},
1474+
title ={View Frustum Optimization to Maximize Object's Image Area},
1475+
journal ={Journal of Graphics, (GPU, & Game) Tools (JGT)},
1476+
volume ={8},
1477+
url ={https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=1fbd43f3827fffeb76641a9c5ab5b625eb5a75ba}
1478+
}

‎modules/imgproc/include/opencv2/imgproc.hpp‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4058,6 +4058,28 @@ CV_EXPORTS_W void approxPolyDP( InputArray curve,
40584058
OutputArray approxCurve,
40594059
double epsilon,bool closed );
40604060

4061+
/** @brief Approximates a polygon with a convex hull with a specified accuracy and number of sides.
4062+
4063+
The cv::approxPolyN function approximates a polygon with a convex hull
4064+
so that the difference between the contour area of the original contour and the new polygon is minimal.
4065+
It uses a greedy algorithm for contracting two vertices into one in such a way that the additional area is minimal.
4066+
Straight lines formed by each edge of the convex contour are drawn and the areas of the resulting triangles are considered.
4067+
Each vertex will lie either on the original contour or outside it.
4068+
4069+
The algorithm based on the paper @cite LowIlie2003 .
4070+
4071+
@param curve Input vector of a 2D points stored in std::vector or Mat, points must be float or integer.
4072+
@param approxCurve Result of the approximation. The type is vector of a 2D point (Point2f or Point) in std::vector or Mat.
4073+
@param nsides The parameter defines the number of sides of the result polygon.
4074+
@param epsilon_percentage defines the percentage of the maximum of additional area.
4075+
If it equals -1, it is not used. Otherwise algorighm stops if additional area is greater than contourArea(_curve) * percentage.
4076+
If additional area exceeds the limit, algorithm returns as many vertices as there were at the moment the limit was exceeded.
4077+
@param ensure_convex If it is true, algorithm creates a convex hull of input contour. Otherwise input vector should be convex.
4078+
*/
4079+
CV_EXPORTS_WvoidapproxPolyN(InputArray curve, OutputArray approxCurve,
4080+
int nsides,float epsilon_percentage = -1.0,
4081+
bool ensure_convex =true);
4082+
40614083
/** @brief Calculates a contour perimeter or a curve length.
40624084
40634085
The function computes a curve length or a closed contour perimeter.

‎modules/imgproc/src/approx.cpp‎

Lines changed: 237 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -39,6 +39,7 @@
3939
//
4040
//M*/
4141
#include"precomp.hpp"
42+
#include<queue>
4243

4344
/****************************************************************************************\
4445
* Chain Approximation *
@@ -860,4 +861,240 @@ cvApproxPoly( const void* array, int header_size,
860861
return dst_seq;
861862
}
862863

864+
enumclassPointStatus :int8_t
865+
{
866+
REMOVED = -1,
867+
RECALCULATE =0,
868+
CALCULATED =1
869+
};
870+
871+
structneighbours
872+
{
873+
PointStatus pointStatus;
874+
cv::Point2f point;
875+
int next;
876+
int prev;
877+
878+
explicitneighbours(int next_ = -1,int prev_ = -1,const cv::Point2f& point_ = { -1, -1 })
879+
{
880+
next = next_;
881+
prev = prev_;
882+
point = point_;
883+
pointStatus = PointStatus::CALCULATED;
884+
}
885+
};
886+
887+
structchanges
888+
{
889+
float area;
890+
int vertex;
891+
cv::Point2f intersection;
892+
893+
explicitchanges(float area_,int vertex_,const cv::Point2f& intersection_)
894+
{
895+
area = area_;
896+
vertex = vertex_;
897+
intersection = intersection_;
898+
}
899+
900+
booloperator < (const changes& elem)const
901+
{
902+
return (area < elem.area) || ((area == elem.area) && (vertex < elem.vertex));
903+
}
904+
booloperator > (const changes& elem)const
905+
{
906+
return (area > elem.area) || ((area == elem.area) && (vertex > elem.vertex));
907+
}
908+
};
909+
910+
/*
911+
returns intersection point and extra area
912+
*/
913+
staticvoidrecalculation(std::vector<neighbours>& hull,int vertex_id,float& area_,float& x,float& y)
914+
{
915+
cv::Point2f vertex = hull[vertex_id].point,
916+
next_vertex = hull[hull[vertex_id].next].point,
917+
extra_vertex_1 = hull[hull[vertex_id].prev].point,
918+
extra_vertex_2 = hull[hull[hull[vertex_id].next].next].point;
919+
920+
cv::Point2f curr_edge = next_vertex - vertex,
921+
prev_edge = vertex - extra_vertex_1,
922+
next_edge = extra_vertex_2 - next_vertex;
923+
924+
float cross = prev_edge.x * next_edge.y - prev_edge.y * next_edge.x;
925+
if (abs(cross) <1e-8)
926+
{
927+
area_ = FLT_MAX;
928+
x = -1;
929+
y = -1;
930+
return;
931+
}
932+
933+
float t = (curr_edge.x * next_edge.y - curr_edge.y * next_edge.x) / cross;
934+
cv::Point2f intersection = vertex +cv::Point2f(prev_edge.x * t, prev_edge.y * t);
935+
936+
float area =0.5f *abs((next_vertex.x - vertex.x) * (intersection.y - vertex.y)
937+
- (intersection.x - vertex.x) * (next_vertex.y - vertex.y));
938+
939+
area_ = area;
940+
x = intersection.x;
941+
y = intersection.y;
942+
}
943+
944+
staticvoidupdate(std::vector<neighbours>& hull,int vertex_id)
945+
{
946+
neighbours& v1 = hull[vertex_id], & removed = hull[v1.next], & v2 = hull[removed.next];
947+
948+
removed.pointStatus = PointStatus::REMOVED;
949+
v1.pointStatus = PointStatus::RECALCULATE;
950+
v2.pointStatus = PointStatus::RECALCULATE;
951+
hull[v1.prev].pointStatus = PointStatus::RECALCULATE;
952+
v1.next = removed.next;
953+
v2.prev = removed.prev;
954+
}
955+
956+
/*
957+
A greedy algorithm based on contraction of vertices for approximating a convex contour by a bounding polygon
958+
*/
959+
voidcv::approxPolyN(InputArray _curve, OutputArray _approxCurve,
960+
int nsides,float epsilon_percentage,bool ensure_convex)
961+
{
962+
CV_INSTRUMENT_REGION();
963+
964+
CV_Assert(epsilon_percentage >0 || epsilon_percentage == -1);
965+
CV_Assert(nsides >2);
966+
967+
if (_approxCurve.fixedType())
968+
{
969+
CV_Assert(_approxCurve.type() == CV_32FC2 || _approxCurve.type() == CV_32SC2);
970+
}
971+
972+
Mat curve;
973+
int depth = _curve.depth();
974+
975+
CV_Assert(depth == CV_32F || depth == CV_32S);
976+
977+
if (ensure_convex)
978+
{
979+
cv::convexHull(_curve, curve);
980+
}
981+
else
982+
{
983+
CV_Assert(isContourConvex(_curve));
984+
curve = _curve.getMat();
985+
}
986+
987+
CV_Assert((curve.cols ==1 && curve.rows >= nsides)
988+
|| (curve.rows ==1 && curve.cols >= nsides));
989+
990+
if (curve.rows ==1)
991+
{
992+
curve = curve.reshape(0, curve.cols);
993+
}
994+
995+
std::vector<neighbours>hull(curve.rows);
996+
int size = curve.rows;
997+
std::priority_queue<changes, std::vector<changes>, std::greater<changes>> areas;
998+
float extra_area =0, max_extra_area = epsilon_percentage *static_cast<float>(contourArea(_curve));
999+
1000+
if (curve.depth() == CV_32S)
1001+
{
1002+
for (int i =0; i < size; ++i)
1003+
{
1004+
Point t = curve.at<cv::Point>(i,0);
1005+
hull[i] =neighbours(i +1, i -1,Point2f(static_cast<float>(t.x),static_cast<float>(t.y)));
1006+
}
1007+
}
1008+
else
1009+
{
1010+
for (int i =0; i < size; ++i)
1011+
{
1012+
Point2f t = curve.at<cv::Point2f>(i,0);
1013+
hull[i] =neighbours(i +1, i -1, t);
1014+
}
1015+
}
1016+
hull[0].prev = size -1;
1017+
hull[size -1].next =0;
1018+
1019+
if (size > nsides)
1020+
{
1021+
for (int vertex_id =0; vertex_id < size; ++vertex_id)
1022+
{
1023+
float area, new_x, new_y;
1024+
recalculation(hull, vertex_id, area, new_x, new_y);
1025+
1026+
areas.push(changes(area, vertex_id,Point2f(new_x, new_y)));
1027+
}
1028+
}
1029+
1030+
while (size > nsides)
1031+
{
1032+
changes base = areas.top();
1033+
int vertex_id = base.vertex;
1034+
1035+
if (hull[vertex_id].pointStatus == PointStatus::REMOVED)
1036+
{
1037+
areas.pop();
1038+
}
1039+
elseif (hull[vertex_id].pointStatus == PointStatus::RECALCULATE)
1040+
{
1041+
float area, new_x, new_y;
1042+
areas.pop();
1043+
recalculation(hull, vertex_id, area, new_x, new_y);
1044+
1045+
areas.push(changes(area, vertex_id,Point2f(new_x, new_y)));
1046+
hull[vertex_id].pointStatus = PointStatus::CALCULATED;
1047+
}
1048+
else
1049+
{
1050+
if (epsilon_percentage != -1)
1051+
{
1052+
extra_area += base.area;
1053+
if (extra_area > max_extra_area)
1054+
{
1055+
break;
1056+
}
1057+
}
1058+
1059+
size--;
1060+
hull[vertex_id].point = base.intersection;
1061+
update(hull, vertex_id);
1062+
}
1063+
}
1064+
1065+
if (_approxCurve.fixedType())
1066+
{
1067+
depth = _approxCurve.depth();
1068+
}
1069+
_approxCurve.create(1, size,CV_MAKETYPE(depth,2));
1070+
Mat buf = _approxCurve.getMat();
1071+
int last_free =0;
1072+
1073+
if (depth == CV_32S)
1074+
{
1075+
for (int i =0; i < curve.rows; ++i)
1076+
{
1077+
if (hull[i].pointStatus != PointStatus::REMOVED)
1078+
{
1079+
Point t =Point(static_cast<int>(round(hull[i].point.x)),
1080+
static_cast<int>(round(hull[i].point.y)));
1081+
1082+
buf.at<Point>(0, last_free) = t;
1083+
last_free++;
1084+
}
1085+
}
1086+
}
1087+
else
1088+
{
1089+
for (int i =0; i < curve.rows; ++i)
1090+
{
1091+
if (hull[i].pointStatus != PointStatus::REMOVED)
1092+
{
1093+
buf.at<Point2f>(0, last_free) = hull[i].point;
1094+
last_free++;
1095+
}
1096+
}
1097+
}
1098+
}
1099+
8631100
/* End of file.*/

‎modules/imgproc/test/test_approxpoly.cpp‎

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -377,4 +377,79 @@ TEST(Imgproc_ApproxPoly, bad_epsilon)
377377
ASSERT_ANY_THROW(approxPolyDP(inputPoints, outputPoints, eps,false));
378378
}
379379

380+
structApproxPolyN:publictesting::Test
381+
{
382+
voidSetUp()
383+
{
384+
vector<vector<Point>> inputPoints = {
385+
{ {87,103}, {100,112}, {96,138}, {80,169}, {60,183}, {38,176}, {41,145}, {56,118}, {76,104} },
386+
{ {196,102}, {205,118}, {174,196}, {152,207}, {102,194}, {100,175}, {131,109} },
387+
{ {372,101}, {377,119}, {337,238}, {324,248}, {240,229}, {199,214}, {232,123}, {245,103} },
388+
{ {463,86}, {563,112}, {574,135}, {596,221}, {518,298}, {412,266}, {385,164}, {462,86} }
389+
};
390+
391+
Matimage(600,600, CV_8UC1,Scalar(0));
392+
393+
for (vector<Point>& polygon : inputPoints) {
394+
polylines(image, { polygon },true,Scalar(255),1);
395+
}
396+
397+
findContours(image, contours, RETR_LIST, CHAIN_APPROX_NONE);
398+
}
399+
400+
vector<vector<Point>> contours;
401+
};
402+
403+
TEST_F(ApproxPolyN, accuracyInt)
404+
{
405+
vector<vector<Point>> rightCorners = {
406+
{ {72,187}, {37,176}, {42,127}, {133,64} },
407+
{ {168,212}, {92,192}, {131,109}, {213,100} },
408+
{ {72,187}, {37,176}, {42,127}, {133,64} },
409+
{ {384,100}, {333,251}, {197,220}, {239,103} },
410+
{ {168,212}, {92,192}, {131,109}, {213,100} },
411+
{ {333,251}, {197,220}, {239,103}, {384,100} },
412+
{ {542,6}, {596,221}, {518,299}, {312,236} },
413+
{ {596,221}, {518,299}, {312,236}, {542,6} }
414+
};
415+
EXPECT_EQ(rightCorners.size(), contours.size());
416+
417+
for (size_t i =0; i < contours.size(); ++i) {
418+
std::vector<Point> corners;
419+
approxPolyN(contours[i], corners,4, -1,true);
420+
ASSERT_EQ(rightCorners[i], corners );
421+
}
422+
}
423+
424+
TEST_F(ApproxPolyN, accuracyFloat)
425+
{
426+
vector<vector<Point2f>> rightCorners = {
427+
{ {72.f,187.f}, {37.f,176.f}, {42.f,127.f}, {133.f,64.f} },
428+
{ {168.f,212.f}, {92.f,192.f}, {131.f,109.f}, {213.f,100.f} },
429+
{ {72.f,187.f}, {37.f,176.f}, {42.f,127.f}, {133.f,64.f} },
430+
{ {384.f,100.f}, {333.f,251.f}, {197.f,220.f}, {239.f,103.f} },
431+
{ {168.f,212.f}, {92.f,192.f}, {131.f,109.f}, {213.f,100.f} },
432+
{ {333.f,251.f}, {197.f,220.f}, {239.f,103.f}, {384.f,100.f} },
433+
{ {542.f,6.f}, {596.f,221.f}, {518.f,299.f}, {312.f,236.f} },
434+
{ {596.f,221.f}, {518.f,299.f}, {312.f,236.f}, {542.f,6.f} }
435+
};
436+
EXPECT_EQ(rightCorners.size(), contours.size());
437+
438+
for (size_t i =0; i < contours.size(); ++i) {
439+
std::vector<Point2f> corners;
440+
approxPolyN(contours[i], corners,4, -1,true);
441+
EXPECT_LT(cvtest::norm(rightCorners[i], corners, NORM_INF), .5f);
442+
}
443+
}
444+
445+
TEST_F(ApproxPolyN, bad_args)
446+
{
447+
Matcontour(10,1, CV_32FC2);
448+
vector<vector<Point>> bad_contours;
449+
vector<Point> corners;
450+
ASSERT_ANY_THROW(approxPolyN(contour, corners,0));
451+
ASSERT_ANY_THROW(approxPolyN(contour, corners,3,0));
452+
ASSERT_ANY_THROW(approxPolyN(bad_contours, corners,4));
453+
}
454+
380455
}}// namespace

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp