Counting blobs

[el_supremo]

I took a photo of part of a large flock of birds this afternoon and now I'd like to count how many there are.
I started with this original photo (reduced in size):
http://members.shaw.ca/el_supremo/birds_640.jpg

and removed the extraneous parts of the image and then reduced it to black and white.
http://members.shaw.ca/el_supremo/birds_bw.gif

Now I want to count the number of "blobs" in the image. I've done it manually but now I'd like to automate it. Does anyone know of an algorithm to do this?

Thanks
Pete

[fmw42]

Negate the image to make the birds white on a black background. Get the average graylevel of the image as percent from identify -verbose info: <image>. Multiply the the area (number of pixels) in the image, ie. widthxheight to estimate the number of bird pixels. Make an estimate of the number of pixels in the average bird blob. Divide the number of bird pixels by the average number of pixels in a bird blob.

[el_supremo]

Hi Fred,
I've done the count by averaging and also by partitioning the image into sections and then counting the birds in each section.
What I would like is a way to automatically count the blobs.
The only thing I can think of at the moment is:
scan the image until a black pixel is found and count it as a bird.
mark that pixel as "found" and then make a list of all black pixels which are its neighbours.
for each one in the list, mark it as "found" and add to the list all the black pixels which are its neighbours except for those already in the list.
repeat until the list is empty.
repeat the whole process until there are no more pixels.

I was wondering if there was some process which would reduce each black blob to a single pixel and then they could just be counted.

Pete

[fmw42]

I don't know of any easy method. Your approach of scanning and finding connected areas and putting them in a list is pretty standard for this kind of thing if you want to program something. I thought you wanted something that could be done by IM already and there is nothing that I know about apart from the approximate techniques that you have used and I have suggested. You might try searching the Internet for some standalone package or other tool that does blob analysis. This is typical of medical applications. For example you might look at ImageJ from NIH. It was designed for medical applications and has a large collection of plugins that are available. You might look at the list of plugins and see what might be available. They are open source.

http://rsb.info.nih.gov/ij/
http://rsb.info.nih.gov/ij/plugins/

[el_supremo]

Thanks for the pointers Fred.
I've written a program which uses the method I outlined previously and it seems to work fine when given a previously prepared black and white image.

Pete

[fmw42]

Any chance that your solution could be submitted to IM for general use with binary images.

You might consider enhancing it with not only the count of blobs, but also a readout of the area (number) of pixels for each blob and perhaps shape analysis, such as a best fit to an ellipse with the major and minor radii for each blob, etc.

[anthony]

In other words. A general bitmap segmentaion routine

