4

EDIT: Added another, more suitable, example below.

Disclaimer: With edge map I mean an image given as bitmap just consisting of black and white pixels.

Short description:
Briefly, I'm searching for fast, practical algorithms (or, even better, working implementations) to extract the parameters of (complete, possibly rotated) geometric objects from images give as bitmap as the following, in order to find objects which are "special" (e.g. in the sense of being completely included in another one like the small ellipse on the right). Is the Hough Transform or a successor the way to go? (Part of) An example image

More details:
In particular, I'm searching for triangles, rectangulars, and ellipses of images where the edges are already (perfectly) extracted. As mostly (possibly rotated) ellipses occur, which seemingly are the hardest objects, I'd like to start with these. As the example illustrates, some objects only partially lie in the image and should be discarded (i.e. can be seen as kind of distortion or noise. This noise can be seen as ellipses with relatively huge axes). Overlapping objects, however, should be detected. I have rough bounds on the axes' parameters. After having found the parameters I want to pick specific objects, for example the ones which are completely included in another one. Maybe detecting all objects in order to achieve this is too excessive?

My research so far:
Up to now, I stumbled accross several algorithms and implementations. Most notably based on the Hough Transform, which solves the problem in the (dual) parameter space using a voting scheme. However, the general Hough transform is rather slow. The implementations from 3, 4,5, and 6 should be faster but are not suited for the images at hand or I'm just too dumb to apply them correctly (which can absolutely be the case). At least for me, the implementations were either "confused" by the distorting, incomplete objects (whoch can be several hundreds), or did not find all objects. Since I only care about completed objects with intact edges, maybe some sort of edge following might also work?

My question:
As I'm not experienced in the image/object detection at all, I don't know whether I'm on the right track when considering the Hough transform for my problem. Is it the way to go, or do you know other algorithms or existing implementations solving the task at hand?

EDIT: As the ellipses are the main problem, which was not represented sufficiently good, I'll add another image. Again, this is just a part of the image which is provided as bitmap consisting of black and white pixels. I highlighted the ellipsis within the ellipsis in blue, while the other complete ellipsis is highlighted brown-ish. In general, there might be up to 30 objects of interest but few hundered disturbing ones (Isn't this always the case?! :/ ). Another, so far missing, information is that the "noisy", incomplete ellipses are different by having larger axes compared to the rather small wanted objects! (I'll also add the information above). Maybe the Hough transform becomes practical if I can find suitable parameter ranges for the small ellipses. Another idea just popping into my mind is that of detecting segments and deleting those with too low slope.

Second example with the wanted objects highlighted and more noise

ellipsoid
  • 41
  • 4

2 Answers2

1

A. Convex polygon inside convex shape

Since all objects are convex, if two endpoints of a line segment are inside an object the entire line is in the segment, and if all the edges of a convex polygon are inside an object the entire polygon is inside that object. This way you can detect if triangles are inside of triangles, rectangles or ellipses. If rectangles are inside triangles, rectangles or ellipsis.

B. Ellipsis inside a polygon

To detect if the ellipsis are inside polygon I would transform the space so that the ellipsis become a circle, then using comparing the closest point to the circle center in a segment (point from which a perpendicular line hit the circle center or the endpoint closest to the circle center), if the distance from such point to the center is less than the radius than the ellipsis is not completely enclosed. If the circle center is not inside the polygon the ellipsis is not inside the polygon.

Ellipsis inside ellipsis

This question was already asked here, all the answers there use some sort of numerical method. And I think this is the way to go, I have to admit, initially I thought the system of inequalities could be reduced to one single conic, but it gives a quartic equation.

Bob
  • 156
  • 5
  • Thanks for your hint regarding convexity, haven't considered it from that point of view so far! However, you are solving the problem "Given a set of $N$ convex objects (either by their edges or, in case of ellipses, by concrete parameters), detect the objects completely contained in some other object", right? I think, this is what you meant by "Easy part", since the detection of objects is abstracted aways. Or did I get it completely wrong? – ellipsoid May 26 '21 at 09:34
  • Regarding the second suggestion: 1) In order to check all, say $k$-many, ellipses for "containment" I'd need to transform the whole space, i.e. all objects $k$ times, right? 2) This does not apply to checking ellipses within ellipses, right? However, assuming the parameters are given, this should become easy without transformation, I guess. – ellipsoid May 26 '21 at 09:45
  • Sorry, that easy part is something I should have removed, I initially would write the post differently. By your drawing the ellipsis are not rotated, then yes, it is easy to check. – Bob May 26 '21 at 10:32
  • Thanks for the clarification and rewriting of your answer. Especially your last finding regarding ellipsis-containment will possibly become handy. Still, the problem of finding the objects itself remains (? Or did I miss something in between the lines? ) – ellipsoid May 26 '21 at 18:04
  • 1
    By your description I understood that you had already the objects, to extract the objects is more difficult and for the triangles and rectangles there may be multiple solutions, specially triangles. I would try to find contours, then for the arcs I would fit ellipsis individually and cluster them on the parameter spaces. Then for the lines I would try to reduce that to a minimum set coverage problem. – Bob May 27 '21 at 08:39
