Diameter of a label image

Given a label image as a numpy matrix, I want to determine the diameter of all the regions. This boils down to finding the diameter of a binary image. Is there a built-in function for it in scikit-image, scipy or related Python packages? By diameter, I mean the diameter of a set, i.e. the largest distance of any of its two points (and not the equivalent diameter in regionprops).
If this is complicated, I could work with the underlying matrix of the binary image. I know that the diameter of a set is the same as the diameter of its convex hull. Are there existing implementations in Python to determine the largest distance (Euclidean distance is sufficient) in a convex hull?

Hi,
I am not sure to understand what you need, maybe attaching an example picture would help.
If you need the largest distance for every segment of a binary image, you have to first run a connected component analysis and then for each segment get the so-called ferret diameter.
I guess there are functions to get the ferret diameter in scikit image or OpenCV.

Assume that the image below, given by a set of pixels, is a region in a label image, all of its pixels having the same label. I want to find the distance of the two furthest pixels.
diameter

Formally, you are looking for the largest distance of the vertices of the convex hull of a point set (the pixels in your image region).

Practically (simple solution)

  • get the convex hull of the mask of your image (ImageJ API: Roi.getConvexHull() )
  • Iterate over all points of the returned PolygonRoi pairwise
    • calculate the point distance
    • store the maximum point distance

The implementation would be easy in Java. (Maybe it is already existing.)
I’m not sure if this can be done as IJ macro.

If your images / convex hulls are very complex and/or huge you may have to look for a more effective approach.

I think you are searching for Feret’s diameter.

In Fiji/imageJ the Particle Analyser (https://imagej.nih.gov/ij/docs/menus/analyze.html#set)
comes with this measure.

I really think there will be an implementation in some python package.

hth,
Emanuele Martini

2 Likes

One thing to mention:
The calculation of the Feret diameter is implemented in ImageJ in the classes Roi.java and ShapeRoi.java in two different ways.
see
http://imagej.1557.x6.nabble.com/Measurement-of-Feret-diameter-td5003818.html

One more thing:
Both implementations in IJ are using object rotations to calculate the maximum feret diameter. The result is usually identical or very close to the ‘true’ maximum diameter. But depending on the angle resolution and the object shape it don’t has to be.

So, using the Feret measurement is indeed the most easy solution for the original question.
Thanks to @emartini

Reminder: Maybe it should be considered one day to unify the different implementations of Feret measurement in ImageJ and also to consider a more sophisticated algorithm borrowed from Computational Geometry.
" The diameter of a convex figure is the greatest distance between parallel lines of support. [Theorem 4,18, Preparata and Shamos, Computational Geometry , 1985]"

See here for more information:

Peter

2 Likes

Thanks. The Feret diameter will be very useful for me because I also need to obtain the largest distance along a given coordinate direction.
However, I don’t yet know the direction along which to measure the diameter.

Indeed, your algorithm was in my mind. This “naive” approach has quadratic complexity. The rotating calipers algorithm has linear complexity.
Thank you for the useful links. I work in Python but based on your pointers, I will be able to implement it.

Hi everyone,

We don’t currently have Feret diameter in scikit-image regionprops, but it’s coming, see this pull request for an implementation:

1 Like

Can you give me a working prototype implementation? I checked the pull request, but

from skimage.measure._marching_cubes_lewiner import marching_cubes

results an import error:

ImportError: cannot import name 'marching_cubes' from 'skimage.measure._marching_cubes_lewiner' 

What version of skimage are you running? You can check with:

import skimage
print(skimage.__version__)

I have version 0.16.2

That makes sense; the PR is on the development version. In 0.16.2, the import is:

from skimage.measure._marching_cubes_lewiner import marching_cubes_lewiner as marching_cubes

Thanks, now it works. Does it determine the maximum Feret diameter? According to my measurements with Fiji, it does:
Feret
Is there a way to compute the Feret diameter in a given direction?