2
$\begingroup$

I'm currently facing the problem of efficiently detecting (special) ellipses in edge images. These images are given (i.e. previous image processing is impossible) and contain quite some noise. I need to detect those ellipses which are completely contained in another ellipsis. The following images gives a reduced example where the desired ellipsis is marked by the blue arrow. Usually the images contain 30-40 "perfect" small ellipses and only 1-2 which are "overlayed". I also added the image without blue arrow, if you want to try it yourself. Below I added some more examples.

enter image description here Example edge image of problem

Disclaimer: I'm unsure how to tackle this problem. I'm no expert in computer vision or computational geometry and hope for your help (as well as apologize for using imprecise terms). Also, if you think this topic suits another community better, I'm thankful for suggestions.

My research first led me to the Hough Transform, but due to its complexity of detecting ellipses this seems rather inefficient. Also I have not yet managed to get implementations to work on my images. Maybe I parametrized stuff wrong or am just to stupid to use the frameworks. Can you suggest frameworks and/or configurations able to solve this problem (not relying on MATLAB, if possible)?

Maybe the Hough transform is over the top as it finds all ellipses. As said, I only need to find the completely overlaying ones, if they exist. Are you aware of any approaches which are useful for that? It seems like an interesting algorithmic problem which might have been tackled (in theory or practice) before. Maybe something heading to sweeping lines?

Lastly, as AI is currently a big thing, I also wanted to mention it. But I wouldn't even know where to start. Also, I have no big training or test sets and the problem seems to be more appropriate to "usual" algorithmic approaches. Or am I wrong?

Update:

As requested in the comments, in the following I provide some more examples, with the first one being the most representative. example example example

Improve this question
$\endgroup$
8
  • $\begingroup$ Can you share more examples? You current example can be easily generated by code, is this the case? $\endgroup$
    – Royi
    Commented Mar 23 at 10:50
  • $\begingroup$ @Royi I added few more examples! Yes, they could be generated by code (which, however, does not change the requirement of visually extracting the desired targets) $\endgroup$
    – hello_darkness
    Commented Mar 25 at 10:07
  • $\begingroup$ Since you can generate those, using Deep Learning would probably be a good path to take. $\endgroup$
    – Royi
    Commented Mar 25 at 11:49
  • $\begingroup$ This might be a way, but there are some issues: 1) I have no concrete parameters but could try to estimate them from few examples (e.g. the clear distinction between small&big ellipses) 2) The problem itself feels like their should be a clean, efficient way to solve it analytically/algorithmically. Maybe I'm wrong (?) 3) I'm no expert in AI, but you suggest "generate representative images. Hand them alongside the (in this case known) target area to Deep Learning algorithm X" (?). Even if I find a way find a good way to approximate the images: What should X be? Run it for how long? $\endgroup$
    – hello_darkness
    Commented Mar 25 at 12:09
  • $\begingroup$ It won't be robust, but I think some sort of greedy algorithm will be able to at least assign every black pixel to an ellipse. Start on a black pixel, find a neightboring black pixel, then find the next pixel in the rough direction of the tangent vector. This will ensure you jump over intersections. Once every black pixel is assigned to an ellipse, then the problem reduces to determining whether one set of points is contained in the convex hull of another set of points. $\endgroup$
    – whpowell96
    Commented Mar 25 at 18:12

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.