February | 2011 |

Project Euler 003 – TSQL

17 02 2011

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Solution

–The prime factors of 13195 are 5, 7, 13 and 29.

–What is the largest prime factor of the number 600851475143?

— this number is bigger than my database

— so we will add it

CREATE PROCEDURE [dbo].[FactorNumber]

@number AS BIGINT,

@originalnumber AS BIGINT

DECLARE @isPrime BIT

SET @isPrime = 1

DECLARE @factor BIGINT

SET @factor = FLOOR(SQRT(@number))

DECLARE @divisor BIGINT

WHILE @factor > 1

BEGIN

IF @number % @factor = 0

BEGIN

EXEC FactorNumber @factor, @originalnumber

— can’t do the math in the function call

— so I used another variable

SET @divisor = @number / @factor

EXEC FactorNumber @divisor, @originalnumber

SET @isPrime = 0

END

SET @factor = @factor – 1

END

— here we store the information for later

IF @isPrime = 1

BEGIN

INSERT INTO NumberFactor (number, factor) VALUES (@originalnumber, @number)

END

–here are the remaining steps to get the answer

–exec FactorNumber 600851475143, 600851475143

–select MAX(factor) from NumberFactor where number = 600851475143

Discussion

I’ve included the procedure and the select statement here because this number exceeded my number list. It follows the same philosophy as some of the previous examples except that it inserts its values into a table instead of returning them to the calling function. This is why we need to pass the original number in as well.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Comments : Leave a Comment »
Tags: Project Euler, TSQL
Categories : Project Euler

Project Euler 003 – IronRuby

16 02 2011

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Solution

#The prime factors of 13195 are 5, 7, 13 and 29.

#What is the largest prime factor of the number 600851475143?

def PrimeFactor(number)

isPrime = true;

factors = Array.new

factorCandidate = Math.sqrt(number).floor

while factorCandidate > 1 do

if number % factorCandidate == 0 then

isPrime = false;

#kinda like the ‘push’ syntax here

PrimeFactor(factorCandidate).each {|factor| factors << factor }

PrimeFactor(number / factorCandidate).each {|factor| factors << factor }

end

factorCandidate -= 1

end

if isPrime then

factors.Add(number)

end

factors

end

factors = PrimeFactor(600851475143)

puts factors.max

Discussion

Even though I copied and pasted my C# solution here it still took me a while to iron out the kinks. There are some things I really enjoy about the syntax so far, but I still haven’t discovered the virtue of dynamic typing. Maybe I will as time passes.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Comments : Leave a Comment »
Tags: IronRuby, Project Euler
Categories : Project Euler

Phone Vision 12–Smoothing Filters

15 02 2011

What does it mean to smooth an image? When I imagine a smooth surface it doesn’t have a lot of bumps or pits. If we were to try to smooth out a rough piece of wood we would probably sand down the peaks and fill in holes. If you apply that analogy to an image it sounds a lot like averaging a neighborhood.

Average Filter

If you remember from last time we described a neighborhood filter using a number of weights as follows:

A simple average would allow all of the pixels in the neighborhood to contribute equally to the average. In that case would represent the filter as:

Using our code from last time, the filter looks like

int[,] filter = new int[,]

{

{ 1, 1, 1 },

{ 1, 1, 1 }

};

And here are the results when we run it:

The original is on the left and the smoothed version is on the right. Notice how the large objects are relatively unchanged, but the small objects have lost a lot of information. In addition to removing noise, if we are trying to segment large objects, we can use smoothing to blur out the small objects.

Modified Filter Code

If we run this filter enough times we will eventually get every pixel to be some sort of gray. It would be more efficient just to increase the size of the window. Let’s modify the filtering code to accept a square filter of arbitrary size.

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

