Blob extraction library

A library to perform binary images connected component labelling. It also provides functions to manipulate, filter and extract results from the extracted blobs, see features section for more information.

News

2007-03-22: Version v6 available for linux. Thanks to Jon Azpiazu.

2007-16-02: New version (v6) available! The performance has been increased drastically for images with large number of blobs (thanks to D.Grossman for the advice).

2006-11-13: Added prebuilt documentation in the Download section.

2006-11-10: New version (v5) available as an attachment to this file (see Download section). This version contains some bug fixes and some new functionalities.

Features

The library provides two basic functionalities:

Extract 8-connected components in binary or grayscale images. These connected components are referred as blobs.
Filter the obtained blobs to get the interest objects in the image. This is performed using the Filter method from CBlobResult.

The library is thread-safe if different objects per thread are used.

Download

The library is distributed in a single zip file cvblobslib_OpenCV_v6.zip for windows and cvblobslib_v6_linux.tar.gz for linux.

The documentation can be downloaded here.

Build intructions

cvBlobsLib has been developed using Microsoft Visual C++ (6.0) and also can be used in .NET. A Linux version could be downloaded here.

cvBlobsLib is distributed in a static library (.lib). To use it, it is needed to build the .lib file and later use that lib file in the desired project. To build the .lib file, simply open the MSVC++ project and build it (debug or release version).

To build the project where the library is to be used follow this steps (MSVC++ 6.0):

In "Project/Settings/C++/Preprocessor/Additional Include directories" add the directory where the blob library is stored
In "Project/Settings/Link/Input/Additional library path" add the directory where the blob library is stored and in "Object/Library modules" add the cvblobslib.lib file
Include the file "BlobResult.h" where you want to use blob variables.
In "Project/Settings/C++/Precompiled Headers" select "Not use precompiled headers" (Thanks Brendan)

NOTE: Verify that in the project where the cvblobslib.lib is used, the MFC Runtime Libraries are not mixed:

Check in "Project->Settings->C/C++->Code Generation->Use run-time library" of your project and set it to
Debug Multithreaded DLL (debug version) or to Multithreaded DLL ( release version ).
1. Check in "Project->Settings->General" how it uses the MFC. It should be "Use MFC in a shared DLL".

NOTE: The library can be compiled and used in .NET using this steps, but the menu options may differ a little

NOTE 2: In the .NET version, the character sets must be equal in the .lib and in the project. [OpenCV yahoo group: Msg 35500]

Documentation

The function documentation is included in source files and a full HTML documentation can be build using Doxygen.

The main classes are: CBlobResult and CBlob. CBlobResult stores a set of blobs and CBlob stores a single blob.

To build a CBlobResult, just use its image constructor on a input 1-channel image. This image can be binary or gray-leveled, in the later case it will be threshholded using the gray level specified in the CBlobResult constructor. This will fill the CBlobResult with all the blobs of the image (see NOTE 3). The blobs from the CBlobResult object can be filtered using the Filter method.

