الفهرس 
Chapter 1.INTRODUCTIONOnly 14 pages are availabe for public view
 |  | from | 123 |  |  |
| | | from | 123 | | |
Abstract
The wide spreading of geo-aware mobile applications provides the op- portunity for huge amounts of user-contributed GPS trajectories to be available with various levels of accuracy. Constructing road maps is one important benefit of such datasets. Now, many applications rely on road map data to provide their services. However, keeping the road map up- to-date and validating the correctness of generated maps pose interest- ing research challenges. Therefore, the research community has been re- cently interested in proposing alternative means of road map production utilizing the crowd-sourced GPS trajectories. There are some challenges related to the inaccuracies incurred on real datasets, such as missing GPS signals, low sampling rate and bad driving behaviour.
In this thesis, we present a clustering-based method to extract the road map from GPS tracks. Additionally, a new preprocessing algo- rithm is proposed to adapt with the common problems related to GPS data. Firstly, the tracks are simplified to extract road turns, as well as to remove the noise data. In order to handle the problems due to the low sampling rate, we adjust the core points of the simplified tracks by moving them closer to the positions of the real turns. Afterwards, a pro- gressive clustering is applied to extract turns and intersections. Both of them are connected based on the trajectory information. Finally, we
proposed an efficient method to integrate the turn connections to derive the road segments. Our method is different from related work in that it deals with multiple issues related to real datasets, specifically noise, inconsistent and rather low sampling rate, and the difficulty of tuning parameters. We extract both intersections and turns, allowing applica- tions to make better use of such GPS data.
We evaluate the accuracy of our results by comparing the proposed method with two of the best state-of-the-art methods using a small-scale dataset that was collected in Cairo under low sampling rate. Another experiment is conducted by extracting a part of the road segments of Egypt using a large-scale dataset with more than 12 million GPS points that are captured with high sampling rate by thousands of taxis all over Egypt. Experimental results show that our proposed method outper- forms the other methods with regard to F-measure, especially with the low sampling rate datasets. Additionally, the results demonstrate that the proposed method can precisely extract the divided roads that have two lanes of traffic, travelling in each direction and is able to ignore the false trajectories that exist due to GPS errors. Finally, this thesis enriches the area of map production by proposing an efficient method that auto- mates the extraction of the road map from low-sampling-rate GPS trajec- tories. The generated road map is considered a highly-precise routable- map that can be utilized for the purpose of navigation. Furthermore, our method can deal with the complex networks such as the network of Egypt.