Freeman / Pieroni Map Data Processing

Proceedings of a NATO Advanced Study Institute on Map Data Processing Held in Maratea, Italy, June 18-29, 1979
1. Auflage 2014
ISBN: 978-1-4832-7215-3
Verlag: Elsevier Science & Techn.
Format: EPUB
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 384 Seiten

Map Data Processing is a collection of papers from a NATO study on the same subject. This collection deals with the exchange of ideas and setting directions in research, particularly in pattern-recognition-, image-processing-, and computer-related issues. The papers discuss the usefulness of computer systems in geographical data processing, as well as the viability of scan digitization resulting from improvements in line thinning and vectorization. Automated spatial data integration can also be helpful in analyzing spatial data, data collection, capture methods, and data characteristics. Another paper addresses the application of the 8-point chain-encoded lineal map data to define more accurate algorithms found in many geographical and medical imagery. One paper considers how the same data used in monochromatic images can be realized for full colored, textured, realist terrain scenes. This book can be a valuable reference for workers involved in areas of geography, computer imaging, cartography, computer graphics, and remote sensing.

Autoren/Hrsg.

Freeman, Herbert

Pieroni, Goffredo G.

Inhaltsverzeichnis

1;Front Cover;1
2;Map Data Processing;4
3;Copyright Page;5
4;Table of Contents;6
5;CONTRIBUTORS;8
6;PREFACE;10
7;CHAPTER 1. A MINICOMPUTER-BASED GEOGRAPHICAL DATA PROCESSING SYSTEM;12
7.1;1. INTRODUCTION;12
7.2;2. HARDWARE;19
7.3;3. SYSTEM SOFTWARE;21
7.4;4. DATA FORMATS;21
7.5;5. USER SOFTWARE;24
7.6;6. CONCLUSION AND OUTLOOK;33
7.7;ACKNOWLEDGMENTS;35
7.8;REFERENCES;36
8;CHAPTER 2. SCAN DIGITIZATION OF CARTOGRAPHIC DATA;38
8.1;I. INTRODUCTION;38
8.2;II. SCANNING;41
8.3;III. LINE THINNING;44
8.4;IV. LINE FOLLOWING;47
8.5;V. LINE WEEDING;49
8.6;VI. ZONING AND DE-ZONING;49
8.7;VII. DE-SYMBOLIZATION;50
8.8;VIII. DISPLAY AND EDIT STATIONS;51
8.9;IX. MANUAL DIGITIZATION;52
8.10;X. AUTOMATIC CORRECTION;53
8.11;XI. PREPARATION PRIOR TO SCANNING;53
8.12;XII. FORMATS;54
8.13;XIII. ECONOMICS;56
9;CHAPTER 3. SPATIAL DATA INTEGRATION;58
9.1;I. INTRODUCTION;58
9.2;II. SPATIAL DATA INTEGRATION;60
9.3;III. SUMMARY;68
9.4;ACKNOWLEDGMENTS;69
9.5;REFERENCES;70
10;CHAPTER 4. A SPATIAL DATA STRUCTURE FOR GEOGRAPHIC INFORMATION SYSTEMS;74
10.1;ABSTRACT;74
10.2;I. INTRODUCTION;74
10.3;II. VECTOR FORMAT SPATIAL DATA;84
10.4;III. RASTER FORMAT SPATIAL DATA;95
10.5;IV. RASTER FORMAT VS. VECTOR FORMAT;100
10.6;V. CONCLUSION;106
10.7;REFERENCES;109
11;CHAPTER 5. DESIGN OF A SPATIAL INFORMATION SYSTEM;112
11.1;I. INTRODUCTION;112
11.2;II. A SPATIAL DATA STRUCTURE;113
11.3;III. THE SPATIAL INFORMATION SYSTEM;117
11.4;IV. DISCUSSION AND CONCLUSIONS;126
11.5;REFERENCES;127
12;CHAPTER 6. WHAT IS A "GOOD" DATA STRUCTURE FOR 2-D POINTS?;130
12.1;INTRODUCTION;130
12.2;REFERENCES;145
13;CHAPTER 7. TREE STRUCTURES FOR REGION REPRESENTATION;148
13.1;1. INTRODUCTION;148
13.2;2. CONVERSION;152
13.3;3. PROPERTY MEASUREMENT;156
13.4;4. CONCLUDING REMARKS;159
13.5;REFERENCES;159
14;CHAPTER 8. ANALYSIS AND MANIPULATION OF LINEAL MAP DATA;162
14.1;1. INTRODUCTION;162
14.2;2. ALGORITHMS;164
14.3;3. CONCLUSIONS;178
14.4;ACKNOWLEDGMENT;178
14.5;REFERENCES;179
15;CHAPTER 9. REPRESENTATION AND RECOGNITION OF CARTOGRAPHIC DATA;180
15.1;1. INTRODUCTION;180
15.2;2. CHAIN CODE;182
15.3;3. POLYGONAL APPROXIMATIONS;184
15.4;4. CONCLUSIONS;198
15.5;REFERENCES;199
16;CHAPTER 10. THE EFFECTS OF GENERALIZATION IN GEOGRAPHICAL DATA ENCODING;202
16.1;I. INTRODUCTION;202
16.2;II. RASTER ACCURACY;203
16.3;III. FRACTIONAL DIMENSIONALITY;207
16.4;IV. SWITZER'S ANALYSIS;208
16.5;V. VECTOR ACCURACY AND SPURIOUS POLYGONS;210
16.6;VI. CONCLUSIONS;214
16.7;REFERENCES;215
17;CHAPTER 11. METHODOLOGICAL OBSERVATIONS ON THE STATE OF GEOCARTOGRAPHIC ANALYSIS IN THE CONTEXT OF AUTOMATED SPATIAL INFORMATION SYSTEMS;218
17.1;THE TOWER OF BABYLON;218
17.2;THE CARTOGRAPHIC DOMAIN;220
17.3;CARTOGRAPHY + COMPUTERS = ?;223
17.4;THE DATA CRISIS;226
17.5;AUTOMATED SPATIAL INFORMATION SYSTEMS;229
17.6;IN CONCLUSION;232
18;CHAPTER 12. THE TRANSFER OF SOFTWARE SYSTEMS FOR MAP DATA PROCESSING;234
18.1;I. INTRODUCTION;234
18.2;II. TRANSFER OF SOFTWARE SYSTEMS;235
18.3;III. CONCLUSIONS;251
18.4;ACKNOWLEDGMENTS;252
18.5;FOOTNOTES AND REFERENCES;253
19;CHAPTER 13. PATTERN RECOGNITION PROBLEMS IN THE CLASSIFICATION OF MULTI-IMAGES;258
19.1;I. PATTERN CLASSIFICATION OF ASSEMBLIES;258
19.2;II. UNSUPERVISED CLASSIFICATION OF IMAGES;272
19.3;ACKNOWLEDGMENTS;274
19.4;REFERENCES;275
20;CHAPTER 14. A COMPARATIVE TEXTURE CLASSIFICATION EXPERIMENT;276
20.1;I. INTRODUCTION;276
20.2;II. TEXTURE FEATURES;282
20.3;III. COMPARATIVE CLASSIFICATION STUDY;286
20.4;IV. SUMMARY;288
20.5;REFERENCES;289
21;CHAPTER 15. SEGMENTATION TECHNIQUES AND PARALLEL COMPUTATION FOR IMAGE PROCESSING;290
21.1;I. INTRODUCTION;290
21.2;II. MAP IMAGES;291
21.3;III. PURPOSE AND MEANING;291
21.4;IV. BASIC DEFINITIONS;292
21.5;V. THRESHOLDING AND EDGE DETECTION;297
21.6;VI. SPLIT-AND-MERGE SEGMENTATION;301
21.7;VII. SEGMENTATION OF A SUBURBAN AREA;303
21.8;VIII. PARALLEL NUMERICAL COMPUTATION;311
21.9;IX. SOME PARALLEL MACHINES;312
21.10;X. SEQUENTIAL VS. PARALLEL IMAGE PROCESSING;313
21.11;XI. CELLULAR LOGIC OPERATIONS;314
21.12;XII. PRACTICAL CLOs;315
21.13;XIII. CONCLUSIONS;316
21.14;REFERENCES;316
22;CHAPTER 16. MAP SEQUENCE PROCESSING;320
22.1;I. INTRODUCTION;320
22.2;II. DYNAMIC SEGMENTATION;325
22.3;III. DYNAMIC STRUCTURE;329
22.4;IV. CONCLUDING NOTES;337
22.5;REFERENCES;339
23;CHAPTER 17. NUMERICAL ALGORITHMS FOR INTERPOLATION AND SMOOTHING;342
23.1;1. INTRODUCTION;342
23.2;2. REPRESENTATION OF FUNCTIONS OF ONE REAL VARIABLE;345
23.3;3. INTERPOLATION OF FUNCTIONS OF TWO REAL VARIABLES;355
23.4;REFERENCES;362
24;CHAPTER 18. COMPUTER GENERATION OF SHADED RELIEF MAPS;366
24.1;I. INTRODUCTION;366
24.2;II. U.S. DEFENSE MAPPING AGENCY DATA;367
24.3;III. EQUATIONS FOR DISPLAYING A SHADED RELIEF MAP;369
24.4;IV. ADDING TEXTURE TO A SCENE;374
24.5;ACKNOWLEDGMENT;376
24.6;REFERENCES;376
24.7;APPENDIX: ALGORITHM FOR VIEWING A HEIGHT FIELD IN PERSPECTIVE;378
25;INDEX;380

