Finding the faces

• note: this is a work in progress...

Finding the faces...

With the sandscope instrument hardware in good working order, we can now focus on refining the software that drives it, and execute the search for faces among millions and millions of sand particles.

5 focal layers

Highly magnified images have a shallow depth of field. The sand particle depicted above has a diameter of about 0.5 mm. Each photo has been taken at a slightly different distance from the object, and thus the focus is on different areas of the particle. To increase the chances of face detection, the detector will have a look at all the focal variants of the same object. Currently 8 'focal layers' are used. The first and last shots of a focus series are usually totally fuzzy, the remaining ones have varying degrees of sharpness. Only a few will have truly sharp areas. The latter are the targets that are worth examining, the others can be skipped, even before the face detector will consider them. The processing pipeline is thus set up as a two-stage filter: first sharpness, then face detection. Only samples that pass both filters make it to the output. Both filters will be implemented as artificial neural networks.

The reference face detector

The off-the-shelf face detector used for this project is a Go implementation of the PICO algorithm described in the paper "Object Detection with Pixel Intensity Comparisons Organized in Decision Trees"
by Nenad Markuš, Miroslav Frljak, Igor S. Pandžić, Jörgen Ahlberg, Robert Forchheimer

https://arxiv.org/abs/1305.4537

PICO is an efficient detector that compares favorably with some industry standard face detectors. It will be the baseline reference to compare our own custom detectors with. PICO returns a score for each detected face, which allows sorting of the search results. Unfortunately, an image with a higher PICO score does not necessarily  look more like a face than an image with a lower score, at least when judged by a human. It has happened that we were unable to see a face in an image with a fairly high PICO score.
The main research task is thus developing a detector that reliably detects faces and gives them face-ness scores that we humans agree with. This will then enable the Sandscope instrument to maintain a top-100 or top-1000 of best faces ever found, without any human intervention.

25 'faces' (1 day search)

These are the results of the first 24-hour test run: the 25 sand particles that more or less look like faces.
I agree with the detector in some cases, in other cases, i wonder what it was triggered by. There is obviously still a lot of work to do on the face detector, but there is reason for optimism: the above image is proof that the Sandscope instrument can actually be implemented, and is not just a theoretical device: faces -albeit vague ones- do appear in the output!
The PICO face detector is still way too lax when it comes to accepting a particle as a human face. This test run produced a collection of about a thousand candidates. Increasing the minimum detection score needed to accept an input image as a 'face' will result in fewer candidates, but doing so will also reject many 'good' sand faces. These 25 images were selected by a human, and they did have a wide variety of scores. So unfortunately PICO's opinion about a clear face does not match my own human opinion about what is a clear face.
Note that the PICO detector tends to favor 'potato heads'. It likes round and blurred shapes with vague facial features. This is likely a result of the inner workings of the algorithm, the way it models an average face as sets of gradients?

Facebook is interested to know who this is!

This grain of sand managed to fool the Facebook face detection algorithms. Many more will follow, it is simply a matter of dedicated search! The Facebook and Sandscope detectors agree on the face-ness of this image: both detectors experienced a level of stimulation that triggered a response. 
Interestingly, when looking at a result like this, once you see the face, you no longer see the grain of sand. Once the image is interpreted in one way, it is hard to switch to another way. 

The Artificial Neural Network face detectors

The custom detector is a regularly formed convolutional network, which has proven to be quite good at image classification in earlier experiments. The input is a 128x128 grayscale image, the output is a class probability. Tests are being done with a 2-class (face/no-face) and a 4 class (none/bad/ok/good) classifier.

The layers of the network are organised as follows:

  convolution       f1 128x128          (3x3 kernel, with dropout)
  max pooling       128x128 → 64x64
  convolution       f2 64x46            (3x3 kernel, with dropout and batch normalization)
  max pooling       64x64 → 32x32
  convolution       f3 32x32            (3x3 kernel, with dropout and batch normalization)
  max pooling       32x32 → 16x16
  convolution       f4 16x16            (3x3 kernel, with dropout and batch normalization)
  max pooling       16x16 → 8x8
  convolution       f5 8x8              (3x3 kernel, with dropout and batch normalization)
  max pooling       8x8 → 4x4
  convolution       f6 4x4              (3x3 kernel, with dropout and batch normalization)
  max pooling       4x4 → 2x2
  fully connected   u1
  fully connected   u2                  (output)

