I have been giving a great deal of thought (and coding and testing) to the blob tracking algorithm i am using. The first hurdle is simple finding blobs in a bitmap. There are dozens of ways to do this, some more complicated than others. The one I finally settled on is a fairly common (i think) algo that is a combination of iterative pixel-by-pixel scanning and recursive similar-color-pixel-grouping.
It basically goes like this:
starting at pixel 0,0 start scanning across the bitmap, going down a row when you get to the end (simple raster) for every pixel check first to see if it is marked. (you will have to have some data structure to keep your marked flags, I am using another bitmap that i can then display to see what is going on) then check to see if it is ‘good’ (ie is blob-worthy. more on goodness later) if it is ‘good’ then hand it off to a recursive method that checks all the neighbors (ie the 8 surrounding pixels) to see if they are also ‘good’ and adding those pixels to a blob (more on blobs later). any non-good pixels it finds, mark them so the raster can ignore them, as well as marking the good ones so the raster will ignore them.
This should give you a nice group of blobs in fairly short order. After this step, I filter the blobs by size (if it is too small, i presume it is a false positive) I also check for blob intersections within a certain distance (ie two smaller blobs might not technically intersect, but if they are close enough together they are probably part of a small cluster that is just a poorly-lit blob, so i merge those based on a configurable minimum distance between them.
(Above: the first time i got the blobtracker and the display all coordinated, hand-modeled by my lovely girlfriend, Leonie. Doesnt have much to do with the blobtrackign algo, i just wanted to post it)
Of course, the real meat of the algo above is what constitutes ‘goodness’ in a pixel? In order to look at the way i have done it, i need to lay out some background thinking that I have done: First, as a general rule, i want to make any algorithm as simple as possible. This is nice for so many reasons, but the big ones are maintainability (ie figuring out what it does in six months when I come back to it) and speed, simpler is (almost) always faster. As for this specific problem, I wanted to avoid using any type of image filter. Why? because if I can pick out the blobs with my own eyes, then there is no need to do any complicated filtering to make them ‘more findable’ by the machine. This does not hold true for all machine vision goals, but for this one i think it does. (that and I spend a great deal of time using quartz composer to generate a filtered image that performed better than just a ‘raw’ image and nothing made it work the cycles to do)
(Above: a raw image from the IR camera under the surface)
With that in mind, i set out to make the simplest ‘goodness’ test that I could.
My original goodness test was basically this: Take the source pixel (ie what the cam is seeing right now) and subtract the background pixel in the same position. If the resulting difference pixel is above a configurable threshold value, then it is good.
This actually works quite well. One thing i really really like about it is that is is very very simple, and very very fast. (computationally) This is basically a difference matte with a threshold applied across the image.
The problem that was plaguing me (and it seems many other DI surface builders) is that this method works really well if you have a really nice even diffused IR lighting (thus making all your blobs nicely the same intensity). However, it would seem that in practice this is never the case (or at least it sure ins’t in my case). However, after spending two weeks tweaking my lighting to make it cover as much as possible, it still sucked in the corners and I am too lazy to go buy more IR illuminators.
Now, being a software guy, i am surprised it took me that long to decide i should be able to fix it in software (stupid hardware, always needing fixing :-). So i came up with a slightly (tho only very) more complicated scheme for blobby goodness.
The idea is this: take your pixel, subtract the background, and then instead of applying a constant threshold across the entire image, use a luminance map to hint the threshold into a value appropriate to the illumination level in that area. I had some ideas as to where to generate the lumi-map, first off being getting something that had a roughly similar IR reflectance as my fingers and cover the whole surface, and take an image. This would give a nice reference image. However, trying to keep things simple, i decided to start with just the background image as a rough lumi-map (since I am illuminating the diffuser (ie tracing paper) and that should give me a nice relative level of illumination.
Now the algorithm for goodness goes something like this: I have a configurable maximum threshold and minimum threshold. The max to be used at the brightest area and the min at the darkest (and smoothly transition for the inbetween areas. So when you take a background shot, quickly analyze it for max and minumum values. Those map to the max and min thresholds. for each pixel, find the difference between source and background, then compare that to the threshold the maps to that background color.
This seems to be 100% better than the straight difference matte + threshold. Until i find something better, I will be sticking with it.