Leseproben

SCAN DIGITIZATION OF CARTOGRAPHIC DATA

A. Raymond Boyle,     Department of Electrical Engineering, University of Saskatchewan, Saskatoon, Sask., Canada

The importance of large scale digitization of existing map series is now apparent to most cartographic establishments. Processes of manual and even automatic line following digitization cannot meet the combined needs of data quality, economics and throughput. Scan digitization, on the other hand, has now been shown to be viable, particularly as a result of recent advances in software for line thinning and vectorization. This paper describes one of the methods, together with the data formats used and some of the post-vectorization processes.

I INTRODUCTION

Coincidently at a number of establishments (CGIS, Canada; CSIR, Pretoria; Mathematical Institute, Bonn; University of Saskatchewan, Canada) experiments have shown that scan-to-line vector conversion of cartographic line data can be achieved at a reasonable cost whereas previous reported work had indicated that it would be extremely expensive, so expensive that, in fact, the process could not be considered for other than essential military work. The reason for this change is still not quite clear, as it has not resulted from a sudden new advance in technology; it would appear that it is perhaps the difference in requirement specifications, as a very slight difference in these can rapidly escalate costs.

This change has created a completely new attitude to the ‘mass’ digitization of existing map series; it has also created a need to answer the new problems that immediately arise. It is the aim of this paper to report on the present state of work in scan digitization, the methods being developed and the next problems to be handled.

