3

I have a set of 2D points and I want to find the potential largest empty circle. By that, I don't mean to code the Largest Empty Circle algorithm.

Here's an image trying to explain my words.

enter image description here

enter image description here

As you can see, there are points inside that circle, so what I want is an algorithm that given that set of 2D points, could compute that circle.

That set of points represents a wall of a sewer which contains a hole. The problem is that this hole may be corked, may contain some dirt at one or more sides of the circle. So, when you laser detect that part, you don't obtain a perfect circle, but kind of a semicircle. What I want to find is the original hole, the clean hole, when there is no dirt. When I say potential, I mean the original hole. In the image, the green circle is the original hole and the points inside that circle are some kind of dirt. The final purpose of this is to decide whether the hole is clean or dirty (Detecting how many points are inside that green circle and decide how dirty it is)

Another example of how it is supposed to be in real life:

enter image description here

Here you can see that the hole has dirt in the bottom part (could be any side of the hole), so when you laser detect it, you don't obtain the circle, but a bunch of points with the upper part of the circle as empty. What I want is from that set of points where you can only see the upper part of the circle empty, reconstruct the original hole, as it was when clean.

Plus, I attach two images of the point cloud, from two different perspectives, so you can know what I am working with.

enter image description here

enter image description here

Nakilon
  • 34,866
  • 14
  • 107
  • 142
