Blob detection
By Erik van Kempen | April 8, 2007
Currently most of my spare time is occupied by my multitouch project. I'm building a low-budget touchscreen, by using simple materials: acrylic, IR LEDs and a simple web cam. Search YouTube for some example videos. The images from the web cam contain light spots on the places where I touched the acrylic. The center coordinates of these 'blobs' needs to be determined in order to use them for UI control.
Part of my research goals is to find a fast blob detection algorithm. So during these boring hours I've been brainstorming about possible methods to determine the center point of blobs.
Without having a look at (commercial) blob detection libraries, I came up with four possible methods.
Linemax
Method
- Find entry point: iterate through pixels until you find 'white' pixel.
- Determine distance to exit point on vertical axis.
- Determine center of that vertical line.
- Find longest line within blob, which goes through center of the found vertical line.
- Determine center of this linemax and define it as center point of the blob
Problems
Watch out for single-pixel blobs. You can exclude all blob pixels (or outer rectangular shape) during further blob analysis.
Speed
The speed of this algorithm is defined by the iterations needed to find longest line within blob. The larger the blob the more possibilities and thus the more iterations needed.
Outer rectangle
Method
- Find xmax, ymax, xmin and ymin points: iterate through pixels until you find 'white' pixel with highest or lowest x and/or why.
- Determine corners of outer rectangle.
- Determine diagonal line of rectangle.
- Define the center of this diagonal line as the center of the blob.
Problems
Finding max and min values is difficult. Various situations, such as overlapping lines can cause strange behaviour. For example banana shapes can cause a center point calculation outside the blob.
Speed
The speed of this method is linear to the size of the blob, because every pixel needs to be examined for the max and min value analysis.
Inner circle
Method
Try to find the largest inner circle for every 'white' pixel. The center of the largest circle can be defined as the center of the blob.
Problems
You need to constantly check if the new point you try is in the same blob as other points.
Speed
This is quite slow, because the speed increases exponentially with the size of the blob. Every pixel has a lot of possibilities.
Inner rectangle
Method
Try to find the largest inner rectangle for every 'white' pixel. The center of the largest rectangle can be defined as the center of the blob.
Problems
You need to constantly check if the new point you try is in the same blob as other points.
Speed
This is quite slow, because the speed increases exponentially with the size of the blob. Every pixel has a lot of possibilities.