Shortest geometric distance from surface in 3d dataset?

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).

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".

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

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.

• 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. – amypersand Jul 12 '12 at 17:47