All 11 entries tagged Project

View all 101 entries tagged Project on Warwick Blogs | View entries tagged Project at Technorati | View all 8 images tagged Project

November 21, 2006

Single point best fit

A while ago I implemented a basic linear regression algorithm to calculate the line of best fit through a set of points. For this stage in prototyping I needed to see what the best fit line looked like at different places on a test image. The “get valid points in circle” function from before is used to get the set of pixels to work with.
An initial use of my regression function highlighted a glaring problem. A set points forming a near vertical “bar” will produce a regression line almost orthogonal to them! This is because a normal linear regression minimizes the Y-error only. (The assumption is that X values are accurate and Y values are experimental results.)
However, I needed both X and Y errors minimized. I did some quick research and it is possible to perform a “perpendicular” regression. This minimizes the perpendicular distance of points to the line.
However, in the interests of getting something working fast, I decided to calculate two regular regression lines. The first as before, the second with X and Y values interchanged. These two lines represent possible best fits. To find the best I calculate the sums of perpendicular distances to each line from every point; taking the smallest sum as best.

Now that I’ve actually written all that down, maybe doing a “perpendicular regression” would be cleaner! (http://www.mathpages.com/home/kmath110.htm has a good description of the process.) For now though the code does produce good looking lines on top of my test image.

Here is the code (omitting the using statements and GetColoredPointsInCircle function from before).

def DistanceBetween(pt : Point, gradient : double, intercept : double)
    def orthogGradient = -1 / gradient

    if (double.IsInfinity(gradient))
        Abs(pt.X - intercept)
    else if (double.IsInfinity(orthogGradient))
        Abs(pt.Y - intercept)
    else
        def orthogIntercept = pt.Y - orthogGradient * pt.X

        def a = gradient
        def b = 1
        def c = orthogGradient
        def d = 1
        def detInv = 1 / (a * d - b * c)
        def aInv = detInv * d
        def bInv = detInv * -b
        def cInv = detInv * -c
        def dInv = detInv * a

        def x = aInv * intercept + bInv * orthogIntercept
        def y = cInv * intercept + dInv * orthogIntercept

        def xDiff = x + pt.X
        def yDiff = y - pt.Y
        Sqrt(xDiff * xDiff + yDiff * yDiff)

def GetLine(points : list[Point]) : (double * int * int)
    def SumWith(f) { points.Map(f).FoldLeft(0, (x,y) => x + y) }

    def xSum : long = SumWith(pt => pt.X)
    def ySum : long = SumWith(pt => pt.Y)
    def xySum : long = SumWith(pt => pt.X * pt.Y)
    def xxSum : long = SumWith(pt => pt.X * pt.X)
    def yySum : long = SumWith(pt => pt.Y * pt.Y)

    def oX = (xSum / points.Length) :> int
    def oY = (ySum / points.Length) :> int

    def denomX : double = (xSum * xSum - points.Length * xxSum)
    def denomY : double = (ySum * ySum - points.Length * yySum)

    def useX = (denomX < -double.Epsilon || double.Epsilon < denomX)
    def useY = (denomY < -double.Epsilon || double.Epsilon < denomY)

    if (useX && useY)
        def gradientX = (xSum * ySum - points.Length * xySum) / denomX
        def interceptX = (xSum * xySum - ySum * xxSum) / denomX
        def gradientY = 1 / ((ySum * xSum - points.Length * xySum) / denomY)
        def interceptY = \
            if(double.IsInfinity(gradientY)) \
                xSum / (points.Length :> double) \
            else \
                -gradientY * (ySum * xySum - xSum * yySum) / denomY

        def countX = points.FoldLeft(0.0, (pt,a) => a + DistanceBetween(pt, gradientX, interceptX))
        def countY = points.FoldLeft(0.0, (pt,a) => a + DistanceBetween(pt, gradientY, interceptY))

        if (countX < countY)
            (gradientX, oX, oY)
        else
            (gradientY, oX, oY)
    else if (useX)
        ((xSum * ySum - points.Length * xySum) / denomX, oX, oY)
    else // useY
        ((ySum * xSum - points.Length * xySum) / denomY, oX, oY)

def f = Form()
def bmp = Bitmap("line.png")

f.Paint += fun(_, e)
    e.Graphics.DrawImage(bmp, 0,0)

f.MouseUp += fun(_, e)
    try
        def radius = 10
        def points = GetColoredPointsInCircle(bmp, Point(e.X, e.Y), radius, Color.Black)
        def (gradient, oX, oY) = GetLine(points)
        using (g = f.CreateGraphics())
            def angle = Atan(gradient)
            def x0 = (0.5 + Cos(angle) * radius + oX) :> int
            def x1 = (0.5 + Cos(angle + PI) * radius + oX) :> int
            def y0 = (0.5 + Sin(angle) * radius + oY) :> int
            def y1 = (0.5 + Sin(angle + PI) * radius + oY) :> int
            g.DrawLine(Pens.Yellow, x0, y0, x1, y1)
    catch
        | ex => Console.WriteLine(ex.ToString())

Application.Run(f)

The amount of special case handling of vertical lines (infinite gradients) does look ugly. That is definately something to look at refactoring later.

Here is an example of the output when clicking on the image in a few places:
Best Fit Demo

It looks pretty good! The only problem to note is when we are inside a huge mass of points (viz. top right of image). Here there is no way to correctly identify a line. In this special case we would probably just continue forward on our current heading.

The next step is to join up these line segments somehow…


Points In Circle

I need to get all valid coloured pixels within a given radius of an origin point. The follow code creates a Form with an image. When clicking the image, all black pixels within a 10 pixel radius of the clicked pixel are coloured red.
Special care is taken not to go off the edge of the image (note the Max and Min function calls).

using System
using System.Drawing
using System.Math
using System.Windows.Forms

def GetColoredPointsInCircle(bmp : Bitmap, origin : Point, radius : int, color : Color) : list[Point]
    def xLine = $[Max(0, origin.X - radius) .. Min(bmp.Width - 1, origin.X + radius)]
    def yLine = $[Max(0, origin.Y - radius) .. Min(bmp.Height - 1, origin.Y + radius)]
    def r2 = radius * radius
    def InCircle(x, y)
        def dX = x - origin.X
        def dY = y - origin.Y
        (dX * dX + dY * dY) < r2

    def CorrectColorAt(x, y)
        bmp.GetPixel(x, y).ToArgb() == color.ToArgb()

    $[ Point(x, y) | x in xLine, y in yLine, InCircle(x,y) && CorrectColorAt(x,y)]

def f = Form()
def bmp = Bitmap("line.png")

f.Paint += fun(_, e)
    e.Graphics.DrawImage(bmp, 0,0)

f.MouseUp += fun(_, e)
    def pts = GetColoredPointsInCircle(bmp, Point(e.X, e.Y), 10, Color.Black)
    using (g = f.CreateGraphics())
        foreach (pt in pts)
            g.FillRectangle(Brushes.Red, pt.X, pt.Y, 1, 1)

Application.Run(f)

This allows me to visually check that the right pixels would be used when performing a linear regression to approximate the line. The size of the radius, 10 pixels, is arbitrary at the moment. It reflects the width of the line drawn in the image.
Also the choice of using ”<” and not ”<=” to check if a point is in the circle is arbitrary for now.

P.S.
Check out the awesome list comprehensions Nemerle lets me do!


Getting Back On Track

The project’s progress has somewhat stalled over the past few weeks. I’ve been too busy with work outside of university. Rather than get bogged down panicking about timetables, phases and other management issues, I decided the most productive thing to do is code. Just get something concrete working! A fair amount of my project is about discovering algorithms and refining them. So instead of pretending that I spent hours writing pseudo-code and defining all the mathematics needed, I am using the most expressive medium I know: code!
My current objective is to build a simple line vectorizer. I am building up the code in a very iterative fashion by writing very simple prototypes. These are most often consecutive; the next prototype copies code from the previous.
I think it will be useful to document the evolution of these prototypes so that at the end I know the design decisions I made along the way. So the plan is to dump each prototype in a blog post and jot down some notes about it.


November 16, 2006

VM Crash

I fired up my project’s Virtual PC image only to have it start reporting weird memory errors. I restarted the OS, but then it would not boot into windows. I was seeing a brief blue screen error. So I mounted my Windows ISO image and ran “chkdsk /r”. It seemed to fix some errors. I also ran fixboot.
Still the OS would not boot (some error reading the registry now). I ran chkdsk on the host OS just in case – no errors were found.
I then tried an in-place install of Windows… still wouldn’t boot.

DAMN.

I decided to cut my losses. I launched a different Virtual PC with the broken PCs hard drive attached as secondary. I was then able to copy all the important files.
Now I’m going to re-install Windows from scratch… so much for a productive day!


November 01, 2006

Nemerle, NUnit and custom operators

Nemerle allows the definition of new operators. I always feel annoyed having to write code like “Assert.AreEqual(42, myVal)” when unit testing with NUnit.

So I created this operator for use in my project’s test library:

namespace Equin.Vectorization.Library.Tests
    module Utilities
        public static @=!=[T](x : T, y : T) : void
            Assert.AreEqual(x, y)

Now in my test cases I can use it like this:

[Test] public PixelAtTopLeft() : void
    using (bmp = CreateBitmap(Size(10, 10), [Pt(0,0)]))
        def ps = PixelSelector(bmp, Color.Black)
        def pixels = ps.GetPixels()

        mutable count = 0
        mutable aPoint : Pt[int] = null
        foreach (pt in pixels)
            count++
            aPoint = pt

        1 =!= count
        0 =!= aPoint.X
        0 =!= aPoint.Y

It’s just sugar, I know, but it makes the assertions really jump out at me. It’s less to type as well :)
I could even make it a macro instead of a method call, that would then let me create a pretty message string as well…


