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.
2. Calculate best-fit lines at each waypoint (images scaled 2x)
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.

You are not allowed to comment on this entry as it has restricted commenting permissions.

Search this blog

• I scratched my eye while i was holding some kind of plastic packagi… by Ercan on this entry
• About a year ago my contacts that i was wearing, i guess were fautl… by Jon on this entry
• I got shower gel in my eye 4 and a half days ago, and becasue i rub… by Chris on this entry
• This website may help http://www.webmd.com/eye–health/tc/Eye–In… by S on this entry
• I somehow got dirt, or debris in my eye. The terrible pain sent me … by Bobbi on this entry

January 2007

Mo Tu We Th Fr Sa Su
Dec |  Today  | Feb
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 31