Doctoral Dissertation Abstracts (UNC-CH Computer Science)

Lee and Plaisted recently developed a new automated theorem proving strategy called hyper-linking. As part of his dissertation, Lee developed a round-by-round implementation of the hyper-linking strategy, which competes well with other automated theorem provers on a wide range of theorem proving problems. However, Lee's round-by-round implementation of hyper-linking is not particularly well suited for the addition of special methods in support of equality.

In this dissertation, we describe, as alternative to the round-by-round hyper-linking implementation of Lee, a smallest instance first implementation of hyper-linking which addresses many of the inefficiencies of round-by-round hyper-linking encountered when adding special methods in support of equality. Smallest instance first hyper-linking is based on the formalization of generating smallest clauses first, a heuristic widely used in other automated theorem provers. We prove both the soundness and logical completeness of smallest instance first hyper-linking and show that it always generates smallest clauses first under a large class of ordering on clauses. We discuss which of the refinements used by Lee in round-by-round hyper-linking are also applicable to smallest instance first hyper-linking.

We add equality support to smallest instance first hyper-linking using unfailing completion, narrowing, and Brand's equality transformation in a method we call unfailing completion equality support. We show the soundness and logical completeness of smallest instance first hyper-linking with unfailing completion equality support. We also show that Brand's equality transformation is unnecessary for the case where all positive equational literals occur in equational Horn clauses. In particular, this means that for pure equational problems, smallest instance first hyper-linking with unfailing completion equality support simply reduces to an application of unfailing completion.

We conclude the dissertation by describing our preliminary implementation of smallest instance first hyper-linking. We present a comparison of our implementation with that of Lee's on the 2,655 problems in the TPTP Problem Library of Sutcliffe and Suttner.

Aliaga, Daniel G. (1999)
"Automatically Reducing and Bounding Geometric Complexity by Using Images"
Under the direction of Anselmo A. Lastra

Large and complex 3D models are required for computer-aided design, architectural visualizations, flight simulation, and many types of virtual environments. Often, it is not possible to render all the geometry of these complex scenes at interactive rates, even with high-end computer graphics systems. This has led to extensive work in 3D model simplification methods.

We have been investigating dynamically replacing portions of 3D models with images. This approach is similar to the old stage trick of draping cloth backgrounds in order to generate the illusion of presence in a scene too complex to actually construct on stage. An image (or backdrop) once created, can be rendered in time independent of the geometric complexity it represents. Consequently, significant frame rate increases can be achieved at the expense of storage space and visual quality. Properly handling these last two tradeoffs is crucial to a fast rendering system.

In this dissertation, we present a preprocessing and run-time algorithm for creating a constant-frame-rate rendering system that replaces selected geometry with images enhanced with depth at each pixel. First, we describe the preprocessing algorithm to automatically bound the geometric complexity of arbitrary 3D models by using images. Second, we explore two general approaches to displaying images, surrounded by geometry, at run time. Third, we present a system tailored to architectural models.

Amburn, Elton P. (1994)
"Development and Evaluation of an Air-to-Air Combat Debriefing System Using a Head-Mounted Display"
Under the direction of Frederick P. Brooks, Jr.

The United States Air Force Red Flag exercise is the premier training experience for fighter pilots. An instrumented range to the north of Nellis AFB, Nevada provides information about aircraft in a Red Flag exercise. The Red Flag Measurement and Debriefing System transmits messages on the high-activity aircraft at a rate of 10 messages per second. These messages contain data such as position, orientation, pilot actions, and aerodynamic variables.

This research created and evaluated a computer system for replay and evaluation of Red Flag air-to-air combat training data. This system can display the air combat data either on a workstation console (a 19-inch CRT) or in a head-mounted display (HMD). A human-performance experiment compared the effectiveness of replaying air combat data using these two display options. Experienced fighter pilots from the 422nd Test and Evaluation Squadron, 57th Test Group, Nellis Air Force Base, Nevada served as subjects for the experiment. Using a computer system to replay and evaluate this type of data is not new; however, using a head-mounted display and evaluating its effectiveness is new.

Quantitative and qualitative data were collected in the human- performance experiment. The quantitative data were collected from probe questions asked during mission replay. The answers to probe questions were used to compute sensitivity as a measure of the effectiveness of the display types. There was no statistically significant difference between the sensitivity of a subject when using the HMD or the 19-inch CRT. However, there was a trend in the subject's performance which favored the HMD. The qualitative data was quite clear and showed a statistically significant difference in the preference of the 19-inch CRT over the HMD.

Arthur, Kevin (2000)
"Effects of Field of View on Performance with Head-Mounted Displays"
Under the direction of Frederick P. Brooks Jr.
Department of Computer Science Technical Report TR00-019
Electronic copy available

The field of view (FOV) in most head-mounted displays (HMDs) is no more than 60 degrees wide--far narrower than our normal FOV of about 200 degrees wide. This mismatch arises mostly from the difficulty and expense of building wide-FOV HMDs. Restricting a person's FOV, however, has been shown in real environments to affect people's behavior and degrade task performance. Previous work in virtual reality too has shown that restricting FOV to 50 degrees or less in an HMD can degrade performance.

I conducted experiments with a custom, wide-FOV HMD and found that performance is degraded even at the relatively high FOV of 112 degrees, and further at 48 degrees. The experiments used a prototype tiled wide-FOV HMD to measure performance in VR at up to 176 degrees total horizontal FOV, and a custom large-area tracking system to establish new findings on performance while walking about a large virtual environment.

FOV was significant in predicting performance of two tasks: searching for and locating a target by turning one's head, and walking through a simple maze-like environment while avoiding walls. Wide FOV (112 degrees or greater) was especially important for the walking task; for it, performance at 112 degrees was 23% less than at 176 degrees. At 48 degrees, performance was 31% less than at 176 degrees. For the search task, performance at 112 degrees was 12% less than at 176 degrees. At 48 degrees, performance was 24% less than at 176 degrees.

Additional analyses of the data show trends that suggest future investigation. Restricting FOV appears to decrease the user's sense of presence, as measured by a questionnaire. VR sickness, also measured by questionnaire, increased with successive exposures to our system within an hour-long session, but stayed at relatively low levels. FOV appears to alter the occurrence of some sickness symptoms, but the data are inconclusive on whether FOV predicts total sickness. I performed additional measures and analyses, including tests of postural instability, distance memory, spatial memory, head-movement behavior, and comparisons with other HMDs and with real-world performance.

Austin Jr., Joseph H. (1973)
"Formal Models of Binding Processes in Control Programs"
Under the direction of Victor L. Wallace

Formal models of control programs are developed for two purposes: (1) to provide a rigorous definition of the concept of a control program, and (2) to formalize the semantics of control programs as a basis for control program programming languages.

It is shown that operating system semantics can be modeled as a rewriting system over graphs. The states of the system, understood as configurations of resources, are modeled by graphs, and the operations or events of the system, understood as changes of the configuration, are modeled by rewriting rules on the graphs.

Applications of the model to major areas of concern to control program design are then discussed:

Hierarchic system design is expressed as (a) elaboration and abstraction of a model and (b) as a relation between two models whereby one is said to be the realization of the other.

Synchronization, sharing, and multiplexing are modeled in terms of the macro-concept of a generalized queue (ordered set) and queuing discipline. Thus the concept of macro-definitions within the model is shown to greatly simplify the description of typical control programs.

Protection and "interrupt" handling are shown to be easily described by the model.

Finally, the model is related to the Petri-net model of asynchronous systems. It is suggested by informal illustration that extension of the Petri-net model to include flow of resources can provide an intuitive overview of the interrelationships of the configuration transitions.

It is concluded that the models provide: (a) a rationally-derived definition of the control program that distinguishes it from other types of programs, (b) a syntactic representation of control program semantics suitable as a basis for a table-driven interpreter, and (c) a methodology for control program design, based on hierarchic elaboration and the resource-flow view of interrelated concurrent processes.

Aylward, Stephen R. (1997)
"Continuous Mixture Modeling via Goodness-of-Fit Cores"
Under the direction of James M. Coggins

This dissertation introduces a new technique for the automated specification of continuous Gaussian mixture models (CGMMs). This approach is ideal for representing distributions that arise in a variety of problems including the driving problem of this dissertation, representing the distribution of the intensities associated with tissues in medical images.

Gaussian mixture models are population density representations formed by the weighted linear combination of multiple, multivariate Gaussian component distributions. Finite Gaussian mixture models are formed when a finite number of discrete component distributions are used. CGMMs are formed when multiple continua of component distributions are used.

The approach to CGMM specification developed here is based on an original structure, the Gaussian goodness-of-fit (GGoF) core. GGoF functions quantify how well a Gaussian having a particular mean and covariance represents the local distribution of samples. GGoF cores capture the continua of Gaussians which well represent a sampled population; they define a CGMM. In this dissertation, Monte Carlo simulations are used to evaluate the robustness of a variety of GGoF functions and binning methods for the specifications of GGoF cores. The log likelihood ratio GGoF function is shown to produce the most accurate and consistent GGoF cores.