As a non-IM method that may be posible. blur the grey scale image a bit
then threshold it back to a bitmap (that will collect disjoint blobs into single blobs. You can then use autotrace to generate the SVG vector image. The number of vectors 'path's it needs to use, minus one for the background color is the number of blobs!!! It is a little off beat but should work.

See my one example of autotrace,
http://imagemagick.org/Usage/transform/#edge_vector

[el_supremo]

You guys are way ahead of me. I'm just counting birds
I can post or email the code if anyone's interested.

Pete

[anthony]

Please do.

Though as I get on a plane to China tomorrow, I may not see it until I get back.

[el_supremo]

[EDIT] I've changed the code so that it uses a queue instead of a stack. The stack required a lot of memory, on the order of width*height/3 bytes.
A queue requires only 2*height bytes. This allocates 3*height just to be sure.
[/EDIT]

Here's the code. It uses Windows MessageBoxes for error reporting but that can easily be massaged.

Pete

Code: Select all

#include <windows.h>
#include <wand/magick_wand.h>
#include <stdio.h>

// It appears that, for a queue, the worst case memory requirement is 2*height bytes
// whereas for a stack it is on the order of width*heigth/3 bytes

// To prepare a photo you can usually just change its number of colours to 2
// which reduces the image to black and white. Then use a white paint brush
// to paint over the black areas which aren't birds. Then save the file as
// GIF or PNG - but NOT jpg or other lossy compression.

#define MARKED 127
struct queue {
	int y;
	int x;
};
struct queue *queue,*top, *bottom;

// This allocates 3*height bytes for the queue and allows the amount
// to be changed easily
#define QUEUE_WIDTH 3
// A macro to add a pixel to the queue if it is within the bounds of the
// image and is black, in which case the pixel is MARKED so that its neighbours
// can't add it again
#define addq(yy,xx) \
	if((yy) >= 0 && (yy) < height && (xx) >= 0 && (xx) < width) {\
		if(*(mi + (yy)*width + (xx)) == 0) {\
			top->y = (yy);\
			top++->x = (xx);\
			*(mi + (yy)*width + (xx)) = MARKED;\
			if(top >= queue + ((QUEUE_WIDTH)*height)) {\
				top = queue;\
			}\
			if(top == bottom) {\
				MessageBox(NULL,"Queue Overflow","",MB_OK);\
				return -1;\
			}\
		}\
	}

// Returns -1 on error or a count of the birds (black blobs) in the image.
// If black_count is not NULL, the number of black pixels in the image is returned
int MagickBirdCount(MagickWand *m_wand,int *black_count)
{
	register unsigned char *p;
	register int i,j;
	int height,width,birdcount;
	int x,y;
	int depth;
	int bcount;
	unsigned char *mi = NULL;

	if(m_wand == NULL)return -1;
	height = MagickGetImageHeight(m_wand);
	width = MagickGetImageWidth(m_wand);
	if(height*width < 1)return -1;

	depth = MagickGetImageDepth(m_wand);
	if(depth != 1) {
		MessageBox(NULL,"Image bit depth is more than one","",MB_OK);
		return -1;
	}
	// Allocate space for the queue
	queue = (struct queue *)AcquireMagickMemory(height*(QUEUE_WIDTH)*sizeof(struct queue));
	if(queue == NULL) {
		MessageBox(NULL,"AcquireMagickMemory failed to allocate the queue","",MB_OK);
		return -1;
	}

	// Allocate space for the image
	mi = AcquireMagickMemory(height*width);
	if(mi == NULL) {
		MessageBox(NULL,"AcquireMagickMemory failed to allocate image memory","",MB_OK);
		RelinquishMagickMemory(queue);
		return -1;
	}
	// and read it into the new array
	if(!MagickGetImagePixels(m_wand,0,0,width,height,"R",CharPixel,mi)) {
 		MessageBox(NULL,"MagickGetImagePixels failed","",MB_OK);
		RelinquishMagickMemory(queue);
		RelinquishMagickMemory(mi);
		return -1;
	}

	// The process is to scan the image until a black pixel is found, add
	// it to the queue and count it as a bird.
	// Then take a pixel off the queue and add back to the queue any of its neighbouring
	// pixels which are black. Repeat this until the queue is empty.
	// Then scan for the next black pixel and repeat until all pixels have been examined
	p = mi;
	birdcount = bcount = 0;

	for(j=0;j<height;j++) {
		for(i=0;i<width;i++,p++) {
			if(*p != 255)bcount++;
			// Skip anything except black
			if(*p)continue;
			// Found a black pixel - count it as a bird
			birdcount++;
			top = bottom = queue;
			// Add this pixel to the queue
			addq(j,i);
			// Now find and mark all neighbouring pixels which are also black
			while(top != bottom) {
				// Get the next element from the bottom of the queue
				y = bottom->y;
				x = bottom->x;
				bottom++;
				if(top == bottom)top = bottom = queue;
				else if(bottom >= queue + ((QUEUE_WIDTH)*height)) {
					bottom = queue;
				}
				// Now add all the neighbours of this element to the queue
				addq(y-1,x-1);
				addq(y-1,x);
				addq(y-1,x+1);
				addq(y,x-1);
				addq(y,x+1);
				addq(y+1,x-1);
				addq(y+1,x);
				addq(y+1,x+1);
			}
		}
	}
	if(black_count)*black_count = bcount;
	RelinquishMagickMemory(mi);
	RelinquishMagickMemory(queue);
	return birdcount;
}