Quantitative evaluation of trajectory based road map construction algorithms

Abstract

In recent years there is a positive trend in the use of quantitative evaluation to assess performance of trajectory based road map construction algorithms. But little effort has been made in to how such an evaluation should be performed. This thesis addresses this problem with the aim of determining how to perform a proper quantitative evaluation. We discern two problems with the current evaluation methodology. The first problem being that the same few public test cases are being used throughout the literature. These test cases only give insight of algorithm performance under very specific circumstances and are provided with ground truth maps that contain roads impossible to be inferred. The second problem involves the evaluation measure with which a similarity is determined between the ground truth and a constructed map. The graph sampling similarity measure introduced by Biagioni and Eriksson is mostly used in the literature. However, little effort has been made in assessing its evaluation performance. To address these problems, we propose a new evaluation framework using synthetically generated trajectories, with which we can investigate algorithm performance under a variety of circumstances. We additionally provide a working public implementation and use it to evaluate two state-of-the-art map construction algorithms. Finally, for the graph sampling measure, we perform a thorough analysis using multiple experiments. By doing so we provide insight in its strengths, shortcomings and proper usage.