Goodbye Netscape

Netscape Navigator has officially been put to pasture. AOL has this to say about it:

"AOL's focus on transitioning to an ad-supported web business leaves little room for the size of investment needed to get the Netscape browser to a point many of its fans expect it to be. Given AOL's current business focus and the success the Mozilla Foundation has had in developing critically-acclaimed products, we feel it's the right time to end development of Netscape branded browsers, hand the reins fully to Mozilla and encourage Netscape users to adopt Firefox."

I feel sad for the loss of Netscape, having been introduced to the Internet on NN3; although the true spirit lives on in Mozilla/FireFox. From my point of view, AOL's takeover of Netscape was the final nail in the coffin. It was clear from the moment of takeover their only interest was to leverage the browser's audience.

It might be a good time to grab old versions if you are interested. The final version will be 9.0.0.6, cue the fat lady.

Posted in News on February 23rd

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 3x3 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.

Posted in Algorithms on February 9th

Wave Analyzer

I've posted some new code under the projects section, a wave analyzer. It's still pretty early in development, but you can use it to see how waves actually move, rather than just looking at formulas.

A simple sine wave is composed of 4 basic components: amplitude, frequency, wave length and phase angle. The wave analyzer allows you to add waves to the graph, and then tweak these components to see how it effects the output.

It gets interesting when you add multiple waves and then combine their output. This shows a similar output to what you would see if you had several wave generators hooked up to a string (in real life) and looked at their combined effect.

To get started, first go download the app (or source code). Run the application and then follow these steps to get something like this:

1. Click "Add Waveform" 2. Click "Add Waveform" again to get a second wave 3. Now in the Function Generators window, increase the wave length parameter of the second wave. 4. You should now see the plot of two waves on the green screen, to see the sum, click the "Sum All Channels" button, on the main window 5. To see *just* the sum, go back toe the Function Generators window and click the "visible" button on both the waves to hide them

Posted in Math, Waves, VB.NET and Modeling on February 5th