New Page 1

ABSTRACT

This paper reports the results of an in-depth study which investigated two algorithms for line simplification and caricatural generalisation, namely those developed by Douglas and Peucker, and Visvalingam respectively. The use of large scale data for man-designed objects, such as roads, has led to a better understanding of the properties of these algorithms and of their utility within the spectrum of scale free mapping. The Douglas-Peucker algorithm is better at minimal simplification. The large scale data for roads makes it apparent that Visvalingam's technique is not only capable of removing entire scale related features, but that it does so in a manner which preserves the shape of retained features. With this technique it is possible to achieve balanced generalisations of an entire map, consisting of several complex lines, using a single tolerance value. This expedites the construction of scale free databases. The results also suggest that it may be easier to formulate concepts for automatic segmentation of in-line features using large-scale road data and Visvalingam's algorithm. The paper also suggests how an even better generalisation, particularly for abstraction of centre lines, may be produced by the inclusion of additional rules when filtering data tagged by Visvalingam's algorithm.

1. Introduction

The main aim of this paper is to explore the utility of Visvalingam's algorithm, reported in Visvalingam and Whyatt (1993), for generalising large scale cartographic data for man made objects, such as roads. As a comparison the properties and behaviour of this algorithm are compared with that of the well known Douglas and Peucker algorithm (1973). Like most other line simplification algorithms, Douglas' algorithm (more widely known as the Douglas-Peucker algorithm) may only be used for modest levels of generalisation. In contrast, Visvalingam's scheme for elimination of points appears to be useful for filtering scale related features and for producing acceptable caricatural generalisations even at fairly gross levels of reduction. The original study by Visvalingam and Whyatt was based an coastline data, captured at the 1:50 000 scale, which were progressively generalised to a 1:10M scale; i.e. it was concerned with relatively small scale applications.

Roads, being man designed features, are relatively smooth compared with coastlines. Given the absence of spiky detail, it was assumed that the two algorithms would perform equally well and that only a small proportion of points could be omitted during minimal simplification; i.e. before the shape of the roads became noticeably altered. Visvalingam and Whyatt had identified some limitations of Visvalingam's method and had indicated a need for further testing. The application of this algorithm to large-scale data was undertaken to study its behaviour and limits of applicability.

This research forms part of an on going project on map generalisation and scale free mapping. Given that roads are engineered to be straight or smoothly curving, we assumed that there would be limited scope for data compression through point elimination. The polygonal outlines of roads in large scale maps are normally collapsed to their centre lines in small scale displays. Road centreline networks, such as the OSCAR product of the Ordnance Survey of Great Britain, are usually digitised manually. Although algorithms have been developed for skeletonising objects such as scissors (Ogniewicz and Ilg, 1986), the process of reducing road networks, with complex junctions and polygonal descriptions, to their skeletons has yet to be automated. An initial requirement is to segment the network into its constituent elements. Both processes of recognition of parts and their skeletonisation benefit from generalisation of data. An aim of this study was to investigate whether Visvalingam's technique was useful for pre processing data for automatic derivation of centre lines. It is widely known that the Douglas-Peucker algorithm is not capable of achieving caricatural generalisation (see review and analysis by Visvalingam and Whyatt, 1990) . This study indicates that the Douglas-Peucker algorithm is better than Visvalingam's technique for minimal simplification. The latter is more suitable for caricatural generalisation. It also revealed some other useful properties of Visvalingam's algorithm which may be used to structure and compress data in scale-free mapping.

In the next, background, section the paper briefly reviews the two algorithms and describes the data used in this study. It then presents some of the results and discusses their implications. The paper concludes by summarising the main properties of Visvalingam's algorithm for line generalisation.

2. Background

In this section we briefly review and compare the algorithms designed by Douglas and by Visvalingam respectively. Only these two methods are compared here since they are both extremely simple in design and easy to implement compared with some other algorithms, such as those described by Deveau (1985), Dettori and Falcidieno (1982) and Beard (1991). It is also easy to comprehend the cartographic implications of their geometric processing. In addition, the Douglas-Peucker algorithm still remains the most widely used in Digital Cartography and in Geographical Information Systems.

