Calculating length of objects in binary image - algorithm

Question

I need to calculate length of the object in a binary image (maximum distance between the pixels inside the object). As it is a binary image, so we might consider it a 2D array with values 0 (white) and 1 (black). The thing I need is a clever (and preferably simple) algorithm to perform this operation. Keep in mind there are many objects in the image.

The image to clarify:

Sample input image:

Answer 1

I think the problem is simple if the boundary of an object is convex and no three vertices are on a line (i.e. no vertex can be removed without changing the polygon): Then you can just pick two points at random and use a simple gradient-descent type search to find the longest line:

Start with random vertices A, B
See if the line A' - B is longer than A - B where A' is the point left of A; if so, replace A with A'
See if the line A' - B is longer than A - B where A' is the point right of A; if so, replace A with A'
Do the same for B
repeat until convergence

So I'd suggest finding the convex hull for each seed blob, removing all "superfluos" vertices (to ensure convergence) and running the algorithm above.

Constructing a convex hull is an O(n log n) operation IIRC, where n is the number of boundary pixels. Should be pretty efficient for small objects like these. EDIT: I just remembered that the O(n log n) for the convex hull algorithm was needed to sort the points. If the boundary points are the result of a connected component analysis, they are already sorted. So the whole algorithm should run in O(n) time, where n is the number of boundary points. (It's a lot of work, though, because you might have to write your own convex-hull algorithm or modify one to skip the sort.)

Add: Response to comment

If you don't need 100% accuracy, you could simply fit an ellipse to each blob and calculate the length of the major axis: This can be computed from central moments (IIRC it's simply the square root if the largest eigenvalue of the covariance matrix), so it's an O(n) operation and can efficiently be calculated in a single sweep over the image. It has the additional advantage that it takes all pixels of a blob into account, not just two extremal points, i.e. it is far less affected by noise.

Answer 2

Find the major-axis length of the ellipse that has the same normalized second central moments as the region. In MATLAB you can use regionprops.

Answer 3

A very crude, brute-force approach would be to first identify all the edge pixels (any black pixel in the object adjacent to a non-black pixel) and calculate the distances between all possible pairs of edge pixels. The longest of these distances will give you the length of the object.

If the objects are always shaped like the ones in your sample, you could speed this up by only evaluating the pixels with the highest and lowest x and y values within the object.

Answer 4

I would suggest trying an "reverse" distance transform. In the magical world of mathematical morphology (sorry couldn't resist the alliteration) the distance transform gives you the closest distance of each pixel to its nearest boundary pixel. In your case, you are interested in the farthest distance to a boundary pixel, hence I have cleverly applied a "reverse" prefix.

You can find information on the distance transform here and here. I believe that matlab implements the distance transform as per here. That would lead me to believe that you can find an open source implementation of the distance transform in octave. Furthermore, it would not surprise me in the least if opencv implemented it.

I haven't given it much thought but its intuitive to me that you should be able to reverse the distance transform and calculate it in roughly the same amount of time as the original distance transform.