CS Theses & Dissertations 1999

For 1999 graduation dates (in alphabetical order by last name):

The Effectiveness of Three Dimensional Interaction
Boritz, James
URI : http://hdl.handle.net/2429/9833
Degree : Doctor of Philosophy – PhD
Graduation Date : 1999-05
Supervisor : Dr. Booth

Most interaction with computers today takes place in a two dimensional environment. Even when using three dimensional graphics applications, input is often still restricted to two dimensions. Many believe that the use of three dimensional input devices will alleviate this restriction and allow for a much more natural human-machine dialog. This thesis seeks to establish how factors dealing with visual feedback and task structure affect the ability to perform interactive tasks in a three dimensional virtual environment. The factors investigated were stereoscopic vision, motion parallax, stimulus arrangement and stimulus complexity. Four tasks were studied. These tasks were: point location, docking, line tracing and curve tracing. All the tasks used a six degree of freedom input device to control a pointer in a three dimensional virtual environment. Four experiments corresponding to the four tasks were conducted to investigate these factors. Among other things the results showed the following. Stereoscopic vision provided a strong benefit to positioning-based tasks, but this benefit was weakened in the case of tracing tasks. Motion parallax via head-tracking often had no effect upon task performance and where an effect was found it was often detrimental. The position of stimuli influenced performance across all of the tasks. The orientation of stimuli influenced performance in the task in which it was varied.

Models and Characterizations of 1-way Quantum Finite Automata
Brodsky, Alexander
URI : http://hdl.handle.net/2429/8895
Degree : Master of Science – MSc
Graduation Date : 1999-05
Supervisor : Dr. Pippenger

Computer Assisted 3D craniofacial reconstruction
Bullock, David William
URI : http://hdl.handle.net/2429/9403
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisors : Dr. Forsey, Dr. Snoeyink

A Tool for Formal Verification of DSP Assembly Language Programs
Currie, David William
URI : http://hdl.handle.net/2429/9415
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisor : Dr. Hu

Graph-Theoretic and Geometric Algorithms Associated with Moment-Based Polygon Reconstruction
Durocher, Stephane T.
URI : http://hdl.handle.net/2429/9688
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisor : Dr. Kirkpatrick

Supporting Learners in a Remote Computer-Supported Collaborative Learning Environment:  The Importance of Task and Communication
Graves, David
URI : http://hdl.handle.net/2429/8948
Degree : Master of Science – MSc
Graduation Date : 1999-05
Supervisor : Dr. Klawe

Video Database Retrieval Based on Trajectory Analysis
Gu, Zhe (Jenny)
URI : http://hdl.handle.net/2429/9647
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisor : Dr. Little

Implementations of User Mobility Support for UPC in Java/Corba Environment
Huynh, Thong Tri
URI : http://hdl.handle.net/2429/9661
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisor : Dr. Vuong

Mesh Collapse Compression
Isenburg, Martin
URI : http://hdl.handle.net/2429/9754
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisor : Dr. Snoeyink

A method of light reflectance measurement
Ke, Lun
URI : http://hdl.handle.net/2429/9176
Degree : Master of Science – MSc
Graduation Date : 1999-05
Supervisor : Dr. Fournier

Train Set Bus Controller
Kender, Nana
URI : http://hdl.handle.net/2429/8969
Degree : Master of Science – MSc
Graduation Date : 1999-05
Supervisor : Dr. Greenstreet

Tracking Color Objects in Real Time
Kravtchenko, Vladimir Petrovitch
URI : http://hdl.handle.net/2429/9696
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisor : Dr. Little

An efficient and effective computation of 2-dimensional depth contours
Kwok, Ivy
URI : http://hdl.handle.net/2429/9682
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisor : Dr. Ng

Computer Vision System for Head Movement Detection and Tracking
Lavergne, Anne
URI : http://hdl.handle.net/2429/9683
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisors : Dr. Lowe, Dr. Booth

Semantic Compression and Pattern Extraction with Fascicles
Madar, Jason Chun Sing
URI : http://hdl.handle.net/2429/9180
Degree : Master of Science – MSc
Graduation Date : 1999-05
Supervisor : Dr. Ng

Supporting User Interaction for the Exploratory Mining of Constrained Frequent Sets
Mah, Teresa Beikie
URI : http://hdl.handle.net/2429/9722
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisor : Dr. Ng

Parallel Computation of Data Cubes
Momen-Pour, Soroush
URI : http://hdl.handle.net/2429/9746
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisor : Dr. Wagner

A Constraint-Based Approach for Computing Fault Tolerant Robot Programs
Ralph, Scott
URI : http://hdl.handle.net/2429/11987
Degree : Doctor of Philosophy – PhD
Graduation Date : 1999-11
Supervisor : Dr. Pai

