Fitting an almost rectangular block to get the width

Hi,

I have a number of scanning electron microscope (SEM) images of nanowires that we've grown, and I need to measure their thickness. The nanowires are visible as a bright line on a dark background, see below, so we had the idea to scan the brightness of the image (across the wire) and plot it as a graph, which would result in a kind of bell-shape or rectangular block, low brightness at the sides and high brightness in the middle. The width of this block (in pixels) would then be a good indication of the width of the nanowire. I can convert from pixels to nanometers or something easily by using the (known) width of the total image.

Here's an example of a SEM image (scaled down):
http://i54.tinypic.com/219c8y1.png

Using C# I get the brightness of each pixel in a 'cross section' of the image (so at a certain height or y value), and plotting this produces this:
http://i51.tinypic.com/156wtx2.png

So, the question is simple... How do I fit a curve through this that I can deduce the width of the wire from? The most important thing is that this width is consistent across different images, so I really like to use a standard non-linear fit, instead of actually fitting a rectangular block. For example I could loop through the pixels (x values) until I find a brightness that is sufficiently higher than the previous brightness and call that the start of the wire, but that is quite arbitrary and might work for some images, but not very well for others. When I got a good fit I will apply the fit across the whole image (imagine scanning the image top to bottom and calculating the width for every height, then averaging them) so this consitency is key.

Anyway, the most obvious choice would be a Gaussian curve fit. This works quite well, and it fits all curves in the same way, but the problem is that I am finding it hard to extract the width from the fit. The FWHM would be the most obvious choice, but it seems it is not very accurate for the actual width. In the image I showed, the FWHM comes to about 101 pixels, whereas the line seems to be about 120-130 pixels when measured using various other manual techniques. This difference (20-30 pixels) is relatively large and will make the widths come out much smaller than the actually are, which of course is not good.

I tried looking for similar curves, but none seem to fit very well. They all have the same problem as the Gaussian fit; they assume the data is bell-shaped, whereas the actual data is more like a rectangle then a real bell shape...

Another thought I had is to manipulate the image to make the contrast between wire and background a lot more pronounced. Probably I could even get the contrast to be 100% (pure black for the background and pure white for the wire) which would make the brightness plots actual rectangles and make it easy to find the width. However, after experiencing some in Photoshop (playing with the Levels of the image) I've found that the width of the resulting wire can change quite a lot depending on how you change the contrast exactly. I managed to take various routes to form a completely black/white image but in all of the routes the widths came out different. So again this is very arbitrary and I'd like to use a more mathematically correct solution...


Any ideas how I can fit this rectangle the best and retrieve the width of the wire from it?
Thanks!

