Finding radius r of the overlappable sphere(s) in 3D image

Question

My current problem:

• I have an input 3D binary image (a 3D matrix that has only 0 and 1) that consists of random numbers of sphere with radius r.
• We do not know how many spheres are there in the image.
• All spheres have the same radius r, but we do not know radius r.
• Spheres are all over the place in the image and can overlap each other.
• example image is given below.

My requirement:

• what is the radius r?

Currently, I simply just flatten the image to get rid of the z axis and perform edge detection and I am trying Hough Transform using: http://rsbweb.nih.gov/ij/plugins/hough-circles.html

However, with Hough Transform, I see that the variables minimum radius, maximum radius, and number of circles have to be specified. I have tried a few attempts below:

Given the correct parameters, Hough Transform can detect the circles just fine. But in the real application, I do not know how many spheres are there, and making the program attempting to guess minimum and maximum radius seems not feasible. Are there other ways to accomplish this?

Cross-link: https://math.stackexchange.com/questions/118815/finding-radius-r-of-the-overlappable-spheres-in-3d-image

Answer 1

A simpler solution and much more computationally efficient when compared to Hough Transform is to use the distance transform:

• Find the surface of your spheres (i.e. the pixels that have value 1 and have at least one neighboring 0 pixel);
• Compute the distance transform with respect to the spheres surface, but constrain the computation only to pixels that are internal to the spheres. The output will be a distance map;
• The radius will be exactly the maximum value in your distance map.

Another advantage of this solution when compared to Hough transform is that it provides a much more precise value for the radius.

Answer 2

The Hough Transform does not, in its general form, require guesses at the radius of the circles you are looking for nor how many there are. Perhaps you have been misled by your source. The transform can be computationally expensive in its most general form; any prior information you have can make the execution of the algorithm more speedy and more accurate.

I would expect the Hough Transform, given your input images, to find the radius of the spheres with reasonable accuracy; there are a lot of points in the images representing points on the circumference of circles with the same radius.

Given that radius, you seem to have the rest of the problem cracked so I won't write any more.

I see that Wikipedia's explanation of the Hough Transform also indicates that it can be used to find 3D objects in 3D images, provided that those objects can be parameterised -- which a sphere certainly could be.