February 23, 2007

Junction Detection

Recently I have been focusing on detection of junctions and end points on a raster network. It is suprisingly difficult, but I have something that works nicely on test images.
Junctions Sample
The parameters the algorithm uses seem to be quite sensitive at the moment, this mainly due to the point grouping function. I need to come up with a more stable point grouper…

However, with the junction detector working vectorising a network is simple a case of line following out of one junction until reaching another!


February 07, 2007

Installing ClickOnce application as non–admin user

Insight shipped a while ago. It is deployed as a ClickOnce application. The bootstrap setup.exe created by the .NET SDK is excellent in that it detects missing pre-requisites on a user’s machine, downloads and installs them.
The problem is that a non-admin user will not be able to install components such as the .NET Framework, Microsoft Reporting Library, etc.
“Right-click, RunAs admin” on the setup.exe works except that the Start Menu entry for the application is put in the Administrator’s start menu and home directory. This means the user has to run Setup.exe again as themself! Argh, imagine the support calls on that one…

My solution is to make a ZIP file containing setup.exe, Install.bat and part2.bat.
Install.bat contains:

@echo off
set _User_=%USERDOMAIN%%USERNAME%
set _wd_=%CD%

echo Installing Insight for %_User_%.
runas /u:%COMPUTERNAME%\Administrator "cmd.exe /c CD \"%_wd_%\" && part2.bat \"%_User_%\" \"%_wd_%\""

which upon running prompts:

Installing Insight for WORK\Andrew Davey.
Enter the password for WORK\Administrator: 

The user types the admin password, hits enter. That runs part2.bat:

@echo off
echo Giving %1 temporary Administrator status
net localgroup Administrators %1 /ADD
echo Running Insight install program
runas /u:%1 "cmd.exe /c CD %CD% && setup.exe" 
echo Removing %1's Administrator status
net localgroup Administrators %1 /DELETE

That adds the user to the Administrator group, then runs setup.exe as the user (but now with admin permissions). Afterwards, the user is removed from the Administrator group.

I took the idea from the MakeMeAdmin.cmd batch file. I could not seem to pass the current directory using MakeMeAdmin, so it could not find setup.exe. That’s why I have two batch files.
Maybe someone can point out how it should be done.

So the result is I can tell someone to download the ZIP, extract and double-click Install.bat. Whilst that’s not exactly “ClickOnce” anymore, it slightly better than the alternative! Of course once installed, any later application updates go into the user’s directory so no admin permissions are required.
I hope Microsoft update the bootstrapper in the next version so that it can handle non-admin users better.


February 02, 2007

Problems focusing

How come the best projects always come along at the busiest times? My mate Alex came to visit last weekend and we got talking about a great project. I don’t want to say too much here in case some sneaky bright-spark implements it before us! The project has great potential and really motivated me to get cracking on a prototype. This is the kind of motivation that makes me work until 3am without even realising!
Of course the problem with all this is that I should be working on my 3rd year uni project right now. In addition, I need to prepare for travelling back the Cornwall on the 8th to sell my primary school assessment tracking app “Insight”. I really should be doing reading for my various uni modules as well. I actually turned down some contract work with a regular client because I’m just too busy. I could have really done with the money too.
Uni is seeming less relevant every day. I have to stick it out, don’t I? My plan for when I finish is to start my own software company. I already have one great product, Insight, and this new project with Alex stands to be an awesome success as well. I guess a few more months won’t seem like a big deal in retrospect, but right now it feels like I’m wasting precious time that would better spent developing my company.
Maybe I should find out the university’s policy on defering my final year…
Heh, isn’t the world richest man a college drop out? ;)


January 17, 2007

Network Vectorization

My recent development efforts have focused on vectorizing networks (either graphs or trees). These structures often appear on maps as rivers and roads that branch out. This is a more general problem than simply capturing a single line. However the approach required to vectorize is in some ways simpler.

My algorithm so far is:
  1. Create “waypoints” on the network by repeatedly getting pixels with the most surrounding pixels withing a given radius. These are rough approximations to the center line that should be followed.
    Waypoints on a network
  2. Calculate best-fit lines at each waypoint (images scaled 2x)
    Best-fit lines on a network
  3. For each line-segment, check for intersections with the other lines. These intersections are the nodes of the polylines representing the network.

I am yet to create step 3. The algorithm will need some reasonable smarts to handle junctions well. I imagine something like “if a line-segment has more than two intersections, those intersection are junctions terminals”.

The primary limitation of the algorithm is the reliance on a fixed line width that manifests as a “radius” parameter used to determine nearby pixels. An improvement will be to calculate the line width at each pixel. I think this can be done by repeatedly increasing the radius until doing so actually reduces the amount of valid pixels captured. A negative weight is assigned to invalid pixels. The amount of negative weight really depends on how sensitive to noise the algorithm needs to be.


Thoughts so far

I didn’t get any work done on my project over Christmas. Things were just too busy. However, I did finish my last piece of external work. So I am now free to concentrate fully on university… (in theory!)