In generalized projective Gaussian distributions, similar feature vectors, when projected onto a subset of basis feature vectors, have a Gaussian distribution. In this dissertation, Monte Carlo simulations and ROC analysis are used to demonstrate that for such distributions CGMMs defined using GGoF cores produce accurate and consistent labelings compared to K-means and finite Gaussian mixture models. Additionally, CGMMs do not suffer from the problems associated with determining an appropriate number of components, initializing the component parameters, or iteratively converging to a solution.

Generalized projective Gaussian distributions exist in a variety of real-world data. The applicability of CGMM via GGoF cores to real-world data is demonstrated through the accurate modeling of tissues in an inhomogeneous magnetic resonance image. The extension of CGMM via GGoF cores to high-dimensional data is demonstrated through the accurate modeling of a sampled trivariate anisotropic generalized projective Gaussian distribution.

Azuma, Ronald T. (1995)
"Predictive Tracking for Augmented Reality"
Under the direction of Gary Bishop
Department of Computer Science Technical Report TR95-007
Electronic copy available

In Augmented Reality systems, see-through Head-Mounted Displays (HMDs) superimpose virtual three-dimensional objects on the real world. This technology has the potential to enhance a user's perception of and interaction with the real world. However, many Augmented Reality applications will not be accepted unless virtual objects are accurately registered with their real counterparts. Good registration is difficult, because of the high resolution of the human visual system and its sensitivity to small differences. Registration errors fall into two categories: static errors, which occur even when the user remains still, and dynamic errors caused by system delays when the user moves. Dynamic errors are usually the largest errors. This dissertation demonstrates that predicting future head locations is an effective approach for significantly reducing dynamic errors.

This demonstration is performed in real time with an operational Augmented Reality system. First, evaluating the effect of prediction requires robust static registration. Therefore, this system uses a custom optoelectronic head-tracking system and three calibration procedures developed to measure the viewing parameters. Second, the system predicts future head positions and orientations with the aid of inertial sensors. Effective use of these sensors requires accurate estimation of the varying prediction intervals, optimization techniques for determining parameters, and a system built to support real-time processes.

On average, prediction with inertial sensors is 2 to 3 times more accurate than prediction without inertial sensors and 5 to 10 times more accurate than not doing any prediction at all. Prediction is most effective at short prediction intervals, empirically determined to be about 80 milliseconds or less. An analysis of the predictor in the frequency domain shows the predictor magnifies the signal by roughly the square of the angular frequency and the prediction interval. For specified head-motion sequences and prediction intervals, this analytical framework can also estimate the maximum possible time-domain error and the maximum tolerable system delay given a specified maximum time-domain error.

Future steps that may further improve registration are discussed.

Babich, Wayne A. (1977)
"High Level Data Flow Analysis Using a Parse Tree Representation of the Program"
Under the direction of Medhi Jazayeri

Data flow analysis is a technique for collecting information about the flow of data within computer programs. It is used by optimizing compilers in order to insure the correctness of optimizations as well as by certain program debugging aids.

This dissertation introduces an iterative technique, called the method of attributes, for performing global data flow analysis using a parse tree representation of the source program. The technique is based on a variant of attribute grammars, and permits most control flow structures found in modern algorithmic languages, including unconstrained GOTO's. It is applied to analysis of live variables and to analysis of available expressions; in both cases, time required for analysis of GOTO- less programs is linear in program size (with a small constant of linearity), regardless of the nesting depth of program loops.

This dissertation also describes the importance of producing data flow analysis information "on demand." The demand problem is the problem of supplying a single piece of data flow information upon request from an optimizer or other processor. The method of attributes is applied to demand analysis of live variables.

KEY PHRASES: Data flow analysis; Live variables; Dead variables; Available expressions; Attribute grammars; Demand analysis; Method of attributes; Program optimization; Program annotation.

Computing Reviews Categories 4.12, 5.24

Bajura, Michael A. (1997)
"Merging Real and Virtual Environments with Video See-Through Head-Mounted Displays"
Under the direction of Henry Fuchs
Department of Computer Science Technical Report TR98-036
Electronic copy available

This dissertation explores the problem of inserting virtual (computer generated) objects into natural scenes in video-based augmented-reality (AR) systems. The augmented-reality system problems addressed are the shorter-term goal of making synthetic objects appear to be more stable and registered and the longer-term goal of presenting proper occlusion and interaction cues between real and synthetic objects. These results can be achieved in video-based AR systems by directly processing video images of the natural scene in real-time. No additional hardware or additional tracking mechanisms are needed above those currently used in augmented-reality systems.

The implications of this work suggest a different approach to the design of AR tracking systems in which the user's world view is used as part of the tracking process. This work shows that tracking system errors which affect the user's world view can be corrected by measuring these errors dynamically and correcting for them in a way which is not readily apparent or objectionable to the user. This means that either cheaper tracking systems could be used or possibly even no separate tracking system in certain situations. Furthermore, the user's world view can be used to construct a 3-D model of his environment which can be used to model object interaction and occlusion relations. This is the first step toward further work of properly shading and lighting synthetic objects inserted into natural scenes.

A real-time (30 Hz) AR system is demonstrated which uses simple image feature tracking to improve registration and tracking accuracy. This is extended to a more general system which illustrates how reconstruction of natural scene geometry, correct synthetic and real object occlusion, and collision detection could be achieved in real-time. 3-D error analysis is included. A camera calibration appendix contains accuracy measurements.

Banks, David C. (1993)
"Interacting with Surfaces in Four Dimensions Using Computer Graphics"
Under the direction of Stephen M. Pizer
Department of Computer Science Technical Report TR93-011

High-speed, high-quality computer graphics enables a user to interactively manipulate surfaces in four dimensions and see them on a computer screen. Surfaces in 4-space exhibit properties that are prohibited in 3-space. For example, nonorientable surfaces may be free of self-intersections in 4-space. Can a user actually make sense of the shapes of surfaces in a larger-dimensional space than the familiar 3D world? Experiment shows he can. A prototype system called Fourphront, running on the graphics engine Pixel-Planes 5 (developed at UNC-Chapel Hill) allows the user to perform interactive algorithms in order to determine some of the properties of a surface in 4-space. This dissertation describes solutions to several problems associated with manipulating surfaces in 4-space. It shows how the user in 3-space can control a surface in 4-space in an intuitive way. It describes how to extend the common illumination models to large numbers of dimensions. And it presents visualization techniques for conveying 4D depth information, for calculating intersections, and for calculating silhouettes.

Bastos, Rui (1999)
"Superposition Rendering: Increased Realism for Interactive Walkthrough"
Under the direction of Frederick P. Brooks, Jr.

The light transport equation, conventionally known as the rendering equation in a slightly different form, is an implicit integral equation, which represents the interactions of light with matter and the distribution of light in a scene. This research describes a signals-and-systems approach to light transport and casts the light transport equation in terms of convolution. Additionally, the light transport problem is linearly decomposed into simpler problems with simpler solutions, which are then recombined to approximate the full solution. The central goal is to provide interactive photorealistic rendering of virtual environments.

We show how the light transport problem can be cast in terms of signals-and-systems. The light is the signal and the materials are the systems. The outgoing light from a light transfer at a surface point is given by convolving the incoming light with the material's impulse response (the material's BRDF/BTDF). Even though the theoretical approach is presented in directional-space, we present an approximation in screen-space, which enables the exploitation of graphics hardware convolution for approximating the light transport equation.

The convolution approach to light transport is not enough to fully solve the light transport problem at interactive rates with current machines. We decompose the light transport problem into simpler problems. The decomposition of the light transport problem is based on distinct characteristics of different parts of the problem: the ideally diffuse, the ideally specular, and the glossy transfers. A technique for interactive rendering of each of these components is presented as well as a technique for superposing the independent components in a multipass manner in real time.

Given the extensive use of the superposition principle in this research, we name our approach superposition rendering to distinguish it from other standard hardware-aided multipass rendering approaches.

Bellovin, Steven M. (1982)
"Verifiably Correct Code Generation Using Predicate Transformers"
Under the direction of David L. Parnas

For about fifteen years, computer scientists have known how to prove that programs meet mathematical specifications. However, the methodology has satisfied only theoreticians; "practical" programmers have tended to reject it for a variety of reasons. Among these are the difficulty of rigorously defining the function of a program, and the fact that the proofs of correctness tend to be much longer and much more complex that the programs themselves.

We have tackled this problem from two sides. First, we deal with proving compilers correct, a special class of programs for which there exists a rather simple specification of purpose. Second, although we would prefer to have programs which are guaranteed to be correct, we will accept a program where we can easily determine if the output of any given run is correct. People will generally be satisfied with a program that usually runs properly, but will always produce a message if it has not. That way, one can have a great deal of confidence in its output.

