Transcript Introduction to Parallel Computing

Algorithms and Modern
Computer Science
Dr. Marina L. Gavrilova
Dept of Comp. Science, University of Calgary,
AB, Canada, T2N1N4
Presentation outline



About my research
Data structures and algorithms to be
studied
Application areas
•
•
•
•

Optimization and computer modeling
Image processing and computer graphics
Spatial data
Biometrics
Summary
My Research Interests








Computer modeling and simulation
Computational geometry
Image processing and visualization
Voronoi diagram and Delaunay triangulation
Biometric technologies
Collision detection optimization
Terrain modeling and visualization
Computational methods in spatial analysis and GIS
Interests and affiliations
SPARCS Lab Co-Founder and Director
BT Lab Co-Founder and Director
Computational Geometry and Applications Founder and Chair since 2001
ICCSA Conference series Scientific Chair (since 2003)
Transactions on Computational Science Journal Springer Editor-in-Chief
Research topics: optimization, reliability, geometric algorithms, data structures
representation and visualization, GIS, spatial analysis, biometric modeling
Data Structures to be Studied






Hashing and hash tables
Trees
Spatial subdivisions
Graphs
Flow networks
Geometric data structures
Algorithms to be studies






Search heuristics
Encoding and compression
techniques
Linear programming
Dynamic programming
Game design techniques
Randomized algorithms
Long-Term Goals of Research in
Computer Science






Provide a solution to a problem
Decrease possibility of an error
Improve methodology or invent a
novel solution
Make solution more robust
Make solution more efficient
Make solution less memory
consuming
Examples of data structures
applications in areas of computer
science

Typical applications:
• Heaps for data ordering and faster access in
operating systems
• K-d trees for multi-dimensional database
searches
• B, B*, B+ trees for file accesses
• Geometric data structures for geographical
data representation and processing
• Compression algorithms for remote access,
Internet, network transmission and security
• Search heuristics for game strategy
implementation
Recent trends

The old definition of computer
science—the study of phenomena
surrounding computers—is now
obsolete. Computing is the study of
natural and artificial information
processes.
ACM Communications 50-07-2007
More Advanced Applications




Data structures in Optimization and
Computer Simulation
Data structures in Image Processing and
Computer Graphics
Data structures in GIS (Geographical
Information Systems) and statistical
analysis
Data structures in biometrics
Back then…
And now…
Einar Rustad, VP Business Development,
Dolphin Interconnect Solutions
But algorithms still should work,
or else …
State of the art in computing
Horst Simon
Director NERSC, Lawrence Berkeley
National Laboratory
High performance computing
Increased Scientific Demands
Part 1. Optimization and
Computer Modeling
• Space partitioning
• Trees
• Geometric data
structures




Biological systems (plants,
corals)
Granular-type materials (silo,
shaker, billiards)
Molecular systems (fluids,
lipid bilayers, protein
docking)
GIS terrain modeling
Pool of Data Structures
Dynamic Delaunay triangulation
P1
P1
P1
P2
P2
P4
P4
P3
P3
P2
P4
P3
INCIRCLE( P1, P2 , P3 , P4 )  0 INCIRCLE( P1, P2 , P3 , P4 )  0 INCIRCLE( P1, P2 , P3, P4 )  0
Spatial subdivisions
Segment trees
k cells
K-d trees
Interval trees
Combination of
data structures
Collision detection optimization
Problem: A set of n moving particles is given in the plane or
3D with equations of their motion. It is required to detect
and handle collisions between objects and/or boundaries.
Collisions are instantaneous and one-on-one only.
Approach: Use dynamic data structures in the context of
time-step event oriented simulation model.
Data structures implemented are:
dynamic generalized DT
 regular spatial subdivision
 regular spatial tree
 set of segment tree

The nearest-neighbor problem
Task: To find the nearest-neighbor in a system of circular objects
{Gavrilova 01}
Approach: To use generalized Voronoi diagram in Manhattan and
power metric and k-d tree as a data structure.
The Initial Distribution Generator (IDG) module:
Used to create various input configurations: the uniform
distribution of sites in a square, the uniform distribution of
sites in a circle, cross, ring, degenerate grid and degenerate
circle. The parameters for automatic generation are: the
number of sites, the distribution of their radii, the size of the
area, and the type of the distribution.
The Nearest-Neighbour Monitor (NNM) module:
The program constructs the additively weighted supremum
VD, the power diagram and the k-d tree in supremum metric;
performs series of nearest-neighbour searches and displays
statistics.
Tests: large data sets (10000 particles), silo model
Example: supremum VD and DT
The supremum weighted Voronoi diagram (left) and the
corresponding Delaunay triangulation (right) for 1000 randomly
distributed sites .
Study of porous materials in 3d
Collaborators: N.N. Medvedev, V.A.Luchnikov, V. P. Voloshin,
Russian Academy of Sciences, Novosibirsk [Luchnikov 01].
Task: To study the properties of the system of polydisperse spheres
in 3D, confined inside a cylindrical container.
Approach: A boundary of a container is considered as one of the
elements of the system.