Visvalingam and Whyatt (1990; 1991 a & b) provided a detailed background and evaluation of the Douglas Peucker algorithm. Only the gist of the Douglas-Peucker algorithm is provided here. It was initially developed as a weeding algorithm for removing spurious variations in digitised lines which fall within the width of the source graphic line. In pattern recognition, Ramer (1972) had already established a more refined version of this algorithm for deriving a minimal description of plane curves and had observed some of its limitations. The method for weeding consists of joining the two ends of the line with a straight line, called the base line. The perpendicular distances of all intermediate points from this base line are then calculated. lf all these distances are less than some pre defined tolerance, representing half the width of the graphic line at source scale, these points may be discarded and the original line can be represented by the base line. If any of the intermediate points fall outside the tolerance band, the line is split into two parts at the furthest point and the process is repeatedly applied to the two resulting parts. This method has been used for line generalisation by selecting a tolerance value attuned to the target scale. It has also been used to rank points into a hierarchy, which reflects their order of selection and their importance within this scheme.

Visvalingam and Whyatt (1991 b) explained why the use of the tolerance band for elimination of points was reasonable. However, the selection of the furthest point outside the band, as a critical point to be retained, is unreliable as this point may be located an spikes (errors) and on minor features. Manual line generalisation is more concerned with preserving salient shapes than with selecting specific points. Indeed, it is very difficult to hand pick precise points on natural features in a consistent way. Visvalingam's technique is based an the observation that it is easier to eliminate entire features (Visvalingam and Whyatt, 1993). Unfortunately, the automatic identification of geomorphic features remains an outstanding problem in Digital Cartography. Although Visvalingam's technique is point based, it is conceptually oriented towards removing triangular geometric features. The algorithm makes multiple passes over the line. On each pass, it eliminates the point which it regards as least important; a variety of metrics may be used to measure the importance of points. Visvalingam and Whyatt (1993) tested the concept of effective area. This measures the area by which the current line would be displaced as a result of removing that point; i.e. it is the area of the triangle formed by connecting the point with its two neighbours. When a point is removed the effective areas of adjacent points need to be recalculated before the next pass. The theoretical ideas and pseudocode for this algorithm are presented and explained in greater detail by Visvalingam and Whyatt (1993).

The Douglas Peucker algorithm has been in use for some twenty years and has been widely studied. Visvalingam's technique is relatively new and there is a need for further testing. Whyatt (1991) obtained better results with Visvalingam's algorithm than with others by Douglas, Dettori and Falcidieno (1982) and Roberg (1985). Visvalingam and Whyatt (1993) demonstrated that Visvalingam's technique can filter out features within features progressively and thus achieve both minimal and caricatural generalisation. The Douglas Peucker method is only suitable for minimal simplification. Also, Visvalingam's technique uses fewer points when representing the same shapes. However, Visvalingam and Whyatt (1993) regarded their findings as just one step towards a more intelligent system for line generalisation and pointed out some limitations.

The evaluation of the two algorithms in this paper is based on a sample of roads from the 1:1250 OSBASE data created by the Ordnance Survey for experimental purposes. This database has now been superseded by other experimental products. The nature of the link-and-node structured OSBASE data and the complex process of extraction of roads were described by Varley and Visvalingam (1994). Data for complex road polygons in a 500 x 500m area (shown in Figure 1) are used in this paper. The co-ordinates were digitised to 5 cm precision. The data were pre-processed as follows. All the map edge links were removed from the road polygons. This segments the road polygon into 23 road sections. Some of these start and end at the map edge while others form closed loops describing the islands in roads. The road boundary sections are thus anchored to the map edge so that the connectivity of the road network across map sheets could be maintained. Since the algorithms always retain at least the two end points on each section, the figures for percentage of points retained in Table 1 have been calculated after discounting these end points.

3. Observations

Visvalingam and Whyatt (1993) pointed out that the inclusion/omission of a few points could markedly alter the shape of a line, particularly at gross levels of generalisation. It is therefore inappropriate to select fixed percentages of points when comparing the two methods. In this study, an effort was made to find cut-off values which provide comparable numbers of points but which do not bias the shapes in favour of a particular method.

Detailed exploratory analysis revealed that the road boundaries encode various types of detail, namely:

(a) small irregularities an the road which do not significantly alter the shape of lines at source scale
(b) gently curving sections at filleted junctions and roundabouts
(c) minor features, e.g. lay byes, metalled entrances to drives, roundabouts
(d) small branch roads
(e) major branch roads
(f) large features, such as car parks and large islands in roads

The tolerance values listed in Table 1 were selected to demonstrate the performance of these two algorithms at filtering out these types of features. The effect of these various cut offs are noted below.