To filter the blobs, the library uses the blob operator concept: a class, derived from COperadorBlob which implements the function operator () on a CBlob object (see for example the CBlobGetArea class to extract the blob's area). The criteria to include or discard blobs is any object from classes derived from COperadorBlob (area, perimeter, gray level, etc., or new classes created by users).

NOTE 3: The are two extra blobs extracted from any image: the background and a blob with area 0. This blob with zero area corresponds to a helper external frame for the blob extraction process, the background can be discarded using the mean gray level (255 or 0, depending on the blob colour).

Algorithm

The algorithm is based on Dave Grossman's code with some few additions. Dave Grossman explained his code in this post:

I first saw this algorithm about 30 years ago in a presentation by Gerry Agin at SRI International (then called Stanford Research Institute). I have been unable to find it in any journal articles, so I implemented it by memory. The basic idea is to raster scan, numbering any new regions that are encountered, but also merging old regions when they prove to be connected on a lower row. The computations for area, moments, and bounding box are very straightforward. But the computation of perimeter is very complicated. The way I implemented it was in two passes. The first pass converts to run code. The second pass processes the run codes for two consecutive rows. It looks at the starting and ending columns of a region in each row. It also looks at their colors, whether or not they were previously encountered, and whether a region is new or old, or a bridge between two old regions. There are lots of possible states, but I deal explicitly with the only states that are important. There are 8 of these states:

I think this might be the paper, W. Snyder and A. Cowart, “An iterative approach to region growing,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 1983.

W. Snyder is a professor at NCSU and explains the algorithm and how to implement it in one pass in his book "Machine Vision".

At each stage, the algorithm is scanning through two consecutive rows, termed LastRow and ThisRow. During this scan, it sees a region in each row. In Cases 1-4, the region in LastRow starts 2 or more columns before the region in ThisRow. In Case 1, the region in LastRow ends one or more columns before the region in ThisRow starts. Therefore, these regions are NOT connected. In Case 2, the region in LastRow starts before the region in ThisRow, but the LastRow region continues at least to the column just before the region in ThisRow starts. Or it continues further, but it ends before the region in ThisRow ends. Therefore, if these regions have the same color, then they are connected.

RickyPetit changed my code to provide 4 or 8 connectivity. I had used 6/2 connectivity, which meant that at a corner like this 01 10 the 0's are connected but the 1s are not connected. In other words, the connectivity of a pixel is given by this mask: 110 1X1 011 i.e., pixel X is connected to the 6 pixels with a 1 but is not connected to the 2 pixels with a 0. This introduces a slight bias in favor of regions that slope to the left, but I consider it preferable to using either 4-connectivity or 8-connectivity.

Project samples

The library has been succesfully used in these projects:

cork stopper inspection
http://derindelimavi.blogspot.com/2007/09/cvblobslib-etiketleme-ve-flopencv-05.html
Add your own!

Code examples

   1 /** Example of extracting and filtering the blobs of an image */ 
   2 
   3 // object that will contain blobs of inputImage 
   4 CBlobResult blobs;
   5 
   6 // Extract the blobs using a threshold of 100 in the image
   7 blobs = CBlobResult( inputImage, NULL, 100, true );
   8 
   9 // create a file with some of the extracted features
  10 blobs.PrintBlobs( "c:\\tmp\\blobs.txt" );
  11 
  12 // discard the blobs with less area than 5000 pixels
  13 // ( the criteria to filter can be any class derived from COperadorBlob ) 
  14 blobs.Filter( blobs, B_INCLUDE, CBlobGetArea(), B_GREATER, 5000 );
  15 
  16 // create a file with filtered results
  17 blobs.PrintBlobs( "c:\\tmp\\filteredBlobs.txt" );
  18 
  19 // object with the blob with most perimeter in the image
  20 // ( the criteria to select can be any class derived from COperadorBlob )
  21 CBlob blobWithBiggestPerimeter, CBlob blobWithLessArea;
  22 
  23 // from the filtered blobs, get the blob with biggest perimeter
  24 blobs.GetNthBlob( CBlobGetPerimeter(), 0, blobWithBiggestPerimeter );
  25 
  26 // get the blob with less area
  27 blobs.GetNthBlob( CBlobGetArea(), blobs.GetNumBlobs() - 1, blobWithLessArea );
  28 
  29 // build an output image equal to the input but with 3 channels (to draw the coloured blobs)
  30 IplImage *outputImage;
  31 outputImage = cvCreateImage( cvSize( inputImage->width, inputImage->height ), IPL_DEPTH_8U, 3 );
  32 cvMerge( inputImage, inputImage, inputImage, NULL, outputImage );
  33 
  34 // plot the selected blobs in a output image
  35 blobWithBiggestPerimeter.FillBlob( outputImage, CV_RGB( 255, 0, 0 ));
  36 blobWithLessArea.FillBlob( outputImage, CV_RGB( 0, 255, 0 ));