Fourier Analysis of Sand Grains

May, 1997

In 1983 or so, while working on my Masters degree in geophysics at the University of Southern California, Dr Robert Osborne, a sedimentology / petrology professor, asked me if I could set up a computer system for him. I had developed a bit of a reputation as a computer wizard.

Doctor Osborne was interested in doing Fourier Analysis of the shape of sand grains. This consists of determining the shape of a sand grain, then performing a Fourier Transform to convert from the spacial domain to the frequency domain. Then you could do multi-variant analysis to separate groups of sand grains into different populations. A useful application of this is in beach conservation. You could determine how much of the sand at the beach is coming from the nearby cliffs, from a nearby river, or from off-shore sources.

Previously, the way to measure the shape of the sand grain would be to place the grain under a microscope and project the image onto a screen. On the screen would be a piece of paper with a bunch of evenly spaced rays extending radially out from a central point. The center of the grain would be aligned with the center point of the rays, and then you'd measure the radius R at each angle alpha around the grain. This was very time consuming, and determining the center of the grain was not always accurate.

A group at the other USC, University of South Carolina, had created a computer system that would determine theses vectors automatically, and Doctor Osborne wanted me to create a similar system. Their system consisted of a video camera looking into a microscope connected to a frame grabber. (BTW the microscope is backlighted, so the sand grain is in shadow.) They would determine the center of the grain, then trace vectors out at evenly spaced angles until they found the boundary point of the grain. They would collect 48 or so radius vectors in just a few seconds.

So I created a similar system. It consisted of an S-100 bus, a Z-80 CPU, a 5.25" floppy drive, and a frame grabber. (This was even before the 8086 and MS-DOS.) All programming was in assembly language. Once the grain shape data was collected, it was transferred via a serial line (no small feat in itself, this was even before Kermit was widely available) to the department's VAX 750.

I quickly realized that I could get much higher resolution than the 48 vectors that South Carolina was using. They would trace out a vector from the center or centroid at evenly spaced angles until they found a boundary point. But I figured out how to determine a Radius vector for every possible boundary point.

The frame grabber would return a set of pixels, a grid of about 200 by 200. The value of each pixel would be black or white, one or zero. To calculate the centroid of a shape, you divide the shape into rectangles, determine the centroid of each rectanges, and calculate the average. Well, the frame grabber already divided the shape into squares of 1 pixel by 1 pixel. I just needed to sum up the X and Y locations of each pixel that was black, then divide by the number of pixels, to determine the location of the centroid. Then, a boundary point is defined to be a pixel that is black and neighboring pixel, above, below, left, or right, is not black. Then I could calculate the Radius and Angle between the centroid and that boundary point. I'd just start at the top of the frame, and scan all the way down, checking each pixel, I=1, 200 and J=1, 200.

Then I'd sort the 250 or so vectors by angle, and interpolate into some number of evenly spaced vectors. Doctor Osborne chose 128 vectors. Then we'd use a Fast Fourier Transform to get the frequency domain, then use some statistical analysis package to sort out the grains into different populations.

Students who used this Z-80 system could digitize hundreds of grains per hour. The most time consuming parts were lining up the grains on the microscope slide, and transfering the data to the departmental VAX.

A few years later, after I had graduated from USC, Doctor Osborne asked me to upgrade his system so that we could do the digitizing and number crunching on the same system. So we purchased a VAXstation II, since it had a Q-bus, and a frame grabber for the Q-bus, and I rewrote the data collection system, using the VAX's WS window managing software.

Another few years later we upgraded the VAXstation II to a VAXstation 3200, and I converted the software to X-Windows/Motif.

In 1994, Doctor Osborne died of Creutzfeldt-Jacob disease. His PhD students continued using the system to finish their thesies. I don't know what has happend since.

Searching the internet I've found a few of the papers that have been published using data collected by this system. Here's a few.

(not sure why the 1982-1988 papers aren't online)