Simple Recursive Blob Detection

Continuing my quest for useless VB.NET code, I am going to delve into blob detection. When I say blob, I am not referring to Binary Large OBjects (like database BLOBs), but blobs in the visual sense – a contiguous area of one specific color (in the simplest case). A good example of blob detection is the magic wand tool in a paint program. When you click an area all similar and contiguous pixels are included to create a selection area. Another is optical character recognition (OCR), where the blobs that are found are possible characters.
The type of blob recognition I am going to describe is a very simple algorithm that does not use calculus – this is a straight forward recursive algorithm, however it may not be the best candidate for the job.

The Goal

The goal of this algorithm is to be able to identify the blobs in the following black and white image.

The first image above is the source image, and the second is the source with each pixel outlined in black and the blobs outlined in red. I will define a blob as a collection of pixels that share any of the 8 possible common borders. Notice that a blob could be defined using only 4 borders (that is, don’t count diagonal boarders), which would change the top two blobs in the example.

The Algorithm

The algorithm is simply going to count the number of pixels in the blob. This could easily be extended to actually collect the pixel locations to create a region. Keep in mind that in this example black pixels are “on” and white pixels are “off”. The basic idea is as follows:

1. To initialize, create a copy of the image, which will
be altered to mark the progress of the algorithm
2. Base Cases
a. If a pixel is off, return zero
b. If a pixel is out of bounds, return zero
3.Recursive Case
a. If a pixel is on
i. Turn off the current pixel
ii. Return 1 plus the sum of all 8 surrounding
pixels

And that’s the entire algorithm.

An Example: BlobSize(6, 1)

An example might help to clear up any confusion. Let’s get the size of the blob located at pixel (6, 1). The following image is a visual representation of what the algorithm is going to do in the first two recursive calls.

Assume our function is BlobSize(x as Integer, y as Integer) and returns an Integer (the number of pixels in the blob), and we are calling BlobSize(6, 1). We go back to the algorithm: step 1, this pixel is on and it is within the boundaries of the image, so we are not at a base case – skip to step 2. Step 2, the pixel is on, so turn it off and then return 1 + the sum of all surrounding pixels, that is:

Return _
BlobSize(5, 0) + BlobSize(6, 0) + BlobSize(7, 0) + _
BlobSize(5, 1) + 1 + BlobSize(7, 1) + _
BlobSize(5, 2) + BlobSize(6, 2) + BlobSize(7, 2)

Notice how each term in the return statement corresponds to a pixel from the 3×3 box in the image above (the 1 being the current pixel). The results from pixels 1, 2, 3, 4, 5, 6, and 7 will all be base cases and return 0 since they are off. But notice that pixel 8 is another recursive case, where it’s surrounding 8 pixels will be tested and the blob will expand. This function will ultimately return 5.
Here is the code for BlobSize():

Private Function BlobSize(ByVal image As Bitmap, _
ByVal x As Integer, ByVal y As Integer) _
As Integer
If x < 0 Or x >= image.Width Or _
y < 0 Or y >= image.Height Then
Return 0
End If
Dim c As Color = image.GetPixel(x, y)
If c.R = 255 And c.G = 255 And c.B = 255 Then
Return 0
End If
image.SetPixel(x, y, Color.White)
Dim size As Integer = 1
For i As Integer = -1 To 1
For j As Integer = -1 To 1
If i = 0 And j = 0 Then Continue For
size += BlobSize(image, x + i, y + j)
Next
Next
Return size
End Function


The Problem

Here is a comparison of the blob size (n) to the number of recursive calls (r):

n | r
---------------
5 | 41
6 | 49
13 | 105
1125 | 9001
1350 | 10801
2925 | 23401

The performance of this algorithm is 8n + 1 or O(n) in Big O notation. This causes a problem because the algorithm is recursive. The problem occurs for larger values of n. On my machine, the upper limit was 26705 recursions on a 196 x 156 pixel, solid black image. At this point the system ran out of stack space and I got a StackOverflowException.

Conclusion

This algorithm will work for images no larger than 3338 pixels on my machine; however the stack space can possibly vary from machine to machine. There are several sneaky tricks that could be done to make it work on larger images, but the bottom line is that this algorithm is not well suited for the task.
Ultimately, you must resort to using calculus to solve this problem with larger image sizes. I will show an implementation using the Gaussian or Laplaceian method some time in the future.

You can download the code and test images for BlobSize() here.

Tagged Tags: Algorithms, VB.NET, Vision on February 9, 2008 at 10:00 am