1

I propose a simple solution, but whether it works will depend on how well line following can separate the groups and how fast the ellips fitting works.

Step 1, follow lines to separate the edge points into groups, each group corresponding to a single object.

Step 2, determine whether the object is complete. A simple pruning is to see if any of the points lie on the edge. If there are such points, check there for gaps in the object.

Step 3, fit an object to the points (this should be faster than a hough transform because you already know the points). For extra speed, you can do the ellips fitting in a multi level scheme.

Step 4, use these representations to identify the desired objects.

Disclaimer: This will likely require some manual coding. So it is not certain that this will be faster than a highly optimised hough transform.

Thijs Steel
  • 1,693
  • 8
  • 16
  • Though the idea is appealing, unfortunately, I think "line following" is not that easy to achieve, as some objets do overlap massively (I'll add another example above). Additonally, I have to admit, I don't get your second point (due to my lack of expertise). Since the image just consists of the edges/points, there is no point which is not on an edge (?) – ellipsoid May 26 '21 at 18:29
  • yeah, it's a simple solution that's not very robust, but the image might just be simple enough to work, the edges look very well defined and sharp. – Thijs Steel May 26 '21 at 19:12
  • Yep, the edges themselves are sharp. But aren't the overlaps a problem? E.g. in the added second example above, the upper part of the bigger blue ellipse is partially covered by a "noisy" big one. Maybe I've got a wrong understanding of line following. Are there some (literature) pointers to start with or do you have some explanation? :D – ellipsoid May 26 '21 at 19:19
  • 1
    i don't have any literature to point you to. I did some hacky line following for my bachelor thesis a long time ago. There, i was looking for edges of triangles and it could handle overlap by following the gradient – Thijs Steel May 26 '21 at 19:58
  • i can think of many other solutions, but those are unlikely to beat a hough transform. Btw, with your image, the hough transform really shouldn't take that long. What implementation are you using? – Thijs Steel May 26 '21 at 20:05
  • Well, considering the gradient, due to the big differences of the axes' parameters, actually might be promising. So far I applied 2 Python implementations, namely SciKit and one from GitHub. While the former did not terminate at all, the latter provided bad-fitted ellipses. Additionally, I tried another (pre-compiled) C++ implementation. – ellipsoid May 27 '21 at 13:36
  • In addition to the libraries tested above: For some libraries I fail to install it properly, as I'm not experieced with C++ and resolving many of the dependency errors. Just getting to run some of the libraries therefore requires much time for me, and after the first successes weren't paying off, I chose to first ask which approach is the most promising one in the eyes of experts. Especially as the problem itself, i.e. whether a somewhat less generic, faster approach exists, made me curious. – ellipsoid May 27 '21 at 13:43