October 27, 2006

Mono + Nemerle on Linux

Today I managed to get Mono installed on my DCS account. I had failed to compile and install from source before, so used the pre-compiled binary installed this time. It works like a charm – as easy as installing something on Windows! :)

Then I installed Nemerle – also easy. So will now be able to compile and run my project at university. This will be useful for demoing, etc.

I’ve not tested the Windows Forms support yet. Ideally I can create a UI capable of running under Windows and Linux with no recompiling…


October 25, 2006

Setting Up Code in VS

I created a Visual Studio solution that will hold all the code for the project. It will eventually contain:
  • Library – The code that has all the algorithms and data structures
  • Tests – NUnit test suites for the library
  • UI – Windows Form application to demo the library

Today I added Library and Tests projects to the solution. These are both Nemerle Class Library projects. I refactored yesterday’s experimental linear regression code into the library project to get the ball rolling.

The project root directory looks like this at the moment:

+ src
| + Equin.Vectorization.Library
  | - Equin.Vectorization.Library.nproj
  | - (various .n files)
| + Equin.Vectorization.Library.Tests
  | - Equin.Vectorization.Library.Tests.nproj
  | - Equin.Vectorization.Library.Tests.nunit
  | - (various .n files)
| - Equin.Vectorization.sln

A set of tests were also written to exercise the BestFit function.

