“A Fast and Economic Scan-to-Line-Conversion Algorithm” by Woetzel

In order to generate cartographic data bases, it is necessary to digitize a large number of existing base maps. One way of replacing the error-prone and very time-consuming manual digitization by an automatic method is scanning the map and extracting the linework from the resulting binary matrix. A sufficiently fast and economic scan-to-line-conversion algorithm has to be developed for the line extraction.

The algorithm presented operates with a skeletonization technique which is further developed from known line thinning methods, so that the scan lines are now skeletonized in a single pass and that only a small number of scan lines has to be held in core storage. The result of this process is equivalent to a multi-pass skeletonization which utilizes a quasi-parallel line thinning in four partitions of the binary matrix for each pass.

The data produced by the extraction algorithm following the skeletonization have two important advantages over data produced by manual digitization: First, the nodes corresponding to the line end points are exactly determined and, second, the correction phase is shortened since the automatic process is less error-prone.

Time and storage requirements of the implemented algorithm applied to some typical scan data show that the conversion for even a complex line structure can be carried out within the time of scanning and the economic use of core storage makes it possible to implement the algorithm on a minicomputer with an on-line scanner.

1. Boyle,A.R., The present status of automated cartography. Computer Graphics (ACM-Siggraph), 9(1975), pp.260-266 
2. Gray,S.B., Local properties of binary images in two dimensions. IEEE Trans. Computers C-20(1971), pp. 551-561
3. Kansy,K., Capture and encoding of area-oriented geographic maps. To appear in: the 3 rd Jerusalem Conference on Information Technology (JCIT) 1978.
4. Klein,K.H., Kreifelts,Th., Pick,K., Woetzel,G., Erfahrungen mit der Digitalisierung von rastermäßig erfaßten Linienstrukturen II. GMD-Mitteilungen Nr. 37, St.Augustin,West Germany,1976.
5. Kreifelts,Th., Pick,K., Wisskirchen,P., Woetzel,G., Erfahrungen mit der Digitalisierung von rastermäßig erfaßten Linienstrukturen I. GMD-Mitteilungen Nr. 30, St.Augustin, West-Germany,1974.
6. Kreifelts,Th., Woetzel,G., Extraktion von Linienmustern aus Binaumlrbildern. To appear in: Kazmierczak,H.(ed), Maschinelle Bildverarbeitung, Springer Heidelberg-Berlin-New York.
7. Mylopoulos,J.P., Pavlidis,T., On the topological properties of quantized spaces I. J.ACM 18 (1971) pp.239-246. 
8. Rosenfeld,A., Connectivity in digital pictures. J.ACM 17(1970), pp.146-160. 
9. Tomlison,R.F.,(ed.),Geographical Data Handling. Int.Geographical Union Second Symposium on Geographical Information Systems, Ottawa,Canada, 1972.
10. Woetzel,G.,Linien- und Knotenextraktion aus Rasterbildern, GMD-Mitteilungen Nr. 44, St.Augustin, West-Germany,1978.