f1 to f6 are the numbers of feature maps of the convolution layers, and u1 and u2 are the number of units of the fully connected layers. Experiments are performed with a variety of settings for these numbers, from small to medium to large sized networks.

The detector is implemented using python and TensorFlow, and runs as server process that uses shared memory for the input images, and a simple text based API over UNIX domain sockets to receive requests and send replies. The main Sandscope application, written in Go, acts as a client of this 'isface' server. This setup turned out to be efficient and reliable. The image processing is reduced to a minimum, no encoding or decoding is necessary to perform the classification. The memory footprint is low, as all the image memory is re-used.

The training data

The custom 2-class (face/noface) networks were initially trained on images containing human faces, and on images that don't contain faces. There are various existing datasets available for download. The following two have been used:

1. Labeled Faces in the Wild : http://vis-www.cs.umass.edu/lfw/index.html
   
   13233 color images, 250x250 pixels, with the faces of 5749 people, gathered from the web. The faces have been centered.
2. CelebA : http://mmlab.ie.cuhk.edu.hk/projects/CelebA.html
   
   202599 color images, 178x218 pixels, with the faces of 10177 people, gathered from the web. The faces have been centered.

These face images were first made square (extracting the center region), then converted to grayscale and resized to 128x128 pixels.

The no-face images were made by automatically downloading random images from wikimedia, resizing them to about 1M pixels, and extracting random crops of 128x128 pixels. The images from wikimedia were manually checked to see if they contained faces. If they did, they were deleted.

It turned out that the above two face image datasets don't contain any young people, nor many old people. The majority is white. To reduce this bias, we gathered images from the web of babies, children, elderly people and all sorts of non Caucasian faces. We also collected faces found in drawings, paintings and sculptures. The faces in artworks are not photo-realistic faces, but very interesting nonetheless, because our human perception has no trouble detecting them as faces.

First experiments

The first neural network training sessions went very smoothly, the reported training and validation accuracies were impressive. Even networks with less than 100K parameters are able to reach validation accuracies of 99.8% and above. That means only 2 mistakes per 1000 input images! And it was funny to see that most of the mistakes made were actually faces of teddy bears, cats and dogs. 

generation 1 neural network, 1 day search

See here a human-made selection of the 25 most face-like sand particles that were found in a 1 day search. The detector gave a large amount of suggestions, in this case about four thousand, of which only a few turned out to have sufficient face-like qualities for us humans. Note that the neural network detector came up with face suggestions that exhibit more shape and expression variety than the PICO detector (there are less 'potato heads' here). This is good.

generation 2, 2 day search

The above image shows a human-made selection of the 25 most convincing faces of the next generation network. This 2nd generation network was trained with an extended dataset that contained several thousands of false positives that the 1st generation network produced. False positives are the cases where the network classified a grain of sand as a face, where we as humans do not see a face at all: detection mistakes. 
We hoped that including such mistakes as negative feedback would make the new network more critical, in effect suggesting less suggestions that were obviously false (in the eyes of a human). This turned out to be the case. The number of face suggestions that the new network produced was slightly lower than before, and the number of actually recognizable faces was significantly higher.

Encouraged by the success of the 'negative feedback' approach, we set out on training the next generation of networks, after adding examples of the failures of the previous network to the training data set. The path forward looked to be simple: train each new generation while adding samples of the mistakes of the previous generation, and in doing so, arrive at networks that are very critical and hardly make mistakes at all any more!
Sadly, this strategy didn't have the desired effect. It turned out that the new networks were forced into a corner too much: there seemed to be a suppression of generic face features, like the overall vertical oval shape. We think that too many mistake samples did have this overall shape, but lacked any further details. So the overall shape was more and more associated with being wrong, and the networks tried to find other face shapes which did still have some details right. This resulted in many face suggestions that looked very compressed and distorted.

