| Page 4

Project Euler 005 – F#

28 02 2011

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution

2520 is the smallest number that can be

divided by each of the numbers from 1 to 10

without any remainder.

What is the smallest positive number

that is evenly divisible by all of the

numbers from 1 to 20?

(* I have put this list in the format of

2^4, 3^2, 5^1 …

let factorsWeCareAboutLessThan20 = [pown 2 4;pown 3 2;5;7;11;13;17;19]

(* multiply them all together *)

let answer = factorsWeCareAboutLessThan20

|> List.fold(fun elem acc -> elem * acc) 1

printfn "%A" answer

Discussion

This is a pretty simple problem if you know what you’re looking for. We want to find the least common multiple of (1,2,3..20).

The key observation here is that anything that is divisible by 16 (2⁴) is also divisible by 2, 4 (2²), and 8 (2³). Restating this as a question: What is the highest power of 2 we need to concern ourselves with? 2⁵ = 32 which is too big (bigger than 20). 2⁴ = 16 so that’s just right. Rinse and repeat with other primes.

Later this week we might look at a more automated approach… if you’re lucky.

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

Comments : 1 Comment »
Tags: F#, Project Euler
Categories : Project Euler

Phone Vision 14 – Sobel Operators

25 02 2011

Last time we explored how we can use the rate of change between adjacent pixels to enhance a boundary between two features in an image. Today we are going to take that one step further and isolate edges using the Sobel operators. Hold on tight…

The Sobel Operators

A search for the Sobel operators will quickly turn up these two filters:

I created a rather colorful graphic to demonstrate some of the concepts.

What do you notice? Here’s what I notice:

All of the non-edges turn black.
Diagonal edges show up in both filters.
The first filter misses horizontal edges
The second filter misses vertical edges.

The union of these two images will give you a more complete view of the edges in the system. If that’s all you wanted to know then you’re done and you can stop here.

I’m curious how they work so I’m going to dig deeper.

Gradient

When you are driving down a mountain you might see a sign (like the one to the right) indicating a steep grade. The grade in the context of a mathematical function is no different. We are trying to find the slope of the function at a given point. This is called the gradient.

Last time we looked at how fast a function was changing by subtracting adjacent intensities. If you think about it, it’s easy to imagine areas with a lot of change having a steep slope, right? So have we already found the gradient? Yes and no. Hold on, this is going to get rough.

Subtracting the adjacent intensities, we determined the slope from one pixel to the next, but we didn’t determine the slope at the pixel. Because we are dealing with discrete values (i.e. there is no ‘in-between’ pixels) the best we can hope for is an approximation of the slope at a pixel. I am hoping that an example will clear this up a bit.

Imagine the sin function represents some hilly terrain you are driving over.

It should be fairly apparent that at the top of the hill our grade is flat (slope = 0). Let’s imagine we have a GPS recording our position every so often so we get an approximation of the terrain.

Using the same technique as the last lesson, let’s try to approximate the slope at the top of the hill. Last time we said the change was f(x+1) – f(x).

Well, that’s not very good. It turns out that if we adjust our formula ever so slightly we get much better results. What if we use the position right before we got to the top of the hill instead of the position at the top?

That is a much better approximation,but what now?

Gradient Edge Detection

Let’s convert our new difference function to our filter representation.

Remember,

f(x+1) = next position (right after the top)
f(x) = current position (at the top)
f(x-1) = previous position (right before the top)

so our gradient function looks like:

-1*f(x-1) + 0* f(x) + 1*f(x+1)

Following the same process in the y direction we end up with

-1*f(y-1) + 0* f(y) +1*f(y+1)

If we apply these we end up with:

It’s a much weaker signal, but I can still spot the edges.

If these filters make sense to you then you should be able to answer the following questions:

Why are the horizontal lines still missing in the first image?
And the vertical lines still missing in the second image?
Why do the diagonals show up?

Separable Filters

You might be thinking, “um, I guess this is nice, but what does it have to do with the Sobel?” Everything.

We don’t have the tools yet to completely analyze this, but the Sobel operator is a separable filter. This means that it is a combination of two 1D filters. Sobel is a smooth filter multiplied with the gradient filter we just built.

A couple of notes:

[1,2,1] is a 1D weighted smoothing filter
This is matrix multiplication. If you need a refresher, check out the Kahn Academy video on the subject. I love that place.

and

Whoa! Mind blown.

Summary

We are starting to add some useful tools to our toolbox, but we are dancing around some really complex concepts. Over the next few lessons we will continue working with a few more simple blur, sharpen, and edge detection routines before we jump head first into frequency analysis.

Download Code

http://cid-88e82fb27d609ced.office.live.com/embedicon.aspx/Blog%20Files/PhoneVision/PhoneVision%2014%20-%20Sobel%20Operator.zip

Up Next: Median Filter

Feel free to leave a comment or follow @azzlsoft on Twitter if you have any questions.

Comments : 1 Comment »
Tags: Azzl Software, Azzlsoft, Blur, Computer Vision, Convolution Mask, Gradient, Grayscale, Histogram, Phone Vision, RGB, Sobel Operators, Spatial Filters, Windows Phone, WP7, WriteableBitmap
Categories : Phone Vision, Technology

Project Euler 004–JavaScript

25 02 2011

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

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 004</title>

</head>

<body >

function IsPalindrome(number)

{

numberStr = number.toString();

// simple palindrome test

// we only have to go through the first

// half of the letters

for (c = 0; c < numberStr.length-c; c++)

{

if (numberStr[c] !=

numberStr[numberStr.length-c-1]) {

return false;

}

return true;

}

answer = 0

//here’s a familiar loop

for(i = 100; i < 1000; i++)

{

for(j = i; j < 1000; j++)

{

product = i*j;

if ((product > answer)

&& IsPalindrome(product))

{ answer = product; }

}

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

</script>

</body>

</html>

Discussion

Nothing too special here, but this is the one solution that didn’t use some sort of built in “reverse” function. Still works. Smile

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

Comments : 2 Comments »
Tags: Javascript, Project Euler
Categories : Project Euler

Project Euler 004 – TSQL

24 02 2011

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Solution

–A palindromic number reads the same both ways.

–The largest palindrome made from the product of

–two 2-digit numbers is 9009 = 91 99.

–Find the largest palindrome made from the

–product of two 3-digit numbers.

— this is a fun query

— we join the number table to

— itself ensuring that the right

— number is greater than or equal

— to the left number

SELECT MAX(LeftNumber.number * RightNumber.number)

FROM Number LeftNumber

INNER JOIN Number RightNumber

ON LeftNumber.number <= RightNumber.number

— then we limit the numbers to 3 digits

— an obvious (and better) method for this is

— LeftNumber.number >= 100

— and LeftNumber.number <= 999

— but this technique is more interesting

WHERE LEN(CAST(LeftNumber.number AS VARCHAR)) = 3

and LEN(CAST(RightNumber.number AS VARCHAR)) = 3

— finally, the clever part is determining

— the palindromicity of the product

and(CAST(LeftNumber.number * RightNumber.number AS VARCHAR)

= REVERSE(CAST(LeftNumber.number * RightNumber.number AS VARCHAR)))

Discussion

I am quite happy with this solution.

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 004 – IronRuby

23 02 2011

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Solution

# A palindromic number reads the same both ways.

# The largest palindrome made from the product of

# two 2-digit numbers is 9009 = 91 99.

# Find the largest palindrome made from the

# product of two 3-digit numbers.

# placeholder

answer = 0;

#loop through each 3-digit number

for i in 100..999 do

for j in i..999 do

product = i*j

# the palindrome test is simple here

# since we are using the same technique

# as the F# and C# functions

if product.to_s().reverse == product.to_s() &&

answer < product

answer = product

end

puts answer

Discussion

I have to admit, Ruby makes this code pretty simple.

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 004 – C#

22 02 2011

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Solution

using System.Collections.Generic;

//A palindromic number reads the same both ways.

//The largest palindrome made from the product of

//two 2-digit numbers is 9009 = 91 99.

//Find the largest palindrome made from the

//product of two 3-digit numbers.

namespace ProjectEulerCSharp_004

{

class Program

{

static void Main(string[] args)

{

//simple placeholder for our

//biggest palindrome

int maxPalindrome = 0;

//loop through each 3-digit number

for (int i = 100; i < 1000; i++)

{

//this is a slight optimization

//over our F# solution because

// 100 * 101 = 101 * 100 so we

// don’t need to perform the second

// multiplication

for (int j = i; j < 1000; j++)

{

int product = i * j;

//used an extension method to test for

//palindromicity (is that a word)

if (product.IsPalindrome()

&& product > maxPalindrome)

{

maxPalindrome = product;

}

System.Console.WriteLine(maxPalindrome);

}

// extension methods are awesome

public static class Extensions

{

// here we create a function called

// IsPalindrome that uses the same

// technique as the F# function

public static bool IsPalindrome(this int i)

{

// get a convenient list of chars

List<char> chars =

new List<char>(i.ToString().ToCharArray());

// reverse them

chars.Reverse();

// are we a palindrome?

return i == int.Parse(new string(chars.ToArray()));

}

Discussion

My favorite part of this solution is the use of the extension method. Why don’t we use those all the time? Of course, the generic List structure offers some helpful routines 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: C#, Project Euler
Categories : Project Euler

Project Euler 004 – F#

21 02 2011

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

http://eulersolutions.com/2011/05/19/project-euler-004-f/

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

Phone Vision – 13 Sharpening Filters

21 02 2011

Smoothing an image was pretty intuitive. When we are smoothing an image we are actually trying to suppress details in the image. When we sharpen an image we are trying to do the opposite. So, how do we do that?

Rates of Change

When we are sharpening an image we are trying to enhance the differences. What are the differences? Well, let’s take a look at a 1D strip of intensities:

If we take a cursory look at these pixels we’ll see that the intensities gradually decrease from left to right before jumping back up dramatically then dropping back down. The dramatic ‘jumps’ are what will ultimately be enhanced when we sharpen the image. Here they are highlighted.

We want to know how fast the intensities are changing. If ∆ represents the rate of change between adjacent pixels then our rate of change looks like:

We just subtract the value of the next pixel from the value of the current pixel. A little more formally, this looks like

∆(x) = f(x+1) – f(x)

Under normal conditions, some natural variation will occur pixel by pixel. We want to ignore that natural variation and only concern ourselves when the change is drastic. For that we will have to perform the subtraction one more time.

Now we can see how fast each intensity is changing. Once again, let’s formalize this.

∆²(x) =∆(x+1) – ∆(x)

∆²(x) = (f(x+1) – f(x)) – (f(x) – f(x-1)

∆²(x) = f(x-1) – 2 * f(x) + f(x+1)

Implementing the 1D Case

Then the filter for our 1D case looks like

If we apply this to our image we end up with this from above:

If we subtract this from our original image something magical happens:

We have sharpened the image!

In order to achieve that result, we subtracted ∆² from the original image f. Our new formula looks like:

sharp = f – ∆²

so in the x direction,

sharp(x) = f(x) – ∆²(x)

sharp(x) = f(x) – (f(x-1) – 2 * f(x) + f(x+1))

sharp(x) = f(x) + -f(x-1) + 2 * f(x) – f(x+1)

sharp(x) = –f(x-1) + 3*f(x) – f(x+1)

Hence, our final 1D filter:

Expanding to 2D

If all images were just a single strip of pixels we’d be done. Unfortunately they aren’t, but accounting this is a pretty simple adjustment. The first thing to notice is that the 1D case works in any direction. If we wanted to apply the filter vertically instead of horizontally it would look like this:

So, how do we expand this to two dimensions? It’s pretty easy, actually:

Now you have a sharpening filter that will work in two dimensions. If you want to include the diagonals, there is no reason you can’t. Using the exact same method the final sharpening filter becomes:

And we’re done!

Summary

With some luck, you will have a solid grasp of how the sharpening filter works. If you are interested in researching this topic more, we walked through creating the Laplacian operator. If you are comfortable with calculus, the difference functions we discussed were actually just the first derivative (∆)and the second derivative (∆²).

Having discussed the filter code at length, the code is not posted here. The code from previous lessons will work fantastically.

Up Next: Sobel Operators

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

Project Euler 003 – JavaScript

18 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

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

<head>

<title>Project Euler 003</title>

</head>

<body >

function PrimeFactor(number)

{

//here is our list of prime factors

factors = new Array();

//assume the number is prime

//unless we find a factor

isPrime = true;

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

factorCandidate = Math.round(Math.sqrt(number), 0);

while (factorCandidate > 1)

{

//is this a factor?

if (number % factorCandidate == 0)

{

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

divisor = number / factorCandidate;

factors.concat(PrimeFactor(factorCandidate));

factors.concat(PrimeFactor(divisor));

isPrime = false;

}

//next

factorCandidate–;

}

//we are only adding prime factors

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

return factors;

}

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();

answer = factors[0];

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

</script>

</body>

</html>

Discussion

Debugging JavaScript is not my forte. The concat function was handy here, but I don’t think that JavaScript is going to get much better for me unless I spend some time getting better tools.

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

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 005 – F#

Phone Vision 14 – Sobel Operators

Project Euler 004–JavaScript

Project Euler 004 – TSQL

Project Euler 004 – IronRuby

Project Euler 004 – C#

Project Euler 004 – F#

Phone Vision – 13 Sharpening Filters

Project Euler 003 – JavaScript

Project Euler 003 – TSQL

Top Posts

Archive