## Project Euler 001 – C#

1 02 2011

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Solution

namespace ProjectEulerCSharp_001

{

//Add all the natural numbers below one

//thousand that are multiples of 3 or 5.

//first, we will get all of

//the numbers divisible by 3

class Program

{

static void Main(string[] args)

{

// add the 3’s, the 5’s, and subtract one set of 15’s

for (int three = 0; three < 1000; three += 3)

for (int five = 0; five < 1000; five += 5)

for (int fifteen = 0; fifteen < 1000; fifteen += 15)

}

}

}

Discussion

If you saw the F# solution then this should be a relatively easy translation.  The main difference is that I create the sum as I’m building the list.

## Phone Vision – 09 Contrast Stretching

1 02 2011

Now that we have a histogram, it’s time to have some fun.  Michael Reichmann at Luminous Landscape uses the following picture for a great post on Understanding Histograms for digital photographers.  He graciously allowed to me to use it here and it’s perfect for what we want to accomplish.

This is a fantastic snow scene, but it would be nice if we could increase the contrast to help us pick out features.  In other words, can we ‘stretch’ the intensities to use the whole spectrum?  Of course we can!

Determining Boundaries

Which intensities do we want to become the new black and white?  You could probably eyeball it and come up with a pretty good approximation, but we’d rather automate this process whenever possible.

Let’s pick a threshold, say, 5% of the highest occurring intensity and use it to determine our lower (black) and upper (white) bounds.  If the highest occurring intensity has 100 pixels, then any intensities with fewer than 5 occurrences will be below our threshold.  Allow the code to clear up any confusion.

public Point DetermineBounds(WriteableBitmap grayscale)

{

//we will use the x value for

//the left boundary and the

//y value for right the boundary

Point bounds = new Point();

int maxIntensity = 0;

int threshold = 0;

//once again, we are determining

//the histogram

int[] histogramData = new int[256];

for (int pixelIndex = 0;

pixelIndex < grayscale.Pixels.Length;

pixelIndex++)

{

byte intensity = (byte)(grayscale.Pixels[pixelIndex] & 0xFF);

histogramData[intensity]++;

if (histogramData[intensity] > maxIntensity)

{

maxIntensity = histogramData[intensity];

}

}

// set the threshold = 5% of max

threshold = maxIntensity / 20;

//first, let’s find the left bound

//we start at one to simplify our math

//if we hit the boundary straight away

//it will be recorded as zero

//which is what we want

for (int intensity = 1;

intensity < histogramData.Length;

intensity++ )

{

//if the number of occurrences of an intensity

//is greater than our threshold then we’ve found our boundary

if (histogramData[intensity] >= threshold)

{

//the current intensity is where we

//crossed the threshold

//we need to store the previous

//intensity

bounds.X = intensity – 1;

break;

}

}

//now let’s find the right bound

//so we’ll start on the right side.

for (int intensity = histogramData.Length – 1;

intensity > 0;

intensity–)

{

//same as before

if (histogramData[intensity] >= threshold)

{

//subtract

bounds.Y = intensity + 1;

break;

}

}

return bounds;

}

And just so we can see what we’re doing, we’ll put in a method to draw the boundaries.

public void DrawBounds(Point bounds)

{

//double threshold = maxCount * .05;

Line lowIntensity = new Line();

lowIntensity.Height = HistogramPlot.Height;

lowIntensity.Width = HistogramPlot.Width;

lowIntensity.Stroke = new SolidColorBrush(Colors.Blue);

lowIntensity.StrokeThickness = 2;

lowIntensity.Y1 = 0;

lowIntensity.Y2 = HistogramPlot.Height;

lowIntensity.X1 = (bounds.X / 256.0) * HistogramPlot.Width;

lowIntensity.X2 = (bounds.X / 256.0) * HistogramPlot.Width;

Line highIntensity = new Line();

highIntensity.Height = HistogramPlot.Height;

highIntensity.Width = HistogramPlot.Width;

highIntensity.Stroke = new SolidColorBrush(Colors.Blue);

highIntensity.StrokeThickness = 2;

highIntensity.Y1 = 0;

highIntensity.Y2 = HistogramPlot.Height;

highIntensity.X1 = (bounds.Y / 256.0) * HistogramPlot.Width;

highIntensity.X2 = (bounds.Y / 256.0) * HistogramPlot.Width;

}