When confronted with sand particles -which often exhibit rather random morphological features- the artificial neural network can easily come up with a 'face-ness' score that is very different from the score we humans make. When searching for faces in sand, the system is operating in a vague area where it has to decide about all sorts of cases that it never was exposed to during training. The AI can see a face where we as humans don't see one, and vice versa. Note that even two humans don't necessarily come to the same conclusion regarding the face-ness of a sand sample.
How to align the machine and human perception more, especially along the gradient of 'not a face' to 'hardly a face' to 'plausible face' to 'convincing face'? Ideally, the detector would only offer suggestions that we as humans agree with: all clear and convincing faces. 

The first face detector networks we implemented were binary classifiers that distinguish between face and
no-face inputs. Realizing that the Sandscope instrument requires a detector with a more nuanced output than only yes or no, experiments were started with multi-class detectors that label their output as being either 'not', 'bad', 'ok' or 'good' face. This meant we had to create a training data set from scratch.

The first idea was to create a not/bad/ok/good face data set automatically, by taking an existing face data set, and using the original face images as the examples of 'good' and then gradually 'messing up' the face images more and more, to form 'ok', 'bad' and 'not' examples. Unfortunately the face detector networks turned out to become very good at discerning between these automatically made artificial samples, but failed to deliver meaningful suggestions when processing images of actual sand particles. The networks must have learned how to recognize the 'fingerprints' of the methods to used to compromise the original images, without caring about the actual underlying content (faces).

What about creating a multi-class training set that purely consists of sand particle images? After all, the Sandcope has been running for months already, and has stored images of thousands and thousands of sand face suggestions! All these images can in principle be sorted into the not/bad/ok/good sample subsets manually, using human judgement, and serve as examples. Training a detector only on sand particles might have an interesting advantage: the detection is then purely based on the pareidolia effect. The network has never seen a real face but forms an imaginary prototype of a face by being exposed to more and more examples of sand that look like faces.

At this point in time, the sand face data set is rather small. This is a problem for artificial neural networks, because they tend to perform better with larger amounts of data to train on. Furthermore, the number of samples per subset varies a lot. There are only few 'good' faces, some more 'ok' faces, quite a few 'bad' faces, and lots of 'not' faces among the suggestions that the Sandscope returns when searching the sand.
As of 2019-11-06 the data set is composed of 693 'good', 1599 'ok', 3324 'bad', 14302 'not' sand face samples. It will be important to expand the data set over time to be able to train more sensitive and efficient detectors. The idea is to train a new network, install it on the Sandscope, do a search for a few weeks, sort out the newly stored suggestions, expand the data set, do a next training, and so on.

Currently the multiclass detectors are not performing so well. They reach accuracies of around 60%, which is significantly better than the 25% which would be the accuracy of a network that makes random guesses, but one would want to do better. Is it the right approach?
We are also still training binary face/no-face detectors using the sand face data set, and these detectors perform better, reaching accuracies between 80 and 90%. But even these networks tend to return too many false positives in their face suggestions. When glancing over these suggestions, you can see why the AI sees a face in them, but too often it takes too much imagination and mind bending effort. Are there networks that are more critical, and at the same time, don't skip good faces?

note: this is a work in progress...

The motions

note: this is a work in progress...

Sketch of the Sandscope instrument

Before coming up with a final design for the sandscope instrument, all of its motion sub-systems will have to be prototyped and experimented with, to be sure they perform well. There will be at least three motions involved in the operation of the instrument:

