Elsevier

Robotics and Autonomous Systems

Volume 83, September 2016, Pages 312-325
Robotics and Autonomous Systems

Incremental scenario representations for autonomous driving using geometric polygonal primitives

https://doi.org/10.1016/j.robot.2016.05.011Get rights and content

Abstract

When an autonomous vehicle is traveling through some scenario it receives a continuous stream of sensor data. This sensor data arrives in an asynchronous fashion and often contains overlapping or redundant information. Thus, it is not trivial how a representation of the environment observed by the vehicle can be created and updated over time. This paper presents a novel methodology to compute an incremental 3D representation of a scenario from 3D range measurements. We propose to use macro scale polygonal primitives to model the scenario. This means that the representation of the scene is given as a list of large scale polygons that describe the geometric structure of the environment. Furthermore, we propose mechanisms designed to update the geometric polygonal primitives over time whenever fresh sensor data is collected. Results show that the approach is capable of producing accurate descriptions of the scene, and that it is computationally very efficient when compared to other reconstruction techniques.

Introduction

Recent research in the fields of pattern recognition suggest that the usage of 3D sensors improves the effectiveness of perception, “since it supports good situation awareness for motion level tele-operation as well as higher level intelligent autonomous functions”  [1]. Nowadays, autonomous robotic systems have at their disposal a new generation of 3D sensors, which provide 3D data of unprecedented quality  [2]. In robotic systems, 3D data is used to compute some form of internal representation of the environment. In this paper, we refer to this as 3D scene representation or simply 3D representation. The improvement of 3D data available to robotic systems should pave the road for more comprehensive 3D representations. In turn, advanced 3D representations of the scenes are expected to play a major role in future robotic applications since they support a wide variety of tasks, including navigation, localization, and perception  [3].

In summary, the improvement in the quality of 3D data clearly opens the possibility of building more complex scene representations. In turn, more advanced scene representations will surely have a positive impact on the overall performance of robotic systems. Despite this, complex scene representations have not yet been substantiated into robotic applications. The problem is how to process the large amounts of 3D data. In this context, classical computer graphics algorithms are not optimized to operate in real time, which is a non-negotiable requirement of the majority of robotic applications. Unless novel and efficient methodologies that produce compact, yet elaborate scene representations, are introduced by the research community, robotic systems are limited to mapping the scenes in classical 2D or 2.5D representations or are restricted to off-line applications.

Very frequently, the scenarios where autonomous systems operate are urban locations or buildings. Such scenes are often characterized for having a large number of well defined geometric structures. In outdoor scenarios, these geometric structures could be road surfaces or buildings, while in indoor scenarios they may be furniture, walls, stairs, etc. We refer to the scale of these structures as a macro scale, meaning that 3D sensor may collect thousands of measurements of those structures in a single scan. A scene representation is defined by the surface primitive that is employed. For example, triangulation approaches make use of triangle primitives, while other approaches such as Poisson surface reconstruction resort to implicit surfaces. Triangulation approaches generate surface primitives that are considered to have a micro scale, since a geometric structure of the scene could contain hundreds or thousands of triangles. Micro scale primitives are inadequate to model large scale environments because they are not compact enough.

In this paper, we present a novel methodology to compute a 3D scene representation. The algorithm uses macro scale polygonal primitives to model the scene. This means that the representation of the scene is given as a list of large scale polygons that describe the geometric structure of the environment. The proposed representation addresses the problems that were raised in the previous lines: the representation is compact and can be computed much faster than most others, while at the same time providing a sufficiently accurate geometric representation of the scene from the point of view of the tasks required by an autonomous system.

The second problem addressed in this paper is the reconstruction of large scale scenarios from a continuous throughput of massive amounts of 3D data. We will use the distinction between the terms scene and scenario. Let scenario refer to a particular location that should be reconstructed, e.g., a city, a road or a building. By scene, we refer to the portion of the scenario that is viewed by the vehicle at a particular time. Thus, the scenario is an integration of scenes over time. In the case of large scale scenarios, the compactness of a given scene representation is even more important. In this paper, we focus also on how the representation may evolve by integrating 3D data from multiple measurements over time.

This is an extended version of  [4]. The new material covers mostly the incremental part of the geometric reconstruction. There is also the possibility of adding texture to the geometric scene description. For further details on this see  [5].