Working with a compiler for Dijkstra's language, as defined in A Discipline of Programming, and using predicate transformers for our semantic definitions, we have presented a methodology for showing that individual compilations are correct. This involves verifying formally the basic code templates and many library subroutines, and presenting a set of rules that allows one to perform a pattern match between the generated code and the standard templates. This match, which is fairly easy to perform and could in fact be done by a separate program, is our guarantee that the output of the compiler is correct.

The set of rules we present includes a few restrictions on the compiler, most notably that the object code for a given statement must be uncoupled from the code for any other statement. In general, non- optimizing compilers are not affected by any of our restrictions; our DPL compiler, which was developed independently, was not changed in any way to meet our requirements.

Bentley, Jon L. (1976)
"Divide and Conquer Algorithms for Closest Point Problems in Multidimensional Space"
Under the direction of Donald F. Stanat

The contributions contained in this dissertation can be broadly classified as falling into three areas: multidimensional algorithms, the "divide and conquer" strategy, and principles of algorithm design.

Contributions to multidimensional algorithms are twofold: basic results and basic methods. The results deal with algorithms for determining properties of sets of N points in k dimensional space. Among other results it is shown that the closest pair among the N points can be found in time proportional to N log N and that the nearest neighbor to each point among the N can be found in time proportional to N(log N)^k-1 (for k > 2). The basic methods include an algorithm schema applicable to many multidimensional problems and fundamental concepts for dealing with such problems.

The algorithms in this dissertation demonstrate the power of the divide and conquer strategy. The strategy is shown to be applicable to multidimensional problems. The basic technique is modified in many interesting ways to create faster algorithms.

The final area to which this dissertation contributes is algorithm design. Instead of merely presenting the results herein as finished products, they are arrived at through a detailed development process. This development is one of the few written records of the development of an asymptotically fast algorithm; as such it is a suitable basis for teaching algorithm design. The general principles of algorithm design employed are enumerated.

Bergman, Lawrence D. (1993)
"VIEW--A System for Prototyping Scientific Visualizations"
Under the direction of Frederick P. Brooks, Jr.

Different visual representations emphasize different aspects of scientific information. As a scientist searches for representations that yield the most profound insights, she wants to try a variety of representations quickly and easily. Current visualization systems emphasize the rapid application of visual representations to new datasets, rather than the rapid development of new visual representations.

The dissertation addresses the question, "How can we facilitate exploratory visualization, particularly creation of new representations?" A design-process-based model is proposed. Based on the principles suggested by this model, VIEW, an interactive molecular visualization system, was developed.

The VIEW system provides a two-pronged solution to the proposed problem. First, the system supplies a library of drawing tools. These tools allow the user to sketch geometric representations, specifying database parameters by interactively selecting geometric elements on-screen. Besides generating geometry, drawing tools modify color, change geometric parameters, reposition geometry, and animate groups.

Second, a facility for developing new drawing tools or modifying existing ones allows the user to extend the library. Tools are specified in a C-like script language. With this language, the user defines new representations and customizes the interaction style of the tools. The system is designed to facilitate a rapid code-try-recode cycle. In addition to the interpreted language, a development environment includes a Macintosh-like editor and an interactive debugger that shows in real time the visual effects of changes to tool script.

The dissertation presents the design model, describes the VIEW system, and then demonstrates the utility of this design-process-based visualization system through a series of case-studies.

Biagioni, Edoardo S. (1992)
"Scan Directed Load Balancing"
Under the direction of Gyula A. Mago and Jan F. Prins
Department of Computer Science Technical Report TR91-045
Electronic copy available

Scan Directed Load Balancing is an algorithm for dynamic load balancing on k-dimensional mesh-connected computers. In one dimension, a scan computes the load to the left of each processor and the total load. The difference between the load to the left and the average load times the number of processors to the left is the number of active data points to be shifted to balance the load.

In two dimensions, scans are used to compute the load of each column of data and the load to the left of each column of processors. The difference between the load to the left and the average load times the number of processor columns to the left is the load of the data columns to be shifted by this column of processors; the computation is repeated for the rows. In more than two dimensions, the load is computed for (hyper-) planes of data and is balanced by shifting data (hyper-) planes among processor (hyper-) planes; the basic one-dimensional step of the algorithm is repeated k times.

The algorithm targets applications that can be expressed as local computations on a grid and whose dynamic activity is unevenly distributed. In one such computation, Variable Conductance Diffusion, different pixels diffuse for different numbers of iterations, with those that require many iterations unevenly distributed and, in the absence of load balancing, often located on a small subset of the processors. Scan Directed Load Balancing is effective in speeding up Variable Conductance Diffusion for a class of images (512 X 512 pixel), and very effective for selected images in which only a small fraction of the pixels requires many iterations. This implementation, and that for a parallel interpreter for the functional language FFP that uses Scan Directed Load Balancing to both manage storage and balance load, are for UNC's MasPar MP-1, with 4096 processors embedded in a 2-dimensional mesh.

Scan Directed Load Balancing does not guarantee optimal load balance, but always assigns neighboring data to the same or to neighboring processors, so communication between neighboring data is local and fast.

Bishop, T. Gary (1984)
"Self-Tracker: A Smart Optical Sensor on Silicon"
Under the direction of Henry Fuchs

A new system for real-time, three-dimensional computer input is described. The system will use a cluster of identical custom integrated circuits with outward looking lenses as an optical sensing device. Each custom integrated sensor chip measures and reports the shift in its one-dimensional image of the stationary room environment. These shifts will be processed by a separate general-purpose computer to extract the three-dimensional motion of the cluster. The expected advantages of this new approach are unrestricted user motion, large operating environments, capability for simultaneous tracking of several users, passive tracking with no moving parts, and freedom from electromagnetic interference.

The fundamental concept for the design of the sensor chip relies on a cyclic relationship between speed and simplicity. If the frame rate is fast, the changes from image to image will be small. Small changes can be tracked with a simple algorithm. This simple algorithm can be implemented with small circuitry. The small circuitry lets a single chip hold the complete sensor, both imaging and image processing. Such implementation allows each sensor to be fast because all high-bandwidth communication is done on-chip. This cyclic relationship can spiral up as the design is iterated, with faster and simpler operation, or down, with slower and more complex operation. The system design sequence described here has been spiraling up.

System, sensor, algorithm, and processor designs have each had several iterations. Most recently, a prototype sensor chip has been designed, fabricated, and tested. The prototype includes a one-dimensional camera and circuitry for image tracking that operates at 1000 to 4000 frames per second in ordinary room light. As part of this research, photosensors that operate at millisecond rates in ordinary room light with modest lenses have been designed, tested and fabricated on standard digital nMOS lines. They may be useful for designers of other integrated optical sensors.

Bokinsky, Alexandra (2003)
"Multivariate Data Visualization with Data-Driven Spots"
Under the direction of Frederick Brooks
Electronic copy available

This dissertation addresses an important problem in the visualization of scientific data: Given a family of single-valued functions Fk(x,y) in two dimensions, all sampled on a regular, finite, two-dimensional grid, i,j, devise visualizations that allow each function to be visually discriminated and studied separately and studied for comparisons and correlations with other functions in the family.

I developed a technique called Data-Driven Spots (DDS), where each function Fk(x,y) is sampled, by a random collection of circular Gaussians with a uniform standard deviation, rather than presented in full. Human visual perception estimates the function’s values where it is not represented in the sample. These sampled functions, called layers, are presented overlaid. Each function is sampled and displayed in some regions where the others are not, thus each can be discriminated separately; since all are shown simultaneously, correlations can also be estimated.

Layers are displayed with alpha-blending, such that each layer is distinguished by hue and/or the standard deviation of the Gaussians. Data values are multiplied by the Gaussian at each i,j grid point; the result determines the opacity of that layer at that point. Blended with a neutral gray background, each layer has color saturation at i,j proportional to the modulated data value. Since opacities are displayed, lower layers are mostly visible between the spots on upper layers.

I built a DDS Toolkit that enables users to construct DDS visualizations of function families. Construction of effective DDS visualizations requires interactive exploration of visualization parameters, which the toolkit facilitates. I used the toolkit to prepare visualizations of many kinds of function families; a collection of images is presented.

To evaluate the effectiveness of the DDS technique, I performed user studies. These studies showed that performance on a spatial correlation task was better for overlaid DDS images than side-by-side DDS images, that alpha-blended layers are visually discriminable in the presence of up to seven distractors, and that animation of layers with respect to each other dramatically increases their visual salience. Animation permits a Fk(x,y) to be seen at every i,j over time; human visual perception integrates non-simultaneously displayed values into a coherent understanding.

Bollella, Gregory (1997)
"Slotted Priorities: Supporting Real-Time Computing Within General-Purpose Operating Systems."
Under the direction of Kevin Jeffay
Electronic copy available