To compute the Voronoi network for a set of balls in a cylinder we
use the modification of the known 3D incremental construction
technique, discussed in {Gavrilova et. al.}

The center of an empty sphere, which moves inside the system so
that it touches at least three objects at any moment of time,
defines an edge of the 3D Voronoi network.
Tests: porous materials, molecular structures
Example: 3D Euclidean Voronoi
diagram
3D Euclidean Voronoi diagram: hyperbolic arcs identify voids –
empty spaces around items obtained by Monte Carlo
method.
Experiments
The approach was tested on
a system representing
dense packing of 300
Lennard-Jones atoms. The
largest channels of the
Voronoi network occur
near to the wall of the
cylinder. A fraction of
large channels along the
wall is higher for the
model with the fixed
diameter (right) than for
the model with relaxed
diameter (left).
Part 2. Image processing and
Computer Graphics
• Space partitioning
• Trees
• Geometric data
structures
• Compression
• Search heuristics






Image reconstruction
Image compression
Morphing
Detail enhancement
Image comparison
Pattern recognition
Pattern Matching

Aside from a problem of measuring
the distance, pattern matching
between the template and the given
image is a very serious problem on
its own.
Template Matching approach to
Symbol Recognition
Compare an
image with each
template and see
which one gives
the best mach
(courtesy of
Prof. Jim Parker,
U of C)
Good Match
Most of the pixels overlap means a good match (courtesy of Prof.
Jim Parker, U of C)
Image
Template
Distance Transform
Given an n x m binary image I of white and black
pixels, the distance transform of I is a map that
assigns to each pixel the distance to the nearest
black pixel (a feature).
Medial axis transform

The medial axis, or skeleton of the
set D, denoted M(D), is defined as
the locus of points inside D which lie
at the centers of all closed discs (or
spheres) which are maximal in D,
together with the limit points of this
locus.
Medial axis transform
Voronoi diagram in 3D
Part 3. Spatial Data and GIS
• Space partitioning
• Grids
• Distance metrics
• Geometric data
structures







Terrain visualization
Terrain modeling
Urban planning
City planning
GIS systems design
Navigation and tracking
problems
Statistical analysis
GIS studies - SPARCS Lab
Collaborators: S. Bertazzon, Dept. of Geography,
C. Gold, Hong Kong Polytechnic, M. Goodchild,
Santa Barbara
Problem: study or patterns and correlation among
attributed geographical entities, including
health, demographic, education etc. statistics.
Approach: pattern analysis using 3D Voronoi
diagram, spatial statistics and autocorrelation
using Lp metrics, pattern matching and
visualization
Terrain models
Quantitative Map Analysis
Population, ’96
0
100Km.
DEM: Digital Elevation Model
• Contains only relative Height
• Regular interval
• Pixel color determine height
•Discrete resolution
Non-Photo-Realistic Real-time
3D Terrain Rendering
• Uses DEM as input of the application
•Generates frame coherent animated view in real-time
•Uses texturing, shades, particles etc. for layer visualization
Part 4. Biometrics
•
•
•
•
Hashing
Space partitioning
Trees
Geometric data
structures
• Searching



Biometric identification
Biometric recognition
Biometric synthesis
Background

Biometrics refers to the automatic identification
of a person based on his/her physiological or
behavioral characteristics.
Thermogram vs. distance transform
Thermogram of an ear (Brent Griffith, Infrared
Thermography Laboratory, Lawrence Berkeley
National Laboratory )
Nearest Neighbor Approach

Voronoi diagram

Directions of
feature points
Delaunay Triangulation of Minutiae
Points
(a) Binary Hand
(b) Hand Contour
Spatial Interpolation using
RBF(Radial Basis Functions)
Deformation in 2D and 3D
Summary

Data structures and algorithms
studies in the course are powerful
tools not only for basic operation of
computer systems and networks but
also a vast array of techniques for
advancing the state of the research
in various computer science
disciplines.