CODEWITHSUNDEEP
algorithmimage-processing
user107986
user107986

Reputation: 1541

Pairing points with nearest objects on the image

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.

Upvotes: 0

Views: 479

Answers (2)

dhanushka
dhanushka

Reputation: 10682

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.

Upvotes: 0

Penguino
Penguino

Reputation: 2186

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.

Upvotes: 1

Related Questions