Recent advances in network technologies, processor capabilities, and microcomputer system hardware, coupled with the explosive growth of the Internet and on-line data access, have created new demands on personal computer operating systems and hardware. In large part, these demands are for the ability to acquire, manipulate, display, and store multimedia data. The computational processes that successfully acquire and display multimedia data necessarily have deadlines. That is, the computation must be complete before a specified point in time. Currently, no general-purpose operating systems support such real-time processes. We have developed a software architecture, called slotted priorities, that defines a way to add support for real-time computation to existing general-purpose operating systems for uniprocessor machine architectures. The slotted priorities architecture shares the resources of a computing system between a general-purpose operating system and a real-time kernel. Software components called executives manage how an instance of a resource is shared. Executives ensure that the RTK can gain access to the resource at precise times. The resulting operating system will be able to guarantee that certain computations will always} complete before their stated deadline. The modifications to the general-purpose operating system are modest.

The architecture is comprised of a resource model, an execution model, and a programming model. The resource model is a classification of resources according to characteristics relevant to the sharing of the resources between the real-time kernel and the general-purpose operating system. The execution model defines how real-time tasks acquire the processor. The programming model defines how programmers write and think about real-time programs for an implementation of the slotted priorities architecture. Finally, we develop a feasibility test which can determine if a set of periodic real-time threads will all meet their deadlines when executed on a system implementing this architecture.

We describe an implementation of the architecture and a set of experiments that validate the implementation. Two real-time demonstration applications were built and executed on the test implementation. Results and analysis of those applications are also presented.

Britton, Edward G. (1977)
"A Methodology for the Ergonomic Design of Interactive Computer Graphic Systems, and its Application to Crystallography"
Under the direction of Frederick P. Brooks, Jr.

This dissertation presents a methodology for the ergonomic design, or human engineering, of interactive computer graphic systems. It proposes human-factors principles based on linguistic and psychological considerations, and proposes an order for designing the features of a system. As a vehicle for developing this methodology, we designed and built a system, described herein, with which biochemists can determine the structures of macromolecules. Crystallographers have used this over one thousand hours and published chemical results based on their work. We assert that the ease with which crystallographers use this system indicates that our methodology for ergonomic design is useful.

Brown, Peter H. (2002)
"Multiscale Evaluation of 3D Shape Perception in Computer Graphics"
Under the direction of Christina Burbeck

This dissertation describes a tool and associated analysis techniques (collectively called the Multiscale Test of Perceived Shape, or MTOPS) for measuring observers' perceptions of 3D surface orientation in computer-graphics visualizations at multiple spatial scales. Using this tool and techniques, I demonstrated that such multiscale measurements are both possible and fruitful. Specifically, I showed the following:

Observers consistently made different surface-orientation settings at different scales, indicating both that perceived orientation changed across scale and that MTOPS was able to measure that change.

By comparing observers' settings to the stimulus geometry, I could measure the across-scale effects of adding a given depth cue to a visualization. Specifically, I found the following:

Adding stereo to a non-stereo presentation caused the accuracy of observers' settings to improve more at large scale than at small.
Adding head-motion parallax to a stereo presentation caused a modest improvement in observers' accuracy, mostly at small scale.
Adding automatic object motion to a non-stereo presentation improved observers' accuracy substantially, at many scales. Adding user-controlled object motion to a non-stereo presentation gave a less consistent, and for most users smaller, accuracy benefit.

The MTOPS tool and techniques were sufficiently sensitive to capture differences in those multiscale depth-cue effects due to surface complexity and observer knowledge.

Brownlee, Jr., Edward H. (1975)
"Lossiness in Tessellation Automata"
Under the direction of Stephen F. Weiss

A tessellation automaton is an infinite array of finite state automata interacting in a prescribed manner. The state of the entire array at any instant is called its configuration. A tessellation automaton is said to be lossy if its global transition function is not one-to-one, that is, if some configuration has more than one predecessor. Lossiness is shown to be equivalent to three other properties of tessellation automata. One of these leads to a sufficient test for lossiness which is easily applied to the local transition function. A necessary condition is also given. Finally, it is shown that certain kinds of computation cannot be carried out in lossless spaces.

Buttelmann III, H. William (1970)
"Syntax-Semantics Systems As Structure Manipulation Systems: Phrase Structure Grammars and Generalized Finite Automata"
Under the direction of David B. Benson

Dissertation has no abstract.

Cannon, Robert L. (1973)
"State Grammar Parsing"
Under the direction of Stephen F. Weiss

A state grammar may be viewed as a context-free grammar with states. The states control the sequence in which the nonterminal symbols in a sentential form become eligible to be rewritten, giving state grammars the power to generate the class of context-sensitive languages.

An algebraic parsing technique, developed for context-free grammars, has been extended for parsing context-sensitive languages as generated by state grammars. The set of all possible parses for an input string is found by iteration upon a single algebraic expression. The number of iterations is a multiple of the length of the input string.

A second parsing technique uses a recursive transition network as a representational tool for state grammar parsing. For the class of non-left-recursive state grammars the algorithm finds a parse if one exists. A result from the algebraic theory extends this algorithm to apply to a larger class of state grammars.

Carlson, Eric D. (1972)
"Techniques for Analysis of Generalized Data Base Management Systems"
Under the direction of Peter Calingaert

Generalized Data Base Management Systems (GDBMS) are software packages designed to facilitate file creation and maintenance, retrieval, and report generation. Two models are proposed for analyzing GDBMS. The first is a formal model of GDBMS components and capabilities. The second is a general model for designing and describing performance analysis experiments. The formal model offers a simple and precise method for describing GDBMS, and for distinguishing them from other systems. Use of the experimental design model for GDBMS performance analyses clarifies the assumptions, formalizes the analysis, and improves the interpretation of results. The two models are shown to be related, and to encompass a variety of analysis techniques. The proposed techniques are compared with alternatives. Examples of the uses of each model are given; the major examples are analyses of the GDBMS ASAP. Of particular interest are the ASAP experiments which indicate the applicability of sample size calculation techniques, of various forms of random sampling, and of nonparametric analyses.

Chadha, Ritu (1991)
"Applications of Unskolemization"
Under the direction of David A. Plaisted

This dissertation describes a novel method for deriving logical consequences of first-order formulas using resolution and unskolemization. A complete unskolemization algorithm is given and its properties analyzed. This method is then applied to a number of different fields, namely program verification, machine learning, and mathematical induction.

The foremost problem in automating program verification is the difficulty of mechanizing the generation of inductive assertions for loops in a program. We show that this problem can be viewed as one of generating logical consequences of the conditions which are true at the entry to a loop. A complete and sound algorithm for generating loop invariants in first-order logic is described. All previous techniques given in the literature for deriving loop invariants are heuristic in nature and are not complete in any sense.

There are a number of problems associated with machine learning, such as the diversity of representation languages used and the complexity of learning. We present a graph-based polynomial-time algorithm for learning from examples which makes use of the method for generating logical consequences. The representation language used is first-order logic, which enables the algorithm to be applied in a large number of fields where first-order logic is the language of choice. The algorithm is shown to compare favorably with others in the literature, and applications of the algorithm in a number of fields are demonstrated.

The difficulty of mechanizing mathematical induction in existing theorem provers is due to the inexpressibility of the principle of induction in first-order logic. In order to handle mathematical induction of the principle of induction within the framework of first-order logic, it is necessary to find an induction schema for each theorem. We describe two methods for tackling this problem, one of which makes use of our method for generating logical consequences. Most existing methods for mechanizing induction can only handle equational theorems. Our approach is more general and is applicable to equational as well as non-equational theorems.

Chan, Francis H. (1982)
(Biomedical Engineering and Mathematics, UNC-Chapel Hill)
"Evaluating the Perceived Dynamic Range of A Display Device Using Pseudocolor"
Under the direction of Stephen M. Pizer

A methodology has been developed to measure the perceived dynamic range (PDR) of any display scale. Such a methodology involves an observer experiment that measures the total number of just noticeable differences (jnd) across the dynamic range of the display/observer combination.

We used two display scales, namely, the heated-object spectrum (HCS), a pseudocolor scale, and the black and white gray scale in our experiment. We found the HCS to have 38% more discernible levels than the gray scale in one observer. Even though there was variability among observers, the error within the last two sets of results in each of the three observers was about 2%. A moderate learning effect was also shown in the first two sets of experiments in one observer.

Our results were also compared with Frei and Baxter's perception model. Good correlation was obtained in the model.

We believe that the definitions underlying the PDR and the methodology of its measurement will be useful for the purpose of comparing display devices in imaging. The jnd-curve (of a display device) obtained in this method can also provide useful information needed to produce a linear relationship between display-driving intensity and perceived intensity.

Chang, Chun-Fa. (2001)
"LDI Tree: A Sampling Rate Preserving and Hierarchical Data Representation for Image-Based Rendering"
Under the direction of Gary Bishop

Multiple reference images are required to eliminate disocclusion artifacts in image-based rendering based on McMillan's 3D image warping. Simply warping each individual reference image causes the rendering time to grow linearly with the number of reference images. This calls for a new data representation for merging multiple reference images.