For testing and evaluation purposes, we use a data-set from the Massachusetts Institute of Technology (MIT) Team, taken from their participation in the DARPA Urban Challenge  [6]. From this data-set we have extracted a 40 s sequence which will be used to assess the proposed algorithms. For the remainder of the paper, this sequence is referred to as MIT sequence. Using this data-set, we aim at reconstructing large portions of the urban environment in which the competition took place.

The remainder of this paper is organized as follows: Section  2 reviews the state of the art, Section  3 presents the proposed approach. Results are given in Section  4 and conclusions in Section  5.

Section snippets

Related work

At first glance, it would seem plain to translate the improvement on the quality of the 3D data into an enhancement of the 3D representations. However, the fact is that the majority of the robotic systems, namely autonomous vehicles, continue to rely on classic 2D or 2.5D scene representations  [7], such as occupancy grids  [8] or elevation maps  [9], or use discretized grid-like approaches as in octrees  [10]. The reason for that is that autonomous vehicles commonly require a large array of

Proposed approach

In this section we will explain in detail the methodologies of our approach. First, we describe the scene reconstruction algorithm (see Section  3.1) and then, in Section  3.2, we describe how a scenario is created over time from a continuous throughput of 3D data.

Results

In order to evaluate the proposed 3D processing techniques, a complete data-set with 3D laser data, cameras and accurate egomotion is required. The MIT autonomous vehicle Talos competed in the DARPA Urban Challenge and achieved fourth overall place. The data logged by the robot is publicly available  [6]. In total, the MIT logs sum up to 315 GB of data. We have cropped a small sequence of 40 s (200 m of vehicle movement) at the start of the race (see Fig. 6). The sequence contains a continuous

Conclusions

This paper proposes a novel approach to produce scene representations using the array of sensors on-board autonomous vehicles. Since roads are semi structured environments with a great deal of macro size geometric structures, we argue that the use of polygonal primitives is well suited to describe these scenes. Furthermore, we propose mechanisms designed to update the polygonal primitives as new sensor data is collected. Results have shown that the proposed approach is capable of producing

Acknowledgments

This work has been supported by the Portuguese Foundation for Science and Technology “Fundação para a Ciência e Tecnologia” (FTC), under grant agreements SFRH/BD/43203/2008 and SFRH/BPD/109651/2015 and projects POCI-01-0145-FEDER-006961 and UID/CEC/00127/2013. This work was also financed by the ERDF European Regional Development Fund through the Operational Programme for Competitiveness and Internationalisation - COMPETE 2020. A. Sappa has been partially supported by the Spanish Government

Miguel Oliveira received the Mechanical Engineering and M.Sc. in Mechanical Engineering degrees from the University of Aveiro, Portugal, in 2004 and 2007, where later in 2013 he obtained the Ph.D. in Mechanical Engineering specialization in Robotics, on the topic of autonomous driving systems. Currently he is a researcher at the Institute of Electronics and Telematics Engineering of Aveiro, Portugal, where he works on visual object recognition in open-ended domains. His research interests