• Rotating the plate of glass. The sand grains will be deposited onto this plate, and will advance toward the microscope in small intervals of about 3 mm. Rotation will always go in one direction. There are no limits to the rotation, so end switches are not necessary. Driving the glass plate with a sturdy rubber wheel that is fixed to the motor axis seems a simple and reliable way to solve this. 
• Adjusting the microscope focus distance. This is achieved by moving the whole camera system up and down. A resolution of at least 0.05 mm is necessary to make proper sets of stacked photos. There should be no detectable sideways motion in the mechanism. otherwise stacking won't work. Since this actuator is limited in its range, end switches will be necessary.
• Controlling the flow of sand coming out of the container. A proper dose of sand is necessary to obtain an ideal spread of the particles onto the glass surface. The particle density should neither be too high nor too low.  A solenoid controlled valve mechanism could make this work.

Motor vibrations can be an issue when working with sensitive optical systems like this. Vibrations should be avoided at all cost, otherwise the photos that are taken will suffer from motion blur. During the initial experiments with stepper motors, it turned out that they can vibrate at high frequencies when driving them in micro-stepping mode. Vibrations during the actual stepping motion are normal, but it turned out that there can even be some vibration when the motor stands still. When in micro-stepping mode, the rotor of the stepping motor is often held in a position between the full steps by activating two coils simultaneously, with a proper dose of current for each coil. I don't know the details of this current regulation yet, i assume there is pulse width modulation involved at some point, and this is what can make a motor vibrate, even when it is supposed to stand still. Digital aliasing effects in the waveforms that are generated can lead to small oscillations of the motor axis. 

I have decided to also experiment with geared DC motors because they are guaranteed to be motionless when not activated. 

Assortment of geared DC motors under test

I have many geared DC motors in stock. For short and precise motions one would need motors with a high reduction in the gear train, so the outgoing axis turns slowly. I have tested several of such motors, and in principle they are suitable to drive the glass disk and the microscope focus mechanism. Without positional encoders, the action of these motors can only be controlled by accurate timing and speed control. The LM293 driver is used to implement forward and backward rotation. A PWM output of the Arduino is used to control the speed.
Even the expensive swiss precision engineered (minimot) motors make more noise and vibrations than a basic stepper motor. This type of motor will never be as durable and reliable as a stepper motor.

Two of the tested stepper motors

I have many stepper motors, both new and salvaged ones. The above two are new and it should therefore be possible to order extra ones as replacement parts, if necessary. These are candidates for use in the sandscope instrument.

• Wantai 42BYGHM809, Nema17 form factor, 400 steps/revolution, coil resistance 1.6 Ohm. Extra long version for higher torque. Axis 5 mm diameter, fully round. Ball bearings.
• MERCURY MOTOR SM-42BYG011-25, Nema17 form factor, 200 steps/revolution, coil resistance 35 Ohm. Axis 5 mm diameter, fully round. Ball bearings.

The Wantai motor seem ideal to drive the glass plate, because of its higher resolution. Smaller steps should result in smoother operation. The coil resistance is so low that the use of a driver with current limiter is mandatory.

2x Polulu DRV8824, 2x opto-interrupter, controlled by an Arduino Micro

Polulu DRV8824
https://www.pololu.com/product/2131

A low-current stepper motor driver module for bipolar stepper motors up to 0.75 A per coil (without heat sink). Uses the Texas Instruments DRV8824 stepper motor driver chip. Supports full step and 2/4/8/16/32 microstep operation.
This driver is a good choice to use with low-current motors. It isn't able to microstep motors with a low coil resistance (< 10 Ohm?). Even the DRV8825 based module, which is a higher current version, isn't able to microstep such motors. The sweet spot of the DRV8824 current limiter is narrow, but easily found by listening to the motor hum and by watching the axis move. Microstepping will fail when the coil current is too high or too low. I have not been able to attain settings that are free of motor vibrations, reliably, nor have i been able to establish completely silent operation, even when the motor stands still.

2x BigEasyDriver, 2x opto-interrupter, controlled by an Arduino Micro

BigEasyDriver
design and documentation : http://www.schmalzhaus.com/BigEasyDriver/
manufacturer: https://www.sparkfun.com/products/12859