For the purpose of this paper it is assumed and accepted that the cartographer needs line data in vector line form and that a raster representation of this is not adequate - that is another point which needs full discussion, however. Moreover, it is also assumed that the mass digitization of existing map series is useful and that for such work colour separation sheets are available with well-defined and clear cartographic line presentation. No attention is given here to the ‘possible’ automatic digitization of composite paper maps or of unclear or badly drawn working map compilations, although it is hoped to indicate the limits where ‘clear’ becomes ‘unclear’. With automatic digitization of clear lines, the resulting data is of very high quality requiring little interactive editing. This is a major difference other than the one of cost, from manually digitized maps.

The first attention must be given to the previous bottleneck of scan to line vector conversion. All the programs examined by the writer consist of two parts - line thinning followed by line following. Most use look-up tables, often in a relatively simple manner. While the operation on each pixel of an image is fast, it must be remembered that there are approximately 108 pixels in one map image using the lowest acceptable resolution. It is therefore essential to reduce the number of passes to a minimum, usually two. Other programs have suffered in timing (and thus cost) by the use throughout of a high level language where assembler routines should have been used. In fact the specification of operational time and cost has been obviously missing from many contracts placed with software houses in the past.

It has now been shown that work can be reduced to two passes of the raster scan data and that the total processing time in a series digital computer should be less than 1 minute on a large main frame and less than 30 minutes on a minicomputer, for a complete separation sheet about 25” square. Actually the minicomputer appears to be longer in time but lower in amortized cost.

