Author :- John Carter IWQS home page.
DWA logo

Institute for Water Quality Studies

 Forestry logo

Raster to Vector conversion in a Local, Exact and Near optimal manner.

John Andrew Carter

Pretoria 1991

Abstract

Remote sensing can be used to produce maps of land-cover, but to be of use to the GIS community these maps must first be vectorized in an intelligent manner.

Existing algorithms suffer from the defects of being slow, memory intensive and producing vast quantities of very short vectors. Furthermore if these vectors are thinned via standard algorithms, errors are introduced.

The process of vectorizing raster maps is subject to major ambiguities. Thus an infinite family of vector maps corresponds to each raster map. This dissertation presents an algorithm for converting raster maps in a rapid manner to accurate vector maps with a minimum of vectors.

The algorithm converts raster maps to vector maps using local information only, (a two by two neighbourhood). The method is "exact" in the sense that rasterizing the resulting polygons would produce exactly the same raster map, pixel for pixel.

The method is "near optimal" in that it produces, in a local sense, that "exact" vector map having the least number of vectors.

The program is built around a home-grown Object Oriented Programming System (OOPS) for the C programming language. The main features of the OOPS system, (called OopCdaisy), are virtual and static methods, polymorphism, generalized containers, container indices and thorough error checking. The following general purpose objects are implemented with a large number of sophisticated methods :- Stacks, LIFO lists, scannable containers with indices, trees and 2D objects like points, lines etc.

Dedication

To Rachel, without whom, Life, The Universe, and Everything would have become just plain too much. I.e. > 42

Preface

The project to create a program to perform raster to vector conversion arose for a number of reasons :-

  1. The Department of Water and Sanitation Remote Sensing Section needed to distribute the results of mapping landcover by satellite images.
  2. The existing software was bug-ridden and unsupported.
  3. The major client for our data was the Department's Geographic Information System (GIS). The GIS required vectorised images.
  4. The vectorization software on the GIS took a long time and produced neither optimal nor exact vectors, resulting in resistance to the acceptance of our results in daily use.

This work was made possible by the forbearance of the Department of Water Affairs and Forestry, the requirements of the Catchment Studies section of the Hydrological Research Institute, the support / nagging / useful discussions of my colleagues and the gentle amusement of God.

Part of this work was presented at the EDIS/SAGIS conference held in Pretoria during July 1991.

My thanks also to my proofreaders who revealed curious aspects of their characters by the nature of the errors they found.

Table of Contents.

 

Glossary cum List of Abbreviations.
1. Introduction.
2. OopCdaisy

2.1 What is object oriented programming?

2.1.1 Representation hiding, and Inheritability - an example.

2.1.2 Polymorphism - An illustrative example.

2.2 How does OopCdaisy implement objects?

2.2.1 What is OopCdaisy?

2.2.2 What are OopCdaisy Objects and methods?

2.2.3 The global conception of object methods.

2.2.4 Dynamic vs Static instances of Objects.

2.2.5 How is a new class of objects created?

2.2.6 How is a new class of objects registered with OopCdaisy?

2.2.7 How is an object created?

2.2.8 How is an object used?

2.3 Other OopCdaisy objects.

2.4 OOPS in the literature.

2.4.1 Turbo Pascal 5.5

2.4.2 Oberon

2.4.3 Smalltalk.

2.4.4 Eiffel.

2.5 OOPS in the future.

3. The first phase of raster to vector conversion - Producing Spaghetti.

3.1 Edges, vexils, strings, nodes, knots, spaghetti - some definitions

3.2 An overview of how the Spaghetti Machine works.

3.3 Block classes.

3.4 Starting up the Spaghetti Machine.

3.5 The Spaghetti Machine.

4. Smoothing.

4.1 Exactness.

4.2 How does one find an exact, near-optimal vector representation of a raster image? - an overview.

4.3 Parse the Spaghetti please.

4.3.1 From string of vexils to a character string.

4.3.2 The language of worms.

4.4 Line Space.

4.4.1 Threading the vexils.

4.4.2 Missing the point.

4.4.3 Putting all the constraints together.

4.4.4 Which feasible line? Global versus Near-optimal representations.

4.4.5 Keeping track of the constraints.

5. Linking the Lines.

5.1 Special cases.

5.1.1 When a Link-point is Else When.

5.1.2 Parallel lines.

6. Examples and Discussion.
7. Time complexity of the Algorithm.
8. Conclusions
Bibliography.
Appendix. An Annotated Example.

A.1 Declaring the data structure.

A.2 Registering the object type.

A.3 Implementing the data structure.

A.4 Using the data structure.

Error processing SSI file
Webmaster :- Willie Geldenhuys IWQS's home page.