NETWORK SIMPLIFICATION BASED ON THE ALGORITHM OF POLARIZATION TRANSFORMATION

H. Qian, L. Meng, M. Zhang

Department of Cartography, Technical University Munich, Munich, Germany

haizhongqian@gmail.com

Recent years, the growing demand on intelligent transportation systems (ITS) that provide relevant routing services has been urging the research world to construct so-called routing-capable digital databases. Although there exist already a dozen of commercially available car navigation databases and an even larger number of navigation databases intended to help tourists walk through densely populated downtown areas, these fine detailed databases are not immediately usable for routing applications in medium-scale ranges such as large-region fleet management and emergency coordination. This paper addresses the issue of automatically simplifying the road network from a large scale to a medium scale range. While the currently available approaches have been mainly focused on the simplification of road junctions and the selection of semantically or visually important roads, the new approach puts its emphasis on the preservation of overall network structure and the relative density of road segments. In addition, the approach works under the assumption that semantic attributes describing the road segments are not or only partly available, which is often the case in the practice. A key technique involved in this new approach is termed as polarization transformation (PT). By means of PT, a two-dimensional network can be converted into a one-dimensional spectrum line without information loss, thus allows a more straightforward cluster analysis to be conducted in a simpler space, i.e. the spectrum line.

The process of the approach involves the following major steps:

1. Preprocessing of road topology

The original fine grained road networks are cleaned by chaining the fragmental segments into strokes and filling erroneous small gaps. The outcome is a connected graph composed of several perceivable network regions.

2. Stroke categorization

By activating a recognition routine, the road strokes are analyzed and differentiated. They bear the following information:

·Metric measures such as stroke length, area of network regions etc.

·Topological measures such as connectivity, intersection etc.

·Category such as dead lock, intermediate line, island line etc., and

·Structural characteristics such as cloverleaf junction, bottle neck between two junctions, auxiliary carriage way etc.

3 Calculation of stroke weight

A multiple mathematic fitting model which takes account of the information in 2 is designed. It will create the weights for all individual strokes.

4. Polarization and network simplification

The individual strokes are replaced by with their center points to form a point cluster. Based on an optimization criterion, a point within the cluster is determined as the origin of polar coordinate system. The polar coordinates of all the points in the cluster is then inwinded onto a spectrum line, with its x-axis corresponding to the polar angle from 0-360° and y-axis corresponding to the weighted polar radius. Finally, the nodes along the spectrum line undergo a simplification procedure, by which only the characteristic nodes are preserved. A simplified network is thus created by converting the selected nodes back to the 2D space.

In order to demonstrate the advantages of this approach, random tests are undertaken with different data from different sources such as Basis DLM (Basic Digital Landscape Model of German Mapping Agencies) and TeleAtlas. The test results have proved the feasibility of the approach. Furthermore, the approach can be easily extended to involve any kind of semantic constraints.