That looks like it accurately portrays the boundaries to me.

Shifting the Intensities

The next two steps should be combined, but it’s a little easier to understand when it’s broken into two separate components.  The first step is to make the left bound the new zero.  This means let’s shift the intensities to the dark side of the spectrum.

public WriteableBitmap ShiftLeft(WriteableBitmap grayscale, Point bounds)

{

WriteableBitmap leftShifted =

new WriteableBitmap(grayscale.PixelWidth,grayscale.PixelHeight);

int maxIntensity = 0;

int[] histogramData = new int[256];

for (int pixelIndex = 0;

pixelIndex < grayscale.Pixels.Length;

pixelIndex++)

{

byte intensity = (byte)(grayscale.Pixels[pixelIndex] & 0xFF);

//here we just subtract every intensity by the

//left boundary being careful not to let any

//negative intensities slip through

intensity = (byte)Math.Max(intensity – bounds.X, 0);

//the rest of this stuff is just fluff

leftShifted.Pixels[pixelIndex] =

255 << 24

| intensity << 16

| intensity << 8

| intensity;

histogramData[intensity]++;

if (histogramData[intensity] > maxIntensity)

{

maxIntensity = histogramData[intensity];

}

}

PlotHistogram(histogramData, maxIntensity);

return leftShifted;

}

That was easy and already I feel I can pick out more detail, but we aren’t using any more of the spectrum than we were before.

Stretching the Contrast

The final piece is to use the gamut of intensities.  Note that we are not adding information here.  We are just going to spread out the information we already have.  Let’s get to it.

public WriteableBitmap Stretch(

WriteableBitmap leftShifted,

Point bounds)

{

WriteableBitmap stretched =

new WriteableBitmap(

leftShifted.PixelWidth,

leftShifted.PixelHeight);

int maxIntensity = 0;

int[] histogramData = new int[256];

for (int pixelIndex = 0;

pixelIndex < leftShifted.Pixels.Length;

pixelIndex++)

{

byte intensity = (byte)(leftShifted.Pixels[pixelIndex] & 0xFF);

//here’s where the magic happens

//in our example, our low bound was

//184 and our high bound was 245

//we have already shifted everything left

//now we just need to spread it out

//our target range is 255 intensities,

//but our current intensity range is only

//61 (245 – 184).  So we want to scale up

//our intensities appropriately.  Our scaling

//factor becomes 255 / 61 ~ 4.18.

// 0 -> 0

// i -> i * 4.18

// 61 -> 255

// > 61 -> 255

intensity = (byte)Math.Min

(intensity * 255 / (bounds.Y – bounds.X), 255);

stretched.Pixels[pixelIndex] =

255 << 24

| intensity << 16

| intensity << 8

| intensity;

histogramData[intensity]++;

if (histogramData[intensity] > maxIntensity)

{

maxIntensity = histogramData[intensity];

}

}

PlotHistogram(histogramData, maxIntensity);

return stretched;

}

Now, that is a picture!  Notice how the histogram bars have spaces between them?  This is because we aren’t actually adding information.  We’re just making it easier to see.

Summary

I really like this picture.  It works out great for a project like this and we are finally starting to do some useful image processing.  The beauty of this lesson is that it took no human interaction to perform and the results are pretty spectacular.

If you have any questions find me on Twitter (@azzlsoft).

http://cid-88e82fb27d609ced.office.live.com/embedicon.aspx/Blog%20Files/PhoneVision/PhoneVision%2009%20-%20Contrast%20Stretching.zip

Up Next: Histogram Equalization

## Project Euler 001 – F#

1 02 2011

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

http://eulersolutions.com/2011/05/16/project-euler-001f/