Maximum ball transform

Consider a finite uniform grid $G$ in three dimensions with a function $f$ mapping integer grid positions $p$ to a boolean value $f(p)$ (i.e., a black/white volume image.)

A ball in $f$ is a set of grid points with center $c$ and radius $r$ where $f(p)$ is true for all $p \in G$ with euclidean distance $|c-p| \leq r$.

The maximum ball transform $MB$ finds for each grid point $p$ the radius $r$ of the largest ball in $f$ containing that point. (Note: This is probably not the actual, commonly used name for this. However I don't know what else to call it.)

Are there good algorithms to compute this transform?

I assume this is related to the (euclidean) distance transform. (Find for each grid point $p$ the radius of the largest disk in $f$ with center $p$.)

$DT(p) = min_{x \in f} |p-x|$

$MB(p) = max_{|x-p| < DT(x)} DT(x)$

In the literature I can find algorithms that compute the euclidean $DT$ (and its reverse) in linear time. There are also algorithms to compute the medial axis transform $MAT$ (the set of all center points of the maximum balls).

Is there a faster algorithm than computing the $MAT$, iterating over all found maximum balls and naively tracking the largest one for each grid point?

Edit: It seems this is sometimes known as Thickness Distribution or Euclidean Opening Function.

A recent paper computes an approximation: Fast and Accurate Approximation of the Euclidean Opening Function in Arbitrary Dimension (D. Coeurjolly, 2010), (presentation)

• Although I don't understand the last sentence of the post, and so may misunderstand the question, I think the likely answer is 'No.' The MAT contains all the information needed to compute $r$ for each point $p$, because it partitions the interior of the shape into regions whose maximal balls touch the same "section" of the boundary. Moreover, algorithms to compute MAT often implicitly sweep over all intermediate points. – Joseph O'Rourke Nov 6 '10 at 19:08
• Let me restate the last sentence: How can I compute MB quickly? Is computing MAT a good first step? How to continue? Scan convert all maximal balls (with max-blending)? That seems very inefficient. – Rumen Nov 6 '10 at 19:44
• Just wondering: do you need Euclidean balls, or might $\ell_1$ or $\ell_\infty$ balls suffice ? – Suresh Venkat Nov 6 '10 at 20:56
• I'm mainly looking for the Euclidean case. – Rumen Nov 6 '10 at 22:30
• Question: For $MB$, are you only interested in an algorithm to compute it for ALL points? If so, there is an implicit reduction to $MAT$, since knowing the radius to a maximum ball's center for each point allows you to instantly compute $MAT$ (given a 3-dimensional space and integer positions, there is at most constant number of points at a given radius from any point that you need to check) -- implying computing $MAT$ first won't cost you anything extra. – Daniel Apon Nov 6 '10 at 22:31

This answer has a problem; see comments below.

Following up on my comments, here is the rest of the full answer:

First, take a look at the 2008 paper Euclidean Skeletons of Digital Image and Volume Data in Linear Time by the Integer Medial Axis Transform by Hesselink and Roerdink.

From my reading of your question, Section 2 of the paper is answering your question fairly explicitly. In particular, the process they use is essentially a scan across grid points.

Additionally, I wouldn't worry about the runtime being excessive. The algorithms involved are all linear time, and in fact experimental results from the paper show that the $IMA$ transform can be computed in a matter of seconds on a modern computer, even on data sets in the tens of millions. An especially nice piece of this: It appears $MB$ is computed along the way (again, Section 2), so if you simply stop the algorithm at that point, you should have an even faster runtime than "a matter of seconds" in practice.

• Linear time would be excellent. You say it computes $MB$. Do you mean the Feature Transform? If I read them correctly, in the above terms that would be $FT(p) = \{y \in G | f(y), |p-y| = DT(p)\}$ That wouldn't compute $MB$ along the way, though. Maybe I'm missing something. – Rumen Nov 7 '10 at 18:06
• Actually, you're correct! The algorithm I had in mind, too, won't work (it took me a bit to come up with a nasty enough case); I think I'm stuck back with something equivalent to the naive technique you described. I'd recommend un-accepting my answer so that your question gets more traffic -- sorry. :) – Daniel Apon Nov 7 '10 at 20:25