Posts tagged with “multitouch”

June 01, 09

Detecting blobs at the speed of light

While working on my eye tracking experiment I got to the point where I needed to execute a blob detection algorithm to determine relative positioning of the eyes. I found some really good blob detection algorithms but I didn't have enough time to try implementing them. Andrei R. Thomaz had ported an existing Processing library (based on subdivision), but it turned out to be too slow/complicated to fit for my needs.

Few days ago while looking for something else, I've found this genius object detection technique by japanese guy Kynd (developed from the original code by Kampei Baba). I decided to try it out for detecting blobs.

UPDATE: This blob detection method has also been discovered by Quasimondo and was shown (!) at Flash on the Beach 2007. It hasn't enough spread as Mario hadn't released the source.

You can test the result below, try it yourself. First, click the Flash area to activate, then click anywhere to add more blobs. You can also press space to toggle debug mode on/off.

I was totally amazed how fast (and exact) it performs! Believe or not but the main blob detection routine has only a few lines of code.

How does it work then?
It's really very simple – the secret lays in utilising the native floodFill Flash Player method in conjunction with getColorBoundsRect. Here's how (after the jump).


Take a bitmapData in. Then use threshold method to convert it into 1-bit (black and white) bitmap (Kynd did it by superimposing slightly displaced images in DIFFERENCE blend mode and then removing noise with ConvolutionFilter and the threshold method, I left it out to gain processing speed - it's not really needed unless you want to isolate more complicated shapes).

Now, the magic happens just in a few steps.

  1. Get the rectangle containing all white pixels by using getColorBoundsRect (exit if it's empty).
  2. Examine the first column of pixels by sampling their values with getPixel32. When white pixel is found, use floodFill to mark the found shape with some third color. Then run getColorBoundsRect again but this time looking for that color.
  3. If the derived rectangle fits the min/max size of the blob, store it's coordinates in the array.
  4. Regardless of the previous result use floodFill again but this time with fourth colour, just to mark that shape as processed.
  5. Repeat again until a number of blobs was found (or there's no more white pixels to examine).

I've modified Kynd's code a little bit, here's just the loop described above (you can grab the full class from his blog post).

while (i < maxBlobs)
    // get the rectangle containing only white pixels
    mainRect = r.getColorBoundsRect(0xffffffff, 0xffffffff);

    // exit if the rectangle is empty
    if (mainRect.isEmpty()) break;

    // get the first column of the rectangle
    var x:int = mainRect.x;

    // examine pixel by pixel unless you find the first white pixel
    for (var y:uint = mainRect.y; y < mainRect.y + mainRect.height; y++)
        if (r.getPixel32(x, y) == 0xffffffff)
            // fill it with some color
            r.floodFill(x, y, FLOOD_FILL_COLOR);

            // get the bounds of the filled area - this is the blob
            blobRect = r.getColorBoundsRect(0xffffffff, FLOOD_FILL_COLOR);

            // check if it meets the min and max width and height
            if (blobRect.width > minWidth && blobRect.width < maxWidth && blobRect.height > minHeight && blobRect.height < maxHeight)
                // if so, add the blob rectangle to the array
                var blob:Object = {};
                blob.rect = blobRect;

            // mark blob as processed with some other color
            r.floodFill(x, y, PROCESSED_COLOR);

    // increase number of detected blobs

In my example the blobs meeting the size conditions are marked with green outline, the remaining ones are marked with red outline.

I am planning to build my own cardboard box touchscreen and try it out to capture finger movements. If you are interested in multitouch interfaces, make sure you check out Lux AS3 framework as well.

08:17 AM | | 15 Comments | Tags: ,