Shortest distance between two digital blobs

Question

We have two digital blobs of arbitrary shape, i.e. two connected components on a digital image. They are described by a run-length-coded representation, i.e. a list of $(x, y, l)$ triples of integers.

I want to find the shortest Euclidean distance between them (from pixel center to pixel center) in an efficient way.

Emphasis is on speed, and the obvious brute-force approach (trying every pair of run endpoints) isn't acceptable. Good asymptotic behavior is not necessarily a concern, the solution must be truly fast.

The blobs are usually of moderate size (say $50$ runs) but can on occasion be larger (say $1000$).

There are two degrees of freedom:

• short preprocessing of the blobs is allowed, as several distances to a given blob will be computed;
• an approximate solution is allowed (say to a relative error of $20\%$).

How would you tackle this ?

---

Update:

Using the convex hulls of the blobs may seem to be an option, because there are less vertices to be considered, and there is an efficient way (linear time) to compute the distance between two disjoint convex polygons. Anyway the algorithm isn't so simple and this won't work for disjoint blobs with non-disjoint convexhulls.

---

Next update:

Based on the ideas of @bubba and Vobarkun, I change the rules a little. It came back to me that the Voronoi diagram solves the "all nearest neighbors" problem, which is actually what I am after.

The Voronoi diagram of the set of blobs is directly related to the distance map to all blobs, which can be computed in linear time wrt the image size (A. Meijster, J. B. T. M. Roerdink and W. H. Hesselink, A general algorithm for computing distance transforms in linear time.)

As the blobs do result from binarization of a source image, preprocessing the image in linear time is allowed as well.

Now when we have a distance map, the shortest distances will be found on the common boundaries of two Voronoi cells that are in contact. My problem is directly related to the medial axis transform.

---

Next update:

It is indeed possible to modify the Euclidean distance map algorithm so that it computes not only the distance to the nearest blob, but also the identity of this blob and the closest pixel of the blob.

Now among the pixels on the border common to the two desired blobs, we may select the border pixels that lead to the closest pair from the two blobs. I believe that in most cases this indeed gives the shortest distance between the blobs, but this needs to be checked.

Answer 1

An exact solution might look as follows:

Lets call the blobs $A$ and $B$.

• First build the Voronoi diagram of blob $A$. With Fortune's algorithm this can be done in $O(n \log n)$, but more importantly, this can be done in preprocessing.
• Then, for each point $b$ in blob $B$ find the cell of the Voronoi diagram that contains $b$ to find the point of $A$ that is closest to $b$.
• Find the minimal distance between the resulting pairs of points.

This works for abitrary sets of points. In your specific case all points lie on a grid, so it can probably be adapted to be even more efficient.

Answer 2

Not an answer (yet), but the beginnings of an idea that's too long for a comment.

Keep expanding each blob by adding pixels around the periphery. At some point, the expanded blobs will touch. Seems like this touching ought to tell you something about the separation distance.

I guess you only need to expand one blob, not both of them. Expand the smaller one, I suppose.

The growing doesn't need to start from zero. You could start with a "growth radius" that's equal to the distance between the bounding boxes of the blobs.

From a mathematical point of view, an expanded blob is the Minkowski sum of the original blob and some other set (like a square or a circle). I vaguely remember seeing algorithms that compute distances by using Minkowski sums and differences. You could try reading a little about Minkowski sums.

If we're allowed to use graphics hardware, this should help with performance. Certainly overlap/touch testing is easy in a graphics subsystem. Also, there's probably some slick way to do the expanding, too (by drawing a circular shape centered at each pixel center).

Another idea ... circumscribe the blobs with straight lines to form polygons. You can start by using each pixel edge as a line, and then combine them into longer lines when possible. The problem of finding distances between polygons has been very widely studied, and there is a vast body of literature that you can leverage. You can start with the references given here. The answer computed from polygons won't be exactly correct, of course, but you said that wasn't very important.