## Project Euler 002 – JavaScript

11 02 2011

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"&gt;

<html xmlns="http://www.w3.org/1999/xhtml"&gt;

<title>Project Euler 002</title>

<body >

<script type="text/javascript">

fib0 = 1;

fib1 = 1;

fib2 = 2;

while (fib2 < 4000000)

{

fib0 = fib1 + fib2;

fib1 = fib0 + fib2;

fib2 = fib0 + fib1;

}

</script>

</body>

</html>

Discussion

C based languages have such similar syntax that this is a copy from the C# solution.  Of course, I had to remove the type declarations because it’s not strongly typed.  Oh, and I guess I do output to HTML.

## Phone Vision 11–Intro to Spatial Filters

11 02 2011

When working with images there is literally an infinite number of operations we can perform on a single pixel.  However, blindly manipulating the image will rarely, if ever, produce a desirable result.  For example, if an image is already too bright, we wouldn’t want to run a ‘brighten’ function on it.  We need to rely on context to achieve sensible results.  In the case of spatial filters our context is the neighborhood of the pixel.

Neighborhoods

What is a neighborhood?  Neighborhoods are simply pixels adjacent to the pixel we are working with. Neighborhoods are typically (but not always) squares with an odd dimension like 3×3 or 5×5.  While this is not a requirement, for our purposes we will stick with 3×3.  Later we may throw in a 5×5.  Incidentally, per pixel operations are a special case of neighborhood operations where the neighborhood is 1×1.

Filters

The term filter actually arises from frequency analysis (something we will get to later).  Some other terms that you might see used are convolution mask or kernel.  For now, we will think of a filter as a set of weights that correspond to pixels in the neighborhood.  If we have a 3×3 filter with weights w then we often express the weights as: When we “apply a filter” we are just calculating the average using the specified weights.  Let’s look at an example.

Imagine our neighborhood… and our filter… So our transformed pixel becomes: This identity* filter is pretty useless for (hopefully) obvious reasons, but it demonstrates the point.  If we apply this filter for every pixel in the image we will get the same image back.

* in mathematics, the ‘identity’ returns the original value for a given operation: e.g. 0 is the identity for addition so 1+0 = 1.

Code

Finally, let’s take a look at a filter function.

private WriteableBitmap Filter(WriteableBitmap grayscale, int[,] filter)

{

// we are going to create a new image

// because we don’t want to modify the

// old image as we are processing it

WriteableBitmap filtered =

new WriteableBitmap(

grayscale.PixelWidth,

grayscale.PixelHeight);

// boiler plate code for our

// histogram stuff

int[] histogram = new int;

int maxIntensity = 0;

// this is the magnitude

// of the weights |w|

// we will divide by this later

int filterMagnitude = 0;

for (int x = 0; x < 3; x++)

{

for (int y = 0; y < 3; y++)

{

filterMagnitude += filter[x, y];

}

}

// the math is easier if we create two loops

for (int y = 0; y < grayscale.PixelHeight; y++)

{

for (int x = 0; x < grayscale.PixelWidth; x++)

{

//here’s the pixel we’re centered on

int pixel = x + y * grayscale.PixelWidth;

byte intensity = (byte)grayscale.Pixels[pixel];

//if we are on an edge we are going to skip it

if (y == 0 ||

x == 0 ||

y == grayscale.PixelHeight – 1 ||

x == grayscale.PixelWidth – 1)

{

histogram[intensity]++;

if (histogram[intensity] > maxIntensity)

{

maxIntensity = histogram[intensity];

}

continue;

}

int newIntensity = 0;

//going from -1 to 1 makes the math easier here too

for (int yoffset = -1; yoffset <= 1; yoffset++)

{

for (int xoffset = -1; xoffset <= 1; xoffset++)

{

// we loop through each pixel in the neighborhood

// and apply the filter. by ‘apply the filter’

// I mean multiply it by the appropriate weight

newIntensity +=

((byte)grayscale.Pixels

[(x + xoffset)

+ (y + yoffset) * grayscale.PixelWidth])

* filter[(yoffset + 1), (xoffset + 1)];

}

}

// here we are scaling the new intensity back

newIntensity /= filterMagnitude;

newIntensity =

Math.Max(Math.Min(newIntensity, 255), 0);

// and now just set the color to the

// new intensity

filtered.Pixels[pixel] = (255 << 24)

| (byte)newIntensity << 16

| (byte)newIntensity << 8

| (byte)newIntensity;

histogram[(byte)newIntensity]++;

if (histogram[(byte)newIntensity] > maxIntensity)

{

maxIntensity = histogram[(byte)newIntensity];

}

}

}

PlotHistogram(histogram, maxIntensity);

return filtered;

}

Here’s a simple way to call this with the identity filter described above:

// create the identity filter

// important note: this is ROW by COLUMN (y, x)

int[,] filter = new int[,] {{0,0,0}, {0,1,0}, {0,0,0}};

WriteableBitmap filtered = Filter(grayscale, filter);

As expected, using the identity filter the results are exactly the same.  This is a good test to make sure we didn’t mess anything up.  Next time we will use this code to apply some useful filters.  Summary

Though the formulas might look a little daunting when you write them down, the concept of spatial filtering is pretty easy.  Now that we have some code that makes it trivial to test different filters, I suggest you do just that.  Play around with this and over the next few lessons we will talk about some specific filters.