9
$\begingroup$

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:

known radius

unknown radius

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

$\endgroup$

migrated from stackoverflow.com Mar 13 '12 at 15:05

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ Edit your question and add a description of the format of the input image. $\endgroup$ – rob mayoff Mar 11 '12 at 7:52
  • $\begingroup$ The format of the input image is a binary 3D image. $\endgroup$ – Karl Mar 11 '12 at 7:53
  • $\begingroup$ Your problem seems underconstrained, unless you intended to say that the spheres cannot overlap each other. $\endgroup$ – ObscureRobot Mar 11 '12 at 8:13
  • $\begingroup$ No, the spheres can overlap each other. In the easiest case, no spheres are overlapped at all, but this is not always true. $\endgroup$ – Karl Mar 11 '12 at 8:20
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But if two spheres are overlapping, wouldn't the maximum be the longer distance from the far side of one sphere to the far side of the other sphere? $\endgroup$ – endolith Mar 30 '12 at 13:56
  • 1
    $\begingroup$ @endolith No, because the distance transform value of a given pixel (voxel), in this case, corresponds to the distance to the nearest sphere surface. $\endgroup$ – Alceu Costa Apr 4 '12 at 2:31
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.