In this dissertation I present a hierarchical data representation, the LDI Tree, for merging reference images. It is distinguished from previous works by identifying the sampling rate issue and preserving the sampling rates of the reference images by adaptively selecting a suitable level in the hierarchy for each pixel. During rendering, the traversal of the LDI Tree is limited to the levels that are comparable to the sampling rate of the output image. This allows the rendering time to be driven by the requirements of output images instead of the number of input images. I also present a progressive refinement feature and a hole-filling algorithm implemented by pre-filtering the LDI Tree.

I show that the amount of memory required has the same order of growth as the 2D reference images in the worst case. I also show that the rendering time depends mostly on the quality of the output image, while the number of reference images has a relatively small impact.

Chen, David T. (1998)
"Volume Rendering Guided by Multiscale Medial Models"
Under the direction of Stephen M. Pizer

Volume rendering is the generation of images from discrete samples of volume data. Multiscale medial models describe object shape by linking pairs of fuzzy boundary points at object middles. This dissertation presents a volume rendering method that uses object shape information provided by a multiscale medial model to guide a splatting volume renderer. This work shows how a user can select regions of interest based on objects in order to omit occluding objects, and how object shape can be used to improve weak and noisy boundaries. The amount of computation required is proportional to the number of screen pixel intersections with the medial model derived surface. In the method the renderer finds a most likely boundary point using a Bayesian approach based on the volume directional derivative and a boundary point specified by the medial model.

Chen, Wei Chao (2002)
"Light Field Mapping: Efficient Representation of Surface Light Fields"
Under the direction of Henry Fuchs
Electronic copy available

Recent developments in image-based modeling and rendering provide significant advantages over traditional image synthesis process, including improved realism, simple representation and automatic content creation. Representations such as Plenoptic Modeling, Light Field, and the Lumigraph are well suited for storing view-dependent radiance information for static scenes and objects. Unfortunately, these representations have much higher storage requirement than traditional approaches, and the acquisition process demands very dense sampling of radiance data. With the assist of geometric information, the sampling density of image-based representations can be greatly reduced, and the radiance data can potentially be represented more compactly. One such parameterization, called Surface Light Field, offers natural and intuitive description of the complex radiance data. However, issues including encoding and rendering efficiency present significant challenges to its practical application.

In this dissertation, I present a method for efficient representation and interactive visualization of surface light fields. I propose to partition the radiance data over elementary surface primitives and to approximate each partitioned data by a small set of lower-dimensional discrete functions. By utilizing graphics hardware features, the proposed rendering algorithm decodes directly from this compact representation at interactive frame rates on a personal computer. Since the approximations are represented as texture maps, I refer to the proposed method as Light Field Mapping. The approximations can be further compressed using standard image compression techniques leading to extremely compact data sets that are up to four orders of magnitude smaller than the uncompressed light field data. I demonstrate the proposed representation through a variety of non-trivial physical and synthetic scenes and objects scanned through acquisition systems designed for capturing both small and large-scale scenes.

Chu, Heng (1994)
"Semantically Guided First-Order Theorem Proving with Hyper- Linking"
Under the direction of David A. Plaisted
Department of Computer Science Technical Report TR94-051
Electronic copy available

An automated theorem prover accepts a set of axioms and a theorem, expressed in a formal logic, and then proves that the theorem logically follows from the axioms. Two basic aspects of a logic are syntax and semantics. Syntax refers to the form of the statements and semantics refers to their meanings. Most current theorem provers conduct proof searching based on syntax only and semantics is rarely used.

In this dissertation we propose a new and complete theorem proving method, called semantic hyper-linking, which makes a substantial use of semantics in an instance-based theorem prover for first-order logic. Semantics is used to generate instances by a combination of unification and enumeration of the Herbrand base. In this method, the proof searching is essentially a process of exhaustively searching for a model of the input problem.

Semantic hyper-linking performs especially well on non- Horn problems whose proofs contain small instances of the input clauses. We also describe several refinements including (1) various model finding strategies to improve model searching without using expensive semantic checks or expanding the search space, (2) the rough resolution method to cooperate with semantic hyper-linking and solve the part of the proof which contains large instances, and (3) the well-known UR resolution to solve the Horn part of the proof.

We have implemented semantic hyper-linking with its refinements, and applied it to over a hundred problems in various domains. Our results show that semantic hyper-linking is indeed a promising technique. Several hard theorems, which many other theorem provers find difficult, have been proved by semantic hyper-linking using no other guidance than the given semantics.

Chung, James Che-Ming (1993)
"Intuitive Navigation in the Targeting of Radiation Therapy Treatment Beams"
Under the direction of Frederick P. Brooks, Jr.
Department of Computer Science Technical Report TR94-025

This research focused on the possible benefits to be gained from using the intuitive navigation made possible by head-mounted displays (HMDs) in the targeting of radiation therapy treatment beams. A tumor surrounded by various types of healthy tissue can present a very complex 3-D situation which must be thoroughly understood for effective treatment to be possible. Conventional 2-D treatment planning suffers from reliance on 2-D diagnostic imaging and dose computations to represent an inherently 3-D problem. Current state-of-the-art treatment planning systems use 3-D models of the patient and compute 3-D dose distributions, but complete exploration of the solution space of possible beam orientations can be hindered by not-so-intuitive navigation controls. The thesis of this dissertation was that head-mounted display will permit freer exploration of the patient anatomy and range of possible beam orientations, thereby resulting in more efficient treatment planning.

To that end, I developed a new, intuitive navigation mode, which used the orientation of a HMD to determine the direction from which its wearer viewed a 3-D model of the patient's anatomy. When the user looked down, he viewed the anatomy from above. Looking up yielded a view from below, and turning his head horizontally in a circle completely scanned around the model. Although it did not have a real-world metaphor, this mode (dubbed Orbital mode) proved to be surprisingly easy to use and well- suited to the task of targeting treatment beams. I compared Orbital mode with more conventional joystick-based rotation in a user study in which radiation oncology professionals designed treatment beam configurations for lung tumor cases. Slightly faster performance was found with Orbital mode, although there appeared to be no significant difference in the quality of the beam configurations. Movement in Orbital mode was more omnidirectional than with the joystick, most likely due to the mechanical construction of the joystick, which preferentially encouraged left-right and forward-back deflection. The overall conclusion from this study was that HMDs in their present state are not appropriate for clinical use, but with future developments in HMD technology, the benefits of intuitive navigation may appear in mainstream radiation treatment planning.

Cohen, Jonathan D. (1998)
"Appearance-Preserving Simplification of Polygonal Models"
Under the direction of Dinesh Manocha

Over the last six years, the automatic simplification of polygonal models has become an important tools for achieving interactive frame rates in the visualization of complex virtual environments. Initial methods employed clever heuristics, but no real quality metrics; then measures of quality for these simplified output models began to develop. This dissertation focuses on the use of error metrics to provide guaranteed error bounds for the simplifications we create. We guarantee bounds on the total appearance of our simplifications with respect to the three major appearance attributes: surface position, surface curvature (normal), and material color.

We present the simplification envelopes and successive mappings algorithms for geometric simplification, two unique approaches that bound the maximum surface-to-surface deviation between the input surface and the simplified output surfaces. We also present the first bound on maximum texture deviation. Using these tools, we develop the first appearance-preserving simplification algorithm. The geometric simplification provides the filtering of the surface position attribute, bounding the error by means of the surface deviation bound. The color and curvature information are stored in texture and normal map structures, which are filtered at run time on a per-pixel basis. The geometry and maps are tied together by the texture deviation metric, guaranteeing not only that the attributes are sampled properly, but that they cover the correct pixels on the screen, all to within a user- or application-supplied tolerance in pixels of deviation.

We have tested these algorithms on polygonal environments composed of thousands of objects and up to a few million polygons, including the auxiliary machine room of a notional submarine model, a lion sculpture from the Yuan Ming garden model, a Ford Bronco model, a detailed "armadillo" model, and more. The algorithms have proven to be efficient and effective. We have seen improvements of up to an order of magnitude in the frame rate of interactive graphics applications, with little or no degradation in image quality.

Cromartie, Robert C. (1995)
"Structure-Sensitive Contrast Enhancement: Development and Evaluation"
Under the direction of Stephen M. Pizer

Display of a digital image is the process by which an array of recorded intensities is presented to a human observer as a light image. A fundamental step in this process is the rule by which the recorded intensities of the original image are mapped to the display-driving intensities of the display device. When performed explicitly, this step is called contrast enhancement. The goal of a contrast enhancement mapping is to help the observer better use the information contained in the intensity variations of the image in the performance of some well-specified task. This dissertation addresses both the problem of designing effective contrast enhancement mappings and the problem of evaluating the resulting techniques for the purpose of choosing between competing methods and for parameter selection for a given method.

First, I describe the development of two new structure-sensitive contrast enhancement techniques, both of which are based on edge-affected diffusion. One, sharpened adaptive histogram equalization (SHAHE), uses edge-affected unsharp masking as a pre-process for contrast-limited adaptive histogram equalization (CLAHE). SHAE has been shown by observer study to offer a significant advantage when used to display radiation therapy portal images.

