4
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ Have you tried line following? How well does is cluster the points? $\endgroup$
    – Thijs Steel
    May 24, 2021 at 19:27

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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 (?) $\endgroup$
    – ellipsoid
    May 26, 2021 at 18:29
  • $\begingroup$ 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. $\endgroup$
    – Thijs Steel
    May 26, 2021 at 19:12
  • $\begingroup$ 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 $\endgroup$
    – ellipsoid
    May 26, 2021 at 19:19
  • 1
    $\begingroup$ 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 $\endgroup$
    – Thijs Steel
    May 26, 2021 at 19:58
  • $\begingroup$ 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? $\endgroup$
    – Thijs Steel
    May 26, 2021 at 20:05
1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – ellipsoid
    May 26, 2021 at 9:34
  • $\begingroup$ 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. $\endgroup$
    – ellipsoid
    May 26, 2021 at 9:45
  • $\begingroup$ 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. $\endgroup$
    – Bob
    May 26, 2021 at 10:32
  • $\begingroup$ 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? ) $\endgroup$
    – ellipsoid
    May 26, 2021 at 18:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bob
    May 27, 2021 at 8:39

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.