Exhibit 2007
`Bradium Technologies LLC - patent owner
`Microsoft Corporation - petitioner
`IPR2016-00449
`1
`
`

`
`2
`
`

`
`GEOGRAPHICAL INFORMATION SYSTEMS
`
`3
`
`

`
`VOLUME 2 : APPLICATIONS
`
`GEOGRAPHICAL
`
`INFORMATION SYSTEMS
`
`PRINCIPLES AND APPLICATIONS
`
`EDITED BY
`
`DAVIDJMAGUIRE,
`
`MICHAELFGOODCHILD
`
`AND
`
`DAVID W RHIND
`
`>l > Longman
`::: Scientific&
`1 Technical
`Copublished in the United States and Canada with
`John Wiley & Sons, Inc., New York
`
`4
`
`

`
`Lungman Scientific and Technical,
`Longman Group UK Ltd
`Longman House. Burnt Mill, Harlow,
`Essex CM20 ZJE, England
`and Associated Companies I/zmuglmut the world.
`copublishred in the United States and Canada with
`John Wiley & Sons, Inc, 605 T}zirdAvenue, New York,
`NY I 0158
`
`© Longman Group UK Limited 1991
`
`All rights reserved; no part of this publication may be
`reproduced, stored in a retrieval system, or transmitted in
`any form or by any means, electronic, mechanical,
`photocopying, recording, or otherwise without either the
`prior written permission of the Publishers or a licence
`permitting restricted copying in the United Kingdom
`issued by the Copyright Licensing Agency Ltd, 90
`Totrcnham Court Road. London WJP 9HE.
`Trademarks
`Throughout this book trademarked names are used.
`Rather than put a trademark symbol in every occurrence
`ofa trademarked name, we state that we are using the
`nnrnes only in an editorial fashion and to the benefit of the
`trademark owner with no intention of infringement of the
`trademarks
`
`First published 1991
`
`British Library Cataloguing in Publication Data
`Maguire, David J.
`Geographical information systems: Principles and
`applications
`I. Title
`II. Goodchildc Michael F.
`III. Rhind, David W.
`910.901
`
`ISBN 0-582-05661-6
`
`Library of Congress Calaloging—in-Publication Data
`Maguirei D. J. (David J.)
`Geographical information systems / by D. J. Maguirc.
`Michael 1-‘. Goodchild, and David W. Rhind.
`p.
`cm.
`Includes bibliographical references and index.
`Contents: v. 1. Principles -v. 2. Applications.
`ISBN 0-470-21789-8
`1. Geographical information systems.
`I. Goodchild, Michael F.
`II. Rhind,
`David.
`111‘ Title.
`G70.2.M354
`1991
`9l(]’.285 - c|c20
`
`91-3724
`CIP
`
`Set in Great Britain
`
`Printed and Bound in Great Britain at the Bath Press, Avon
`
`5
`
`

`
`Dedicated to the memory of
`
`DAVID S SIMONETT
`
`1926-90
`
`David Simonett was born in Australia in 1926. After earning a Doctorate at the
`University ofSydney, he became a leadingpioneer in thefield of Remote Sensing,
`holdingfaeulty positions at the University of Kansas, the University ofSydney and
`the University of California, Santa Barbara. He was director of land use applications
`at Earth Satellite Corp from 1972 to 1975.
`
`As Chair at Santa Barbarafrom 1975, he was able to build one of the foremost
`Geography programs in the US, culminating in 1988 with the establishment of the
`National Center for Geographic Information and Analysis. The Santa Barbara site
`of the Center was renamed the David Simonett (Ienterfor Spatial Analysis in 1990 in
`recognition of his role in its creation. He received the Honours A wardfrom the
`Association ofAmerican Geographers and the Victoria Medalfrom the Royal
`Geographical Society.
`
`David Simonett lost a courageous fight against cancer on December 22, 1990 in
`the course of the preparation of his contribution to this book. The editors dedicate
`this book to his memory and to the outstanding role he has played in the
`development of the field of Geographical Information Systems.
`
`6
`
`

`
`0
`
`VOLUME 1
`
`:
`
`PRINCIPLES
`
`Preface
`List of contributors
`Acknowledgements
`
`Section I Overview
`
`Introduction
`DJMaguire, M FGOodchz'Zd and D W Rhind
`
`1. An overview and definition of GIS
`D J Maguire
`
`2. The history of GIS
`J T Cappock and D W Rhirzd
`
`3. The technological setting of GIS
`M F Goodchila’
`
`4. The commercial setting of GIS
`J Dangermond
`
`5. The government setting of GIS in the United Kingdom
`R Charley and R Buxton
`
`6. The academic setting of GIS
`D I Unwm
`
`7. The organizational h0II1C for GIS in the scientific
`professional community
`I L Morrison
`
`8. A critique of GIS
`R TAangeenbrug
`
`Section 11 Principles
`
`Introduction
`M F Goodchild, D WRhind and D J Maguire
`
`xiii
`xvii
`xxvii
`
`3-7
`
`9-20
`
`21-43
`
`45-54
`
`55-65
`
`67-79
`
`81-90
`
`91-100
`
`101-7
`
`111-l7
`
`vii
`
`7
`
`

`
`VOLUME1
`
`:
`
`PRINCIPLES
`
`(a) Nature of spatial data
`9.
`
`Concepts of space and geographical data
`A C Gatrell
`
`10.
`
`ll.
`
`12.
`
`13.
`
`14.
`
`(b)
`15.
`
`16.
`
`17.
`
`Coordinate systems and map projections for GIS
`D H Malirzg
`
`Language issues for GIS
`A UFrank and D M Mark
`
`The error component in spatial data
`N R Chrisman
`
`Spatial data sources and data problems
`P F Fisher
`
`GIS and remote sensing
`F W Davis and D S Simonett
`
`Digital representation
`
`Computer systems and low-level data structures for GIS
`Wm R Franklin
`
`High—leve1 spatial data structures for GIS
`M J Egenhofer and J R Herring
`
`GIS data capture hardware and software
`M J Jackson and P A Woodsfora’
`
`119-34
`
`135-46
`
`147-63
`
`165-74
`
`175-89
`
`191-213
`
`215-25
`
`227-37
`
`239-49
`
`viii
`
`8
`
`

`
`VOLUME1
`
`:
`
`PRINCIPLES
`
`18.
`
`1‘).
`
`20.
`
`Database management systems
`R G Henley
`
`Digital terrain modelling
`R Weibel and M Heller
`
`Three-dimensional GIS
`J FRaper and B Kelk
`
`Functional issues
`
`. The functionality of GIS
`D J Maguire and J Dangermond
`
`. Information integration and GIS
`I D H Shepherd
`
`. Cartographic modelling
`C D Tomlin
`
`. Spatial data integration
`R Flowerdew
`
`251-67
`
`269-97
`
`299-317
`
`319-35
`
`337-60
`
`361-74
`
`375-87
`
`. Developing appropriate spatial analysis methods for GIS
`S Openshaw
`
`389-402
`
`. Spatial decision support systems
`P J Densham
`
`. Knowledge—based approaches in GIS
`T R Smith and Je Yicmg
`
`403-12
`
`413-25
`
`9
`
`