I am painly aware of the lack of reading done so far. I keep trying to find relevant papers, but whenever something good turns up I can’t get the damn content! I’m so sick of only reading great sounding abstracts. The library seems to be totally lacking the resources I need. I’m not sure where my tution fees are going!

I discussed this problem with my supervisor, who suggested emailling authors directly. Hopefully this will return some useful material.

My supervisor pointed out that vectorising raster images is a hard problem and told me not to expect great results in the short time available. Lots of work has been done in the area (though I can’t get the damn papers!). I have had lots of ideas myself, but I got the impression I should just be implementing existing ideas and reporting the results… sigh.


November 29, 2006

Point Grouping

Another part of my project is vectorising point objects on an image. The code for this is fairly simple, but I think I may want to re-use it to improve the line follower.
Points on Line

I am thinking about using the closest “point” as a hint to the next heading to take when following a line.


November 23, 2006

Line Follower

My initial line follower is working! It was tricky working out which end of a line segment, created by best fitting points, to follow each time. The code is still not perfect since tight hair-pin corners confuse it. The main assumption is that a line only changes direction gradually. So the line follower always try to continue in a direction close to the previous heading.
Here is a sample of a vectorized line (shown in red):
bestfit001

To improve performance when turning sharp corners I think the algorithm needs to be able to look at the image at different levels. Perhaps it can start with a small radius to capture points and grow it a few times to get a sample of possible headings. This would probably require the erasure of “used” points from the image.

In fact maintaining multiple possible paths could make the algorithm more adaptive. This would make junction handling easy. Both routes are taken, only one has to succeed.

Here is the NextSegment function so far:

        public NextSegment (prevPoint : Point, prevLine : Line) : (Point * Point * Line)
            def points = GetColoredPointsInCircle(prevPoint)
            def (centroid, angle) = BestFit(points)

            def rCosA = Cos(angle) * _radius
            def rSinA = Sin(angle) * _radius
            def startPoint = Point(centroid.X - rCosA, centroid.Y - rSinA)
            def endPoint = Point(centroid.X + rCosA, centroid.Y + rSinA)
            def line = Line(startPoint, endPoint)

            def betterStartPoint = match (line.Intersect(prevLine))
                | Line.Intersection.Point (pt) =>
                    if (PointInLineSegment(pt, startPoint, endPoint))
                        pt    
                    else
                        prevPoint
                | Line.Intersection.Parallel =>
                    prevPoint
                | Line.Intersection.Coincident =>
                    prevPoint

            def (next,l) = if (Abs(prevLine.AngleTo(line)) > PI/2)
                (startPoint, Line(line.Point2, line.Point1))
            else
                (endPoint, line)

            _finished =  (next.DistanceTo(_end) < _radius)
            (betterStartPoint, next, l)

The code to choose the correct next point on the polyline is a bit of hack. Basically it has to flip the best fit “line” as well to ensure the heading is maintained. This block will be changed in future versions to include the multiple branching.


Line–Line Intersection

I decided to represent lines as two distinct points. Two lines can either:
  1. Intersect at a single point
  2. Be coincident (i.e. identical)
  3. Be parallel

I created an Intersection function on my Line type. It takes another Line and returns an Intersection value. “Intersection” is a union type representing the above three cases.

Here’s the code:

#pragma indent

using System
using System.Console
using System.Math
using Nemerle.Utility

namespace Prototype

    static class DoubleExtensions
        public static IsTiny(this d : double) : bool
            -double.Epsilon < d && d < double.Epsilon

    [Record] struct Point
        [Accessor] _x : double
        [Accessor] _y : double

        public override ToString () : string
            $"($_x, $_y)" 

        public static @:( pt : int * int ) : Point
            | (x,y) => Point(x,y)

        public static @:( pt : double * double ) : Point
            | (x,y) => Point(x,y)

    [Record] struct Line
        [Accessor] _point1 : Point
        [Accessor] _point2 : Point

        public Intersect (other : Line) : Intersection
            def Det (a,b,c,d)
                a * d - b * c

            def (x1,x2,x3,x4) = (Point1.X, Point2.X, other.Point1.X, other.Point2.X)
            def (y1,y2,y3,y4) = (Point1.Y, Point2.Y, other.Point1.Y, other.Point2.Y)

            def d1 = Det(x1, y1, x2, y2)
            def d2 = Det(x3, y3, x4, y4)
            def denom = Det(x1 - x2, y1 - y2, x3 - x4, y3 - y4)

            if (denom.IsTiny())
                def x = Det(d1, x1 - x2, d2, x3 - x4)
                def y = Det(d1, y1 - y2, d2, y3 - y4)
                if (x.IsTiny() && y.IsTiny())
                    Intersection.Coincident()
                else
                    Intersection.Parallel()
            else
                def x = Det(d1, x1 - x2, d2, x3 - x4) / denom
                def y = Det(d1, y1 - y2, d2, y3 - y4) / denom
                Intersection.Point(Point(x,y))

        public variant Intersection
            | Parallel
            | Coincident
            | Point
                pt : Prototype.Point

using Prototype
def l1 = Line((1,1), (10,10))
def l2 = Line((0,1), (12,13))
def l3 = Line((5,1), (1,5))
def l4 = Line((0,0), (12,12))

