UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The application of interactive graphics and pattern recognition to the reduction of map outlines Clement, Andrew 1973

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-UBC_1973_A6_7 C47_4.pdf [ 4.47MB ]
Metadata
JSON: 831-1.0052003.json
JSON-LD: 831-1.0052003-ld.json
RDF/XML (Pretty): 831-1.0052003-rdf.xml
RDF/JSON: 831-1.0052003-rdf.json
Turtle: 831-1.0052003-turtle.txt
N-Triples: 831-1.0052003-rdf-ntriples.txt
Original Record: 831-1.0052003-source.json
Full Text
831-1.0052003-fulltext.txt
Citation
831-1.0052003.ris

Full Text

C.0T5CJ 3 THE APPLICATION OF INTERACTIVE GRAPHICS AND PATTERN RECOGNITION TO THE REDUCTION OF MAP OUTLINES by Andrew Clement B.Sc., U n i v e r s i t y of B r i t i s h Columbia, 1968 A t h e s i s submitted i n p a r t i a l f u l f i l l m e n t of the requirements f o r the degree of Master of Science i n the Department of Computer Science We accept t h i s t h e s i s as conforming to the r e q u i r e d standard The U n i v e r s i t y of B r i t i s h Columbia March 1973 In presenting t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of the requirements f o r an advanced degree at the U n i v e r s i t y of B r i t i s h Columbia, I agree that the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r reference and study. I f u r t h e r agree that permission f o r extensive copying of t h i s t h e s i s f o r s c h o l a r l y purposes may be granted by the Head of my Department or by h i s r e p r e s e n t a t i v e s . I t i s understood that copying or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l gain s h a l l not be allowed without my w r i t t e n permission. Department of The U n i v e r s i t y of B r i t i s h Columbia Vancouver 8, Canada Date A b s t r a c t Techniques from i n t e r a c t i v e g r a p h i c s and p a t t e r n r e c o g n i t i o n are a p p l i e d to the problem of reducing map o u t l i n e s . S i n c e the r e s u l t i n g g e n e r a l i 2 e d o u t l i n e s are intended f o r use i n i n t e r a c t i v e g r a p h i c s systems t h e i r data content should be c o n s i d e r a b l y l e s s than t h a t of the o r i g i n a l l i n e s . A l s o i t i s u s e f u l to have s e v e r a l l e v e l s of g e n e r a l i z a t i o n f c r the same l i n e and an e x t e n s i o n of the X-Y c o o r d i n a t e encoding scheme i s i n t r o d u c e d to r e p r e s e n t such h i e r a r c h i c a l l y reduced . l i n e s . Experiments are conducted t h a t suggest that people l c o k at o u t l i n e s i n d i f f e r e n t ways. To accomodate these d i f f e r e n c e s i n t a s t e and purpose the system i s designed to adapt to the i n d i v i d u a l u s e r ' s p r e f e r e n c e s . T h i s i s dene by having the user reduce s e v e r a l o u t l i n e s by hand. The system analyzes p a t t e r n s i n these l i n e s and so l e a r n s to mimic the user's behaviour. Once enough has been lea r n e d the system i s given new l i n e s to g e n e r a l i z e on i t s own. Experiments are performed to measure the l e a r n i n g a b i l i t y and the g e n e r a l i z a t i c n performance. Other e x p e r i n e n t s are performed to show the p o t e n t i a l f e a s i b i l i t y of t h i s approach. There i s a review of work dene i n r e l a t e d f i e l d s . i i T a ble of Contents I n t r o d u c t i o n 1 Chapter I Related Work 1.0 I n t r o d u c t i o n .3 1.1 C a r t o g r a p h i c G e n e r a l i z a t i o n 3 1.2 Psychology of P e r c e p t i o n 7 1.3 P a t t e r n Recognition and Learning 8 1.1 L i n e Encoding Schemes 12 1.5 L i n e Reduction 14 1.6 I n t e r a c t i v e Graphics 16 Chapter I I Methods and Techniques 2.0 I n t r o d u c t i o n 21 2.1 Line Representation 21 2.2 Manual I n t e r a c t i v e A l t e r a t i o n of L e v e l s 25 2.3 Learning 27 2.4 Automatic G e n e r a l i z a t i o n 33 Chapter I I I Experimental R e s u l t s 3.0 I n t r o d u c t i o n 34 3.1 P e r c e p t u a l Response to G e n e r a l i z a t i o n 34 3.2 L o c a l Reduction 40 3.3 The System's G e n e r a l i z a t i o n Performance 43 3.4 Other Questions 49 i i i Chapter IV Evaluation 4.0 Introduction 50 4.1 Critical Summary 50 4.2 Future Work , 54 4.3 Ethical'Concerns 55 4.4 Conclusions 56 Bibliography 57 XV L i s t of Tables Table 3.1 R e s u l t s f o r Experiment I page 35 Ta b l e 3.2 R e s u l t s f o r Experiment II 35 Table 3.2 R e s u l t s f o r Experiment I I I 41 Table 3.4 Learning S t a t i s t i c s 45 Table 3.5 Learning R e s u l t s 45 Table 3.6 G e n e r a l i z a t i o n R e s u l t s 45 V L i s t o f F i g u r e s C h a p t e r I F i g u r e 1.1 f o l l o w i n g page 5 F i g u r e 1.2 5 F i g u r e 1.3 5 F i g u r e 1.4 8 F i g u r e 1.5 8 F i g u r e 1.6 10 F i g u r e 1.7 12 F i g u r e 1.8 12 F i g u r e 1.9 12 F i g u r e 1.10 12 F i g u r e 1.11 13 F i g u r e 1.12 13 C h a p t e r I I F i g u r e 2.1 21 F i g u r e 2.2 21 F i g u r e 2.3 21 F i g u r e 2.4 22 F i g u r e 2w5 22 F i g u r e 2.6 22 F i g u r e 2.7 22 F i g u r e 2.8 22 F i g u r e 2.9 26 F i g u r e 2.10 26 v i F i g u r e 2.11 28 F i g u r e 2.12 28 Figure 2.13 30 F i g u r e 2.14 30 Chapter I I I Figure 3.1 35 F i g u r e 3.2 3 5 Figure 3.3 35 Figure 3.4 3 5 . F i g u r e 3.5 37 F i g u r e 3.6 37 F i g u r e 3.7 40 F i g u r e 3.8 42 F i g u r e 3.9 42 Figure 3.10 42 Figure 3.11 42 F i g u r e 3.12 42 F i g u r e 3.13 42 F i g u r e 3.14 42 F i g u r e 3.15 43 Figure 3.16 43 F i g u r e 3.17 43 F i g u r e 3.18 44 Figure 3.19 44 F i g u r e 3.20 44 v i i F i g u r e 3.21 44 F i g u r e 3.22 44 F i g u r e 3.23 45 Figure 3.24 46 Figure 3.25 ' 46 F i g u r e 3.26 46 Figure 3.27 46 F i g u r e 3.28 46 F i g u r e 3.29 47 F i g u r e 3.30 47 F i g u r e 3.31 48 F i g u r e 3.32 48 F i g u r e 3.33 48 F i g u r e 3.34 48 Figure 3.35 48 F i g u r e 3.36 48 F i g u r e 3.37 48 Figure 3.38 48 Figure 3.39 48 Figure 3.40 48 Chapter IV Figure 4.1 50 F i g u r e 4.2 50 F i g u r e 4.3 50 F i g u r e 4.4 51 v i i i Many people have helped me in my work and in the preparation of this thesis. To all these people I give my thanks. I am especially indebted to Frieder Hake, my advisor, whose patience and insight made it a pleasure to work with him and continued to sustain me for the last seven months that I was on my own. Thanks go also to Jim Kennedy for his careful reading and helpful comments on the rough draft and to Eoug Seeley and Tom Peucker for their suggestions. I am also grateful to Inger Hisson for her typing of Chapter 3. There are many others, people who cheerfully submitted to be subjects in the various experiments, the people who wrote the software that I depended on heavily, and the taxpayers of Canada who through their institutions, the Department of Computer Science at O.B.C., and the Canada Council supported my work financially. I especially wish to thank my wife, not only for the typing and help with the diagrams, but also for her support throughout. 1 INTRODUCTION The growing use of i n t e r a c t i v e graphic f a c i l i t i e s f o r the d i s p l a y , manipulation, and i n t e r r o g a t i o n of geographic i n f o r m a t i o n has c r e a t e d a demand f o r a more f l e x i b l e and compact r e p r e s e n t a t i o n of map o u t l i n e data, whereas i n t r a d i t i o n a l naps the accuracy and d e t a i l cf o u t l i n e s were considered important, i n the case of i n t e r a c t i v e g r a p h i c s the primary concerns o f t e n are the r e d u c t i o n of storage requirements over a range of s c a l e dependent on l e v e l s of r e s o l u t i o n , while enough d e t a i l i s maintained^ f o r v i s u a l i d e n t i f i c a t i o n . The concern with minimizing the storage requirements stems from the u s u a l l y s e v e r e l y l i m i t e d memory c a p a c i t i e s of CRT 1 d i s p l a y d e v i c e s . In a d d i t i o n the p r o c e s s i n g times f o r t y p i c a l o p e r a t i o n s such as shading and i n t e r s e c t i n g r e g i o ns o f t e n vary as the square of the number of p o i n t s along o u t l i n e s . Due to the l i m i t e d screen s i z e s a v a i l a b l e at the present i t i s a l s o necessary to change r a d i c a l l y the s c a l e of the d i s p l a y of a map and at the same time c o r r e s p o n d i n g l y change the l e v e l of d e t a i l . T h i s i s to enable a person to view a l a r g e r e g i o n at s m a l l s c a l e and r e l a t i v e l y low l e v e l of d e t a i l and then "zoom'1 i n on an area c f i n t e r e s t and observe more d e t a i l as the s c a l e became l a r g e r . While i n t e r a c t i v e g r a p h i c s has created a denand f o r new methods of r e p r e s e n t i n g map o u t l i n e s i t has at the same time provided a p o t e n t i a l l y powerful t o o l to a i d i n the c c n v e r s i o n of o u t l i n e s to a more compact form. T h i s a r i s e s from the l i n k that can be e s t a b l i s h e d between the computer's speed and accuracy at 1 CRT = Cathode Ray Tube 2 arithmetic operations and the ability of people tc recognize easily shapes and patterns in two-dimensional information. The work described in this thesis represents one attempt to take advantage of this link offered by interactive graphics to build a system for reducing the data content of map outlines. The way in which this has been done is tc display a series of outlines on the screen of the CRT and allow the user to train the system by manually reducing their data content according to his own particular tastes and requirements. The system learns by recording and analysing the actions of the user until it can satisfactorily mimic the person's behaviour, once this point has been reached the system is then given new lines to reduce on its own. The results can then be checked by the user and corrected. The user can also re-teach the system if necessary. Chapter 1 describes in general terms the processes involved in the system and how they are related to work dene by other people. Chapter 2 goes into the detailed workings of the system. Chapter 3 describes and analyses the results cf experiments with the system. Chapter 4 evaluates the performance of the system as well as the work as a whole. 3 CHAPTER I RELATED WORK 1.0 I n t r o d u c t i o n The work d e s c r i b e d here draws on work done i n many other f i e l d s . In a sense i t p r o p e r l y belongs i n cartography, but c o n t r i b u t i o n s come from f i e l d s as d i v e r s e as perceptual psychology, p a t t e r n r e c o g n i t i o n and l e a r n i n g , l i n g u i s t i c s , computer g r a p h i c s , i n t e r a c t i v e systems, and numerical a n a l y s i s . Some of the i n f l u e n c e s from these areas are d i s c u s s e d i n t h i s c h a p t e r . 1.1 C a r t o g r a p h i c g e n e r a l i z a t i o n Reducing the i n f o r m a t i o n content of an o u t l i n e i s j u s t one aspect of a process t h a t c a r t o g r a p h e r s r e f e r t c as "automatic g e n e r a l i z a t i o n " . G e n e r a l i z a t i o n i s necessary whenever a map of reduced s c a l e or s p e c i a l purpose i s to be produced from other maps. The aim i s "the e x p r e s s i o n of d e t a i l e d by l e s s d e t a i l e d i n f o r m a t i o n by s e l e c t i o n , and s i m p l i f i c a t i o n " (Keates (1972)). Others t h i n k of i t i n terms of " s i m p l i f i c a t i o n , s e l e c t i o n , and emphasis." (Robinson and Sale(1969)) T h i s i s done so that the important s p a t i a l r e l a t i o n s h i p s are conveyed simply and c l e a r l y without i n t e r f e r e n c e from extraneous d e t a i l . For example, out of a p o t e n t i a l l y l a r g e number of p o s s i b l e c h o i c e s c e r t a i n towns, r i v e r s , roads, i s l a n d s , and so on must be s e l e c t e d f o r i n c l u s i o n i n a map while o t h e r s are omitted or combined. L i n e s (e.g., boundaries, c o a s t l i n e s ) must be s i m p l i f i e d while maintaining 4 t h e i r c h a r a c t e r (e.g., a rocky c o a s t l i n e should u s u a l l y remain rough). T h i s i s i n g e n e r a l a very complicated process demanding much knowledge and s k i l l of the c a r t o g r a p h e r . The e v e n t u a l purpose and s c a l e of the map, s p e c i a l knowledge cf the r e g i o n , a e s t h e t i c s , g r a p h i c l i m i t a t i o n s must a l l be considered by a c a r t o g r a p h e r i n t h i s work. I t i s thus h i g h l y s u b j e c t i v e and t h e r e f o r e d i f f i c u l t to automate s i n c e any automatic scheme must i n c l u d e p r o v i s i o n f o r these f a c t o r s . A major c o n t r i b u t i o n to the automation of g e n e r a l i z a t i o n has been the work of T o p f e r (1966). He has d e r i v e d an e x p r e s s i o n t h a t r e l a t e s the d e n s i t y of map items to the s c a l e of the map. T h i s p r o v i d e s a q u a n t i t a t i v e c r i t e r i o n f o r judging the r e s u l t s of g e n e r a l i z a t i o n . However t h i s g i v e s only an estimate of the number of items to be s e l e c t e d without any d i r e c t i n d i c a t i o n s of the p a r t i c u l a r items to be s e l e c t e d . Work by Sukhov (1970), Srnka(1970), and o t h e r s i n S o v i e t c i r c l e s have employed s t a t i s t i c a l and i n f o r m a t i o n t h e o r e t i c p r i n c i p l e s to a i d i n t h i s s e l e c t i o n p r o c e s s . A combination of these approaches promises to be f r u i t f u l f o r automating g e n e r a l i z a t i o n . However the f a c t o r s of map purpose, a e s t h e t i c s , and s p e c i a l r e g i o n a l knowledge w i l l c o n t i n u e to demand the i n f l u e n c e of experienced c a r t o g r a p h e r s . Much of the work i n the automation of g e n e r a l i z a t i o n has centred around the p r o c e s s i n g of l i n e data. The work in t h i s area can be roughly d i v i d e d i n t o two c l a s s e s depending on how the p o i n t s along a l i n e are , t r e a t e d . The f i r s t c l a s s i s c h a r a c t e r i z e d by " p o i n t f i l t e r i n g " schemes. What t h i s means i s that the p o i n t s d e f i n i n g l i n e s i n the new map are simply a 5 subset of the p o i n t s from the o r i g i n a l map. No p o i n t s have been added or moved. Hershey (1963) removed p o i n t s i f they were c l o s e r than some amount depending on the d i s p l a y d e v i c e ' s dot s i z e . T h i s technique ran i n t o t r o u b l e when l i n e s became very near each other and when there was a d r a s t i c s c a l e change. Lang (1969) d e s c r i b e s a scheme that removes p o i n t s i f they do not d e v i a t e too much from s t r a i g h t l i n e approximations. In a s i m i l a r v e i n i s recent work by Douglas (1972). The process s t a r t s by c o n s i d e r i n g a s t r a i g h t l i n e j o i n i n g the end p o i n t s of the l i n e . I f the p o i n t on the l i n e that i s f u r t h e s t from t h i s s t r a i g h t l i n e i s f a r t h e r than a s p e c i f i e d t o l e r a n c e then that point i s s e l e c t e d . The process i s repeated r e c u r s i v e l y cn each of the two s e c t i o n s formed by the newly s e l e c t e d p o i n t u n t i l nowhere i s the d e v i a t i o n g r e a t e r than a s p e c i f i e d amount. Figure 1.1 i l l u s t r a t e s t h i s and i n d i c a t e s the order i n which p o i n t s are s e l e c t e d . Thus, i n a way, the s e l e c t i o n of p o i n t s depends on a l l of the r e s t of the l i n e . The work d e s c r i b e d i n t h i s t h e s i s a l s o belongs- to t h i s c l a s s . P o i n t s are s e l e c t e d based on the r e c o g n i t i o n of p a t t e r n s i n the l i n e s t h a t have been taught to the system by the user. In the second group i s work by Koeman and van der Weiden (1970) . They use an averaging process ever a sequence of p o i n t s to a l t e r the l i n e , thus s i m p l i f y i n g i t . Recent work by Brophy (1972) combines approaches of both groups. P o i n t s are f i r s t s e l e c t e d based cn the d e s i r e d s c a l e and l i n e width and then moved a c c o r d i n g to the degree of g e n e r a l i z a t i o n t c e i t h e r exaggerate or s i m p l i f y the l i n e . C e r t a i n f e a t u r e s are e l i m i n a t e d 1 Outline with points removed Figure 1.3 6 i f adjacent l i n e s begin to merge. T h i s work i n cartography, although d i r e c t e d towards r e d u c i n g the i n f o r m a t i o n content of a l i n e , i s only of l i m i t e d a p p l i c a b i l i t y . The reason f o r t h i s i s t h a t the maps th a t r e s u l t are q u i t e d i f f e r e n t from the s o r t of maps we are i n t e r e s t e d i n . The c a r t o g r a p h e r ' s maps are made of paper, they are "hard" and s t a t i c . They w i l l be hung on w a l l s , s t a r e d a t, and measured c a r e f u l l y . accuracy i s important and the p o i n t s are u s u a l l y spaced a c c o r d i n g to the best r e s o l u t i o n p o s s i b l e ( i . e . , spacing on t h e order of the l i n e width). The degree of i n f o r m a t i o n r e d u c t i o n r e q u i r e d i s governed only by the eye's a b i l i t y to p e r c e i v e and d i s t i n g u i s h images from co l o u r e d ink cn paper. On the other hand, the maps th a t we are i n t e r e s t e d i n are q u i t e d i f f e r e n t . Our maps w i l l be dynamic, " s o f t " , and formed by the glow of phosphor dots of the screen of a CRT. Kost of these maps w i l l l i v e only f o r a few seconds or minutes to convey some r e l a t i o n s h i p b e f o r e being r e p l a c e d by another. Accuracy w i l l not be so important s i n c e measurements w i l l probably not be made from these maps. T h i s means that p o i n t s can be f a i r l y f a r apart - the important c r i t e r i o n being that the o b j e c t s are c l e a r l y i d e n t i f i a b l e . The i n f o r m a t i o n content of l i n e s w i l l be reduced to d i m i n i s h the sto r a g e requirements, t r a n s m i s s i o n time, and p r o c e s s i n g time. At CRT dev i c e s the amount of i n f o r m a t i o n that can be d i s p l a y e d i s o f t e n r e s t r i c t e d by the memory s i z e of the d e v i c e . T r a n s m i t t i n g l a r g e amounts of i n f o r m a t i o n to a d i s p l a y t e r m i n a l i s o f t e n time-consuming and expensive. The processing times f o r many o p e r a t i o n s t h a t can be performed on maps grow very g u i c k l y with the number of po i n t s i n v o l v e d (e.g., f i n d i n g 7 the i n t e r s e c t i o n of two regions can be p r o p o r t i o n a l to the square of the number of p o i n t s ) . These c o n s i d e r a t i o n s encourage us to be "bold and i n t r e p i d " ( M i l l e r and Voskuil(1964)) i n the e l i m i n a t i o n cf p o i n t s . Even though we are f o r c e d to reduce d r a s t i c a l l y the number cf p o i n t s t h i n g s are not so bad s i n c e the c o n s t r a i n t s of accuracy have been loosened somewhat. 1.2 Ps_ycholocjy_ Of P e r c e p t i o n We r e c e i v e some a d d i t i o n a l i n d i c a t i o n that we s h a l l be s u c c e s s f u l from the f i e l d of p e r c e p t u a l psychology. Studies by Attneave (1954) show t h a t most c f the i n f o r m a t i o n f o r the r e c o g n i t i o n of a f i g u r e comes from the r e g i o n s of maximum c u r v a t u r e . Belated i n d i c a t i o n s come from Byan and Shwartz (1956) who r e p o r t t h a t c a r i c a t u r e s , though d i s t o r t e d , are o f t e n more r e a d i l y r e c o g n i z e d than photographs of the corresponding s u b j e c t s . T h i s i s because there i s too much d e t a i l and redundant i n f o r m a t i o n i n the o r i g i n a l . H o p e f u l l y t h i s w i l l be true f o r the i d e n t i f i c a t i o n of map o u t l i n e s as w e l l . I f i t i s tr u e then i t should only be necessary to reco g n i z e and s e l e c t p o i n t s where the c u r v a t u r e i s q u i t e l a r g e i n order to produce o u t l i n e s that are e a s i l y r e c o g n i z a b l e . Some c o n t r a r y i n d i c a t i o n s come from G e s t a l t Psychology s i n c e i t i s maintained that the r e c o g n i t i o n of a f i g u r e i s dependent on the f i g u r e taken as a whole. In other words, f i g u r e r e c o g n i t i o n i s a g l o b a l r a t h e r than a l o c a l p r o c e s s . Which of these views i s the more important i n our s i t u a t i o n w i l l have to be decided by experiment. 8 1.3 Pattern Recognition And Learning In deciding which points are to be removed from an outline in order to reduce its data content the neighbouring portions of the line must be considered. For example, in the two cases shown in Figure 1.2 the point on the left can safely be removed while the one on the right cannot. The result cf removing these points is shown in Figure 1.3. In order for the system to automatically decide on the fate of points in a host of less clear cut cases it must somehow "look" at sections of the line and classify them appropriately. This process is an example of what is commonly known as "Pattern Recognition". A pattern is described by an n-tuple of features f. i.e., f = (f», f 2,..., f"). Pattern Recognition consists of assigning these patterns tc classes, c , out of a set of m classes c = {c1, c2,...,c***} . A standard way of looking at this problem is to consider the space cf patterns to be divided into a number of disjoint regions each with a unique label chosen from c. Classifying a pattern now means finding the label of the region in which the pattern vector lies. For example figure 1.4 illustrates a case where n=2 and m=4. The pattern vector f lies in a region labelled "A". The difficulty arises in defining the boundaries cf these regions. Since we can rarely know a priori what the region boundaries are a pattern recognizing machine must be trained to determine them. This is usually done by specifying initial approximate boundaries and then adjusting them based on externally classified patterns. This is done by giving the device a series of patterns to classify. These patterns should 8a Two Feature Pattern C l a s s i f i c a t i o n Figure 1.4 Root node feature 1 feature 2 feature 3 l e v e l 1 Verdict nodes l e v e l 2 l e v e l 3 Decision Tree f o r Pattern C l a s s i f i c a t i o n Figure 1.5 9 be fairly representative of all the pattern classes. If a pattern is classified correctly then boundaries are often left unchanged. However, if the classification is incorrect the boundary of the appropriate region is moved closer to the point so as to either give the correct classification or else come "nearer" to it . With successive patterns and with repetitions of the same patterns the classification should become more and more reliable and the boundaries move less and less. If the pattern classes are well separated by the measured features , the training patterns are reasonably representative, and the initial boundaries are not too far out then this process should converge and result in a satisfactory pattern classifier., A standard way of specifying region boundaries is in a piece-wise fashion using hyperplanes. This means that only linear polynomials are needed to evaluate pattern class membership. The learning process using this approach consists of adjusting polynomial coefficients. This is a fairly well understood technique and would be appropriate for us except that it demands that all n features be measured in order tc arrive at a verdict for a pattern. In our case, in order to consistently guarantee that enough of the line surrounding a point is considered, n would have to be guite large, say 10 or more (using angles and lengths of straight line segments). However, it is often possible to make the right decision by considering only a single feature. This occurs when the line is virtually straight at the point. Since there is a certain expense associated with measuring a feature and since learning is generally slower and less reliable with more parameters a method 10 which considers only the minimum number of relevant features would seem desirable. This is the approach taken in Sequential Pattern Recognition (SPR) (Slagle and Lee (197 1)). With SPR features are considered one at a time as needed. When a new feature is measured a test is made to determine whether the pattern classification can be made reliably. If it can then we can move on to the next pattern. If not then a decision is made as to whether further features would be likely to increase the reliability of the verdict and if so , which one. Only if this is affirmative is another feature selected. although the work for each feature considered this way is more than in the "parallel" case, fewer features will be involved so there can be a considerable overall saving. a simplified version of this SPR technique has been used in this project. With each new feature the only decision made is whether a verdict can be made. If it can, it is, otherwise the next feature is considered. The order in which the features are taken is fixed ahead of time. This decision process is conveniently represented as a tree (see Fig. 1.5). The root is the initial node and the features as they are measured in turn cause transitions down the appropriate arcs until a terminal node is reached. At the beginning of the learning process the tree consists only of the top level (root plus terminal nodes,see Figure 1.6). As patterns are presented, if the verdict agrees with the classification given then that verdict is reinforced. If there is disagreement then the tree either sprouts new terminal nodes from the previous terminal node or else the verdict is weakened or changed depending on the depth Root Node Terminal (Verdict) Nodes Decision Tree Before Learning Figure 1.6 11 and past h i s t o r y of that v e r d i c t . T h i s l e a r n i n g and c l a s s i f i c a t i o n scheme i s very s i m i l a r to that cf EP AM (Feigenbaum (1963)) and the work of Sherman and E r n s t (1969). Which f e a t u r e s to measure i s of t e n a s e r i o u s problem i n P a t t e r n R e c o g n i t i o n . They must c o n t a i n the e s s e n t i a l d i s t i n g u i s h i n g c h a r a c t e r i s t i c s of the o r i g i n a l , otherwise a l l subseguent work w i l l be f u t i l e . S i n c e we are d e a l i n g with g r a p h i c or two-dimensional i n f o r m a t i o n there might be an i n i t i a l temptation to measure two-dimensional f e a t u r e s (as i n the case o f Ohr and V o s s l e r ' s p a t t e r n r e c o g n i t i o n machines(1963)). However, s i n c e we are i n t e r e s t e d i n the boundaries of regions and not the r e g i o n s themselves, we can c o n v e n i e n t l y e x p l o i t the e s s e n t i a l l y one-dimensional nature of our l i n e drawings by c o n v e r t i n g them i n t o s t r i n g s of c h a r a c t e r s . I have chosen to do t h i s by q u a n t i z i n g the l e n g t h s and the angles between i n d i v i d u a l segments along the l i n e s i n c e t h i s appears to o f f e r the best way of c a p t u r i n g the essence of a l i n e . The c l a s s i f i c a t i o n r e c o g n i t i o n problem can now be locked a t as r e c o g n i z i n g whether s t r i n g s belong to a p a r t i c u l a r language over a f i n i t e alphabet. Since the data i's " n a t u r a l l y " o c c u r i n g the language i s very messy and i l l - d e f i n e d , but t h i s c r u d e l y l i n g u i s t i c approach co u l d be f r u i t f u l i n the f u t u r e . Some people who have t r i e d t h i s approach i n other f i e l d s are M i l l e r and Shaw (1968), Feder(1968), P f a l t z (1970) , and Seeley (1970). 12 1.4 l i n e Encoding Schemes Whenever one comes to r e p r e s e n t i n g l i n e data i n the computer one i s faced with making a choice of which of three encoding schemes to use. The most t r a d i t i o n a l scheme i s known as the v e c t o r approximation or X-Y c o o r d i n a t e method. fi curve i s approximated by a s e r i e s of contiguous s t r a i g h t l i n e segments and t h e a b s o l u t e c o o r d i n a t e s of the endpoints of these segments (or vectors) i s recorded r e l a t i v e t o a f i x e d c o o r d i n a t e system. For example, the curve shown i n F i g u r e 1.7 would be encoded n u m e r i c a l l y as: 1 1 10 22 15 35 25. 45 33 55 40 65 • m • • m m another way to encode l i n e s i s with the use cf Freeman cha i n s (Freeman (1961)). T h i s i s done by o v e r l a y i n g a r e c t a n g u l a r g r i d of f i x e d mesh s i z e and f i n d i n g the i n t e r s e c t i o n p o i n t s of the curve with the g r i d , (see F i g . 1.8) The g r i d p o i n t s nearest these i n t e r s e c t i o n p o i n t s are determined and connected i n order with l i n e segments whose l e n g t h i s e i t h e r 1 or s g r t (2) times the mesh s i z e (see F i g . 1.9). These s h o r t segments are encoded with the d i g i t s 0 through 7 a c c o r d i n g to the diagram shown i n F i g 1.10. Thus the f i n a l encoding of the o r i g i n a l curve would be ...00101320... . a t h i r d encoding scheme t h a t i s mainly s u i t a b l e f o r c l o s e d 12a Chain-encoding ( g r i d overlay) Figure 1.8 12b o / £ J r * } ) 7 > < . ' A 0 0 Chain-encoding Figure 1.9 Chain-encoding (basic increments) Figure 1.10 13 curves i s one f i r s t proposed by Elum (1964). T h i s method, r e f e r r e d to as s k e l e t o n encoding, i s based on f i n d i n g the maximal neighbourhoods of planar r e g i o n s . In a p a r t i c u l a r metric the neighbourhood of a p o i n t i s the set of a l l p o i n t s within some d i s t a n c e from that p o i n t . With the " c i t y - b l o c k " metric i n F i g . 1.11 (from P f a l t z and Rosenfeld (1967)) the 2-neighbourhood of the p o i n t P i s i n d i c a t e d by the rhombus. For a c l o s e d r e g i o n i n the plane every p o i n t i n the i n t e r i o r of the r e g i o n has a neighbourhood completely w i t h i n the r e g i o n . The maximal neighbourhoods of the r e g i o n are the set of such neighbourhoods that are not completely e n c l o s e d w i t h i n some other neighbourhood. The c e n t r e s of these maximal neighbourhoods form s t i c k - l i k e s k e l e t o n s which together with the corresponding r a d i i g i v e an adeguate d e s c r i p t i o n of the o r i g i n a l o u t l i n e (Figure 1.12). (see P f a l t z and Rosenfeld (1967), Mcntanari (1968)). Each o f these methods has i t s own advantages and disadvantages, depending on the s i t u a t i o n i n which i t i s used. 1 G e n e r a l l y chain-encoding g i v e s the most compact r e p r e s e n t a t i o n f o r very d e t a i l e d o u t l i n e s and i s well s u i t e d to f i n d i n g l e ngths and areas, a l s o , chain encoding lends i t s e l f to c o n s i d e r a b l e t h e o r e t i c a l a n a l y s i s (see Freeman (1961) and Feder (1968)). Skeleton-encoding, while poor f o r processes a s s o c i a t e d with the boundary, such as f i n d i n g the perimeter of the r e g i o n , i s s u p e r i o r when i t comes to " a r e a l " o p e r a t i o n s such as shading and i n t e r s e c t i o n of r e g i o n s . Vector approximation i s g e n e r a l l y i n t e r m e d i a t e . I t enjoys an advantage i n economy of .__ ™ 1 see Deeker(1970) f o r a much more complete comparison of these three encoding schemes. The 2-neighbourhood of point P Figure 1.11 Skeleton of an Outline Figure 1.12 14 r e p r e s e n t a t i o n when the o u t l i n e i s f a i r l y simple and permits easy r o t a t i o n . I t i s b e t t e r s u i t e d t o our p a r t i c u l a r purposes f o r reasons t h a t w i l l be d i s c u s s e d i n the next c h a p t e r . 1.5 L i n e Reduction The problem of reducing and s i m p l i f y i n g l i n e data i s met i n many areas other than cartography. Some of the major sources of t h i s data are photomicrographs of chromosomes and c e l l s i n the biomedical f i e l d , bubble chamber photographs i n high energy p h y s i c s , and a e r i a l photos i n remote sensing. Such a p p l i c a t i o n s as these produce enormous q u a n t i t i e s of l i n e data that must be reduced i n some way before they are manageable. J a r v i s (1971) has done work on f i t t i n g low-order polygons to the chain-encoded boundaries of muscle c e l l s . The approach he took was to pick a po i n t i n the i n t e r i o r of the c e l l and p l o t the d i s t a n c e to the boundary as a f u n c t i o n of angle. The peaks and troughs of t h i s f u n c t i o n can be a s s o c i a t e d with the v e r t i c e s of the o r i g i n a l shape. These v e r t i c e s are added one by one to the polygon d e s c r i p t i o n u n t i l a l e a s t squares d e v i a t i o n e r r o r f a l l s below a s p e c i f i e d t h r e s h o l d . Zahn (1969) has a l s o attempted to reduce the data content of chain-encoded boundaries but by not nea r l y as d r a s t i c an amount. He e s s e n t i a l l y re-codes the d e s c r i p t i o n by r e c o g n i z i n g r e g u l a r i t i e s i n the c h a i n . No i n f o r m a t i o n i s l o s t i n the process and the o r i g i n a l l i n e can be r e c o n s t r u c t e d p r e c i s e l y . More r e c e n t l y (Zahn and Roskies(1972)) he has used F o u r i e r D e s c r i p t o r s to encode l i n e s . The c o e f f i c i e n t s i n the F o u r i e r expansion of a l i n e are s u f f i c i e n t to s p e c i f y i t adequately. Since most of the i n f o r m a t i o n i s u s u a l l y s t o r e d i n 15 the lower terms the remainder can be dropped i n order to reduce the data content of the l i n e . There have been s e v e r a l attempts to o b t a i n the minimum perimeter polygon (MPP) from the ch a i n -encoding of shape. An MPP of a shape i s the polygon of minimum perimeter t h a t produces the same chain-encoding as the o r i g i n a l shape. Montanari (1970) was one of the f i r s t and h i s approach was to s t a r t with a chain-encoding and then move the v e r t i c e s around w i t h i n s m a l l neighbourhoods of t h e i r o r i g i n a l p o s i t i o n s u n t i l the r e s u l t i n g boundary was of minimal l e n g t h . In a more t h e o r e t i c a l v e i n i s the work of Sklansky e t al{1972). A l l these attempts have i n common the f a c t that the r e s u l t i n g l i n e must s a t i s f y some s t r i c t mathematical r e l a t i o n s h i p to the o r i g i n a l l i n e . T h i s makes the l i n e s more s u i t a b l e f o r comparision and a n a l y s i s but does net n e c e s s a r i l y g i v e the best r e d u c t i o n s from the point of view of v i s u a l r e c o g n i t i o n . I t may w e l l turn out t h a t there i s seme we l l -d e f i n e d mathematical c r i t e r i o n that produces the most a p p r o p r i a t e r e d u c t i o n v i s u a l l y , but one i s not known yet. I t t h e r e f o r e seems reasonable to allow the p r o s p e c t i v e user to d e f i n e e m p i r i c a l l y what he t h i n k s i s most a p p r o p r i a t e by r e d u c i n g l i n e s manually. The system c o u l d l e a r n to mimic the user and thus the c r i t e r i a are e s t a b l i s h e d i n t e r n a l l y a c c o r d i n g t o the i n d i v i d u a l ' s needs and p r e f e r e n c e s . 16 1.6 I n t e r a c t i v e Graphics T h i s t a i l o r i n g of the system to s u i t a p a r t i c u l a r user's t a s t e s i s one of the main a t t r a c t i o n s o f f e r e d by i n t e r a c t i v e computing. An i n t e r a c t i v e system i s one i n which a person has immediate access t o the computation process and plays a d i r e c t r o l e i n g u i d i n g i t s course. T h i s i s done by having t e r m i n a l d e v i c e s a t t a c h e d to a computer that allow output frcm a program to be d i s p l a y e d to the user and permits the user to enter i n f o r m a t i o n f o r the program. The e a r l i e s t competing systems were of t h i s nature. A person had the machine to h i m s e l f and was able to d i r e c t l y monitor i t s performance and make changes to i t and the program as d e s i r e d . As computers became f a s t e r and more powerful i t became necessary to submit programs i n batches with consequent s e p a r a t i o n of user and process. More r e c e n t l y , with the advent of time-sharing systems, i t again became p o s s i b l e to put people and process back together again. T h i s development promised many great t h i n g s . I t was thought that by c o u p l i n g man and machine i t would be p o s s i b l e t o e x p l o i t the d i v e r s e s k i l l of the two p a r t i e s s i m u l t a n e o u s l y . Computers are w e l l - s u i t e d to performing simple r e p e t i t i v e o p e r a t i o n s g u i c k l y and a c c u r a t e l y . People, while poor at t h i s are good a t r e c o g n i z i n g p a t t e r n s i n i n f o r m a t i o n from d i v e r s e sources and i d e n t i f y i n g g c a l s : things that computers are not good a t . While many see t h i s l i n k i n g of people and computer with t h e i r v a s t l y d i f f e r e n t s k i l l s and speeds of o p e r a t i o n as o f f e r i n g a much improved method of t a c k l i n g many problems, Norbert Wiener d i d not share t h i s optimism. He wrote i n 1963: 17 D i s a s t r o u s r e s u l t s are to be expected not merely i n the world of f a i r y t a l e s but i n the r e a l world wherever two agencies e s s e n t i a l l y f o r e i g n t c each other are coupled i n the attempt to achieve a common purpose. I f the communication between these two agencies as t c the nature of t h i s purpose i s incomplete, i t must only be expected that the r e s u l t s of t h i s c o o p e r a t i o n w i l l be u n s a t i s f a c t o r y . ... One of the c h i e f causes of the danger of d i s a s t r o u s consequences i n the use of the l e a r n i n g machine i s that man and machine operate on two d i s t i n c t time s c a l e s , so that the machine i s much f a s t e r than man and the two do not gear together without s e r i o u s d i f f i c u l t i e s . Although t h i s was w r i t t e n before i n t e r a c t i v e systems were widely a v a i l a b l e h i s comments are' s t i l l r e l e v a n t and should be c o n s i d e r e d s e r i o u s l y . An a t t i t u d e of c a u t i o n and s c e p t i c i s m i s e s p e c i a l l y important when c o n f r o n t i n g proponents c f Man-Machine Symbiosis such as L i c k l i d e r (1960) l e s t i t be f o r g o t t e n that the machine i s to be our t o o l . On a more co n c r e t e l e v e l i n t e r a c t i v e systems promise to make computing more e f f i c i e n t from the user's point c f view. Not on l y would r e s u l t s g e n e r a l l y be a v a i l a b l e f a s t e r than with batch systems, but l e s s work would be r e q u i r e d on h i s part to o b t a i n them. T h i s i s p a r t l y because the context of any o p e r a t i o n could be narrowed c o n s i d e r a b l y . Since a program can prompt f o r i n p u t and show the r e s u l t s immediately, the user does not have to a n t i c i p a t e ahead of time p r e c i s e l y what w i l l be needed. This i s e s p e c i a l l y a p p l i c a b l e to debugging programs, where the behaviour i s o f t e n u n p r e d i c t a b l e , and i n e d i t t i n g programs and t e x t , where the context i s l i m i t e d t c the r e c e n t output and changes can be ' v e r i f i e d immediately. G e n e r a l l y , a p p l i c a t i o n s most s u i t a b l e f o r i n t e r a c t i v e 18 systems can be c h a r a c t e r i z e d a c c o r d i n g to the f o l l o w i n g modes of o p e r a t i o n : • R e l a t i v e l y few, s t r a i g h t - f o r w a r d o p e r a t i o n s with immediate response, e.g., i n q u i r y systems ( a i r l i n e r e s e r v a t i o n systems, customer record systems) • Many s e q u e n t i a l d e c i s i o n s with f a s t response, each a c t i o n o f t e n depending on the r e s u l t of e a r l i e r a c t i o n s ; e.g., e d i t t i n g , program debugging, computer-aided l e a r n i n g (CAL), computer-aided design (CAD) • Complex s e q u e n t i a l o p e r a t i o n s , each a c t i o n h e a v i l y dependent on r e s u l t s of p r e v i o u s ones; e.g., o n - l i n e p r o b l e m - s o l v i n g , i n t e r a c t i v e s i m u l a t i o n s . While these d i f f e r e n t c a t e g o r i e s o v e r l a p and i n f a c t r e a l l y belong on a continuum they are intended to h i g h l i g h t some of the b a s i c d i s t i n c t i o n s . I t i s i n the second c l a s s t h a t the work d e s c r i b e d here belongs. The s e q u e n t i a l manual s e l e c t i o n and r e j e c t i o n of p o i n t s along an o u t l i n e a f f e c t s the shape of the r e s u l t i n g o u t l i n e and hence i n f l u e n c e s f u t u r e a c t i o n s . A l s o , during l e a r n i n g i t i s important to know how the system i s behaving s i n c e t h i s has a bearing on the order i n which sample p a t t e r n s are presented t c i t . Computer G r a p h i c s , which i s the computer manipulation and d i s p l a y of 2-(or more) dimensional i n f o r m a t i o n (as opposed to the p r o c e s s i n g of one-dimensional s t r i n g and numerical information) goes n a t u r a l l y with i n t e r a c t i v e computing. T h i s i s t r u e f o r two d i s t i n c t reasons. In the f i r s t case, with many i n t e r a c t i v e s i t u a t i o n s a c o n s i d e r a b l e amount of data i s produced 19 upon which the next a c t i o n by the user i s to be based. T h i s i n f o r m a t i o n i s o f t e n b e s t represented g r a p h i c a l l y because t h i s i s a form i n which people are good a t seeing p a t t e r n s and r e l a t i o n s h i p s . T h i s i s t r u e even when the i n f o r m a t i o n i t s e l f i s not i n h e r e n t l y g r a p h i c such as i n numerical or s t a t i s t i c a l a p p l i c a t i o n s . Secondly, when d e a l i n g with i n f o r m a t i o n that i s b a s i c a l l y g r a p h i c , i n t e r a c t i v e methods are of t e n h i g h l y p r e f e r r e d to n o n - i n t e r a c t i v e methods. T h i s i s because i t o b v i o u s l y makes sense to s p e c i f y i n gr a p h i c terms the o p e r a t i o n s that are to be performed. The a l t e r n a t i v e i s through numerical or l i n g u i s t i c d e s c r i p t i o n s . These are i n ge n e r a l n e c e s s a r i l y long and messy s i n c e so much context must be s u p p l i e d that was in h e r e n t i n the o r i g i n a l g r aphic form. T h i s i s a conseguence of the f a c t t h a t p i c t u r e s , diagrams, maps and sc on are i n f o r m a t i o n a l l y very r i c h . T h i s f a c t , however, makes i t d i f f i c u l t to get raw gra p h i c data i n t o the machine. Because present computers are not " g r a p h i c machines" such i n f o r m a t i o n must be d i g i t i z e d somehow - u s u a l l y a le n g t h y and expensive a f f a i r . The way to get around the problem cf s p e c i f y i n g o p e r a t i o n s g r a p h i c a l l y , once the b a s i c i n f o r m a t i o n has teen entered the hard way, i s to d i s p l a y t h i s i n f o r m a t i o n on a gr a p h i c t e r m i n a l and use the a v a i l a b l e i n t e r a c t i v e d e v i c e s to i n d i c a t e the d e s i r e d manipulations. These de v i c e s (such as l i g h t - p e n s , j o y - s t i c k s , f u n c t i o n keys, "mice", t a b l e t s etc.) allow one to enter g r a p h i c i n f o r m a t i o n d i r e c t l y . They can be used t o draw f i g u r e s , s e l e c t p i c t u r e components to be operated on, c o n t r o l the form of the d i s p l a y and so on. The v i n f o r m a t i o n t h a t we are d e a l i n g with, s i n c e i t comes 2 0 from maps, i s b a s i c a l l y g r a p h i c . In a d d i t i o n the s e l e c t i o n / r e j e c t i o n of p o i n t s demands the v i s u a l i n s p e c t i o n c f o u t l i n e s and s p e c i f i c a t i o n of o p e r a t i o n s on a po i n t by p o i n t b a s i s . For these reasons the f a c i l i t i e s of i n t e r a c t i v e g r a p h i c s were used i n the approach d e s c r i b e d here to the r e d u c t i o n of map o u t l i n e s . 21 CHAPTER I I METHODS AND TECHNIQUES 2.0 I n t r o d u c t i o n The l e a r n i n g and subsequent automatic g e n e r a l i z a t i o n of l i n e s i s embedded i n a c o n s i d e r a b l y l a r g e r system f o r manipulating l i n e s and the l e v e l s that \ are attached to the i n d i v i d u a l p o i n t s on these l i n e s . The b a s i c components cf t h i s system and t h e i r i n t e r r e l a t i o n s are shown i n Figure 2.1. This diagram shows the flow of i n f o r m a t i o n as l i n e s cn maps are d i g i t i z e d and the data s t o r e d on a d i s k . A person using the v a r i o u s d e v i c e s around him can s p e c i f y that these l i n e s are to be brought i n t o the computer's i n t e r n a l memory, manipulated i n v a r i o u s ways, and d i s p l a y e d on the screen of the g r a p h i c s t e r m i n a l . 2.1 L i n e Representation Jextgrnal). I chose to r e p r e s e n t l i n e s e x t e r n a l l y by means of the standard X-Y c o o r d i n a t e method as d e s c r i b e d i n the pre v i o u s chapter. The l i n e used i n the example then (see Fig u r e 1.7) might be g e n e r a l i z e d s e v e r a l times to give a number of l e v e l s of d e t a i l as shown i n F i g u r e 2.2 (a and b). The a d d i t i o n a l i n f o r m a t i o n to be s t o r e d i n the l i n e i s e a s i l y handled by a t t a c h i n g to each p o i n t of the vector approximation a number that i n d i c a t e s the r e l a t i v e importance of that p c i n t i n conveying the shape of the l i n e as a whole. In the case of the previous example these values (or l e v e l s ) of the p o i n t s would be as d e p i c t e d i n F i g u r e 2.3. When i t comes to d i s p l a y i n g t h i s l i n e at a p a r t i c u l a r l e v e l of d e t a i l , these l e v e l s t e l l us which 21a External Line Storage (disk) 4-Graphic T^gmingl Function Keys O r i g i n a l Map r Ma i n j : omp_u te r_ (IBM 260/67}_ ""I Manipulation & Display Routines 4- I n t e r n a l Storage I Display Computer (Adage Corp. DPR-2). •Light Pen Dia l s Keyboard Terminal L (Tj»M 2260) The I n t e r a c t i v e Line Processing System Figure 2.1 Levels of Detail Figure 2.2 22 p o i n t s to i n c l u d e and which to leave out. A l i n e d i s p l a y e d at a s p e c i f i e d l e v e l w i l l c o n t a i n only those p o i n t s whose l e v e l s are g r e a t e r than or egual to the s p e c i f i e d l e v e l . Thus at l e v e l 0 we get F i g u r e 2.3 (without the numbers), at l e v e l 1 we get F i g u r e 2.2a, and at l e v e l 2, F i g u r e 2.2b. The numerical r e p r e s e n t a t i o n of the l i n e with a l l these l e v e l s would be: X Y V 10 22 2 15 35 0 25 45 1 33 • 55 • 0 • • • • • • The method d e s c r i b e d above f o r encoding l i n e s at d i f f e r e n t l e v e l s by a t t a c h i n g a unique l e v e l to each point i s q u i t e adequate as long as there i s a s t r i c t h i e r a r c h i c a l o r d e r i n g cf the •importance* of each p o i n t . For example the l i n e shown i n F i g u r e 2.4 might appear at one l e v e l as i n F i g u r e 2.5 while at a lower l e v e l of d e t a i l ( i . e . , higher l e v e l of d i s p l a y ) appear as i n F i g u r e 2.6. The p o i n t i n d i c a t e d by the 'X' cannot have a unique l e v e l but needs r a t h e r ranges of l e v e l s a s s o c i a t e d with i t . A s i m i l a r problem a r i s e s when handling the r e p r e s e n t a t i o n s of o b j e c t s such as r i v e r s . I f the o r i g i n a l map contained a r i v e r as i n Figure 2.7 and at a p a r t i c u l a r l e v e l of g e n e r a l i z a t i o n i t was to appear as shown i n F i g u r e 2.8 then s i n g l e l e v e l s are again not adequate s i n c e the two edges come tog e t h e r . T h i s l a s t case can be taken care of by a s s o c i a t i n g with each point two values t h a t s p e c i f y the upper and lower l i m i t s of the l e v e l s at which the p o i n t -can be d i s p l a y e d . In the case of the r i v e r , s e v e r a l d i f f e r e n t l i n e s would have t c be a s s o c i a t e d with the A Line to be Generalized Figure 2.4 Generalized to a Greater Degree Figure 2.6 22b Generalized River Figure 2.8 23 r i v e r s i n c e the two r i v e r banks, merge. By a p p r o p r i a t e adjustment of the values only the proper l i n e s would appear when they were a l l ' d i s p l a y e d 1 at seme p a r t i c u l a r l e v e l of g e n e r a l i z a t i o n . The implemented system makes p r e v i s i o n f o r the i n c l u s i o n of two values a s s o c i a t e d with each p o i n t , although the system i s not r e a l l y s u i t a b l e f o r handling these more complicated cases i n a convenient way. For the remainder of t h i s d i s c u s s i o n only the f i r s t of the two values w i l l be r e f e r r e d to. Ho confusion should a r i s e from t h i s e x c l u s i o n . The v e c t o r approximation method f o r encoding curves was chosen because i t enjoys s e v e r a l c o n s i d e r a b l e advantages over the a l t e r n a t i v e methods. Chain encoding using Freeman c h a i n s , while an e x c e l l e n t way to r e p r e s e n t s t a t i c l i n e s , g i v e s r i s e to s e r i o u s problems when d r a s t i c g e n e r a l i z a t i o n i s attempted. The reason f o r t h i s i s t h a t data r e d u c t i o n can only r e a l l y be accomplished by making the base g r i d c o a r s e r . Chain encoding's r e l i a n c e on a r e g u l a r g r i d means th a t i t cannot take advantage of l o n g , r e l a t i v e l y f e a t u r e l e s s s e c t i o n s of o u t l i n e s to reduce s t o r a g e requirements. These r e l a t i v e l y s t r a i g h t s e c t i o n s of o u t l i n e occur q u i t e f r e g u e n t l y i n the s o r t of data that we are i n t e r e s t e d i n (urban, p o l i t i c a l boundaries) and e s p e c i a l l y as the l i n e s become l e s s d e t a i l e d through g e n e r a l i z a t i o n . The v e c t o r approximation method can take f u l l advantage of these sections,* c o n c e n t r a t i n g v e c t o r s only i n the areas of important f e a t u r e s , another important o b j e c t i o n to c h a i n encoding i s that one must maintain as many c o p i e s of a l i n e as there are l e v e l s of g e n e r a l i z a t i o n , although the space per copy decreases as the 24 l e v e l of g e n e r a l i z a t i o n i n c r e a s e s , because of the l a r g e r step s i z e s , i t s t i l l r e s u l t s i n being very clumsy to handle . I f one i s not happy with s e c t i o n s of the encoding at a p a r t i c u l a r l e v e l then t h a t whole l i n e must be regenerated from the next lowest l e v e l . The changes could a l s o a f f e c t s u c c e s s i v e l y higher l e v e l s of l i n e s . The v e c t o r approximation with l e v e l s attached to the p o i n t s allows the changing of l e v e l s to be done much more e a s i l y . A f u r t h e r p o i n t i n favour of v e c t o r approximation i s that most of the data t h a t was a v a i l a b l e was d i g i t i z e d by t h i s method. A l s o , the g r a p h i c d i s p l a y device (an AGT-10) i s a vector d r i v e n machine. Skeleton-encoding i s b e t t e r s u i t e d to r e p r e s e n t i n g d i f f e r e n t l e v e l s of g e n e r a l i z a t i o n than chain-encoding because the r a d i i of the maximal neighbourhoods a l r e a d y i n d i c a t e to a c o n s i d e r a b l e extent the r e l a t i v e importance of that p a r t i c u l a r neighbourhood. In t h i s way g e n e r a l i z a t i o n could be seen n a t u r a l l y i n terms of simply choosing those neighbourhoods whose r a d i i were g r e a t e r than some p a r t i c u l a r value. T h i s would probably lead to f a i r l y decent r e p r e s e n t a t i o n s . However the expense of c o n v e r t i n g from the boundary encoding cf the i n i t i a l d i g i t i z a t i o n i n t o s k e l e t o n form and then back again f o r d i s p l a y would be c o n s i d e r a b l e . A l s o there does not seem to be an obvious and convenient way f o r s i m p l i f i c a t i o n s i n the o u t l i n e to be r e f l e c t e d i n changes i n the s k e l e t o n s h o r t of re-enccding the whole r e g i o n . 25 2.2 Manual I n t e r a c t i v e A l t e r a t i o n Of Levels. i In the p r e v i o u s s e c t i o n we have seen that an o u t l i n e can be c o n v e n i e n t l y represented on s e v e r a l l e v e l s of g e n e r a l i z a t i o n by a t t a c h i n g an e x t r a value to each p o i n t along the o u t l i n e . In t h i s s e c t i o n I w i l l d e s c r i b e the way i n which these values can be a l t e r e d e i t h e r en masse or s i n g l y , under the d i r e c t c o n t r o l of the u s e r . In order to a l t e r the l e v e l s of one or more p o i n t s s e v e r a l s t a g e s of s e l e c t i o n must be made, The f i r s t stage i s to s e l e c t the subset of l i n e s c o n t a i n i n g the d e s i r e d p o i n t s . T h i s i s done by s p e c i f y i n g the i d e n t i f i e r s of these p a r t i c u l a r l i n e s . In a d d i t i o n the l e v e l s of the l i n e s i n t h i s subset are a l s o s p e c i f i e d . I f the set of l i n e i d e n t i f i e r s i s I = { i 1 , i 2 , . . . i n } and the l e v e l of s e l e c t i o n i s ¥ AL then the set of p o i n t s s e l e c t e d so f a r i s : P = ^ { (Xik, Y i k , Vik) £ L i | Vik > VAL ] i £ I 1<k< J L i | (where J L i | i s the number of p o i n t s i n l i n e L i ) I f a number o f values are to be a l t e r e d simultaneously then the s e t P can be f u r t h e r r e f i n e d by s p e c i f y i n g an upper bound (UBV) and lower bound (LBV) f o r the values of the p o i n t s tc be a l t e r e d . The r e s u l t i n g s e t of p o i n t s i s : P« * { ( X j , Y j , Vj) £ P l LBV < Vj < 0BV } I f , i n s t e a d , the values are to be a l t e r e d one at a time then a s p e c i f i e d fragment of P or one of the L i can be d i s p l a y e d on the 26 screen of the d i s p l a y device at another s p e c i f i e d l e v e l (VJL). The fragment to be d i s p l a y e d i s d e s c r i b e d by g i v i n g a s t a r t i n g p o s i t i o n (START) and a length (LEN) so that what appears on the screen i s the s e t of p o i n t s : PS = { (Xj, Y j , V j ) t P | Vj > VAL, START < j < START • LEN } I f one of the l i n e s (Li) was given then the e x p r e s s i o n f o r PS i s the same but with P A i i r e p l a c i n g P. i . e . , PS = { ( X j , Y j , Vj)£POLi | Vj > VAL, START < j < START + LEN } Consecutive p o i n t s are j o i n e d by s t r a i g h t l i n e s i f the p o i n t s belong to the same l i n e and they are a l l s c a l e d to f i l l the screen as much as p o s s i b l e . Superimposed on the f i r s t p c i n t i s a s m a l l 'X1: and at the bottom of the screen i s some text i n d i c a t i n g the l e v e l of d i s p l a y and the name of the l i n e i f one was s p e c i f i e d . I f the value of the p o i n t i n d i c a t e d by the 'X' i s to be a l t e r e d then a p a r t i c u l a r f u n c t i o n key attached to the g r a p h i c s computer i s pressed, otherwise a d i f f e r e n t f u n c t i o n key i s pressed. In e i t h e r case the •X1 moves on to the next p o i n t . I f the new value of a point f a l l s below the d i s p l a y l e v e l then t h a t p o i n t and i t s a d j o i n i n g segments disappear, and i f i t was not an end p o i n t the adjacent p o i n t s are reconnected d i r e c t l y (see Pig 2.9). Before the 'X' gets to the end of the s e c t i o n of the l i n e d i s p l a y e d on the s c r e e n , and i f there are point s remaining to be d i s p l a y e d then the next p o r t i o n cf t h i s s et of p o i n t s i s d i s p l a y e d together with the l a s t few of the former p o r t i o n (see F i g . 2.10). The purpose of t h i s i s so that there w i l l always be a reasonable amount of context f o r making the d e c i s i o n to a l t e r the value of a point. In t h i s way the »X' step s along the l i n e and the value of each p o i n t i s e i t h e r Point A l t e r a t i o n Figure 2.9 The Changing View of the Line Figure 2.10 27 transformed or l e f t unchanged. Regardless of which method has been used to s e l e c t the p o i n t s to be a l t e r e d , the method cf changing the values i s the same. The values of the p o i n t s that have been s e l e c t e d undergo a l i n e a r t r a n s f o r m a t i o n . i . e . : Vnew = C1 • C2 * Void The parameters of t h i s t r a n s f o r m a t i o n (C1 and C2) are s p e c i f i e d by the user at the time he i n i t i a t e s the second step of the s e l e c t i o n process. 2.3 L e a r n i n g In the l a s t s e c t i o n we saw how l i n e s c ould be g e n e r a l i z e d by hand, so to speak, although doing i t t h i s way i s f a i r l y f a s t , i t i s s t i l l f a i r l y expensive and very time consuming i f many l i n e s are to be processed. For t h i s reason a component was added to t h e system t h a t a l l o w s i t to l e a r n to mimic the s e l e c t i o n behaviour of the user. Once the program's performance reasonably approximates t h a t of the user then the job of s e l e c t i n g p o i n t s f o r a l t e r a t i o n can be l e f t up to the program. I t i s my hypothesis that i f a person c o u l d do a s a t i s f a c t o r y job of s e l e c t i n g p o i n t s , when a l l he could see at one time was a s m a l l s e c t i o n of the l i n e (10 p o i n t s , s a y ) , then so could a program. (The c o r r e c t n e s s of the b a s i c assumption i n t h i s h y p o thesis w i l l be examined i n the next chapter.) The f i r s t s t ep i n g e t t i n g the machine to r e c o g n i z e p o i n t s f c r a l t e r a t i o n i s t o r e p r e s e n t the l i n e s i n a more convenient form. The main c r i t e r i o n t h a t a new encoding scheme must s a t i s f y i s that i t must r e p r e s e n t l i n e s i n a much more gen e r a l way without 28 s a c r i f i c i n g the e s s e n t i a l f e a t u r e s . I t should a l s o c o n s i s t of the elements that are most important f o r v i s u a l d i s c r i m i n a t i o n . I suspect these are the lengths of the v e c t o r s and the angles between them. For these reasons I chose to adopt a v a r i a n t of chain-encoding to r e p r e s e n t l i n e s t o be processed by the l e a r n i n g and automatic a l t e r a t i o n components of the system. Using t h i s scheme a l i n e i s represented by an a l t e r n a t i n g sequence of l e n g t h s - (Li) -and angles (Ai) . For example, the l i n e i n F i g u r e 2.11 would be s t o r e d as: fij X>| ^£ ^3 • • • So f a r t h e r e has been no i n f o r m a t i o n l o s t i n the sense that the o r i g i n a l d i g i t i z e d l i n e c o u l d be r e c o n s t r u c t e d e x a c t l y . However we have to go f u r t h e r than t h i s s i n c e there i s . s t i l l too much d i s t i n c t i o n between e s s e n t i a l l y s i m i l a r l i n e s . The next step i s to q u a n t i z e these angles and l e n g t h s . I.e., they are transformed to take on only d i s c r e t e v a l u e s . (In the c u r r e n t implementation the number of these d i s c r e t e values f o r both angles and lengths i s 8.) The guantized length depends mainly on the l o g a r i t h m of the o r i g i n a l length s i n c e i t p r o v i d e s a good way t o compress the great range over which the l e n g t h s can vary and a l s c because i t seems t o correspond to v i s u a l importance. (Another good p o t e n t i a l c a n d i d a t e would be the Arctangent f u n c t i o n s i n c e i t too compresses a great range of lengths.) The exact r e l a t i o n s h i p between the g u a n t i z e d and o r i g i n a l l e n g t h that the system c u r r e n t l y uses i s given by the f o l l o w i n g e x p r e s s i o n : QLEN = I log / L EN \ * 8 + 1 |_ VMISLEil log/MAXLEjn i M l i L E N / The parameters MINLEN and MAXLEH can be s p e c i f i e d by the user 28a Thresholds f o r Angle Quantlztion 29 based on p r i o r knowledge of the l i n e s being processed and should approximate the a c t u a l bounds on the len g t h s to be encountered. The "8" corresponds to the number of l e v e l s of q u a n t i z a t i o n . The net e f f e c t i s to transform the len g t h s onto the i n t e g e r s 1 through 8 such that the q u a n t i z a t i o n l e v e l s are c l o s e r together with s h o r t e r l e n g t h s . The angle between the two v e c t o r s at a p o i n t i s c a l c u l a t e d by r i g i d l y r o t a t i n g the two v e c t o r s i n order that the incoming v e c t o r l i e s along the p o s i t i v e x - a x i s . The angle made by the outgoing v e c t o r i s then j u s t the usual one with the r e s t r i c t i o n t h a t the angle must be between +U and -II . The correspondence between t h i s angle and the quantized angle i s given by F i g . 2.12. Thus i f the o r i g i n a l angle was between THRESHOLD(2) and THRESHOLD (3) the corresponding quantized angle would be 4, and so on. The standard values f o r these t h r e s h o l d s are approximately those depicted i n F i g . 2.12, but can be changed at w i l l by the user. The t h r e s h o l d s are bunched around 180° because most angles w i l l be i n t h i s range and t h i s i s the c r i t i c a l r e g i o n f o r p o i n t e l i m i n a t i o n . T h i s q u a n t i z a t i o n process i s a p p l i e d a l t e r n a t e l y to each angle and l e n g t h along the e n t i r e l i n e so that a l i n e t h a t o r i g i n a l l y appeared as i n Fig u r e 2.11 might r e s u l t i n : 0 4 2 3 8 3 3 2 4 1 0 where the O's i n d i c a t e ' undefined angles at the ends. When a p a r t i c u l a r p o i n t i s under c o n s i d e r a t i o n during the l e a r n i n g process t h i s quantized v e r s i o n of the l i n e i s reordered to correspond to the •view' of the l i n e as seen from that p o i n t . 30 There are a number c f ways that t h i s could be done and the way I have chosen i s as f o l l o w s : I f the l i n e i n the v i c i n i t y of a p o i n t P i i s as d e p i c t e d i n F i g u r e 2. 13a and the d i r e c t i o n of p r o c e s s i n g i s to the r i g h t then the l i n e i s transformed i n t o the c h a i n shown i n F i g u r e 2.13b. T h i s g i v e s a b i a s t o l o c k i n g ahead along the l i n e . E f f e c t i v e l y we p r o g r e s s i v e l y look f a r t h e r i n a l t e r n a t i n g d i r e c t i o n s along the l i n e . I f one end of the l i n e i s encountered then that d i r e c t i o n of view stops and i s continued i n the other d i r e c t i o n u n t i l t h a t end i s reached too. A b i a s i s given to a ngles i n t h i s scheme because i t seems that they are more important i n v i s u a l d i s c r i m i n a t i o n than are l e n g t h s . The l e a r n i n g process at a p o i n t begins by f e e d i n g the l i n e i n t h i s converted form i n t o a d e c i s i o n t r e e (see F i g 2.14a) i n order to come up with a v e r d i c t on whether or not the p o i n t should be a l t e r e d . T h i s s t r i n g of symbols determines a path through the d e c i s i o n t r e e u n t i l a t e r m i n a l node c o n t a i n i n g the v e r d i c t i s reached. For example i f the l i n e was represented by the sequence "3545..." then i t would reach the i n d i c a t e d node where the v e r d i c t i s t h a t the p o i n t should be a l t e r e d . In a d d i t i o n t o the v e r d i c t being l o c a t e d at the t e r m i n a l nodes there i s a l s o s t o r e d a measure of how ' s t r o n g ' or ' r e l i a b l e ' the v e r d i c t i s and a l s o how ' o l d ' i t i s ( i . e . , the number of times i t has been r e f e r e n c e d ) . Once the expected v e r d i c t has been determined i n t h i s way i t i s compared with the v e r d i c t of the user. I f they agree then the v e r d i c t a t t h a t t e r m i n a l node can simply be made 'stronger' D i r e c t i o n of processing > (\i L t AiJM L^, AiM Lt., AlouL-lo. (b) Transformation of a Line Figure 2.13 with respect to the point The Decision Tree and an Addition to i t Figure 2.14 31 and ' o l d e r * by a u n i t value. However i f they d i s a g r e e then there are s e v e r a l t h i n g s t h a t can be done: the v e r d i c t can be l e f t the same but made weaker, or the v e r d i c t can be changed, or the t r e e can s p r o u t new t e r m i n a l nodes from that node, each with i t s own v e r d i c t . Which of these three a l t e r n a t i v e s i s chosen depends on the depth o f the node, the 'age' and ' s t r e n g t h ' of the v e r d i c t and whether there are any more symbols l e f t i n the l i n e . These f a c t o r s are contained i n the f o l l o w i n g ALGOL-like e x p r e s s i o n : i f (4 * / 1_J - 1 \ - /STRENGTH_H\\ > 0 V V DEPTH MAXDEPTH/ \ AGE+1~ // then "SPRO0T" e l s e i f STRENGTH > 0 then "WEAKEN" e l s e "CHANGE"; The e f f e c t o f t h i s e x p r e s s i o n i s such that the deeper the node i s , the l e s s l i k e l y i t i s that the tree w i l l be expanded f u r t h e r . T h i s i s done to avoid growing e x c e s s i v e l y l a r g e t r e e s (e.g., the number of nodes i n a complete tree of depth d i s about 9**d which grows very q u i c k l y with d ) . Also i f the v e r d i c t i s n e a r l y as ' s t r o n g ' as i t i s ' o l d * and i t i s reasonably o l d i then i t has given good s e r v i c e and so should only be punished s l i g h t l y . T h i s i s done by making i t weaker by one u n i t . I f , however, i t i s young or o l d and weak then i t i s much more l i k e l y to have the v e r d i c t changed. In t h i s case the age i s incremented as usual but the s t r e n g t h i s reduced by the u n i t amount. I f , i n f a c t , i t has been decided to sprout more t e r m i n a l nodes then the v e r d i c t of a l l these new nodes, except one, i s s e t to agree with the v e r d i c t of the former t e r m i n a l node. The o p p o s i t e v e r d i c t i s given to the node reached by c o n s i d e r i n g the next symbol of the l i n e . For example i f the input l i n e i s the same as i n the 32 example above ( i . e . , "3545...") and i t has been decided to expand the t r e e because the user d i d not concur with the expected v e r d i c t , then the a d d i t i o n s to the t r e e w i l l appear as i n F i g u r e 2.14b. In t h i s manner the t r e e grows from being o n l y of depth 1 at the s t a r t of l e a r n i n g . There are two ways f o r the user to s p e c i f y the true v e r d i c t . One way i s to manually a l t e r the l e v e l s a t the same time. In other words the v e r d i c t comes d i r e c t l y from the person pushing one of the two f u n c t i o n keys at the g r a p h i c s t e r m i n a l . An advantage of t h i s method i s that a preview of the d e c i s i o n of the program i s a v a i l a b l e on the screen. T h i s can help the user guide the t r a i n i n g of the program. I f the l e v e l to which a p o i n t i s a l t e r e d i s lower than the l e v e l of d i s p l a y then the i n t e r n a l quantized v e r s i o n of the l i n e i s changed to r e f l e c t the d e l e t i o n o f t h i s p o i n t . T h i s a l l o w s the 'view* of the l i n e to be e f f e c t i v e l y expanded at no e x t r a c o s t . The other way to i n d i c a t e the true v e r d i c t i s to a l t e r the l e v e l s beforehand and then the v e r d i c t i s determined by whether the l e v e l of a p o i n t i s below a s p e c i f i e d l e v e l . T h i s has the advantage t h a t the same l i n e can be used many times to r e i n f o r c e the message. To help e v a l u a t e the behaviour of the program l e a r n i n g s t a t i s t i c s are a v a i l a b l e with both methods; These s t a t i s t i c s g ive a breakdown f o r each l i n e processed i n terms of the number of v e r d i c t s made s t r o n g e r and weaker and "changed" and the number o f times the t r e e was e n l a r g e d . In general, the program w i l l have l e a r n e d to c a p a c i t y when continued l e a r n i n g r e s u l t s mainly i n v e r d i c t s g e t t i n g s t r o n g e r with r e l a t i v e l y few 33 v e r d i c t s being made weaker or changed and only slew enlargement of the t r e e . 2.4 Automatic G e n e r a l i z a t i o n Once the program appears to have learned s a t i s f a c t o r i l y i t can be turned l o o s e on new l i n e s that are s i m i l a r to the l i n e s i t l e a r n e d on. T h i s i s done by s p e c i f y i n g the p a r t i c u l a r l i n e s , a l e v e l , and the t r a n s f o r m a t i o n to be performed on the l e v e l s of the p o i n t s to be s e l e c t e d . In t h i s case; once a l i n e has teen q u a n t i z e d , c o n v e r t e d , and fed i n t o the d e c i s i o n t r e e , then the v e r d i c t r e t u r n e d determines whether the p o i n t i s to be a l t e r e d . I f the new value f o r the point»s l e v e l f a l l s below the giv e n l e v e l then the quantized r e p r e s e n t a t i o n of the l i n e i s updated. T h i s automatic g e n e r a l i z a t i o n can be helped out by r a i s i n g the l e v e l s of some p o t e n t i a l l y " b o r d e r l i n e " p o i n t s . T h i s i s done so t h a t even i f these p o i n t s are l a t e r a l t e r e d the r e s u l t i n g l e v e l s w i l l s t i l l be s u f f i c i e n t l y high to ensure that they w i l l always be p a r t o f the context of nearby p o i n t s . A f t e r the l i n e s have been a l t e r e d the r e s u l t s can be d i s p l a y e d f o r i n s p e c t i o n and c o r r e c t i o n . Those s e c t i o n s "that have been g e n e r a l i z e d poorly can be redone manually. I f there i s some s i m i l a r i t y between these s e c t i o n s then the program can be taught some mere as these c o r r e c t i o n s are being made. T h i s w i l l h o p e f u l l y d i m i n i s h the chances of the same mistakes being made i n the f u t u r e . 34 Chapter I I I EXPERIMENTAL RESULTS 3. 0 I n t r o d u c t i o n There are a great many que s t i o n s that can be asked r e g a r d i n g the approach to the g e n e r a l i z a t i o n t h a t has been d e s c r i b e d i n the p r e v i o u s c h a p t e r . Three of the most important and wide ranging of these questions are: What i s the nature of people's p e r c e p t u a l responses to g e n e r a l i z e d o u t l i n e s ? Is i t p o s s i b l e to achieve s a t i s f a c t o r y g e n e r a l i z a t i o n of o u t l i n e s with p u r e l y l o c a l c o n s i d e r a t i o n s ? - How w e l l does the system perform with regard to the g e n e r a l i z a t i o n c f map o u t l i n e s ? The remainder of t h i s chapter i s devoted to a d i s c u s s i o n of experiments that were performed i n attempts to answer these g u e s t i o n s . 3.1 P e r c e p t u a l Response t c G e n e r a l i z a t i o n A major purpose of t h i s work i s to provide a way of g e n e r a l i z i n g map o u t l i n e s r e q u i r i n g a minimum c f data storage while r e t a i n i n g enough of the e s s e n t i a l components to be e a s i l y r e c o g n i z a b l e by people. I t i s t h e r e f o r e necessary to i n v e s t i g a t e how people respond to o u t l i n e s that have to be g e n e r a l i z e d d r a s t i c a l l y . Is the r e n d i t i o n of prominent f e a t u r e s the most important element of r e c o g n i t i o n or i s i t the maintenance of l i n e c h a r a c t e r t h a t i s primary? What r o l e does a e s t h e t i c s play? To help answer these questions two experiments were performed that i n v o l v e d people ranking a number of 35 g e n e r a l i z a t i o n s o f a p a r t i c u l a r o u t l i n e a c c o r d i n g to the degree to which they each resembled the o r i g i n a l o u t l i n e . Both experiments were conducted i n the same way except that the o u t l i n e s used were d i f f e r e n t . The o r i g i n a l l i n e , used i n both cases, was the o u t l i n e of the m u n i c i p a l i t y of West Vancouver (see F i g u r e 3.1) t h a t was d i g i t i z e d at a s c a l e of approximately 1:200000. A s m a l l e r s c a l e v e r s i o n (see F i g u r e 3.2) was p l o t t e d and mounted on a piece of opaque cardboard as were the va r i o u s g e n e r a l i z a t i o n s of t h i s o u t l i n e (see F i g u r e s 3.3 and 3.4). In each experiment the s u b j e c t was given cards with the o r i g i n a l o u t l i n e (marked with a "1") and i t s g e n e r a l i z a t i o n s (which were s h u f f l e d and marked with a l e t t e r ) and asked to arrange these cards i n order of the s i m i l a r i t y to the one marked "1". Each s u b j e c t was asked i n the same way and were given no guidance on what " s i m i l a r i t y " meant. The opaque mounting prevented o v e r l a y i n g the maps t o make comparisons d i r e c t l y and i n s t e a d f o r c e d the s u b j e c t s to compare the d i f f e r e n t v e r s i o n s mere by t h e i r i n d i v i d u a l appearance. The r e s u l t of these rankings i n the two experiments are recorded i n T a b l e s 3.1 and 3.2. Every t r i a l w i t h i n an experiment was performed by a d i f f e r e n t person although some i n d i v i d u a l s took part i n both. These s u b j e c t s h a r d l y r e p r e s e n t e d a c r o s s - s e c t i o n of s o c i e t y or even p o t e n t i a l i n t e r a c t i v e map u s e r s , coming, as they d i d , almost e n t i r e l y from among my c o l l e a g u e s and f r i e n d s . However, the d i v e r s i t y of o p i n i o n e x h i b i t e d by t h i s s m a l l sample i s , I b e l i e v e , i n d i c a t i v e of the range t h a t might be expected from a l a r g e r , l e s s homogeneous group and i s g u i t e s u f f i c i e n t f o r my purposes. The o u t l i n e s used i n the f i r s t experiment were de r i v e d from 35a LEVEL=0 WEST_VAN Outline of West Vancouver Municipality-Figure 3.1" O r i g i n a l West Vancouver Outline Figure 3.2 Versions of West Vancouver Outline f o r Experiment I ^ Versions of West Vancouver Outline f o r Experiment II Figure 3.4 Figure 3.4(continued) CD RESULTS FOR EXPERIMENT 1 Ranking of s i m i l a r i t y to o u t l i n e 1 T r i a l High Number 1 1 D E B C F G 2 C D E B F G 3 E D B C F G 4 E D B C F G 5 C D B E F G 6 E D C B F G 7 E D B C F G 8 E D B C F G 9 E D B C F G 10 E D C B F G TABLE 3.1 35g RESULTS FOR EXPERIMENT 2 Ranking of similarity to outline 1 Trial High Low Number 1 2 3 4 5 6 7 8 1 h. f b e c a • d g 2 b e e g d h a f 3 a c e b g - d f h 4 h b e e f d g a 5 e f b a c g d h 6 d b e g c a h f 7 b e d e g a h f 8 b e a c f h d g 9 b d e c g a h f 10 f h a e d b e g 11 b e h a f c g d 12 b e e h a g d f 13 d g e b a c h f 14 f h b a e c g d TABLE 3.2 36 the o r i g i n a l i n a v a r i e t y of ways. The gen e r a l aim was to reduce the number of p o i n t s to about 23, one quarter of the number of p o i n t s i n the o r i g i n a l (which i s 92). Following are d e t a i l s of the ways i n which the p o i n t s were s e l e c t e d f o r the v a r i o u s o u t l i n e s : - O u t l i n e A - Randomly. Every point was considered i n t urn and was s e l e c t e d with a p r o b a b i l i t y of 0.25. 22 p o i n t s . O u t l i n e B. Douglas #1. The method of Douglas (see Chapter 1) was used with a t h r e s h o l d d e v i a t i o n of 0.08". 23 p o i n t s . O u t l i n e C. Hand-picked. The p o i n t s were s e l e c t e d by hand to ensure t h a t the small i n l e t i n the lower r i g h t - h a n d corner remained open. 21 p o i n t s . O u t l i n e D. Douglas #2. The same as f o r o u t l i n e B except that the t h r e s h o l d was reduced to 0.06". 26 p o i n t s . - O u t l i n e E. Lang. P o i n t s were s e l e c t e d using a s l i g h t v a r i a t i o n of Lang's method (see Chapter 1) with a t h r e s h o l d d i s t a n c e of 0.07". 27 p o i n t s . - O u t l i n e F. Lar g e s t a n g l e s . The p o i n t s that had the 23 l a r g e s t angles ( i . e . g r e a t e r than 66°) of bend were s e l e c t e d . 25 p o i n t s . - O u t l i n e G. Every n'th p o i n t . Every f o u r t h point was kept. 24 p o i n t s . Note: the p o i n t s i n the u p p e r - l e f t and u p p e r - r i g h t hand c o r n e r s of the map were a u t o m a t i c a l l y kept to avoid gross d i s t o r t i o n s i n the cases where the 37 method used to o b t a i n the o u t l i n e d i d not s p e c i f y they be kept. T h i s was r e g u i r e d with o u t l i n e s A and G. There are a l s o s m a l l wiggles i n these o u t l i n e s t h a t do not correspond to a c t u a l p o i n t s . They a r i s e from the i n c r e m e n t a l nature of the Calcomp p l o t t e r that was used. By r e f e r r i n g to T a b l e 3.1 we can see that the average order of p r e f e r e n c e i s EDCBFGA. T h i s order was c a l c u l a t e d by adding up the p o s i t i o n numbers of each l e t t e r f o r each t r i a l . These t o t a l s are 16, 19, 32, 33, 50, 60, 70 r e s p e c t i v e l y . G e n e r a l l y people conformed to t h i s sequence, but i t i s the d e v i a t i o n s that are i n t e r e s t i n g . C and B are almost t i e d and i n f a c t E was p r e f e r r e d by more people than C. However, when C i s p r e f e r r e d i t i s by a g r e a t e r margin. T h i s i s probably due to the f a c t that the s m a l l i n l e t i n the lower r i g h t hand corner was l e f t open while i n B, D and E i t c l o s e d o f f . T h i s s u p p o s i t i o n i s borne out by comments made by the s u b j e c t s a f t e r they had f i n i s h e d ranking the o u t l i n e s . Some people s a i d that they regarded the accurate r e n d i t i o n of the lower r i g h t corner as the o v e r r i d i n g f a c t o r while o t h e r s s a i d the d e t a i l s along the l e f t s i d e were more important. Some but not a l l regarded the maintenance of the bumpy c h a r a c t e r along the bottom c e n t e r as an important c o n s i d e r a t i o n . The a c t u a l accuracy i n terms of the t o t a l (or i n t e g r a t e d ) d e v i a t i o n from the o r i g i n a l probably was net a c r u c i a l f a c t o r as some people's preference f o r B over D and D over E i n d i c a t e s . I t i s q u i t e l i k e l y that people would p r e f e r l i n e I I I to l i n e I I as a r e p r e s e n t a t i o n of l i n e I (see F i g u r e 3.5) although superimposing them as i n F i g u r e 3.6 shows that A Line and Two Possible Generalizations Figure A l l Three Lines Superimposed Figure 38 l i n e I I o b v i o u s l y d e v i a t e s much l e s s . G e n e r a l l y we can conclude from t h i s experiment that d i f f e r e n t people see maps i n d i f f e r e n t ways and that they respond to d i f f e r e n t a s p e c t s of them when making comparisons. There i s l i t t l e we can say about how to g e n e r a l i z e o u t l i n e s s a t i s f a c t o r i l y . T h i s i s p a r t l y because the o u t l i n e s used vary i n the number of p o i n t s along t h e i r boundaries. G e n e r a l l y , of course, the more p o i n t s one has a v a i l a b l e the b e t t e r the r e n d i t i o n p o s s i b l e . What would be of i n t e r e s t i s to see people's p r e f e r e n c e s among v a r i o u s v e r s i o n s of an o r i g i n a l map that a l l have the same number of p o i n t s . I t was with t h i s aim i n mind that a second experiment was designed and performed. The o u t l i n e s used i n the second experiment were a l l d e r i v e d i n r o u g h l y the same way. In a l l of the 8 g e n e r a l i z e d o u t l i n e s there i s the same b a s i c s e t of 19 p o i n t s together with f o u r other p o i n t s chosen from an a d d i t i o n a l f i x e d s et of 7. 1 Thus a l l o u t l i n e s have 23 p o i n t s (except d and )^.\arid' 'are; f a i r l y s i m i l a r . The average r a n k i n g , c a l c u l a t e d i n the same way as before, i s becahdfg and the t o t a l s are 33, 46, 57, 68, 69, 73, 76, 82 r e s p e c t i v e l y . C e r t a i n l i n e s are r a t e d f a i r l y c o n s i s t e n t l y , such as b, e and c, while others such as h, f and d are more c o n t r o v e r s i a l . T h i s can be seen by i n s p e c t i o n of Table 3.2 or more r i g o r o u s l y by adding the d e v i a t i o n s i n each t r i a l from t h e i r mean p o s i t i o n s . T h i s g i v e s t o t a l s of 19, 19, 23, 22, 33, 1 Except f o r d and g which have only 3 of the p o s s i b l e 7. 39 27, 34, 30 (where the order i s the same as b e f o r e ) . By l o o k i n g at the i n d i v i d u a l o u t l i n e s (see F i g u r e 3.4) we can p a r t i a l l y account f o r t h i s . Most people do not l i k e the sharp poi n t at the lower l e f t but there are some who do not mind. The c h a r a c t e r of the l i n e i n the middle of the l e f t i s important to some while f o r o t h e r s i t i s the o v e r a l l shape. The comments people made l a t e r to j u s t i f y t h e i r r a n k i n g support these views. Every person saw some p a r t i c u l a r aspects of the shape t c be most important while other aspects were r e l a t i v e l y unimportant. Gne person s a i d t h a t he was more i n t e r e s t e d i n bays than i n peninsulas and a t t r i b u t e d t h i s to the f a c t t h a t he looked at a c o a s t l i n e from the p o i n t of view of the land and not the sea. The tone and e x p r e s s i o n s used by people a l s o i n d i c a t e d that t h e i r p e r c e p t i o n was q u i t e s u b j e c t i v e . Often they were "bothered" by the presence or absence of p a r t i c u l a r f e a t u r e s as i f they were r e a c t i n g on a e s t h e t i c grounds as w e l l . I t h i n k t h a t t h i s experiment shews even mere c l e a r l y than the f i r s t that people have q u i t e d i f f e r e n t ways of looking at o u t l i n e s and that a s i n g l e technique f o r doing g e n e r a l i z a t i o n s w i l l not s a t i s f y everybody. Some people w i l l l i k e to see c h a r a c t e r p r e s e r v e d , others p a r t i c u l a r f e a t u r e s , and s t i l l o t h e r s the o v e r a l l shape. T h i s suggests that a method that can be s u i t e d to an i n d i v i d u a l ' s t a s t e s and p r e f e r e n c e s would enjoy an advantage over l e s s f l e x i b l e methods. I t i s the aim of the work d e s c r i b e d here t c provide such a f l e x i b l e system. 40 3.2 L o c a l _ B e d u c t i o n i I t i s g e n e r a l l y the case t h a t computer processing of i n f o r m a t i o n i s more e a s i l y and c o n v e n i e n t l y performed on a l o c a l r a t h e r than g l o b a l b a s i s . Computer a r c h i t e c t u r e and e x i s t i n g software discourage making d e c i s i o n s using i n f o r m a t i o n that i s widely s e p a r a t e d . It. i s u s u a l l y much simpler and cheaper to make d e c i s i o n s based on i n f o r m a t i o n t h a t i s r e s t r i c t e d s p a t i a l l y . In t h i s sense t h i s work i s no e x c e p t i o n . However, i t i s not c l e a r a £riori t h a t l o c a l c o n s i d e r a t i o n s w i l l be adequate to perform g e n e r a l i z a t i o n s a t i s f a c t o r i l y . Even i f we do not need f u l l y g l o b a l c o n s i d e r a t i o n s i t i s not obvious what p o i n t on the l o c a l -g l o b a l continuum i s most a p p r o p r i a t e f o r our purposes. C l e a r l y , making the d e c i s i o n to s e l e c t or r e j e c t a p o i n t depending only on the angle at t h a t p o i n t w i l l i n general be u n s a t i s f a c t o r y , but how much more of a l i n e does a program have to look at? We can get some estimate of a lower bound on the r e q u i r e d view by o b s e r v i n g how w e l l people perform at manually reducing o u t l i n e s when a l l t h a t can be seen at one time i s a small s e c t i o n . (If a person cannot do i t , then probably n e i t h e r can a machine.) An experiment to do j u s t t h i s was set up and performed. B a s i c a l l y the experiment to i n v e s t i g a t e the adeguacy of a l o c a l view i n v o l v e d a number of s u b j e c t s manually reducing an o u t l i n e of North Vancouver M u n i c i p a l i t y (see F i g u r e 3.7) i n the manner d e s c r i b e d i n Chapter 2. A s e c t i o n of the o u t l i n e c o n t a i n i n g at most 7 p o i n t s was d i s p l a y e d on the screen with a s m a l l "X" at one of the p o i n t s . The person would then press one of two buttons depending on whether that p o i n t was to be kept or 40a Outline of North Vancouver M u n i c i p a l i t y Figure 3.7 LEVEL=0 N0RTH_VRN_D1STRICT f 41 removed. I f the p o i n t was removed then the l i n e was re-drawn without t h a t p o i n t . In e i t h e r case the "X" moved to the next p o i n t . I f the M X W moved to second to the l a s t p o i n t , then the l i n e was re-drawn adding the next three p o i n t s and keeping the l a s t f o u r . In t h i s way every p o i n t along the o r i g i n a l o u t l i n e was c o n s i d e r e d i n turn and with no fewer than 2 p o i n t s cn e i t h e r s i d e . The s c a l e at which the i n d i v i d u a l fragments were d i s p l a y e d was the same f o r every fragment and was chosen so t h a t i f the whole o u t l i n e were d i s p l a y e d i t would j u s t f i l l the s c r e e n . The i n d i v i d u a l fragments were a l s o centered i n the middle of the screen to a v o i d g i v i n g s p a t i a l c l u e s . The task of g e n e r a l i z i n g a l i n e under such circumstances r e g u i r e s c o n s i d e r a b l e s k i l l and I suspected (based on my p e r s o n a l experience) t h a t the performance would depend cn p r a c t i s e . In order to give the s u b j e c t s some op p o r t u n i t y to l e a r n how to do i t they were given the o u t l i n e of West Vancouver t o s t a r t w i t h . They were shown f i r s t a l l of t h i s o u t l i n e on the screen and asked to aim f o r a r e d u c t i o n of t h r e e - q u a r t e r s ( i . e . l e a v i n g about 23 p o i n t s ) . The fragments were then d i s p l a y e d i n t u r n and p o i n t s e l i m i n a t e d . The reduced v e r s i o n was then d i s p l a y e d and the number of p o i n t s remaining counted. T h i s gave the person an o p p o r t u n i t y to see how much mere r u t h l e s s they would have to be i n pruning p o i n t s from the North Vancouver o u t l i n e . . As can be seen from Table 3.3, people were not very s u c c e s s f u l i n a c h i e v i n g the t h r e e - q u a r t e r s r e d u c t i o n . The next s t e p was the r e d u c t i o n of the North Vancouver o u t l i n e using only the s m a l l fragments without s e e i n g the whole t h i n g f i r s t and without knowing what i t was. The r e s u l t of these r e d u c t i o n s f o r 41a RESULTS FOR EXPERIMENT 3 Number of Points Remaining T r i a l West Vancouver North Vancouver Number (92 points o r i g i n a l l y ) (134 points o r i g i n a l l y ) 1 44 45 2 47 47 3 47 47 4 38 44 5 56 55 6 46 33 TABLE 3.3 42 both maps are shown i n F i g u r e s 3.9 to 3.14 with the o r i g i n a l s shown at the same s c a l e i n F i g u r e 3.8. In g e n e r a l terms we can see t h a t the g e n e r a l i z a t i o n was done f a i r l y w e l l although there are some g l a r i n g mistakes. Almost a l l the main f e a t u r e s are captured and the c h a r a c t e r of the c o a s t l i n e on the r i g h t - h a n d i s maintained. R e f e r r i n g to t h i s s e r i e s of f i g u r e s and to Table 3.3 i t i s c l e a r t h a t the s u b j e c t s d i d l e a r n to be more d r a s t i c i n t h e i r r e d u c t i o n . The average r e d u c t i o n f o r West Vancouver was s l i g h t l y over one-half of o r i g i n a l 92 p o i n t s while with North Vancouver the average r e d u c t i o n was s l i g h t l y above o n e - t h i r d of the o r i g i n a l 134 p o i n t s . T h i s was done i n s p i t e of the l a r g e number of long segments i n the lower l e f t c orner. One person i n p a r t i c u l a r (on T r i a l 6, F i g u r e 3.14) became e x c e s s i v e l y concerned about the d e s i r e d degree of r e d u c t i o n and removed a l a r g e p o r t i o n from the lower middle although the remainder c f the l i n e was done q u i t e s a t i s f a c t o r i l y . T h i s person a c t u a l l y l e f t l e s s than cne quarter of the p o i n t s remaining. In order to more f u l l y answer the question posed at the beginning of t h i s s e c t i o n much more experimentation would have to be done. I t would be i n t e r e s t i n g to see hew people's performance depended on the s i z e of the view a v a i l a b l e , the d e s i r e d degree of r e d u c t i o n , and on t h e i r experience doing g e n e r a l i z a t i o n i n t h i s manner. The e f f e c t of the c h a r a c t e r of the o u t l i n e s used i s a l s o an important f a c t o r that would have to be i n v e s t i g a t e d . R e l a t i v e l y smooth l i n e s w i l l present d i f f e r e n t problems than l i n e s i n which there are l a r g e angles between O r i g i n a l Outlines of West Vancouver and North Vancouver Figure 3.8 SB 43 c o n s e c u t i v e v e c t o r s . However, i n s p i t e of the l i m i t e d extent cf the t e s t i n g t h a t was done there i s s u f f i c i e n t evidence to suggest that i t i s not hopeless to expect a program oper a t i n g o n l y on a l o c a l b a s i s to perform g e n e r a l i z a t i o n s s a t i s f a c t o r i l y . 3-3 The S y s t e m ' s , G e n e r a l i z a t i o n Performance The t h i r d major ques t i o n that was asked at the beginning of t h i s c h apter was how well can the system d e s c r i b e d here l e a r n tc g e n e r a l i z e map o u t l i n e s . Since the system g e n e r a l i z e s by f i r s t l e a r n i n g to mimic a s e t of p r e v i o u s l y reduced o u t l i n e s , the q u e s t i o n can be broken down i n t o two p a r t s : How w e l l does i t mimic and how w e l l does i t do on o u t l i n e s i t has never met before? The f i r s t step i n attempting t c answer these guestions i s the s e l e c t i o n and manual r e d u c t i o n of an i n i t i a l s et of o u t l i n e s on which the system i s to l e a r n . In our case these l i n e s were chosen from the d i g i t i z e d boundaries cf some of E.C.'s Lower Mainland M u n i c i p a l i t i e s (see F i g u r e 3.15). The o u t l i n e s l a b e l l e d with the l e t t e r s A through F were chosen to be the b a s i c l e a r n i n g s e t . The reason t h a t these p a r t i c u l a r l i n e s were chosen r a t h e r than o t h e r s i s simply that they spanned the r e g i c n of the map and that they appeared to c o n t a i n a v a r i e t y of f e a t u r e s and l i n e types. These l i n e s were reduced by hand so that d i s p l a y e d at l e v e l 0 we have F i g u r e 3.16 and a t l e v e l 8 F i g u r e 3.17. This r e d u c t i o n was aimed to leave as c l o s e to one q u a r t e r of the o r i g i n a l number of p o i n t s i n each o u t l i n e as p o s s i b l e without e x c e s s i v e d i s t o r t i o n . The o r i g i n a l and remaining number of p o i n t s f o r each l i n e i s shown i n T a b l e 3.5. T h i s b a s i c l e a r n i n g 43a 43b LEVEL-8 Reduced Outlines f o r Learning Figu 44 s e t of o u t l i n e s was then fed i n t o the l e a r n i n g component of the system i n the manner d e s c r i b e d i n Chapter 2 with a p o i n t t h r e s h o l d l e v e l of e i g h t . The angle and l e n g t h parameters were standard 1 and the maximum a l l o w a b l e depth i n the d e c i s i o n t r e e was twelve, thus p e r m i t t i n g a view of the l i n e about the same as was permitted f o r the experiment d e s c r i b e d i n the previous s e c t i o n . T h i s l e a r n i n g procedure was performed f i v e times i n s u c c e s s i o n to r e i n f o r c e the message. fifter each i t e r a t i o n s t a t i s t i c s were produced to i n d i c a t e how many t e r m i n a l node v e r d i c t s were made s t r o n g e r , weaker or changed and how many times new nodes were added to the d e c i s i o n tree (see Table 3.4). In a d d i t i o n , a f t e r each i t e r a t i o n , the system was given the l e a r n i n g s e t at l e v e l zero to g e n e r a l i z e using i t s c u r r e n t knowledge. The r e s u l t i n g o u t l i n e s are shown i n F i g u r e s 3.18 through 3.22 and the numbers of p o i n t s i n each of these o u t l i n e s i s g i v e n i n Table 3.5. There are s e v e r a l ways of using the r e s u l t s mentioned so f a r t o answer the q u e s t i o n of how well the system can mimic a person's g e n e r a l i z a t i o n behavior. The f i r s t step i s tc ensure that the system i s a c t u a l l y capable c f d u p l i c a t i n g the person's performance. T h i s c l e a r l y i s the case as can be seen by comparing the r e s u l t s a f t e r f i v e i t e r a t i o n s (Figure 3.22) with the model l i n e s shown i n F i g u r e 3.17. The only r e a l l y d i s c e r n a b l e d i f f e r e n c e occurs i n the upper r i g h t corner of o u t l i n e F and even then there can be doubt as t c whether the 1 i e . The angle t h r e s h o l d s (in radians) were 0.65, 2.15, 2.80 and 3.05 r e s p e c t i v e l y and the minimum and maximum lengths were 0.01" and 0.5" at the s c a l e o f F i g u r e 3.15 44a Figure 3.18 44b LEVEL;r8 R e d U C 6 d 0 u t l i n e s a f t e r 4 Learning I t e r a t i o n s Figure 3.21 LEVEL = 8 R e d U C 6 d 0 u t l i n e s a f t e r 5 Learning Iterations Figure 3.22 45 manually produced v e r s i o n g i v e s a b e t t e r r e n d i t i o n of the o r i g i n a l l i n e than the a u t o m a t i c a l l y generated r e s u l t . I t i s necessary to note that at t h i s stage a l l the measures i n d i c a t e that the l e a r n i n g has s t a b i l i z e d . The f a c t t h a t the system i s capable of f a i r l y p r e c i s e mimicry i s encouraging because i t suggests that the l o c a l viewing of l i n e s t h a t the system i s f o r c e d to adept i s q u i t e adequate. If the system can account f o r a person's g e n e r a l i z a t i o n behavior over a r e p r e s e n t a t i v e s e t cf l i n e s then th e r e should be enough i n f o r m a t i o n a v a i l a b l e l o c a l l y to s a t i s f a c t o r i l y g e n e r a l i z e any l i n e . However, the problem remains of how to ensure t h a t one has a t r u l y r e p r e s e n t a t i v e set of l i n e s . The next step i n e v a l u a t i n g the system's a b i l i t y to mimic i s to determine the r a t e at which i t l e a r n s . There are s e v e r a l measures a v a i l a b l e to us and they a l l give roughly c o n s i s t e n t r e s u l t s . For each i t e r a t i o n we can look at the t o t a l number of o i s c l a s s i f i c a t i o n s of p o i n t s , the d i f f e r e n c e between the number of p o i n t s i n the master copy and i m i t a t i o n (see Table 3.5), and the changes t h a t the d e c i s i o n t r e e has undergone (see Table 3.4). A graph summarizing t h i s l a s t set of i n f o r m a t i o n i s shown i n F i g u r e 3.23. From i t we can see t h a t the l e a r n i n g seems to be f a i r l y r a p i d , although there i s no independent standard f o r comparison. Of course the r e a l t e s t of the system comes when we look at how w e l l i t g e n e r a l i z e s o u t l i n e s that i t has never met before. To t e s t t h i s aspect of performance the g e n e r a l i z a t i o n component 45a Weakened verd i c t s 1 2 3 4 5 Learning I t e r a t i o n Number Learning Progress Figure 3.23 45b Learning S t a t i s t i c s Number of Changes to Terminal Node Verdicts I t e r a t i o n 1 Line T o t a l I t e r a t i o n 2 Line T o t a l I t e r a t i o n 3 Line T o t a l I t e r a t i o n 4 Line T o t a l I t e r a t i o n 5 Line A B C D E F A B C D E F A B C D E F A B C D E F A B C D E F T o t a l Stronger 71 105 . • 30 45 22 99 372 76 121 34 51 26 113 421 88 129 35 54 26 124 456 89 133 35 57 27 127 468 89 133 36 58 27 129 472 Weaker 0 2 1 2 0 4 9 3 0 0 0 0 1 4 1 0 0 1 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Changed 6 13 4 4 6 15 48 8 8 1 2 3 5 27 1 2 1 0 3 3 10 1 1 2 1 1 3 9 2 0 0 1 1 1 5 Number of Tree Expansions 15 14 2 8 1 13 53 5 5 2 6 0 12 30 2 3 1 4 0 4 14 2 0 0 1 1 1 5 1 1 1 0 1 1 5 Table 3.4 45c Learning Results Number of Points in Outline :line Original Learning After Learning Iteration Outline Master 1 2 3 4 5 A 92 23 33 29 29 29 23 B 134 41 48 40 41 41 41 C 37 19 19 19 19 19 19 D 59 16 15 15 15 15 15 E 29 10' 11 11 11 11 10 F 131 33 36 34 33 33 33 Table 3.5 Generalization Results Number of Points In Outline Outline Original 1/4 Original Learning Iteration Douglas Method 1 2 3 4 5 0.05" 0.0< A 92 23 . 33 29 29 29 23 16 26 B 134 35 48 40 41 41 41 30 35 C 37 9 19 19 19 19 19 14 16 D 59 15 15 15 15 15 15 13 15 E 29 7 11 11 11 11 10 10 10 F 131 33 36 34 33 33 33 32 33 G 308 77 44 39 40 40 39 38 48 H 51 13 10 12 11 11 11 . 10 10 I 23 6 5 5 8 8 8 5 5 J 123 31 18 15 17 15 16 19 24 K 38 10 9 9 9 10 9 5 9 L 55 14 13 15 15 15 14 10 11 M 27 7 5 5 5 5 4 6 6 N 182 46 26 28 25 24 24 24 32 0 29 7 6 6 5 5 5 4 4 P 51 13 8 9 8 8 8 5 8 Q 26 7 5 5 5 5 5 5 5 Table 3.6 46 of the system was presented a f t e r each of the f i v e l e a r n i n g i t e r a t i o n s , with a l l the o u t l i n e s shown i n F i g u r e 3.15. The r e s u l t i n g o u t l i n e s are found i n F i g u r e s 3.24 through 3.28, while Table 3.6 gives the number of p o i n t s i n each o u t l i n e o r i g i n a l l y and the number of p o i n t s a c t u a l l y remaining a f t e r each g e n e r a l i z a t i o n . We can see that the g e n e r a l i z a t i o n has been s u c c e s s f u l i n that the g e n e r a l shapes of the o u t l i n e s have been well maintained and that the r e d u c t i o n i n the number c f p o i n t s i s of the d e s i r e d degree. However, there are some g l a r i n g flaws ( e s p e c i a l l y i n o u t l i n e N) that immediately catch the eye. There are a l s o a number of other s e r i o u s d i s t o r t i o n s , seme c f which d i m i n i s h with i n c r e a s e d l e a r n i n g although there i s g e n e r a l l y l i t t l e change throughout the seguence. T h i s i s somewhat d i s c o u r a g i n g s i n c e , i n view of the f a c t that the l e a r n i n g was v i r t u a l l y s t a b i l i z e d , we cannot look to a d d i t i o n a l l e a r n i n g to remedy the s i t u a t i o n . The a c t i o n s that are l e f t open are: a l t e r the l e a r n i n g parameters ( i e . the angle t h r e s h o l d s , minimum/maximum len g t h s and t r e e depth), i n c r e a s e the l e a r n i n g s e t making i t more r e p r e s e n t a t i v e , re-reduce the l e a r n i n g set and g i v e a more general r e n d i t i o n , or manually reduce the o f f e n d i n g p o r t i o n s while l e a r n i n g at the same time. The l a s t a l t e r n a t i v e i s a p a r t i c u l a r case of the preceding one and both are reasonable s t e p s to take i f there i s a l a r g e , r e l a t i v e l y homogeneous s e t of o u t l i n e s t h a t need to be g e n e r a l i z e d . The second a l t e r n a t i v e i s probably not l i k e l y t c make much d i f f e r e n c e e s p e c i a l l y s i n c e i t i s not c l e a r where the c u r r e n t manual r e d u c t i o n could be improved s i g n i f i c a n t l y . I f we r e s t r i c t 46a 46b 46c 46d 46e 47 o u r s e l v e s to the o r i g i n a l given s e t of o u t l i n e s then an obvious st e p t o take i s to a l t e r seme of the l e a r n i n g parameters. Another way to e v a l u a t e the g e n e r a l i z a t i o n performance of t h i s l e a r n i n g method i s to compare i t with other methods of g e n e r a l i z a t i o n . , The method chosen f o r comparison i s the one proposed by Douglas (1972) and d e s c r i b e d i n Chapter 1. The r o u t i n e s reguiEed f o r t h i s method are s t r a i g h t - f o r w a r d and were e a s i l y i n c o r p o r a t e d i n t o the system as j u s t another means f o r s e l e c t i n g subsets of p o i n t s whose values are t c undergo a s p e c i f i e d t r a n s f o r m a t i o n . T h i s method was chosen f o r comparison not only f o r convenience, but a l s o because i t i s a good method. I t has the advantage t h a t e f f e c t i v e l y g l o b a l c o n s i d e r a t i o n s are i n v o l v e d i n the s e l e c t i o n of p o i n t s , and i t a l s o guarantees that no p o i n t i n the o r i g i n a l l i n e i s f u r t h e r than a s p e c i f i e d d i s t a n c e from the g e n e r a l i z e d v e r s i o n . Thus some of the g l a r i n g mistakes encountered with the p r e v i o u s method w i l l be avoided. Using t h i s method with d e v i a t i o n t h r e s h o l d s of 0.05" and 0.04" the complete s e t of o u t l i n e s was g e n e r a l i z e d . The r e s u l t i n g o u t l i n e s are shown i n F i g u r e s 3.29 and 3.30 r e s p e c t i v e l y while the l a s t two columns i n Table 3.6 r e c o r d the number of p o i n t s i n each of the o u t l i n e s . There i s l i t t l e doubt that these are, on the whole, b e t t e r g e n e r a l i z a t i o n s than the e a r l i e r ones. Also , the computation r e q u i r e d to do them i s c o n s i d e r a b l y l e s s (approximately 2.0 seconds of CPU time as opposed to 7.5 s econds). I t i s t h e r e f o r e c l e a r from t h i s comparison that the l e a r n i n g method does have some d e f i c i e n c i e s . The l e a r n i n g method f o r g e n e r a l i z a t i o n does, however, enjoy 47a 47b LEVEL=9 48 an advantage when i t comes to s p e c i a l types of l i n e s t h a t are being g e n e r a l i z e d f o r s p e c i a l purposes. T h i s i s because the g e n e r a l i z a t i o n i s done e s s e n t i a l l y by r e c o g n i z i n g p a t t e r n s w i t h i n the l i n e , an extreme example i l l u s t r a t e s t h i s p c i n t . S t y l i z e d v e r s i o n s of the a r a b i c numerals 0,1,2,,..,9 were d i g i t i z e d (see F i g u r e 3.31) and then given to the l e a r n i n g component (with s u i t a b l e adjustment of parameters) with the i n s t r u c t i o n that the numerals 3,4 and 9 were to be r e t a i n e d while the remaining numerals were to be reduced to a p o i n t , a f t e r each of the d i g i t s had been presented s e v e r a l times they were a l l reduced a c c o r d i n g to what had been l e a r n e d . The r e s u l t appears i n F i g u r e 3.32. a more p r a c t i c a l example i n v o l v e s the g e n e r a l i z a t i o n of a c o a s t l i n e c o n t a i n i n g docks. From the o u t l i n e d e p i c t e d i n F i g u r e 3.33 one person (a s h i p * s p i l o t , say) may want a g e n e r a l i z a t i o n that keeps the docks (Figure 3.34) while another person may want the docks removed to show the o r i g i n a l landform (Figure 3.35). These two v e r s i o n s were used to teach the system (cn separate o c c a s i o n s ) and a f t e r f o u r i t e r a t i o n s the l e a r n i n g had s t a b i l i z e d to the p o i n t t h a t g e n e r a l i z a t i o n s of the o r i g i n a l l i n e were v i r t u a l l y i d e n t i c a l to t h e i r r e s p e c t i v e models (see F i g u r e s 3.36 and 3.37). The same l e a r n i n g was employed to g e n e r a l i z e a p o r t i o n of the Vancouver wat e r f r o n t (see F i g u r e 3.38, which i s an enlargement of a s e c t i o n of the upper edge of o u t l i n e G i n F i g u r e 3.15) g i v i n g the two v e r s i o n s shown i n F i g u r e s 3.39 and 3.40. The key i n t h i s case was the adjustment cf the angle t h r e s h o l d s to r e c o g n i z e r i g h t a n g l e s . LEVEL=0 Arabic Numerals Figure 3.31 48b L LEVEL=8 Reduced Arabic Numerals Figure 3.32 48c A Coastline with Docks LEVEL=0 DOCKS Figure 3.33 Reduced Coastline for Learning (docks kept) Figure 3.34 LEVEL=8 DQCKS_KEPT Reduced Coastline tor Learning (docks remove Figure 3.35 _EVEL^ 8 DQCKS_GQNE 48f LEVEL=8 Reduced Coastline a f t e r Learning (docks kept) Figure 3.36 LEVELS Reduced Coastline after Learning (docks removed) Figure 3.37 48h O r i g i n a l Vancouver Waterfront LEVELS VRNCOUVER_DOCKS Figure 3.38 Reduced Vancouver Waterfront (docks kept) LEVEL=8 F i§u r e 3-39 LEVEL=8 Reduced Vancouver Waterfront (docks removed) Figure 3.40 49 3.4 Other.Questions Apart from the qu e s t i o n s that have teen d i s c u s s e d so f a r , there are many other q u e s t i o n s that can be asked about the system and answered through experiments. One l a r g e l y untouched problem i s that o f measuring the homogeneity of a s e t cf l i n e s and s e l e c t i n g r e p r e s e n t a t i v e subsets. I have made some i n i t i a l attempts i n t h i s area by l o o k i n g at the d i s t r i b u t i o n c f lengths and angles w i t h i n l i n e s and a l s o by c o n s i d e r i n g the guantized lengths and angles along l i n e s as Markov c h a i n s . Nothing very promising has yet emerged, however. Without some understanding of the s i m i l a r i t i e s and d i f f e r e n c e s between l i n e s the s e l e c t i o n of a r e p r e s e n t a t i v e l e a r n i n g s et and the assignment of parameter values i s very much a h i t or miss a f f a i r . A r e l a t e d problem that deserves more a t t e n t i o n i s how the r a t e of l e a r n i n g and the t r a n s f e r a b i l i t y of t h i s l e a r n i n g i s a f f e c t e d by p a r t i c u l a r assignments o f parameter v a l u e s . Another i n t e r e s t i n g q u e s t i o n t h a t might be asked concerns the "psychology" of the l e a r n i n g process. Since the l e a r n i n g mechanism i s EPAM-like (Feigenbaum (1963)) we should expect to see evidence o f such p s y c h o l o g i c a l f e a t u r e s of l e a r n i n g as o s c i l l a t i o n , f o r g e t t i n g , i n t e r f e r e n c e and so on. 50 Chapter IV EVALUATION 4.0 I n t r o d u c t i o n There are three main aspects of t h i s work that may be of some s i g n i f i c a n c e . These are : -an encoding scheme that i s s u i t a b l e f o r the r e p r e s e n t a t i o n of h i e r a r c h i c a l l y g e n e r a l i z e d l i n e s , -an i n t e r a c t i v e g r a p h i c s system t h a t p r o v i d e s the means to manipulate l i n e s represented i n t h i s way and g e n e r a l i z e them e i t h e r manually or a u t o m a t i c a l l y . -a system that performs g e n e r a l i z a t i o n by l e a r n i n g to r e c o g n i z e p a t t e r n s i n l i n e s . These are summarized c r i t i c a l l y i n t h i s chapter as well as r e l a t e d t o p i c s that I t h i n k deserve f u t u r e i n v e s t i g a t i o n . Some of my e t h i c a l concerns are touched on and the chapter ends with a summary and c o n c l u s i o n s . 4•1 C r i t i c a l Summary I b e l i e v e the idea of a l i n e with l e v e l s attached to the p o i n t s to be a p o t e n t i a l l y u s e f u l n o t i o n . T h i s i s because s e v e r a l v e r s i o n s of a l i n e , each g e n e r a l i z e d to a d i f f e r e n t degree, can be represented w i t h i n a s i n g l e e n t i t y . Apart frcm being compact, i t a l s o a l l o w s a c o n c e p t u a l l y e l e g a n t way of r e f e r r i n g to a whole f a m i l y of r e l a t e d l i n e s . For example, with o n l y a s i n g l e l e v e l attached to each p o i n t , r e p r e s e n t i n g the importance of the p o i n t i n conveying the message of the l i n e , i t i s p o s s i b l e to c o n v e n i e n t l y s p e c i f y the enlargement process observed i n the sequence of F i g u r e s 4.1 through 4.3. T h i s i s 50a with reduced D e t a i l Figure 4.1 LEVEL - 4 Enlargement of Figure 4.1 with more D e t a i l Figure 4.2 50c LEVEL = 0 Enlargement of Figure 4.2 with more D e t a i l Figure 4.3 51 t y p i c a l o f many i n t e r a c t i v e g r a p h i c s a p p l i c a t i o n s and i n t h i s case can be handled by simply s p e c i f y i n g the l i n e s to be d i s p l a y e d , the window parameters and the r e l a t i o n s h i p between s c a l e and l e v e l of d i s p l a y . For the enlargement observed i n F i g u r e H.U two l e v e l s attached to each point are adeguate f o r the r e p r e s e n t a t i o n of the s t r e e t s t h a t are i n v o l v e d . The compactness c f encoding a r i s e s from the f a c t t h a t the i n d i v i d u a l p o i n t s that are shared by s e v e r a l v e r s i o n s of the same l i n e need be st o r e d only once. The a c t u a l s a v i n g c f course depends on f a c t o r s such as the c h a r a c t e r of the l i n e s , the number of l e v e l s o f g e n e r a l i z a t i o n , and the p a r t i c u l a r i n t e r n a l machine r e p r e s e n t a t i o n of the p o i n t s . T h i s l i n e r e p r e s e n t a t i o n technique does have some drawbacks. I t means that every time a l i n e i s used each p o i n t must be i n s p e c t e d to determine i f i t i s to be i n c l u d e d . I t might be cheaper and more convenient, i f a good g e n e r a l i z a t i o n scheme i s a v a i l a b l e , to g e n e r a l i z e the l i n e to the d e s i r e d degree every time. T h i s way the s p e c i f i c needs do not have to be a n t i c i p a t e d and a l l the g e n e r a l i z a t i o n done beforehand. The r e l a t i v e t r a d e o f f s here are j u s t another i n s t a n c e of the " d i s p l a y s t r u c t u r e s " versus " d i s p l a y procedures" (Newman (1971)) argument. An i n t e r a c t i v e g r a p h i c s system s u i t a b l e f o r l i n e g e n e r a l i z a t i o n i s another aspect c f t h i s work that i s of some i n t e r e s t . I t pr o v i d e s a means of b r i n g i n g i n l i n e s from e x t e r n a l s t o r a g e , a s s o c i a t i n g v a l u e s with the points along the l i n e s and d i s p l a y i n g these l i n e s at va r i o u s l e v e l s . The manipulation cf ft St. h ^ t . The Enlargement of Street Intersection Figure 4.4 52 values can be done manually using a r a p i d l y updated image on the screen of a g r a p h i c s t e r m i n a l or e l s e by a v a r i e t y cf automatic methods with the r e s u l t s a v a i l a b l e w i t h i n seconds f o r c o r r e c t i o n i f necessary. Such c a p a b i l i t i e s are d e s i r a b l e f e a t u r e s i n any g e n e r a l i z a t i o n and geographic e d i t t i n g scheme. However, s i n c e the system was designed mainly as a v e h i c l e f o r developing and t e s t i n g the l e a r n i n g p a r t , i t l a c k s many of the components necessary f o r i t to be a p r a c t i c a l and u s e f u l system. It has, I b e l i e v e , a sound, b a s i c s t r u c t u r e and c onceptual framework but has a number of i n c o n s i s t e n c i e s and i s o f t e n clumsy to use. I c o u l d t o l e r a t e these s i n c e I knew i t i n t i m a t e l y and had r e s t r i c t e d g o a l s , but they would prove to be stumbling blocks f o r t h e average user. For example, i f one makes a mistake i n a s s i g n i n g a value i t can o f t e n be d i f f i c u l t to c o r r e c t s i n c e p o i n t s have to be processed s e q u e n t i a l l y w i t h i n l i n e s . Baking p r o v i s i o n f o r the use of the l i g h t pen or c r o s s h a i r s would net be hard to do and would overcome much of t h i s c u r r e n t d i f f i c u l t y . At p r e s e n t there i s no way to change the c o o r d i n a t e s of a p o i n t although t h i s would be necessary i n many r e a l a p p l i c a t i o n s . The f a c t t h a t the system i s not p r e s e n t l y very u s e f u l i s a shortcoming of t h i s work s i n c e through i t s use not only would more people b e n e f i t , but a l s o a much t e t t e r understanding of g e n e r a l i z a t i o n could be o b t a i n e d . However, the system does r e p r e s e n t an i n i t i a l s tep and does have p o t e n t i a l f o r development i n t o a f l e x i b l e and u s e f u l t o o l f o r map x g e n e r a l i z a t i o n . The major emphasis i n t h i s work has been the development of a technique f o r the g e n e r a l i z a t i o n of map o u t l i n e s ' which 53 operates by r e c o g n i z i n g p a t t e r n s that have been taught to i t by people. The aim of t h i s g e n e r a l i z a t i o n i s to produce maps s u i t a b l e f o r use i n i n t e r a c t i v e graphic s i t u a t i o n s , which means they must r e q u i r e much l e s s data storage but at the same time r e t a i n t h e i r r e c o g n i z a b i l i t y . Since people have widely d i f f e r i n g views about the s i m i l a r i t y of maps and s i n c e these g e n e r a l i z e d maps may be used f o r a v a r i e t y of purposes there i s a need to t a i l o r the g e n e r a l i z a t i o n to a p a r t i c u l a r i n d i v i d u a l ' s wants and t a s t e s . The system d e s c r i b e d p r e v i o u s l y was c o n s t r u c t e d to s a t i s f y t h i s need by l e a r n i n g to mimic the user's behaviour a t g e n e r a l i z i n g l i n e s manually. Experiments with people suggest t h a t a program should be able t o g e n e r a l i z e by r e c o g n i z i n g f a i r l y l o c a l p a t t e r n s w i t h i n l i n e s land i n f a c t the performance of the system bears t h i s out. I t i s able to l e a r n to mimic almost p r e c i s e l y the person, with r e l a t i v e l y few l e a r n i n g t r i a l s . I t i s a l s o a b l e to g e n e r a l i z e new l i n e s but i s not as r e l i a b l e nor as p r o f i c i e n t as e x i s t i n g a n a l y t i c methods with g e n e r a l types of l i n e s . T h i s appears to be due to gaps or holes i n t he l e a r n i n g that are a r e s u l t c f not having a r e p r e s e n t a t i v e enough s e t of l i n e s to l e a r n from and not being able to g e n e r a l i s e i t s l e a r n i n g s u f f i c i e n t l y from the cases ^presented to i t . While I have l i t t l e doubt that the system c o u l d s a t i s f a c t o r i l y g e n e r a l i z e any reasonably homogeneous set of l i n e s , the t r o u b l e taken to do t h i s would not be worthwhile. L i k e a d e l i c a t e instrument i t would r e q u i r e a great d e a l of t i n k e r i n g before working p r o p e r l y . T h i s r a t h e r d e f e a t s the purpose of being e a s i l y s u i t e d to an i n d i v i d u a l ' s requirements. One p o s s i b l e way to overcome t h i s d i f f i c u l t y i s to have a b a s i c 54 r e p e r t o i r e of l e a r n i n g l i n e s that c o n t a i n many of the commonly o c c u r r i n g f e a t u r e s . Then the system i s taught with e x t r a l i n e s that are s p e c i a l l y chosen to "tune" i t f o r a p a r t i c u l a r a p p l i c a t i o n , another disadvantage of the c u r r e n t system i s that i t i s s i g n i f i c a n t l y more expensive to use than ether methods, both i n terms of p r o c e s s i n g and storage requirements. Perhaps with d e c r e a s i n g hardware c o s t s t h i s f a c t o r w i l l d i m i n i s h i n importance as an o b s t a c l e to the a p p l i c a t i o n of t h i s technique f o r g e n e r a l i z a t i o n . 4.2 Future work Sin c e the technique f o r q e n e r a l i z a t i o n i n t h i s t h e s i s i s new t h e r e are s e v e r a l areas that r e q u i r e f u r t h e r i n v e s t i g a t i o n before the technique becomes a u s e f u l one. One such area concerns the way i n which people p e r c e i v e and recognize maps, e s p e c i a l l y when t h e i r data content has been reduced d r a s t i c a l l y . Related to t h i s , t h e r e must be more study of o u t l i n e g e n e r a l i z a t i o n . What are the v a r i o u s c r i t e r i a that dermine how w e l l a p a r t i c u l a r g e n e r a l i z a t i o n approximates the o r i g i n a l l i n e ? I t i s t h i s q u e s t i o n that has been at the heart of my i n v e s t i g a t i o n . another area of i n t e r e s t i s i n t r y i n g a l t e r n a t i v e techniques of p a t t e r n r e c o g n i t i o n f c r g e n e r a l i z a t i o n . C u r r e n t l y each p o i n t i s considered i n t u r n and i t s immediate environment i n s p e c t e d to determine whether the point should be removed or not. T h i s approach was taken simply f o r convenience but i t would perhaps he more l o g i c a l to r e c o g n i z e c e r t a i n f e a t u r e s in l i n e s (such as bays, i n l e t s , docks, rocky s h o r e l i n e s , p e n i n s u l a s . 55 etc.) and to g e n e r a l i z e the whole f e a t u r e a t once. E i t h e r the f e a t u r e c o u l d be removed completely or r e p l a c e d by a few s u g g e s t i v e l i n e s or j u s t s i m p l i f i e d s l i g h t l y . Which of the p o s s i b l e a c t i o n s i s taken c o u l d be chosen a c c o r d i n g t c v a r i o u s p r o b a b i l i t i e s t h a t are dependent on v a r i o u s parameters of the f e a t u r e so t h a t i t would be p o s s i b l e to maintain the c h a r a c t e r of l a r g e s e c t i o n s of o u t l i n e {e.g., a deeply indented c o a s t l i n e such as that of northern B r i t i s h Columbia) . In order to o b t a i n a r e p r e s e n t a t i v e l e a r n i n g s e t f o r any p a t t e r n r e c o g n i t i o n scheme more work must be done to c a t e g o r i z e d i f f e r e n t types c f l i n e s . On a more co n c r e t e l e v e l there i s much to be done on the c u r r e n t l y implemented technique before i t s p o t e n t i a l f o r improvement i s exhausted. Apart from seeing i n more d e t a i l how the l e a r n i n g and g e n e r a l i z a t i o n performance depend on parameter values and on the types of l i n e s used i n the l e a r n i n g , m o d i f i c a t i o n to the h e u r i s t i c s employed i n the l e a r n i n g component might a l s o l e a d to s i g n i f i c a n t l y improved performance. I suspect that changes to the way i n which the d e c i s i o n t r e e i s expanded co u l d be p a r t i c u l a r l y f r u i t f u l . 4.3 E t h i c a l Concerns Approximately h a l f of the papers that I made use of i n my work were supported by the U.S.A. M i l i t a r y . T h i s d i s t u r b s me because i t makes me wonder whether the uses to which my work i s put, i f any, w i l l be b e n e f i c i a l . T h i s f a c t alone i s not s u f f i c i e n t to convince me that I should do other work but i t i s an aspect that I must c o n s i d e r . What d i s t u r b s me more i s that other people are apparently not so concerned about the p o t e n t i a l 56 uses of t h e i r work. Very seldom are the dangers of the p o t e n t i a l a p p l i c a t i o n s of work d i s c u s s e d . Nowhere have I found any mention of the dubious use of p a t t e r n r e c o g n i t i o n i n the a n a l y s i s of a i r photos f o r m i l i t a r y espionage f o r i n s t a n c e , an o f t e n c i t e d a p p l i c a t i o n . There should be a much more open d i s c u s s i o n of how r e s e a r c h might be used and what the consequences of t h i s use might be. I b e l i e v e t h i s to be e s s e n t i a l i f rese a r c h i s going to be of net b e n e f i t to mankind. 4.4 C o n c l u s i o n s I t has been a p r i n c i p a l aim of mine in doing t h i s work to e x p l o r e techniques f o r making the computer a u s e f u l t o o l to serve people. The problem of g e n e r a l i z i n g map o u t l i n e s f o r use i n i n t e r a c t i v e g r a p h i c s s i t u a t i o n s i s one area which r e g u i r e s of a computer system a c e r t a i n amount of t a i l o r i n g to an i n d i v i d u a l ' s needs. I b e l i e v e I have shown that the a p p l i c a t i o n of i n t e r a c t i v e g r a p h i c s and p a t t e r n r e c o g n i t i o n to t h i s problem can be f r u i t f u l i n p r o v i d i n g f l e x i b l e enough systems. ' 57 JIBlICGBaPHX Attneave, Fred (1954), " I n f o r m a t i o n a l Aspects of V i s u a l P e r c e p t i o n " , P s y c h o l o g i c a l Review, Volume 61, pp183-193. Blum, H. (1964), "A Transformation f o r E x t r a c t i n g New D e s c r i p t o r s of Shape", Symposium on Models f o r the P e r c e p t i o n of Speech and V i s u a l Form, Wather-Dunn Heiant (eds.), pp362-380. Deeker, Gordon (1970), " I n t e r a c t i v e Graphics and a Planning Problem", M.Sc. T h e s i s , Department of Computer S c i e n c e , U n i v e r s i t y of A l b e r t a (Edmonton), ( F a l l 1970). Deeker, G. S Penny, J.P. (1972), "Cn I n t e r a c t i v e Map Storage and R e t r i e v a l " , INFOS, Volume 10, #1, pp6 2-74. Douglas, David (1972), P e r s o n a l communication - not yet p u b l i s h e d . Feder, Jerome (1968), "Languages cf Encoded Line P a t t e r n s " , Information and C o n t r o l , Volume 13, pp230-244. 58 Feigenbaum, Edward (1963), "The S i m u l a t i o n of Verbal Learning Behavior", Computers and Thought, Feigenbaum and Feldman (eds.), pp297-309. Freeman, Herbert (1961), "On the Encoding of a r b i t r a r y Geometric C o n f i g u r a t i o n s " , T r a n s a c t i o n s of the JBE on E l e c t r o n i c Computers, EC-10, pp260-268. Freeman, Herbert (1971), "Techniques f o r the D i g i t a l Computer a n a l y s i s of Chain-Encoded A r b i t r a r y Plane Curves", Proceedings of the N a t i o n a l i l e c t r o n i . e s Conference, Volume 17, pp421-432. Hershey, T. (1963), "A P l o t t i n g c f Maps on a CBT P r i n t e r " , NWL Report, #1844. J a r v i s , C.L. (1971), "A Method For F i t t i n g Polygons to Figure Boundary Data", The A u s t r a l i a n Computer J o u r n a l , Volume 3, #2, pp50-54. Keates, John S. (1972), "Symbols and Meaning i n Topographic Maps", I n t e r n a t i o n a l Yearbook f o r Cartography, pp168-180. Koeman, C. S van der Weiden, F. 1. (1970) , "The A p p l i c a t i o n of Computation and Drawing Instruments to S t r u c t u r a l G e n e r a l i z a t i o n " , C a r t o g r a p h i c Jjournal, Volume 7, pp47-49. 59 Koffka K. (1935), P r i n g i g l g s of G e s t a l t Psycholojgj, Harccurt Brace, New York. K o l e r s , P.A. & Eden, M. (eds.) (1968), Recognizing P a t t e r n s -S t u d i e s i n l i v i n g and Automatic S_ysterns, HIT P r e s s . Lang, T. (1969), "Rules f o r Robot Draughtsmen", Geographical Magazine, Volume XLII, #1, pp55-51. i L i c k l i d e r , J.C.R. (196 0) , from P e r s p e c t i v e s on the Computer R e v o l u t i o n , Zenon W. Pylyshyn (ed.), P r e n t i c e -H a l l (1970). M i l l e r , W.F. S Shaw A.C. (1968); " L i n g u i s t i c Methods i n P i c t u r e P r o c e s s i n g - A Survey", Proceedings of the FJCC, Volume 33 p a r t 1, pp279-290. M i l l e r , O.M. & V o s k u i l , R.J. (1964), "Thematic-Map G e n e r a l i z a t i o n " , G e o g r a p h i c a l Review, pp13-19. Montanari, Ugo (1968), "A Method f o r Obtaining Skeletons Using a Q u a s i - E u c l i d e a n Distance", J o u r n a l of the A s s o c i a t i o n f o r Computing Machinery, Volume 11, m, pp600-624. 60 Montanari, Ogo (1970), "A Note on Minimal l e n g t h Polygonal Approximation to a D i g i t a l Contour", Communications of the A s s o c i a t i o n f o r Computing Machinery, Volume 13, #1, pp41-47. Newman, W i l l i a m M. (1971), " D i s p l a y Procedures", Communications of the A s s o c i a t i o n f o r Computing Machinery, Volume 14, #10, pp651-660. N i l s s o n , N. (1965) , L e a r n i n g Machines^ Foundations of T r a i n a b l e P a t t e r n C l a s s i f y i n g Systems, McGraw H i l l . P f a l t z , John (1970), "Web Grammars and P i c t u r e D e s c r i p t i o n " , T e c h n i c a l Report 70^_138, Computer Science Center, U n i v e r s i t y of Maryland. A P f a l t z , J . S Rosenfeld, A. (1967), "Computer Repre s e n t a t i o n of Planar Regions by T h e i r S k e letons", Communications of the A s s o c i a t i o n f o r Computing i!f^lLiil§IIi Volume 11, #2, pp119-123. Robinson, A.H. S S a l e , R.D. (1969), figments of Cartography J 3 r d edition}., John Wiley S Sons. Ryan, T.A. S Schwartz, C.B. (1956), "Speed cf P e r c e p t i o n as a 1 F u n c t i o n of Mode of Re p r e s e n t a t i o n " , American J o u r n a l of Psychology, Volume 69, pp60-69. 61 Seeley, D.A.R. (1970), "The Use of F i n i t e - S t a t e Models f o r P a t t e r n D e t e c t i o n with A p p l i c a t i o n to E l e c t r o e n c e p h a l o g r a p h ^ Data", PhE. T h e s i s , Department of I n d u s t r i a l E n g i n e e r i n g , U n i v e r s i t y of Toronto. Sherman, R, S E r n s t , G.W. (1969), "Learning Patterns i n Terms of Other P a t t e r n s " , P a t t e r n R e c o g n i t i o n , Volume 1, pp301-313, Pergamon Press. Skiansky, J . , Chazen, R.L. 8 Hansen, B.J. (1972), "Minimum Length Polygons of D i g i t i z e d S i l h o u e t t e s " , IEEE T r a n s a c t i o n s on Computers, C-21, #3, pp260-268. S l a g l e J.R. S Lee, R.C.T. (1971), " A p p l i c a t i o n of Game Tree Searching to S e q u e n t i a l P a t t e r n R e c o g n i t i o n " , Communications of the A s s o c i a t i o n f o r Computing Machinery, Volume 34, #2, pp163-170. Srnka, E r h a r t (1970), "The A n a l y t i c S o l u t i o n of Regular G e n e r a l i z a t i o n i n Cartography", I n t e r n a t i o n a l Yeartook f o r Cartography, pp48-62. Sukhov, V.I. (1970), " A p p l i c a t i o n of Information Theory i n G e n e r a l i z a t i o n of Map Contents", I n t e r n a t i o n a l Yearbook f o r Cartography, pp41-47. 62 To p f e r , F. S P i l l e w i z e r , W. ,(1966), "The P r i n c i p l e s of S e l e c t i o n " , The C a r t o g r a p h i c J o u r n a l , #3, pp10-16. Uhr, L. & V o s s l e r , C. (1963), "A P a t t e r n R e c o g n i t i o n Program th a t Generates, E v a l u a t e s , and Adjusts i t s own Operators", Computers and Thought, Feigenbaum and Eeldman (eds.), pp251-268. Weiner, Norbert (1960); "Some Moral and T e c h n i c a l Consequences of Automation", S c i e n c e , Volume 131, pp1355-1358. Zahn, C.T. (1969), "A Formal D e s c r i p t i o n f o r 2-Dimensicnal P a t t e r n s " , Proceedings of the I n t e r n a t i o n a l Conference on A r t i f i c i a l I n t e l l i g e n c e , Washington 1969. Zahn, C.T. 8 Roskies, R.Z. (1972), " F o u r i e r D e s c r i p t o r s f o r Plane Closed Curves", IEEE T r a n s a c t i o n s on Compujters, C-21, #3, pp269-281. 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0052003/manifest

Comment

Related Items