`
`VOLUME1
`
`:
`
`PRINCIPLES
`
`(cl) Display issues
`28. Visualization
`B P Butter;/ield and WA Mackaness
`
`29. Computer name placement
`H Freeman
`
`30. Generalization of spatial databases
`J—C Muller
`
`(e) Operational issues
`
`31. GIS specification, evaluation and implementation
`A L Clarke
`
`32. Legal aspects of GIS
`E F Epstein
`
`33. Managing an operational GIS: the UK National On-Line
`Manpower Information System (NOMIS)
`M J Blakemore
`
`34. Spatial data exchange and standardization
`S C Guptill
`
`Consolidated bibliography
`List of acronyms
`'
`Author index
`Subject index
`
`427-43
`
`445-56
`
`457-75
`
`477-88
`
`489-502
`
`503-13
`
`515-30
`
`531-591
`593-5 98
`599-613
`615-649
`
`10
`
`

`
`VOLUME2
`
`: APPLICATIONS
`
`Preface
`List of contributors
`A cknowledgements
`
`Section III Applications
`
`Introduction
`
`D WRhind, D J Maguire and M F Goodcliild
`
`(a)
`35 .
`
`36.
`
`37.
`
`38.
`
`National and international GIS programmes
`
`A USGS perspective on GIS
`L E Starr and K EAnders0n
`
`Development of GlS—related activities at the
`Ordnance Survey
`M Sawton
`
`National GIS programmes in Sweden
`L Ottoson and B Rystedt
`
`The development of GIS in Japan
`5 Kubo
`
`. Land and Geographical Information Systems in Australia
`J FO’Callaghan and B J Garner
`
`40.
`
`GIS and developing nations
`D R F Taylor
`
`(b)
`
`Socio-economic applications
`
`. Land information systems
`P F Dale
`
`42.
`
`43.
`
`44.
`
`45.
`
`GIS and utilities
`R P Mahoney
`
`Car navigation systems
`M White
`
`Counting the people: the role of GIS
`1) W Rhind
`
`GIS and market analysis
`J R Beaumont
`
`xiii
`xvzz
`xxvii
`
`11-22
`
`23-38
`
`39-46
`
`47-56
`
`57-70
`
`71-84
`
`vi
`
`11
`
`

`
`VOLUMEZ : APPLICATIONS
`
`(c) Environmentalapplications
`
`46. Soil information systems
`P A Burrough
`
`47. Integration of geoscientific data using GIS
`G FBOnham—Carter
`
`48. Multisource. multinational environmental GIS: lessons
`learnt from CORINE
`H M Moimsey.
`49. Environmental databases and GIS
`J R G Towrisllcnd
`
`50. Global databases and their implications for GIS
`D M Clark, D A Hastings and]! Kmeman
`
`(d) Management applications
`
`51. GIS and public policy
`H W Calkins
`
`52. Urban GIS applications
`R Parrott and F P Stutz
`
`53. Land resource information systems
`K C Siderelis
`
`54. Land management applications of GIS in the state of
`Minnesota
`A Robinette
`
`55. GIS in island resource planning: a case study in map
`analysis
`J K Berry
`
`56. Integrated planning information systems
`D J Coweri and W L Shirley
`
`Section IV Epilogue
`
`Epilogue
`D W Rhmd, M FG00dchild and D J Magulre
`
`Consolidated bibliography
`List of acronyms
`Author index
`Subject index
`
`153-69
`
`171-84
`
`185-200
`
`201-16
`
`217-31
`
`233-45
`
`247-60
`
`261-73
`
`275-83
`
`285-95
`
`297-310
`
`3 13-27
`
`329-389
`391 -396
`397-411
`413-447
`
`xii
`
`12
`
`

`
`CAR NAVIGATION SYSTEMS
`
`M WHITE
`
`Automobile navigation is a demanding application of digital maps and appears
`likely to become a common and economically important one. A few systems are
`commercially available and many prototypes exist. These systems determine location
`using wheel rotation sensors, solid state compasses, inertial devices (gyros and other
`novel devices), radio location or some combination of them. Requirements of the
`source maps depend on the methods used and the user interface, as well as on
`functions performed in addition to location determination (such as map display,
`verbal directions, pathfinding and destination finding by address or landmark).
`Typical map requirements for particular systems include positional accuracy to the
`order ofa car length, detailed street classification, turn restriction data and
`topological encoding. Creating such digital maps to support navigation is a daunting
`task. At the time of writing, there are severalpilo/projects, just afew commercial
`operations and some fledgling consortia which have as their mission the production
`of digital m.aps for navigation or the promulgation ofslandards for such maps. All
`systems require faster retrieval than (71.? systems have typically provided.
`Applicntions using navigation systems include experimental traffic systems, such as
`trafflc congestion reporting and ‘sign-post’ transmitters and receivers for
`communicating with on—board navigation systems.
`
`INTRODUCTION
`
`The automobile is becoming a much richer
`electronic environment for the driver. On—board
`computers, cellular telephones and vehicle
`navigation are already available, and real—time
`traffic information and route guidance have been
`demonstrated. The market for factory—installed
`systems appears to be huge. In Japan, Nissan has
`been selling more than 1000 systems per month as
`an option on the Nissan Cedric. This option is a
`combination of navigation system and television
`(which can only be operated with the vehicle
`stopped). In Germany, Bosch began to sell the
`Travelpilot in 1989. In the United States, Etak sold
`2000 Navigators over a period of two years. Because
`electronics are pervading the automobile, a factory-
`installed navigation option will probably become
`inexpensive, perhaps less than US 5500. As a
`consequence, demand for and use of digital map
`
`data will grow. Market analysts have estimated that
`sales of navigation systems will grow from US $5
`million in 1990 to US $100 million in 1994 (Frost &
`Sullivan 1989).
`Car navigation uses maps intensively. The map
`must provide information for:
`
`0
`
`0
`
`0
`
`determining and maintaining the location of the
`vehicle in relation to features represented on
`the map;
`
`displaying a map graphically or generating
`routing instructions in text or voice;
`
`linking effectively with infrastructure.
`
`This chapter reviews the current ‘state of the
`art’ of digital mapping as regards vehicle navigation
`and, since it is still in its infancy, some speculations
`are made about likely future developments. The
`infancy of the technology is reflected in the meagre
`
`13
`
`

`
`M White
`
`
`
`Fig. 43.2 The Honda Gyrocator screen (courtesy author).
`
`purchases the vehicle. In J apan, the Toyota Crown
`and the Nissan Cedric have offered factory—installed
`navigation options since 1987 and 1989 respectively.
`'l‘he Etak, Bosch and Nissan systems use dead
`reckoning and map matching (explained below) but
`the Toyota system uses only dead reckoning. The
`map matching systems require topologically
`encoded digital maps, whereas the Toyota system
`uses bit—mappcd images of paper maps (see Plate
`43.1 and Figs. 43.1 and 43.2)
`
`
`
`
`
`Fig. 43.1 The Nissan Cedric screen (courtesy
`author).
`
`In addition, there are several experimental
`systems and ‘concept cars’ either demonstrating or
`‘mocking up’ navigation systems. In an auto show in
`Japan in early 1990, more than a dozen
`
`supply of prior research considering the subject and
`directly related cartography (Petchenik 1989).
`Marine navigation is not included in this discussion,
`It has similar requirements and applications and,
`indeed, was the origin and inspiration for much of
`the current vehicle navigation technology.
`However. it differs in many ways from land-based
`vehicle navigation and warrants separate discussion.
`The following sections discuss vehicle
`navigation systems and methods already in use and
`how information is displayed graphically, reported
`textually or by voice. Then applications such as
`finding dcstinations and pathfinding are considered.
`Finally, there is a review of the essential
`characteristics of digital maps, in so far as
`navigation and its related functions are concerned.
`From this, it will become evident that navigation
`and related applications require a topologically
`encoded and seamless database, as well as very fast
`data retrieval.
`
`NAVIGATION
`
`There are only a few vehicle navigation systems
`commercially available at the time of writing (mid-
`l990). In the United States, the Etak Navigator has
`been available since 1985. The Bosch Travclpilot, a
`derivative of the Etak Navigator, became available
`in Germany in 1989. Both of these systems are
`‘after—market’ devices, that is, they are installed
`after manufacture and usually after the end—user
`
`‘I16
`
`14
`
`

`
`Car Navigation Systems
`
`fl\,¢«"”‘
`
`Fig. 43.3 The Autoguide screen (courtesy Department of Transport).
`
`manufacturers showed such concept cars. This
`indicates a strong interest in navigation and, by
`implication, maps for navigation. Examples of
`experimental systems include the Philips CARIN
`(Thoone 1987), Clarion NAVI and the UK
`Autoguide (Catling and Belcher 1989). CARIN and
`Autoguide present stylized graphic instructions
`representing the upcoming intersection to the driver
`(see Fig. 43.3). Only the general principles on which
`such systems work are known: all the current
`vendors of navigation systems regard their software
`and data storage methodology as proprietary and,
`accordingly, do not reveal details. This is
`unsurprising because navigation has pushed forward
`the frontier of map access technology: typically, on-
`board computers are much less powerful
`computationally and contain less copious RAM
`than ‘normal’ GIS require and, at the same time,
`demand a faster response rate than available GIS
`offer. In addition, navigation algorithms and their
`implementation have involved substantial
`expenditure. The commercial stakes are high and,
`accordingly, secrecy prevails on the internal details
`of each vendors offerings.
`
`POSITION DETERMINATION
`
`Navigation includes determination of position as
`well as guidance toward a destination. There are
`three essentially different technologies used for
`position determination. These are dead reckoning,
`radio location and proximity beacon detection.
`They can be used alone or in combination.
`Destination finding and guidance towards the
`destination have various quite different user
`interfaces.
`
`Dead reckoning and radio location
`
`Dead Reckoning (DR) is the process of computing
`an updated position from three inputs: details of a
`prior position; the distance travelled from the prior
`position; and the heading travelled since that prior
`position. The Etak Navigator, Bosch Travelpilot
`and Nissan Cedric all use DR. Figure 43.4 illustrates
`dead reckoning. To measure the distance travelled,
`all three use sensors mounted on the wheels. Other
`systems have tried to use the vehicle’s odometer but
`this is much less accurate.
`
`15
`
`

`
`M White
`
`7|
`
`.---P""
`
`4'0
`
`Fig. 43.4 Dead reckoning — computing a new
`position from heading (h) and distance (d).
`
`For determining the heading, two
`measurements are taken. An absolute heading
`estimate is made using a solid-state compass (e.g.
`sec Phillips 1987) and a relative heading is
`computed from the wheel sensor measurements. A
`solid state compass (i.e. a two-axis magnetometer)
`measures two components of the ambient magnetic
`field; from this the horizontal component of the
`earth’s magnetic field is computed. There are many
`physical considerations involved such as the
`magnetic flux focusing effect of the steel in the
`vehicle and the local magnetic declination.
`Ilowevcr, all mapping considerations eventually
`come down to using the approximate position of the
`vehicle, a model of the earth’s magnetic field and
`the measured magnetic field. An important
`consideration for in—vehicle applications is dip
`angle, the angle that the plane of the compass
`makes with the earth’s magnetic field vector. The
`earth’s magnetic field is horizontal only at the
`magnetic equator, which coincides approximately
`with the geographical equator. So the compass
`measures the magnetic field vector projected on to
`its own plane. While this is normally close to
`horizontal, local variations in ground slope caused
`by hills and the road crown may amount to several
`degrees and affect the compass/magnetic field
`relationship accordingly. Computation of the
`heading from compass measurements must take all
`these cffects into consideration.
`The difference in the distance travelled on two
`opposing wheels depends on the change in heading.
`When travelling straight ahead (i.e. without heading
`change), the two wheels travel the same distance.
`When turning, the outside wheel travels further
`
`than does that on the inside of the curve. Thus
`wheel sensor readings yield relative heading
`information. Again many physical considerations
`come into play, including wheel base,
`circumference, radius of curvature of the turn,
`steering geometry and wheel slip. Taking all these
`factors into account, however, a new heading can be
`computed from the prior heading and the difference
`in distance travelled by the two wheels.
`Other sensors are under development or have
`been demonstrated in experimental systems. These
`include a gyro turning rate sensor. a vibrating rod
`turning rate sensor, an inclinometer, a GPS (Global
`Positioning System) receiver, a LORAN—C receiver
`and an optical speed sensor.
`A gyroscope (more commonly a ‘gyro’) is a
`spinning mass and the vehicle’s turning rate is
`measured indirectly by measuring forces resulting
`from the conservation of momentum; such forces
`can be experienced by holding a spinning bicycle
`wheel off the ground and turning it. Large gyros are
`used in inertial navigation systems common on
`board ships or aircraft. The vibrating rod sensors
`also operate on conservation of momentum. An
`inclinometer measures the angle of inclination of a
`stationary (or, more generally, a non-accelerating)
`vehicle and may be used to remove the effects of dip
`angle on the compass measurement as well as
`effects of hills on distance travelled. Any
`acceleration experienced affects the inclinometer so
`this must also be considered. As a group, the gyro,
`vibrating rod and inclinometer are all inertial
`sensors: they depend on the physics of momentum
`and inertia for their operation. For a survey of such
`inertial navigation sensors, see Smith 0986).
`CPS and LORAN«C are radio location
`
`systems. These radio location sensors are not used
`in dead reckoning. Instead they provide position
`‘fixes’ that are independent of the prior position.
`They both operate by an on—board receiver and
`computer comparing signals from multiple
`transmitters and determining receiver location from
`known transmitter positions and signal propagation
`times. The LORAN—C transmitters are based on the
`ground and the G PS are on a constellation of
`satellites in orbit. GPS will cover the entire globe
`when the satellite constellation is completed.
`French (1986) provides an overview of radio
`location systems.
`Compass and radio location sensors are
`‘absolute‘ sensors; in contrast, wheel sensors and
`
`16
`
`16
`
`

