Map Digitizing

The aim of this project is to convert a scanned topographic map into digitized data.

Abstract
The aim of this project is to convert a scanned topographic map into digitized data.
The data includes:

  • Topographic data (DTM)
  • 1-D data (places of wells, electric poles etc.)
  • Curves data (Rivers, electric line, etc.)
  • Surfaces data (Seas, lakes, Mudded areas etc.)

 

The problems

We’ve divided the main problem to three, separate problems:

  • Colors separation problem
  • Pattern recognition problem
  • Logical problems

Colors separation problem

The map is printed using 4 different colors: brown, black, blue and green, the first stage is to make 4 layers of the map, each layer contains the information which is printed in specific color.

This stage will make further identification of patterns much easier.

Methods we used

To separate the colors, we’ve transformed the colors of the image to the RGB space, and we’ve tried to find the basis colors of the printer.
After the basis colors were found, we’ve quantized the image, we had a problem when two colors where printed at the same place, and we’ve used filters to solve this problem.

1

Pattern recognition problem

After separating the map to four colors layers, the next stage is to recognize the various signs which is being used on the map.
The patterns are – straight lines (the UTM grid), curved lines (rivers and roads), circles (wells), characters (contours heights, names) and so on.

Methods we used
We used several filters to recognize simple patterns (as circles), and algorithms that uses more complicated filters to recognize characters. To recognize straight lines we used radon/hough transforms, while finding curved lines required a simple algorithm that completes erased or dashes lines, the algorithm solved an optimization problem in order to find two nearest lines which their directions are approximately the same.
2
We’ve also used morphological operations in order to find end of lines or directions of lines (operations as erosion, dilation, skeletoning and labeling).

Logical problems

In order to build a DTM (Digitized Terrain Mapping) from the contours, one should first assign a height to every curve. This is not an intuitive problem, especially when the curves do not close inside the scanned part of the map.

3
Another problem is how to interpolate the contours points, in order to assign a height to every point on the DTM.

4

Methods we used

When the curves are closed, we used a graph to describe the curves; in the graph every vertex is a curve and every edge represent ‘containity’, The root of the graph is the curve which contains all other curves , etc.

Now, we can use BFS (Breadth-first search) and every layer in the graph will be assign a height according to it’s distance from the root.

In order to assign height to an open curve, we’ve used two different methods:

The first methods used information about wadis; When a wadi crossed (in the map) a contour, we can know which side of the curve is higher according to the direction of the wadi.

The second method is two iterations method: in the first iteration we use the closed curves only, and assign heights to every point on the map, in the second iteration we decide which side of every unclosed curve is high according to the approximation which was made in the first iteration.

After assigning height to every contour, we used several methods of non-uniform interpolation in order to assign a height to the point. The final method we used is an approximation to the ideal interpolation, it works on X and Y axis separately and takes the average.

Results

5

Tools:

Matlab version 6.5 was used, especially Image Processing toolbox, but some other toolboxes also.
A simple scanner was used to scan the maps (UMAX 3400).

When the curves are closed, we used a graph to describe the curves; in the graph every vertex is a curve and every edge represent ‘containity’, The root of the graph is the curve which contains all other curves , etc.

Bibliography

    • Digital Image Processing / R.C.Ronzalez, P.wintz, Addison Wesley
    • Machine Vision / R.jain , R. kasturi, B.G. schunck , McGraw Hill 1955
    • Digital Image Processing / K. Castleman , Prentice – Hall 1979
    • Computer Vision – A Modern Approach / D.A.forsyth, J.Ponce , Prentice – Hall 2003
    • Computer Graphics – Principles and Practice (2nd Edition in C). J.D.Foley, A.Van-Dam, S.K.Feiner and J.F.Hughes. Addison-Wesley, 1996
    • Computational Geometry: Algorithms and Applications (2nd ed.), M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Springer-Verlag, 2000

Acknowledgments
We would like to thank our supervisor Johanan Erez for his support and guidance throughout this project.
We would like to thank The Ollendorff Minerva Center Fund who supported this project.