Finding the particles
Now that the microscopic imager system is able to make good quality photos of sand particles, time has come to implement the first stages of image processing: detecting and isolating individual grains of sand that will be the targets for further investigation. For the purposes of face detection in these grains of sand, grayscale images suffice, they might even have more potential than full color images because color can distract from form. The modest Sony a5100 Live View resolution of 1024x680 is high enough to do good initial segmentation.
For testing purposes i have made a glass slide onto which raw, unfiltered sand from the Texel beach has been spread out onto a layer of transparent lacquer. After drying, this slice can serve as a reference object.
It has regions with various sand grain densities. The test image used here is from a medium dense area, which is suitable to test the algorithms because it is more challenging than a less dense area. Denser areas will have more clusters of particles that touch than less dense areas.
Ideally the sand grain detection system should be able to detect all individual grains of sand, even when they touch and show no trace of the background in between them. In the test image seen below, we humans have no trouble at all discerning each individual particle, even in a single glance. Particles that are surrounded by the monochrome background on all sides are the easiest. Particles that lie next to each other can be separated too, even when their texture is quite similar. Let us see how far we get with a first iteration of a software detection algorithm.
 |
| original 1024x680 Live View capture |
Detecting the background is a relatively trivial task. The background is bright and fairly monochrome. This will always be the case in the micro imager setup, where the light shines from behind into the microscope objective.
// FloodFill fills the image with pixel value nv, for each pixel with a value
// in range [min, max], starting at sx, sy. Returns the number of filled pixels.
func FloodFill(img *ImageGray8, nv, min, max uint8, sx, sy int) int
This flood fill operation will reliably and efficiently fill the background, as long as the starting position is in the background area. In areas where the grains are clustered, it is possible that parts of the image background can't be reached. This problem is easily solved by starting the flood fill multiple times, from various locations in the background.
// GridFloodFill searches flood fill starting places on a grid with a spacing
// of d pixels. When there is a horizontal and vertical line segment of at
// least n pixels with a value in the range [min, max], a flood fill is started.
func GridFloodFill(img *ImageGray8, nv, min, max uint8, n, d int) in
With a sufficiently small grid spacing and sufficiently large segment length, virtually all of the background can be found and made black (value 0). After the background has been detected, the next step is filling all non-black pixels to white (value 255).
// RangeFill sets all pixels with a value in the range [min, max] to the new
// value nv. Returns the number of filled pixels.
func RangeFill(img *ImageGray8, nv, min, max uint8) int
This results in the following output image. Note that there are clusters of several particles here and there. Note also how the background has leaked into a few grains. This happens when a grain has a fuzzy and light spot in its contour, effectively connecting its bright interior with the background.
 |
| flood-filled, range-filled: foreground/background separation |
The clusters, or 'blobs' that consist of several particles can often be separated into individual particles by a process of pixel erosion.
// Erode will set non-black contour pixels to black. nSteps iterations will be
// performed. Black pixels have value 0.
func Erode(img *ImageGray8, nSteps int)
Blobs with a sufficiently narrow 'waist' will be split into multiple parts. The number of erosion steps should be carefully chosen. Values that are too large will lead to the complete disappearance of smaller particles or even multi-particle blobs. In the following image it can be seen that not all multi-particle blobs have been turned into a set of isolated particles. There are also some particles that have almost been eroded away completely.
 |
| eroded to separate some clumps |
As a final step, each white blob that is present after erosion is flood filled with a unique shade. This fill operation will also track the bounding box of the filled area, so that it generates information about both the size and the location of each blob. Filling the blob with a non-white color ensures that it won't be processed twice.
// FloodFillBBox fills the image with pixel value nv, for each pixel with a
// value in range [min, max], starting at sx, sy. Returns the bounding box of
// the filled area and the number of filled pixels.
func FloodFillBBox(img *ImageGray8, nv, min, max uint8, sx, sy int) (aabbox.Box2, int)
The following image shows the Live View image in grayscale, overlaid with all the bounding boxes that have been found. Note how some bounding boxed contain multiple grains of sand, and how some grains of sand have not been found. However, the system performs well enough to be used. It is fast too, segmentation only takes a fraction of a second!
 |
| bounding boxes around targets |
Isolating the particles
After the full resolution capture has been made, the results of the segmentation can be used to locate the potential targets for analysis. Ideally, the grain of sand is centered in a square, with some free space around it. The face detector system can then be presented with a clean input. Rotated versions of the target can easily be made, without any artifacts.
It often happens that the cropped image around the target grain contains parts of other grains. The following procedure is used to generate a clean targets. Note that only grains of sand that do not touch other grains will survive this process.
Flood fill with black all the white blobs that touch the edges. This will erase them. The resulting mask is ready for application to the raw crop.
The final target crops, generated by setting those pixels in the raw crop to the background color, where the mask is black. Nothing is changed where the mask is white. The background color here is the lower limit of the flood fill range that was used earlier to fill the background. Perfectly seamless results!
Once we have the clean targets, a set of rotated versions can be made. The face detection classifier will be trained on upright faces, so each grain of sand should be looked at under several angles. Rotations can be generated efficiently by rendering the target image as a texture in an off-screen framebuffer, applying the desired rotation, and reading back the rendered pixels. As the final step of the image processing pipeline, these new images will be downscaled to the classifier resolution. Here are two example series, sets of 12 rotations each (using 30 degree increments) @ 256x256 pixels.
Future work
It will be worthwhile to try and improve the segmentation system so that it has a higher yield. The current algorithms extract only about 15 to 30 clean targets from the capture depicted above, depending on where the focus was. I guess this number could be doubled, or tripled even? Note that efficiency will be better with less dense samples, where there will be relatively few clumps of particles to start with.
The main flaw in the current segmentation code is the separation of nearby and touching particles. This could be improved by using a more refined processing pipeline:
- erode faster at convex spots than at concave spots: should conserve the constituent parts better
- dynamic erosion that stops before a particle totally disappears
- make a stacked image out of several images that have been focused at a different depth
- use a more adaptive way to detect the background (no more hard-coded range of shades)
note: this is a work in progress...
