GeekBlog.nl -

Blob detection II - Tracing edges

By Erik van Kempen | May 9, 2007

After considering several methods for finding the center of a blob in the entry "Blob detection", I found another method: edge tracing.

By tracing the edges of the blobs, you can find the extreme values in the x and y direction and thus the center of the blob.

My technique is based on an approach developed by Arslan and Türkoglu at University of Firat, Turkey. In their paper they describe how to trace the edge of an object fast and easy.

1. Find an entry point
2. Look for next surrounding pixel with sub threshold (or the other way around) properties in a certain order and remember the direction.
3. Change the order of checking pixels based on that direction and go back to step 2

I wrote a simple test for this method, including some enhancements, in C. Download as file.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct coordinate
{
	unsigned int x;
	unsigned int y;
};
typedef struct coordinate coordinate;

struct zone
{
	unsigned int xmin;
	unsigned int xmax;
	unsigned int ymin;
	unsigned int ymax;
};
typedef struct zone zone;

char * createBytemap(unsigned int width, unsigned int height)
{
	int i, j;

	char * bytemap = (unsigned char *) malloc(width * height * sizeof(char *));
	return (unsigned char *) bytemap;
}

int findEntryPoint(coordinate * entryPoint, unsigned char * bytemap, unsigned int width, unsigned int height)
{
	unsigned int x, y;

	for(y = 0; y < height; y++)
	{
		for(x = 0; x < width; x++)
		{
			if(bytemap[y*width+x] == (unsigned char) 255)
			{
				entryPoint[0].x = x;
				entryPoint[0].y = y;

				printf("Entry point found @ (%u,%u)\n", x, y);

				return 1;
			}
		}
	}

	printf("No entry point found\n");
	entryPoint = NULL;
	return 0;
}

void findCenterPoint(unsigned char * bytemap, int width, int height)
{
	int i, j;

	coordinate entryPoint;
	coordinate point;

	unsigned int direction = 0;

	zone rectangle;

	while(findEntryPoint(&entryPoint, bytemap, width, height))
	{
		point = entryPoint;

		rectangle.xmin = point.x;
		rectangle.xmax = point.x;
		rectangle.ymin = point.y;
		rectangle.ymax = point.y;

		while(1)
		{
			switch(direction)
			{
				case 0: // Normal mode
					if(bytemap[((point.y + 0) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += 0;
						direction = 3;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += 1;
						direction = 3;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x + 0)] == 255)
					{
						point.x += 0;
						point.y += 1;
						direction = 0;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += 1;
						direction = 0;
					}
					else if(bytemap[((point.y + 0) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += 0;
						direction = 1;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += -1;
						direction = 1;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x + 0)] == 255)
					{
						point.x += 0;
						point.y += -1;
						direction = 2;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += -1;
						direction = 2;
					}
					/*else
					{
						point = previousPoint; // Return to previous point
					}*/
					break;
				case 1:
					if(bytemap[((point.y + 1) * width) +  (point.x + 0)] == 255)
					{
						point.x += 0;
						point.y += 1;
						direction = 0;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += 1;
						direction = 0;
					}
					else if(bytemap[((point.y + 0) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += 0;
						direction = 1;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += -1;
						direction = 1;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x + 0)] == 255)
					{
						point.x += 0;
						point.y += -1;
						direction = 2;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += -1;
						direction = 2;
					}
					else if(bytemap[((point.y + 0) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y = point.y;
						direction = 3;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += 1;
						direction = 3;
					}
					break;
				case 2:
					if(bytemap[((point.y + 0) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += 0;
						direction = 1;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += -1;
						direction = 1;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x + 0)] == 255)
					{
						point.x += 0;
						point.y += -1;
						direction = 2;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += -1;
						direction = 2;
					}
					else if(bytemap[((point.y + 0) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += 0;
						direction = 3;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += 1;
						direction = 3;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x + 0)] == 255)
					{
						point.x += 0;
						point.y += 1;
						direction = 0;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += 1;
						direction = 0;
					}
					break;
				case 3:
					if(bytemap[((point.y - 1) * width) +  (point.x + 0)] == 255)
					{
						point.x += 0;
						point.y += -1;
						direction = 2;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += -1;
						direction = 2;
					}
					else if(bytemap[((point.y + 0) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += 0;
						direction = 3;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += 1;
						direction = 3;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x + 0)] == 255)
					{
						point.x += 0;
						point.y += 1;
						direction = 0;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += 1;
						direction = 0;
					}
					else if(bytemap[((point.y + 0) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += 0;
						direction = 1;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += -1;
						direction = 1;
					}
					break;
			}

			if(point.x < rectangle.xmin)
				rectangle.xmin = point.x;
			if(point.x > rectangle.xmax)
				rectangle.xmax = point.x;
			if(point.y < rectangle.ymin)
				rectangle.ymin = point.y;
			if(point.y > rectangle.ymax)
				rectangle.ymax = point.y;

			if(point.x == entryPoint.x && point.y == entryPoint.y)
				break;
		}

		// Calculate center point
		point.x = (((rectangle.xmax-rectangle.xmin)/2) + rectangle.xmin);
		point.y = (((rectangle.ymax-rectangle.ymin)/2) + rectangle.ymin);

		printf("Center: (%u, %u)\n", point.x, point.y);

		// Draw rectangle black (exclude this zone from further analysis)
		for(i = (rectangle.ymin - 1); i < (rectangle.ymax + 1); i++)
			for(j = (rectangle.xmin - 1); j < (rectangle.xmax + 1); j++)
				bytemap[i * width + j] = (unsigned char) 0;

		// Draw crosshair
		bytemap[(point.y - 1) * width + point.x] = 128;
		bytemap[point.y * width + point.x - 1] = 128;
		bytemap[point.y * width + point.x] = 128;
		bytemap[point.y * width + point.x + 1] = 128;
		bytemap[(point.y + 1) * width + point.x] = 128;
	}
}

int main()
{
	// Timing
	clock_t start;
	clock_t stop;

	unsigned char * bytemap;
	unsigned int width, height;
	int x, y;

	FILE * image = fopen("blobs.pgm", "rb");
	FILE * result = fopen("result.pgm", "wb");

	if(fscanf(image, "P5 %u %u 255 ", &width, &height) != 2) // Fetch height and width or die
		exit(1);

	bytemap = createBytemap(width, height);

	// Read bytes from original image
	for(y = 0; y < height; y++)
	{
		for(x = 0; x < width; x++)
		{
			bytemap[y * width + x] = (unsigned char) fgetc(image);
		}
	}

	start = clock();
	// Find center point
	findCenterPoint(bytemap, width, height);
	stop = clock();

	printf("Total time: %.3f s\n", ((double) stop - (double) start) / (double) CLOCKS_PER_SEC);

	// Write results to result image
	fprintf(result, "P5 %u %u 255 ", width, height);
	for(y = 0; y < height; y++)
	{
		for(x = 0; x < width; x++)
		{
			fputc((int) bytemap[y * width + x], result);
		}
	}

	fclose(image);
	fclose(result);
	return 0;
}

Return to home