In order to obtain efficient conversion certain restrictions should be applied to the input document. It now appears that these are not onerous although some of the older routines such as CGIS are too restrictive for production use.

The conditions applicable to the input document are as follows:

1) The lines should be well-defined. Preferably the original work will have been scribed and this is normal for most map series made in the last twenty years. Copy work from the original must be properly controlled in quality.

2) Line weights should be within a specified range (the U-of-S system for example allows a 4:1 ratio).

3) Gaps between lines should be greater than a specified minimum (usually 1 or 2 pixels).

4) Unwanted data should be absent or removed (usually by opaquing).

5) ‘Blob’ symbols and very wide lines (greater than 0.4mm (0.016?)) can cause difficulty in most systems and are catastrophic in some, e.g. CGIS. A ‘blob’ symbol may be a small house block as symbolized on a medium scale map.

It should be reiterated that the discussion is only of the digitization of high quality separation sheets as presently made for colour printing.

II SCANNING

Before examining the scan to line conversion process, it is necessary to understand the scanner operation. Within the last few years, high quality scanners have been made for many applications, particularly for alphanumeric copy work and for the graphic arts industry. At first scanners were used in the analog mode to handle grey scale more easily, but recently digital methods have become more popular. Most use rotating drums and axially moving heads. The better ones have settable resolutions (number of lines per inch) and spot size. Although not essential, these variable facilities are very useful in cartographic work. These drum systems unfortunately tend to be difficult to manufacture and thus become expensive.

It has been reasonably common in graphic arts work to scan an image on one drum and repeat the trace on a scan plotter at the same time. However, the copy that is made can be modified in intensity and contrast, and both of these for selected parts of the image in order to provide enhancement. The same process is used with colour filters on the reading head to produce colour separations for printing purposes.

Many of these scanners can be used for digital scanning of cartographic separations, the signal line being fed to a level discriminator (black/white) before passing to digital logic circuits and a computer storage system.

The drums usually rotate at a constant synchronous speed; 300 rpm is frequently chosen (5 rps) which means that one scan line is output in 0.2 seconds for one complete drum rotation. The timing resolution of this line might be into 10,000 parts over the drum periphery of say 1 meter (40?) (the drum must be large enough for the work in hand). This would also infer 10,000 scan lines for 1 meter axial motion resulting in a total scan time of 2,000 seconds or approximately 40 minutes. This scan time is fixed for a certain resolution and dimensions, independently of the amount of information on the separation.

The new breed of flat-bed laser beam scanners appears to be preferable as constructional costs are lower and speeds can be much higher without excessive dynamic difficulties. The time of full scan can easily be reduced to one tenth of that of the drum without running into any major problems of bit data entry or data storage speeds.

The reader will appreciate that a raster scan is one where the separation sheet is automatically examined step by step, each step being the resolution size, normally of about 0.1 mm (0.004?). The output is similar to that used for a black/white television image, but of much greater resolution. Examining a separation of 1 meter × 1 meter at 250 lines/inch will result in 108 pixels, which must be stored on an attached unit as they are produced. This unit need not be a computer, but often that is the most convenient device. This amount of data is large but it is well within the speed and bulk capabilities with reasonable planning. The pixel data may be stored as on-off (1,0) bits or in a run length encoded form (i.e., distance from last set pixel).

The optimum resolution in lines per inch (and the related spot size) is always an arguable point; 250 lines per inch is suggested by the writer as reasonable. It means that the spacing of scan lines is 0.1 mm (0.004?) each with a set precision of 0.05 mm (0.002?). Thus with a good quality mechanism, a precision of ±0.05 mm (±0.002?) could be expected and, as a data representation, this will be as good as could have been originally drawn by hand. There is no concern here with separation stretch or contraction (providing it is an orthogonal change) as registration marks are automatically digitized along with line data and the × and Y scaling is then automatically corrected. The spot size used will be approximately 0.12 mm (0.005?) to allow slight overlap between lines. The mechanism must produce evenly spaced parallel straight scan lines at a constant travel speed (normally time in the one axis gives position).

Users who think that they should use a higher resolution must remember that a resolution of 500 lines per inch requires four times the data...