3.1 Minimal Simplification
The effects of weeding and minimal simplification were studied using the section of the line extending from A to B in Figure 1, which consists of 268 points (266 internal points) and maps drawn at larger than source scale. These maps did not show any noticeable displacement of the source line using a 1 mm (0.125 m on ground) tolerance. Both methods may be used to weed over 55% of internal points.

Visvalingam and Whyatt (1993) were able to achieve good minimal simplification of coastlines with just 23% of points. However, with this data set, it was possible to visually detect deviation from the original line with even 35% of points; see Figure 2a, which was originally drawn at slightly larger than 1:1250 scale. The original line is shown as a dotted line and the simplified line is shown as a solid line. The simplified line in Figure 2a is noticeably displaced from the original line. Figure 1 shows that the majority of points occur along curves. Visvalingam's technique is tending to cut curves, which are better preserved by the Douglas Peucker algorithm.

The differences between the two methods have become more noticeable in Figures 2b and 2c. It is apparent that Visvalingam's technique is cutting curves but even the Douglas Peucker algorithm is beginning to drop points an curves and, more importantly, to displace the course of the line. Figure 2d shows that the Douglas-Peucker algorithm is able to retain all the features in the map using less than 20% of internal points although some displacement of the lines is noticeable even at reduced scale. Visvalingam's technique is beginning to drop points an minor features. It appears that the Douglas Peucker algorithm is better than Visvalingam's area based method for minimal simplification. It requires fewer points for minimal simplification of large scale data. This contradicts the observations made by Visvalingam and Whyatt (1993) in the context of small scale data.

3.2 Elimination of Minor Features

The tolerance values had to be selected more carefully for this level of generalisation. Figure 3ai illustrates the best shape which could be achieved with the Douglas-Peucker method. There is noticeable displacement of the course of the lines. In comparison, Visvalingam's technique shows no such marked deviation from the original line except at curves. When the same tolerance is applied to the whole map (Figure 3bii), minor features such as lay byes, metalled entrances to roads and very narrow islands in roads are removed. The curves at road junctions and the curved sections of road islands have become truncated. In contrast, the Douglas-Peucker algorithm (Figure 3bi) produces less satisfactory results. The curves and minor features are only partially retained distorting the shapes of roads. The use of large-scale data reveals that Visvalingam's technique tends to short-cut curves, which was not noticed by Visvalingam and Whyatt (1993).

3.3 Elimination of Major Features

The Douglas Peucker algorithm retains extreme points at the expense of overall shape with around 5% of points (Figures 4a and 4b). In comparison, Visvalingam's technique drops entire features (such as branch roads) whilst retaining the shape of the main feature. It would be interesting to see what the Whirlpool program, based an Perkal's algorithm, would make of such lines. Would it leave roundabouts behind as detached sections of roads given that it segmented heads of estuaries and left them behind as lakes in Beard (1991)?

Figure 4c shows that Visvalingam's technique can produce an appropriate shape even using just 2 internal points. Figures 4d and 5 demonstrate the well known fact that the Douglas Peucker algorithm cannot be used for caricatural generalisation.

Visvalingam and Whyatt (1993) observed that Visvalingam's algorithm has the effect of omitting scale related features in their entirety. This study reveals that the shape of the retained features are fairly well preserved even at gross levels of generalisation.

4. Discussion

Visvalingam and Whyatt (1990) noted that the most distant point from an anchor floater point selected by the Douglas-Peucker method has a tendency to fall on minor features. The designation of these extreme points as critical points and their retention inhibits the scope for achieving caricatural generalisation. In contrast, Visvalingam's technique has the effect of progressively removing scale-related features at increasing levels of generalisation even though the technique itself does not have any intelligence as yet to recognise features as such. The present study draws attention to aspects of the algorithm which were not obvious when using small scale data.

Firstly, Visvalingam's technique initially eliminates points on smoothly varying curves since they are more closely spaced and result in small effective areas. A slightly offset or redundant intermediate point on a long straight section can still subtend a larger area. Thus, offset based methods are better at weeding and minimal simplification. Visvalingam's method works on the part generalised line and not the original line. As a result the generalised line can become progressively displaced from the original line in smoothly curved sections resulting in noticeable truncation of filleted corners.

