4
$\begingroup$

I have a three-dimensional binary image of a collection of discrete, individual voxels ("seeds") contained in a connected 3-dimensional surface ("skin"). (Like a small fruit, with a surface delineated by a one-pixel boundary, that contains seeds.)

The binary matrix was derived from a three-dimensional intensity image of the same size (grayscale). (It's easy to label the surface voxels "2", the seed voxels "1", and the background "0" using MATLAB's label function).

In MATLAB, How do I compute the shortest geometric distance between each individual "seed" and the surface? In the (crude) 2-dimensional diagram in the link below, each desired distance is represented by the magnitudes of the red lines (in number of voxels).

enter image description here

$\endgroup$
3
$\begingroup$

Do you just need the distance, or do you need the closest point?

For the closest point, the FLANN library can help, and it has Matlab bindings.

If you only need the distance, you can also use a distance transform. Try googling for "distance transform 3d matlab" for implementations.

Which one is faster depends on the number of "seeds" and "skin voxels".

$\endgroup$
  • $\begingroup$ Thank you for your helpful answer! I will investigate both of your suggestions, and report back in the event of further questions. $\endgroup$ – amypersand Jul 12 '12 at 17:47
3
$\begingroup$

I'm going to answer assuming that you are searching for the conceptual answer. First find all the seed voxels. You can do this in MATLAB using find(labels==1). Also have a corresponding structure containing all the surface voxels. You can get this similarly using find(labels==2).

Then loop over each seed voxel which has an array index (i,j,k) and calculate its distance from every point (x,y,z) in the surface voxel structure. The distance can be a simple Euclidean distance given by $d=\sqrt{(x-i)^2 + (y-j)^2 + (z-k)^2}$. So for each seed point you will calculate its distance from EVERY surface point and record the minimum as the distance to the surface.

As you can imagine, if you have even a moderate amount of seed and surface points, this procedure is highly inefficient. As nikie pointed out, you can use FLANN to find the nearest neighbor in a fast and efficient manner. For further pointers, look into an octree data structure which can let you do nearest neighbor searches in a more efficient manner when using voxel like data.

$\endgroup$
  • $\begingroup$ Thank you for your answer! I appreciate your conceptual formulation of the problem and practical suggestion to use find with a distance metric. I'll definitely look into octree structures, and will update this post for further queries. $\endgroup$ – amypersand Jul 12 '12 at 17:47

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.