All 21 entries tagged Project
February 26, 2007
I combined the junction detector with the line following algorithm. The result is a graph vectoriser! I still need to refine the algorithm so it only uses each junction exit once, but basically it works!
The rest of the week can now be spent building an interaction demo. :D
February 23, 2007
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.
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!
January 17, 2007
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:
- 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.
- Calculate best-fit lines at each waypoint (images scaled 2x)
- 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.
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
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.
I am thinking about using the closest “point” as a hint to the next heading to take when following a line.
November 23, 2006
Here is a sample of a vectorized line (shown in red):
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.
- Intersect at a single point
- Be coincident (i.e. identical)
- 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")
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 => ...
November 22, 2006
- 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
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.
Using my previous prototypes I created a line following program. Given two initial points that indicate the start point and heading, it is able to follow a line drawn on my sample image.
The key function is:
def NextPoint(prevGradient : double, prevStartPoint : Point, prevEndPoint : Point, radius : int, bmp : Bitmap) : (double * Point * Point)
- previous gradient
- line segment (start and end points)
- pixel capture radius
- gradient of the next line segment
- the improved end point for the previous line segment
- the end point of the new line segment
Repeatedly calling this function passing in the previous data follows the line. The “improved end point” return is the intersection of the previous and current line segments – this make the polyline fit much better around corners. Without that it will overshoot then swing back each time.
I will not post the code here because frankily it’s getting messy! Also I am having some real difficulty expressing vertical lines as Infinite gradients and an X-intercept. It is now time to introduce some proper data structures to represent lines, etc, and better methods of calculating intercept points, etc.
One more quick idea:
Once the line follower has “used” some pixels should they be “removed” to prevent later confusion? I could not remove after one step, since previous pixels are used to shape the current line segment. But the pixels two-steps back should now be out of range. This would also stop the NextPoint function “turning around” at a dead-end.