Initially, this was seen as a defect but on reflection this was appreciated as the most significant and useful property of the algorithm. For it is the same process of working relative to the current, rather than the original, line which enabled Visvalingam and Whyatt (1993) to produce appropriate scale related caricatures of Carmarthen Bay and which results in the progressive elimination of scale-related features in roads and coastlines. Although the results produced by Visvalingam and Whyatt gave the impression of an elimination of scale-related features, they pointed out that they could not use it in its present form to automatically segment the coastline into its constituent features except when a number of adjoining points were eliminated together, for example an the River Ouse and Spurn Head. It could be argued that even manual segmentation of lines describing natural coastlines is likely to be problematic and subjective. In contrast, the truncation of curves on man designed artefacts makes them automatically detectable.

Secondly, this truncation of curves by Visvalingam's technique also allows us to adopt better strategies for both representing and generalising the road. We could continue to represent the truncated curve as a detached list of points and use the Nth point algorithm to select a scale determined subset. Or, we could store the curve in compact parametric form and generate the appropriate number of points. Moreover, the fact that the original line refers to a road enables us to add additional semantic labels to curves since curves only occur in particular contexts within roads; for example, at junctions and roundabouts. In the context of road centre line calculations (which was one of the original reasons for this study) the detection of such a feature could be used to trigger the search for corresponding elements. Thus, the output of Visvalingam's technique is potentially more useful than that produced by the Douglas-Peucker algorithm.

Thirdly, Visvalingam's technique also drops minor features, such as entrances to driveways, relatively early before distorting the distinctive shape of the road. The removal of these unwanted features again expedites centre line calculations; i.e. more abstract structural generalisation. The results also suggest that it may be possible to automatically segment branch roads. The automatic segmentation and detection of sub-features will not only facilitate the automatic derivation of the road centre line network, but it will also enable the incorporation of a rule base to expedite the selection/omission of parts of the road boundary on application defined criteria.

Also, seeing is a constructive process. Whereas, even highly stylised caricatures of natural features, such as coastlines, are acceptable, we tend to reject shapes which do not coincide with our expectations of designed artefacts, such as roads. The shapes output by the Douglas Peucker algorithm do not correspond to our expectations of roads at gross levels of generalisation (see Figure 5i). We tend to expect the shapes of such features to correspond to their transport functions. Even at fairly gross levels of generalisation, the shapes output by Visvalingam's technique, though not entirely acceptable, are still recognisable as roads.

Finally, in Figure 5, the map generalised using Visvalingam's algorithm has also become unbalanced and some roads have acquired a funnel shape. However, these problems arise partly as a result of edge effects. Normally, such extreme generalisation would only be undertaken when this data forms a part of data for a much larger area. When part generalised data for adjacent sheets are seamed together, it is highly unlikely that the end points of lines falling an the map edge will be retained. The automatic removal of these points on seaming will correct the funnel shapes. Also, some of the smaller feeder roads, such as A in Figure 5, are likely to be dropped while small blocks of intervening land, such as C in Figure 1, are likely to be retained or correctly processed when seamed with adjoining sheets. Figure 3bii shows another problem. One narrow island in the road (D in Figure 1) was eliminated before the others. This could pose a problem in centre line caiculation. However, the metrics and rules driving Visvalingam's technique can be adapted to ensure that all the necessary elements are retained for centre line calculation. For example, a rule that each polygon must be represented by at least two internal points would overcome this problem.

5. Summary and Conclusion

This study suggests that applications which work with a subset of large-scale data, such as roads, could derive space and time savings through use of line simplification methods. Both the Douglas-Peucker and Visvalingam's algorithms need only about 40% of the original points for minimal simplification, i.e. before shape distortions become noticeable. The Douglas Peucker algorithm is superior to Visvalingam's method when it comes to minimal simplification of roads an 1:1250 maps using a tolerance of less than one to two metres.

Further elimination of points produces effects which are noticeable even an reduced displays. With the Douglas-Peucker method, the retention of extreme points results in the distortion of shapes. In contrast, Visvalingam's technique progressively eliminates scale related features. The Douglas-Peucker algorithm cannot be used with a single tolerance to generalise satisfactorily even a single complex line, such as AB in figure 1, (see discussion in Visvalingam and Whyatt, 1990). This paper has shown for the first time that it is possible to achieve a balanced generalisation of an entire map consisting of several lines using a single tolerance with Visvalingam's algorithm.