We develop a new framework, based on the Least Constraint, for programming robots to perform a task using a fault tolerant trajectory. We take a specification of the task, expressed as a set of constraints on the robot's configuration over time, and produce a fault tolerant trajectory. The methodology encourages fault tolerant behavior at two levels: first at the task-design phase by encouraging the designer to omit extraneous constraints which reduce the potential for fault tolerant operation, and secondly, at the trajectory generation phase by avoiding critical configurations. The critical configurations are identified via a measure of fault tolerance which is global in nature. The dual optimization of fault tolerance at both the high-level design phase as well as the low-level recoverymotion generation phase allows more of the inherent fault tolerance of the robot to be exploited. We believe that combining these two processes into a single formalism is unique and beneficial. The methodology is unique in its ability to deal with robots which are not kinematically redundant with respect to arbitrary task, but which are sufficiently redundant with respect to the particular task constraints to allow the task to be described as a set of "loose" constraints over time. The constraint-based approach allows us to model faults as additional constraints to the specification, thereby allowing an efficient means of computing the effect a fault will have on the ability to complete the task, using the reduced configuration space of the robot. Faults not previously considered, such as the inclusion of additional obstacles, as well as dynamic information arising from sensors, can also be included using this formalism. An efficient algorithm for constructing a recovery motion for a fault has been developed. A specific example of a seldom considered fault, the collision of the robot with an unknown obstacle, is presented. We show that in addition to detecting the event, we are also able to recover the collision geometry. This information can then be used in a more intelligent recovery motion selection. We have developed a new global fault tolerance measure called longevity. The fault tolerance measure examines a set of faults which may occur at a given configuration, and based on the optimal recovery motions for the given fault, ranks the configuration in its ability to satisfy the future task requirements. Using this fault tolerance measure, a trajectory which maximizes the worst-case failure mode of the robot is computed. A number of experiments show the applicability of the method to a number of domains. We analyze the resulting trajectories with respect to their ability to sustain a fault, and we compare them to more traditional methods for accomplishing the same task. We demonstrate that trajectories obtained using the least constraint specification and the fault tolerance measure are able to achieve a much larger degree of fault tolerance than naive methods for the same task. The fault tolerant trajectories make optimal use of the 1-fault tolerant configuration space, and maximize the worst-case utility of the trajectory given a fault.

Analyzing Exception Flow in JavaTM Programs
Robillard, Martin
URI : http://hdl.handle.net/2429/10164
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisor : Dr. Murphy

Using semantic document representations to increase performance in information retrieval
Rongione, Nicholas Michael
URI : http://hdl.handle.net/2429/9740
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisor : Dr. Rosenberg

Elephant:  The File system that never forgets
Santry, Douglas
URI : http://hdl.handle.net/2429/9748
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisor : Dr. Feeley

Models of 2D-Scene Complexity: A look at the Intrinsic Complexity of Scenes
Sauer, Mark Ryan
URI : http://hdl.handle.net/2429/9749
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisor : Dr. Kirkpatrick

A Three-Tiered Java Application for Secure Transactions over Internet
Siddiqui, Ghazala Yasmeen
URI : http://hdl.handle.net/2429/9264
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisor : Dr. Vuong

Efficient Multimedia retrieval using custom Indexing Method
Steenburgh, Malcolm
URI : http://hdl.handle.net/2429/9059
Degree : Master of Science – MSc
Graduation Date : 1999-05
Supervisor : Dr. Ng

Sound Synthesis for Virtual Reality and Computer Games
van den Doel, Cornelis (Kees)
URI : http://hdl.handle.net/2429/10055
Degree : Doctor of Philosophy – PhD
Graduation Date : 1999-05
Supervisor : Dr. Pai

The synthesis of audio in real-time computer simulations is investigated. A physics based parameterized vibration model for physical objects is constructed, and a realtime synthesis algorithm is developed which allows the synthesis of the sound made by such objects under any kind of interaction force. Methods for obtaining the parameters of such models are investigated. We study mathematical models with simple geometries, parameter fitting to measured data, and empirical models. Models for interaction forces occurring during contacts between rigid bodies such as impact and sliding interactions are developed, as well as models for the driving forces for combustion engines and avalanches. Studies were conducted of several objects which were successfully modeled with these techniques. Several computer programs were written for the testing of models, for the construction of models, and for the demonstration of the level of realism that can be achieved with this type of synthesis. It is concluded that this type of synthesis can generate realistic, interactive audio using only a small fraction of available CPU power on modern personal computers.

Integration of complex shapes and natural patterns
Walter, Marcelo
URI : http://hdl.handle.net/2429/10058
Degree : Doctor of Philosophy – PhD
Graduation Date : 1999-05
Supervisor : Dr. Fournier