Note: I am not necessarily looking for a way to fit the data in .NET (C#), I can use various maths tools (Origin, Matlab, etc) to do it, but if you know a solution in C# that would be even better :)

As a human, I have trouble figuring out the left and right endpoints on your sample graph, so I imagine getting a machine to give a consistent answer would quite difficult. The right endpoint is particularly fuzzy. Should it be at about 400 pixels, or 425?

My best internal algorithm essentially tries to curve fit the right and left endpoints of the wire using the whole image instead of just one scanned line of it. Perhaps using all the information from the image instead of just one line is essential to getting a good width. Have you tried any edge detection techniques? I tried the "fuzzy select tool" in GIMP (GNU Image Manipulation Program; free Photoshop, essentially) and after modifying the "threshold" slightly, I got very good results on the outline of the shape, from which I could pretty easily calculate the widths.

Attached is an example of the fuzzy select tool. Sorry for the large size, but I think it's important to be able to see the pixels very clearly to determine the goodness of fit.

Quote:

---

Originally Posted by jemidiah

As a human, I have trouble figuring out the left and right endpoints on your sample graph, so I imagine getting a machine to give a consistent answer would quite difficult. The right endpoint is particularly fuzzy. Should it be at about 400 pixels, or 425?

My best internal algorithm essentially tries to curve fit the right and left endpoints of the wire using the whole image instead of just one scanned line of it. Perhaps using all the information from the image instead of just one line is essential to getting a good width. Have you tried any edge detection techniques? I tried the "fuzzy select tool" in GIMP (GNU Image Manipulation Program; free Photoshop, essentially) and after modifying the "threshold" slightly, I got very good results on the outline of the shape, from which I could pretty easily calculate the widths.

Attached is an example of the fuzzy select tool. Sorry for the large size, but I think it's important to be able to see the pixels very clearly to determine the goodness of fit.

---

I would say it should be around 425 pixels, but yes, it is rather arbitrary. Above all, since the image itself is taken using electrons rather than light you can have all kinds of effects that distort your image so we can't even be sure about what we see... (For example, a pcarbon nanotube is only 1-2 nm wide yet shows up as 50 nm) Still, the algorithm I use should give consistent results for different images, regardless of whether that image depicts reality.

As for your idea, the select tool (I think its the magic wand tool on PhotoShop) might work. However that requires quite some manual work. I need to measure a lot of these images so it would be awesome if it were automated as much as possible.

Do you have any further ideas, maybe some that I can implement in matlab, origin or even C# ?

In the mean time I tried fitting a gaussian again but taking the width at quarter maximum instead of FWHM, that seems to give better results. I might go with that method, but I'd like to have a function to fit that more closely resembles the shape of my graphs...

Well, I'm sure Photoshop or a similar program can be scripted to mostly/entirely automate a "magic wand" selection process and the ensuing width computations. Also, there are extensive open source computer vision libraries that I'm sure implement the same thing, somewhere. Perhaps a relatively simple algorithm would suffice, too--something like pick a pixel that's definitely on the wire, breadth-first search out from it, and stop when the brightness gets too different from your source. This method might be worth trying out in Matlab or C# since it should only take an hour or two of fiddling.


I had a few other less promising ideas, but I'll list them since you asked:

1. Using your brightness graph, fix a brightness that's just a bit above the background "noise" and find the leftmost and rightmost points that equal that brightness (well, slightly exceed it). With a fixed level of 20, this would give a band between about 275 and 425 pixels in your example image. Tune the fixed value as needed; hopefully you could use a single one for all images.

2. Draw a line down the center of the original image. Expand the line to a rectangle by pushing the left and right borders. Do so until you add a line of pixels with average brightness below some threshold.

3. Convolve a unit step function of width d with your brightness graph. Figure out the largest value of the convolution. Repeat for many values of d in reasonable ranges. Normalize the results, and pick the width that gave rise to the largest value overall. This would give a pretty good rectangular block fit, but I doubt it would work well in practice. Your example is really more trapezoidal than rectangular, and this method would greatly favor a conservative estimate. [The language of convolutions is not essential, but it's convenient, so I've used it.]

4. Extend (3) to a trapezoidal fit. With an extra set of parameters, the rather inefficient method I've described might take too long, especially if you have eg. thousands of images to process.

I like your idea nr 1. Finding the brightness just above noise level might be a little tricky to do automatically, but if all else fails I could do it manually by just clicking in a graph. I am already plotting the graph using C# so that shouldn't be too difficult.

Perhaps I could use the average of all the brightness values (in one height or y-value) as the brightness just above noise level. Since there is a large peak in the middle the average will almost certainly be above the noise, and since there is more background than peak it should be between the peak and the noise somewhere. I'll have to run a few tests to see how the average comes out but I think it might work... Then I could just get the first and last point that are higher than the average and I'm done.

I like the idea, I'll try soon if it works out in practice.

Oh, also, I don't have nearly as much as thousands of images, but I do have too many to all do by hand.

Instead of measuring the brightness of a pixel, measure the contrast between two pixels. Your graph will then have two peaks, and the distance between those peaks will be the width of the wire.

More specifically, instead of graphing Brightness(x), graph Abs(Brightness(x - c) - Brightness(x + c)). If nothing else, it might be easier to analyze.

Good idea. Unfortunately it doesn't work with the images I've tried it with, they are probably just too noisy, resulting in a very noisy graph without two easily discernible peaks. If I try it with an image I cleaned up (increased the contrast a lot so that it's almost completely white on almost completely black), then I get to clearly visible peaks.

If I can do this 'cleaning' procedure via C# then I'd have a good method to use, I'll research that...

I agree: the graph for a single y-value is indeed unclear. Try taking the average on ten randomly selected y-values. This seems to work quite well on your scaled-down image. Could you provide a full-size image for testing?