OpenCV Q&A Forum - RSS feedhttp://answers.opencv.org/questions/OpenCV answersenCopyright <a href="http://www.opencv.org">OpenCV foundation</a>, 2012-2018.Wed, 25 Jul 2018 08:17:09 -0500a question from《learning opencv3》 chapter 14http://answers.opencv.org/question/196330/a-question-fromlearning-opencv3-chapter-14/Hi,i have some problem when soloving a question from《learning opencv3》 chapter 14
the question is
1. We can find the extremal points (i.e., the two points that are farthest apart) in a
closed contour of N points by comparing the distance of each point to every
other point.
a. What is the complexity of such an algorithm?
b. Explain how you can do this faster.
I think ,the answer of a is O(N*N) (am i right),but to b,the only idea i can think out is
Finding the convex hull of the contour,
do the algorithm above at the convex hull .
ami i right?or better solution?
thanks！
jsxyheluWed, 25 Jul 2018 01:44:05 -0500http://answers.opencv.org/question/196330/a-question-fromlearning-opencv3-chapter-14/Comment by jsxyhelu for <p>Hi,i have some problem when soloving a question from《learning opencv3》 chapter 14</p>
<p>the question is </p>
<ol>
<li><p>We can find the extremal points (i.e., the two points that are farthest apart) in a
closed contour of N points by comparing the distance of each point to every
other point.</p>
<p>a. What is the complexity of such an algorithm?</p>
<p>b. Explain how you can do this faster.</p></li>
</ol>
<p>I think ,the answer of a is O(N*N) (am i right),but to b,the only idea i can think out is</p>
<p>Finding the convex hull of the contour,
do the algorithm above at the convex hull .</p>
<p>ami i right?or better solution?</p>
<p>thanks！</p>
<p>jsxyhelu</p>
http://answers.opencv.org/question/196330/a-question-fromlearning-opencv3-chapter-14/?comment=196376#post-id-196376boundingRect sounds good,but boundingRect is a function of RotatedRect and we use minAreaRect to get it.
RotatedRect minRect = minAreaRect( Mat(contours[i]) );
Point2f rect_points[4];
minRect.points( rect_points );
Finally minAreaRect is basd on hull
cv::RotatedRect cv::minAreaRect( InputArray _points )
{
CV_INSTRUMENT_REGION()
Mat hull;
Point2f out[3];
RotatedRect box;
convexHull(_points, hull, true, true);
if( hull.depth() != CV_32F )
{
Mat temp;
hull.convertTo(temp, CV_32F);
hull = temp;
}Wed, 25 Jul 2018 08:17:09 -0500http://answers.opencv.org/question/196330/a-question-fromlearning-opencv3-chapter-14/?comment=196376#post-id-196376Comment by LBerger for <p>Hi,i have some problem when soloving a question from《learning opencv3》 chapter 14</p>
<p>the question is </p>
<ol>
<li><p>We can find the extremal points (i.e., the two points that are farthest apart) in a
closed contour of N points by comparing the distance of each point to every
other point.</p>
<p>a. What is the complexity of such an algorithm?</p>
<p>b. Explain how you can do this faster.</p></li>
</ol>
<p>I think ,the answer of a is O(N*N) (am i right),but to b,the only idea i can think out is</p>
<p>Finding the convex hull of the contour,
do the algorithm above at the convex hull .</p>
<p>ami i right?or better solution?</p>
<p>thanks！</p>
<p>jsxyhelu</p>
http://answers.opencv.org/question/196330/a-question-fromlearning-opencv3-chapter-14/?comment=196371#post-id-196371use boundingRect?Wed, 25 Jul 2018 06:45:01 -0500http://answers.opencv.org/question/196330/a-question-fromlearning-opencv3-chapter-14/?comment=196371#post-id-196371Comment by StevenPuttemans for <p>Hi,i have some problem when soloving a question from《learning opencv3》 chapter 14</p>
<p>the question is </p>
<ol>
<li><p>We can find the extremal points (i.e., the two points that are farthest apart) in a
closed contour of N points by comparing the distance of each point to every
other point.</p>
<p>a. What is the complexity of such an algorithm?</p>
<p>b. Explain how you can do this faster.</p></li>
</ol>
<p>I think ,the answer of a is O(N*N) (am i right),but to b,the only idea i can think out is</p>
<p>Finding the convex hull of the contour,
do the algorithm above at the convex hull .</p>
<p>ami i right?or better solution?</p>
<p>thanks！</p>
<p>jsxyhelu</p>
http://answers.opencv.org/question/196330/a-question-fromlearning-opencv3-chapter-14/?comment=196370#post-id-196370ow sorry, did not read with attention. Extremal points are for me points that deviate from a general outline or trajectory, but it seems here, that they want the actual 2 points that are the farthest away from eachother. No idea how to speed that up xDWed, 25 Jul 2018 06:43:13 -0500http://answers.opencv.org/question/196330/a-question-fromlearning-opencv3-chapter-14/?comment=196370#post-id-196370Comment by jsxyhelu for <p>Hi,i have some problem when soloving a question from《learning opencv3》 chapter 14</p>
<p>the question is </p>
<ol>
<li><p>We can find the extremal points (i.e., the two points that are farthest apart) in a
closed contour of N points by comparing the distance of each point to every
other point.</p>
<p>a. What is the complexity of such an algorithm?</p>
<p>b. Explain how you can do this faster.</p></li>
</ol>
<p>I think ,the answer of a is O(N*N) (am i right),but to b,the only idea i can think out is</p>
<p>Finding the convex hull of the contour,
do the algorithm above at the convex hull .</p>
<p>ami i right?or better solution?</p>
<p>thanks！</p>
<p>jsxyhelu</p>
http://answers.opencv.org/question/196330/a-question-fromlearning-opencv3-chapter-14/?comment=196365#post-id-196365but the " the two points that are farthest apart" must not be direct neighbourhood.
sorry i did not get your idea.Wed, 25 Jul 2018 06:11:53 -0500http://answers.opencv.org/question/196330/a-question-fromlearning-opencv3-chapter-14/?comment=196365#post-id-196365Comment by StevenPuttemans for <p>Hi,i have some problem when soloving a question from《learning opencv3》 chapter 14</p>
<p>the question is </p>
<ol>
<li><p>We can find the extremal points (i.e., the two points that are farthest apart) in a
closed contour of N points by comparing the distance of each point to every
other point.</p>
<p>a. What is the complexity of such an algorithm?</p>
<p>b. Explain how you can do this faster.</p></li>
</ol>
<p>I think ,the answer of a is O(N*N) (am i right),but to b,the only idea i can think out is</p>
<p>Finding the convex hull of the contour,
do the algorithm above at the convex hull .</p>
<p>ami i right?or better solution?</p>
<p>thanks！</p>
<p>jsxyhelu</p>
http://answers.opencv.org/question/196330/a-question-fromlearning-opencv3-chapter-14/?comment=196344#post-id-196344I would look for extremal points by only comparing to the direct neighbourhood of the contour, lets say 50 points to left and 50 to right. To me it makes no sence if you have a large object, to compare the distance between a possible extremal point and the other side of the object, far away from the actual points. A convex hull would work, but in principle it will not reduce the amount of points that much.Wed, 25 Jul 2018 03:50:46 -0500http://answers.opencv.org/question/196330/a-question-fromlearning-opencv3-chapter-14/?comment=196344#post-id-196344