{

// we are still 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[256];

int maxIntensity = 0;

//here’s where the magic starts

//assume the filter is square

int length = (int)Math.Sqrt(filter.Length);

int filterMagnitude = 0;

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

{

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

{

filterMagnitude += filter[x, y];

}

// this will be used for our loops

// it’s important that our size is odd

// so that our current pixel can be the

// center point.

int radius = length / 2;

// the math is still easier if we create two loops

// instead of one

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 leave it

// as the original intensity. you will see the

// edges increasingly unsmoothed as the window

// size increases. here we are using the radius

// to determine our bounds

if (y <= radius – 1 ||

x <= radius – 1 ||

y >= grayscale.PixelHeight – radius ||

x >= grayscale.PixelWidth – radius)

{

//maintain the original / non-smoothed

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

| (byte)intensity << 16

| (byte)intensity << 8

| (byte)intensity;

histogram[intensity]++;

if (histogram[intensity] > maxIntensity)

{

maxIntensity = histogram[intensity];

}

continue;

}

int newIntensity = 0;

//going from -radius to radius makes the

//math easier here too

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

{

for (int xoffset = -radius;

xoffset <= radius;

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 + radius),

(xoffset + radius)];

}

// scale the new intensity back

newIntensity /= filterMagnitude;

newIntensity =

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

// and now just set the color

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;

}

Now we can really smooth the image.

A Large Filter

A 21×21 filter is about as large as I can do without having the mask wrap to the next line.

int[,] filter = new int[,]

{

{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },

};

We coded it so that the edges are unfiltered. To work around this issue you can perform your average with the pixels you have available. Notice here that the large objects are still relatively unchanged, while the smaller objects have lost a substantial amount of information.

Summary

This technique is pretty easy. More important however, is that the masks can be changed easily and the effects can be seen instantly. Once again I recommend that you play around with the masks on your own. As we’ll see soon they can be used for things far more powerful than blurring an image.

Download Code

http://cid-88e82fb27d609ced.office.live.com/embedicon.aspx/Blog%20Files/PhoneVision/PhoneVision%2012%20-%20Smoothing%20Filters.zip

Up next: Sharpening Filters

Comments : 3 Comments »
Tags: Azzl Software, Azzlsoft, Blur, Computer Vision, Convolution Mask, Grayscale, Histogram, Phone Vision, RGB, Smooth, Spatial Filters, Windows Phone, WP7, WriteableBitmap
Categories : Phone Vision, Technology

Project Euler 003 – C#

15 02 2011

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Solution

using System.Collections.Generic;

using System;

namespace ProjectEulerCSharp_002

