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

e51b2b9a58824dd068d8777ec6e97e4d(((more)))

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;
                blobs.push(blob);
            }

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

    // increase number of detected blobs
    i++;
};

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 | | 14 Comments | Tags: ,

Comments

  1. As you mentioned in my blog I am going to try this algorithm to improve speed, but mine works pretty fast for me. the worst part is to detect direction of every blob. It takes lots of CPU. As for my example I'm using Region Growing algorithm

    Eugene on

  2. Thank you for great compliments but I'd confess that the words should go to Kanpei Baba who invented the most important part of the code. I thought I had mentioned that in the post but it's missing... The original code can be downloaded from here: http://faces.bascule.co.jp/motiondetection I also added a link to my blog.

    kynd on

  3. Thanks,very interesting, I linked your blog;)

    Touch User Interface on

  4. Ha, that's exactly algorithm I showed in my blob tracking demo back at Flash on the Beach 2007. Serves me right for never publishing my code.

    Mario Klingemann on

  5. Nice post! Thanks for not only publishing the source, but for the great explanation as well. Always nice to read a blog post where code is defined in plain words.

    cipriano on

  6. Hi Og2t! You've got a great blog Is there any chance to make de code available? I'm needing it desperately hurry. Many thanks in advice

    Litle girl from Brasil

    Camila on

  7. This looks really interesting. I wonder how complicated it would be to alter this so that each blob get's an id and then we know if a blob is new or if an existing blob just moved, or was removed.

    Did you ever try to to such a thing?

    Best

    Sammi on

  8. @Camila The most of the source code (that does fast blob detection) is available above, just hook it up to whatever you need.

    @Sammia Thanks, the feature you're talking about is implemented in multi touch interface. Just google for it, it's open source.

    Og2t on

  9. HI Looks awesome, and am surprised how fast it is. IM trying to have a play and have gone through you sources and got the relevent codes, but unless im missing something i think there is some code missing can you post it? Thanks Wayne AS3 newbie

    Wayne on

  10. Hi! Sammia asked amout ID'ing the blobs, you said there was a project that implemented this ... i can't find it ... when i google for it it gives me lots of multitouch links but not the thing i'm looking for. Do you have a direct link or site?

    Marty on

  11. hi mano, can you share your code i am trying to make multitouche table???

    vladozver on

  12. I'm not 100% sure but I also think there's something missing in your code. At the moment you just scan down the first line of the mainRect and look for blobs here. Don't you also need to continue scanning across x aswell?

    Jimmy on

  13. Can you please provide full code, need something similar to track flies experience... Regards Sérgio

    Sérgio Silva on

  14. Huge thanks for the starter with this.... I took your trackLight class and added a camera calibration around it for a recent projection game... download the code here http://www.spotdesign.co.uk/2011/08/31/whack-a-pyramid-ir-tracking/ Nice work.

    Mark on

Adding comments disabled for now.