All entries for Wednesday 17 January 2007
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.