A TEST OF AUTOMATIC ROAD EXTRACTION APPROACHES

Roads are important objects for many applications of topogr aphic data. They are often acquired manually and as this enta ils significant effort, automation is highly desirable. Deficits in the auto matic extraction hindering a wide-scale practical use have led to the idea of setting-up a EuroSDR test comparing different approache s for automatic road extraction. The goal is to show the poten tial of the state-of-the-art approaches as well as to identify promisi ng directions for research and development. After describi ng the data and the evaluation criteria used, we present the approaches of a num ber of groups which have submitted results and give a detaile d d scussion of the outcome of the evaluation of the submitted results. We finally present a summary and conclusions. 1.  The need for accurate, up-to-date, and detailed informatio n for roads is rapidly increasing. They are used in a variety of app lications ranging from the provision of basic topographic inf rastructure, over transportation planning, traffic and fleet ma nagement, car navigation systems, location based services (LBS ), and tourism, to web-based applications. While road extraction has been performed by digitizing maps, the update and refinement of the road geometry is often based on aerial imagery or high resolution satellite imagery such as Ikonos or Quickbird. A dditionally, terrestrial methods, particularly mobile mappi ng are of significant importance for determining attributes for navi gat onal purposes. Because road extraction from imagery, on which we focus for t he remainder of this paper, entails large efforts in terms of ti me and money, automation of the extraction is of high potential int erest. Full automation of the extraction of topographic objects is currently practically impossible for almost all applications and thus a combination with human interaction is necessary. An impor tant factor hindering the practical use of automated proced ures is the lack of reliable measures indicating the quality and acc uracy of the results, making manual editing lengthy and cumbersom e. Manufacturers of commercial systems have developed very fe w tools for semi-automated extraction and their cooperation with academia has been minimal. Thus, users and producers of such data, including national mapping agencies (NMAs) and large p ivate photogrammetric firms, have been left with many wishes t o be fulfilled. NMAs increasingly plan to update their data in shorter cycle s. Their customers have increasing demands regarding the leve l of accuracy and object modeling detailedness, and often reque st additional attributes for the objects, e.g., the number of lan es for roads. The insufficient research output and the increasing u ser needs, necessitate appropriate actions. Practically orie nted research, e.g., the ATOMI project at the ETH Zurich (Zhang, 2004), has shown that an automation of road extraction and up date is feasible to an extent that is practically very releva nt. Companies that have developed semi-automated tools for buildi ng extraction and other firms too, could very well offer similar to ols for roads. These considerations led to the idea of setting-up a road ext raction test under the umbrella of EuroSDR (European Spatial Da ta Research – www.eurosdr.net). An important inspiration for it was the highly successful 3D reconstruction test of (Scharstei n and Szeliski, 2002) which has become a standard in the field. The e mphasis of our test is put on the thorough evaluation of the cur rent status of research (including models, strategies, methods an data used). Through testing and comparing existing semior full y automated methods based on various datasets and high quality r eference data extracted manually by an experienced operator f om the image data used for the test, weak points as well as promis ing directions should be identified and, strategies and methods that lead to a fast implementation of operational procedures for road extraction, update, and refinement should be proposed. Howe ver, since most of the participating groups focus on road extract ion rather than on refinement or update, the scope of this test has been limited purely on road extraction for the time being. 2. DATA AND TEST SET-UP Initially, eight test images were prepared from different a eri l and satellite sensors. All images have a size of at least 4,000 4,000 pixels. Unfortunately, this was found to be insurmountable by nearly all approaches and, therefore, the limiting factor o f the test. Reasons for an inability to process the larger scenes w ere apparently twofold: First, because of missing functionali ty for processing the whole image in patches which are then combine d into one solution, intermediate results just exceeded the a vailable memory. Second, even if this had not been the case, the time it takes to process the images together with the need to adapt th e parameters to all variations in the larger scenes, meant the se images required too much effort for most people. Hence we decid ed eventually to cut out three smaller parts with 1,600 1,600 pixels of Ikonos images where we found the largest interest. In the following, only those images are listed, for which at l east three extraction results were submitted: 3 scanned aerial images from the Federal Office of Topography, Bern, Switzerland (image scale 1 : 16 000, focal length 0.3 m, RGB, 0.5 m ground resolution, 4 000 4 000 pixels – see Fig. 1) ) – Aerial1: suburban area in hilly terrain – Aerial2: hilly rural scene with medium complexity – Aerial3: hilly rural scene with low complexity 3 IKONOS images (Geo) from Kosovo, provided by Bundeswehr Geoinformation Office (AGeoBw), Euskirchen, Germany, given as pan-sharpened images in red, green, blue, and infrared (1 600 1 600 pixels – see Fig. 1 and 2) – Ikonos1-Sub1: urban/suburban area in hilly terrain – Ikonos3-Sub1 and -Sub2: rural hilly scenes with medium complexity For evaluation we use criteria put forward by (Wiedemann et a l., 1998). The basic assumption is that reference data is availa ble n the form of the center lines of the roads. Additionally, it is a sumed that only roads within a buffer of a certain width, usua lly the average width of the roads, around the road, here 5 pixels on both sides, i.e., 10 m for the Ikonos data, are correct. The ex tracted roads which are inside the buffer of the given refere nce roads and vice versa are determined via matching of the respe ctive vector data. The most important criteria defined by (Wie demann et al., 1998) based on these matching results to which we have restricted the analysis are: Completeness: This is the percentage of the reference data which is explained by the extracted data, i.e., the part of the refe rence network which lies within the buffer around the extracted da ta. The optimum value for completeness is 1. Correctness: It represents the percentage of correctly extracted road data, i.e., the part of the extracted data which lie with in t e buffer around the reference network. The optimum value for c orrectness is 1. RMS (root mean square): The RMS error expresses the geometrical accuracy of the extracted road data around the reference network. In the given evaluation framework its value depends on the buffer widthw. If an equal distribution of the extracted road data within the buffer around the reference network is assum ed, it can be shown that RMS = w=p3. The optimum value is RMS = 0. As RMS mainly depends on the resolution of the image, it is given in pixels in this paper. The reference data has an estimated precision of half a pixel . It comprises major and secondary roads, but no paths or short dr iveways. The reference data has not been made available to the pa rticipants. The participants usually asked only once or twic e for an evaluation, i.e., no optimization in terms of the reference data was pursued. Opposed to (Scharstein and Szeliski, 2002) we allo wed people to optimize their parameters for each and every image , as constant parameters were seen as too challenging. 3.  APPROACHES We will shortly introduce the approaches of the participati ng groups (alphabetical ordering according to corresponding author): Uwe Bacher and Helmut Mayer, Institute for Photogrammetry and Cartography, Bundeswehr University Munich, German y: The approach is only suitable for the Ikonos images and is focusing on rural areas where roads are mostly homogeneous and are not disturbed by shadows or occlusions. It is based on ear lier work from TU München of (Wiedemann and Hinz, 1999) and partially (Baumgartner et al., 1999). The approach of (Wied emann and Hinz, 1999) starts with line extraction in all spect ral bands using the sub-pixel precise Steger line extractor (St eger, 1998) based on differential geometry and scale-space inclu ding a thorough analysis and linking of the topology at intersect ions. The lines are smoothed and split at high-curvature points. T he resulting line segments are evaluated according to their wi dth, length, curvature, etc. Lines from different channels or ex t acted at different scales, i.e., line widths, are then fused on a be st first basis. From the resulting lines a graph is constructed, supp lemented by hypotheses bridging gaps. After defining seed line s in the form of the best evaluated lines, optimal paths are compu ted in the graph and from it gaps to be closed are derived. Bacher has extended this by several means (Bacher and Mayer, 2005). The central idea is to take into account the spectral informa tion by means of a (fuzzy) classification approach based on fully a tomatically created training areas. For the latter parallel e dges are extracted in the spirit of (Baumgartner et al., 1999) in a buf fer around the lines and checked if the area in-between them is ho mogeneous. The information from the classification approac h is used to evaluate the lines. Additionally, it is the image inf ormation when