`
`gyros are ‘relative’ sensors. Relative sensors give
`change information and absolute sensors provide
`information with respect to the earth itself. All
`sensors, however, suffer characteristic defects.
`Wheel sensors and gyros have noise and bias.
`Magnetic compasses measure magnetic anomalies
`as well as the earth’s magnetic field. Radio location
`(GPS and LORAN) signals are distorted or blocked
`in highly urbanized areas. Manifestly, the sensor
`characteristics are important in assessing the
`accuracy of the estimated position. In addition,
`however, combining sensors can yield good results
`even when one sensor is noisy or fails entirely. The
`Etak method of computing heading. using both a
`compass and differential whccl sensor
`measurement, is an example in which the absolute
`sensor (the compass) suffers no accumulation of
`error and the relative sensor (the differential
`odomctcr) is unaffected by magnetic anomalies —
`yielding a combined result that is rarely erroneous
`(Honey, Milnes and Zavoli W88).
`Despite such accurate and resilient methods of
`deriving heading, the accuracy of a dead reckoned
`position still also depends on the accuracy of
`location of the prior position. The ineluctable errors
`in sensors lead to accumulated error in DR position.
`In practice, DR alone is insufficient for navigation
`since the accumulated error will eventually exceed a
`threshold of usefulness. So occasional fixes are
`needed, achieved either by human intervention,
`radio location or map matching. The first of these is
`tircsomc and assumes accuracy on the part of the
`user; the third method is discussed in detail below,
`Radio location, however, has characteristic errors
`that are quite different to those already discussed.
`These errors do not accumulate over time or
`distance. Instead, signals are typically received
`clearly and the error level is the characteristic
`iriinimum or, altcrn atively, there is no position
`information available. It is, however, possible to
`dead reckon between radio fixes or, as Iitak has
`done, use radio location (in this case LORAN—C) as
`just another sensor to be considered in location
`determination.
`
`Map matching
`
`Map matching is used to remove accumulated error
`from dead reckoning. The path travelled is
`determined by dead reckoning or radio location and
`
`Car Navigation Systems
`
`integrating this with roads and intersections
`constitutes map matching (see Fig. 43.5). Dead
`reckoning with map matching is like navigation with
`absolute sensors in that the error in estimated
`position does not continue to grow (as it does with
`use of dead reckoning alone), It differs in that, once
`lost, the map matching algorithm is unlikely to
`recover; absolute sensors, on the other hand, may
`fail for a time or region but, outside that period or
`region, they have their usual error characteristics.
`
`
`
`Fig. 43.5 Map matching — identifying a DR path
`(dashed line) with streets on the map.
`
`By way of an example, one would eventually
`accumulate significant error using only DR while
`wandering along city streets. Through comparing
`the DR path to the map, however, the navigation
`algorithm can eliminate errors that accumulate from
`sensor noisc. Etak pioneered the map matching
`approach (see Honey er al. 1989) for the Navigator.
`The Bosch Travclpilot uses the same approach and
`the Nissan Cedric uses a similar map matching
`method. Such map matching depends on the driver
`staying mainly on the roads; it is inappropriate for
`automatic guidance of a vehicle. In this approach,
`heading as well as position is determined as an
`output of map matching and is used for orienting
`the map displayed to the driver. Experience
`indicates that the impression given by a map display
`with a slightly ‘wrong’ orientation is that the
`computer is lost or will be soon — somewhat like the
`impression of a misaligned street name on a printed
`map. For this reason, map matching methods are
`used to orient and position the display even for
`absolute location methods, such as radio location.
`Other navigation approaches that have been
`
`tried require extensive infrastructure, such as
`
`17
`
`

`
`M White
`
`bcacons mounted on traffic signal standards. ALI/
`SCOUT and Autoguide (Catling and Belcher 1989)
`are examples of such systems. Such approaches can
`also be co upled with broadcast traffic information.
`In Japan, the Advanced Mobile Traffic Information
`and Coinmunication System (AMTICS) project was
`a test of such a concept (Tsuzawa and Okamoto
`1989). The PATHFINDER project in the Los
`Angeles region is intended to gather information
`about alternative routes drivers select when
`provided with traffic congestion information
`(Wasielewski 1988).
`
`Display and report
`
`All of the commercially available systems display
`map and vehicle location information graphically on
`a dash—inounted CRT. Some work has been done to
`present instructions by voice, but this approach is
`still in early development stages. Regardless of the
`method, safety is paramount. Map displays in this
`context are a dashboard instrument and must
`provide the needed information at a glance and
`must not distract the driver. When audio systems
`become available, they will also be required to
`facilitate driving, but not distract the driver’s
`attention. As a result, the human interface must
`conform to dashboard instrumentation design
`guidelines. For visual displays, this includes letter
`and symbol sizes in terms of subtended angle for the
`driver and readability at a glance. In the case of
`audio output, sounds must be non-distracting and
`easily understood.
`So far as map displays in cars are concerned,
`heading-up orientation (i.e. displaying the map so
`that ‘up’ on the display is ‘ahead’ on the ground and
`hence left and right on the display show features
`that are left and right of the vehicle respectively)
`makes the display much simpler to understand and
`read at a glance. I11 the Etak Navigator‘ and Bosch
`Travelpilot, the display is heading up with some
`hysteresis in the heading adjustment to avoid a
`‘jumpy’ display. The Nissan Cedric permits display
`at only the four cardinal headings and operates in a
`‘near heading up’ mode. In addition, more
`generalized views provided through smaller scale
`map presentations are also quite helpful to a driver
`for choosing routes or just learning context. All
`commercially available systems provide generalized
`views. For a map to be readable at a glance, very
`
`I euuvuwnr ‘
`
`i
`
`I BMLPUNKT
`
`Fig. 43.6 Etak map displays at three scales
`showing few feature labels (courtesy author).
`
`little annotation is possible. All three of the systems
`mentioned show only four or five feature labels at
`one time. Figure 43.6 shows three displays from the
`Travel pilot at various scales, each showing only a
`few labels. The labels shown were chosen by an
`algorithm that favours more important streets, the
`selected destination street and the street on which
`
`the ear is currently placed.
`
`1 8
`
`18
`
`

`
`GUIDANCE TOWARDS A DESTINATION
`
`A primary use of navigation systems is in finding the
`location of destinations, usually specified by street
`address but also by street intersection or major
`landmark, and then finding a way to proceed to the
`destination.
`
`Destination finding
`
`To find a destination, the map database is searched
`via specially designed indexes and the destination is
`shown, for example, on the plot with a flashing star.
`The driver proceeds towards the star and his or her
`destination, as it was for the Biblical Star of
`Bethlehem! In—vel1icle destination finding is
`interactive, may lack a keyboard and — because it is
`interactive — can take advantage of the uscr’s
`ingenuity. In the Bosch Travelpilot and the Etak
`Navigator, for example, there are 12 buttons for
`input and the user only needs to enter a few
`characters before selecting from a list of possible
`cities or street names which match what has already
`been entered. Figure 43.7 shows a destination entry
`in progress. The user‘s ingenuity is exploited for
`recognizing spelling variants, in contrast to the
`common practice in geocoding software to search
`for sound-alike or otherwise similar words.
`
`Car Navigation Systems
`
`restaurant menus may be included. Various
`experiments are under way to test technical aspects
`as well as market acceptance of in-vehicle business
`listings.
`
`Path finding
`
`At the time of writing, only experimental systems
`such as EVA and CARIN compute recommended
`paths from the current location to the destination.
`For pathfinding, the street network topology is
`required. Furthermore, for the recommended paths
`to be feasible, the pathfinding algorithm must use
`traffic flow and turn restriction information; this
`places a significantly larger burden on the map
`database. People often expect the guidance system
`to declare the best route and, ultimately,
`pathfinding is likely to be a required feature of all
`navigation systems.
`The user interface for the pathfinding function
`can take many forms. Autoguidc, for example,
`provides only an arrow indicating the action at the
`next intersection, or a more elaborate graphic for a
`roundabout. Highlighting the path on a map display
`is another approach. Two further approaches
`highlight the path on the map display and offer
`verbal instructions (Cass 1989).
`
`.4 urzczt ll
`3 SF”
`‘LL
`nuizwnu
`uuyrz
`unvvc sank
`HIEMXTH
`uizuxrau
`nrcrrax
`
`uzrxsr
`
`Fig. 43.7 Destination entry to the Etak Navigator.
`
`In the future, business directories (‘Yellow
`Pages‘) and other lists of destinations will be
`provided as part of the map. Finding the nearest
`hardware store or service station is an example of
`such applications. Detailed business information or
`advertising could also be provided: for example,
`
`DIGITAL MAP REQUIREMENTS AND
`CHARACTERISTICS
`
`A digital map for navigation must meet demanding
`criteria. It must reside on rugged media, satisfy
`geometrical requirements imposed by the method of
`position determination, provide very fast retrieval
`and use an appropriate coordinate system.
`
`Storage media
`
`The storage medium for all available systems except
`the Etak Navigator is Compact Disk (CD) (Honey
`and White 1986). The Navigator uses compact
`cassette tape. The media and reading device must
`be sufficiently rugged for vehicle environments and
`these suffer wide temperature fluctuations and
`severe vibration. CD players meeting in-vehicle
`environmental specifications only became available
`
`19
`
`

`
`M White
`
`in 1989 and, being designed some years earlier, the
`Etak cassette player was made specifically to meet
`in—vehicle requirements for the application. All such
`devices are relatively slow for random retrieval;
`typical average seek time for a CD is 1 second —
`over 30 times that of a typical hard disk. The Etak
`cassette tape, which operates at 80 inches per
`second, has typical seek times of 10 seconds. These
`relatively slow speeds impose noteworthy
`challenges and severe constraints for the retrieval
`software, which are discussed below.
`Digital maps also consume considerable space.
`Each CD holds approximately 600 Mb. This is
`sufficient in EtakMap format to contain all of the
`streets, with their names and address ranges, in the
`United States. Etak’s cassette tape holds 3.5 Mb,
`which is sufficient for approximately the same
`information as shown in two typical folded paper
`street maps. lnevitably, the current trend is towards
`Compact Disk because the speed is workable and
`the storage available is capacious.
`
`Images, vectors, topology and geometry
`
`The simplest digital map representation to acquire
`and display is the bit—inapped image. It is also the
`least informative to the navigation software and
`most voracious in memory requirements. Map
`matching systems cannot use such images nor are
`images useful for destination finding. They only
`support display and, in any event, only at one scale
`and in one or a very few orientations: thus an
`upside—down image would not be readable. This is a
`severe limitation since most systems display the map
`with the heading of the vehicle being towards the
`top of the display, the so-called ‘heading—up’
`orientation described above.
`A more useful form of map encoding for
`navigation software is the vector encoding. in which
`linear features are encoded as directed line
`segments (vectors) or sequences of segments (see
`Egenhofer and Herring 1991 in this volume). This
`encoding is far more compact but is much more
`costly to acquire. It can support rudimentary map
`matching and display as well as variations in scale
`and orientation. Simply coding vectors (i.e. storing
`the equivalent of plotter commands) is not,
`however, sufficient for pathfinding nor is it
`adequate for sophisticated map matching that uses
`the network topology in its calculations. On the
`
`
`
`other hand. a geometrical encoding which includes
`topology fully supports map matching and display.
`Map matching requires the geometry of the road
`network for comparing and matching the dead
`reckoned path with streets; it also requires the
`geometry for evaluating