References (33)

  • A. Bykat

    Convex hull of a finite set of points in two dimensions

    Inform. Process. Lett.

    (1978)
  • A. Birk et al.

    3-d perception and modeling

    IEEE Robot. Autom. Mag.

    (2009)
  • R.B. Rusu, S. Cousins, 3D is here: Point Cloud Library (PCL), in: IEEE International Conference on Robotics and...
  • W. Burgard et al.

    Editorial: Three-dimensional mapping, part 1

    J. Field Robot.

    (2009)
  • M. Oliveira, V. Santos, A.D. Sappa, P. Dias, Robot 2015: Second Iberian Robotics Conference: Advances in Robotics,...
  • M. Oliveira et al.

    Incremental texture mapping for autonomous driving

    Robot. Auton. Syst.

    (2016)
  • A.S. Huang et al.

    A High-rate, Heterogeneous Data Set from the DARPA Urban Challenge

    Int. J. Robot. Res.

    (2011)
  • Z.C. Marton, R.B. Rusu, M. Beetz, On fast surface reconstruction methods for large and noisy datasets, in: Proceedings...
  • T. Weiss, B. Schiele, K. Dietmayer, Robust driving path detection in urban and highway scenarios using a laser scanner...
  • F. Oniga et al.

    Processing dense stereo data using elevation maps: Road surface, traffic isle, and obstacle detection

    IEEE Trans. Veh. Technol.

    (2010)
  • K. Zhou et al.

    Data-parallel octrees for surface reconstruction

    IEEE Trans. Vis. Comput. Graphics

    (2011)
  • S. Thrun et al.

    Stanley: The robot that won the darpa grand challenge

    J. Field Robot.

    (2006)
  • C. Urmson et al.

    A robust approach to high-speed navigation for unrehearsed desert terrain

    J. Field Robot.

    (2006)
  • C. Urmson et al.

    Autonomous driving in urban environments: Boss and the urban challenge

    J. Field Robot.

    (2008)
  • M. Montemerlo et al.

    Junior: The stanford entry in the urban challenge

    J. Field Robotics

    (2008)
  • A. Bacha et al.

    Odin: Team victortango’s entry in the darpa urban challenge

    J. Field Robot.

    (2008)
  • Cited by (0)

    Miguel Oliveira received the Mechanical Engineering and M.Sc. in Mechanical Engineering degrees from the University of Aveiro, Portugal, in 2004 and 2007, where later in 2013 he obtained the Ph.D. in Mechanical Engineering specialization in Robotics, on the topic of autonomous driving systems. Currently he is a researcher at the Institute of Electronics and Telematics Engineering of Aveiro, Portugal, where he works on visual object recognition in open-ended domains. His research interests include multimodal sensor fusion, computer vision and robotics.

    Vítor Santos obtained a 5 year degree in Electronics Engineering and Telecommunications in 1989, at the University of Aveiro, Portugal, where he later obtained a Ph.D. in Electrical Engineering in 1995. He was awarded fellowships to pursue research in mobile robotics during 1990–1994 at the Joint Research Center, Italy. He his currently Associate Professor at the University of Aveiro and lectures courses related to advanced perception and robotics, and has managed research activity on mobile robotics, advanced perception and humanoid robotics, with the supervision or cosupervision of more than 100 graduate and undergraduate students, and more that 120 publications in conferences, books and journals. At the University of Aveiro he has coordinated the ATLAS project for mobile robot competition that achieved 6 first prizes in the annual Autonomous Driving competition and has coordinated the development of ATLASCAR, the first real car with autonomous navigation capabilities in Portugal. He is one of the founders of Portuguese Robotics Open in 2001 where he has kept active participation ever since. He his also cofounder of the Portuguese Society of Robotics, and participated several times in its management since its foundation in 2006. His current interests extend to humanoid robotics and the application of techniques from perception and mobile robotics to autonomy and safety in ADAS contexts.

    Angel Domingo Sappa (S’94-M’00-SM’12) received the Electromechanical Engineering degree from National University of La Pampa, General Pico, Argentina, in 1995, and the Ph.D. degree in Industrial Engineering from the Polytechnic University of Catalonia, Barcelona, Spain, in 1999. In 2003, after holding research positions in France, the UK, and Greece, he joined the Computer Vision Center, Barcelona, where he is currently a Senior Researcher. He is a member of the Advanced Driver Assistance Systems Group. His research interests span a broad spectrum within the 2D and 3D image processing. His current research focuses on stereoimage processing and analysis, 3D modeling, and dense optical flow estimation.

    Paulo Dias graduated from the University of Aveiro Portugal in 1998 and started working in 3D reconstruction at the European Joint research Centre in Italy. In September 2003, he concluded his Ph.D. with the thesis “3D Reconstruction of real World Scenes Using Laser and Intensity Data”. He is currently an assistant professor within the Department of Electronics Telecommunications and Informatics (DETI) and is involved in several works and projects within the Institute of Electronics and Informatics Engineering of Aveiro (IEETA) related to 3D Reconstruction, Virtual Reality, Computer Vision, Computer Graphics, Visualization and Combination and Fusion of data from multiple sensors.

    António Paulo Moreira graduated with a degree in electrical engineering at the University of Oporto, in 1986. He then pursued graduate studies at University of Porto, obtaining an M.Sc. degree in electrical engineering-systems in 1991 and a Ph.D. degree in electrical engineering in 1998. Presently, he is an Associate Professor at the Faculty of Engineering of the University of Porto and researcher and manager of the Robotics and Intelligent Systems Centre at INESC TEC. His main research interests are process control and robotics.

    View full text