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.