A stepper motor driver module for bipolar stepper motors up to a max 2A/phase. Uses the Allegro A4988 stepper driver chip. Supports full step and 2/4/8/16 microstep operation.
This driver turned out to be especially useful for driving motors with low coil resistance. The sweet spot of the current limiter is narrow, but easily found by listening to the motor hum and by watching the axis move. Microstepping will fail when the coil current is too high or too low. With the proper current setting, there will be no noise nor any detectable vibration when the motor isn't stepping. 

Laser setup

For stepper motor position and vibration testing the setup show above has turned out to be very handy: a laser beam is directed at a mirror that is fixed to the motor axis. The movement of the motor axis is magnified substantially when the laser dot shines onto a wall that is meters away. Tiny angular displacements can be observed this way. The lasers turn out to have a sharp diffraction pattern which is helpful to detect the presence of vibrations. Any vibrations in the motor axis will blur the projected image. 

Some 3D printed parts for rapid prototyping

Thanks to my new Creality 3D Ender-3 printer I can design and fabricate functional prototyping parts easily. The parts shown here are used to test the glass plate drive mechanism. 3D printing is quite slow, all these parts together took about 18 hours to print. However, the printer has turned out to be reliable, so once a print has been started, you can go work on other things. The filament used here is Innofil InnoPET natural, which is a sturdy transparent material. Surprisingly strong. It can be bent, but it won't break easily. The accuracy in X and Y (width and depth) is high, the accuracy in Z (height) is disappointing, sometimes it is off by up to 0.3 mm. I will research this flaw and try to find a fix for it. 

UPDATE
I had a good look at the Z drive mechanism, and it turned out that the guide wheels were fixed too tightly. Loosening all these wheels and carefully tightening them again solved the Z irregularities completely. Make sure to stop tightening when everything just tight enough to remove all slack in the mechanism. I can make the wheels slip against the extrusion, by turning them with my fingers, which wasn't possible before. The whole assembly is much easier to move up and down now. No more step loss!

UPDATE
I noticed that all printed parts were slightly slanted to the right. Closer inspection of the printer geometry revealed that the x-axis was not perfectly square to the z-axis. The Ender 3 setup guide gives no warning about this potential issue, and does not advise to take special care when assembling the x-axis. There is some play in the way you can fix the parts together. Unfortunately you can't get at the screws when the x-axis is mounted on the machine, so you can't adjust it to be square while it is in place, and then tighten the screws. Solution: tighten the screws only lightly, so that it is still possible to fine-tune the alignment of the x-axis parts. Then mount the x-axis on the printer, measure the squareness, and fiddle with it until it is square. Then carefully take the x-axis off, tighten all screws well, and mount it again.
   

CBX 1605, Z-drive by RATTM MOTOR

CBX 1605 100mm Slide Stroke Linear Z Axis, RATTM MOTOR
www.ebay.com/itm/113145641019
€88 including DHL shipment from Changzhou, China (arrived after only 4 days!).

This is an industrial Z-axis assembly with a precision ball screw and linear guide, including a strong 200 steps per revolution Nema23 bipolar stepper motor to actuate it. The part is designed for vertical loads up to 30 kg, which is tens of times more than it will ever have to handle. The extra sturdiness and weight of this drive mechanism will help to keep microscope vibrations to a minimum. 
I can't feel any slack in the guide at all. According to the specs the maximal positional deviation is 30 μm.  
The screw pitch is 5.0 mm. With 1/16th microstepping of the 200 steps/rev motor, this gives a Z resolution of 1.5625 μm.  This should be more than enough to make stacked sets of microscope photos with different focus distances.

UPDATE
This z-axis has some slack after all. When looking at the microscope image while he camera is being moved up and down, you see a sideways shift. The shift is mostly vertical, and it is caused by the sliding block being driven off-center by the spindle. The block tends to rotate due to the leverage effect. This is a problem when stacking images: the images will be out of alignment. I am considering buying a high precision linear bearing and upgrading this z-axis with it.  

above: Z-drive, below: glass plate drive

In the test setup for the glass plate drive, a rubber wheel with an effective diameter of 10 mm is used,
which is pressed onto the motor axis directly. Combined with a 400 steps/rev motor in 16th microstep mode, this gives a resolution of 4.9 μm per step. Well beyond the minimum requirements!
The final design will likely have an O-ring with an effective diameter of 14 mm, which will give a resolution of
6.8 μm per step. 

