0

I have a bunch of points with their coordinates. I'd like to analyze a binary image containing only black objects - these objects are approximately rectangles - and for each points from my set, assign the nearest object. All I know is for each point in my set there is exactly one object somewhere close to it, I just don't know where.

My idea is to find the objects on the image and then use one of the algorithms for closest pair of points problem. Or would it be better to start scanning the image somehow starting from a point in my set in search for that object? The goal is to find the location and size of these black objects as well. Have been searching for an algorithm obviously better than the one I've mentioned, but without much luck.

user107986
  • 1,461
  • 1
  • 17
  • 24
  • How about showing us an image? And telling us what tools you are using and on which OS? – Mark Setchell Sep 24 '14 at 18:25
  • C++, openCV, Windows. Here's an example - I want to find the location and approximate size of black blobs and to assign the nearest black blob to every red point (I know the coordinates of red points). http://i57.tinypic.com/2rysxs1.png – user107986 Sep 24 '14 at 18:39
  • I would suggest a BFS from each red point. This way, you don't necessarily need to process the entire image. – Nico Schertler Sep 24 '14 at 20:39
  • Have you had any thoughts about how you define `nearest`? Is a blob near a dot if the blob's nearest point is nearest to the dot? Or is it the distance from the centroid of the blob to the dot? Or are we trying to pair blobs and dots to minimise the total combined distance between all blob centroids and their associated dots? – Mark Setchell Sep 24 '14 at 21:19
  • Nearest = blob's nearest point is nearest to the dot. I just take dots and want to find the nearest blob for each of them. Keep in mind that I don't know the location or size of the blobs. – user107986 Sep 24 '14 at 21:30
  • I'm thinking of starting at each red dot and doing an ever-increasing spiral search away from it till I hit a black pixel... see here... http://stackoverflow.com/questions/398299/looping-in-a-spiral – Mark Setchell Sep 24 '14 at 22:01
  • Are we allowed to assign the same blob to two or more dots? – j_random_hacker Sep 25 '14 at 00:25
  • No. Every blob has one red dot assigned to it and vice versa. – user107986 Sep 25 '14 at 06:50

2 Answers2

1

I assume each dot can be considered separately in that either no blob will be nearest to two dots or if that is the case it is acceptable for two or more dots to 'recognize' the same blob.

Simplest algorithm is to do a breadth-first search over an increasing radius disc from the dot until you detect black. This finds the nearest blob. You could identify the blob either by that first contact point, or you could then do a flood-fill on the blob to select all the points in the blob if you need them.

If processing time is of concern, and you have some expectation on minimum blob dimensions, then you could speed up the process by searching for black in circles of radius R,2R,3R (where R is a known minimum blob-dimension). Once you detect black at some nR, you then need to backtrack your search to the region between radius (n-1)R and nR to ensure you have found the closest blob. Obviously this won't work if you can't guarantee blobs have some minimal dimension as then you could jump over a blob and detect the next nearest. The savings may not be significant unless the typical dot-blob distance is large.

Penguino
  • 2,136
  • 1
  • 14
  • 21
  • Every dot always has one blob I'm supposed to assign to that dot. No more, no less. I'm supposed to find out the size and location of the blobs, so yeah, once I find the first pixel I need to use some algorithm to find blob's size and location (of center point) and size. I don't need all pixels of the blob, I can get size and location from contours only. I guess it's faster than using flood-fill here. – user107986 Sep 25 '14 at 07:50
0

In OpenCV, there's a function called pointPolygonTest that you can use to get the signed distance from a point to the nearest contour edge. So you just have to binarize the image to extract the black regions and test each point against contours using pointPolygonTest distance.

dhanushka
  • 10,492
  • 2
  • 37
  • 47