Here is a sample of the testing code:

#pragma indent
using System
using NUnit.Framework
using Equin.Vectorization.Library

namespace Equin.Vectorization.Library.Tests
    [TestFixture] public class BestFit

        [Test] public Diagonal_Points() : void
            def points = [Point(0,0), Point(1,1), Point(2,2)]
            def line = points.BestFit()
            match (line)
                | Line.Normal(g, i) =>
                    Assert.AreEqual(1f, g)
                    Assert.AreEqual(0f, i)
                | _ => Assert.Fail("Line should have been Normal.")

Once compiled, the Tests assembly was opened in the NUnit test runner GUI. I may get a test runner for Visual Studio installed, so I don’t have to leave the IDE.

Having got the BestFit function working with the tests, I imported the solution into SubVersion (svn server runs on a separate machine downstairs). I then did the slightly annoying “rename old folder, create new folder, svn export” dance :) So I now have a solid project tree to work under.

I will need to setup a batch backup system soon to copy the repository to a university server. Maybe I’ll even get fancy continuous integration tool running to perform nightly builds, etc!


October 24, 2006

Linear Regression

I’ve made a start on Phase 1 of the project.
One of the goals of this phase is to get Nemerle up and running. As a warm up I implemented a linear regression algorithm. The idea being given a list of points, calculate the line of best fit.

First some basic type definitions:

[Record] class Point
    [Accessor] _x : float
    [Accessor] _y : float

[Record] variant Line
    | Normal
        [Accessor] _gradient : float
        [Accessor] _yIntercept : float
    | Vertical
        [Accessor] _xIntercept : float