Both the glass plate drive and the Z drive mechanisms have been tested for days on end. No anomalies have been detected so far. The stepper motors hum happily, and i cannot feel any vibrations when they do not turn. Both motors warm up only slightly. Passive cooling will suffice. The driver chips on the BigEasyDriver modules get warm to the touch, i guess about 50 to 60 degrees, which is very modest.

SandScope prototype #1

The first setup of all the prototyped parts turned out to be a working ensemble already. The basic functionality of the SandScope is up and running. No automatic sand dispersal and removal yet.

Observing things though a microscope makes their deviations clearly visible. I assumed that the glass disk would be flat enough, keeping the zero plane at virtually the same height. The glass is not flat... there is a wobble of about 0.2 mm, which is in the same range as the height of a small sand particle: very noticeable. Since the instrument will make several photos, each at a different focus layer, perfect flatness is not required. However, in the next iteration i will position a glass guide wheel as close as possible to the microscope lens to maximize the height stability there.

I will try to make all mechanisms as low as possible, to be sure that everything will fit under the perspex dome that will protect the instrument from dust and undesirable human intervention. As a bonus, stability will increase when minimizing the height.

Glass disk drive, prototype #2

The second iteration of the glass disk drive mechanism works well. The rubber dampens the motor microsteps, resulting in very smooth movement of the disk and the sand particles it carries. There is some slippage when testing sequences of clockwise and counter-clockwise motions. This slippage is fairly regular, and occurs when the direction of movement changes. In practice, this isn't a problem, because the disk will always rotate in a single direction.

Detail of the sand being observed

The 4.5 x 3.0 mm large viewing area of the SandScope usually contains 5 to 30 grains of sand. The sand as seen above has not yet been dispersed automatically. I have spread it out in a circle by hand. Ideally, a dispersal mechanism would achieve a more equal density with less dilution to the sides, so that less sand is 'wasted'. The sand handling is the next subsystem to design and implement!

The sand dispenser under test

The very first idea for a reliable and computer controllable sand dispenser that came up turned out to work really well. A thin and flexible silicone rubber tube is squeezed shut by a metal spring. A solenoid is attached to one end of the spring and on demand, it can pull the end of the spring away from the tube and in so doing, opens it, letting the sand particles through. A brief activation of a few hundreds of a second suffices to release a small quantity of sand.
Some refinements were necessary to ensure longevity of this mechanism. Initially the thin metal spring was in direct contact with the rubber tube, and after a few thousands of activations the tube was cut open and sand began to leak. Too much pressure! A lighter spring was used, in combination with a rubber damper where it touches the tube. There is no noticeable wear on the tube even after a million activations. 

Laying down the sand

In order to have a nice homogeneous density of deposited sand, the falling particles go through a spreader that has a few ^ shaped dividers in it. These dividers work as obstacles, the sand collides and bounces inside the spreader, disturbing the gaussian distribution that the sand grains would normally settle into. After some experimentation with the placement of the dividers, the particles come out in a quite uniform random way. 

The next generation of 3D-printed parts

Some of the next gen parts fresh from the printer, ready to be assembled. After the fine-tuning and calibration of the Creality Ender 3 printer, the printed parts come out much better. Squareness is good, the dimensions in X Y and Z are accurate. None of the parts have noticeable warping. Even the parts with a large footprint are nice and flat, and stand stable as a rock on a flat surface. Note that i have used the double amount of clamps to fix the flexible print bed, doing this may have contributed to prevent warping during 3D printing.

The real thing

note: this is a work in progress...

Grains of sand

note: this is a work in progress...

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. 

Two examples of raw crops of centered targets that are near other particles. The other particles make the view unnecessarily complex and might disturb the accuracy of the face detection system.

Flood fill the background to black, using a narrow shade range. Range fill all non-black pixels to white. This creates the raw mask that will be used to clean up the raw crop.

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...