 |
2004 . 2003 . 2002 . 2001 . 2000 . 1999 . 1998 . 1997 . 1996 . 1995 . 1994 . 1993 . 1992 . 1991 . 1990
MS-CIS-00-01
Rajeev Alur, Radu Grosu, Yerang Hur, Vijiay Kumar, and Insup
Lee
We propose a language, called {\sc Charon}, for modular specification
of interacting hybrid systems. For hierarchical description
of the system architecture, {\sc Charon} supports building
complex agents via the operations of instantiation, hiding,
and parallel composition. For hierarchical description of the
behavior of atomic components, {\sc Charon} supports building
complex modes via the operations of instantiation, scoping,
and encapsulation. Features such as weak preemption, history
retention, and externally defined Java functions, facilitate
the description of complex discrete behavior. Continuous behavior
can be specified using differential as well as algebraic constraints,
and invariants restricting the flow spaces, all of which can
be declared at various levels of the hierarchy. The modular
structure of the language is not merely syntactic, but can
be exploited during analysis. We illustrate this aspect by
presenting a scheme for modular simulation in which each mode
can be compiled solely based on the locally declared information
to execute its discrete and continuous updates, and furthermore,
submodes can integrate at a finer time scale than the enclosing
modes.
MS-CIS-00-02
Camillo J. Taylor and David Jelinek
This paper deals with the problem of recognizing objects
seen from arbitrary viewpoints based on information obtained
from a small number of reference images. We proceed by constructing
a database that consists of a small number (ten is typical)
of images of each object. Corner features are detected in each
of the images in the database and local descriptors for these
features are formed from the grayscale values in the surrounding
regions. When a test image is obtained, its interest points
and local descriptors are compared to those in the database.
The recognition procedure also enforces an appropriate version
of the epipolar constraint for affine cameras. The space requirements
for this scheme increase linearly with the number of objects,
and the time complexity scales logarithmically.
The method combines the advantages of feature based and image
based recognition algorithms, while avoiding many of the drawbacks.
While the method does identify and match interest points from
images, we avoid the combinatorial issues inherent in the correspondence
schemes employed by many feature based methods. In contrast
to image based recognition techniques, the number of stored
images is relatively small, yet the algorithm is capable of
recognizing objects from viewpoints not represented in the
database.
MS-CIS-00-03
Camillo J. Taylor and David Jelinek
This paper deals with the problem of recovering the dimensions
of an object and its pose from a single image acquired with
a camera of unknown focal length. It is assumed that the object
in question can be modeled as a polyhedron where the coordinates
of the vertices can be expressed as a linear function of a
dimension vector, $\lambda$. The reconstruction program takes
as input a set of correspondences between features in the model
and features in the image. From this information the program
determines an appropriate projection model for the camera (scaled
orthographic or perspective), the dimensions of the object,
its pose relative to the camera and, in the case of perspective
projection, the focal length of the camera. We demonstrate
that this reconstruction task can be framed as an unconstrained
optimization problem involving a small number of variables,
no more than four, regardless of the number of parameters in
the dimension vector.
MS-CIS-00-04
Piglet: a Low-Intrusion Vertical Operating System
Steve Muir and Jonathan Smith
Vertically-structured operating systems are a recent proposal
for providing application-level resource management. While
this has been accomplished, the issue of how the structure
of the operating system affects application behaviour remains
largely unexplored.
We introduce the concept of OS intrusion as a measure of
the overheads that the operating system's policies and mechanisms
impose upon applications. Vertical operating systems address
policy intrusion; we analyse the costs of two forms of mechanism
intrusion---interrupt handling and system call overhead---in
the Linux kernel, and demonstrate their significance.
Piglet is a new architecture intended to provide the resource-management
capabilities of a vertical OS, while reducing mechanism intrusion.
Measurements of a prototype implementation show that Piglet
achieves these goals; for example, round-trip times measured
by the ping application are up to 20% lower than for Linux.
MS-CIS-00-05
Geoffrey Egnal
Almost all imaging systems require some form of registration.
A few examples are aligning medical images for diagnosis, matching
stereo images to recover shape, and comparing facial images
in a database to recognize people. Recently, a new type of
solution to the registration problem has emerged, based on
information theory. In particular, the mutual information similarity
metric has been used to register multi-modal medical images.
Mutual information compares the statistical dependence between
the two images. Unlike many other registration techniques,
mutual information makes few a priori assumptions about the
surface properties of the object or the imaging process, making
it adaptible to changes in lighting and changes between sensors.
The method can be applied to larger dimensional registration
and many other imaging situations. In this report, we compare
two approaches taken towards the implementation of rigid 2D
mutual information image registration. We look further at algorithm
speedup and noise reduction efforts. A full background is provided.
MS-CIS-00-06
Camillo J. Taylor
This paper describes an approach to capturing the appearance
and structure of immersive environments based on the video
imagery obtained with an omnidirectional camera system. The
scheme proceeds by recovering the 3D positions of a set of
point and line features in the world from image correspondences
in a small set of key frames in the image sequence. Once the
locations of these features have been recovered the position
of the camera during every frame in the sequence can be determined
by using these recovered features as fiducials and estimating
camera pose based on the location of corresponding image features
in each frame. The end result of the procedure is an omnidirectional
video sequence where every frame is augmented with its pose
with respect to an absolute reference frame and a 3D model
of the environment composed of point and line features in the
scene.
By augmenting the video clip with pose information we provide
the viewer with the ability to navigate the image sequence
in new and interesting ways. More specifically the user can
use the pose information to travel through the video sequence
with a trajectory different from the one taken by the original
camera operator. This freedom presents the end user with an
opportunity to immerse themselves within a remote environment
and to control whay they see.
MS-CIS-00-07
Michael Hicks and Stephanie Weirich
We present the load-calculus, used to model dynamic
loading, and prove it sound. The calculus extends the polymorphic
lambda-calculus with a load primitive that dynamically
loads terms that are closed, with respect to values. The calculus
is meant to approximate the process of dynamic loading in TAL/Load
[4], an version of Typed Assembly Language [7] extending with
dynamic linking. To model the key aspects of TAL, the
calculus contains references and facilities for named types.
Loadable programs may refer to named types defined by the running
program, and may export new types to code loaded later. Our
approach follows the framework initially outlined by Glew et.
al [3]. This calculus has been implemented in the TALx86 [6]
version of Typed Assembly Language, and is used to implement
a full-featured dynamic linking library, DLpop [4].
MS-CIS-00-08
Peng Song, Peter Kraus, Vijay Kumar and Pierre Dupont
The use of Coulomb's friction law with the principles of
classical rigid body dynamics introduces mathematical inconsistencies.
Specifically, the forward dynamics problem can have no solutions
or multiple solutions. In these situations, compliant contact
models, while increasing the dimensionality of the state vector,
can resolve these problems. The simplicity and efficiency of
rigid body models, however, provide strong motivation for their
use during those portions of a simulation when the rigid body
solution is unique and stable.
In this paper, we use singular perturbation analysis in conjunction
with linear complementarity theory to establish conditions
under which the solution predicted by the rigid body dynamic
model is stable. We employ a general model of contact compliance
to derive stability criteria for planar mechanical systems.
In particular, we show that for cases with one sliding contact,
there is always at most one stable solution. Our approach is
not directly applicable to transitions between rolling and
sliding where the Coulomb friction law is discontinuous. To
overcome this difficulty, we introduce a smooth nonlinear friction
law, which approximates Coulomb friction. Such a friction model
can also increase the efficiency of both rigid body and compliant
contact simulation. Numerical simulations for the different
models and comparison with experimental results are also presented.
MS-CIS-00-09
Osman Ertugay, Michael Hicks, Jessica Kornblum and Jonathan
Smith
The ubiquity and complexity of modern networks require automated
management and control. With increases in scale, automated
solutions based on simple data access models such as SNMP will
give way to more distributed and algorithmic techniques. This
article outlines present and near-term solutions based on the
ideas of active networks and mobile agents, which permit sophisticated
programmable control and management of ultra large scale networks.
MS-CIS-00-10
Fred Azar
Multiple Attribute Decision Making (MADM) involves "making
preference decisions (such as evaluation, prioritization, selection)
over the available alternatives that are characterized by multiple,
usually conflicting, attributes". The problems of MADM are
diverse, and can be found in virtually any topic. In this paper,
we use three different scoring methods for evaluating the performance
of different imaging techniques used to detect cancers in the
female breast. The need for such a decision support system
arises from the fact that each of the several techniques which
helps diagnose breast cancer today, has its own specific characteristics,
advantages and drawbacks. These characteristics or attributes
are generally conflicting. The goal is to detect as many malignant
lesions in the breast as is possible, while identifying the
maximum number of benign lesions. The four imaging techniques
that are compared here are Magnetic Resonance Imaging (MRI),
Mammography, Ultrasonography, and Nuclear Medicine. The three
different multiattribute scoring methods are the Simple Additive
Weighting method (SAW), the Weighted Product Method (WPM),
and the Technique for Order Preference by detail, and then
used to rank the four imaging techniques. The results are analyzed
and the validity and robustness of the methods are tested using
post-evaluation analysis.
MS-CIS-00-11
Fred Azar
Breast cancer is the most commonly diagnosed cancer and the
second leading cause of cancer death among women in America.
A few years ago the odds of developing breast cancer were reported
as 1 in 13. Now the chance is 1 in 9. The only way today to
find out for sure if a breast lump or abnormal tissue is cancer,
is by having a biopsy: A suspicious tissue is removed by a
surgical excision or needle biopsy and is examined under a
microscope by a pathologist who makes the diagnosis. Imaging
techniques of the breast are therefore vital since they will
allow early detection of cancer, and localization of the suspicious
lesion in the breast for a biopsy procedure.
MS-CIS-00-12
Jonathan Moore and Scott M. Nettles
Recent research in active networking has motivated the use
of programmable, or active, packets in which a traditional
packet header is replaced by a program that controls a packet's
actions in the network. Despite the popularity of this idea
in the active networking community, it has not taken hold in
general. We claim that this is because the current active packet
systems are not sufficiently practical.
Our goal is to consider why current systems are not practical
and to propose directions that will facilitate movement towards
practical programmable packets. To this end, we first establish
a framework that defines what it means to be "practical". Next,
we look at the existing "first-generation" active packet systems,
paying particular regard to the key aspects of our framework.
This survey is one of the major contributions of this paper.
Finally, we discuss the overall lessons we draw from the first
generation systems and present a view of what "second-generation" systems
should consist of. We illustrate our views on second-generation
systems by using SNAP (Safe Networking with Active Packets),
a second-generation system we are currently exploring.
MS-CIS-00-13
Karl Crary, Michael Hicks and Stephanie Weirich
We present the design and implementation of a framework for
flexible and safe dynamic linking of native code. Our approach
extends Typed Assembly Language with a primitive for loading
and typechecking code, which is flexible enough to support
a variety of linking strategies, but simple enough that it
does not significantly expand the trusted computing base. Using
this primitive, along with the ability to compute with types,
we show that we can program many existing dynamic
linking approaches. As a concrete demonstration, we have used
our framework to implement dynamic linking for a type-safe
dialect of C, closely modeled after the standard linking facility
for Unix C programs. Aside from the unavoidable cost of verification,
our implementation performs comparably with the standard, untyped
approach.
MS-CIS-00-14
Karthikeyan Bhargavan, Carl A. Gunter and Davor Obradovic
MS-CIS-00-15
Karthikeyan Bhargavan, Carl A. Gunter and Davor Obradovic
MS-CIS-00-16
Jane Mulligan and Kostas Daniilidis
Tele-immersion is a new medium that enables a user to share
a virtual space with remote participants. The user is immersed
in a rendered 3D-world that is transmitted from a remote site.
To acquire this 3D description we apply bi-and trinocular stereo
techniques. The challenge is to compute dense stereo range
data at high frame rates, since participants cannot easily
communicate if the processing cycle or network latencies are
long. Moreover, new views of the received 3D-world must be
as accurate as possible. We address both issues of speed and
accuracy and we propose a method for combining motion and stereo
in order to increase speed and robustness.
MS-CIS-00-17
Rama Bindiganavale
Virtual worlds may be inhabited by intelligent agents who
interact by performing various simple and complex actions.
If the agents are human-like (embodied), their actions may
be generated from motion capture or procedural animation. In
this thesis, we introduce the CaPAR interactive system which
combines both these approaches to generate agent-size neutral
representations of actions within a framework called Parameterized
Action Representation (PAR). Just as a person may learn a new
complex physical task by observing another person doing it,
our system observes a single trial of a human performing some
complex task that involves interaction with self or other objects
in the environment and automatically generates semantically
rich information about the action. This information can be
used to generate similar constrained motions for agents of
different sizes.
Human movement is captured by electromagnetic sensors. By computing
motion zero-crossings and geometric spatial proximities, we isolate
significat events, abstract both spatial and visual constraints
from an agent's action, and segment a given complex action into
several simpler subactions. We analyze each independently and
build individual PARs for them. Several PARs can be combined
into one complex PAR representing the original activity. Within
each motion segment, semantic and style information is extracted.
The style information is used to generate the same constrained
motion in other differently sized virtual agents by copying the
end-effector velocity profile, by following a similar end-effector
trajectory, or by scaling and mapping force interactions between
the agent and an object. The semantic information is stored in
a PAR. The extracted style and constraint information is stored
in the corresponding agent and object models.
MS-CIS-00-18
Jonathan T. Moore, Michael Hicks and Scott Nettles
We present SNAP (Safe and Nimble Active Packets), a new scheme
for programmable (or active) packets centered around a new
low-level packet language. Unlike previous active packet approaches,
SNAP is practical: namely, adding significant flexibility over
IP without compromising safety and security or efficiency.
In this work we compare SNAP's flexibility to other active
packet systems, give proof sketches of its novel approach to
resource control, and present experimental data showing SNAP
attains performance extremely close to that of a software IP
router.
MS-CIS-00-19
Chandra Chekuri and Sanjeev Khanna
A classical scheduling problem is to find schedules that
minimize average weighted completion time of jobs with release
dates. When multiple machines are available, the machine environments
may range from identical machines (the processing time required
by a job is invariant across the machines) at one end, to unrelated
machines (the processing time required by a job on any machine
is an arbitrary function of the specific machine) at the other
end of the spectrum. While the problem is strongly NP-hard
even in the case of a single machine, constant factor approximation
algorithms have been known for even the most general machine
environment of unrelated machines. Recently, a polynomial-time
approximation scheme (PTAS) was discovered for the case of
identical parallel machines [1]. In contrast, it is known that
this problem is MAX SNP-hard for unrelated machines [10]. An
important open problem is to determine the approximability
of the intermediate case of uniformly related machines where
each machine i has a speed si and
it takes p/si time to executing a job of
processing size p. In this paper, we resolve this problem
by obtaining a PTAS for the problem. This improves the earlier
known ratio of (2 + eps) for the problem.
MS-CIS-00-20
Geoffrey Egnal
Traditional stereo systems often falter over changes in lighting
between their two views. Unfortunately, such changes often occur
when using stereo with a wide baseline or between images from
different spectra. In this paper, we propose a new dense stereo
correspondence similarity metric, mutual information, which has
the potential to overcome such adverse conditions. We explore
the strengths and weaknesses of this metric, both quantitatively
and qualitatively, undera variety of conditions. Throughout the
exploration, we compare mutual information to a more traditional
cross-correlation stereo system. We show that mutual information
performs under conditions in which traditional dense stereo fails.
MS-CIS-00-21
Vassilis Prevelakis and Angelos Keromytis
The wide availability of public domain IPsec implementations
allows the creation of VPNs based on low-cost platforms. However,
setting up a VPN node involves a lot of work such as the creation
of IPsec Security Associations and associated tunnels, including
the necessary management of keys. Moreover, routing and firewall
facilities must be provided to ensure the isolation of the
members of the VPN from the public Internet. In this paper
we present a drop-in VPN node that is compact, low-cost and
requires little administration or maintenance. We discuss the
features and advantages of our system. Next, we demonstrate
how this system was used for the creation of a VPN linking
networks within the University campus with others located in
outside locations (e.g. other companies, home networks etc.)
Finally, we present our evaluation of the work performed and
describe our future plans.
MS-CIS-00-22
Osman N. Ertugay and Jonathan M. Smith
Meeting the service demands from Qo-S-based network applications
is a very challenging task performed in many high-end routers
and switches. This task involves management of resources like
bandwidth and memory in network devices. The memory in the
form of a very fast cache that instruments wire-speed classification,
discrimination, and forwarding of network packets needs to
be managed very effectively. We examine the management of a
specific IP flow-cache architecture through simulations based
on traffic traces collected from a campus intranet. A probabilistic
cache install policy is examined over a range of cache sizes
and install probabilities. This policy successfully identifies
the flows that warrant caching and slightly improves deployable
policies based on site-specific traffic information can increase
the switching performance even higher.
MS-CIS-00-23
Arnaud Sahuguet
In this paper we report our experience in building Kweelt,
an open source Java framework for querying XML based on the
recent Quilt proposal. Kweelt is intended to provide a reference
implementation for the Quilt language but also to offer a framework
for all kinds of experiments related to XML including storage,
optimization, query language features, etc. And we report in
this paper on the differences entailed by the use of two different
storage managers, based respectively on character files and
relational databases. An important design decision was to do
a "direct" implementation of Quilt. Instead of relying on preconceptions
(and misconceptions!) inherited from our database query processing
background, we wanted this reference implementation to expose
exactly what is easy and what is hard both in terms of expressiveness
and of efficiency. The process has lead naturally to what may
in hindsight be called mistakes, and to formulate lessons that
will hopefully be used in future implementations to mix-and-match
pieces of existing technology in databases and programming
languages for optimal results.
MS-CIS-00-24
Shih-Schon Lin and Ruzena Bajcsy
Pinhole camera model is a simplified subset of geometric
optics. In special cases like the image formation of the cone
(a degenerate conic section) mirror in an omni-directional
view catadioptric system, there are more complex optical phenomena
involved that the simple pinhole model can not explain. We
show that using the full geometric optics model a true single
viewpoint cone mirror omni-directional system can be built.
We show how such system is built first, and then show in detail
how each optical phenomenon works together to make the system
true single viewpoint. The new system requires only simple
off-the-shelf components and still out performs other single
viewpoint omni-systems for many applications.
MS-CIS-00-25
Image Quality Analysis of Cone Omni-Cam
Shih-Schon Lin and Ruzena Bajcsy
MS-CIS-00-26
Peter Buneman, Susan Davidson, Wenfei Fan, Carmem Hara, Wang-Chiew
Tan
We study two classes of XML keys introduced in [6], and investigate
their associated (finite) implication problems. In contrast
to other proposals of keys for XML, these two classes of keys
can be reasoned about efficiently. In particular, we show that
their (finite) implication problems are finitely axiomatizable
and are decidable in square time and cubic time, respectively.
|
|