{

class Program

{

static void Main(string[] args)

{

List<long> factors = PrimeFactor(600851475143);

// this sorts the numbers in ascending order

factors.Sort();

// this reverses the list so the biggest one

// is on top.

factors.Reverse();

//show me the money

System.Console.WriteLine(factors[0]);

}

public static List<long> PrimeFactor(long number)

{

//here is our list of prime factors

List<long> factors = new List<long>();

//assume the number is prime

//unless we find a factor

bool isPrime = true;

//here is the upper limit of what we need to test

long factorCandidate = (long)Math.Sqrt(number);

while (factorCandidate > 1)

{

//is this a factor?

if (number % factorCandidate == 0)

{

//if so, what are it’s factors?

factors.AddRange(

PrimeFactor(factorCandidate));

//what about the other divisor?

factors.AddRange(

PrimeFactor(number / factorCandidate));

//we know this one isn’t prime

isPrime = false;

}

//next

factorCandidate–;

}

//we are only adding prime factors

if (isPrime) { factors.Add(number); }

//send ’em back

return factors;

}

Discussion

In contrast to my F# solution this didn’t take much longer than 5 minutes to write. I didn’t spend any time optimizing it because it ran so fast for the problem already.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Comments : Leave a Comment »
Tags: C#, Project Euler
Categories : Project Euler

Project Euler 003 – F#

14 02 2011

This has content has been moved. Please find it here:

http://eulersolutions.com/2011/05/18/project-euler-003-f/

Comments : Leave a Comment »
Tags: F#, Project Euler
Categories : Project Euler

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">

<head>

<title>Project Euler 002</title>

</head>

<body >

answer = 0;

fib0 = 1;

fib1 = 1;

fib2 = 2;

while (fib2 < 4000000)

{

answer += fib2;

fib0 = fib1 + fib2;

fib1 = fib0 + fib2;

fib2 = fib0 + fib1;

}

document.write("<b>" + answer + "</b>");

</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.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Comments : Leave a Comment »
Tags: Javascript, Project Euler
Categories : Project Euler

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[256];

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

// instead of one

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.

Download Code

http://cid-88e82fb27d609ced.office.live.com/embedicon.aspx/Blog%20Files/PhoneVision/PhoneVision%2011%20-%20Intro%20to%20Spatial%20Filters.zip

Up next: Smoothing Filters

Comments : 2 Comments »
Tags: Azzl Software, Azzlsoft, Computer Vision, Convolution Mask, Grayscale, Histogram, Phone Vision, RGB, Spatial Filters, Windows Phone, WP7, WriteableBitmap
Categories : Phone Vision, Technology

Project Euler 002–TSQL

10 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

–By considering the terms in the Fibonacci sequence\

–whose values do not exceed four million, find the

–sum of the even valued terms.

–this is a trivial query to write

select SUM(number) from Number

where number < 4000000

and isfibonacci = 1

and number % 2 = 0

Discussion

Once again, I have a large database of numbers with properties associated with them. That makes this solution fairly uninteresting.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Comments : Leave a Comment »
Tags: Project Euler, TSQL
Categories : Project Euler

Project Euler 002 – IronRuby

9 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

#By considering the terms in the Fibonacci sequence

#whose values do not exceed four million, find the

#sum of the even valued terms.

# this uses the same technique

# as the c# implementation

# I find this initialization

# syntax interesting

answer = 0

fib0, fib1, fib2 = 1, 1, 2;

while fib2 < 4000000

answer += fib2

#odd + even = odd

fib0 = fib1 + fib2;

#odd + even = odd

fib1 = fib0 + fib2;

#odd + odd = even

fib2 = fib0 + fib1;

end

puts answer

Discussion

This is obviously a port of the C# solution. The one piece I find interesting is

fib0, fib1, fib2 = 1,1,2;

Seems to be equivalent to

fib0 = 1, fib1 = 1, fib2 = 2;

For cutting and pasting large lists, the first option might be more attractive? Why not use an array in that case? I suppose I’ll learn more as I continue down the path.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Comments : Leave a Comment »
Tags: IronRuby, Project Euler
Categories : Project Euler

Project Euler 002 – C#

8 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

namespace ProjectEulerCSharp_002

{

//By considering the terms in the Fibonacci sequence

//whose values do not exceed four million, find the

//sum of the even valued terms.

class Program

{

static void Main(string[] args)

{

int answer = 0;

//typically when calculating fibonacci series

//it’s performed two elements at a time

//this is not a requirement

int fib0 = 1;

int fib1 = 1;

int fib2 = 2;

while (fib2 < 4000000)

{

//we know the fib2

//is always even

//and represents ALL

//evens in the series

//see the ‘proof’ below

answer += fib2;

//odd + even = odd

fib0 = fib1 + fib2;

//odd + even = odd

fib1 = fib0 + fib2;

//odd + odd = even

fib2 = fib0 + fib1;

}

System.Console.WriteLine(answer);

}

Discussion

As I mentioned in the F# solution, an obvious optimization is to sum as you go. I’ve also taken it a step further and removed the check for evenness because every third Fibonacci is even. I layout a rough proof in my comments above.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Comments : 2 Comments »
Tags: C#, Project Euler
Categories : Project Euler

Project Euler 003 – TSQL

Project Euler 003 – IronRuby

Phone Vision 12–Smoothing Filters

Project Euler 003 – C#

Project Euler 003 – F#

Project Euler 002 – JavaScript

Phone Vision 11–Intro to Spatial Filters

Project Euler 002–TSQL

Project Euler 002 – IronRuby

Project Euler 002 – C#

Top Posts

Archive