Adventures in connected component labeling

Original Adventures in connected component labeling Editable
version 1 of 1



 

Connected component labeling is a relatively simple form of computer vision. The goal is to identify contiguous regions of pixels and note their outline, size, number or position.

what is connected component labeling algorithm and one example pro...


 

In the simplest sense, how many blobs are in the image?

There is plenty of CCL software existing, see below for a list. But none of them filled my need for a small, standalone, fast and free library/utility. First and foremost, QuickBlobs was made to meet all those goals.

 


4k test image, with white and black areas marked

So how does QuickBlobs stack up? It is written in C and is extremely light weight, compiling to less than 5KB as a library or 15KB as an executable. The worst case memory use of the algorithm is O(sqrt(n)) and a 10 thousand pixel wide image needs at most 640KB. QuickBlob is naturally fairly quick. My low end laptop can do a 4k by 4k image in just 0.6 seconds. Most of that time is spent decoding the image. Even with the decode time, it is more than fast enough to process standard definition video in real time. Finally it is licensed LGPL, so you can use it freely in your applications.

How is it so fast? It uses a single pass algorithm based on sorted quadruply linked lists. Most other algorithms work one pixel at a time, while QuickBlob operates on run-length-encoded line segments. It only holds at most two RLE-ed rows of data in memory at any given moment. This particular implementation allocates the maximum amount of memory possible from the start for best cache spatial locality.

Quick Start

Building the QuickBlob library should need almost nothing. It is very close to not even needing a libc. To use it as a library, you'll need to define a few stub functions for loading images and logging results. Take a look at quickblob.h for a summary.

QuickBlob comes with a small example utility, csv-blobs. This takes an image as input and produces a comma separated list of every blob found. It needs the DevIL library for image loading. While csv-blobs has not been tested on windows, it should be no more difficult to install than DevIL. On Linux or OSX, just run make to build the library and utility.

For most common workloads, Imagemagick + csv-blobs should meet your needs. If you need help building QuickBlob for your platform or integrating it into your application or even just have a feature request, feel free to email me.

Todo

  • contour tracking
  • concave splitting
  • visibility attributes
  • private structures
  • make libc optional

Other Applications:

  • Dotcount proprietary, windows only, non-commericial
  • RoboRelm proprietary, windows only, $150
  • Insight Tool Kit Apache licensed, very large (550 pages of docs)
  • cvBlobsLib BSD, based on OpenCV
  • cvBlob LGPL, C++ library, based on OpenCV
  • Blobscanner GPLv3, Processing Language
  • Blob Tool Lisp based image processing toolkit
  • Imagemagic but the --segment option either does not work or is very slow.
  • Plugins for Matlab, ImageJ and other similar large math/image suites. Often these plugins do not work with recent versions.