Blob detection V: growing regions algorithm
By Erik van Kempen | January 14, 2008
As promised in the previous article about blob detection, I would describe an better and faster algorithm for detecting and finding blobs in an image. This algorithm uses a more intuitive approach for finding the blobs: growing the interesting regions.
Algorithm
The concept is easy. An image is represented as a matrix with a certain number of pixels on a certain number of lines. When the image is grayscale, every one of those pixels has a value which indicates the brightness of the image at that point. When you (virtually) convert this grayscale image to a black and white image, where every pixel above a certain threshold is white and under that threshold is black, you have generated a black and white image with the white area's being the blobs. With that in mind you can run the following sequence of actions:
Check the first line of the image and find groups of one or more white pixels. These are the blobs on a certain line, called lineblobs. Number each of these groups. Repeat this sequence on the next line. While you are collecting the lineblobs, you check the lineblobs on the line you have checked before this current line and see if these blobs overlap each other. If so, you merge these lineblobs as one blob ie. give the current lineblob the same number or id as the lineblob(s) on the other line. Repeat this for every line and you have a collection of blobs.
Take for example the following image of 6x5 pixels. On the left you see the image as a whole and on the right you see it as seperate lines. The right is what the algorithm sees. First you check line 0 and you will find no white pixels, so proceed to line 1. There is a lineblob on this line with starting point 1 and ending point 2. This lineblob is assigned ID=0 There is no other lineblob on this line or on the previous line, so proceed to the next line. There is a lineblob with starting point 1 and ending point 2. Now check if there is lineblob on the previous line with overlapping pixels and you will find that this is the case, so you give this lineblob the same ID (ID=1) as the overlapping lineblob. We are still on line 2 and you are checking the next pixels. You will find another lineblob with starting point 4 and ending point 4 (just a single pixel). You check for it to overlap with the lineblob on the previous line. This is not the case, so you assign ID=2 and proceed to the next line. You will find another lineblob with starting point 4 and ending point 4. Once again, you check for overlapping lineblobs on the previous line. The first lineblob on the previous line does not overlap, the second does, so you give it ID=2. Then you proceed to the next line, which does not contain a lineblob. You are finished and you have collected two blobs.
Collected data
In the meantime you count the number of pixels in the blobs, which is the area of the blob; you calculate the bounding box with the extreme values of x and y; and you calculate the center point. The easiest way to calculate the centerpoint is by calculating the centerpoint of the bounding box. This is faster, but not as precise. I personally think this is all the data you need.
Example implementation
This is an example implementation in C++. I know this is really bad code and some steps could be merged in the same pixel evaluation loop, but this is just an implementation hacked together in one night. It uses a stream of images from the OpenCV library which is often used to perform image manipulation and computer vision technologies. Or download the source file.
#include <iostream> #include <fstream> #include <string> #include <vector> #include <map> #include <ctime> #include "cv.h" #include "highgui.h" using namespace std; struct coordinate { unsigned int x, y; void * data; }; struct lineBlob { unsigned int min, max; unsigned int blobId; bool attached; }; struct blob { //unsigned int blobId; coordinate min, max; coordinate center; }; bool detectBlobs(IplImage* frame, IplImage* finalFrame) { int blobCounter = 0; map<unsigned int, blob> blobs; unsigned char threshold = 235; vector< vector<lineBlob> > imgData(frame->width); for(int row = 0; row < frame->height; ++row) { for(int column = 0; column < frame->width; ++column) { //unsigned char byte = (unsigned char) imgStream.get(); unsigned char byte = (unsigned char) frame->imageData[(row*frame->width)+ column]; if(byte >= threshold) { int start = column; for(;byte >= threshold; byte = (unsigned char) frame->imageData[(row*frame->width)+ column], ++column); int stop = column-1; lineBlob lineBlobData = {start, stop, blobCounter, false}; imgData[row].push_back(lineBlobData); blobCounter++; } } } /* Check lineBlobs for a touching lineblob on the next row */ for(int row = 0; row < imgData.size(); ++row) { for(int entryLine1 = 0; entryLine1 < imgData[row].size(); ++entryLine1) { for(int entryLine2 = 0; entryLine2 < imgData[row+1].size(); ++entryLine2) { if(!((imgData[row][entryLine1].max < imgData[row+1][entryLine2].min) || (imgData[row][entryLine1].min > imgData[row+1][entryLine2].max))) { if(imgData[row+1][entryLine2].attached == false) { imgData[row+1][entryLine2].blobId = imgData[row][entryLine1].blobId; imgData[row+1][entryLine2].attached = true; } else { imgData[row][entryLine1].blobId = imgData[row+1][entryLine2].blobId; imgData[row][entryLine1].attached = true; } } } } } // Sort and group blobs for(int row = 0; row < imgData.size(); ++row) { for(int entry = 0; entry < imgData[row].size(); ++entry) { if(blobs.find(imgData[row][entry].blobId) == blobs.end()) // Blob does not exist yet { blob blobData = {{imgData[row][entry].min, row}, {imgData[row][entry].max, row}, {0,0}}; blobs[imgData[row][entry].blobId] = blobData; } else { if(imgData[row][entry].min < blobs[imgData[row][entry].blobId].min.x) blobs[imgData[row][entry].blobId].min.x = imgData[row][entry].min; else if(imgData[row][entry].max > blobs[imgData[row][entry].blobId].max.x) blobs[imgData[row][entry].blobId].max.x = imgData[row][entry].max; if(row < blobs[imgData[row][entry].blobId].min.y) blobs[imgData[row][entry].blobId].min.y = row; else if(row > blobs[imgData[row][entry].blobId].max.y) blobs[imgData[row][entry].blobId].max.y = row; } } } // Calculate center for(map<unsigned int, blob>::iterator i = blobs.begin(); i != blobs.end(); ++i) { (*i).second.center.x = (*i).second.min.x + ((*i).second.max.x - (*i).second.min.x) / 2; (*i).second.center.y = (*i).second.min.y + ((*i).second.max.y - (*i).second.min.y) / 2; int size = ((*i).second.max.x - (*i).second.min.x) * ((*i).second.max.y - (*i).second.min.y); // Print coordinates on image, if it is large enough if(size > 800) { CvFont font; cvInitFont(&font, CV_FONT_HERSHEY_PLAIN, 1.0, 1.0, 0, 1, CV_AA); char textBuffer[128]; // Draw crosshair and print coordinates (just for debugging, not necessary for later multi-touch use) cvLine(finalFrame, cvPoint((*i).second.center.x - 5, (*i).second.center.y), cvPoint((*i).second.center.x + 5, (*i).second.center.y), cvScalar(0, 0, 153), 1); cvLine(finalFrame, cvPoint((*i).second.center.x, (*i).second.center.y - 5), cvPoint((*i).second.center.x, (*i).second.center.y + 5), cvScalar(0, 0, 153), 1); sprintf(textBuffer, "(%d, %d)", (*i).second.center.x, (*i).second.center.y); cvPutText(finalFrame, textBuffer, cvPoint((*i).second.center.x + 5, (*i).second.center.y - 5), &font, cvScalar(0, 0, 153)); cvRectangle(finalFrame, cvPoint((*i).second.min.x, (*i).second.min.y), cvPoint((*i).second.max.x, (*i).second.max.y), cvScalar(0, 0, 153), 1); // Show center point //cout << "(" << (*i).second.center.x << ", " << (*i).second.center.y << ")" << endl; } } } int main() { CvCapture * capture = cvCaptureFromCAM(CV_CAP_ANY); if(!capture) { fprintf( stderr, "ERROR: capture is NULL \n" ); getchar(); return -1; } // Create a window in which the captured images will be presented //cvNamedWindow( "Capture", CV_WINDOW_AUTOSIZE ); cvNamedWindow("Capture", 0); cvNamedWindow("Result", 0); while(1) { // Get one frame from the web cam IplImage* frame = cvQueryFrame(capture); if(!frame) { fprintf( stderr, "ERROR: frame is null...\n" ); getchar(); break; } IplImage* gsFrame; IplImage* finalFrame; gsFrame = cvCreateImage(cvSize(frame->width,frame->height), IPL_DEPTH_8U, 1); finalFrame = cvCloneImage(frame); // Convert image to grayscale cvCvtColor(frame, gsFrame, CV_BGR2GRAY); // Blur the images to reduce the false positives cvSmooth(gsFrame, gsFrame, CV_BLUR); cvSmooth(finalFrame, finalFrame, CV_BLUR); // Detection (with timer for debugging purposes) clock_t start = clock(); detectBlobs(gsFrame, finalFrame); clock_t end = clock(); cout << end-start << endl; // Show images in a nice window cvShowImage( "Capture", frame ); cvShowImage( "Result", finalFrame ); // Do not release the frame! cvReleaseImage(&gsFrame); cvReleaseImage(&finalFrame); //If ESC key pressed, Key=0x10001B under OpenCV 0.9.7(linux version), //remove higher bits using AND operator if( (cvWaitKey(10) & 255) == 27 ) break; } // Release the capture device housekeeping cvReleaseCapture( &capture ); cvDestroyWindow( "Capture" ); cvDestroyWindow( "Result" ); return 0; }
Or have a look at the generated output (16% CPU usage, 10 millisecons per blob calculation time):
Pros
- This algorithm is extremely fast. Most definitely faster than tracing edges of blobs.
- It is quite intuitive.
- Small memory footprint
- Because of the use of vectors of data it can perfectly be used by the more modern SIMD processors, which can process multiple data (in a vector) extremely fast, like the Cell processor.
Cons
- It still uses a fair amount of CPU cycles (15% @ 800 MHz with an Intel Pentium M 1.8GHz).
More information
You can find more information about OpenCV here:
Interested?
If you are also interested in this technology or if you want to ask a question, you can always contact me via my email address (see footer or ). I would love to hear your ideas.