avm_69
  • 183
  • 2
  • 11
  • 3
    what do you mean with "potential largest empty circle"? the one in the image is neither empty nor "largest" in any obvious sense – 463035818_is_not_an_ai Apr 06 '16 at 11:45
  • What I mean is that given this 2D point set, detect the potential largest empty circle. By potential, I mean that continuing to apply the radius tangency to the upper part of the circle, complete the whole circle. In more general terms, that green circle represents a hole which lower part is corked. What I want to find is how is the hole supposed to be when not corked. That means finding that green hole (and the points that are inside the green hole are the parts that are "corking" the hole") – avm_69 Apr 06 '16 at 11:51
  • 2
    It's very unclear, to me at least, what you mean. Can you show some different sets of points and what the answer would be for each? – Mark Setchell Apr 06 '16 at 11:55
  • 1
    sorry, but now I am even more confused than before. – 463035818_is_not_an_ai Apr 06 '16 at 11:55
  • 1
    Please describe your problem clearly both in Image & in your problem statement – Balaji R Apr 06 '16 at 11:57
  • Sorry about that. That set of points represents a wall of a sewer which contains a hole. The problem is that this hole may be corked, may contain some dirt at the bottom or at the top. So, when you laser detect that part, you don't obtain a perfect circle, but kind of a semicircle. What I want to find is the original hole, the clean hole, when there is no dirt. When I say potential, I mean the original hole. In the image, the green circle is the original hole and the points inside that circle are some kind of dirt. The final purpose of this is to decide whether the hole is clean or dirty. – avm_69 Apr 06 '16 at 12:00
  • Are you sure that the dirt can be only at either the bottom or the top? not on a side for example? – Marco Apr 06 '16 at 12:26
  • 2
    i think if the sample image represents the quality of the actual source data, it might be a pretty difficult task, since if you connect the points on the free border (http://www.mtcelestia.org/hole.png), even a human will only be able to give a very approximate answer – Anton Knyazyev Apr 06 '16 at 12:34
  • @Marco No, my fault, it could also be on a side. – avm_69 Apr 06 '16 at 13:02
  • The size of the circle is fixed or it can change ? – Marco Apr 06 '16 at 13:07
  • @Marco It can change, It depends on the size of the hole. Plus, the number of points inside that circle is variable (depending on the dirt inside of the hole) For example, http://i.imgur.com/ldALw22.png – avm_69 Apr 06 '16 at 14:01
  • Given your dataset, how do **you** decide that your circle is that big, and not 5 pixels larger/smaller in diameter? – Yuri Apr 06 '16 at 14:12
  • @Yuri The image I have shown is an approximation of what the algorithm should return, it's just an image in Paint. I guess that knowing, for example, the 20% of the top of a circle you could construct the rest. Once known how is the upper 20% of the circle, you could construct the whole circle (and detect the inner points of that circle aka dirt) – avm_69 Apr 06 '16 at 14:17
  • 1
    So.. of the following image, which one is the actual circle? http://i.imgur.com/1JyQQ3a.png . You can't tell for sure unless you define a formal constraint. Try to start there. (and yes, my paint skills are worse than yours ;) – Yuri Apr 06 '16 at 14:28
  • @Yuri No, I can't tell for sure on your image. But the images I provide are different in the sense that I have a much more dense space and the upper part of the circle is well seen. You can assume that the part of the hole that is visible is just like the reality (no matter if it is 10%, 20% or 80% of the original hole). Then, I guess that from that you could construct the rest of the circle. In this image I try to explain what I want. http://i.imgur.com/kB46wHn.png And when you say formal constraint, what do you mean exactly? Thanks, Alex. – avm_69 Apr 06 '16 at 14:41
  • Without a real image, all this discussion is a nonsense. –  Apr 07 '16 at 22:56
  • @YvesDaoust I don't have real images because all that I recieve in my project is the point cloud, nothing else. The most that I could apport is an schema of what happens in real life: http://i.imgur.com/h3rtTOD.png Here you can see that the hole has dirt in the bottom part (could be any side of the hole), so when you laser detect it, you don't obtain the circle, but a bunch of points with the upper part of the circle as empty. What I want is from that set of points where you can only see the upper part of the circle empty, reconstruct the original hole, as it was when clean. – avm_69 Apr 08 '16 at 09:20
  • @avm_69: why don't you show the point cloud then ? Need to see the true point density and smoothness. A schema is of no use. –  Apr 08 '16 at 09:31
  • @YvesDaoust Here you have two images from two different perspectives. If you need any other perspective or the point cloud file (in .pcd format) let me know. http://i.imgur.com/ZXgmuHF.png http://i.imgur.com/fdkQeyR.png – avm_69 Apr 08 '16 at 09:41
  • @avm_69: that sewer again ! You first need to convert the 3D problem to 2D by taking an appropriate viewpoint. –  Apr 08 '16 at 09:51
  • @YvesDaoust I do have done that. This is the new perspective from the 2D projected points of the wall where the hole is located: http://i.imgur.com/S5agJ9h.png It is a bit bad-rotated and you can also see the coordinate system As you can see in the image, the hole is in the left part, and it is quite clean (as the 2D point cloud has almost a perfect circle in that zone) – avm_69 Apr 08 '16 at 10:18
  • @avm_69 "almost a perfect circle": stop dreaming. –  Apr 08 '16 at 10:36
  • @YvesDaoust http://i.imgur.com/0M5XlgO.png – avm_69 Apr 08 '16 at 11:23
  • Hey, closers, what's not clear here? Nothing to solve with jQuery? OP, try here: http://dsp.stackexchange.com/ – Nakilon Apr 13 '16 at 18:45

2 Answers2

1

I would find the bounding box of hole and then inspect the sides. find the one that is not linear but curved instead and set that as circle border. Then fit circle to that side only. For more info see:

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
1

If you can scale the coordinates in order to draw the point into an image, here is a solution:

  1. Draw the points into an image
  2. Compute the distance map using all the points as a source point.
  3. Then, each pixel will contain the distance to the closets point. So the pixel with the highest value will be the center of the largest circle, and the pixel value will be the circle radius.
  4. Find the closest points to the circle center.
  5. Find the circle passing by all theses points (Hough?). The solution might not be unique.
FiReTiTi
  • 5,597
  • 12
  • 30
  • 58
  • That only works if you can see *at least* the full radius (i.e. bottom half, top half, or more) – Yuri Apr 07 '16 at 06:26
  • @FiReTiTi I don't understand the concept of drawing a point into an image. What do you mean by that. Furthermore, I don't know if I understand what you mean. For example, in this image, http://imgur.com/ldALw22 which point should be the center of the circle? I would say is some point in the sixth row. Does your idea apply into that example? Or another example even more extreme: http://i.imgur.com/nPrtFkw.png In this image only a small portion of the original circle is clean. Thank you, Alex. – avm_69 Apr 07 '16 at 09:13
  • 1
    The idea to draw the points into an image, let you use a distance map ( http://www.cs.cornell.edu/courses/cs664/2008sp/handouts/cs664-7-dtrans.pdf ), which is really easy to compute, and which gives you the center of the circle. But it gives you the center of the circle that does not contain any point. Now I realize in your example that you want a circle (because many exist) that contains the empty zone plus some points. – FiReTiTi Apr 07 '16 at 16:51
  • @FiReTiTi Yes, what I want to find is the original hole, that is, the circle that contains the empty zone plus some points (which are the ones that in real life is dirt in the hole, so the laser detects them) – avm_69 Apr 08 '16 at 09:06
  • 1
    @avm_69: then the problem is not the same. So I've edited my solution. – FiReTiTi Apr 08 '16 at 17:09