6

Suppose that I have a mask of an object and a point. I want to find the closest point of the object mask to the point.

For example, in my drawing, there is an object, the blue shape in the image (assume inside is also the part of the object mask). And the red point is the point from which I want to find the closest distance to the object mask.

image

So, I want to find the thick green line as it is the shortest distance to the mask not the other ones (pink, orange, etc). I can do this using one of the following ways:

  • An inefficient way is to find the distances of all the pixels to the point using something like this (brute-force).
  • Another way is to create many lines towards the mask with epsilon angle difference and find the closest point over that line, which is also not very nice.
  • I can create lines over the edge, and find the closest point of each of those lines on the object border. (This may not be as easy as I thought, first I need to find the outer border, etc.)

But none of these methods are is elegant. I am wondering what is a more elegant and the most efficient way to determine this?

smttsp
  • 4,011
  • 3
  • 33
  • 62

2 Answers2

2

You can use pointPolygonTest to find the closest distance between the blue mask region and any point

  1. Find the contours of the blue region and that will be our polygon

  2. If you set the distance flag to true, you can find the closest distance between the point and the polygon

    closestDist = cv2.pointPolygonTest(contours[0], redPoint, True)

  3. One more info what we can get from this function is that, if the distance is negative, then the point is out of the polygon, distance is 0 if the point is on the polygon edge, and positive if the point is inside the polygon

Gopiraj
  • 647
  • 7
  • 19
1

You could do a sort of binary search:

  • let's call P your point and consider circles centred on P
  • pick any point M on the mask, the circle through M will intersect the mask
  • now repeat until convergence, if circle intersects mask, reduce radius otherwise increase it (by binary search type amounts)

This will not work if your mask is not nicely connected, but then if that's not the case I doubt you can do better than brute force...

The total cost should be linear for the circle-mask intersection check times log for the binary search.

Julien
  • 13,986
  • 5
  • 29
  • 53
  • I like this idea a lot. However, how can I tell if a circle is intersecting with the mask? Is there an easy way for that? – smttsp Nov 05 '20 at 01:28
  • 1
    Just compute the equations of the 2 semi-circle y=f(x) and walk the pixels on it. – Julien Nov 05 '20 at 02:35