I then present an experimental framework for using a model observer to evaluate competing display techniques and to find the best parameters for particular methods. My approach uses computer-generated images, Monte Carlo simulation of image noises, both computer generated random noise and structured noise from real images, and a carefully specified task. Using this framework, I conducted a two-stage experiment to select the best parameters for SHAHE for a distance estimation task on radiation oncology portal images. For these experiments, the model was based on Object Representation by Cores, an emerging theory of human object perception currently under development at the University of North Carolina. The experiments demonstrated the feasibility of the framework, and suggested that variations of SHAHE parameters within the subjectively plausible range could make the model's performance vary from slightly better than no enhancement to considerably worse.

Culver, Timothy. (2000)
"Computing the Medial Axis of a Polyhedron Reliably and Efficiently"
Under the direction of Dinesh Manocha
Electronic copy available

The medial axis transform is a fundamental shape operation with applications in many fields. In solid modeling, the MAT has proven a useful tool for finite element meshing, model simplification, and feature recognition. The MAT is also a complete shape representation that could be used in place of a boundary representation. Yet the MAT is not widely used because computing it is difficult both in theory and in practice. For a three-dimensional polyhedral solid, the medial axis consists of quadric surfaces and degree-four algebraic space curves. Computing with high-degree curves and surfaces requires high numerical precision. Most previous methods attempt to avoid such computation by discretizing, or otherwise approximating, the medial axis. The few existing continuous methods are based exclusively on floating-point arithmetic, which leads to reliability problems.

I present a new reliable, continuous algorithm for accurately computing the medial axis of a polyhedron. It is the only continuous medial axis algorithm that is insensitive to roundoff error. Further, my algorithm handles the most common forms of degeneracy. The algorithm is also efficient in a practical sense. The foundation of my approach is exact computation. My MAT representation uses arbitrary-precision rational numbers to describe the medial geometry. My algorithm is based on a point-ordering predicate that is always evaluated correctly.

By its nature, exact computation requires high-precision arithmetic, which is significantly more expensive than hardware-supported floating-point arithmetic. However, my approach avoids the extra expense where feasible, using techniques such as floating-point filters and lazy evaluation. The result is an algorithm whose running time approaches that of floating-point methods when high precision is not required. I demonstrate this assertion by applying my implementation to several complex polyhedral solids.

Danforth, Scott H. (1983)
"DOT: A Distributed Operating System Model of a Tree-Structured Multiprocessor"
Under the direction of Guyla A. Mago

This dissertation presents DOT, a process-oriented design and simulation model for a highly parallel multiprocessor, and describes a complete associated programming system. The design methodology includes the use of layered design, abstract data types, and a process- oriented view of concurrency. Our results demonstrate that these software engineering structuring principles can be successfully applied to the design of highly parallel multiprocessors.

DOT is represented using an executable high-level language that provides support for discrete-event simulation. This allows verification and accurate simulation of the complete programming system, which is composed of three logical levels.

The top, or user level of the programming system is that of FFP (Formal Functional Programming) languages. The middle, or system support level is that of LPL, a low-level concurrent programming language used to define and implement FFP operators on the DOT architecture. The DOT design represents the lowest level of the programming system, a highly parallel tree-structured multiprocessor that directly supports the LPL and FFP languages.

During execution, user programs consisting of FFP language symbols are entered into a linear array of processing cells (the leaves of the binary tree of processors represented in the DOT design), and segments of this array that contain innermost FFP applications execute LPL programs in order to perform the required reductions. The LPL programs for a useful set of FFP primitives are given.

In addition to DOT and the overall programming system, this dissertation presents an analytic model which may be used to derive upper and lower bounds for program execution time. Predictions of the analytic model are compared with simulation results, and various design alternatives and possible extensions are examined.

Davis, Mark C. (1990)
"A Computer for Low Context-Switch Time"
Under the direction of Frederick P. Brooks, Jr.
Department of Computer Science Technical Report TR90-012

A context switch is the suspension of one running process and the activation of another in a multitasking environment. Many applications, such as process control, require frequent context switches among many processes. A context switch requires a substantial amount of time: about 1000 microseconds on a VAX 11/780 and about 500 microseconds on Sun 4/280. Recently introduced computer architectures, such as the SUN 4, have not improved context-switch performance as much as they have improved throughput. A computer architecture with appropriate memory hierarchy can give better support to context switching. The Computer for Low Context-Switch Time (CLOCS) is a computer with such an architecture. Because the architecture has minimum state inside the Central Processing Unit, CLOCS can switch context in less than the time required to execute one instruction. The CLOCS Memory Management Unit provides virtual memory without degrading context- switch time as long as the new process is located in physical memory. Analyses of the architecture show that CLOCS throughout performance approaches the performance of contemporary RISC workstations and that it is well suited for real-time applications. Because these analyses showed promise for the CLOCS architecture, a register-transfer level implementation was designed and simulated to estimate more accurately the performance of a feasible CLOCS computer system. Although many standard implementation techniques were not useful, a technique called short-circuiting reduced memory references by 15%. On the Dhrystone integer benchmark program, CLOCS performed at least 30% as fast as contemporary workstations constructed from the same electronic technologies, and further significant improvement of CLOCS performance is possible. By using this lower bound on CLOCS throughout performance, the proper architecture can be identified for an application with challenging context-switch requirements.

Dunigan Jr., Thomas H. (1978)
"The Design of a Computer System with All-Electronic Files"
Under the direction of Frederick P. Brooks, Jr.

A new computer memory device is postulated and its hardware/software implications are investigated. The memory device is defined to have an access time of ten microseconds and a ten millicent cost-per-bit, slower and cheaper than current main memories but faster than electro-mechanical devices (drums and disks). The current uses of mass memories are investigated, and a set of device parameters that would serve these uses is described. Alternative architectures for interfacing the new device to the central processing unit are analyzed. The analysis shows that treating the new device in a cache-like memory hierarchy yields the most desirable configuration.

Techniques for including the device as part of a multi-level, hardware-controlled cache-like memory hierarchy are investigated. Design decisions affecting the performance between adjacent levels of the hierarchy are analyzed, including block size, fetch and replacement policies, block addressing, store-through, and write-back. Algorithms for determining the number of levels, their capacities, and access times are presented, with analyses of the effect of task-switch time on memory-fault management. The analyses show that optimum cost- performance is obtained when the device is the slowest member of a three-level cache-like memory hierarchy.

Alternatives for address-space and name-space management are analyzed assuming that the new device is part of a billion-byte processor address space. Segmentation schemes and file systems are compared as alternatives for managing the information on the postulated billion-byte, directly addressable device. The analyses show that segmentation is a more effective management policy. The new device's effect on third-generation data management systems and control program structure is investigated. The new device would reduce I/O traffic on existing third generation computing systems by 90%. Most access methods and some utilities can be eliminated and the structure of the operating system is freed from constraints of limited main-memory space.

Dybvig, R. Kent (1987)
"Three Implementation Models for Scheme"
Under the direction of Gyula A. Mago
Department of Computer Science Technical Report TR87-011

This dissertation presents three implementation models for the Scheme Programming Language. The first is a heap-based model used in some form in most Scheme implementations to date; the second is a new stack-based model that is considerably more efficient than the heap-based model at executing most programs; and the third is a new string-based model intended for use in a multiple-processor implementation of Scheme. The heap-based model allocates several important data structures in a heap, including actual parameter lists, binding environments, and call frames. The stack-based model allocates these same structures on a stack whenever possible. This results in less heap allocation, fewer memory references, shorter instruction sequences, less garbage collection, and more efficient use of memory. The string-based model allocates versions of these structures right in the program text, which is represented as a string of symbols. In the string-based model, Scheme programs are translated into an FFP language designed specifically to support Scheme. Programs in this language are directly executed by the FFP machine, a multiple-processor string-reduction computer. The stack-based model is of immediate practical benefit; it is the model used by the author's Chez Scheme system, a high-performance implementation of Scheme. The string-based model will be useful for providing Scheme as a high-level alternative to FFP on the FFP machine once the machine is realized.

Eastman, Caroline M. (1977)
"A Tree Algorithm for Nearest Neighbor Searching in Document Retrieval Systems"
Under the direction of Stephen F. Weiss

The problem of finding nearest neighbors in a document collection is a special case of associative retrieval, in which searches are performed using more than one key. The concept tree algorithm, a new associative retrieval algorithm suitable for document retrieval systems that use similarity measures to select documents, is described. The basic structure used is a binary tree; at each node a set of keys (concepts) is tested to select the most promising branch. Backtracking to initially rejected branches is allowed and often necessary.

The average search time required by this algorithm is O(log2N)k, where N is the number of documents in the collection, and k is a system-dependent parameter. A series of experiments with a small document collection confirm the predictions made using the analytic model; the value of k is approximately 4 in this situation.

