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.

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

3  C.0T5CJ  THE  APPLICATION OF TO  INTERACTIVE GRAPHICS THE  REDUCTION OF  MAP  AND  PATTERN  RECOGNITION  OUTLINES  by  Andrew B.Sc., U n i v e r s i t y  A thesis the  Clement  of B r i t i s h  submitted i n p a r t i a l  Columbia,  fulfillment  r e q u i r e m e n t s f o r the degree Master in  1968  of  of  of Science  t h e Department  of  Computer S c i e n c e  We  accept this  t h e s i s as conforming to the  required  The  University  standard  of B r i t i s h  March  1973  Columbia  In p r e s e n t i n g  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 r e q u i r e m e n t s f o r  an advanced degree a t the U n i v e r s i t y of B r i t i s h Columbia, I agree t h a t 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 r e f e r e n c e and  I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e f o r s c h o l a r l y purposes may by h i s r e p r e s e n t a t i v e s .  copying of t h i s  be g r a n t e d by the Head of my  thesis  Department or  I t i s u n d e r s t o o d t h a t c o p y i n g 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  g a i n s h a l l not be a l l o w e d w i t h o u t  written permission.  Department o f The U n i v e r s i t y o f B r i t i s h Columbia Vancouver 8, Canada  Date  study.  my  Abstract Techniques recognition Since  from  are applied  the r e s u l t i n g  interactive to t h e problem  g e n e r a l i 2 e d  interactive  graphics  systems  considerably  less  that  useful line  to  and  have  an  than  graphics  several  their  data  of the o r i g i n a l  content lines.  of g e n e r a l i z a t i o n  introduced  to  such  hierarchically  Experiments  are conducted  that  suggest  in  taste  purpose  and  individual reduce these  different  user's  several lines  enough  learning  been on  ability  approach.  is  designed  by hand. The  learns  t o mimic  learned  i t s own.  experinents are this  so  system  and  system  is  scheme  is  reduced . l i n e s .  t o show  to  lcok  at  system  is  to  the  having the user  behaviour.  given  are performed  new  Once  lines  t o measure  performance.  the p o t e n t i a l of  adapt  analyzes patterns i n  user's  generalizaticn  i s a review  i t  f c r t h e same  people  i s dene by  the  Experiments  performed There  the  the  be  accomodate t h e s e d i f f e r e n c e s i n  preferences. This  outlines  and  has  generalize  the  ways. To  that  should Also  c o o r d i n a t e encoding  outlines  outlines.  a r e i n t e n d e d f o r use i n  e x t e n s i o n o f t h e X-Y represent  pattern  o f r e d u c i n g map  outlines  levels  and  the Other  feasibility  work dene i n r e l a t e d  to  of  fields.  ii  Table  of  Contents  Introduction  Chapter  Chapter  Chapter  I  1  Related  Work  1.0  Introduction  1.1  Cartographic  1.2  Psychology  1.3  Pattern  1.1  Line  Encoding  1.5  Line  Reduction  1.6  I n t e r a c t i v e Graphics  II  .3 Generalization  3  of P e r c e p t i o n  Recognition  Methods and  and  7 Learning  Schemes  8 12 14 16  Techniques  2.0  Introduction  21  2.1  Line  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  2.3  Learning  27  2.4  Automatic G e n e r a l i z a t i o n  33  Representation  I I I Experimental  of L e v e l s  25  Results  3.0  Introduction  3.1  Perceptual  3.2  L o c a l Reduction  40  3.3  The  43  3.4  Other Questions  Response  34 to G e n e r a l i z a t i o n  System's G e n e r a l i z a t i o n Performance  34  49  iii  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  List  of  Tables  Table  3.1  R e s u l t s f o r Experiment  I  T a 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  III  41  Table  3.4  Learning  Statistics  45  T a b l e 3.5  Learning  Results  45  Table  Generalization  3.6  Results  page  35  45  V  List  of  Chapter  Chapter  Figures  I Figure  1.1  following  page  5  Figure  1.2  5  Figure  1.3  5  Figure  1.4  8  Figure  1.5  8  Figure  1.6  10  Figure  1.7  12  Figure  1.8  12  Figure  1.9  12  Figure  1.10  12  Figure  1.11  13  Figure  1.12  13  Figure  2.1  21  Figure  2.2  21  Figure  2.3  21  Figure  2.4  22  Figure  2w5  22  Figure  2.6  22  Figure  2.7  22  Figure  2.8  22  Figure  2.9  26  Figure  2.10  26  II  vi  Chapter  Figure  2.11  28  Figure  2.12  28  Figure  2.13  30  Figure  2.14  30  Figure  3.1  35  Figure  3.2  35  Figure  3.3  35  Figure  3.4  35 .  Figure  3.5  37  Figure  3.6  37  Figure  3.7  40  Figure  3.8  42  Figure  3.9  42  Figure  3.10  42  Figure  3.11  42  Figure  3.12  42  Figure  3.13  42  Figure  3.14  42  F i g u r e 3.15  43  Figure  3.16  43  Figure  3.17  43  Figure  3.18  44  Figure  3.19  44  Figure  3.20  44  III  vii  Chapter  Figure  3.21  44  Figure  3.22  44  Figure  3.23  45  Figure  3.24  46  Figure  3.25  Figure  3.26  46  Figure  3.27  46  Figure  3.28  46  Figure  3.29  47  Figure  3.30  47  F i g u r e 3.31  48  Figure  3.32  48  Figure  3.33  48  Figure  3.34  48  Figure  3.35  48  Figure  3.36  48  Figure  3.37  48  F i g u r e 3.38  48  Figure  3.39  48  Figure  3.40  48  Figure  4.1  50  Figure  4.2  50  Figure  4.3  50  Figure  4.4  51  '  46  IV  viii  Many  people  have  helped  preparation of this thesis. thanks.  I am  me  in my  To a l l these  work  and in the  people  I give my  especially indebted to Frieder Hake, my advisor,  whose patience and insight made i t 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 Hisson  for her typing  of Chapter  3. There are many others,  people who cheerfully submitted to be subjects experiments,  in the various  the people who wrote the software that I depended  on heavily, and the taxpayers institutions,  to Inger  of Canada  who  through  their  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  display,  manipulation,  information  the accuracy the  and  graphic f a c i l i t i e s  interrogation  o f map o u t l i n e  and d e t a i l  case  cf outlines  of i n t e r a c t i v e  on  levels  of  were  g r a p h i c s the primary  resolution,  visual  identification.  minimizing  the  storage  requirements  shading  the  memory c a p a c i t i e s  processing  and i n t e r s e c t i n g  times  enough  The  stems  of CRT  1  regions often  display  radically  the s c a l e  correspondingly  of the display  change t h e l e v e l  also  of d e t a i l .  level  of  observe  more d e t a i l  While  interactive  provided  a potentially  outlines  t o a more compact  1  representing  map  powerful  between  CRT = C a t h o d e Ray Tube  form.  screen to  became  outlines tool  as  sizes change time  This i s to enable a and r e l a t i v e l y  i n on an a r e a  low  c f i n t e r e s t and  larger.  g r a p h i c s has c r e a t e d  of  be e s t a b l i s h e d  1  as t h e s c a l e  methods  can  "zoom'  In  of the  o f a map and a t t h e same  t o view a l a r g e r e g i o n a t s m a l l s c a l e and t h e n  with  the u s u a l l y  necessary  person  detail  detail i s  vary as the square  is  i t  scale  o p e r a t i o n s such  available  present  of  devices.  Due t o t h e l i m i t e d  the  often  concern from  for typical  naps  important,  concerns  number o f p o i n t s a l o n g o u t l i n e s . at  and compact  o v e r a range  while  for  addition  geographic  considered  maintained^  severely limited  f o r the  d a t a , whereas i n t r a d i t i o n a l  are the r e d u c t i o n of storage requirements dependent  of  has c r e a t e d a demand f o r a more f l e x i b l e  representation  in  use of i n t e r a c t i v e  a  denand  for  i t has a t t h e same  new time  t o a i d i n the c c n v e r s i o n of  T h i s a r i s e s from  t h e c o m p u t e r ' s speed  the l i n k  that  and a c c u r a c y a t  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 The  way  in  of  outlines.  which this has been done is tc display a series of  outlines on the screen of the CRT and allow the the  map  user  to  train  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  i t 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 i f 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  1.0  I  RELATED WORK  Introduction The  work d e s c r i b e d h e r e draws on  fields.  In  a  sense  contributions  come  psychology, computer Some  i t  properly  from  pattern  fields  of  the  belongs as  recognition  graphics, interactive influences  from  work done  in  systems,  as  these areas  but  perceptual  learning, and  other  i n cartography,  diverse  and  many  linguistics,  numerical  analysis.  are d i s c u s s e d i n  this  chapter.  1.1  Cartographic Reducing  aspect  of  generalization  the  a  process  generalization". reduced  scale  maps. The  aim  information Others  important without a  in  a map  special  i s "the by  selection,  and  and  i s t o be  produced by  from  large  extraneous  detail.  number o f p o s s i b l e  islands,  and  while others are coastlines)  so on omitted  must  be  must be or  map  from  less  (Keates (1972)).  that  s i m p l y and  example, o u t  selected  combined.  for  the  of  towns,  inclusion  Lines  while  and  clearly  choices certain  simplified  other  selection,  For  of  detailed  T h i s i s done so  a r e conveyed  one  "automatic  whenever a  simplification"  Sale(1969))  relationships  interference  boundaries,  purpose  i s just  t c as  i t i n terms of " s i m p l i f i c a t i o n ,  spatial  roads,  cartographers refer  e x p r e s s i o n of d e t a i l e d  (Robinson  potentially  rivers,  that  o f an o u t l i n e  G e n e r a l i z a t i o n i s necessary or  think of  emphasis."  information content  (e.g.,  maintaining  4  their  character  rough).  This  (e.g.,  a rocky  i s i n general  a very  much knowledge and  skill  of  purpose  of  map,  and  aesthetics,  scale graphic  cartographer therefore include  difficult  major  been t h e  that This of  the  density  selection be  and and  map  for  purpose,  continue  to  Much centred  the  of  around  can  be  points  the  to  all  the  any  along  points  by  items  in  the  a and  must  generalization an  only  any  expression  scale  judging an  of  the  the  of  Work  results  estimate of  by  circles  these  and  are  experienced  line  data.  i n t o two  have  employed  lines in  in  this  The  The  to  factors  knowledge  will  cartographers.  generalization  classes  , treated.  filtering"  of  Sukhov (1970),  However t h e  automation of  of  the  approaches promises  special regional of  map.  direct indications  generalization.  divided  defining  by  subjective  t h e o r e t i c p r i n c i p l e s to a i d  processing  "point  to  Soviet  influence  line  region,  considered  derived  for  without  work i n t h e  a  eventual  a u t o m a t i c scheme  has  selected.  automating  roughly  be  automation of  t h i s gives  be  aesthetics,  the  map  A combination  the  The  i s thus h i g h l y  criterion  others  demand t h e  characterized that  of  information  process.  fruitful  area  to  selected  p a r t i c u l a r items  statistical  It  However be  demanding  factors.  provides a quantitative  items to  process  remain  s p e c i a l knowledge c f t h e  work o f T o p f e r (1966). He  Srnka(1970),  of  for these  usually  cartographer.  to automate s i n c e  generalization.  the  the  work.  contribution  relates  number o f  complicated  l i m i t a t i o n s must  this  provision  A has  in  the  c o a s t l i n e should  work  in  depending first  has this  on  how  class  is  schemes. What t h i s means i s  the  new  map  are  simply  a  5  subset added  of the  points  or moved. H e r s h e y  closer  than  some  size.  This  near  each o t h e r  deviate vein  too  is  the  line  into trouble was  straight  work  by  on  Douglas  line  the  process  formed  by  greater  illustrates  this  of the  The  of  class.  Points  in  lines  the In  than  and  the  work  the  in  this  s e l e c t e d based  second  to  line,  averaging  then  selected  based  moved a c c o r d i n g  exaggerate or  of  then  in  dot very Lang  do a  not  similar  starts the  this  that  by  line.  straight point  each o f  is  the  two  nowhere i s  the  amount.  Figure  1.1  which  points  are  points  depends on a l l  t h e s i s a l s o belongs-  on  the  r e c o g n i t i o n of  to the  thus  process  to  of  cn  the  the  degree of  s i m p l i f y the  ever  simplifying  Brophy (1972) c o m b i n e s a p p r o a c h e s first  In  process  system  by  g r o u p i s work by Koeman and  an  the  they  points  specified  s e l e c t i o n of  were  line.  described are  end  order  they  became  i f  r e c u r s i v e l y cn  i n d i c a t e s the  (1970) . They use alter  a  been  s c a l e change.  (1972). The  tolerance  t h a t have been t a u g h t  the  lines  newly s e l e c t e d p o i n t u n t i l  Thus, i n a way,  rest  when  the  have  d i s p l a y device's  t h a t i s f u r t h e s t from  i s repeated  the  deviation  selected.  the  if  approximations.  joining  line  points  points  a drastic  line  i s f a r t h e r than a s p e c i f i e d  sections  on  No  a scheme t h a t removes p o i n t s  a straight  s e l e c t e d . The  map.  removed  when t h e r e  much f r o m  point  (1963)  ran  and  recent  considering  the o r i g i n a l  amount d e p e n d i n g  technique  (1969) d e s c r i b e s  If  from  line.  both  desired  user.  der  a sequence of i t .  Recent  groups.  s c a l e and  generalization  C e r t a i n f e a t u r e s are  Weiden points  work  Points  line  this  patterns  the  van  to  width tc  by are and  either  eliminated  1  Outline with points  removed  Figure  1.3  6  if  adjacent  lines  begin  t o merge.  This  work  in  cartography,  reducing  the information  applicability. are q u i t e The  The reason  different  They  carefully.  will  on  the  order  for this  be hung on is  walls,  of  the  stared  important  to the best  and  width).  perceive  and  the  hand, t h e maps t h a t we a r e  distinguish  Our  live  only  relationship be  so  before  the  being since  maps. T h i s  important  the  can  be  device. terminal  storage  Transmitting is  often  guickly  with  in  time-consuming that  are  quite  and formed  to  by the  convey  of lines  n o t be made far  will  be  apart  transmission  reduced t i m e , and  information  by t h e memory s i z e  performed  t h e number o f p o i n t s  some  the o b j e c t s a r e c l e a r l y  and e x p e n s i v e .  c a n be  maps  Accuracy w i l l not  probably  t h e amount o f  restricted  to  i n k cn p a p e r . On  l a r g e amounts o f i n f o r m a t i o n  t i m e s f o r many o p e r a t i o n s very  that  requirements,  i s often  ability  p o i n t s c a n be f a i r l y  content  At CRT d e v i c e s  displayed  eye's  minutes  measurements w i l l  being  spacing  o f a CRT. K o s t o f t h e s e  by a n o t h e r .  criterion  measured  (i.e.,  interested  replaced  to  time.  the  or  The i n f o r m a t i o n  processing  by  seconds  means t h a t  and  The d e g r e e o f i n f o r m a t i o n  be d y n a m i c , " s o f t " ,  identifiable. diminish  only  of the screen  f o r a few  important  from these -  dots  result  the p o i n t s a r e u s u a l l y  images from c o l o u r e d  maps w i l l  glow o f p h o s p h o r will  i s governed  limited  a r e " h a r d " and  at,  resolution possible  line  of  o f maps we a r e i n t e r e s t e d i n .  required  different.  i s only  towards  i s t h a t t h e maps t h a t  reduction  other  directed  maps a r e made o f p a p e r , t h e y  accuracy  spaced a c c o r d i n g  of a l i n e ,  from t h e s o r t  cartographer's  static.  content  although  involved  to  a  that of the  display  The  processing  on  maps  (e.g.,  grow  finding  7  the  i n t e r s e c t i o n o f two  regions  can  be  proportional  to  the  s q u a r e o f the number o f p o i n t s ) . These c o n s i d e r a t i o n s (Miller  and  Voskuil(1964))  t h o u g h we a r e f o r c e d things  are  not  been l o o s e n e d  Of  We r e c e i v e  Attneave  readily  of  that  This  information  the are  only  Gestalt of  that  than  map  i s quite  recognizable.  Psychology  cf  comes  caricatures,  situation  points  of accuracy  have  there  we  shall  be  from  information the  regions  Byan and  for  of  the  o f maximum  S h w a r t z (1956)  the  this  and r e d u n d a n t f o r the  o u t l i n e s as w e l l .  I f i t i s true  then i t  to recognize  select  and  large  i n order  Some  contrary  will  more  corresponding  i s t o o much d e t a i l  Hopefully  by  be t r u e  on t h e f i g u r e  indications that  the  where  taken  more  as  come  a  from  whole. than  important  by e x p e r i m e n t .  that  the r e c o g n i t i o n  i s a global rather  is  have t o be d e c i d e d  points  to produce o u t l i n e s  i t i s maintained  Which o f t h e s e v i e w s will  that  though d i s t o r t e d , a r e o f t e n  words, f i g u r e r e c o g n i t i o n  process.  the  photographs  since  a f i g u r e i s dependent  other  cf  Even  psychology. Studies  i n d i c a t i o n s come from  i s because  of  indication  most  figure  be n e c e s s a r y  curvature easily  cf points.  t h e number  the c o n s t r a i n t s  of perceptual  i n the o r i g i n a l .  identification should  a  recognized  subjects.  bad s i n c e  the f i e l d  Belated  report  t o reduce d r a s t i c a l l y  some a d d i t i o n a l  (1954) show  curvature.  i n the e l i m i n a t i o n  and i n t r e p i d "  Perception  from  recognition  who  so  us t o be " b o l d  somewhat.  1.2 Ps_ycholocjy_  successful  encourage  a in  In  local our  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  i t 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 ,..., f").  Pattern  2  Recognition consists of assigning these patterns tc classes, c , out of a set of m classes c = {c , c,...,c***} . A standard way of 1  looking  2  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 pattern  vector  n=2  and  m=4.  The  f lies in a region labelled "A". The difficulty  arises in defining the boundaries cf these regions. Since boundaries  we  can rarely  is usually  boundaries  and  externally classified patterns. device  a priori  what  the  region  are a pattern recognizing machine must be trained to  determine them. This approximate  know  done  then This  by  specifying  adjusting is done  them by  initial  based  on  giving the  a series of patterns to classify. These patterns should  8a  Two  Feature  Pattern  Classification  Figure  1.4  Root node V e r d i c t nodes feature 1 level  1  feature 2  level 2  feature 3 level 3  D e c i s i o n Tree f o r P a t t e r n  Classification  Figure  1.5  9  be fairly representative pattern  of a l l the pattern  classes.  If a  is classified correctly then boundaries are often left  unchanged. However, i f the classification boundary  is incorrect the  of the appropriate region is moved closer to the point  so as to either give the correct  classification  or else  come  "nearer" to i t . 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  piece-wise fashion linear  of specifying  using  polynomials  region boundaries is in a  hyperplanes.  are needed  This  means  to evaluate  that  pattern  only 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 i t demands that a l l n features be measured in order tc arrive at a  verdict  for a pattern. In our case, in order to consistently  guarantee that  enough  considered,  would  n  of the line have  to be  surrounding  point i s  guite large, say 10 or more  (using angles and lengths of straight line it  a  segments). However,  is often possible to make the right decision by considering  only a single feature. This occurs when the line straight  at the point.  associated with  measuring  Since a  there  feature  is a and  is virtually  certain expense  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 Pattern  Recognition  (SPR)  (Slagle  and  features are considered one at a time feature  is  measured  a  test  as  in  Sequential  Lee (197 1)). needed.  With SPR  When  then  we  move on to the next pattern. If not then a decision is made  as to whether further features would be likely to reliability  of  each  increase  the  the verdict and i f so , which one. Only if this  is affirmative is another feature selected. for  new  is made to determine whether the  pattern classification can be made reliably. If i t can can  a  feature  considered  this  way  although  is  more  the  work  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 whether  a  decision  made is  verdict can be made. If i t can, i t i s , otherwise the  next feature is considered. The order in which the features taken  is  fixed  ahead  of  time.  This  decision  process  conveniently represented as a tree (see Fig. 1.5). The the  initial  root  are is is  node and the features as they are measured in turn  cause transitions down the appropriate node  is  reached.  tree  consists  arcs  until  a  terminal  At the beginning of the learning process the  only  of  the  top  level  (root  plus  terminal  nodes,see Figure 1.6). As patterns are presented, if the verdict agrees  with  the  reinforced. If sprouts  new  classification  there  terminal  is  given  disagreement  then then  that the  verdict is tree  either  nodes from the previous terminal node or  else the verdict is weakened or changed depending on  the  depth  Root Node  Terminal (Verdict) Nodes  D e c i s i o n Tree B e f o r e L e a r n i n g  Figure  1.6  11  and  past  history  classification  of  scheme  that  is  verdict.  very  similar  This to  learning  that  cf  (Feigenbaum (1963)) and t h e work o f Sherman and E r n s t Which Pattern  features Recognition.  distinguishing subseguent graphic  Ohr  to  and  converting  we  Since messy could  information  pattern  we  there  the data  themselves,  features  of  dealing  with  t h i s appears  essence  of  a  i's " n a t u r a l l y "  ill-defined,  but  between  The  this  crudely  to  do  individual  the best  way  classification  a t as r e c o g n i z i n g  the  the  d r a w i n g s by  language over a f i n i t e  are M i l l e r  P f a l t z (1970) , and S e e l e y (1970).  exploit  line  to o f f e r  i n t h e f u t u r e . Some p e o p l e fields  of regions  I have c h o s e n  line.  occuring  initial  machines(1963)).  our  and t h e a n g l e s  to a particular  approach i n other  all  (as i n t h e c a s e  we c a n c o n v e n i e n t l y  nature  the lengths  the  be f r u i t f u l  otherwise  might be an  recognition  p r o b l e m c a n now be l o c k e d  belong  are  essential  are i n t e r e s t e d i n the boundaries  the line since  capturing  and  Since  problem i n  the  the o r i g i n a l ,  them i n t o s t r i n g s o f c h a r a c t e r s .  segments a l o n g  recognition  contain  of  futile.  one-dimensional  t h i s by q u a n t i z i n g  strings  be  Vossler's  since  essentially  must  EP AM  (1969).  i s often a serious  measure t w o - d i m e n s i o n a l  not t h e r e g i o n s  of  They  or two-dimensional  However, and  measure  characteristics  work w i l l  temptation of  to  and  alphabet.  language  is  linguistic who have  and Shaw ( 1 9 6 8 ) ,  whether  very  approach  tried  this  Feder(1968),  12  1.4  line  Encoding  Whenever computer encoding the  one  one  schemes  by  vectors)  a  of f i x e d  the  curve  1  1  10 15 25. 33 40  22 35 45 55 65  •  m  m  way  to  1.10.  Figure  fi  straight  1.7  three  scheme i s known a s  method.  to a fixed  lines  T h i s i s done and f i n d i n g  the g r i d ,  segments  curve  line  is  segments  of these  segments  c o o r d i n a t e system. would  be  encoded  i s with  t h e use c f Freeman  by o v e r l a y i n g a r e c t a n g u l a r the i n t e r s e c t i o n  (see F i g . 1.8) The g r i d  p o i n t s are determined whose l e n g t h i s e i t h e r  points  points  and c o n n e c t e d  nearest  in  1 o r s g r t (2)  of  order  times  the  ( s e e F i g . 1.9). T h e s e s h o r t segments a r e encoded  with  0 through  Fig  Thus  the  ...00101320...  a  relative  encode  mesh s i z e  intersection  digits  of contiguous  the  m  •  with  size  in  as:  grid  mesh  traditional  coordinate  shown i n  (Freeman ( 1 9 6 1 ) ) .  line  data  making a c h o i c e o f which o f  o r X-Y  i s recorded  another  with  line  c o o r d i n a t e s of the endpoints  •  these  representing  with  series  example, t h e curve  chains  to  t o use. The most  the absolute  numerically  the  faced  vector approximation  (or For  comes  is  approximated and  Schemes  third  7 according  final  encoding  to the  diagram  of the o r i g i n a l  shown  in  curve  would  be  .  encoding  scheme t h a t i s m a i n l y  suitable  for  closed  12a  Chain-encoding ( g r i d  overlay)  Figure 1.8  12b  o r  /  £ J *  } )  <.  >  0  '  0  A  Chain-encoding  Chain-encoding  (basic  increments)  7  Figure  1.9  Figure  1.10  13  curves  is  referred  one  first  to as  proposed  skeleton  by  encoding,  Elum is  (1964).  based  T h i s method,  on  finding  maximal n e i g h b o u r h o o d s o f p l a n a r r e g i o n s . In a p a r t i c u l a r the  neighbourhood  of  some d i s t a n c e from Fig. of in  1.11  (from  a  that  p o i n t . With  P f a l t z and  every  neighbourhood  are  by  not  stick-like give  an  1.12).  within  completely  The  Generally  and  these  disadvantages,  and  areas,  also,  theoretical  on  of  such  (see  while  as  finding  intermediate.  of  regions. It  enjoys  The  lends  own  Vector an  neighbourhoods some  other form  outline  radii  (Figure  (1968)).  advantages  suited  to f i n d i n g  itself (1961)  perimeter  to and  and used.  1  of  approximation advantage  lengths  considerable Feder  (1968)).  a s s o c i a t e d with  o p e r a t i o n s such  in  the  the r e g i o n , i s as  shading  is  and  generally  economy  of  ™  s e e D e e k e r ( 1 9 7 0 ) f o r a much more c o m p l e t e t h r e e e n c o d i n g schemes. 1  a  maximal  i n which i t i s  f o r processes the  has  most compact r e p r e s e n t a t i o n  i s well  when i t comes t o " a r e a l "  intersection  region.  Mcntanari  its  Freeman  poor  region  the o r i g i n a l  (1967),  in  region  the c o r r e s p o n d i n g  the s i t u a t i o n  chain encoding  analysis  the  within  with  has  and  a closed  maximal n e i g h b o u r h o o d s  g i v e s the  outlines  Skeleton-encoding,  .__  methods  chain-encoding  very d e t a i l e d  superior  these  Rosenfeld  depending  for  boundary,  the  metric  2-neighbourhood  t h e s e t o f such  description  (see P f a l t z  of  enclosed  centres of  adeguate  of  (1967)) t h e  t h e rhombus. F o r  s k e l e t o n s which t o g e t h e r  Each  "city-block"  p o i n t i n the i n t e r i o r  completely  neighbourhood.  the  Rosenfeld  neighbourhoods o f the r e g i o n are that  metric  p o i n t i s the s e t of a l l p o i n t s w i t h i n  the point P i s indicated the plane  the  comparison  of  these  The 2-neighbourhood o f p o i n t P  S k e l e t o n o f an O u t l i n e  Figure  Figure  1.11  1.12  14  representation easy for  when t h e o u t l i n e  rotation.  It  reasons that  i s better  will  is  fairly  suited  simple  and  permits  t o our p a r t i c u l a r  purposes  be d i s c u s s e d i n t h e next c h a p t e r .  1.5 L i n e R e d u c t i o n  The  problem  o f r e d u c i n g and s i m p l i f y i n g  line  data  i s met i n  many a r e a s o t h e r t h a n c a r t o g r a p h y . Some o f t h e major s o u r c e s this  data  a r e photomicrographs  biomedical physics,  field,  and a e r i a l  as t h e s e produce reduced has  bubble  in  photos  in  boundary  some  shape.  These  description specified data  of the c e l l  precisely.  More  are  a least Zahn  with  added  one  he took  the  was t o  a  to the  of  this  of the o r i g i n a l to  error  the  polygon  falls  below a  attempted  re-codes  to  reduce  line  t h e d e s c r i p t i o n by  No i n f o r m a t i o n i s l o s t i n can  be  reconstructed  (Zahn and R o s k i e s ( 1 9 7 2 ) )  line  a  b o u n d a r i e s b u t by n o t n e a r l y  i n the c h a i n . original  (1971)  pick  the d i s t a n c e  one  squares d e v i a t i o n (1969) has a l s o  recently  of  by  be  to the chain-encoded  the v e r t i c e s  D e s c r i p t o r s t o encode l i n e s . expansion  must  o f a n g l e . The p e a k s and t r o u g h s  regularities and  energy  applications  data that  and p l o t  an amount. He e s s e n t i a l l y  process  Fourier  polygons  content of chain-encoded  recognizing  Fourier  vertices until  of l i n e  The a p p r o a c h  associated  threshold.  as d r a s t i c  the  be  high  i n remote s e n s i n g . Such  low-order  cells.  the i n t e r i o r  can  in  i n the  way b e f o r e t h e y a r e manageable. J a r v i s  as a f u n c t i o n  function  photographs  enormous q u a n t i t i e s  b o u n d a r i e s o f muscle  the  chamber  done work on f i t t i n g  point  o f chromosomes and c e l l s  of  are  The  he h a s used  coefficients  sufficient  to  a d e q u a t e l y . S i n c e most o f t h e i n f o r m a t i o n i s u s u a l l y  i n the  specify i t stored  in  15  the  lower terms  t h e r e m a i n d e r can  the data content o f the l i n e . to  obtain  the  minimum  e n c o d i n g o f shape. perimeter shape.  An MPP  that produces  theoretical  All  boundary  vein  these  resulting  suitable  of the f i r s t  of  original  minimal  line.  c o m p a r i s i o n and  It  may  from  well  mathematical  in  some  the  turn  visually,  out  but  thinks  and  he  m a n u a l l y . The  thus the c r i t e r i a  to the i n d i v i d u a l ' s  needs  system  fact  until a  more  that  one the is  could  preferences.  the  mathematical  the net  lines  more  necessarily  view  of  visual  t h e r e i s seme  produces  are e s t a b l i s h e d  and  of  that  that  define  what  makes  point  allow  empirically  the  a n a l y s i s but does  t h e r e f o r e seems r e a s o n a b l e t o  user  In  was  around  positions  strict  This  criterion  reduction  lines  h i s approach  length.  common  satisfy  recognition.  reducing  and  t h e n move t h e v e r t i c e s  of t h e i r  have  must  reductions  appropriate  chain-  original  one  i s the p o l y g o n  the  t h e same c h a i n - e n c o d i n g as t h e  was  attempts  give the best  defined  from  minimum  to t h e o r i g i n a l  for  (MPP)  attempts  i s t h e work o f S k l a n s k y e t a l { 1 9 7 2 ) .  line  relationship  several  of  w i t h a c h a i n - e n c o d i n g and  resulting  i n order to reduce  have been  o f a shape  w i t h i n s m a l l neighbourhoods the  There  perimeter polygon  M o n t a n a r i (1970) was  to s t a r t  be d r o p p e d  well-  the  most  i s n o t known y e t . I t prospective most learn  user  to  appropriate  by  to  internally  mimic  the  according  16  1.6 I n t e r a c t i v e This tastes  Graphics  tailoring  is  one  o f t h e system  of  t h e main  c o m p u t i n g . An i n t e r a c t i v e immediate role  system  t o a computer  be d i s p l a y e d t o t h e  user  process  i s that  and  done  to  nature.  directly  A person  monitor  powerful  the put  people  performing  back  w h i l e poor  information that  from  terminal  user  to  enter  systems  were  repetitive at t h i s  faster  t o i t and and  more  programs i n b a t c h e s  i t again  together  simultaneously.  simple  has  f r c m a program  competing  and p r o c e s s . More  machine i t would be p o s s i b l e  People,  the  recently,  with with  became p o s s i b l e t o  again.  many g r e a t t h i n g s . I t was t h o u g h t  t h e two p a r t i e s  having  became  t o submit  of t i m e - s h a r i n g systems, and p r o c e s s  person  and make c h a n g e s  computers  s e p a r a t i o n of user  advent  promised and  As  i t became n e c e s s a r y  consequent  a  had t h e machine t o h i m s e l f and was a b l e  i t s performance  t h e program as d e s i r e d .  by i n t e r a c t i v e  output  permits  user's  and p l a y s a d i r e c t  by  allow  i n f o r m a t i o n f o r t h e program. The e a r l i e s t of t h i s  particular  i s one i n which  t o the computation  attached  a  attractions offered  i n guiding i t s course. This  devices to  access  to s u i t  This  that  development  by c o u p l i n g man  to exploit  the d i v e r s e s k i l l of  Computers  are  operations guickly  well-suited  and a c c u r a t e l y .  a r e good a t r e c o g n i z i n g  diverse sources  to  and i d e n t i f y i n g  patterns gcals:  in  things  c o m p u t e r s a r e n o t good a t .  While their  vastly  offering Norbert  many s e e t h i s  a much  different improved  linking skills method  Wiener d i d n o t s h a r e  this  of  people  and of  and  speeds tackling  optimism.  of  computer  with  operation many  as  problems,  He wrote i n 1963:  17  Disastrous r e s u l t s a r e t o be e x p e c t e d not m e r e l y i n the world of f a i r y tales but in the real 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 o t h e r a r e c o u p l e d i n the a t t e m p t t o a c h i e v e a common purpose. I f the communication between these two agencies as tc the nature of this purpose is incomplete, i t must only be expected that the results o f 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 chief causes of the danger of disastrous consequences i n t h e use o f t h e l e a r n i n g machine i s t h a t man and machine operate on two distinct time scales, so t h a t t h e machine i s much f a s t e r t h a n 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  this  available  was  his  written comments  considered  seriously.  especially  important  Symbiosis  such  as  machine i s t o be On  our  narrowed  and  show t h e  anticipate especially often  'verified  because  widely  should  be  scepticism  is  c f Man-Machine  i t be f o r g o t t e n  that  the  systems  promise  to  the u s e r ' s p o i n t  c f view.  Not  interactive from be  available be  faster  required  results  immediately,  ahead o f t i m e applicable  i s limited  the  precisely  to debugging  than  with  on h i s p a r t  t h e c o n t e x t o f any  c o n s i d e r a b l y . S i n c e a program  u n p r e d i c t a b l e , and  the context  and  o f c a u t i o n and  (1960) l e s t  work would  them. T h i s i s p a r t l y be  relevant  were  tool.  generally  less  systems  when c o n f r o n t i n g p r o p o n e n t s  more e f f i c i e n t  but  still  attitude  Licklider  would r e s u l t s  systems,  is  An  are'  a more c o n c r e t e l e v e l  make c o m p u t i n g only  before i n t e r a c t i v e  can  user  does  what w i l l  be  not  programs and  t c the r e c e n t output  and  could  for input have  to  needed. T h i s i s  p r o g r a m s , where t h e  in editting  to o b t a i n  operation prompt  batch  behaviour  text,  changes  where  can  be  immediately.  Generally,  applications  most  suitable  for  interactive  18  systems can  be  characterized  according  to  the  f o l l o w i n g modes of  operation: •  R e l a t i v e l y few,  immediate  straight-forward  response,  reservation  e.g.,  operations  i n q u i r y systems  systems, customer  record fast  action  result  actions;  depending e.g.,  computer-aided  on  the  editting,  learning  response, of  program  (CAL),  (airline  systems)  • Many s e q u e n t i a l d e c i s i o n s w i t h often  with  each  earlier  debugging,  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  heavily  d e p e n d e n t on  ones; e.g.,  on-line  r e s u l t s of  problem-solving, While  these  different  belong  on  basic  distinctions. here  rejection  of  resulting during  interactive categories  a continuum they  described  It  belongs. points  o u t l i n e and  learning  it  are  the  of  processing  true  for  interactive  intended in  the  and  in  second  influences  on  really  c l a s s t h a t the  manual  an o u t l i n e a f f e c t s  important  fact  t o h i g h l i g h t some o f  sequential  the work  selection the  future  and  shape of  actions.  to  know  how  the  the  order  in  which  the  Also,  system  is  sample  tc i t . which  i s the  more) d i m e n s i o n a l of  distinct  computer  information  one-dimensional  goes n a t u r a l l y with  two  simulations. overlap  a bearing  Graphics,  2-(or  information)  The  is  patterns  display  is  hence  s i n c e t h i s has  Computer  are  along  behaving  presented  previous  string  interactive  reasons.  In  situations a considerable  the  manipulation (as  opposed  and  amount o f  case, data  to  numerical  computing. T h i s  first  and  with  is many  i s produced  19  upon which t h e n e x t a c t i o n by t h e u s e r  is  information  g r a p h i c a l l y because  is  a form  is  i n which  relationships. not  people  This  basically preferred  to  obviously that  are  such  Secondly,  graphic  good  ,  in  interactive  with  methods.  descriptions.  These  This  the  i n the o r i g i n a l  fact  that  pictures,  informationally difficult present  very  must be d i g i t i z e d The  operations entered  are  to  terminal  indicate  the  way,  desired  into  allow  to  enter  necessarily that  sc  the  machine.  problem  cf  the  basic  this  specifying has  teen  information  on a  interactive These  information  devices  devices  "mice",  Because  expensive  information  display  are  information  the  graphic  was  makes i t  around  keys,  on  however,  and  to  i t  numerical  lengthy  function  u s e d t o draw f i g u r e s , s e l e c t  through  a  is  highly  because  machines" such  manipulations.  joy-sticks,  is  and  fact,  and u s e t h e a v a i l a b l e  light-pens, one  This  usually  g r a p h i c a l l y , once hard  often  terms the o p e r a t i o n s  maps  not " g r a p h i c  get  that i s  form. T h i s i s a conseguence of  data  somehow -  way  the  graphic  rich.  and  itself i s  must be s u p p l i e d  diagrams,  t o g e t raw g r a p h i c computers  affair.  graphic  this  statistical  are i n general  and messy s i n c e s o much c o n t e x t  inherent  or  are  This  patterns  information  methods  makes s e n s e t o s p e c i f y i n g r a p h i c  linguistic  based.  seeing  numerical  dealing  non-interactive  be  when t h e i n f o r m a t i o n  as  when  at  a r e t o be p e r f o r m e d . The a l t e r n a t i v e i s  long  on,  represented  i s t r u e even  inherently graphic  applications.  or  often best  to  to  (such a s  tablets etc.)  directly.  p i c t u r e components t o  They c a n be be  operated  c o n t r o l t h e form o f t h e d i s p l a y and so on.  The  v  information  that  we a r e d e a l i n g  with,  s i n c e i t comes  20  from  maps,  is  selection/rejection outlines basis.  basically of  points  and s p e c i f i c a t i o n  graphic.  outlines.  i n the approach  addition  demands t h e v i s u a l  of o p e r a t i o n s  For these reasons the f a c i l i t i e s  were u s e d  In  described  here  on  a  the  inspection  point  of i n t e r a c t i v e  by  cf  point  graphics  to the r e d u c t i o n  o f map  21  CHAPTER 2.0  II  METHODS AND  Introduction The  lines  l e a r n i n g and is  lines  individual system  shows  digitized various  the  flow  lines.  of  and  larger  that \ are  attached  a r e shown i n information  on a  Figure  on  for  to  the  disk.  A  these  This  cn maps a r e  person  memory,  the  2.1.  as l i n e s  him c a n s p e c i f y t h a t  displayed  system  of  The b a s i c components c f t h i s  i n t o t h e computer's i n t e r n a l  ways,  generalization  considerably  stored  around  automatic  levels  on t h e s e  and t h e d a t a  brought  a  interrelations  devices  various  in  and t h e  points  and t h e i r  diagram  subsequent  embedded  manipulating  be  TECHNIQUES  using lines  the  are t o  manipulated  screen  in  of the graphics  terminal.  2.1 L i n e  Representation  I chose standard  might  coordinate  The l i n e  used  lines  externally  method  i n the  as  example  as  information attaching  shown  in  Figure  t o be s t o r e d to  each  indicates  conveying  the  previous  example  as  depicted  at  a particular  point  the  in  2.2 the  then  relative  i n Figure level  values  means  line  is  (see  Figure  b).  1.7)  The a d d i t i o n a l  easily  handled  of  that  by  a number  pcint  in  a s a whole. I n t h e c a s e o f t h e  (or l e v e l s ) o f t h e p o i n t s  would  2.3. When i t comes t o d i s p l a y i n g t h i s of d e t a i l ,  the  i n the previous  approximation  importance  of  a number o f l e v e l s o f  and  of the vector  shape o f t h e l i n e these  (a  by  described  be g e n e r a l i z e d s e v e r a l t i m e s t o g i v e  detail  that  to represent  X-Y  chapter.  Jextgrnal).  these  levels  tell  us  be  line which  21a  O r i g i n a l Map  Ma i n j : omp_u te r_ (IBM  r  4-  Manipulation  External Line Storage (disk)  4-  260/67}_  ""I  Internal  & D i s p l a y Routines  Storage  I Display  Computer  (Adage Corp. DPR-2).  • L i g h t Pen G r a p h i c T^gmingl Function  Keys Dials  Keyboard Terminal L  (Tj»M  2260)  The I n t e r a c t i v e L i n e P r o c e s s i n g  System  F i g u r e 2.1  Levels of D e t a i l  Figure  2.2  22  points  t o i n c l u d e and  specified greater get  and  the  at l e v e l  The by  as  2.4  lower  level  Figure  it. of  10 15 25 33  22 35 45 55  2 0 1 0  •  •  • •  • •  •  •  described  of  2.6.  A similar objects  unique there  each  such  not  as  2.7  and  (i.e.,  arises  shown i n F i g u r e  taken  care  p o i n t -can different  be  o f by  two  as  level  u p p e r and  would  get  at  we  Figure  point  the  the  is  shown  2.5  while  display)  the map  in at a as  have  a  associated  with  representations contained  a  river  of g e n e r a l i z a t i o n i t  then  single  with  lower l i m i t s the  cf  appear  cannot  levels  quite  ordering  line  'X'  level  different  levels  edges come t o g e t h e r .  In  0  representation  lines  of  original  2.8  level  1 we  in Figure  associating  displayed.  lines  Thus a t  hierarchical  when h a n d l i n g  I f the  are  each  ranges of  at a p a r t i c u l a r  t h a t s p e c i f y the  several  i n d i c a t e d by  whose l e v e l s  level  example  higher  at a  be:  to  level  displayed  numerical  is a strict  adequate s i n c e the  be  at  would  point. For  rivers.  points level.  The  level  needs r a t h e r  problem  A line  above f o r e n c o d i n g  but  t o a p p e a r as  the  levels  point  was  which  2.2b.  The  i n Figure  values  of  detail  as  c a s e can  as  those  numbers),  m i g h t a p p e a r a t one  level  again  Figure  V  out.  specified  the  Y  long  only  the  X  •importance*  unique  2,  attaching a  Figure  in  to  a l l these  method  adequate the  with  to l e a v e  contain  2.3 ( w i t h o u t  line  levels  will  than or e g u a l  Figure  2.2a, of  level  which  case  have t c be  each  This  last  point  two  of the of  are  levels  the  associated  at  river, with  the  A L i n e to be  Generalized  Generalized  to a G r e a t e r Degree  Figure  Figure  2.4  2.6  22b  Figure Generalized  River  2.8  23  river of all  since  t h e two  'displayed  two  values  suitable way.  first  of the  two  arise  from  chosen the  this  reason  methods. way  is  by  interested lines  vector  features,  of  quite  must  method  the system  discussion  t o . Ho  of is  only  the  confusion should  become  data  grid  encoding  These  reduction  less  method can  The  only  really  take  straight  advantage  through full  although  the space  reduce of  we  are  especially  as  generalization.  The  and  that  advantage  v e c t o r s o n l y i n the a r e a s o f  important objection  to  sections  of data  be  encoding's  of o u t l i n e s  to c h a i n encoding  m a i n t a i n as many c o p i e s o f a l i n e  generalization,  i s attempted.  i t cannot  boundaries)  take  over  to  can  i n the s o r t  detailed  was  gives r i s e  c o a r s e r . Chain  relatively  freguently  advantages  lines,  generalization  means t h a t  curves  u s i n g Freeman c h a i n s ,  featureless sections  concentrating another  f o r encoding  considerable  Chain  (urban, p o l i t i c a l  approximation  sections,*  one  in  f o r the i n c l u s i o n  of t h i s  making t h e base g r i d  relatively  occur  were  generalization.  although  to represent s t a t i c  that  storage requirements. outline  when t h e y  more c o m p l i c a t e d c a s e s i n  be r e f e r r e d  when d r a s t i c  on a r e g u l a r  long,  point,  f o r handling these  i t enjoys s e v e r a l  for this  reliance  with each  approximation  problems  accomplished  of  adjustment  exclusion.  an e x c e l l e n t  serious  level  appear  makes p r e v i s i o n  values w i l l  vector  because  appropriate  would  For t h e r e m a i n d e r  alternative  while  system  associated  a convenient  The  lines  a t seme p a r t i c u l a r  1  implemented  not r e a l l y  the  banks, merge. By  the v a l u e s o n l y the proper  The  of  river  as  per copy  of  these  important is  there are  that levels  d e c r e a s e s as  the  24  level  of  sizes,  i t still  is  happy w i t h  not  then  that  level. of  generalization  The  that  The  A  the  the  method. A l s o ,  graphic  of  considerable  naturally in were  probably  of the  extent  neighbourhood.  from  the  next  level lowest  to  levels  to  be  a v a i l a b l e was  attached done  of v e c t o r  be  much  the more  approximation  digitized  by  (an AGT-10) i s a  lead  the  relative  this  way  is  this vector  than fairly  considerable.  in  region.  from  Also  importance of  choosing  some  the  those  there  and  i n the  that  seen  neighbourhoods  whose  value.  encoding  does n o t  skeleton  in  particular  could  seem t o be the  short  This  would  However  c f the  t h e n back a g a i n  for simplifications  changes  i n d i c a t e to a  representations.  boundary  because  be  particular  decent  representing  chain-encoding  generalization  i n t o s k e l e t o n form  way  to  maximal n e i g h b o u r h o o d s a l r e a d y  In  to  suited  g e n e r a l i z a t i o n than  greater  convenient  reflected  better  t e r m s of s i m p l y  digitization  whole  one  with  d i s p l a y device  is  expense of c o n v e r t i n g  and  . If  levels  levels  was  to handle  step  s u c c e s s i v e l y higher  i n favour  that  larger  at a p a r t i c u l a r  regenerated  of  point  data  the  levels  radii  would  encoding  also affect  changing  clumsy  the  machine.  different  radii  the  must be  Skeleton-encoding  the  very  vector approximation  further  most o f  driven  line  changes c o u l d  allows  easily.  i n being  s e c t i o n s of  whole  lines.  points  results  i n c r e a s e s , b e c a u s e of  the  initial  for display an  outline  obvious to  of re-enccding  be the  25  2.2  Manual  Interactive  A l t e r a t i o n Of  Levels.  i In  the  previous section  conveniently attaching this be of  represented an  section altered  the  extra  have seen  several  value  that  l e v e l s of  to e a c h p o i n t  I will  describe  either  en  the  masse o r  way  an  o u t l i n e can  generalization  along  the  s i n g l y , under  the  by  outline.  i n which these  be  values  In can  direct control  user.  In stages  order of  to  subset  by  specifying  addition  of  the  specified. level  alter  the  l e v e l s of  s e l e c t i o n must be  the  the  on  we  the  identifiers  levels  I f the of  made, The  l i n e s containing the  of  set  of  one  or  first  desired of  stage  points.  several  i s to This  select  is  done  these p a r t i c u l a r l i n e s .  the  lines  line  identifiers  s e l e c t i o n i s ¥ AL  more p o i n t s  in  then the  this  subset  are  also  i s I={i1,i2,...in }  set  of  points  In  and  selected  so  far i s :  P  =  ^ { i  (Xik, Yik,  £  1<k<  a number o f  set  P can  and  be  lower  altered.  P« * If,  instead,  specified  number o f  values are  further  points  to  (LBV)  for of  { ( X j , Y j , Vj) £ P values are  fragment  of  be  r e f i n e d by  r e s u l t i n g set  the  > VAL  ]  JLi|  bound  The  L i | Vik  I  (where J L i | i s t h e If  Vik) £  altered  the  Li)  simultaneously  specifying  an  values  then  upper bound  of  the  the (UBV)  points  tc  be  then  a  points i s : l LBV  to be  P o r one  in line  of  < Vj  altered the  < 0BV one  L i can  } at a time be  displayed  on  the  26  screen The  of  the d i s p l a y device  fragment  position screen  at another  specified  t o 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  (START) and a l e n g t h  one o f t h e l i n e s  t h e same b u t w i t h  ( L i ) was g i v e n  PAii  then  | V j > VAL, START < j < START + LEN }  belong  the  to  screen  same  and  1  indicating  at  t o be a l t e r e d  then  pressed. t h e new  value  a particular i s pressed,  points  case  to  (see  to  steps along  otherwise  screen  is  key  some  text  the  screen,  with  the  and t h e  and  i f  t h e next the l a s t  the  point.  level  then  and i f i t was  there  directly  are  points  portion cf t h i s  s e t of  few  context  of  of  each  the  former  i s so t h a t for  o f a p o i n t . In t h i s  value  to  t o t h e end o f t h e s e c t i o n o f  amount o f  value  i f one  f u n c t i o n key  reconnected  F i g . 2.10). The p u r p o s e o f t h i s  the l i n e  isa  attached  the d i s p l a y  are  the  pcint  moves on to t h e next  1  points  be d i s p l a y e d t h e n  alter  points  by the 'X' i s  a different  below  t h e 'X' g e t s  a l w a y s be a r e a s o n a b l e  decision  the  function  t h e •X  i s displayed together  portion  on t h e f i r s t  and i t s a d j o i n i n g segments d i s a p p e a r ,  d i s p l a y e d on  the  a r e a l l s c a l e d to f i l l  of  of a point f a l l s  P i g 2.9). Before  remaining  i f  of the p o i n t i n d i c a t e d  an end p o i n t t h e a d j a c e n t  the l i n e  lines  o f d i s p l a y and t h e name o f t h e l i n e  In e i t h e r  point  (see  will  and t h e y  bottom  I f the value  g r a p h i c s computer  not  the  the l e v e l  was s p e c i f i e d .  that  line  as much a s p o s s i b l e . S u p e r i m p o s e d 'X :  f o r PS i s  r e p l a c i n g P. i . e . ,  p o i n t s a r e j o i n e d by s t r a i g h t  If  what a p p e a r s on t h e  the e x p r e s s i o n  Consecutive  is  starting  | V j > VAL, START < j < START • LEN }  PS = { ( X j , Y j , V j ) £ P O L i  small  a  (VJL).  i s the s e t o f p o i n t s :  PS = { ( X j , Y j , V j ) t P If  (LEN) so t h a t  level  point  there  making  the  way t h e »X' is  either  Point  The  Alteration  Changing View o f the  Figure  Line  Figure  2.9  2.10  27  transformed  or  left  been used  to s e l e c t  changing  the  unchanged. R e g a r d l e s s  the  v a l u e s i s the  have been s e l e c t e d Vnew = C1  • C2  parameters of t h i s  by  the  user  2.3  at  same. The  which  method  has  altered,  the  method  cf  v a l u e s of  the  points that  transformation.  i.e.:  * Void transformation  the  time  section  we  he  (C1  and  C2)  are  specified  initiates  the second  step  of  the  how  could  generalized  process.  Learning  In t h e l a s t by  be  undergo a l i n e a r  The  selection  p o i n t s to  of  h a n d , so  it  is  to speak, a l t h o u g h  still  l i n e s are  fairly  t o be  to t h e system behaviour  of  the  satisfactory  can  my  be  job  c o u l d a program.  step i n getting to  the  represent  criterion must  will  user  left  up  be  then  the  to the that  in  mimic  the  selection  performance  reasonably  added  selecting  points  could  line  do  could  chapter.)  points  fcr  scheme must more  The  at  then  the b a s i c assumption next  a  see  (10 p o i n t s , s a y ) ,  more c o n v e n i e n t  much  i f many  was  p o i n t s , when a l l he  in a  fast,  a component  person  to r e c o g n i z e  a  consuming  job of  a  examined i n t h e  lines  is fairly  program.  if  of the  encoding  lines  to  be  way  time  reason  c o r r e c t n e s s of  machine  t h a t a new  represent  (The  the  very  Once t h e p r o g r a m ' s  a small section  hypothesis  and  this  of s e l e c t i n g  so  i t this  i t to l e a r n  hypothesis  time  is  For  of the  one  this  was  user.  that  for alteration is  processed.  lines  doing  expensive  that allows  approximates  It  saw  in  first  alteration  f o r m . The  satisfy  is  general  way  that  main i t  without  28  sacrificing the  the  essential  e l e m e n t s t h a t a r e most i m p o r t a n t  I suspect between  these  are the  them.  For  chain-encoding learning Using  this  automatic  scheme  a  line  F i g u r e 2.11  f a r there  would  the  the  only  number o f 8.)  The  ^3  no  original  to  potential  candidate  the  currently  s i n c e there  uses i s given  QLEN =  similar  values.  the  values  visual be  and by  MINLEN  alternating  sense  the  that  is .still  lines.  The  they  f o r both  the  can  vary  next  are  line  the  much  step i s  transformed  implementation  the  and  lengths  logarithm  of  way  t o compress  the  and  alsc  importance.  because i t  (Another  Arctangent  lengths.)  too  angles  on  a good  original  good  function since i t  The  exact  length  that  relationship the  system  the f o l l o w i n g e x p r e s s i o n :  I l o g / L EN \ |_ VMISLEil  parameters  the  system.  example,  (In t h e c u r r e n t  lengths  would  guantized  an  i n the  l e n g t h s . I.e.,  compresses a g r e a t range of  between  by  be r e c o n s t r u c t e d e x a c t l y . However  this  and  to  angles  of the  by  (Ai) . F o r  l e n g t h depends m a i n l y  correspond  the  processed  components  length since i t provides  seems  and  • • •  discrete  which  of  as:  could  angles  guantized  be  information lost  line  these  range over  The  ^£  discrete  great  too  stored  f u r t h e r than  these  to  angles  consist  to a d o p t a v a r i a n t of  represented  between e s s e n t i a l l y  to q u a n t i z e on  be  been  digitized  distinction  is  has  have t o go  to take  is  vectors  I chose  alteration  also  for visual discrimination.  the  lines  o f l e n g t h s - ( L i ) -and  original we  reasons  represent  fij X>| So  l e n g t h s of  these  to  and  sequence in  f e a t u r e s . I t should  and  *  8 log/MAXLEjn iMliLEN/ MAXLEH can  be  +  1  specified  by  the  user  28a  Thresholds f o r Angle  Quantlztion  29  based  on p r i o r  knowledge o f t h e l i n e s  approximate the a c t u a l The  "8" c o r r e s p o n d s  net  effect  through with  8 such  bounds on t h e l e n g t h s t o be  t o t h e number  to  transform  vector  that  the  l e n g t h s onto  the integers 1  are closer  along  vector  the  t h e two v e c t o r s i n o r d e r the  i s then  angle  positive  just  must be between  angle  2.12.  i f the o r i g i n a l  Thus  THRESHOLD (3) on.  together  approximately  standard  those  +U  and -II  angle  region  will  f o r point  This  angle  is  incoming  made by t h e restriction  correspondence  given  by F i g .  was between THRESHOLD(2) and  quantized  values  angle  for  would  these  be  4,  and  thresholds  are  d e p i c t e d i n F i g . 2.12, b u t c a n be c h a n g e d a t  be i n t h i s  range  and  around  this  i s  180° b e c a u s e the  critical  elimination.  quantization  and l e n g t h a l o n g  originally  the  . The  by t h e u s e r . The t h r e s h o l d s a r e bunched  most a n g l e s  the  x - a x i s . The a n g l e  and t h e q u a n t i z e d  the c o r r e s p o n d i n g  The  that  t h e u s u a l one w i t h  between t h i s  angle  encountered.  between t h e two v e c t o r s a t a p o i n t i s c a l c u l a t e d  rotating  lies  outgoing  will  and s h o u l d  o f l e v e l s o f q u a n t i z a t i o n . The  that the quantization levels  angle  rigidly  so  processed  shorter lengths. The  by  is  being  appeared  process  the entire  i s applied alternately line  so  that  a  to each  line  that  a s i n F i g u r e 2.11 m i g h t r e s u l t i n :  0 4 2 3 8 3 3 2 4 1 0 where  the  particular process  O's  point i s  this  correspond  indicate' under  quantized  undefined  angles  consideration version  of  t o t h e •view' o f t h e l i n e  a t t h e ends.  during  the  a s seen  line  the  When a  learning  i s reordered to  from  that  point.  30  There are  a number  have  chosen  point  P i i s as  processing chain  is  c f ways t h a t as  follows:  depicted  i s to the  along  the  2.13b. T h i s  we  progressively  directions  along  then  d i r e c t i o n of  that  direction  until  in  important  The in  to  should  I f one  end  come up  the  there  has  i n the  the  I  of  a  direction  i s transformed a bias  way  vicinity  the  to  form  because  tree  reached.  For  to  verdict the  is  is  of  into  locking  until  been  a  example  the  ahead  too.  how  of  is  that  by  other  given  they are  feeding  tree  i f the  (see or  Fig  not  node  line  point  to more  the  line  2.14a) i n the  point  symbols d e t e r m i n e s a  terminal  'old' i t i s  i n the  lengths.  begins  how  i s encountered  bias  seems  located  a measure o f  also  A  whether  the  alternating  i s continued  i t would r e a c h  that  in  line  than are  string  v e r d i c t being  and  the  into a decision  This  decision  of  i t  w i t h a v e r d i c t on  altered.  farther  and  process at a point  i s also stored  verdict  end  i s reached  scheme  converted  is  addition  line  look  view s t o p s  s e q u e n c e "3545..." t h e n  where  it  line.  that  learning  through the  the  the  this  be  verdict  done and  and  gives  in visual discrimination  this  order  line  2. 13a  the  be  line.  Effectively  angles  I f the  in Figure  r i g h t then  shown i n F i g u r e  t h i s could  containing  was  the  indicated  the  'strong' (i.e.,  the  represented  should  at  path  be  the  node  altered.  terminal or  by  nodes  'reliable' number o f  In  the  times  referenced).  Once the  expected  it  i s compared  the  v e r d i c t at  with that  v e r d i c t has  the  v e r d i c t of  terminal  been d e t e r m i n e d the  node can  user.  simply  this  way  I f they agree  then  be  in  made  'stronger'  D i r e c t i o n of processing  >  (\i L t  AiJM L ^ , A iM  Lt.,  A l o u L- l o . (b)  Transformation of a Line w i t h r e s p e c t to the p o i n t  Figure  2.13  The  D e c i s i o n Tree and  an A d d i t i o n to i t  Figure  2.14  31  and  'older*  by a u n i t v a l u e .  However i f they  disagree  then  there  a r e s e v e r a l t h i n g s t h a t c a n be done: t h e v e r d i c t can be l e f t same b u t made weaker, can  sprout  verdict. the  new  and  terminal  nodes f r o m three  o f t h e node,  whether t h e r e  factors  o r t h e v e r d i c t can be c h a n g e d , o r the t r e e  Which o f t h e s e  depth  the  that  node, e a c h w i t h  a l t e r n a t i v e s i s c h o s e n depends  t h e 'age' and  i n the  i n the f o l l o w i n g ALGOL-like  (4 * / 1_J -  on  ' s t r e n g t h ' of the v e r d i c t  a r e any more s y m b o l s l e f t  are contained  i t s own  line.  These  expression:  \ - /STRENGTH_H\\ > 0 V V DEPTH MAXDEPTH/ \ AGE+1~ // then "SPRO0T"  if  else  i f  1  STRENGTH > 0 then "WEAKEN" else  The  effect  is,  the less  further. (e.g., about is  "CHANGE";  of this  expression  likely  i t  This  i s done  is  i s such  that  to a v o i d  that  the  tree  nearly  as  'strong'  will  be  expanded  growing e x c e s s i v e l y l a r g e  t h e number o f nodes i n a c o m p l e t e 9**d which grows v e r y  t h e d e e p e r the node  tree  q u i c k l y with  as i t i s ' o l d *  of  d). Also and  trees  depth  d  is  i f the v e r d i c t  i t i s reasonably  old  i  then  i t has g i v e n  slightly. however,  This  good s e r v i c e and so s h o u l d i s  i t i s young  done  by  o r o l d and  making  i t weaker  h a v e t h e v e r d i c t c h a n g e d . In t h i s c a s e  as  usual  fact,  i t has been  verdict the  i s reduced  decided  of a l l these  new  to sprout  line.  t o t h e node  by  reached  by one  unit. I f ,  t h e age i s i n c r e m e n t e d  one,  is  in  nodes t h e n t h e  i s s e t t o agree  node. The o p p o s i t e  line  likely  the u n i t amount. I f ,  by c o n s i d e r i n g  F o r example i f t h e i n p u t  punished  more t e r m i n a l  nodes, e x c e p t  v e r d i c t o f the former t e r m i n a l  given  be  weak t h e n i t i s much more  to  but the s t r e n g t h  only  with  verdict i s  t h e n e x t symbol o f t h e the  same  as  in  the  32  example expand  above the  (i.e.,  tree  "3545...")  because  the  expected  v e r d i c t , then the  in  Figure  2.14b. I n  of  depth  1 at the  There  time.  In  pushing An  way  other  one  of  program  guide is  two  the  the  this  the  of  of  point.  This  effectively  The levels the  expanded  other  way  beforehand  level  of  to  no  then  the  To  help  statistics the and  give  number o f the  program results  screen.  the  the  mainly  as  only  This  the  can  level  true  the the  same person  terminal. decision  help  the  then the  of  point  internal  the  the  of  user  t o which a  to r e f l e c t  'view*  the  deletion  line  to  be  cost.  true  v e r d i c t i s to a l t e r  v e r d i c t i s determined  can  be  evaluate  used the  available  times the  at  graphics  of d i s p l a y  behaviour  tree  and  was  to c a p a c i t y  in verdicts getting  by  This  many t i m e s t o  with  v e r d i c t s made s t r o n g e r  have l e a r n e d  being  from  a preview of  both  a breakdown f o r e a c h l i n e  number o f will  are  the  appear  specify  i s below a s p e c i f i e d l e v e l .  same l i n e  statistics  to  with  will  levels  the  i s changed  extra  the  learning  tree  to  the  keys at  level  line  advantage t h a t message.  concur  grows f r o m  user  alter  i n d i c a t e the  and  a point  the  the  allows  at  the  program. I f t h e the  the  to  tree  i s that  i s a v a i l a b l e on  version  not  been d e c i d e d  v e r d i c t comes d i r e c t l y  method  quantized this  for  function  i s lower than  has  learning.  manually  two  t r a i n i n g of  altered  of  i t  did  additions  ways  i s to  user  manner t h e  words t h e  advantage of  the  start  are  v e r d i c t . One  this  and  of  weaker  enlarged. when  stronger  has  program These  i n terms  and In  the  reinforce  methods;  of  "changed"  general,  continued with  whether  the  processed  the  the  learning  relatively  few  33  verdicts  being  made weaker o r c h a n g e d and o n l y  slew  enlargement  of t h e t r e e . 2.4 A u t o m a t i c  Once  t h e p r o g r a m a p p e a r s t o have l e a r n e d  can  be t u r n e d  it  learned  a level, the  lines  i s done by s p e c i f y i n g t h e p a r t i c u l a r  lines,  converted,  new  then  This  that  In t h i s c a s e ; once a  the p o i n t  f o r t h e point»s  level  representation  so  that  levels  will  always  still  be p a r t  these  points  are later  be s u f f i c i e n t l y  o f the context  high  have been a l t e r e d t h e r e s u l t s c a n be and  falls  tree,  then t h e  the given  i s updated.  o u t by  raising  This  i s done  a l t e r e d the r e s u l t i n g  points.  displayed  that After for  they  these  be  redone  sections  manually.  If  t h e n t h e program  c o r r e c t i o n s a r e being  there  inspection  i s some s i m i l a r i t y  c a n be t a u g h t  made. T h i s  c h a n c e s o f t h e same m i s t a k e s b e i n g  will  will  the l i n e s  c o r r e c t i o n . T h o s e s e c t i o n s "that have been g e n e r a l i z e d  can  teen  altered.  below  points.  t o ensure  o f nearby  has  i s t o be  g e n e r a l i z a t i o n c a n be h e l p e d  l e v e l s o f some p o t e n t i a l l y " b o r d e r l i n e " i f  line  of the l i n e  the  even  on t h e l e v e l s o f  and f e d i n t o t h e d e c i s i o n  the quantized  automatic  are s i m i l a r to  t o be p e r f o r m e d  d e t e r m i n e s whether  value  satisfactorily i t the  t o be s e l e c t e d .  returned  the  level  on new l i n e s  on. T h i s  quantized,  If  loose  and t h e t r a n s f o r m a t i o n  points  verdict  Generalization  poorly between  some mere a s t h e s e  hopefully  diminish  made i n t h e f u t u r e .  the  34  Chapter 3. 0  III  EXPERIMENTAL RESULTS  Introduction There  are  regarding  the  described  in  and  a  great  approach the  wide r a n g i n g What  to  these questions the  it  nature  of  of  can  Three of  be  that  the  asked  has  most  been  important  are: people's  perceptual  outlines?  possible  generalization  that  generalization  chapter.  responses to generalized Is  questions  the  previous  of  is  many  to  achieve  outlines  satisfactory  with  purely  local  considerations?  The  -  How  well  the  g e n e r a l i z a t i o n c f map  remainder of  experiments  does the  t h i s chapter  that  were  system  perform  with  regard  to  outlines?  is  devoted  performed  in  to  a  attempts  discussion t o answer  of  these  guestions. 3.1  Perceptual  Response t c  A major p u r p o s e o f generalizing  map  this  outlines  w h i l e r e t a i n i n g enough o f recognizable  by  how  respond  people  drastically. important line  people.  Is the  element  of  To  answer  that  is  to  provide  a  way  r e q u i r i n g a minimum c f d a t a e s s e n t i a l components t o  outlines  r e n d i t i o n of  that  performed  the  work  It i s therefore  to  character  help  Generalization  that  or  involved  questions people  easily  to  investigate  have t o  be  generalized  features  i s i t the  the  two ranking  most  maintenance  i s p r i m a r y ? What r o l e does a e s t h e t i c s  these  storage  necessary  prominent  recognition  be  of  play?  experiments a  of  number  were of  35  generalizations of a particular to  which  they  experiments outlines cases, (see  each  were  3.1) t h a t  1:200000. A s m a l l e r mounted  each  (marked  shuffled cards  and  what  their two  marked  except  municipality  version  line, of  (see F i g u r e  the  subject  meant.  an  although  to  hardly  and a s k e d  t o the  one  opaque  make c o m p a r i s o n s  among  The r e s u l t  was  individuals  performed took  represented a cross-section  interactive my  colleagues  exhibited  of  range  homogeneous  The  was  and  plotted  3.4). In  (which  were  to arrange  these  marked  "1".  outlines  and  by t h i s  that  group  Each  mounting  prevented  directly  and i n s t e a d  versions  mere  by  part  a  different  i n b o t h . These  of society  might  friends.  o r even  However,  and i s g u i t e  expected sufficient  used i n t h e f i r s t  person subjects  potential from  t h e d i v e r s i t y of  from  a  f o r my  experiment  trial  entirely  s m a l l sample i s , I b e l i e v e , be  by  of t h e s e r a n k i n g s i n t h e  map u s e r s , c o m i n g , a s t h e y d i d , a l m o s t  opinion the  3.2)  a r e r e c o r d e d i n T a b l e s 3.1 and 3.2. E v e r y  experiment some  Vancouver  was g i v e n c a r d s w i t h t h e o r i g i n a l  The  appearance.  experiments  i n both  of approximately  (see F i g u r e s 3.3  t h e s u b j e c t s t o compare t h e d i f f e r e n t  within  used  the  o f opaque c a r d b o a r d a s were t h e v a r i o u s  with a l e t t e r )  maps  individual  that  West  at a scale  Both  i n t h e same way and were g i v e n no g u i d a n c e on  "similarity"  forced  way  degree  outline.  w i t h a "1") and i t s g e n e r a l i z a t i o n s  was a s k e d  overlaying  original  The o r i g i n a l  i n order of the s i m i l a r i t y  subject  according to the  same  was d i g i t i z e d  scale  the  the  the  of t h i s o u t l i n e  experiment  outline  of the  on a p i e c e  generalizations  in  different.  was t h e o u t l i n e Figure  and  resembled  were c o n d u c t e d  used  outline  indicative  larger,  less  purposes.  were d e r i v e d  from  35a  LEVEL=0 WEST_VAN  Outline  of West Vancouver M u n i c i p a l i t y Figure  3.1"  O r i g i n a l West Vancouver Outline Figure  3.2  V e r s i o n s o f West Vancouver f o r Experiment I  Outline ^  V e r s i o n s o f West Vancouver f o r Experiment I I  Outline  Figure 3.4  Figure 3.4(continued) CD  RESULTS FOR EXPERIMENT 1  Ranking o f s i m i l a r i t y  to o u t l i n e 1  Trial Number  High 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  TABLE 3.1  B  F  G  35g  RESULTS FOR EXPERIMENT 2  Ranking of similarity to outline 1 Trial Number  High 1  2  3  1  h.  f  b  2  b  3  a  c  e  4  h  b  e  5  e  f  e  4  e  5  6  e  c  a•  g  d  b  g  e b  a  h  -  Low 8  7  d  f  d  c  g  d  g  a  f  f  h  g  a 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  12  b  13 14  e  h  e  e  d  g  f  h  a  f  h  c a  g g  d d  f  e  b  a  c  h  f  b  a  e  c  g  d  TABLE 3.2  36  the  original  the  number  points the  in a variety  o f ways. The g e n e r a l  aim was  to reduce  of p o i n t s  t o a b o u t 23, one q u a r t e r  o f t h e number  of  i n the o r i g i n a l  (which i s 9 2 ) . F o l l o w i n g  are  of  ways  in  which  the  points  details  were s e l e c t e d f o r t h e v a r i o u s  outlines: - Outline in  turn  22  points.  A - Randomly. E v e r y  and was s e l e c t e d  B.  Outline Chapter  1)  0.08". 23  with  considered  a probability  o f 0.25.  a  threshold  deviation  of  points. C. H a n d - p i c k e d . The p o i n t s  hand t o e n s u r e t h a t  right-hand  corner  Outline except  with  was  D o u g l a s #1. The method o f D o u g l a s (see  was used  Outline by  point  the s m a l l  remained  were  inlet  open. 21  selected  i n the  lower  points.  D. D o u g l a s #2. The same as f o r o u t l i n e B  that  the t h r e s h o l d  was r e d u c e d  to  0.06".  26  points. -  Outline  slight with 23  E.  Lang.  variation  a threshold  Outline  distance  angles  were s e l e c t e d . 25 -  Outline  G.  was k e p t . 24 Note:  the  hand c o r n e r s avoid  gross  were s e l e c t e d  o f L a n g ' s method  F. L a r g e s t  largest  Points  o f 0.07".  angles. (i.e.  (see 27  Chapter  a 1)  points.  The p o i n t s  greater  using  that  than  had t h e  66°) o f bend  points.  Every n'th p o i n t .  Every  fourth  point  points. points  i n t h e u p p e r - l e f t and  o f t h e map  were a u t o m a t i c a l l y  distortions  in  the  cases  upper-right kept  to  where the  37  method used t o they  be  and  G.  kept. There  outlines They  obtain This are  that  arise  do  from  of the  16,  conformed  to  interesting. by  more  greater inlet and  this  of  bumpy  over  people  the  E  letter 70  Some but  the not along  The  f a c t o r as  I I I to l i n e  3.5)  although  to a c t u a l  points.  see  I I as  the  average  trial.  order  adding  due  to was  left  said  that  they as  the  them  by  the  left  as  an  original  probably  as  the  that  people  line  in Figure  the  factor  were more of  the  important total  f o r B over  D  accurate  maintenance  of  of  i n B,  comments  the  side  a  small  ranking  i n terms  a representation  the  overriding  center  likely  preferred  while  regarded  the  bottom  open  are  i t i s by  that  finished  the  along  regarded  E was  i s b o r n e out  had  details  fact  people  that  i s preferred the  up  These t o t a l s  deviations  when C  they  superimposing  the  in fact  after  It i s quite  of  c a l c u l a t e d by  and  supposition  from  that  i t i s the  However,  the  nature  some p e o p l e ' s p r e f e r e n c e  indicates.  line  these  respectively. Generally  a c t u a l accuracy  deviation  in  f o r each  almost t i e d  all  specify  outlines A  wiggles  was  lower r i g h t c o r n e r  said  consideration.  crucial  can  order  60,  off. This  character  integrated)  we  i s probably  subjects  others  important.  50,  t h a n C.  Some  rendition  3.1  l o w e r r i g h t hand c o r n e r  the  outlines.  used.  each  B are  margin. T h i s  made by  was  not  with  incremental  s e q u e n c e , but  i t closed  while  33,  C and  people  i n the E  32,  reguired small  i s EDCBFGA. T h i s  19,  did  correspond  the  p o s i t i o n numbers o f  are  was  not  r e f e r r i n g to Table  preference  outline  also  Calcomp p l o t t e r t h a t  By  the  was D  (or net  and  a D  would  prefer  (see  Figure  I 3.6  shows  that  A L i n e and Two  A l l Three L i n e s  Possible Generalizations  Superimposed  Figure  Figure  38  line  I I obviously  Generally different respond There  we  i s  course,  little  the  rendition  the  i s  other all  in  can  say about  This  i s partly  points  along  points  how  their  experiment ways  when  because  one  this  different  o f them  same  number  versions  i n the second  same  basic  p o i n t s c h o s e n from outlines  have  23  the  of  better the  i s t o see people's map  that a l l  t h i s aim i n mind  and p e r f o r m e d .  experiment 8  an a d d i t i o n a l f i x e d (except  were a l l d e r i v e d  generalized  s e t o f 19 p o i n t s  points  vary i n  Generally,  available  t h e same way. I n a l l o f t h e the  comparisons.  t h e o u t l i n e s used  o f an o r i g i n a l  was d e s i g n e d  they  to g e n e r a l i z e o u t l i n e s  boundaries.  has  that  and t h a t  making  o f p o i n t s . I t was w i t h  experiment  o u t l i n e s used  roughly  there  maps  from  aspects  we  more  less.  conclude  among v a r i o u s  t h a t a second  The  much  p o s s i b l e . What would be o f i n t e r e s t  preferences  in  see  to different  number o f  have  can  people  satisfactorily. the  deviates  outlines  together s e t of  d and  with  7.  four Thus  1  ^).\arid' 'are;  fairly  similar. The is  average ranking,  becahdfg  respectively. as  b,  e  and  the t o t a l s  Certain lines  and  controversial.  c a l c u l a t e d i n t h e same way a s  c,  while  a r e 3 3 , 46, 57, 68, 69, 73, 76, 82  are rated others  T h i s c a n be seen  more  rigorously  their  mean p o s i t i o n s . T h i s g i v e s  1  by  adding  E x c e p t f o r d and g which  before,  fairly  such  as  consistently,  h, f and d a r e more  by i n s p e c t i o n o f  the  Table  d e v i a t i o n s i n each  totals  have o n l y  such  o f 19, 19, 23,  3.2  trial 22,  3 o f t h e p o s s i b l e 7.  or from 33,  39  27, at  34,  30  (where t h e  the i n d i v i d u a l  account lower  the l i n e for  saw  but  Most  (see F i g u r e  people  do  not  t h e r e a r e some who  i n the middle  others  later  outlines  for this. left  o r d e r i s t h e same as b e f o r e ) .  it  is  to j u s t i f y  the o v e r a l l  their  some p a r t i c u l a r  he  was  attributed  ranking support  the  point  of  expressions was  quite  or  absence  the  of  advantage  they  work d e s c r i b e d h e r e  not  views. be  Every  most Gne  at a  while made  person  important person  said  coastline  t h e s e a . The that  their  were " b o t h e r e d "  f e a t u r e s as  i f they  shews even  by  from  tone  and  perception the  presence  were r e a c t i n g  everybody. others  Some  for  people  particular  t a s t e s and  flexible  t c p r o v i d e such  clearly  ways o f  doing  shape. T h i s s u g g e s t s  less  mere  different  technique  individual's over  and  have q u i t e  a single  overall  looked  indicated  experiment  people  that  t o an  Often  some  comments p e o p l e  these  the  bays t h a n i n p e n i n s u l a s and  he  land  at  on  well.  preserved,  the  the  people a l s o  this  satisfy  character  that  particular  that  and  be s u i t e d  of  g r o u n d s as  not  others  by  think that  outlines  an  used  first  will  view  subjective.  aesthetic  I  to the f a c t  partially  c h a r a c t e r of  to  unimportant.  in  looking  point  n o t mind. The  s h a p e . The  interested  can  the s h a r p  a s p e c t s o f t h e shape t c  more  this  we  i s important  w h i l e o t h e r a s p e c t s were r e l a t i v e l y that  like  do  o f the l e f t  3.4)  By  looking  will  like  a  to  and  method  methods. I t i s t h e aim system.  see  still  that  p r e f e r e n c e s would  a flexible  at  generalizations  features, that  than  can  enjoy of  the  40  3.2  Local_Beduction It  is  generally  information rather  i  i s more e a s i l y  than  global  software discourage widely separated. decisions this  based  sense t h i s  on  on  the  but can  the angle  how get  at  how  when a l l t h a t person  experiment  can  view  be  we  i t , then  North  manner  described  was  a  at  time  set  up  on  Chapter  containing  a t most 7 p o i n t s  small  "X"  a t one  of  buttons depending  of  the  was  points. on  be  the  i s a small  and  A  (see  The  whether  on  person that  local-  Clearly,  depending  only  at?  view  We by  outlines  section.  can  (If  a  a machine.)  An  of  a  manually reducing  an  adeguacy  Figure  section  displayed  fully  performed.  subjects  2.  the  required  neither  In  unsatisfactory,  t o i n v e s t i g a t e the  number o f  on  need  manually r e d u c i n g  Vancouver M u n i c i p a l i t y in  a point  make  clear a  program have t o l o o k  probably  experiment  involved  of  this  to  is  perform  purposes.  general  bound  perform  that  to  not  what p o i n t  reject  does a  s e e n a t one  just  the  outline  two  if  in  of a lower  people  do  t o do  Basically local  well  cannot  Even  f o r our  local  spatially.  adequate do  of  existing  cheaper  be  s e l e c t or  a  However, i t i s not  obvious  will  and  will  i s most a p p r o p r i a t e  some e s t i m a t e  on  information  is restricted  exception.  much more o f a l i n e  observing  using  that  i t i s not  point  performed  much s i m p l e r  considerations  that  processing  Computer a r c h i t e c t u r e and  information  d e c i s i o n to  computer  conveniently  satisfactorily.  continuum  that  making d e c i s i o n s  global considerations  making  and  basis.  work i s no  generalization  case  It. i s usually  £riori t h a t l o c a l  global  the  of  3.7)  in  the  outline  the  screen  would  then  point  was  with press  t o be  kept  the  a one or  40a  Outline  o f N o r t h Vancouver M u n i c i p a l i t y  Figure  LEVEL=0 N0RTH_VRN_D1STRICT f  3.7  41  r e m o v e d . I f the without point.  that I f the  line  was  last  four.  was  M  X  was  was  point.  In  removed  In  The  moved to s e c o n d  W  this  way  same  the  every  i n turn  s c a l e at  the  then  and  next  with  individual  i t would  individual  also  screen  to avoid  The  task  giving spatial  of  considerable  personal  experience)  learn  In  how  to s t a r t  t o do with.  screen  and  (i.e.  leaving  displayed then  asked  successful step  was  the  small  without  the  can  aim  the  be  I  the  reduction fragments  knowing  the of  what i t was.  the the  outline cn  either  displayed  that  i f the  screen.  The  middle of  the  points  on  my  depend  cn  some o p p o r t u n i t y  this  West  o u t l i n e on  of  The  version  reduced  remaining  p o i n t s from 3.3,  counted.  result  the of  then was This  much  mere  ruthless  the  North  Vancouver  people  were not  reduction.  The  Vancouver o u t l i n e using  seeing  the  three-quarters were  how  to  Vancouver  fragments  three-quarters  The  (based  o u t l i n e of  The  North  circumstances  would  reduction  to see  without  such  a l l of  from T a b l e  the  the  i n the  subjects  a  number o f  seen  were  suspected  the  points).  i n pruning  be  fill  next  then  original  performance  for  opportunity  the  keeping  c h o s e n so  under  points eliminated.  in achieving  the  and  give  23  and  and  have t o As  to  about  p e r s o n an  outline..  to  just  line  i t t h e y were g i v e n  in turn  would  that  and  fragments  centered  They were shown f i r s t  displayed  gave the they  order  skill  moved t o  than 2 p o i n t s  was  re-drawn  clues.  generalizing a  reguires  practise.  were  was  point,  the  fewer  f r a g m e n t and  "X"  points  along  no  line  last  three  whole o u t l i n e were d i s p l a y e d fragments  the  to the  point  which t h e  f o r every  the  e i t h e r case  re-drawn adding  considered  side.  point  whole t h i n g these  first  reductions  very next only and for  41a  RESULTS FOR EXPERIMENT 3  Number o f P o i n t s Trial Number  Remaining  West Vancouver (92 p o i n t s o r i g i n a l l y )  N o r t h Vancouver (134 p o i n t s 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  shown a t  In done  the  shown i n F i g u r e s  same s c a l e  general  fairly  Almost the  are  a l l the  did  of  the  to  be  f o r West  original  92  points  reduction  was  slightly  This  was  s e g m e n t s i n the Trial  6,  desired lower  the  points  In  t o be  It  be  would  depended  degree of  generalization the  slightly North  in  o u t l i n e s used  of One  and  average  one-half the  of  average 134  large  number o f  long  in particular concerned  line  actually left  subjects  original  a large  r e m a i n d e r c f the  this  the  person  removed  of  to  The  Vancouver  the  answer t h e  (on  about  the  p o r t i o n from  the  was  done  l e s s than  question  be on  interesting the  reduction, this  size and  of on  manner. The  i s a l s o an  than  lines  in  cne  posed  see  the  quite quarter  there  the  would  have  hew  people's  experience of  the  f a c t o r that will are  at  view a v a i l a b l e ,  effect  important  which  to  their  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  problems  mistakes.  the  over  of  was  character  reduction.  became e x c e s s i v e l y  person  the  t h i s s e c t i o n much more e x p e r i m e n t a t i o n  done.  desired  and  i t i s c l e a r that  spite  corner.  reduction  This  generalization  some g l a r i n g  one-third  in  originals  i s maintained. R e f e r r i n g  with  t o more f u l l y  of  performance  done  the  remaining.  order  beginning  are  was  above  a l t h o u g h the  satisfactorily. of  while  with  the  captured  3.3  Vancouver  3.14)  degree of  middle  to Table  lower l e f t  Figure  are  3.14  more d r a s t i c i n t h e i r  reduction  points.  that  there  right-hand  to  3.8.  see  although  f i g u r e s and  learn  can  main f e a t u r e s  c o a s t l i n e on  series  in Figure  terms we  well  3.9  the  doing  character  of  would have  to  present  different  large angles  between  O r i g i n a l O u t l i n e s o f West Vancouver  Figure  3.8  and N o r t h Vancouver  SB  43  consecutive the  vectors.  testing  that  suggest  that  only  a local  3-3  on The  However, was  done  i t i s not basis  i n s p i t e of there  hopeless to to  perform  System's,Generalization  The  third  this chapter generalize learning  map  how  question  can  be  mimic and  how  well  of  broken  a  cf  evidence  program  generalizations  the  o u t l i n e s . Since  t o mimic a s e t  sufficient  expect  that  w e l l can  l i m i t e d extent  to  operating  satisfactorily.  Performance  major q u e s t i o n  was  is  the  was  asked  system the  system  beginning  of  here l e a r n  tc  generalizes  reduced  down i n t o two on  the  described  previously  does i t do  at  parts:  outlines  by  first  outlines, How  it  the  w e l l does i t  has  never  met  before?  The the on  first  step  s e l e c t i o n and which  chosen  the  manual r e d u c t i o n  system  from  i n attempting  the  i s to  digitized  Mainland  Municipalities  with the  letters  learning  s e t . The  rather  and  line  types.  at  A  reason  that  level  they  These  0 we  lines  that  aimed  original  number  excessive  distortion.  f o r each  line  were these  that  3.16  points The  initial case  as  chosen  at  to  be  the  hand so level to  i n e a c h o u t l i n e as  i s shown i n T a b l e  3.5.  were  the  basic  were c h o s e n  regicn  of  the  features  and  that  8 Figure  one  and  outlines  outlines labelled  a v a r i e t y of  by  is  E.C.'s Lower  particular lines  close  original  of  lines  some of  t h e y spanned  and  set  these  3.15). The  to c o n t a i n  to leave  of  our  were r e d u c e d  have F i g u r e  was  In  Figure F  appeared  reduction  points  (see  i s simply  o f an  boundaries cf  through  than o t h e r s  map  learn.  t c answer t h e s e g u e s t i o n s  displayed 3.17.  This  quarter  of  possible  without  remaining This  number  basic  the  of  learning  43a  43b  LEVEL-8 Reduced O u t l i n e s f o r L e a r n i n g  Figu  44  set  o f o u t l i n e s was  system  in  threshold standard  the  of  and  the  was  twelve,  was  permitted  section.  manner  level 1  thus  to  statistics  were  In  nodes  experiment  after  There are to  the  the  comparing the  model  the  discernable outline  F and  was  zero  to  point  parameters  were  line  in  fifter how  the  same  previous  five  times  in  iteration  and  node  how  many  (see T a b l e  3.4).  the  system  generalize  using  was  given  its  the  current  shown i n F i g u r e s  numbers of p o i n t s i n e a c h o f  these  3.18  outlines  question  using of  how  clearly  shown  difference even t h e n  The  capable is  after in  the five  there  can  results  well  the  first  in be  mentioned  system  step  so  can  mimic a  tc  ensure  is  c f d u p l i c a t i n g the  person's  case  seen  as  can  iterations  Figure  occurs  the  3.17. the doubt  be  ( F i g u r e 3.22) The  upper as  only right tc  by with  really corner  whether  i e . The a n g l e t h r e s h o l d s ( i n r a d i a n s ) were 0.65, 2.15, and 3.05 r e s p e c t i v e l y and t h e minimum and maximum lengths 0.01" and 0.5" a t t h e s c a l e o f F i g u r e 3.15 1  as  the  many t e r m i n a l  changed  are  decision tree  each  decision tree  outlines  with  about  performed  or  iteration,  a  i n the  described  weaker  to the  each  results  lines  the  indicate  i s actually  performance. T h i s  depth  2  the  3.5.  the  system  length  to  person's g e n e r a l i z a t i o n behavior. that  and  message.  s e v e r a l ways o f  answer  Chapter  the  resulting  i n Table  in  procedure  were added  and  angle  l e a r n i n g component o f  a view o f  produced  The  3.22  given  far  the  s e t at l e v e l  knowledge.  the  maximum a l l o w a b l e  reinforce  addition,  learning  is  e i g h t . The  were made s t r o n g e r ,  new  through  into  described  learning  succession  times  fed  permitting  for  This  verdicts  then  of the  2.80 were  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  Iterations 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  original  line  necessary that  than  to  learning  The  fact is  viewing  of  that  lines  to  at  this  system  is  the  rendition  of  the  result.  It  is  generated  measures i n d i c a t e  i t  of  generalize  can  one  line.  has  a  that  to  adept  account  information  any  fairly  suggests  for  a representative  enough  ensure that  capable  system i s f o r c e d  system  be  better  s t a g e a l l the  because  behavior over  satisfactorily how  the  the  should  a  stabilized.  that  If  generalization  of  has  gives  automatically  encouraging  adequate.  there  the  note that  the  mimicry  version  set  truly  the  local  is  quite  a  person's  cf l i n e s  available  However, the  precise  then  locally  problem  representative  to  remains set  of  lines.  The is  next  step  to determine  measures  the  rate at  available  results.  For  each  to  points  the  changes  3.4). in  i n the  us  fairly  3.23.  rapid,  and  of  system's a b i l i t y to  i t learns.  There  they a l l give can  look  points,  the  difference  master copy  that  the  we  the  From i t we although  and  this can there  at  tree  last see  set that  is  no  are  roughly  the  imitation  decision  A graph summarizing  Figure  which  iteration  oisclassifications of  in evaluating  mimic  several  consistent  total  number  between  the  of  number  (see T a b l e  3.5),  has  undergone  (see  Table  of  information  is  shown  the  learning  and  seems t o  independent standard  be for  comparison.  Of  course the  real  test  of  the  system  how  well  i t generalizes  o u t l i n e s that  To  test  this  performance  aspect  of  comes when we  i t has  the  never  met  generalization  look  at  before. component  45a  Weakened  1  2  3  verdicts  4  5  L e a r n i n g I t e r a t i o n Number  L e a r n i n g Progress  Figure  3.23  45b Learning  Statistics Number o f  Number o f Changes t o Terminal Stronger Iteration 1 Line  Total Iteration 2 Line  0 2 1 2 0 4 9  6 13 4 4 6 15 48  15 14 2 8 1 13 53  A B C D E F  76 121 34 51 26 113 421  3 0 0 0 0 1 4  8 8 1 2 3 5 27  5 5 2 6 0 12 30  A B C D E F  88 129 35 54 26 124 456  1 0 0 1 0 0 2  1 2 1 0 3 3 10  2 3 1 4 0 4 14  A B C D E F  89 133 35 57 27 127 468  0 0 0 0 0 0 0  1 1 2 1 1 3 9  2 0 0 1 1 1 5  89  0  2  1  Total Iteration 5 Line  A B C D  E F Total  Changed  71 105 . • 30 45 22 99 372  Total Iteration 4 Line  Weaker  Tree Expansions  A B C D E F  Total Iteration 3 Line  Node V e r d i c t s  133 36 58 27 129 472  Table  0  0  1  0 0 0 0 0  0 1 1 1 5  1 0 1 1 5  3.4  45c  Learning Results Number of Points in Outline :line  Original Outline  Learning Master  92 134 37 59 29 131  23 41 19 16 10' 33  A B C D E F  After Learning Iteration 2 3 4 5 1 33 48 19 15 11 36  29 40 19 15 11 34  29 41 19 15 11 33  29 41 19 15 11 33  23 41 19 15 10 33  Table 3.5  Generalization Results  Outline  Original  A B C D E F G H I J K L M N 0 P  92 134 37 59 29 131 308 51 23 123 38 55 27 182 29 51 26  Q  Number of Points In Outline 1/4 Original Learning Iteration 1 2 3 4 5 23 35 9 15 7 33 77 13 6 31 10 14 7 46 7 13 7  . 33 48 19 15 11 36 44 10 5 18 9 13 5 26 6 8 5  29 40 19 15 11 34 39 12 5 15 9 15 5 28 6 9 5  Table 3.6  29 41 19 15 11 33 40 11 8 17 9 15 5 25 5 8 5  29 41 19 15 11 33 40 11 8 15 10 15 5 24 5 8 5  23 41 19 15 10 33 39 11 . 8 16 9 14 4 24 5 8 5  Douglas Method 0.05" 0.0< 16 30 14 13 10 32 38 10 5 19 5 10 6 24 4 5 5  26 35 16 15 10 33 48 10 5 24 9 11 6 32 4 8 5  46  of t h e system  was p r e s e n t e d  iterations, resulting Table and  with  after  a l l the  outlines  o u t l i n e s a r e found  3.6 the  gives  each  i n Figures  t h e number o f p o i n t s  number  of  points  of  the  five  learning  shown i n F i g u r e  3.15. The  3.24  through  3.28,  i n each o u t l i n e  actually  remaining  while  originally  after  each  generalization.  We that  can  the  general  maintained the  s e e t h a t t h e 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  and t h a t  desired  little  change  discouraging  remedy the  since,  stabilized,  learning  look  parameters lengths  (ie.  and t r e e  give  a  more  portions  alternative  is  reasonable  homogeneous second  general while  is  l e a r n i n g at the  is  could  that  probably since  is need  not  to  thresholds, the l e a r n i n g learning  time.  large,  tc  set  reduce the The  last  one and both relatively  t o be g e n e r a l i z e d .  likely  was  open a r e : a l t e r  manually  a  somewhat  learning  the  same  which  the learning  increase  or  cf  flaws  i s generally  angle  re-reduce  rendition,  outlines  especially  manual r e d u c t i o n  there  are l e f t  depth),  t o take i f there  of  alternative  difference  seme  a p a r t i c u l a r case o f the p r e c e d i n g  steps  set  the eye. There  that  the  i s of  catch  to additional  that  well  glaring  This  view o f t h e f a c t  The a c t i o n s  been  some  although  seguence.  making i t more r e p r e s e n t a t i v e ,  offending  are  the  we c a n n o t  the s i t u a t i o n .  minimum/maximum  and  in  are  distortions,  learning  throughout  have  i n t h e number c f p o i n t s  immediately  serious  increased  outlines  there  i n o u t l i n e N) t h a t  with  virtually  the  However,  a l s o a number o f o t h e r  diminish  set  of  the reduction  degree.  (especially are  shapes  make  The much  i t i s not c l e a r where t h e c u r r e n t  be i m p r o v e d  significantly.  I f we  restrict  46a  46b  46c  46d  46e  47  ourselves step  to  this  to the  take  original  i s to  alter  given seme o f  to evaluate  way  learning  method i s t o compare  proposed  by  routines easily  Douglas  reguiEed  subsets  (1972)  involved no  point  distance  in  the  the  set  with  the  outlines  the  columns i n T a b l e  3.6  of  the  o u t l i n e s . There  the  whole, b e t t e r  the  computation  ( a p p r o x i m a t e l y 2.0 seconds). learning  The  It  is  seconds therefore  in  straight-forward  and  were  just  another  values was  are  chosen  tc  for  i t also  to of  method  do CPU  clear  of  3.30  than  will  is  are that  the  glaring  be  avoided.  0.05"  that  earlier  time from  method.  than a s p e c i f i e d  and The  number o f  doubt  them  comparison  0.04"  resulting  respectively  the  the  undergo a  guarantees  generalized.  is little  for  considerations  further  record  means  i t i s a good  global  and  generalizations required  The  is  was  3.29  each  one  thresholds  shown i n F i g u r e s  two  i s the 1.  previous  o u t l i n e s are last  comparison  v e r s i o n . Thus some o f  deviation  of  of  Chapter  p o i n t s , and line  of  methods  a l s o because  effectively  generalized  method w i t h  complete  but  original  encountered  this  system as  s e l e c t i o n of  from t h e  mistakes Using  advantage t h a t  i n the  are  method  f o r convenience,  the  method  performance  other  described  This  not  with  for  whose  transformation.  has  it  obvious  parameters.  generalization  points  specified only  learning  chosen  i n t o the of  the  and  for this  incorporated  selecting  method  o f o u t l i n e s t h e n an  the  Another  g e n e r a l i z a t i o n . , The  It  set  while  points  these  are,  ones.  opposed  t h i s comparison  on  Also,  considerably as  in  less  to  7.5  that  the  method does have some d e f i c i e n c i e s .  learning  method  f o r g e n e r a l i z a t i o n d o e s , however, e n j o y  47a  47b  LEVEL=9  48  an  advantage  being  when i t comes to  generalized  generalization within  the  is  line,  Stylized digitized  done  an  instruction  that  while  remaining  the  each of  were  a l l reduced  the  one  person  that  keeps the  the  docks  T h e s e two  to  the  virtually and  portion an  3.40.  The  thresholds  key  i s because  recognizing  given of 9  this  to  the  patterns  pcint.  the  were  learning  parameters) with were  to be  presented  t o what had  example  to  be  reduced  point,  times  learned.  the  retained  to a  several  been  involves  d o c k s . From pilot,  (Figure  that  the  The  they result  show t h e  may  teach  the  was  in this  case  to r e c o g n i z e  of  two  the  right  models  (see  the angles.  in  (Figure (cn had  (see to  Figure  want 3.35).  separate stabilized line  were  Figures  3.36  generalize 3.38,  outline  cf  a  which i s  shown i n F i g u r e s adjustment  a  Figure  p e r s o n may  original  upper edge o f  versions  was  the  employed  Vancouver waterfront a section  learning  of  generalization  system  of  respective  learning  g i v i n g the  landform  i t e r a t i o n s the  to t h e i r  want a  while another  original  to  generalization  outline depicted  say)  3.34)  the  generalizations  same  the  3.15)  been  were used  identical  of  had  a f t e r four  enlargement of  Figure  were  are  3.32.  docks  3 . 3 7 ) . The  then  numerals  (a s h i p * s  point  This  that  n u m e r a l s 0,1,2,,..,9  adjustment  according  versions and  and  and  removed t o  occasions)  by  arabic  n u m e r a l s 3,4  containing  3.33  the  3.31)  more p r a c t i c a l  coastline  of  digits  appears i n Figure a  essentially  suitable  after  purposes.  lines  extreme example i l l u s t r a t e s  Figure  (with  the  special  versions  (see  component  for  s p e c i a l types of  G  3.39  the  in and  angle  LEVEL=0  A r a b i c Numerals Figure  3.31  48b  L  Reduced Arabic Numerals  LEVEL=8  Figure 3.32  48c  LEVEL=0 DOCKS  A C o a s t l i n e w i t h Docks Figure  3.33  Reduced C o a s t l i n e f o r Learning (docks kept)  LEVEL=8 DQCKS_KEPT  Figure  3.34  Reduced C o a s t l i n e t o r L e a r n i n g  (docks remove  Figure  _EVEL^8 DQCKS_GQNE  3.35  48f  Reduced C o a s t l i n e a f t e r L e a r n i n g (docks  LEVEL=8  kept)  Figure  3.36  Reduced C o a s t l i n e a f t e r Learning (docks removed)  LEVELS  Figure  3.37  48h  O r i g i n a l Vancouver W a t e r f r o n t  LEVELS VRNCOUVER_DOCKS  F i g u r e 3.38  Reduced  LEVEL=8  Vancouver W a t e r f r o n t  (docks  kept)  Fi  § u r e 3-39  Reduced Vancouver W a t e r f r o n t  LEVEL=8  (docks removed)  Figure 3.40  49  3.4  Other.Questions Apart  there  from  the q u e s t i o n s  a r e many o t h e r q u e s t i o n s  system  and  problem  i s t h a t o f measuring  and  selecting  attempts and  answered  within  has  lines  values i s very  along  of  this  assignments o f parameter  the  interesting  "psychology"  mechanism see  lines  is  evidence  oscillation,  One l a r g e l y  such  chains.  between  is  lines initial lengths  Nothing  some  understanding  lines  the  selection  of parameter  A related  affected  very  problem  by  that  and t h e  particular  values. q u e s t i o n t h a t might process.  (Feigenbaum  psychological  forgetting,  cf  the r a t e of l e a r n i n g  learning  of the learning  EPAM-like  of  how  cf  by c o n s i d e r i n g t h e g u a n t i z e d  s e t and t h e a s s i g n m e n t  is  the  untouched  I have made some  as Markov  and d i f f e r e n c e s  attention  transferability  about  the h o m o g e n e i t y o f a s e t  much a h i t o r m i s s a f f a i r .  more  Another  be  experiments.  and a l s o  a representative learning  deserves  asked  can  y e t emerged, however. W i t h o u t  of t h e s i m i l a r i t i e s of  that  a r e a by l o o k i n g a t t h e d i s t r i b u t i o n  l e n g t h s and a n g l e s promising  d i s c u s s e d so f a r ,  representative subsets.  in this  angles  through  t h a t have t e e n  be a s k e d  Since  the  (1963)) we s h o u l d features  i n t e r f e r e n c e and so on.  of  concerns learning expect to  learning  as  50  Chapter 4.0  IV  EVALUATION  Introduction There  are  three  main a s p e c t s  some s i g n i f i c a n c e . T h e s e a r e -an  encoding  -an  of  interactive  and  that  is  graphics lines  generalize  work t h a t  suitable  hierarchically  means t o m a n i p u l a t e  this  may  be  of  well  as  :  scheme  representation  of  generalized  system  that  represented  them  for  lines,  provides in  either  the  the  this  way  manually  or  automatically. -a  system  that  to recognize These  are  related of  my  •1  patterns  summarized  t o p i c s that ethical  a summary and 4  Critical  on  learning  and  chapter  as  investigation. the  chapter  Some  ends  with  to  the  conclusions. Summary  versions can  idea  a  potentially of  be  of a l i n e  a line,  represented  to a whole f a m i l y  a single level  attached  a of to  the  point  is  to  conveniently  attached  notion.  This  generalized  to  related lines. each  point, the  specify  Figures  i s because  a  different  a s i n g l e e n t i t y . Apart  conceptually  i n conveying  sequence of  levels  useful  within  importance of  i n the  with  each  compact, i t a l s o a l l o w s  observed  this  touched  be  possible  in  concerns are  several  only  critically  future  to  referring  by  lines.  deserve  points  being  in  I think  I b e l i e v e the  degree,  performs g e n e r a l i z a t i o n  4.1  elegant For  of  example,  with  representing  the  message o f the  way  frcm  the  enlargement  through  4.3.  line, i t process This  is  50a  w i t h reduced  Detail F i g u r e 4.1  LEVEL - 4  Enlargement of F i g u r e  4.1  w i t h more D e t a i l  Figure  4.2  50c  Enlargement o f F i g u r e 4.2 w i t h more D e t a i l F i g u r e 4.3 LEVEL = 0  51  typical  of  many  c a s e c a n be displayed, scale  the  handled the  and l e v e l  Figure  interactive graphics applications  H.U  window  two  same l i n e  For  l e v e l s attached of the s t r e e t s  points need  on  specifying  that  be s t o r e d  factors  are only  such  the  This  line  that  be is  time. This and  from  the  observed  the f a c t  once. The a c t u a l  as  every  t o determine  to generalize  character  tradeoffs  saving  structures"  are  in  the  of the  cf  course  o f the l i n e s , the  and t h e p a r t i c u l a r  technique  time a l i n e  internal  is  does  have  used  i f a good  the l i n e  just  done  another  point  I t might  generalization  t o the d e s i r e d  beforehand. instance  versus  "display  procedures"  interactive  graphics  system  of  some  each  i f i t i s t o be i n c l u d e d .  generalization  here  that  versions  scheme  degree  way t h e s p e c i f i c needs do n o t have t o be  a l l the  between  a r e adeguate f o r  s h a r e d by s e v e r a l  c h e a p e r and more c o n v e n i e n t , available,  point  be  are involved.  arises  representation  be i n s p e c t e d  to  o f the p o i n t s .  d r a w b a c k s . I t means t h a t must  lines  enlargement  t o each  number o f l e v e l s o f g e n e r a l i z a t i o n , machine r e p r e s e n t a t i o n  the  p a r a m e t e r s and t h e r e l a t i o n s h i p  compactness c f encoding  individual  depends  simply  of display.  representation  The  by  and i n t h i s  every  anticipated  The  relative  the  "display  (Newman  (1971))  argument.  An  generalization interest. storage,  is  another  aspect  c f t h i s work t h a t  I t p r o v i d e s a means o f b r i n g i n g associating  displaying  these  values with  lines  suitable  along  line  i s o f some  i n l i n e s from  the points  at various  for  external  the l i n e s  and  l e v e l s . The m a n i p u l a t i o n c f  ft St.  h^t.  The Enlargement of Street I n t e r s e c t i o n Figure 4.4  52  v a l u e s can screen  of  be  a graphics  methods w i t h if  done m a n u a l l y  the  necessary.  the  system  testing  necessary believe, has  a  the  points  a  to  difficulty. a  do  only  x  For it  can  processed use  of  and  The  more  the  fact that  of  people  light  i s no would the  of  an  into  it to  be  pen  way  be  to  use.  and  had  not  since  would  net  current  coordinates in  many r e a l  presently  through a  in  Baking  this the  does  and  useful  I  blocks  lines. hairs  I but  very  i t s use  much  have tool  not  tetter  o b t a i n e d . However,  s t e p and  flexible  I t has,  to c o r r e c t  of  also  and  mistake  necessary  but  could  a  to change  is  since  stumbling  cross  much  be  any  components  clumsy  within or  in  framework  makes  difficult  system  benefit,  the  intimately  t h i s work s i n c e  initial a  of  i s often  prove  be  correction  for developing  conceptual  overcome  generalization  does r e p r e s e n t  development  often  for  u s e f u l system.  sequentially  would  a shortcoming  would  automatic  However,  knew  the  cf  scheme.  many  and  image on  features  a vehicle  and  I  variety seconds  example, i f one  this  understanding  for  they  although  would  system  but  there  applications. is  since  updated  desirable  p r a c t i c a l and  At p r e s e n t  point  useful  the  as  lacks  structure  these  be  for  a  it  a  within  inconsistencies  value  have t o  hard  of  be  average user.  provision be  of  mainly  part,  i t to  goals,  assigning  by  geographic e d i t t i n g  sound, b a s i c  restricted  else  available  designed  tolerate  or  a rapidly  c a p a b i l i t i e s are  learning  number  could  for  and  for a  results  was  the  terminal  Such  generalization  using  the  potential for  map  generalization.  The a  major emphasis  technique  for  the  i n t h i s work has generalization  been of  map  the  development outlines'  of  which  53  operates  by r e c o g n i z i n g  p e o p l e . The a i m suitable they  of  this  retain  their  views  about  much l e s s d a t a  the s i m i l a r i t y  The  satisfy  t h i s need  but a t  people  have  the  maps  same  widely these  time  differing generalized  is  lines  manually.  fairly  patterns  local  t h e system  be  precisely  trials.  I t i s also able  general  nor  the  as  person,  is  a  need  to  This  set  generalise While  of  I  have  tinkering purpose  little  delicate before of being  taken  easily  at  people  new l i n e s  suggest  recognizing  the performance learn  relatively  c f not having from  doubt any  and  from  to  few  but  mimic  learning  is  not  would would  properly.  holes  representative  not  the  reasonably  i t  a  being  able to to  system  could  homogeneous  setof  not  require  This  as with  the c a s e s ^presented  that  t o do t h i s  instrument working  behaviour  a p p e a r s t o be due t o gaps o r  learn  generalize  the trouble a  to  to  a s e x i s t i n g a n a l y t i c methods  i t s learning sufficiently  satisfactorily lines,  lines  to  constructed  by  i n fact  able  with  to generalize  with  generalize  l i n e s land  out. I t  proficient  types of l i n e s .  to  the learning that are a r e s u l t  enough  was  Experiments  able  within  bears t h i s  almost  reliable  previously  by l e a r n i n g t o mimic t h e u s e r ' s  should  Like  produce  s i t u a t i o n s , which means  o f maps and s i n c e  described  t h a t a program  it.  to  f o r a v a r i e t y of purposes there  system  generalizing  One  storage  is  t o i t by  t h e g e n e r a l i z a t i o n t o a p a r t i c u l a r i n d i v i d u a l ' s wants and  tastes.  in  generalization  r e c o g n i z a b i l i t y . Since  maps may be u s e d  of  t h a t have been t a u g h t  f o r use i n i n t e r a c t i v e g r a p h i c  must r e q u i r e  tailor  patterns  be  worthwhile.  a great  rather  deal of  defeats  the  s u i t e d t o an i n d i v i d u a l ' s r e q u i r e m e n t s .  p o s s i b l e way t o overcome  this difficulty  i s t o have a  basic  54  repertoire occurring that  of  f e a t u r e s . Then t h e  are  specially  application, it  is  learning lines  both i n terms of with  importance  as an  hardware obstacle  for  generalization.  4.2  Future  work  Since  the  new  there  before  are  the  especially Related  to  well a It  that  t o use  this  a  than  a  the  must  requirements.  Perhaps  further one.  various  and  more  this  question  that  has  been  at  thesis i s  investigation such  recognize  area maps,  drastically.  study  criteria  in  technique  One  of  that  p a r t i c u l a r g e n e r a l i z a t i o n a p p r o x i m a t e s the  is  diminish  this  been r e d u c e d  be  that  methods,  useful  has  is  ether  factor will  require  lines  particular  system  a p p l i c a t i o n of  content  there  What a r e  for  current  people perceive  data  this,  generalization.  the  commonly  extra  for qeneralization in this  becomes  i n which  when t h e i r  of  the  with  it  storage  to the  s e v e r a l areas  way  "tune"  costs  technique  technique  concerns the  and  many o f  i s taught  more e x p e n s i v e  processing  decreasing  to  disadvantage  significantly  contain  system  chosen  another  that  outline  dermine original  the  heart  how line?  of  my  investigation.  another techniques each  point  inspected not.  as  of  of pattern  interest  to  in turn  determine was  more l o g i c a l bays,  is  recognition  i s considered  T h i s approach  p e r h a p s he (such  area  whether  taken  and  its  the  simply  docks,  trying  alternative  fcr generalization. Currently immediate  point  should  environment be  removed  f o r c o n v e n i e n c e but  to r e c o g n i z e  inlets,  in  certain features  rocky  shorelines,  or  i t would in  lines  peninsulas.  55  etc.)  and  feature  to  generalize  could  suggestive possible  be  lines  or  so  of  sections  large  such  as  that  that  of  a representative more work must  On  just  completely simplified  i s taken c o u l d  that  feature  whole f e a t u r e  removed  actions  probabilities  the  are  d e p e n d e n t on  i t would be of o u t l i n e  s e t f o r any  done t o  level  there  implemented  improvement  i s exhausted. Apart  values  and  and on  modification  I suspect  to  that  expanded c o u l d 4.3  Which  pattern  from  types  lines  heuristics  also lead changes t o be  of  scheme  in  employed  cf  lines.  done  on  the  potential  for  detail on  in  learning,  the  the  how  parameter  the  the  i n which  the  recognition  improved  particularly  of  obtain  to s i g n i f i c a n t l y way  various  to  i n more  used  the  character  order  its  seeing  few  coastline  d i f f e r e n t types  before  a  tc  indented . In  the  of  maintain the  i s much to be  technique  the  learning  performance.  decision  tree  is  of  my  fruitful.  E t h i c a l Concerns  Approximately work were s u p p o r t e d  half by  of  the  the  papers that  U.S.A.  i t makes me  wonder whether t h e  put,  any,  be  i f  sufficient aspect  other  will  beneficial.  t o c o n v i n c e me that  that  I must c o n s i d e r .  people are  apparently  not  What  This  uses to  This  I should  so  I made use  Military.  because  an  by  g e n e r a l i z a t i o n p e r f o r m a n c e depend the  component m i g h t  to  Columbia)  categorize  replaced  parameters  {e.g., a d e e p l y  learning  Either  according  various  British  a more c o n c r e t e  learning  chosen  northern  be  or  once.  slightly.  possible  currently  the  be  at  do  concerned  disturbs  which  my  alone  other  work but  me  more  about the  me  work i s  fact  disturbs  in  is  is  not i t is that  potential  56  uses  of t h e i r  applications of  work. V e r y  for  application. research might  military  might  be  be. I b e l i e v e  recognition for  be a much and  mention  i n the a n a l y s i s  instance,  of a i r  an o f t e n  more open d i s c u s s i o n  what t h e c o n s e q u e n c e s  t h i s t o be e s s e n t i a l i f r e s e a r c h  cited  of  how  o f t h i s use i s going  to  t o mankind.  Conclusions  It explore serve  a  used  potential  Nowhere have I f o u n d any  espionage  There should  be o f n e t b e n e f i t  in  are the dangers of the  o f work d i s c u s s e d .  t h e d u b i o u s use o f p a t t e r n  photos  4.4  seldom  h a s been  a p r i n c i p a l aim o f mine i n d o i n g  techniques  p e o p l e . The  for  problem  i n t e r a c t i v e graphics computer  system  i n d i v i d u a l ' s needs.  making  the  computer  of g e n e r a l i z i n g  s i t u a t i o n s i s one a  certain  I believe  of  i n t e r a c t i v e graphics  can  be f r u i t f u l  and  in providing  amount  map  a useful  outlines  area of  which  flexible  recognition enough  the  to  t o o l to for  to  use of an  application  to t h i s  systems.  work  reguires  tailoring  I have shown t h a t pattern  this  problem  ' 57  JIBlICGBaPHX  Attneave,  Fred  (1954),  "Informational  Perception",  Aspects  Psychological  of  Review,  Visual  Volume  61,  pp183-193.  Blum,  H.  (1964),  "A  Transformation  Descriptors  of  for  Shape",  Symposium  t h e P e r c e p t i o n o f S p e e c h and Dunn H e i a n t  D e e k e r , Gordon  (1970),  (eds.),  Science,  M.Sc.  Graphics  Thesis,  University  Visual  New  on Models f o r Form,  Wather-  pp362-380.  "Interactive  Problem",  Extracting  of  and  Department  a  Planning  of  Computer  A l b e r t a (Edmonton),  (Fall  1970).  D e e k e r , G. S Penny,  J.P.  ( 1 9 7 2 ) , "Cn  Retrieval",  Douglas,  David  (1972),  INFOS,  Interactive  Volume 10, #1,  Personal  Map  Storage  and  pp6 2-74.  communication  -  not  yet  published.  Feder,  Jerome  (1968),  "Languages  Information  cf  Encoded  Line  and C o n t r o l , Volume 13,  Patterns", pp230-244.  58  Feigenbaum,  Edward  (1963),  Behavior", Feldman  Freeman, H e r b e r t  "The S i m u l a t i o n o f V e r b a l L e a r n i n g  Computers and T h o u g h t , Feigenbaum  (eds.),  pp297-309.  (1961), "On t h e E n c o d i n g  Configurations", Electronic  Freeman,  Herbert  of a r b i t r a r y  Transactions  C o m p u t e r s , EC-10,  (1971), " T e c h n i q u e s  analysis  of  for  of  Hershey,  T.  ( 1 9 6 3 ) , "A P l o t t i n g Report,  Jarvis,  Boundary  K e a t e s , John  S.  on  the  Digital  Computer  Arbitrary  Plane  ilectroni.es  17, pp421-432.  c f Maps on a CBT P r i n t e r " ,  NWL  #1844.  C.L. ( 1 9 7 1 ) , "A Method  Volume  JBE  pp260-268.  Chain-Encoded  Volume  Geometric  the  Curves", Proceedings of the N a t i o n a l Conference,  and  Data",  3, #2,  (1972), Maps",  For F i t t i n g  Polygons  The A u s t r a l i a n  to  Computer  Figure Journal,  pp50-54.  "Symbols  and  International  Meaning Yearbook  in  Topographic  f o r Cartography,  pp168-180.  Koeman, C. S van d e r Weiden, F. 1. Computation  "The  Application  and Drawing I n s t r u m e n t s  Generalization", pp47-49.  (1970) ,  of  to S t r u c t u r a l  C a r t o g r a p h i c J j o u r n a l , Volume  7,  59  Koffka  K.  (1935),  Pringiglgs  B r a c e , New  Kolers,  P.A.  &  Gestalt  Psycholojgj,  Harccurt  York.  Eden, M.  Studies  of  (eds.)  in  living  (1968), and  Recognizing Patterns -  Automatic  S_ysterns,  HIT  Press.  Lang,  T.  (1969),  "Rules  f o r Robot Draughtsmen", G e o g r a p h i c a l  M a g a z i n e , Volume  X L I I , #1,  pp55-51.  i  Licklider,  J.C.R.  (196 0) ,  from  Revolution, Hall  Miller,  W.F.  S Shaw A.C.  Volume  O.M.  &  Zenon  Ugo  Pylyshyn  (1968); " L i n g u i s t i c - A Survey",  33 p a r t  1,  Voskuil,  Generalization",  Montanari,  W.  on  the  (ed.),  Computer Prentice-  (1970).  Processing  Miller,  Perspectives  Methods i n  Picture  P r o c e e d i n g s o f the F J C C ,  pp279-290.  R.J.  (1964),  "Thematic-Map  G e o g r a p h i c a l Review,  pp13-19.  ( 1 9 6 8 ) , "A Method f o r O b t a i n i n g S k e l e t o n s U s i n g a Quasi-Euclidean Association m,  Distance",  Journal  f o r Computing M a c h i n e r y ,  pp600-624.  of Volume  the 11,  60  Montanari,  Ogo  (1970),  "A  Note  Approximation  to  Communications Machinery,  Newman, W i l l i a m  M. of  N.  the  the A s s o c i a t i o n  f o r Computing  13,  #10,  #1,  John  (1970),  "Web  Procedures", for  Planar  Systems,  McGraw  A.H.  Volume  by  Representation Their  T.A. 1  S  Schwartz, F u n c t i o n of Journal  11,  #2,  C.B.  Wiley S  for  Computing  pp119-123.  of  J3rd  Sons.  (1956), "Speed  Mode  of  Skeletons",  (1969), f i g m e n t s of Cartography  edition}., John  Ryan,  Description",  A  (1967), "Computer  S S a l e , R.D.  Hill.  Picture  Communications of the A s s o c i a t i o n  Robinson,  Trainable  70^_138, Computer S c i e n c e C e n t e r ,  Regions  i!f^lLiil§IIi  Machinery,  F o u n d a t i o n s of  of Maryland.  J . S R o s e n f e l d , A.  Communications  Computing  Grammars and  Report  University  pp41-47.  pp651-660.  Classifying  Technical  Pfaltz,  Contour",  Association  14,  Polygonal  Digital  (1965) , L e a r n i n g M a c h i n e s ^ Pattern  Pfaltz,  of  Volume  Minimal length a  (1971), " D i s p l a y  Volume  Nilsson,  on  c f P e r c e p t i o n as a  Representation",  o f P s y c h o l o g y , Volume 69,  American  pp60-69.  61  Seeley,  D.A.R.  (1970),  "The  Pattern  Use  of  Detection  Finite-State  with  Electroencephalograph^  of  Application  Data",  Department o f I n d u s t r i a l  Models f o r  PhE.  Engineering,  to  Thesis,  University  Toronto.  Sherman, R, S E r n s t ,  G.W.  Other  (1969), " L e a r n i n g P a t t e r n s i n Terms o f  Patterns",  Pattern  pp301-313, Pergamon  Skiansky, J . , Chazen, Length  R.L.  8  Press.  Hansen,  Polygons  R e c o g n i t i o n , Volume 1,  B.J.  of Digitized  (1972),  "Minimum  Silhouettes",  IEEE  T r a n s a c t i o n s on C o m p u t e r s , C-21, #3, pp260-268.  S l a g l e J.R. S L e e , R.C.T. Searching  (1971), to  "Application  Sequential  Pattern  Communications o f the A s s o c i a t i o n Machinery,  Srnka,  Erhart  (1970),  V.I.  "The  Analytic  in  Tree  Recognition", f o r Computing  f o r Cartography,  (1970),  "Application  Generalization  of  Solution  Cartography",  Yeartook  Yearbook  Game  Volume 3 4 , #2, pp163-170.  Generalization  Sukhov,  of  Map  of  Regular  International  pp48-62.  Information  Contents",  f o rCartography,  of  pp41-47.  Theory i n  International  62  Topfer,  F.  S  Pillewizer,  Selection",  W.  The  ,(1966),  "The  Principles  Cartographic Journal,  #3,  of  pp10-  16.  Uhr,  L.  &  Vossler, that  C.  (1963), "A  Generates,  Weiner,  Norbert of  Zahn,  C.T.  (eds.),  (1960);  "A  and T h o u g h t ,  its  own  Feigenbaum  and  pp251-268.  S c i e n c e , Volume  Formal  Patterns", Conference  Adjusts  "Some M o r a l and T e c h n i c a l  Automation",  (1969),  R e c o g n i t i o n Program  E v a l u a t e s , and  O p e r a t o r s " , Computers Eeldman  Pattern  Description  Proceedings on  Artificial  of  131,  Consequences pp1355-1358.  for  2-Dimensicnal  the  International  Intelligence,  Washington  1969.  Zahn, C.T.  8 Roskies, Plane  R.Z.  (1972),  Closed  Compujters,  C-21,  "Fourier  Curves", #3,  IEEE  pp269-281.  Descriptors Transactions  for on  

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}]}"
                            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:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0052003/manifest

Comment

Related Items