These types use the Record macro to generate constructors that assign the fields in the order defined. For example, Point(10,20) .
The Accessor macro generates public property getters for the fields, so that they are externally visible. For example, pt.X + pt.Y .

A line is usually defined by a gradient and y-intercept. However, a vertical line has an infinite gradient and no y-intercept. Therefore the Line type is a variant capturing these two cases.

The best-fit function is defined as:

BestFitLine(points : list[Point]) : Line
    def SumWith(f) { points.Map(f).FoldLeft(0f, (x,y) => x + y) }

    def xSum = SumWith(pt => pt.X)
    def ySum = SumWith(pt => pt.Y)
    def xySum = SumWith(pt => pt.X * pt.Y)
    def xxSum = SumWith(pt => pt.X * pt.X)

    def denom = (xSum * xSum - points.Length * xxSum)
    if (denom >= -float.Epsilon && denom <= float.Epsilon)
        Line.Vertical(xSum / points.Length)
    else
        def gradient = (xSum * ySum - points.Length * xySum) / denom
        def intercept = (xSum * xySum - ySum * xxSum) / denom

        Line.Normal(gradient, intercept)

Nemerle language features to note here are:
  • Local functions – e.g. SumWith that projects a list of points using a function f, and then sums the values.
  • Lambda functions – e.g. pt => pt.X is a function from a Point to its X value.
  • Type inference – Nemerle is statically typed, so type inference is a great time saver.
  • Indentation sensistive block constructs as an optional alternative to braces and semi-colons.

The function can be used like this:

def points = [Point(1,10), Point(2,5), Point(3,9), Point(4,4)]
def line = BestFitLine(points)

match (line)
    | Line.Normal(g, i) =>
        WriteLine($"Gradient $g")
        WriteLine($"Intercept $i")
    | Line.Vertical(x) => WriteLine($"Vertical @ X = $x")

The match block is a powerful pattern matching construct, ideal for breaking apart variant types.
The $ macro is for splicing expressions into strings.

I am very pleased with Nemerle as a language so far. It’s functional features make algorithms succinct. The object oriented features will make building a large project managable and easy to use from other .NET projects.

The Visual Studio integration is not perfect yet. However, intellisense and the debugger will be very useful during development.


October 18, 2006

Project Specification

I have completed my initial project specification. This is meant to be a working document that evolves with the project.

The current version (0.1.1) is online www.equin.co.uk/uni/project/Specification-0.1.1.pdf

I will be handing it in tomorrow.


October 07, 2006

Nemerle VSIP

I am planning to write my project’s code using Nemerle . It has a good cross section of language features that I will leverage. The concentration on efficient algorithms and data structures will leverage the functional aspects of Nemerle. Whilst the vast .NET libraries and imperative constructs will make image handling and UI code easy.

Of course, being a Visual Studio junkie means I will require decent tool support. Luckily I managed to get the Nemerle VSIP (Visual Studio Integration Package) to work yesterday. Now I can edit code inside Visual Studio with the aid of intellisense, syntax highlighting and built-in compiler support.
The package is still somewhat under development, so I’m not sure how stable it will be. My project will not require too much code so I think it will hold up OK. To be honest, just having a Visual Studio “project” to manage building source, etc is a God send compared to manually writing build scripts and command line compiling!

I’m looking forward to getting this project off the ground. My current goal is writing the proposal document by week 3…


Google Ads

Search this blog

Most recent comments

  • I scratched my eye while i was holding some kind of plastic packaging.. Anyways the corner of the pl… by Ercan on this entry
  • About a year ago my contacts that i was wearing, i guess were fautly, because shortly after they wer… by Jon on this entry
  • I got shower gel in my eye 4 and a half days ago, and becasue i rubbed my eyes a lot, i have scratch… by Chris on this entry
  • This website may help http://www.webmd.com/eye–health/tc/Eye–Injuries–Home–Treatment by S on this entry
  • I somehow got dirt, or debris in my eye. The terrible pain sent me in a tailspin. I was afraid of sa… by Bobbi on this entry

Tags

September 2021

Mo Tu We Th Fr Sa Su
Aug |  Today  |
      1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30         

Galleries

Blog archive

Loading…
RSS2.0 Atom
Not signed in
Sign in

Powered by BlogBuilder
© MMXXI