16
$\begingroup$

I have hundreds of images similar to this image:

Valid XHTML

I'm looking to count the number of ellipses as well as their major and minor diameters. The ellipses are touching, hence,

img = Import["https://i.sstatic.net/lkToU.png"] EdgeDetect[img]

doesn't return fillable ellipses so using something like 

WatershedComponents[%]

returns useless information.

I'm very new to this type of image analysis using Mathematica so any help would be greatly appreciated.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ A Flying saucers invasion detector! $\endgroup$ Commented Oct 5, 2013 at 0:51
  • 1
    $\begingroup$ Hmm... At first glance I thought all the ellipses had the same "shape", that is, orientation and aspect ratio, so if you affine-tranformed the image in the right way they would all turn into circles and detecting them would become much easier. But it turns out that this is not the case: i.sstatic.net/Zl5M2.png $\endgroup$ Commented Oct 5, 2013 at 1:00
  • 1
    $\begingroup$ Check this out $\endgroup$ Commented Oct 5, 2013 at 2:15
  • $\begingroup$ @belisarius 3.bp.blogspot.com/_QEPCmku0Hrw/TUiC-piwWoI/AAAAAAAAAjU/… $\endgroup$ Commented Jan 9, 2014 at 23:37

1 Answer 1

Reset to default
24
$\begingroup$

One standard way to detect circular shapes is to binarize the image and apply a distance transform: The maxima locations of the distance transform are the centers of the circles.

To make this work on your ellipses, I first have to stretch them to be (roughly) circular, as @Rahul Narain suggested in a comment:

img = ColorConvert[Import["http://i.imgur.com/oNrJq0j.png"], "Grayscale"] {w, h} = ImageDimensions[img]; ir = ImageResize[img, {w/5, h*5}] stretched = ImageRotate[ImageResize[img, {w/5, h*5}], 90 \[Degree]]

enter image description here

(The rotation is just for display. If I don't rotate the image by 90°, this post will be very long. It has no influence on the ellipse detection.)

Calculating the distance transform and finding the maxima is easy:

distTransform = DistanceTransform[Binarize[stretched]]; maxima = MaxDetect[distTransform, 2];

Here's a display of the result so far:

Grid[ Transpose[{ {"Stretched", "Binarized", "Distance Transform", "Distance Transform Maxima"}, Image[#, ImageSize -> All] & /@ { stretched, Binarize[stretched], ImageAdjust[distTransform], HighlightImage[stretched, maxima]} }]]

enter image description here

Now I can use ComponentMeasuements to find connected maxima locations, their orientation, shape and the max. value in the distance transform image:

components = ComponentMeasurements[{MorphologicalComponents[maxima], distTransform}, {"Centroid", "SemiAxes", "Orientation", "Max"}]; Show[stretched, Graphics[ { Red, components[[All, 2]] /. { {centroid_, semiAxes_, orientation_, maxR_} :> Rotate[Circle[ centroid, {maxR*Sqrt[semiAxes[[1]]/semiAxes[[2]]], maxR}], orientation, centroid] } }]]

enter image description here

As you can see:

  • the centroids are quite good, except for the ellipses near the border, because the border changes the distance transform
  • the minor radius of the ellipses is ok (it's just the distance from the center to the nearest background point)
  • the estimated orientation is ok,
  • but the semi-axis length ratio of the maximum is only a rough estimate.
  • You could probably apply smoothing before binarizing, use MorphologicalBinarize and hand-tune the filter/binarization parameters to improve the result

ADD:

I can improve the shape estimate a bit further using WatershedComponents, with the distance transform maxima as seed points:

watershedComponents = WatershedComponents[ColorNegate[distTransform], maxima] * ImageData[Binarize[stretched]]; Colorize[watershedComponents]

enter image description here

Estimated Ellipses:

components = ComponentMeasurements[ watershedComponents, {"Centroid", "SemiAxes", "Orientation"}]; Show[stretched, Graphics[ { Red, components /. { (n_ -> {centroid_, semiAxes_, orientation_}) :> { Rotate[Circle[centroid, semiAxes], orientation, centroid], Text[n, centroid] } } }]]

enter image description here

Improve this answer
$\endgroup$
5
  • 6
    $\begingroup$ Anytime I read you answers, I learn something new. Nice answer ... $\endgroup$ Commented Oct 5, 2013 at 9:09
  • 1
    $\begingroup$ Those are remarkably good results! Very nice. It is not clear whether the same stretching to {w/5, h*5} will work for all of the OP's images, but we can wait for him to clarify that. Another thought: "the Hessian of the... distance transform" is not likely to be useful, as the distance function is not even first-differentiable at its maxima. $\endgroup$ Commented Oct 5, 2013 at 9:41
  • $\begingroup$ @RahulNarain: Yes, you're right of course. I was thinking of the absolute value, which is not differentiable at the origin, but it's square is. But, as you said, that's not true for the distance transform. I'll delete that paragraph from the answer. $\endgroup$ Commented Oct 5, 2013 at 9:50
  • $\begingroup$ Hi, thanks so much for the very detailed answer. Yes, luckily all of my images have ellipses at relatively the same orientation. I'm going to have to spend a bit of time going through this answer to decipher each segment but again, thanks so much for your help! $\endgroup$ Commented Oct 7, 2013 at 17:11
  • $\begingroup$ Nice post! It is "featured" in this video: "Markdown to Mathematica converter demo". $\endgroup$ Commented Sep 28, 2022 at 14:21

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.