/ Assoc. Prof. Dr. N. Necla ULUGTEKIN is a senior lecturer in the Cartography Division of Department of Geodesy and Photogrammetry in Istanbul Technical University – ITU. Her main interests recently are cartography, visualization, GIS and small display cartographic design.
She was involved in a number of individual and team studies and projects on Electronic Atlas, Mountain Maps, Map Design for Hand Held Devices and etc. She actively remains supporting chambers activities and taken position as a string head or a member in the technical commissions, like Cartography Commission Secretary from Standing Scientific and Technique Commission of Chamber of Surveying, Geographic Information System Commission, and etc. She is working on cartography in national and international activities.
/ Assis. Prof. Dr. Seval ALKOY, Epidemiologist and Public Health Specialist.
She is senior lecturer of Abant Izzet Baysal University Izzet Baysal Medical Faculty, Public Health Department. Her main interests are epidemiology, biostatistics and environmental health. She is studying for generalizing the use of GIS for epidemiological purposes. In addition to her academic studies, she is also president of Association of Doctors for Environmental which is a member of International Society of Doctors for Environmental-ISDE.
CLASSIFICATION OF ROAD JUNCTIONS BASED ON MULTIPLE REPRESENTATIONS: ADDING VALUE BY INTRODUCING ALGORITHMIC AND CARTOGRAPHIC APPROACHES
A.O. Dogru1, N. Van de Weghe2, N.N. Ulugtekin1, Ph. De Maeyer2
1 Istanbul Technical University, Cartography Division, Istanbul, Turkey (dogruahm,)
2 Ghent University, Department of Geography, Gent, Belgium (nico.vandeweghe, )
ABSTRACT
In this study, car navigation is considered as the basic activity and the multiple representation approach for the production of the navigation maps is taken into account to derive road network data for different representation levels. In this context, road junctions, which are the most complicated parts of road networks, are classified considering two different approaches, an approach based on cartographic aspects and an approach based on algorithmic aspects. In the first approach, road junctions are classified according to their aspects at different representation levels. In this concept, three representation levels, which are derived from 1:5000 scaled base level, are used and representations of possible road junctions are structured according to characteristics of these levels. Finally, they are classified by considering their geometrical shapes in each level. In the second approach, road junctions are classified according to algorithmic concerns. Junctions are defined in matrices based on their specific characteristics and also these matrices are classified according to their similarity. Finally, common representations are determined for these classes.
Key Words: Multiple representations, road junctions, classification, junction representation.
1. INTRODUCTION
Navigation is one of the fundamental human activities. Thanks to the technological developments in computer and electronic sciences, navigation industry and the navigation technology developed rapidly and has become an integral part of everyday life. In addition to the technical components, maps are considered as the basic component of navigation systems. Moreover, database models and representation approaches, which form the basic infrastructure of these maps, are another fundamental component of these systems. These maps should be considered in two different dimensions: the base maps which involve the road network data on which network algorithms, such as finding shortest path and optimal way, are executed, and the maps which are used as user interface (Dogru, 2004; Yuefeng et al 2005; Dogru and Ulugtekin, 2006). In addition to this development, since the display media of the navigation systems are small in size, it is impossible to present the base map as the user interface during the navigation process because base map data is quite complex with its network data of multi-lanes, one-way streets, cloverleaf junctions etc. Hence, abstracted representations of road network and related data are used in this manner. Detailed studies on deriving multiple representations from related databases (Multiple Representation Databases, MRDB) were executed by Kilpelainen (1997) and Dunkars (2004).
It is clear that deriving multiple representations of a base data requires generalization works. Several studies have been succeeded on road network generalization. It is obvious that, in addition to the studies executed by Mackaness and Beard (1993) and Thomson and Richardson (1995), one of the most important developments in the road network generalization was succeeded by Mackanness and Mackechnie (1999). This approach proposes a method for the detection and simplification of road junctions using a combination of spatial clustering and graph theory. In this concept, junctions are identified via cluster analysis and generalized based on graph theoretical methods. As a result, each junction formed by set of connections is represented by a single vertex representing the centroid of determined junction clusters. This approach was basically developed to derive topographic maps for National Mapping Agencies. However, some application-based requirements should also be taken into account while developing generalization algorithms.
This study introduces a method for representing more detailed road networks, in particular road junctions, although they are generalized. The main aim of the study is to derive road maps, which can be used as different levels of user interfaces for navigational purposes, by clustering the junctions and determining a common representation for each cluster. In this concept, road junctions and related works are presented in the second part of the paper. Additionally, final remarks and benefits of the proposed methods for the use navigation systems or as a supplementary part of current generalization algorithms are presented in the third part of the study.
2. ROAD JUNCTIONS
The identification of what is a “junction” is essentially a scale dependent issue. For example, a collection of roads comprising a town, when viewed at 1: 250,000 could be viewed as a complex junction required to be reduced to a single point (Mackanness and Mackechnie, 1999). When the term junction is considered in terms of navigation system it can also refer to the intersection of two lines or a set of dense intersecting lines (junctions), which is also called as complex junctions (Zhang, 2004). Mostly, road network generalization approaches collapse these complex junctions according to the target scale. However, they should be represented in more detail for navigation systems. Therefore, more useful organization can be imposed on the maze of junctions. In this study, an efficient classification of junctions is considered as the first step for better organizations of junctions.
2.1. Current Classification Approaches
Design and the classification of the junctions differ according to the road engineering principles and fundamental usage aim of the junctions. In this concept, junctions can be classified in terms of accident assessment, capacity of the road, turning rights, etc. For example, junctions are classified as major/minor, signals and roundabouts in terms of accident assessment (Watkiss et al, 2000). Additionally, each of these classes is subdivided into standard, small and mini and totally 96 different junction types are obtained in this manner (DMRB, 1997). As a second example, Geographic Data Files standard, European Union standard for storing and using road data for navigational purposes, defines two main types of road junctions called intersection and junction. These junctions combine 9 different road types to each other. According to this classification intersections are divided in three groups as freeway intersection, roundabout and crossing (GDF3.0, 1995). However, most common and basic classification of junctions is based on their grade separation. If a road junction has a grade separation, it is called an intersection. In this type of junctions, roads cross each other directly. It is called as interchanges if roads pass above or below one another, preventing a single point of conflict by utilizing grade separation and slip roads. The terms “motorway junction” and “highway junction” typically refer to this layout (Dogru, 2004).
2.2. New Approaches
In this study, totally 29 different kinds of junctions (intersections and interchanges) that can be encountered as a real world road structure were determined to use in practice and we tried to find a clustering method for them. Potential behaviors of the car driver passing a junction are considered to obtain the optimum clustering for navigation purposes.
Although there are several classifications including these junction types, new approaches are tried to be applied to obtain better results of classification. In this concept, these junctions are classified by using algorithmic methods. First of all junctions were represented as matrices by considering their complexity and turning rights in all directions. As it is seen from Figure 1, first row and column of the matrix represent the directions of the crossing roads as left, right, up, and down (L, R, U, and D). Complexity matrix is structured by using the topological relations of the line segments while the turning rights matrix is structured according to the turning rights defined on the junctions of road network. If it is possible to turn from a direction to another it was represented as 1 otherwise 0. As it is represented in Figure 1, it is not possible to turn in all directions while driving through the sample junction.. After determining the matrix representations of all junctions, they were classified according to the similarities of these matrixes. As a result of this classification, 29 junction structures, including both interchanges and intersections classified in 7 and 9 sub classes in terms of complexity and turning rights respectively.
Figure 1. Matrix representation of parclo junction
As a result of the discussions on these classification results, it is determined that matrix representations individually are not sufficient to completely represent the characteristics of road junctions in terms of navigation purposes. Hence a new methodology was proposed to succeed the classification task.
According to stated methodology; junctions were represented as tree structures by considering all potential maneuvers of a driver passing the junction. In this concept, a junction (J) is considered with its all directions of connecting roads (Left, Right, Up, and Down) and all maneuvers of a driver, entering to the junction from any direction, at a connection point of the junction are defined as representing the route selection with a digit starting from 1; 1 for the first path on the right side (see Figure 2). The junction is represented as a whole by merging these tree structures into one according to merging algorithms (Kim 2000; Chen et al 2003).
Figure 2. Tree representation for all routes of a junction
3. CONCLUDING REMARKS AND FUTURE WORKS
The proposed methodology is a part of ongoing study being executed to implement an automated junction recognition and representation system in terms of MRDB. This approach will be used to determine the levels of detail for road networks in representation levels emphasized by Dogru and Ulugtekin (2006). In this concept clustering and representing process will be repeated to determine details of the higher levels of representations. Such an implementation has several benefits in terms of increasing the quality of road maps used for different purposes. Hence it is obvious that this approach will also add value to the current navigation systems by enabling them to produce road maps by considering the behaviors of the driver. Integration of proposed approach, as an automated system to MRDB will be useful for both navigation systems and automated map production studies by enabling system to produce different representations for different applications automatically.
It is obvious that some modifications can also be applied to this tree representation by using reduction algorithms. In the following stages of the clustering methodology, obtained tree structures are planned to be clustered based on the shock graph approach implemented by Sebastian et al. (2001), Torsello et al. (2003), and Torsello and Hancock (2004). Finally, graph similarity algorithms will be used to determine a common representation for each cluster (Blondel et al 2004).
Implementation of proposed approach in an automated way is the future work of the authors. Moreover, studies on integration of the implemented system with MRDB studies are considered as another future work. In addition to these works some additional studies should be taken into account to integrate the real-time map production capability to current navigation systems.
4. REFERENCES
Blondel, V. D., Gajardo, A., Heymans, M., Senellart, P., and Dooren, P. V. 2004. A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching. SIAM Rev. 46, 4 (Apr. 2004), 647-666. DOI= http://dx.doi.org/10.1137/S0036144502415960
Chen Z., Ding J., Zhang M., Tavanapong W., and Johnny S W. J.S., 2003. Hierarchical Clustering-Merging for Multidimensional Index Structures, E. M. Bakker et al. (Eds.): CIVR 2003, LNCS 2728, pp. 81–90, 2003. Springer-Verlag Berlin Heidelberg.
DMRB, 1997. Economic Assessment of Road Schemes: COBA Manual, Design Manual for Roads and Bridges, Volume 13, The Highways Agency.
Dogru, A.O., 2004. Multiple Representations For Junction Modeling In Car Navigation Map Design, MSc. Thesis, Istanbul Technical University, Institute of Science and Technology, Turkey (in Turkish).
Dogru, A.O., Ulugtekin, N., 2006. Car Navigation Map Design in terms of Multiple Representations, First International Conference on Cartography and GIS, 25-28 January, Borovets, Bulgaria (CD-rom).
Dunkars, M., 2004. Multiple Representation Databeses for Topographic Information, PhD Thesis, KTH Royal Institute of Technology, Sweden.
GDF 3.0, 1995. Geographic Data Files, European Committee for Standardisation, European Standard, CEN TC 278. http://www.ertico.com/en/links/links/gdf_-_geographic_data_files.htm (accessed, 02.03.2007)
Kilpelainen, T., 1997. Multiple Representation and Generalization of Geo-Databases for Topographic Maps, PhD Thesis, Finnish Geodetic Institute, Finland.
Kim Y., 2000. Simple and Fault-Tolerant Key Agreement for Dynamic Collaborative Groups, CCS '00, Athens, Greece. 2000 1-58113-203-4/00/0011.
Mackaness, W.A., and Beard, M.K., 1993. Use of Graph Theory to Support Map Gen-eralisation. Cartography and Geographic Information Systems 20: 210 – 221.
Mackaness W., Mackechnie G., 1999., Automating the Detection and Simplification of Junctions in Road Networks, GeoInformatica 3:2, 185-200.