The concept tree algorithm is compared with two other searching algorithms, sequential search and clustered search. For large collections, the predicted average search time for a concept tree search is less than that for a sequential search and greater than that for a clustered search. Only the sequential search and the concept tree search guarantee that the near neighbors found are actually the nearest neighbors.

The concept tree search could be used to advantage in some document retrieval systems. The algorithm can also be considered for other applications requiring associative retrieval.

Eberly, David H. (1994)
"Geometric Methods for Analysis of Ridges in N-Dimensional Images"
Under the direction of Stephen M. Pizer
Department of Computer Science Technical Report TR94-066
Electronic copy available

Image segmentation is a process which identifies and labels objects in an image. The goals of this dissertation are to produce an algorithm for segmenting an image in the way that a front-end vision system does, using the local geometry induced by the intensity values of the image, to create multiscale representations of the objects that allow exploration of the details of the image via an interactive computer system, and to provide a formal geometric foundation for multiscale image analysis. The geometric concept of ridges is discussed. These structures are used to describe the shape properties of objects in an image. Various definitions are given for d-dimensional ridge structures of n-dimensional images. Ridges are used in conjunction with multiscale methods to segment an image. The output of the segmentation is a single tree and the objects in the image are represented as unions and differences of subtrees. The tree and image are used as input to a visualization tool which allows the user to explore the image interactively. A formal foundation for multiscale analysis is given which involves non- Euclidean geometry. Metric selection for scale space is naturally related to invariances required for a particular application. The anisotropic diffusion process for generating multiscale data is automatically determined by the metric. Moreover, the metric is used as an aid in developing fast, stable, and adaptive numerical algorithms for solving the nonlinear diffusion equations. This geometric foundation for multiscale analysis provides a natural set of tools for extracting information about objects in an image.

Ellsworth, David A. (1996)
"Polygon Rendering for Interactive Visualization on Multicomputers"
Under the direction of Henry Fuchs

This dissertation identifies a class of parallel polygon rendering algorithms suitable for interactive use on multicomputers, and presents a methodology for designing efficient algorithms within that class. The methodology was used to design a new polygon rendering algorithm that uses the frame-to-frame coherence of the screen image to evenly partition the rasterization at reasonable cost. An implementation of the algorithm on the Intel Touchstone Delta at Caltech, the largest multicomputer at the time, renders 3.1 million triangles per second. The rate was measured using a 806,640 triangle model and 512 i860 processors, and includes back-facing triangles. A similar algorithm is used in Pixel- Planes 5, a system that has specialized rasterization processors, and which, when introduced, had a benchmark score for the SPEC Graphics Performance Characterization Group "head" benchmark that was nearly four times faster than commercial workstations. The algorithm design methodology also identified significant performance improvements for Pixel-Planes 5.

All fully parallel polygon rendering algorithms have a sorting step to redistribute primitives or fragments according to their screen location. The algorithm class mentioned above is one of four classes of parallel rendering algorithms identified; the classes are differentiated by the type of data that is communicated between processors. The identified algorithm class, called sort-middle, sorts screen-space primitives between the transformation and rasterization.

The design methodology uses simulations and performance models to help make the design decisions. The resulting algorithm partitions the screen during rasterization into adaptively sized regions with an average of four regions per processor. The region boundaries are only changed when necessary: when one region is the rasterization bottle-neck. On smaller systems, the algorithm balances the loads by assigning regions to processors once per frame, using the assignments made during one frame in the next. However, when 128 or more processors are used at high frame rates, the load balancing may take too long, and so static load balancing should be used. Additionally, a new all-to-all communication method improves the algorithm's performance on systems with more than 64 processors.

Erikson, Carl M. (2000)
"Hierarchical Levels of Detail to Accelerate the Rendering of Large Static and Dynamic Polygonal Environments"
Under the direction of Dinesh Manocha

Interactive visualization of large three-dimensional polygonal datasets is an important topic in the field of computer graphics and scientific visualization. These datasets can be static, such as walkthrough applications, or dynamic, such as CAD scenarios where a designer moves, adds, or deletes parts. In many cases, the number of primitives in these models overwhelms the rendering performance of current graphics systems. One method for accelerating the rendering of these environments is polygonal simplification. This dissertation describes the creation and application of levels of detail, or LODs, and hierarchical levels of detail, or HLODs, to accelerate the rendering of large static and dynamic polygonal environments. The principal idea of this work is that simplification methods should not always treat objects, or collections of polygons, in a scene independently. Instead, they may be able to produce higher quality and drastic approximations by simplifying disjoint regions of a scene together. This idea is applicable to the creation of LODs for individual objects that consist of unconnected polygons, and for the construction of HLODs, or approximations representing groups of static or dynamic objects.

We present a polygonal simplification algorithm called General and Automatic Polygonal Simplification, or GAPS, that excels at merging disjoint polygons through the use of an adaptive distance threshold and surface area preservation. We use GAPS to create LODs and HLODs for nodes in the scene graphs of large polygonal environments. These approximations enable two rendering modes, one that allows the user to specify a desired image quality and another that targets a frame-rate. When objects in the scene move, our algorithm updates HLODs that have become inaccurate or invalid using asynchronous simplification processes. Our algorithm currently handles scenes with limited rigid-body dynamic movement. We demonstrate its performance on several large CAD environments including a 13 million polygon power plant model. Our approach has achieved nearly an order of magnitude improvement in average rendering speed with little or no loss in image quality for several viewing paths of complex environments.

Faith, Rickard E. (1998)
"Debugging Programs After Structure-Changing Transformation"
Under the direction of Jan F. Prins

Translators convert a program from one language to another, and are used to solve a wide range of problems, such as the construction of compilers, optimizers, and preprocessors. Although many tools support the creation of translators, these tools do not provide integrated support for debugging the translator or the output of the translator.

This dissertation investigates the tracking of information necessary to provide debugging capabilities for those translators that are structured as a set of program transformations operating on a tree-based representation. In this setting I describe how basic debugging capabilities can be automatically and transparently defined without semantic knowledge of the languages being translated. Furthermore, advanced debugging support, relying on the semantics of the languages and transformations, can be incorporated into this basic framework in a systematic manner.

To evaluate this approach I have constructed KHEPERA, a program transformation system with integral support for the construction of debuggers. With this system I have explored debugging capabilities for traditional compiler optimizations, for more aggressive loop and parallelizing transformations, and for the transformation process itself. I also present algorithms that increase the performance of the transformation process.

Faulk, Stuart R.(1989)
"State Determination in Hard-Embedded Systems"
Under the direction of David L. Parnas

"Hard-embedded" describes a class of real-time systems with tight time and memory constraints. We are interested in developing documentation and software for hard-embedded systems that are easy to understand, change, and maintain. Part of what makes these systems difficult to understand or change is a failure to separate concerns where system state information must be shared among system tasks.

We present a systematic approach to 1) writing software requirements, 2) designing software modules, and 3) writing code so loosely connected tasks sharing state information can be developed and understood independently. We construct a formal model for system states and state transitions based on finite state automata. A method for specifying system requirements, based on the model, is developed and applied to a real system. The requirements are realized in the design of an information hiding module that keeps track of state information at run- time. A formal specification of the module interface is provided and we show that the design preserves ease of change for programs sharing state information.

A technique that aids separation of concerns is development of a system as a set of cooperating sequential processes. Where a hard-embedded system is developed as loosely connected processes, a synchronization mechanism must be used to allow processes to signal and synchronize with changes in the system state. Since there are no established criteria for choosing an appropriate synchronization device, we describe a set of objective criteria appropriate for hard-embedded systems. We demonstrate that the State Transition Event (STE) synchronization mechanism satisfies our criteria. As part of that demonstration, we give a procedure for translating a formal specification of synchronization requirements into an implementation in terms of STE variables.

