Transcript Calculating a Map Quality Metric

Measuring Map Quality
Material & Presentation by:
Richard Frank
Simon Fraser University
February 2004
Presentation Overview






Motivation
Uses of Map Quality
Requirements
Assumptions
Definitions
Algorithm Details
Motivation

Maps are generated in different ways


Carefully by a human designer
Automatically by a professional program


Automatically by a free service



Microsoft MapPoint
www.mapquest.com
They can also be shown on a wide variety of
medium
Due to resolution constraints, objects will
change or disappear.
Motivation
In printed form
(map)
Motivation
www.MapQuest.com
through a webbrowser
Motivation
Microsoft
MapPoint
(Standalone
Program)
Motivation
Displayed on a
PDA
(Mapopolis)
Uses of Map Quality


Give the user some indication of how
accurate different aspects (location,
shape, etc) of the map are
Beneficial in providing the end-user a
map that is much better tailored to their
specific wants

If the end user is interested in the structure
of the maps, the computer can select the
best map out of a set of possible maps with
best possible structure
Uses of Map Quality



Can compare qualities of two alternate maps at
same scale
Can measure quality after the generalization
operator, or after the visualization operator
On the backside, it can be used to determine
which data-cubes to generate

Ones that can quickly produce, without
generalization, on-demand maps above a certain
quality
Comparison


compare proposed
map to original map
(the best possible
map)
To determine best
alternative, compare
measures of the
maps
Map Quality Indicator
Requirements for good
measurement

Measure must take into account





individual objects on a map
the structure between them
their distribution on a map
These are enough to describe changes
on a map
No such measure currently exist
Assumptions

No symbolic representation for shapes



Shapes remain shapes
We’re not concerned about changes in
readability
Objects with holes are treated as multiple
objects, i.e.: holes are treated as objects
themselves
Definition – Voronoi Diagram

Given a map of objects

Find closest object or object edge

If the closest edges belong to two or more objects which are
equally close, then it is a Voronoi boundary
Definition – Voronoi Skeleton

If the point is inside the object and the closest edges belong to
two or more edges of the same object then it is part of the
Voronoi Skeleton
Voronoi Skeleton (in Red)
Algorithm Components

Object Shape Similarity
Structure Similarity
Information Content Similarity

Each will generate a measure


Shape Similarity



A map is a collection of
objects, which after
generalization can
change in shape
The information loss
during the shapechange has to be
measured
Use: Edit-Distance of
Voronoi Skeleton

Idea adapted from ‘EditDistance of Shock
Graphs’
Shape Similarity


Objects that contain holes are treated as multiple objects
Small perturbations do not affect the Voronoi Skeleton


Ideal for maps and bitmap objects
Calculate edit distance by assigning costs to
transformations that are required to change one
structure into the other
Object from Original Map
Object from Generalized Map
No Bump!
Structure similarity


Objects will be displaced
during generalization
the position of an object will
change



Objects & their Voronoi Regions
Before
After
relative to the map
boundaries
Relative distance to other
objects
Procedure



Measure distances
Input distances into matrix
calculate a cosine similarity
(standard way of comparing
matrices)
Length between neighbors
Information Content Similarity


During generalization, several objects could be
merged/aggregated into one larger object, or can be
deleted
There is loss of information because we loose
information about the individual objects
Loose 4 small objects
Gain 1 large object
Information Content: Entropy

Usual method: Entropy


Original calculation: SUM(Pi*ln(Pi))
Should modify it by weighing objects according to
the area of their Voronoi regions


If information is lost when something disappears, the
objects remaining become more important/influential
Modified method: VE=SUM(Pi*ln(Pi)*%V)


%V is the area of the Voronoi region for the object
divided by the total map area
Where Pi = Ki/N


Ki = # of objects of type i
N = total # of objects on the map
Algorithm Components

Consolidate the 3 measures into one number (representing the
quality of the map)?


Q = W1 * M1 + W2 * M2 + W3 * M3
Where




Q = Map quality measure
Pi = some weight for metric i
Mi = Measure of metric i
The parameters can either be pre-defined, representing an ‘ideal’
situation (if there is one), or can be left up to the user to let them
specify which issue is more important to them.
OR

Display all three resulting measures independently to the user
and let them interpret the results
Future Work


Currently working on implementation
Spatio-Temporal Data mining

We can compare sub-areas of two maps
from different time periods to find area with
most change, with possibility of restricting to
any class

ex: Find square kilometer with most road
development
References







Shape matching using edit-distance: an implementation (2001), Philip N.
Klein, Thomas B. Sebastian, Benjamin B. Kimia, Symposium on Discrete
Algorithms
Framework for Matching shock graphs, Thomas B. Sebastian, Philip N.
Klein, Benjamin B. Kimia,
www.lems.brown.edu/vision/researchAreas/ShockMatching/shock-matching.html,
10/16/2003
Quantitative measures for spatial information of maps, Zhilin Li and Peizhi
Huang, Hong Kong Polytechnic University, Dec 2001
Supporting Multiple Representations with Spatial Database Views
Management and the concept of VUEL, Yvan Bedard and Eveline Bernier,
Universite Laval
Fast computation of Generalized Voronoi Diagrams using Graphics
Hardware. Kenneth E Hoff, Tim Culver, John Keyser, Ming Lin, Dinesh Manocha.
University of North Carolina
Voronoi Diagrams of Polygons: A Framework for shape representation. Niranjan
Mayya & V.T. Rajan, University of Florida
Conflict Reduction in Map Generalization using Iterative Improvement, J
Mark Ware & Christopher B. Jones, University of Glamorgan. 1998