The process of generating an image for a computer graphics object is traditionally broken down into three steps: modelling of the shape or geometric attributes (such as height, width, and length), modelling of the visual attributes (how the object is going to look), and an integration step that connects the first two (a visual attribute is defined for every point on the surface of the object). The separation of modelling the shape from modelling the visual attributes makes the whole process highly flexible and powerful; from a conceptual point of view, the process is easier to handle. While generally good for many classes of objects, this separation is prone to problems when the geometry of the object is complex. For example, the mapping of visual characteristics to every point of such complex surfaces is non-trivial. Furthermore, this separation assumes that these two steps are independent of each other, but for some objects, there is an interaction between the shape modelling and visual modelling that plays a significant role on the final image. Typical examples are patterned animals such as giraffes and leopards, where the pattern visible on the fur of an adult animal is the result of a process that took place while the animal was an embryo in the womb. In this case, modelling the interplay between the embryo growth process and the pattern formation process is as important as modelling the individual processes themselves. In this thesis we introduce a novel solution for integrating shape and visual modelling. This solution defines the visual attributes directly on the surface of the object as the object changes shape, for example, due to growth. We present results of applying this solution to a giraffe model. This thesis makes three contributions: (1) a new model of mammalian pattern formation called Clonal Mosaic, suitable for computer graphics purposes and with strong biological plausibility. The model is based on cell division and cell-to-cell interactions, and it can generate repeating spotted and striped patterns occurring in several species of mammals, especially the big cats and giraffes; (2) a technique to modify the shape of an object based, for example, on a small set of input measurements. The technique consists of defining local coordinate systems (cylinders) around the growing parts of the body, each one being transformed according to the relevant growth data while maintaining their relationship with the adjoining parts and the continuity of the surface. The local coordinates also permit ordinary animation mainly as relative rotation such as in articulated objects; and, (3) the integration of the modelling of Clonal Mosaic patterns with the shape modification technique. Finally, this thesis advances the notion of integration of independent tools as an important development in the field of computer graphics. Individual tools have been reaching exceptional levels of performance and therefore we need efficient ways to integrate them smoothly.

Using Idle Workstations to Implement Parallel Prefetch Prediction
Wang, Yongqi (Jasmine)
URI : http://hdl.handle.net/2429/9820
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisor : Dr. Feeley

The Importance of Team Skills for Software Development
Wick, Carolyn
URI : http://hdl.handle.net/2429/8988
Degree : Master of Science – MSc
Graduation Date : 1999-05
Supervisor : Dr. Booth

An MPI messaging Layer for Network Processors
Wijeyeratnam, Aloysius Christopher (Ashley)
URI : http://hdl.handle.net/2429/9809
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisor : Dr. Wagner

SNMP for Mobile Computing
Yin, Qing Vincent
URI : http://hdl.handle.net/2429/9075
Degree : Master of Science – MSc
Graduation Date : 1999-05
Supervisor : Dr. Vuong

An Event-Based Robot Control Architecture
Yu, Jie
URI : http://hdl.handle.net/2429/9282
Degree : Master of Science – MSc
Graduation Date : 1999-11
Supervisor : Dr. Little

A Study of Bandwidth Allocation Mechanisms on sonet-ring based Transport Networks
Zhang, Ding Liang (Dillon)
URI : http://hdl.handle.net/2429/9172
Degree : Master of Science – MSc
Graduation Date : 1999-05
Supervisor : Dr. Neufeld

Coverage Analysis for Conformance Testing of Communication Protocols
Zhu, Jinsong
URI : http://hdl.handle.net/2429/9921
Degree : Doctor of Philosophy – PhD
Graduation Date : 1999-05
Supervisor : Dr. Vuong

Generation of effective test suite and the evaluation of any given test suite are two of the most essential issues in conformance testing. We combine these two aspects and propose quantitative coverage measures that are subsequently used as the basis for generating test suites with any test coverage requirement. Two criteria for coverage measure are studied: a) fault coverage which measures the effectiveness by examining the fault detecting ability of a test suite under a certain fault model, and b) behavior coverage which measures the effectiveness by computing the amount of protocol behavior space that are exercised by a test suite. In the realm of fault coverage, we propose a coverage measure that targets on finite state specifications, typically in the form of I /O Finite State Machines (FSMs). A formal definition and algorithms that compute the measure are given. The computation of the measure is hard in general (no better than NP-complete); however, with search optimization techniques, the performance of our algorithm has been shown to be high and practical for some large protocols. The measure is then utilized to generate additional test cases to a "weak" test suite, thereby producing test suites with better coverage. The enhancement of a test suite can be done incrementally to satisfy a particular coverage requirement. The application of the measure in fault localization is also explored. The above coverage measure is further extended to the case of testing embedded modules of a composite system modeled as a set of communicating FSMs. The problem differs from the isolated module case in that the module under test has limited observability and controllability due to the presence of the test context. We propose an approach that reduces the problem to the case of isolated modules while maintaining observational equivalence at the composite system level. We prove that the calculation of the coverage measure is no better than NP-complete. However, application of the measure to a real life protocol, the protocol that supports the Universal Personal Computing on the Internet, shows that at a higher level of abstraction, the approach remains effective. As a last contribution of the thesis, we studied the coverage measure for behavior coverage based on Labeled Transition System (LTS). We use the basic metric based method [100] as our theoretical foundation. We generalize the basic method to handle protocols extended with data storage in the model of extended LTS. This results in a metric characterization that incorporates the testing distance contribution from data variations. We proved that this generalized metric space possesses the total boundedness and completeness properties, which allows for a test generation and selection process that can approximate the entire protocol space with arbitrary precision.