A METHODOLOGY FOR
RASTER TO VECTOR
CONVERSION OF
COLOUR SCANNED MAPS
OJASWA SHARMA
May 2006
TECHNICAL REPORT
NO. 217
TECHNICAL REP
Abstract
This thesis is an attempt to automate a portion of the paper map conversion process.This includes replacing the manual digitization process by computer assisted skele-tonization of scanned paper maps. In colour scanned paper maps various features on the map can be distinguished based on their colour. This research work differs from the previous research in the way that it uses the Delaunay triangulation and the Voronoi diagram to extract skeletons that are guaranteed to be topologically correct. The features thus extracted as object centrelines can be stored as vector maps in a Geographic Information System after labelling and editing. Further more, map updates are important in any Geographic Information System. This research work can also be used for updates from sources that are either hard copy maps or digital raster images. The extracted features need manual editing in order to be usable in a Geographic Information System. This involves manual gap filling and clutter removal. A prototype application that is developed as part of the research has been presented. This application requires a digital image as input and processes it to produce skeletons or boundaries of objects. This research work can be further extended by considering automated gap filling in the extracted features.
Table of Contents
Abstract ii
Acknowledgments iii
Table of ContentsivList of Figures vii
1 Introduction 1
1.1 Motivation and Problem Definition . .. .2
1.2 Research Objectives . . . . . . . . . . . . . . . . . . . . . . . . . .3
1.3 Methodolgy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
1.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . .4
1.5 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6
1.5.1 Raster Image . . . . . . . . . . . . . . . . . . . . . . . . . . .7
1.5.2 Vector Image . . . . . . . . . . . . . . . . . . . . . . . . . . .9
1.5.3 Map Feature . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5.4 Skeleton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5.5 Object Sampling . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5.6 Delaunay Triangulation . . . . . . . . . . . . . . . . . . . . 13
1.5.7 Voronoi Diagram . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6 Applications of the Proposed Research . . . .. . . . . 17
2 Previous Research 19
2.1 Previous Research on Feature Extraction . . . . . . . . 19
2.1.1 Skeletonization using thinning . . . . . . . . . . . .. . . . . 21
2.1.2 Skeletonization using Distance Transform . . . . . . 25
2.1.3 Skeletonization using Delaunay/Voronoi graphs . .. . 25
2.2 Edge Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.1 Binary Image Edge Detection . . . . . . . . . . . . . . . . . . 27
2.2.2 Gray Scale Image Edge Detection. . . . . . . . . . . . . . . 29
2.2.3 Colour Image Edge Detection . . . . . . . . . . . . . . . . . . 31
2.3 Image Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . 36iv
2.4 Image Segmentation by Mean Shift Algorithm . .. . . 40
2.4.1 Mean Shift Algorithm . . . . . . . . . . . . . . . . . . . . . . 40
2.4.2 Application to Image Segmentation . . . . . . . . . . . . . 42
2.5 The Quad-edge Data Structure . . . . . . . . . . . . . . . . . . . 46
2.5.1 Incremental Construction of Delaunay Triangulation 50
2.5.2 Computation of the Voronoi Diagram . . . . . . . . . . . . 54
2.6 Crust Extraction by Gold . . . . . . . . . . . . . . . . . . . . . 55
2.7 Skeleton Extraction by Anton et al. . . . . . . . . . . 56
3 Extension of Existing Algorithm to Colour Images 60
3.1 Considerations to Process Colour Information . . .... 60
3.2 Colour Image Segmentation . . . . . . . . . . . . . . . . . . 62
3.3 Object Selection from Segmented Image . . . . . . . . . 63
3.4 Object Sample Points Collection . . . . . . . . . . . . . 64
3.5 Boundary and skeleton extraction . . . . . . .. . . . . 66
3.6 The Holistic Picture . . . . . . . . . . . . . . . . . . . . . . . . . 67
4 Skeletonization 73
4.1 Skeleton extraction from the Voronoi Diagram . . .. 74
4.1.1 Obtaining Anti-crust from the Voronoi diagram ... 74
4.2 Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.2.1 Threshold Based Pruning . . . . . . . . . . . . . . . . . . . 77
4.2.2 Pruning by Removing Leaf Edges . . . . . .. . . . . . . . 78
4.2.3 Ratio Based Pruning of the Anti-crust . . . .. . . . . . . 84
4.3 Comparison of the pruning methods . . . . . . . .. . . . 85
5 Results and Comparison 87
5.1 Feature Extraction Process . . . . . . . . . . . . . . . . . . . . . 88
5.2 Results with Scanned Maps . . . . . . . . . . . . . . . . . . . . . 93
5.3 Results with Satellite Imagery . . . . . . . . . . . . . . . . . . 101
5.4 Positional Accuracy of Skeleton and Boundary ...... 106
5.5 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.6 Step Ahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.7 Advantages of this Research . . . . . . . . . . . . . . . . . . . 111
5.8 Limitations of this Research . . . . . . . . . . . . . . . . . . . 112
6 Conclusions and Future Work 114
6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.2 Future Work and Recommendations . . . . . . .. . . . 116
Bibliography 123
Appendices 124
A Matlab code 124
Vita 126
Full Text Click Here
0 تعليقات
شكرا لتعليقك .. سيتم الرد عليكم في اقرب وقت ممكن .
كوكب المنى