1993 Graduate Student Research Conference Program (GSRC93)
Session 1:Computer Graphics and Image Analysis
Hierarchical Shape Description and Recognition
Jiangying Zhou and Theo Pavlidis
A critical problem in character recognition is the construction of
a description of character shapes. The major challenge we face in solving
this problem is to find a description that is complete and intrinsic
for the recognition of the shape. We think that a description
which is constructed a priori to the knowledge of a character is
probably perceptually insufficient and inevitably entails some degree of
uncertainty in the recognition of the character.
In this talk we will present a multi-level representation scheme, in which
it is possible to defer an interpretation about a particular part of a shape
if there is not sufficient evidence, and the description is completed in
the subsequent levels.
Volume Sampled Voxelization of Geometric Primitives
Sidney W. Wang and Arie Kaufman
We present a 3D antialiasing algorithm for voxel-based geometric models.
The technique band-limits the continuous object
before sampling it at the desired 3D raster resolution.
The algorithm not only creates voxel models which are free from
object space aliasing, but it also incorporates the image
space antialiasing information as part of the view independent
voxel model.
The resulting alias-free voxel models have been used to model synthetic
scenes, for discrete ray tracing applications.
The discrete ray-traced image is superior in quality to the
image generated with
a conventional surface-based ray tracer, since silhouettes of
objects, shadows, and reflections appear smooth (jaggy-less).
Global Illumination Models for Volume Rendering
Lisa Sobierajski and Arie Kaufman
Global illumination models have been used extensively in the rendering of
classical geometric objects, but have not been rigorously investigated in
the area of volume rendering. Volume rendering techniques typically employ
only a local illumination model for shading, and therefore produce images
without global effects. In this talk the application of global illumination
models to volume rendering will be explored. The use of standard global
illumination models for rendering isosurfaces contained within scalar fields
will be described. A volumetric global illumination model, along with the
associated volume rendering algorithm, will also be presented.
Parallel Volume Rendering
Claudio Sliva and Arie Kaufman
Volume rendering is a powerful, but computational intensive, computer
graphics technique. In recent years its use has grown from small
research applications to industrial medical and geological
applications to name a few. Now even PC games use volumetric data.
In this talk a new approach to parallel volume rendering, the
"pipelined parallel ray caster" will be presented. The PPRC currently
runs on networked workstations and the Intel iPSC/860. The algorithm
and the implementation will be described along with latest results.
The VolVis Volume Visualization System
Rick Avila and Arie Kaufman
The VolVis volume visualization system has been developed which contains
a powerful set of tools for displaying and analyzing three dimensional
data. The VolVis system is supported by a generalized abstract model
which provides for both geometric and volumetric constructs. VolVis
also contains several rendering algorithms including ray tracing of
isosurfaces and transparent volumes. In addition, a fast volume rendering
algorithm has been developed, which is capable of exploiting existing
graphics hardware without placing any viewing restrictions or compromising
accuracy. VolVis also includes a volumetric navigation facility, an
animation generator, quantitative analysis tools, and a generalized
protocol for communicating with 3D input devices.
Session 2:
Concurrency and Systems
"Concurrency Factory": A Tool for Design of Distributed Systems
Oleg Sokolsky and Scott Smolka
Communication is the critical part of distributed systems, where
several independent devices or processes perform concurrently.
"Concurrency Factory" is a software tool that allows to design
the communication structure of a distributed system as a
hierarchical network of communicating finite-state automata.
It also provides facilities for simulation of the resulting
system and its verification against a logical or behavioural
specification.
The Semantics of State Refinement in Process Algebra
Andrew Uselton and Scott Smolka
We introduce a state refinement operator into BPA with
recursive specifications and present a comprehensive technical
development of the resulting theory, BPA+SR. Our main technical
results are that bisimulation is a congruence in BPA+SR and that
guarded recursive specifications have unique solutions. We also have
that bisimulation remains a congruence if the merge operator of ACP is
added to BPA+SR. This is significant since action refinement,
another approach to refinement in process algebra, does not in general
preserve semantic equivalences based on interleavings of atomic
actions.
An Integrated Approach to Communication Axioms Among
Concurrent Processes
Rui Hu and Philip Lewis
Currently different kinds of axiom schemas are used to describe
synchronous communication, two-stage shift register communication
and virtual circuit communication. Here we define a common model
to describe those different communications. The underlying idea of
the new model is that the nth receive command gets the value sent
by the nth send command. We have the same axiom schema for all
communications that share this property. The difference between the
communication method is modeled by different termination conditions
for the axioms.
Client-Server Scalability and Reliability
Michael Vernick and Gary Schloss
The increase in power and capacity of workstations and personal computers
has created a trend in the computer industry where enterprises are moving away
from the traditional dumb terminal/main-frame environment and into
the client-server environment. In the client-server architecture (CSA),
the server provides the computing power for shared data manipulation
and access. Our goal is to increase the scalability and reliability
of the CSA system. We present a description of a hybrid architecture
called HCSA (Hybrid Client-Server Architecture) which is a combination
of the CSA and Shared-Disk architectures.
We also present the EWS (Exclusive Write Protocol) where clients
read directly from disk, bypassing the server, but write through the server.
Electronic Design & Test Automation at Stony Brook
Ramesh Sathianathan and David Smith
The design and test of a VLSI circuit is a complicated
process that goes through several phases. At each
phase, the design is represented at a different level
of abstraction. A suite of CAD tools have been developed
at Stony Brook to support the design and test of a circuit,
described in the SBL hardware description language, and
facilitate the generation and test of its equivalent circuit
layout.
Session 3:
Multimedia Systems
Virtual Input Devices for 3D Systems
Taosong He and Arie Kaufman
The device unified interface is a generalized and easily expandable protocol
for the communication between applications and input devices.
The key idea is to unify various
device data into the parameters of a so-called ``virtual input device.''
The device information-base, which includes device dependent information,
is also incorporated into the virtual input device.
Using the device unified interface, system builders are able to
design their applications independent of the input devices as well
as utilize the capabilities of several devices in the same application.
Geographical Information Systems and Data Structures
Cristian Mata and Joe Mitchell
Geographical information systems (GIS) will become more important
as domain independent computing becomes more widespread. Already, applications
pertaining to global orientation, positioning, trajectory tracking are in
use. One of the problems of GIS is that as the area covered by such a system
increases, the complexity of the underlying data structure tends to
grow proportinally. E.g. a city map can be kept in the main memory of
a present day computer but the entire map of a state cannot. One approach
of solving this problem is to reduce the complexity of the map keeping
some desired properties. Mathematically, since most maps are modelled
as graphs or weighted subdivisions, this means the use of graph spanners.
We will present some thoretical results in the field and some practical
applications in the computation of shortest paths.
Near-line Storage Systems
Chitra Venkatramani and Tzi-cker Chiueh
With the coming of multi-media applications and applications that
incorporate large amounts of data into their computations, the need
for a new level in the traditional storage hierarchy has arisen. This
is the near-line storage level that provides fast access to massive
amounts of data. Mass storage devices constitute storage systems of this
kind. A taxonomy of mass storage technologies according to recording
medium, recording mechanism and cost/performance characteristics is
given. The two most important types of mass storage devices, classified
based on the recording medium --- magnetic and optical --- are
discussed in detail. Also, an indepth tutorial on related architectural
issues for computer scientists is provided.
File System Support for Multimedia Applications
Thirumale Niranjan and Gary Schloss
Multimedia (MM) is an application domain that imposes unique demands
on the file underlying system. Previous work assumes that MM is
just another special case, which, like many other applications (most
notably, database systems), should handle its data I/O by implementing
its own file system, usually on a separate disk partition.
In this talk we briefly survey the major challenges that generic
file systems like UNIX FFS must overcome in order to adequately support
MM file storage. Then, we propose and describe a modified file system,
which is very predictably called: Multimedia File System (MMFS), that
in our view can significantly improve FFS performance in a generic
environment of mixed MM and non-MM applications.
Data Models for Multimedia
Michael Wynblatt and Gary Schloss
As multimedia presentations becomes more commonplace,
tools are needed to aid in their development. At Stony
Brook, we are developing a data model which can describe
multimedia's complex characteristics including data stream
synchronization and sequencing, intricate display layout,
and interactivity. Using a layered design, the model
stresses the conceptuual differences between data, data
presentation and data manipulation. The model is designed
as a conceptual tool, but is intended for extension to a
practical development system.
Session 4:
Programming Languages
XSB -- Stony Brook Prolog
Terrance Swift and David Warren
The XSB Programming System is a shareware logic programming system
that includes full functionality of Prolog. A goal of XSB is to tie
together the logical power of Prolog with the declarativeness and
persistence of deductive database systems. To this end, XSB extends
Prolog by adding tabling and HiLog, two features used by the newest
generation of deductive database systems. However XSB's engine
executes at the speed of compiled Prolog and evaluates most programs
faster than available deductive databases can. Version 1.2 is
available by anonymous ftp from sbcs.sunysb.edu.
Determinacy Analysis for Efficient Prolog Execution
Steven Dawson and I. V. Ramakrishnan
In order to realize more fully the potential of Prolog
as a declarative programming language, many performance issues need
to be addressed. Prolog's ability to simulate non-deterministic
computation, while a powerful problem-solving tool, incurs
substantial overhead for programs that express determinate
computations. A sophisticated program analysis method has been
developed at Stony Brook that can reveal at compile time many
kinds of determinate computation that have eluded previous
approaches. This analysis can benefit both sequential and
parallel Prolog implementations.
Trends in Debugging of High-level Programming Languages
Karen Bernstein and Eugene Stark
High-level programming languages abstract the programming process
allowing programmers to concentrate on what their program does rather
than how it does it. Suprisingly, even though debugging is closely
related to programming, debugging for languages such as Prolog and ML
is done at a much lower level of abstraction. Debuggers for high-level
languages require the programmer to reason explicitly about how the
program is executing rather than concentrating on the result. In this
talk, I will explain some of the reasons why debugging is difficult and
survey some popular proposed approaches to simplifying the debugging
process.
Object Oriented Programming
Sergio Martin and Jack Heller
The Object-Oriented paradigm has found a widespread interest in
recent years, both at academia and industry. In the context of
large software projects requiring industrial-quality software,
the Object-Oriented approach is concerned with better ways for
software producers to deliver functionality to software
consumers.
This work proposes an Object Design Representation
targeted to express not only conceptual aspects of the object-oriented
paradigm, but also some of the implementational characteristics found
in object-oriented languages, with particular emphasis on C++.
Return to the GRC home page
If you have problems with this page, please send E-mail to:
evans@cs.sunysb.edu