We demonstrate effectiveness of the overall approach by developing a real example from requirements through implementation. Experience with the techniques on a large system (the U.S, Naval Research Laboratory's SCR A-7E aircraft software) is described.

Frank, Geoffrey A. (1979)
"Virtual Memory Systems for Closed Applicative Language Interpreters"
Under the direction of Donald F. Stanat

Closed applicative languages include the FFP languages introduced by Backus in the 1977 Turing lecture. In this work, a class of interpreters for these languages is described. These interpreters are designed to be implemented on machines with a two level storage hierarchy, and are called virtual memory interpreters since they hide the memory hierarchy from the user. Virtual memory interpreters eliminate the need to store the entire program text in main store, and may reduce the execution time and space required to execute some programs by (1) allowing pointers to auxiliary memory to be moved instead of expressions, (2) allowing data sharing in auxiliary store.

A virtual memory interpreter is shown to be a correct implementation of its closed applicative language by describing a virtual memory language for the interpreter, and defining a translation function that (1) maps the expressions of the closed applicative language to the expressions of the virtual memory language and (2) preserves the meanings of the languages.

Mago has designed a cellular processor system for interpreting closed applicative languages that can take full advantage of the potential parallelism in a program if there is enough space in the machine to hold the program throughout execution. In order to demonstrate the capabilities of a virtual memory interpreter, a program for a file update problem is analyzed, and the execution times of this program on a Mago machine and on a virtual memory machine based on a Mago machine are compared. This example indicates that for some programs execution on a virtual memory interpreter can save time and space when compared with execution on a Mago machine.

Fredericksen, R. Eric (1993)
"The Biological Computation of Visual Motion"
Under the direction of Stephen M. Pizer and Willem H. van de Grind (University of Utrecht)

The mechanisms underlying the computation of visual motion in biological systems are explored. Psychophysical experiments in visual perception of apparent motion (sequences of static images as in film, video, or computer controlled displays) were performed using random dot apparent motion stimuli designed to isolate populations of biological motion detectors. The results of these experiments along with extant information in the psychophysical, neurophysiological, and neuroanatomical literature are used to construct mathematical models for the distribution of biological motion detectors in the visual field, and for the mechanisms underlying the combination of motion detector outputs over visual space and time (stimulus duration). The mathematical models are shown to capture the major characteristics of the visibility of motion in humans. The detector distribution is described in terms of the visibility of spatial displacement size and image frame rate, and the dependence of that visibility on stimulus eccentricity in the visual field. The mathematical form of the distribution is a natural consequence of the mapping of visual space to visual cortex combined with a homogeneous distribution of cortical correlation distances, self-organization processes, and the availability of motion information in the visual field. The mechanisms for combination of motion detector responses over visual space and over time are modeled based on known neurophysiology. Preliminary results from simulations of the self-organization of the detector array are consistent with the psychophysical data. A comprehensive model is presented and the implications of the model with respect to the computer controlled display of motion information are discussed.

Fritsch, Daniel S. (1993)
(Biomedical Engineering, UNC-Chapel Hill)
"Registration of Radiotherapy Images Using Multiscale Medial Descriptions of Image Structure"
Under the direction of James Coggins

The representation of object shape in medical images is an important precursor to many common image interpretation needs, including recognition, registration and measurement. Typically, methods for such computer vision tasks require the preliminary step of image segmentation, often via the detection of object edges. This dissertation presents a new means for describing greyscale objects that obviates the need for edge-finding, i.e., classifying pixels as being either inside or outside of an object boundary. Instead, this technique operates directly on the greyscale image intensity distribution to produce a set of "medialness" measurements at every pixel and across multiple spatial scales that capture more global properties of object structure than edge-based methods. When the set of all medialness measurements at some optimal scale of measurement are considered, a ridge-like intensity structure is formed along the middles of objects and a generalized medial axis is obtained by labeling pixels along this ridge and associating a scale value with each axis position. The result of this procedure is an image description called the Multiscale Medial Axis (MMA), which represents the structure of objects in an image at multiple and simultaneous levels of scale, and which provides several desirable properties for describing the shape of greyscale forms. Application of this image description technique to the automatic registration of radiotherapy planning and treatment images is described.

Furst, Jacob D. (1999)
"Height Ridges of Oriented Medialness"
Under the direction of Stephen M. Pizer

Shape analysis of objects is an important aspect of medical image processing. Information gained from shape analysis can be used for object segmentation, object-based registration and object visualization. One shape analysis tool is the core, defined to be a height ridge of a medial strength measure made on an image. In this dissertation I present 3D cores, defined here to be optimal scale-orientation height ridges of oriented medial strength measurements. This dissertation covers:

a medial strength measurement, Blum-like medialness, that is robust, efficient, and insensitive to intrafigural interference,

a new definition for a ridge, the optimal parameter height ridge, and its properties, and

an algorithm, Marching Ridges, for extracting cores.

The medial strength measurement uses Guassian derivatives, so is less sensitive to noise, and responds to object boundaries at points rather than on entire spheres, so is faster to calculate and less sensitive to boundaries of other image figures. The Marching Ridges algorithm uses the grid structure of the image domain to identify ridge points as zero-crossings of first derivatives and to track ridges through the image domain.

Gauch, John M. (1989)
"The Multiresolution Intensity Axis of Symmetry and its Application to Image Segmentation"
Under the direction of Stephen M. Pizer
Department of Computer Science Technical Report TR89-047

A new shape description for grey-scale images called the intensity axis of symmetry (IAS) and an associated curvature-based description called vertex curves are presented. Both of these shape description methods focus on properties of the level curves of the image and combine this information across intensities to obtain representations which capture properties of both the spatial and intensity shape of an image. Methods to calculate and to display both image shape descriptions are described. To provide the necessary coherence across the spatial and intensity dimensions while computing the IAS, the boundary-based active contour method of Kass is extended to obtain a surface-based functional called the active surface. To illustrate the effectiveness of the IAS for image shape description, an interactive image segmentation program which identifies and displays image regions associated with individual components of the IAS is demonstrated. These regions often correspond to sensible anatomical structures in medical images. An analysis of the multiresolution behavior of the IAS reveals that it is possible to impose a quasi-hierarchy on IAS sheets by focusing on the multiresolution properties of much simpler geometric structures: vertex curves approximated by watershed boundaries.

Gauch, Susan E. (1990)
"An Expert System for Searching in Full-Text"
Under the direction of John B. Smith
Department of Computer Science Technical Report TR89-043

This dissertation explores techniques to improve full-text information retrieval by experienced computer users or novice users of retrieval systems. An expert system which automatically reformulates Boolean user queries to improve search results is presented. The expert system differs from other intelligent database functions in two ways: it works with semantically and syntactically unprocessed text; and the expert system contains a knowledge base of domain independent search strategies. The passages retrieved are presented to the user in decreasing order of estimated relevancy. This combination of user interface features provides powerful, yet simple, access to full-text documents.

Experimental results demonstrate that the expert system can improve the search efficiency of novice searchers without decreasing their search effectiveness. Further, an evaluation of the ranking algorithm confirms that, in general, the system presents potentially relevant passages to the user before irrelevant passages.

Glassner, Andrew S. (1988)
"Algorithms for Efficient Image Synthesis"
Under the direction of Frederick P. Brooks, Jr.
Department of Computer Science Technical Report TR90-031

This dissertation embodies six individual papers, each directed towards the efficient synthesis of realistic, three-dimensional images and animations. The papers form four major categories: ray tracing, animation, texture mapping, and fast iterative rendering.

The ray tracing papers present algorithms for efficiently rendering static and animated scenes. I show that it is possible to make use of coherence in both object space and time to quickly find the first intersected object on a ray's path. The result is shorter rendering times with no loss of quality.

The first animation paper considers the needs of a modern animation system and suggests a particular object-oriented architecture. The other animation paper presents an efficient and numerically stable technique for transforming an arbitrary modeling matrix into a fixed sequence of parametric transformations which yield the same matrix when composed. The result is that hierarchical, articulated models may be described by the human modeler or animator with any convenient sequence of transformations at each node, and the animation system will still be able to perform parametrically smooth motion interpolation.

The fast rendering paper describes a system built to allow quick modification of object surface description and lighting. I use a space/time tradeoff to capitalize on the constant geometry in a scene undergoing adjustment. The result is a system that allows relatively fast, iterative modification of the appearance of an image.

The texture mapping paper offers a refinement to the sum table technique. I show that the fixed, rectangular filter footprint used by sum tables can lead to oversampling artifacts. I offer a method which detects when oversampling is likely to occur, and another method for iteratively refining the texture estimate until it satisfies an error bound based on the oversampled area.

Together, these six papers present a collection of algorithms designed to enhance synthetic images and animations and reduce the time required for their creation.

Goddard, Stephen (1998)
"On the Management of Latency in the Synthesis of Real-Time Signal Processing Systems from Processing Graphs"
Under the direction of Kevin Jeffay
Department of Computer Science Technical Report TR98-027
Electronic copy available

Complex digital signal processing systems are commonly developed using directed graphs called processing graphs. Processing graphs are large grain dataflow graphs in which nodes represent processing functions and graph edges depict the flow of data from one node to the next. When sufficient data arrives, a node executes its function from start to finish without synchronization with other nodes, and appends data to the edge connecting it to a consumer node.

We combine software engineering techniques with real-time scheduling theory to solve the problem of transforming a processing graph into a predictable real-time system in which latency can be managed. For signal processing graphs, real-time execution means processing signal samples as they arrive without losing data. Latency is defined as the time between when a sample of sensor data is produced and when the graph outputs the processed signal.

We study a processing graph method, called PGM, developed by the U.S. Navy for embedded signal processing applications. We present formulae for computing node execution rates, techniques for mapping nodes to tasks in the rate-based-execution (RBE) task model, and conditions to verify the schedulability of the resulting task set under a rate-based, earliest-deadline-first scheduling algorithm. Furthermore, we prove upper and lower bounds for the total latency any sample will encounter in the system. We show that there are two sources of latency in real-time systems created from processing graphs: inherent and imposed latency. Inherent latency is t