Gap Breaching

We had a look at our results and noticed that there were some gaps in a number of our ouptuts. It was decided to try and breach these gaps by converting our raster centerlines into vector format.With the help of the open source GIS application GRASS we were able to do the conversion and also do some elementary clean-up work on the vectors. This included snapping of nearby vectors, smoothing/straightening of wiggly lines and removal of small anomalies. It turns out that GRASS has a module (developed as part of Google’s Summer of Code 2007) that will do various clean-up operations that are specific to road networks. There’s even a tutorial that explains the how some of the components works. Very handy!

Based on our new clean set of vectors, we implemented a very basic algorithm that breaches gaps based on the following criteria:

• the orientation of endpoints,
• the distance between endpoints, and
• the length of the line segments to be connected.

Our method works really well and it performs as expected. It connects a lot of the lines I would connect, if I did not know what the input data looked like.

Unfortunately some of our results include a lot of false positives. The gap breaching algorithm connects these false positives (FP) and we end up with even more incorrect line segments.

This is just a rough guess, but I would say that we see improvements of around 5-15% on data sets with little FPs and a couple of gaps. Unfortunately the real world data sets contains FPs and we are unable to improve on our highest quality measures of 64%. Bummer.

The next step would be to reduce the number of FPs, which obviously causes the number of true positives (TP) to drop. Hopefully the gap breaching algorithm will be able to compensate for the loss of TPs, but I’m not holding my breath.

~ by ahauptfleisch on December 13, 2007.