Visvalingam and Whyatt (1993) noted that the progressive elimination of smaller features, such as rivers feeding into estuaries, provides some scope for segmentation of features for intelligent generalisation. Once segmented, the rivers could be subjected to minimal simplification, or they may be collapsed into their centre lines or be completely omitted to suit the scale and purpose of the map. The same ideas are applicable in the context of large scale data. When viewed within such a range of generalisation possibilities, McMaster's (1987) mathematical criteria (for example areal and vector displacement relative to the original line) for comparing algorithms seem inappropriate particularly for caricatural generalisation.

By offering some prospects for the clean segmentation of lines into substantive constituents, Visvalingam's approach also encourages the use of more intelligent procedures for the recording and display of lines. For example, the chord truncation of filleted corners, enables us to either represent the fillets in parametric form or to flag the filleted segment for Nth point sampling. Given that it is possible to automatically extract roads (Varley and Visvalingam, 1994), it should be possible to include semantic rules for recognising truncated features such as roundabouts an cul-de-sacs, curves at road junctions, branch roads and so on.

The methodology for automatic segmentation of lines into constituent features is still the subject of research. It appears that the rules and procedures for achieving this would be easier to discover using data for man made features than for natural features. Large scale data for roads form ideal input for this future research.

ACKNOWLEDGEMENTS

This research was undertaken without funding. However, we are grateful for a grant from the UK Training and Enterprise Council to Peter Williamson which enabled him to acquire relevant expertise through an MSc Conversion course in Information Technology and Manufacture in the Department of Computer Science, University of Hull. We are also indebted to the Computer Centre of the University of Hull for providing Peter Williamson with continuing access to their facilities for this research. We would like to thank John Farrow, formerly of the Ordnance Survey, for permission to use the OSBASE road data and past research students in the Department of Computer Science of the University of Hull, especially Dominic Varley for supplying the data as a set of polygons and Phil Wade for permission to use his implementation of the Douglas Peucker algorithm. Special thanks go to Alan Whitaker, our Computer Systems Manager, for substantially improving the quality of the original figures by generating PostScript directly from the original map coordinates and for double checking the table, all in the spirit of camaraderie

REFERENCES

Beard, K M (1991) "The Theory of the Cartographic Line Revisited", Cartographica 28 (4) 32-58.

Dettori, G and Falcidieno, B (1982) "An algorithm for Selecting the Main Points on a Line", Computers and Geosciences 8 (1), 3-10.

Deveau, T J (1985) "Reducing the Number of Points in a Plane Curve Representation", Proc. Auto Carto 7, Washington D.C, 152-160.

Douglas, D H and Peucker, T K (1973) "Algorithms for the Reduction of the Number of Points Required to Represent a Digitised Line or its Caricature", The Canadian Cartographer 10 (2), 112-122.

McMaster, R B (1987) "Automated Line Generalisation", Cartographica 24 (2) 74-111.

Ogniewicz R and Ilg M (1986) "Skeletons with Euclidean Metric and Correct Topology and their Application in Object Recognition and Document Analysis", Proc of 4th Int Symp of Spatial Data Handling Zurich 1986, Int. Geog Union, 15-24.

Ramer, U (1972) "An Iterative Procedure for the Polygonal Approximation of Plane Curves", Computer Graphics and Image Processing 1, 244-256.

Roberge, J (1985) "A Data Reduction Algorithm for Planar Curves", Computer Vision, Graphics and Image Processing 29, 168-195.

Varley D A and Visvalingam M (1994) "Road Extraction and Topographic Data Validation using Area Topology", Computer J 37 (1), 3 - 15

Visvalingam, M and Whyatt, J D (1990) "The Douglas Peucker Algorithm for Line Simplification: Re evaluation through Visualisation", Computer Graphics Forum 9 (3) 213-228.

Visvalingam, M and Whyatt, J D (1991 a) "Cartographic Algorithms: Problems of Implementation and Evaluation and the Impact of Digitising Errors", Computer Graphics Forum 10 (3) 225-235.

Visvalingam, M and Whyatt, J D (1991 b) "The Importance of Detailed Specification, Consistent Implementation and Rigorous Testing of Cartographic Software", in K. Rybaczuk and M. Blakemore (eds) Mapping The Nations vol 2, 15th Conference of Int. Cartographic Assoc. (September, Bournemouth) 856-859.

Visvalingam, M and Whyatt, J D (1993) "Live Generalisation by Repeated Elimination of Points", Cartographic J 30 (1), 46-51.

Whyatt, J D (1991) "Visualisation and Re evaluation of Line Simplification Algorithms", Unpublished Ph D Thesis, University of Hull, 259 pp.