Rectangle or Ellipse

[Gronne]

The ellipse-detection has a tendency to detect rectangles (like the paper around the RobotEllipses) as ellipses as well. An extra method is needed in RobotEllipseFiltering to filter the rectangle-ellipses out.

[CThuleHansen]

@Gronne This is how And you can keep writing

[CThuleHansen]

Rectangle_or_Ellipse_problem.pdf

[nickbattle]

I've only read this problem description briefly, but I wonder whether this can be done by trying to fit a linear equation to the points, starting with two and adding a third, fourth and so on. For polygons of low order you would get a good linear fit as you progress along an edge until the end, at which point you would start to see the fit get worse and worse, so you restart the fit from when it started to diverge and proceed until the next corner, etc. At the end there should be a small number of linear segments. With an ellipse, or any non-linear shape, you should get a poor fit after a few points and not really ever be able to fit more than a few points to a straight line. And in the middle, polygons of very high order would look like curved shapes... but then they do!

Might something like that work?

[Daniella1]

Ellipse_problem_ideas.pdf

[nickbattle]

The attached sort-of does what I was trying to explain (in VDM-SL). You would need to tune the LIMIT values, depending on how much noise there is in the readings, I suspect. The listEdges function lists the edge-subsequences, so if you have a large number of these, you either have a high-order polygon or a curved shape of some sort:

Parsed 1 module in 0.09 secs. No syntax errors
Type checked 1 module in 0.253 secs. No type errors
Initialized 1 module in 0.162 secs. 
Interpreter started
> p listEdges(SQUARE)
= [[mk_P(0, 0), mk_P(0, 1), mk_P(0, 2)], [mk_P(0, 2), mk_P(1, 2), mk_P(2, 2)], [mk_P(2, 2), mk_P(2, 1), mk_P(2, 0)], [mk_P(2, 0), mk_P(1, 0)]]
Executed in 0.018 secs. 
> p len listEdges(SQUARE)
= 4
Executed in 0.016 secs. 
> p listEdges(LINE)
= [[mk_P(0, 0), mk_P(0, 1), mk_P(0, 2)]]
Executed in 0.002 secs. 
> p len listEdges(LINE)
= 1
Executed in 0.002 secs. 
> p listEdges(ELIPSE)
= [[mk_P(1, 2), mk_P(1, 3), mk_P(1, 4)], [mk_P(1, 4), mk_P(2, 5), mk_P(3, 6)], [mk_P(3, 6), mk_P(4, 6), mk_P(5, 6)], [mk_P(5, 6), mk_P(6, 5), mk_P(7, 4)], [mk_P(7, 4), mk_P(7, 3)], [mk_P(7, 3), mk_P(6, 2)], [mk_P(6, 2), mk_P(6, 1)], [mk_P(6, 1), mk_P(5, 0)], [mk_P(5, 0), mk_P(4, 0), mk_P(3, 0)], [mk_P(3, 0), mk_P(2, 1)]]
Executed in 0.012 secs. 
> p len listEdges(ELIPSE)
= 10
Executed in 0.015 secs. 
> 

Spec attached: PolyOrCurve.vdmsl.txt

[Gronne]

Thanks, @Daniella1 and @nickbattle, I will try your ideas tomorrow and the day after to see if they work. Both of them look promising! An update will be posted when I have tested them:)

[nickbattle]

If you can give me a list of coordinates (either for a rectangle or ellipse), I can easily convert to VDM-SL and try the model, if that helps - it would otherwise take you a while to get set up with Overture etc.

[Gronne]

@nickbattle thank you for the offer to help. I have four lists; two ellipses and two rectangles. I need to have it implemented in Python, but it would be great to test whether the method workes before the implementation. I will post the lists at noon (around 15:30 danish time).

[clegaard]

@Gronne another approach is to use standard fiducial markers such as ARUCO (similar to QR-codes). The most important benefit is that tried and tested algorithms exist for these in OpenCV or similar.

See:

• OpenCV's ARUCO documentation
• Example on how to use in Python

If you want to dig a bit deeper, I found a few references for you:

• Speeded up detection of squared fiducial markers

^^ this one lists performance and error of various algorithm implementations

• Automatic generation and detection of highly reliable fiducial markers under occlusion

• Fractal Markers: A New Approach for Long-RangeMarker Pose Estimation Under Occlusion

[nickbattle]

I will post the lists at noon (around 15:30 danish time).

Did Denmark change timezone? :-) but I look forward to trying it with real data, thanks. I can usually convert any simple data format to VDM-SL, though something like CSV would be easiest.

[Gronne]

Not edge cases, but two squares and two ellipses in a .txt file

Sqaure2.txt Ellipse1.txt Ellipse2.txt Sqaure1.txt

[nickbattle]

OK, thanks for those. Massaging the data into VDM-SL and processing produces the following:

> p len listEdges(SQUARE1)
= 4
Executed in 0.091 secs. 
> p len listEdges(SQUARE2)
= 4
Executed in 0.038 secs. 
> p len listEdges(ELLIPSE1)
= 39
Executed in 0.016 secs. 
> p len listEdges(ELLIPSE2)
= 31
Executed in 0.022 secs. 
> 

So the SQUAREs are polygons with four sides (they could be any sort of quadrilateral, but four sided), and the ELLIPSEs are either curves or polygons with over 30 sides... which are probably curves(!!).

So this seems to work, and even in the VDM interpreter it's pretty fast. I have some concerns about the algorithm, but perhaps you could test it with more examples to see whether it does what you need? I'll attach an updated spec that includes your own test data and more comments, so that it's hopefully easy to convert into Python.

PolyOrCurve.vdmsl.txt

[Gronne]

Hello @Daniella1 , @nickbattle , and @clegaard . I got it to work, thanks for the help :) I have tried to implement Daniella's and Nick's, both worked and also relatively fast. The execution time is still a problem and has resulted in it being a feature you can switch on and off. Maybe it can be optimized more in the future. Thanks again.