I recently stumbled onto a C tutorial on edge detection and decided to implement the algorithm in VB.NET. Edge detection is a machine vision technique that attempts to identify interesting parts of an image, such as where one object ends and another begins. One way of finding these areas is to search for sharp changes in intensity between each pixel and its neighbors. A source image is processed and an output image is created that highlights the edges found in the source. The output image is a visualization of what the algorithm detected and ultimately these results can be applied to solve a specific problem.
Although the background and mathematical basis for the algorithm are interesting, I’m only going to discuss them briefly and focus on the implementation and performance issues in .NET. If you are curious about the details behind the algorithm, you should check out the original articles I found.
The Algorithm
To find relative changes in intensity level, the algorithm processes the image one pixel at a time. It looks at the change in intensity to the left and right of the current pixel, stores it and then checks the change in intensity in the pixels above and below the current pixel and stores it as well. The actual process happens one dimension at a time for each pixel (horizontal and then vertical), and then combines the result into two dimensional pixel data, the output image.
As each pixel is encountered, its neighboring pixel’s intensity levels get calculated and then subtracted from the neighbor pixel on the opposite side. The resulting sum of all the pixels is the relative change in intensity at that location. If opposite neighbor pixels are the same color, when subtracted from each other the result will be zero (black). If the two neighboring pixels were radically different intensity levels the output would be greater than zero. The mechanism that averages the pixels is a weighted matrix, one for vertical (the xMask) and one for horizontal (the yMask):
Dim xMask(,) As Single _
= New Single(,) {{-1, 0, 1}, _
{-2, 0, 2}, _
{-1, 0, 1}}
Dim yMask(,) As Single _
= New Single(,) {{1, 2, 1}, _
{0, 0, 0}, _
{-1, -2, -1}}
Each element in the matrices represents a bordering pixel, with the center element being the current pixel. The numbers in each matrix is the weighting of the importance of the pixel at that location, so pixels directly above or beside the current pixel are weighted heavier (denoted above with a 2 instead of a 1) than diagonal pixels. Notice that in both matrices, the current pixel is ignored (set to zero).
For the vertical yMask, the strictly horizontal elements are zero, and the opposite is true for the xMask. The elements of each matrix are multiplied by the border pixels intensity levels, and then the results are summed. Since the opposite sides are also opposite signs, the sum is the change in intensity we were looking for. The final step is to add the absolute value of the horizontal and vertical differences in intensity. This process is actually a rough approximation of the mathematical gradient of the image.
First Implementation: GDI+
To get things started, I wanted to keep the details of working with the image data to a minimum, so I created the algorithm to work with the infinitely slow GDI+ Bitmap object using the GetPixel and SetPixel methods. The implementation is straight forward:
1. Create X and Y loops to scan across
each pixel in the source image
2. Create I and J loops to process the
eight border pixels for the current pixel (X,Y)
3. Get the current border pixel
Intensity(X + I, Y + J) : 1/3 * (R + G + B)
using Bitmap.GetPixel on the source image
4. Multiply the intensity by the appropriate mask
5. Clamp the output value to [0, 255]
6. Write the output pixel value to the output
image (Bitmap.SetPixel)
Below is sample output of the initial implementation:
This process typically runs in about 3K pixels /second, which sounds fast… but actually takes about 160 seconds to process an 800 x 600 pixel image (480K pixels). So for real-time processing, this method is absolutely out. Although it’s very slow, this method works as expected and was useful to me as a reference renderer as I tested new approaches.
Take Two: Direct Pixel Access
The GDI Bitmap object offers a handy function, Lock/UnlockBits(), that returns the raw bytes of memory composing the Bitmap object. By using this function, it is possible to read all pixels in one call, process them, and then write them back in a single call. This is much, much faster than using Get/SetPixel() methods which operate on a single pixel for each read and write. The intense down side of LockBits is that you no longer have friendly access to the pixel by X and Y coordinates, and documentation is pretty bad.
When calling LockBits(), you specify what format you want the data to be returned in. The pixels get returned as a contiguous array of bit data, and you are charged with picking it apart. For my purposes, I’ve forced the format to always be 24 bit RGB. The function returns a one dimensional array of bytes. Each pixel is encoded according to the format specified, so in my case, there are 3 bytes for each pixel (R, G and B). To emulate two dimensions, a “stride” value is given, which lets you know how many bytes there are per line, along with a “height” which is the total number of scan lines. So each pixel can still be accessed with X and Y coordinates by using the following formula:
Pixel.Red = Array[stride * Y + X * 3]
Pixel.Blue = Array[stride * Y + X * 3 + 1]
Pixel.Green = Array[stride * Y + X * 3 + 2]
Notice that the Y value is multiplied by the width of the scan line and X is multiplied by the amount of byte data per pixel, the 3 here is for RGB. The first byte at this location is red, the next byte is green and the last byte is blue, which is why 0, 1 and 2 are added to X.
To make this logic less painful, I created a wrapper class for the bitmap object which has its own GetPixel and SetPixel methods. This class locks the bits on the image when it loads and then operates on the array. It implements IDisposable, and when Dispose is called, it calls UnlockBits on the original bitmap image, committing all changes to the image at once.
This implementation runs at around 50Kp/s, a huge improvement of over the original. Processing the pixels in blocks greatly improved performance, but this is still a little too slow for any real-time application. The 800x600 image still takes about 10 seconds to process with this new method.
Take Three: Divide and Conquer
The next approach I took was to reduce the input data by splitting the image in two. The actual split is done by creating Rectangle objects and then passing these rectangles to LockBits when retrieving the image data.
Since I wanted to test different numbers of splits, it became very important to *neatly* keep track of work units, that is, what part of the image was actually being processed. Also, I had another idea in mind for the next implementation, so I wanted this idea of work units to be reusable. To facilitate this, I created a class called ImageWorkUnit with the following properties:
Image: The input Bitmap which is being processed
WorkArea: The Rectangle of the area to process
Result: The output Bitmap shared by all workers
Using this new work unit class, I then created a method to split the image into multiple work units (the number of units is variable) and then a loop to process each loop sequentially. Right now, stop and make a quick estimate of how fast this new method will run using two units (splitting the image in half). Before I ran this new implementation, I made an approximation of no more than few percent speed increase. I was wrong. This method runs at a blazing 450Kp/s, a vast improvement over the direct pixel access method.
As happy as I was with the result, it was a little disturbing and I decide to do some tests. I varied the number of divisions, and much to my surprise, using only one division it ran at the same speed, 450Kp/s. This implied that the speed increase was not caused by dividing the image, but by something else. Here is the original processing loop:
For y As Integer = 0 To inImg.Height - 1
For x As Integer = 0 To inImg.Width – 1
...
Next
Next
Now here is the new processing loop for the work unit based implementation:
For y As Integer = 0 To area.Height - 1
For x As Integer = 0 To area.Width - 1
...
Next
Next
The speed increase was due to the fact that I was no longer accessing the Height and Width properties of the image (it was also accessed in the body of the loop). It turns out, the Height and Width properties of the Bitmap object are not exactly optimized. By simply not accessing these properties inside the loop, I got a speed up of about 900%.
Take Four: Use the Cores Luke
In the final implementation, I created a new class to spawn separate threads to process the image in parallel. This function gets the processor count, and then splits the image that many times and spawns threads to process the chunks.
Oddly, this method runs at either 500Kp/s *or* around 700Kp/s. The discrepancy is because of the thread scheduler. In the new class I created, I simply spawn threads, fire them off and leave it up to the thread scheduler to pick a core to execute on. If both threads execute on the same core, the result is 500Kp/s, when they happen to run on different cores, the speed up to 700Kp/s occurs. I’m not exactly sure how to get around this in managed code – if you have any ideas, please post a comment and let me know.
So with the fastest algorithm, and my fingers crossed, it can process that 800x600 image in about 0.6 seconds (down from 2.5 minutes), which is actually a reasonable rate for real time applications.
Download the Sobel edge detector code and sample images.
Posted in Math, VB.NET and Algorithms on March 22nd
The new version of JavaScript aims to promote the script language to a full blown OOP language, with classes, inheritance, object-everything (no primitive types), etc. A change like this will inevitably create the standard issue bloat nay-sayers (refer to the C vs. C++ argument, in which C++ "is just C with a bunch of bloated useless garbage", or VB classic vs VB.NET or ASP classic vs ASP.NET or C++ vs Java or...). So which side of the fence are you on, does JavaScript need OOP?
Anyway, here is a nice posting describing some of the highlights...
Posted in JavaScript and Web2.0 on March 21st
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
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
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
I have updated the Matrix Library to make it more useful. Mainly, I've removed the 2x2 limitations from calculating determinants and finding inverses. I also added several new functions:
isSize: Checks the size of a matrix by rows and columns
newMatrix: Creates a new matrix of the specified size
transpose: Transposes the given matrix (rows -> cols)
augment: Augments A with matrix B -> AB
multRow: Multiplies the given row by constant k, k != 0
multRowAdd: Multiplies the source row by constant k, k != 0
then adds that row to the dest row
swapRow: Swaps row i with row j
ref: Uses Gauss elimination to reduce to row-echelon
format
rref: Uses Gauss-Jordan elimination to reduce to
reduced-row-echelon format
swapCol: Swaps column i for column j
delCol: Deletes the specified column
delRow: Deletes the specified row
minor: Returns the row minor, Mij
The most important additions were the elementary row operations, multRow, swapRow and multRowAdd - these were used to implement the row-echelon reduction methods. det(), ref() and rref() are the most *interesting* additions, although, I think the algorithms are not very efficient.
Posted in Math and Python on January 31st
The ASCII style of the site is novel, although not very functional. Google is not correctly indexing the site - the googlebot does not understand that there are columns of text, and treats the menus as part of the paragraph. Furthermore, search results from VisualCore.com are showing up at the bottom of the list. Another and perhaps bigger problem, is that copying text off the site is painful. If it is multiple lines, you always get chunks of the menu mixed in with the code (or other content) you are trying to copy.
So I have been working on a new graphical style, hopefully the initial release will be by Sunday (tomorrow). The layout work is done, I just need to flesh out the page content. I am also adding the ability to post comments to everything, which will be nice.
After the initial release, I plan to employ a few of the various open source JavaScript libraries, to see how they perform and to get some experience with them. For now, I plan on using Prototype (of course), Scriptaculous, Moo.Fx, LightBox, and maybe ASP.NET AJAX - although, it is a little bulky, so I'm not sure about that yet.
Posted in Design on January 26th
Recently, I have been learning how to create mathematical models in code so I figured I would share a little. Models are used to show how some phenomenon in life behaves and are typically based on an equation that represents the thing to be modeled. So the trick is to find a way to solve those equations in code.
Euler's method (pronounced Oiler) is one way of doing this, and I will show a very simple example using the following differential equation:
dy/dx = 2x
When solved by integration, the actual solution is:
y = x ^ 2
So that is the value that we want to obtain from the program after it completes. The Euler method requires initial known values for a starting point and then determines the slope of the tangent line at that point in order to find the next *approximate* point on the curve. The initial x, y values can be arbitrary (x=1 and y=1 are used in the example), but it must be a solution to the system - using x=1, y=8 would be bad since x^2=8 is false.
Since this is an approximation, the the final result will always be off by some margin of error (for example, for xMax=2, y should equal 4, since 2 ^ 2 = 4, but when you run this code, you will see that it is off by a small amount). This error is a function of the step size, dx. Smaller step sizes are generally more accurate. In the example below, a step size of 0.01 is used, which results in an error of 0.25% and a step size of 0.005 results in an error of 0.103%.
In the code below, xMax is the ending x-value that will be approximated, dx is the step size, and x & y are the initial known values. The code was written to be run as a console application in VB.NET 2005.
Sub Main()
Dim x As Double = 1
Dim y As Double = 1
Dim xMax As Double = 2
Dim dx As Double = 0.01
Console.WriteLine("X , Y -- % Error")
Do While x < xMax
Euler(x, y, dx)
Console.WriteLine( _
"{0:f2} , {1:f2} -- Error: {2:f3}%", _
x, y, (1 - (y / x ^ 2)) * 100)
Loop
Console.Read()
End Sub
Sub Euler(ByRef x As Double, _
ByRef y As Double, _
ByVal dx As Double)
Dim slope As Double = 2 * x
Dim change As Double = slope * dx
y += change
x += dx
End Sub
Here is a sample run:
X , Y -- % Error
...
1.91 , 3.64 -- Error: 0.249%
1.92 , 3.68 -- Error: 0.250%
1.93 , 3.72 -- Error: 0.250%
1.94 , 3.75 -- Error: 0.250%
1.95 , 3.79 -- Error: 0.250%
1.96 , 3.83 -- Error: 0.250%
1.97 , 3.87 -- Error: 0.250%
1.98 , 3.91 -- Error: 0.250%
1.99 , 3.95 -- Error: 0.250%
2.00 , 3.99 -- Error: 0.250%
As you can see from the sample run, the output claims that:
x ^ 2 = y
2 ^ 2 = 3.99
illustrating the approximation error. However, models are not supposed to be exact, they are supposed to be a representation that exhibits behavior similar to the thing your are trying to analyze. Also, there are much better approximation methods (such as Runge-Kutta). You wouldn't want to really use this method to solve the equation in this example, this was just to establish how the concept works. As the complexity of the model grows, this method becomes much more attractive.
This basic framework can be used to model all sorts of neat stuff. Coming up, I will post an example model for a cooling liquid using this method in conjunction with Newton's law of cooling, and then gravity and falling objects.
You can read more about Euler's method here.
Posted in Math, VB.NET, Modeling and Algorithms on January 20th
I recently ran across an interesting question in a usenet post; How do you convert an arbitrary color to a known / system color?
After some thought, I reasoned: in order to find the nearest known color, you must get the difference for each known color based on your sampled color. You could do this by looping through each known color in the enumeration Drawing.KnownColor.
Next, you could compare the R, G, and B values (or H, S, V values if that is more appropriate) for the known to the sample. To get the distance, you could either do a simple sum of the absolute differences, or if you are a Man or Woman of science, you would use the RMS (Root Mean Square) value. Finally, you keep the value with the smallest difference and return it.
In my sample code below, I also created a structure for returning the Name, Color and the Distance - this is just a little sugar to help the medicine go down, not really necessary.
Private R As New Random
Private Sub Button1_Click(ByVal sender As System.Object, _
ByVal e As System.EventArgs) _
Handles Button1.Click
Dim randColor As Color = _
Color.FromArgb(R.Next(0, 255), _
R.Next(0, 255), _
R.Next(0, 255))
Me.RandomColorBox.BackColor = randColor
Me.RandomColorLabel.Text = randColor.ToString
'// now match to nearest known color
Dim nearest As ColorName = FindNearestKnown(randColor)
Me.KnownColorLabel.Text = nearest.Name
Me.NearestColorBox.BackColor = nearest.Color
End Sub
Structure ColorName
Public Color As Color
Public Name As String
Public Distance As Integer
End Structure
Public Function FindNearestKnown(ByVal c As Color) _
As ColorName
Dim best As ColorName
best.Name = Nothing
For Each colorName As String In _
[Enum].GetNames(GetType(KnownColor))
Dim known As Color = Color.FromName(colorName)
Dim dist As Integer
dist = Math.Abs(CInt(c.R) - known.R) _
+ Math.Abs(CInt(c.G) - known.G) _
+ Math.Abs(CInt(c.B) - known.B)
If best.Name Is Nothing _
OrElse dist < best.Distance Then
best.Color = known
best.Name = colorName
best.Distance = dist
End If
Next
Return best
End Function
Posted in VB.NET and Windows on January 20th
A friend sent me this link recently to this guy who is doing amazing hacks with the Wii remote. He has an example of head tracking to create desktop VR that is pretty incredible.
You can check it out here.
Posted in News and Wii on December 27th, 2007
This work is licensed under a
Creative Commons Attribution-Share Alike 3.0 Unported License.