DIMACS Workshop on Algorithmic Issues in Modeling Motion
November 18 - 20, 2002
Title: Tracking Hands By Recognition
Hand gestures are examples of fast, complex motions that are hard to track in video. Yet good hand trackers would enable gesture recognition, motion capture for animation, and many other applications. Current approaches in the literature are usually either pure tracking or pure recognition: Pure tracking models a hand as a set of links connected by joints, identifies the image region corresponding to each link, and estimates the joint parameters directly from the images. Pure recognition matches images, typically hand silhouettes, to pre-stored templates corresponding to hand configurations of interest, and disregards the three-dimensional joint configuration altogether. Pure tracking is very hard because hands are by-and-large untextured, and palm and fingers occlude each other from view. Pure recognition does not provide three-dimensional hand configurations. This talk proposes a combination of these extreme approaches: As in pure recognition, the new approach precomputes image descriptors for interesting hand configurations. However, it does so from the images produced by a rendering program for animation, so that it can associate three-dimensional joint configurations to each descriptor. The descriptors are used for matching images to key configurations, and joint-space interpolation with descriptor-space coefficients provides intermediate hand configurations. Just as for pure tracking, these configurations can be used for driving animations, or to provide viewpoint-independent gesture recognition. New image representations are proposed to achieve descriptor invariance to image scale, translation and rotation.
Dimitris Metaxas, Rutgers University
Title: Human Motion Estimation: Visual Cues, Representation, Statistics
We present our modeling approach to human motion estimation which is based on research at the level of visual cues, motion representation and statistical estimation. In particular we present our methodology for 1) human gait recognition based on the use of motion invariants and algorithms from computational biology, 2) Facial tracking based on statistical cue integration and 3) Stochastic segmentation methods for internal organ shape and motion estimation. Our approach emphasizes the discovery of novel representations of shape and motion that facilitate the process of motion estimation.
Tong Zhang, RPI
Title: Multiple Motions in 3D Fractured Concrete Specimen
We analyze the multiple motions caused by fracture in a sequence of 3D
images of concrete specimen under increasing load. Compared with the
analysis of multiple motions in computer vision, our work is different
in that (1) the large amount of 3D data requires motion estimation
with high efficiency, and (2) the multiple motions caused by fracture
cannot be assumed to be independent, but have very strong spatial
constraints relative to each other. The multiple motions, rather than
a single motion, also distinguish our work from the 3D motion
analysis in biomedical image applications. Due to the large amount of data,
we currently recover the multiple objects based on the sparsely estimated
motion vector field. We show that important information, such as the number
of objects and the rigid motions associated with each object, have already
been revealed at such low resolution.
Michael Gleicher, University of Wisconsin - Madison
Title: Animation by Example
Motion for computer animation is notoriously difficult to create. In
order to achieve the expressiveness, subtlety and realism of quality
motion, practitioners have relied on either capturing the movements of
real performers, or labor and skill intensive manual specification
methods. Such methods create specific, short clips of motion. These
clips may provide the desired quality, but lack the flexibility
required when all movements cannot be pre-planned. In contrast to
clip-based methods, motion synthesis approaches can flexibly create
motions on the fly, but (to date) have not provided sufficient quality.
In this talk, I will introduce our synthesis-by-example approach to
creating streams of high-quality motion based on a database of
examples. Simple transition schemes along with methods that identify
when they are appropriate automatically transform a set of motion
clips into a motion graph, a structure containing a set of connected
motion clips. The motion graph is constructed such that any walk on
the graph corresponds to a valid motion, transforming the motion
synthesis problem into one of searching for walks on the graph. I will
describe two of our instantiations of our approach, the original
motion graphs as well as our newer Snap-Together Motion methods
specifically designed for interactive applications.
Samuel Hornus, INRIA
Title: 3D Radial Decompositions and Their Kinetic Maintenance
Consider a set of k non-intersecting convex polyhedra in 3D space.
Given a moving viewpoint, we address the problem of constructing and
continuously updating the visibility polyhedron
of the viewpoint using the Kinetic data structure framework.
If we consider the viewpoint as an opaque object, the
maintained data structure is a 2.5D cut in the 3D visibility (Durand).
This work-in-progress is largely inspired from the work of Olaf
Hall-Holt, who gives a solution for the 2D case.
Dinesh K. Pai, Rutgers University
Title: Motion, Constraints, and Contact
Algorithms for representing and reasoning about motion are very
important. However, in this talk we will argue that the dual problem
of representing and reasoning about the constraints on motion is
equally important, and that it is advantageous to deal with both
simultaneously. We will focus on constraints due to contact, since
they are essential for physical interaction and for creating tangible
virtual environments. Contact interactions involve visible
deformation, haptic forces, and audible sounds driven by the contact
forces. I will describe how we can model these contact phenomena, and
how they can be measured using the UBC Active Measurement Facility
(ACME) and the Rutgers haptic Auditory and Visual Environment (the
RAVE).
Voicu Popescu and Elisha Sacks, Purdue University
Title: Point-and-Shoot Model Acquisition
We are developing an inexpensive, hand-held device for producing
high-fidelity 3D geometric models of real-world scenes in real time.
Real-time geometry acquisition is an enabling technology for computer
graphics, removing the modeling bottleneck in generating realistic images of
complex scenes. The benefits span modeling and simulation, acquisition of
real world data, photorealistic rendering, virtual reality, virtual training,
and telecollaboration. Current 3D acquisition devices are slow, bulky,
expensive, and produce redundant yet incomplete data sets. Moreover some only
work in controlled environments and some do not acquire color. Our depth
camera has the potential to solve these problems.
The depth camera consists of a digital video camera augmented with an array
of laser pointers and linked to a portable computer. The operator scans the
scene and a texture-mapped model is constructed automatically. We have built
a prototype for $300 using commodity components. We believe that a
commercial version can be designed in three years that will make 3D color
modeling as easy and inexpensive as home video.
Making the device work poses several research challenges.
Title: Kinetic Data Structures for Collision Detection
Collision detection is a basic and unavoidable computational problem
arising in all areas of geometric modeling involving objects in motion.
Most approaches to collision detection work in two phases. First, a
broad phase algorithm and data structure are used to determine pairs of
objects that might possibly collide. A different narrow phase algorithm
and data structure then tests each pair. In general, such approaches
force the objects into a representation best suited for one of the two
phases or involve some kind of hybrid representation not ideally
suited for either.
In this talk we propose a simple and elegant kinetic data structure for
detecting collisions between polygonal (but not necessarily convex)
objects in motion in the plane. Our structure is compact, maintaining an
active set of certificates whose number is proportional to a
minimum-size set of separating polygons for the objects. It is also
responsive; invariants can be restored quickly on the failure of a
certificate. Furthermore, our structure does not need to distinguish
between broad and narrow phases, but adapts to both the nature and
degree of separation between objects.
Fabian Schwarzer, Mitul Saha, and Jean-Claude Latombe, Stanford University
Title: Exact collision checking of robot paths
Collision checking is a fundamental operation in the computer simulation and
planning of object motions (robotics, graphic animation, physical simulation).
While static collision checking amounts to testing a single configuration
of the moving objects for spatial overlaps, dynamic collision checking
requires determining whether all configurations on a continuous path in
configuration space are collision-free, or not. Today, dynamic
collision checking remains a major bottleneck in many applications.
In particular, probabilistic roadmap (PRM) planners
heavily rely on the availability of efficient dynamic checkers to test
``local paths'' between randomly sampled configuration for collision.
Most such planners use a bounding-volume method to test intermediate
configurations along the local paths at
some pre-selected resolution. If this resolution is coarse, then
collisions are easily missed, especially when some objects are thin.
If it is small, time is wasted checking
many configurations. This presentation will describe an efficient exact
dynamic collision checker. This checker adjusts the resolution at
which a path is checked by relating the distances between objects
in the workspace to the maximal lengths of the paths traced out by
points on these objects. It has been extensively tested,
in particular with very thin objects. It is faster than the resolution-based
approach (with adequate resolution), with the enormous advantage that
it never returns an incorrect answer.
Patrice Koehl, Stanford University
Title: Biomolecules in Motion: With or Without Water?
Accurate modeling of biomolecules in solution using molecular mechanics
requires realistic models for the interaction of the solvent with the
molecule. To treat such a medium (usually water) in a molecular
calculation, both explicit and implicit solvent models have been developed.
While explicit models rely on using thousands of discrete solvent molecules,
implicit models introduce a continuous medium having the average
properties of the real solvent. They surround the solute beginning at the
van der Waals surface. These implicit or continuum models relate the
energetics of the interaction of the solvent with the protein to the
geometry of this surface. In this paper, we provide a brief review of the
concepts underlying implicit solvent models. We then describe the
challenges encountered in implementing these models in a molecular
dynamics simulation. We focus on the solution to these challenges
provided by computational geometry.
Joint work with Herbert Edelsbrunner and Michael Levitt
Nancy Amato, Texas A&M University
Title: Using Motion Planning to Study Protein Folding with a case study of hairpin formation in Proteins G & L
In this talk, we investigate a novel approach for studying protein folding
that has evolved from robotics motion planning techniques called
probabilistic roadmap methods (PRMs). Our focus is to study issues related
to the folding process, such as the formation of secondary and tertiary
structure, assuming we know the native fold. A feature of our PRM-based
framework is that the large sets of folding pathways in the roadmaps it
produces, in a few hours on a desktop PC, provide global information about
the protein's energy landscape. This is an advantage over other
simulation methods such as molecular dynamics or Monte Carlo methods
which require more computation and produce only a single trajectory in
each run. In our initial studies, we obtained encouraging results
for several small proteins. In this talk, we investigate more
sophisticated techniques for analyzing the folding pathways in our
roadmaps. In addition to more formally revalidating our previous results,
we present a case study showing our technique captures known folding
differences between the structurally similar proteins G and L.
This is joint work with Guang Song and Shawna Thomas, PhD students at
Texas A&M, Ken Dill (UCSF), and Marty Scholtz (Texas A&M). More
information regarding our work, including movies, can be found at
http://parasol.tamu.edu/people/amato/
Mark de Berg, TU Eindhoven (the Netherlands)
Title: Lower Bounds for Kinetic Data Structures
A kinetic data structure (KDS) is a data structure that maintains
a certain attribute---the convex hull, for instance---of a set of
continuously moving objects. In most KDSs, the attribute under
consideration is uniquely defined, and it is maintained explicitly.
In such cases one can obtain a lower bound on the maintenance cost
(the number of events the KDS has to process) by proving a lower
bound on the number of changes the attribute can undergo. In other
cases, e.g. when one wants to maintain a binary space partition of
a set of moving objects, the attribute is not uniquely defined,
and proving lower bounds becomes more difficult. Finally, one can
consider KDSs that do not explicitly maintain a certain attribute
of the given set, but only a data structure that can answer queries
about the set. In such cases, there will be a trade-off between the
maintenance cost and query time. In this talk I will discuss lower
bounds for some problems of each of these three types.
Boris Aronov, Polytechnic University
Title: On the number of views of translates of a cube
It is known that a general polyhedral scene of complexity N has at
most O(N^6) distinct orthographic views and at most O(N^9) distinct
perspective views, and that these bounds are tight in the worst case.
In this paper we show that, for the special case of scenes consisting
of a collection of pairwise disjoint translates of a cube, these
bounds improve to O(N^{4+epsilon}) and O(N^{6+epsilon}), for any
epsilon>0, respectively. In addition, we present constructions
inducing Omega(N^4) orthographic views and Omega(N^6) perspective
views thus showing that these bounds are nearly tight in the worst
case. Finally, we show how to extend the upper bounds to several
classes of related scenes.
Joint work with Robert Schiffenbauer and Micha Sharir.
Title: Clustering Motion
Given a set of moving points in R^d, we show that one can cluster them
in advance, using a small number of clusters, so that in any point in
time this static clustering is competitive with the optimal k-center
clustering of the point-set at any point in time. The advantage of
this approach is that it avoids the usage of kinetic data-structures
and as such it does not need to update the clustering as time passes.
To implement this static clustering efficiently, we describe a simple
technique for speeding-up clustering algorithms, and apply it to
achieve a faster clustering algorithms for several problems. In
particular, we present a linear time algorithm for computing a
2-approximation to the k-center clustering of a set of n points in
d-spaced. This slightly improves over the algorithm of Feder and
Greene, that runs in \Theta(n log k) time (which is optimal in
the comparison model).
John Hershberger, Mentor Graphics Corp.
Title: Smooth Kinetic Maintenance of Clusters
This paper proposes a simple, deterministic kinetic data structure
(KDS) for maintaining a covering of moving points by axis-aligned unit
boxes in R^d. The number of boxes is always within a factor of 3^d of
the best possible static covering. In the plane, this approximation
factor (9) compares favorably with the approximation factor (around
one million) of the best previous algorithm [Gao et al., SCG 2001].
The new KDS is efficient, local, compact, and responsive.
Title: Routing in Mobile Wireless Networks
A mobile wireless network is an ad-hoc network formed by a set of
mobile nodes which communicate with each other using radio signals:
two nodes can directly communicate only when they are within certain
distance. The routing in such a network is difficult because of the
mobility of the nodes and the lack of central control. One approach
to reducing the routing complexity is by constructing a sparse graph
with "good quality" on the mobile nodes and running the routing
algorithm on the sparse graph. In this talk, I will present an
algorithm to construct and maintain such a graph for mobile nodes.
Our algorithm consists of two stages. In the first stage, we form
clusters on the nodes such that the centers of clusters are sparsely
distributed. In the second stage, we form a planar graph with a
constant stretch factor on the centers of the clusters. The algorithm
in both stages are dynamic, distributed, and localized. In addition,
it can be efficiently implemented under the kinetic data structure
model to take advantage of the motion coherence. I will also discuss
routing on such graphs and some open problems.
This is joint work with Jie Gao, Leo Guibas, John Hershberger,
and An Zhu.
David M. Mount, University of Maryland
Title: Incremental Motion and k-Means Clustering
Given a set of points P in real d-dimensional space and an integer k,
k-means clustering seeks a set of k points in space so as to minimize
the average squared distance from each point of P to its closest center.
Lloyd's algorithm (also called the k-means algorithm) is a popular
heuristic for k-means clustering, which works by associating each point
with its nearest center and then incrementally moving each center to the
centroid of its associated cluster. In the limit, Lloyd's algorithm
converges to a locally minimal solution. Lloyd's algorithm when
combined with local search has been shown to be a practical
approximation algorithm for k-means clustering.
The principal computational cost of k-means clustering is in computing
the nearest center to each point of P. We present an practical approach
to computing these distances. Our algorithm takes advantage of the
incremental nature of the movement of centers to achieve significant
speed-ups over existing nonincremental approaches. Our analysis will be
primarily empirical, based on data sets that have been generated both
synthetically and real data arising from clustering applications.
Hai Huang, Arizona State University
Title: Approximation Algorithms for the Mobile Piercing Set Problem
with Applications to Clustering in Ad-hoc Networks
A piercing set of a given collection of objects is a set of points such
that for every object there exists a point in the set such that the
point is in the object (``pierces the object''). The minimum piercing
set problem seeks for a piercing set with the minimum cardinality. We
consider a dynamic variation of the (static) piercing set problem on a
collection of unit-disks (unit-diameter disks), where disks are moving
in space. In the mobile piercing set (MPS) problem, we would like to
maintain a dynamic piercing set of a collection of mobile disks such
that, at any time, it is a minimum piercing set of the current
configuration of the disks. Moreover, we would like to be able to
devise a distributed algorithm to solve this problem. The MPS problem
has many applications outside its main computational geometry domain,
as for example in mobile ad-hoc communication networks.
Our main contributions are two-fold. First, we present a simple,
general framework for obtaining efficient constant-factor approximation
algorithms for the mobile piercing set (MPS) problem on unit-disks for
standard metrics in fixed dimension vector spaces, with both optimal
setup and update cost. Second, we show how the proposed algorithms can
be directly applied to provide theoretical performance analyses for two
popular 1-hop clustering algorithms in ad-hoc networks: the lowest-id
algorithm and the Least Cluster Change (LCC) algorithm. We also present
an O(log(n))-approximation algorithm for the mobile piercing set
problem for nonuniform disks (i.e., disks that may have different
radii), with constant update time.
Feng Zhao, Palo Alto Research Center (formerly Xerox PARC)
Title: Distributed Networked Sensing and Information Processing
Because of advances in MEMS micro-sensors, wireless networking, and
embedded processing, ad-hoc networks of sensors are becoming
increasingly available for commercial and military applications such
as environmental monitoring (e.g., traffic, habitat, security),
industrial sensing and diagnostics (e.g., factory, appliances),
infrastructure protection (e.g., power grids, water distribution), and
battlefield awareness (e.g., multi-target tracking). From the
engineering and computing point of view, sensor networks become a rich
source of problems in communication protocols, sensor tasking and
control, sensor fusion, distributed databases, probabilistic
reasoning, and algorithmic design.
In this talk, I will describe PARC's recent work in distributed
networked sensing and applications. Tracking is an essential
capability for sensor networks in many practical applications, and
will be used as a canonical problem to drive out some of the central
issues in designing sensor network algorithms and applications.
Traditional signal processing approaches have focused on optimizing
estimation quality for a fixed set of resources. However, for
power-limited and multi-user decentralized systems, it becomes
critical to carefully select the embedded sensor nodes that
participate in the sensor collaboration, balancing the information
contribution of each against its resource consumption or potential
utility for other users. We term this style of computation in
distributed embedded systems as collaborative signal and information
processing (CSIP). I will describe our recent work on IDSQ sensing
and routing algorithms, and group management that address the key CSIP
problem of defining and forming dynamic collaborative groups of
distributed sensors to accomplish given tasks. Experimental results on
several PARC testbeds will also be demonstrated.
Sotiris Nikoletseas and Paul Spirakis, CTI, Patras
Title: Distributed Communication Algorithms for Ad-hoc Mobile Networks
An ad-hoc mobile network is a collection of mobile hosts, with wireless
communication capabilities, forming a temporary network without the aid
of any established fixed infrastructure.
In such networks, topological connectivity is subject to frequent,
unpredictable change. Our work focuses on networks with high rate of such
changes to connectivity. For such dynamically changing networks we
propose protocols which exploit the co-ordinated (by the protocol)
motion of a small part of the network. We show that such protocols can
be designed to work correctly and efficiently even in the case of
arbitrary (but not malicious) movements of the hosts not afected by the protocol.
We also propose a methodology for the analysis of the expected behavior
of protocols for such networks, based on the assumption that mobile hosts
(those whose motion is not guided by the protocol) conduct concurrent
random walks in their motion space.
In particular, our work examines the fundamental problem of
communication and proposes distributed algorithms for it. We provide rigorous
proofs of their correctness, and also give performance analyses by
combinatorial tools. Finally, we have evaluated these protocols by
experimental means.
Title: Modeling Motion in Ocelot
Ocelot is a software system developed at Bell Labs for predicting and
optimizing the performance of cellular phone systems. A key aspect of
such systems is plainly that people making cellphone calls can move
around. The effect of such motion on system performance is hard to
model, especially since our desire to optimize the system means that
the function predicting performance should be smooth; this limits
the usefulness for us of Monte Carlo simulation, for example. I will
describe our attempts to cope with this situation, where we model
motion but don't allow anything to move.
Title: Combinatorial Roadmaps in Configuration Spaces of Simple Planar Polygons
The pseudo-triangulation roadmap algorithm is a systematic way of
generating paths in the configuration space of non-self-intersecting
planar polygons. While the combinatorial part is well understood, the
search for efficient solutions to the algebraic components of the
algorithm is posing a number of interesting theoretical questions. We
will present the problems, many of which are open, and discuss
solutions to some of them.
Sue Whitesides, McGill University
Title: Complexity Issues in Chain and Tree Reconfiguration
We describe our investigations of several complexity issues
concerning the reconfiguration of simple (non-crossing)
polygonal chains of fixed-length segments in 3D and of
simple trees of fixed-length segments in 2D.
In 2D, it is known that every simple polygonal chain
of fixed-length segments can be continously reconfigured to a
straightened configuration. On the other hand,
it is known that simple trees of fixed length segments
cannot always be moved to configurations that are essentially
``flat''. Indeed, a tree in 2D may have exponentially
many equivalence classes of configurations.
We have investigated several complexity issues whose
interest is highlighted by the above results.
We show that ``flattening'' problems for trees
moving in 2D are decidable, and appear to be P-Space Complete.
In 3D, we show that the question of straightenability for
a polygonal chain of fixed-length segments also
appears to be P-Space complete.
(joint work with Helmut Alt, Christian Knauer, and G\"unter Rote)
Alper Ungor, Duke University
Title: Relaxed Scheduling in Dynamic Skin Triangulation
We introduce relaxed scheduling as a paradigm for mesh maintenance and
demonstrate its applicability to triangulating a skin surface in
3-space.
Joint work with Herbert Edelsbrunner.
Title: Building space-time meshes over arbitrary spatial domains
We present an algorithm to construct meshes suitable for space-time
discontinuous Galerkin finite-element methods, which can used to model
physical systems governed by hyperbolic PDEs. The key feature of
these problems is that information flows outward from every point in
space-time at some finite, but not necessarily constant, rate. Given
an arbitrary simplicially meshed domain D of any dimension and a time
interval [0,T], our algorithm builds a simplicial mesh of the
space-time domain D x [0,T], in constant time per element. Our
algorithm avoids the limitations of previous methods by carefully
adapting the durations of space-time elements to the local quality and
feature size of the underlying space mesh.
This is joint work with Damrong Guoy, John Sullivan, and Alper
\"Ung\"or, published in the Proceedings of the 11th International
Meshing Roundtable, 391-402, 2002.
Ouri Wolfson, Univ. of Illinois, Chicago
Title: Managing the location of Moving Objects: Linguistic and performance issues
Miniaturization of computing devices, and advances in wireless communication
and sensor technology are some of the forces that are propagating computing
from the stationary desktop to the mobile outdoors. Some important classes
of new applications that will be enabled by this revolutionary development
include location-based services, tourist services, mobile electronic
commerce, and digital battlefield. Some existing application classes that
will benefit from the development include transportation and air traffic
control, weather forecasting, emergency response, mobile resource
management, and mobile workforce. Location management, i.e. the management
of transient location information, is an enabling technology for all these
applications. Location management is also a fundamental component of other
technologies such as fly-through visualization, context awareness, augmented
reality, cellular communication, and dynamic resource discovery.
In this talk we present our view of the important linguistic constructs for
accessing databases of location information, and efficient processing
algorithms for these constructs. We also compare various approaches for
addressing the tradeoff between resource consumption and accuracy that is
inherent in tracking. Finally, we present experimental results concerning
the compression of location information.
Cecilia M. Procopiuc, AT&T Research Labs
Title: Indexing Mobile Data
Several areas such as air-traffic control, digital battlefields,
and geographic information systems need the capability to index moving
objects so that various queries on them can be answered in real time.
With the rapid advances in positioning systems, such as GPS, ad-hoc
networks, and wireless communication, it is becoming increasingly feasible
to track and record the changing position of continuously moving objects.
This has posed new challenges for database systems, requiring the
development of new methods for indexing and querying moving objects
efficiently.
In this talk I will review a few recent advances in kinetic database
technology. The algorithms I will discuss draw on results and data
structures developed in the context of computational geometry. I will
briefly present some of the paradigms and techniques, and discuss how they
can be used for developing efficient kinetic indexes.
Title: Kinetic Medians and $kd$-Trees
We propose algorithms for maintaining two variants of $kd$-trees
of a set of moving points in the plane. A pseudo $kd$-tree allows
the number of points stored in the two children to differ. An
overlapping $kd$-tree allows the bounding boxes of two children to
overlap. We show that both of them support range search operations
in $O(n^{1/2+\epsilon})$ time, where $\epsilon$ only depends on
the approximation precision. When the points move, we use
event-based kinetic data structures to update the tree when
necessary. Both trees undergo only a quadratic number of events,
which is optimal, and the update cost for each event is only
polylogarithmic. To maintain the pseudo $kd$-tree, we make use of
algorithms for computing an approximate median level of a line
arrangement, which itself is of great interest. We show that the
computation of the approximate median level of a set of lines or
line segments, can be done in an online fashion smoothly, i.e.,
there are no expensive updates for any events. For practical
consideration, we study the case when there are speed limit
restrictions or smooth trajectory requirements. The maintenance of
the pseudo $kd$-tree, as a consequence of the approximate median
algorithm, can also adapt to those restrictions.