def foos = [l1.Intersect(l2), l1.Intersect(l3), l1.Intersect(l4)]

foreach (i in foos)
    | Line.Intersection.Point(pt) => WriteLine($"Point $pt")
    | Line.Intersection.Coincident => WriteLine("Coincident")
    | Line.Intersection.Parallel => WriteLine("Parallel")

P.S.
Some Nemerle gems:
1) Implicit cast from (int * int) to Point. This lets me use (1,3) in place of Point(1,3) – cuts down on the visual noise when building up lists of points!
2) match inside foreach

foreach (x in xs)
  | Foo => ...
  | Bar => ...

very cool!!


November 22, 2006

Line representation

What is the most sensible representation of a line? There are a few possibilities including:
  • Gradient and intercept: (y=mx+c)
  • Two distinct points: (x1,y1) & (x2, y2)
  • r = x cos(a) + y sin(a) : r = the perpendicular distance to the line. a = the angle r makes with the x-axis.

I suppose the actual operations I need to perform on lines should dictate the best represention to ease calculations. Using gradients gets tricky when dealing with vertical lines. Angles are preferable since they range between -Pi/2 and Pi/2.

The line following algorithm relies on calculating the intersection of lines. It produces start and end points of line segments. Therefore representing lines as two distinct points may be the best approach. Calculating the intersection of two lines represented this way is described here


Better Best Fit

As part of my code tidy up I have been thinking again about fitting a line to a set of points.
The new code uses the method described here

#pragma indent

using System
using System.Console
using System.Math
using System.Windows.Forms
using Nemerle.Utility
using Nemerle.Assertions

[Record] struct Point
    [Accessor] _x : double
    [Accessor] _y : double

    public this (x : int, y : int)
        _x = x
        _y = y

    public Offset (x : double, y : double) : Point
        Point(_x + x, _y + y)

    public override ToString () : string
        $"($_x, $_y)" 

module ListPointExts
    private static Sum[T] (items : list[T], f : T -> double) : double
        items.FoldLeft(0.0, (pt, a) => f(pt) + a)

    private static Centroid (points : list[Point]) : Point \
        requires points.Length > 0
        Point(Sum(points, pt => pt.X) / points.Length, Sum(points, pt => pt.Y) / points.Length)

    public static BestFit (this points : list[Point]) : (Point * double)
        def centroid = Centroid(points)
        def pts = points.Map(pt => pt.Offset(-centroid.X, -centroid.Y))

        def xySum = Sum(pts, pt => pt.X * pt.Y)
        def x2_y2Sum = Sum(pts, pt => pt.X * pt.X - pt.Y * pt.Y)

        if (-double.Epsilon < xySum && xySum < double.Epsilon)
            if (-double.Epsilon < x2_y2Sum && x2_y2Sum < double.Epsilon)
                // Points all evenly spaced around centroid
                // HACK: Return horizontal line for now
                (centroid, 0.0)
            else if (x2_y2Sum < 0)
                // Points lie on vertical line
                (centroid, PI / 2)
            else
                // Points lie on horizontal line
                (centroid, 0.0)
        else
            def b = x2_y2Sum / xySum
            def a1 = Atan( (-b + Sqrt(b*b + 4)) / 2 )
            def a2 = Atan( (-b - Sqrt(b*b + 4)) / 2 )

            def SumDistances(a)        
                def cos_a = Cos(a)
                def sin_a = Sin(a)
                def RotateY2(pt)
                    def y = (-pt.X * sin_a) + (pt.Y * cos_a)
                    y * y
                Sum(pts, RotateY2)

            if (SumDistances(a1) < SumDistances(a2))
                (centroid, a1)
            else
                (centroid, a2)

def f = Form()
mutable pts : list[Point] = []

f.MouseUp += fun (_,e)
    if (e.Button == MouseButtons.Left)
        pts = Point(e.X, e.Y) :: pts
    else
        pts = []
    f.Invalidate()

f.Paint += fun (_,e)
    when (pts.Length > 0)
        def (c, a) = pts.BestFit()

        def x1 = c.X - Cos(a) * 100
        def y1 = c.Y - Sin(a) * 100
        def x2 = c.X + Cos(a) * 100
        def y2 = c.Y + Sin(a) * 100
        e.Graphics.DrawLine(System.Drawing.Pens.Red, x1 :> int, y1:> int, x2:> int, y2:> int)

    foreach (pt in pts)
        e.Graphics.FillRectangle(System.Drawing.Brushes.Black, pt.X :> int, pt.Y :> int,1,1)

Application.Run(f)

For now the function returns the centroid of the points and the angle of the line. One special case is when there is no “best” fit line because all points are evenly spaced around the centroid. When line following we would want to simply ignore the bogus angle and instead put a line through the centroid from the previous segment end point.
So the BestFit function really needs some kind of tagged union (variant in Nemerle) data type to return. I will create this once the line follower is formalized.


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

November 2014

Mo Tu We Th Fr Sa Su
Oct |  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
© MMXIV