CS Theses & Dissertations 2000

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

A Parsing Explanation of Linear Movement Asymmetry in Natural Language
Alphonce, Carl
URI : http://hdl.handle.net/2429/11362
Degree : Doctor of Philosophy - PhD
Graduation Date : 2000-05
Supervisors : Dr. Poole, Dr. Davis

Natural language sentences are made up of words. Groups of words which can act together as a unit are called constituents. Movement is a syntactic process which displaces a constituent from its canonical position. The moved constituent is called a filler. The position from which a filler is displaced is termed a gap. A gap is a particular type of empty category. Interestingly, a filler always appears to the left of its associated gap. My thesis is that this linearity constraint on filler-gap dependencies is not a syntactic constraint but rather a product of the parsing mechanism. I develop a parsing algorithm which can process filler-gap dependencies only if the filler is identified before the gap. What makes this possible in general is that I treat the problem of licensing and identification of empty categories during on-line processing as a case of ambiguity resolution. I develop a fine-grained typology of norninals (both overt and empty) which supports the use of underspecified representations. In turn, this permits the parser to resolve empty category ambiguities incrementally as parsing proceeds. The main results of the dissertation are as follows. The parsing algorithm presented herein offers an explanation for the curious fact that overt movement is leftward. It also explains why, in a language like Italian, postverbal DPs are preferentially interpreted as objects rather than subjects when they appear after optionally transitive verbs. There are also several predictions which arise from this work. The operation of the algorithm predicts that a prenominal relative clause is possible only in a language which permits personal pronouns to act as relative pronouns. There is also predicted to be a filled-gap effect with structures (such as left dislocation in English) for which there is an ambiguity as to whether movement has taken place. Finally, this research supports the view that the human language processing mechanism constructs a single underspecified representation, and resolves ambiguities incrementally as the parse progresses.

Dynamic Light Textures
Brooks, Stephen
URI : http://hdl.handle.net/2429/10244
Degree : Master of Science - MSc
Graduation Date : 2000-05
Supervisor : Dr. Fournier

Efficient generation of contour trees in three dimensions
Carr, Hamish
URI : http://hdl.handle.net/2429/10372
Degree : Master of Science - MSc
Graduation Date : 2000-05
Supervisor : Dr. Snoeyink, Dr. Kirkpatrick

Packet Loss Effects on the Quality of MPEG-Video Transported over IP Networks
Chiu, Daniel Kwok Cheung
URI : http://hdl.handle.net/2429/10250
Degree : Master of Science - MSc
Graduation Date : 2000-05

Supervisor : Dr. neufeld

Learning and Planning in Structured Worlds
Dearden, Richard
URI : http://hdl.handle.net/2429/11051
Degree : Doctor of Philosophy - PhD
Graduation Date : 2000-11
Supervisor : Dr. Boutilier

This thesis is concerned with the problem of how to make decisions in an uncertain world. We use a model of uncertainty based on Markov decision problems, and develop a number of algorithms for decision-making both for the planning problem, in which the model is known in advance, and for the reinforcement learning problem in which the decision-making agent does not know the model and must learn to make good decisions by trial and error. The basis for much of this work is the use of structural representations of problems. If a problem is represented in a structured way we can compute or learn plans that take advantage of this structure for computational gains. This is because the structure allows us to perform abstraction. Rather than reasoning about each situation in which a decision must be made individually, abstraction allows us to group situations together and reason about a whole set of them in a single step. Our approach to abstraction has the additional advantage that we can dynamically change the level of abstraction, splitting a group of situations in two if they need to be reasoned about separately to find an acceptable plan, or merging two groups together if they no longer need to be distinguished. We present two planning algorithms and one learning algorithm that use this approach. A second idea we present in this thesis is a novel approach to the exploration problem in reinforcement learning. The problem is to select actions to perform given that we would like good performance now and in the future. We can select the current best action to perform, but this may prevent us from discovering that another action is better, or we can take an exploratory action, but we risk performing poorly now as a result. Our Bayesian approach makes this tradeoff explicit by representing our uncertainty about the values of states and using this measure of uncertainty to estimate the value of the information we could gain by performing each action. We present both model-free and model-based reinforcement learning algorithms that make use of this exploration technique. Finally, we show how these ideas fit together to produce a reinforcement learning algorithm that uses structure to represent both the problem being solved and the plan it learns, and that selects actions to perform in order to learn using our Bayesian approach to exploration.

The AHI: An Audio and Haptic Interface for Simulating Contact Interactions
Difilippo, Derek Peter
URI : http://hdl.handle.net/2429/10588
Degree : Master of Science - MSc
Graduation Date : 2000-11
Supervisor : Dr. Pai

The Computer Modelling of Fallen Snow
Fearing, Paul Kendall
URI : http://hdl.handle.net/2429/11075
Degree : Doctor of Philosophy - PhD
Graduation Date : 2000-11
Supervisor : Dr. Fournier

One of nature's greatest beauties is the way fresh snow covers the world in a perfect blanket of crystalline white. Snow replaces sharp angles with gentle curves, and clings to surfaces to form ghostly silhouettes. It is said the Inuit have 50 different words for snow, yet even they can be left speechless, as snow is one of the most complex natural materials in existence. This research presents a new model of visual snow accumulation for computer graphics. We are primarily concerned with creating and simulating fallen snow (not falling snow - an important distinction), with our ultimate goal to produce view-independent, static, 3D snow surface models that can be used in artistic and scientific visualisation, film, and advertising. Our contribution is divided into two major components: snow placement and snow stability. Each are essential for modelling the appearance of a thick layer of snowfall on the ground. Snow placement requires us to determine how much snow falls upon the scene, and where it accumulates. We simulate this with an adaptive particle/surface hybrid system that allows for such phenomena as flake flutter, flake dusting and wind-blown snow. We compute snow accumulation by shooting particles upwards towards the sky, giving each source surface independent control over its own sampling density, accuracy and computation time. Importance ordering minimises sampling effort while maximising visual information, generating smoothly improving global results that can be interrupted at any point. Once snow lands on the ground, our stability model moves material away from physically unstable areas in a series of small, simultaneous avalanches. We use a simple local stability test that handles very steep surfaces, obstacles, edges, and snow transit due to wind. Our stability algorithm is flexible enough to simulate other materials, such as flour, sand, and flowing water. We show physical plausibility by comparing various aspects of our approach with real snow images. As proof that our algorithm is flexible and usable, we provide several examples of snow on complex models containing hundreds of thousands of polygons. The completed 3D snow surface model can be easily imported into commercial modelling and rendering software, allowing users to convert existing animations to a brand new season.

Keyhole state space construction with applications to user modeling
Gorniak, Peter John
URI : http://hdl.handle.net/2429/10623
Degree : Master of Science - MSc
Graduation Date : 2000-11
Supervisor : Dr. Poole

Face detection by facets: combined bottom-up and top-down search using compound templates
Holst, Glendon Randal
URI : http://hdl.handle.net/2429/10646
Degree : Master of Science - MSc
Graduation Date : 2000-11
Supervisor : Dr. Lowe

A Network Processor Based Message Manager for MPI
Keppitiyagama, Chamath Indika
URI : http://hdl.handle.net/2429/10681
Degree : Master of Science - MSc
Graduation Date : 2000-11
Supervisor : Dr. Wagner

Fast contact evolution for piece wise smooth surfaces
Kry, Paul Gregory
URI : http://hdl.handle.net/2429/10690
Degree : Master of Science - MSc
Graduation Date : 2000-11
Supervisor : Dr. Pai

Robust Sculpting Using Boundary Represented Solids
Lee, Cedric Ching
URI : http://hdl.handle.net/2429/10705
Degree : Master of Science - MSc
Graduation Date : 2000-11
Acting Supervisor : Dr. Booth

The Computational Geometry of Hydrology Data in Geographic Information Systems
McAllister, Michael
URI : http://hdl.handle.net/2429/10824
Degree : Doctor of Philosophy - PhD
Graduation Date : 2000-05
Supervisors : Dr. Snoeyink, Dr. Kirkpatrick

Computational geometry counts geographic information systems (GIS) among its application areas. GIS data sets are large and are related to the Earth's surface by geometric coordinates. These properties mesh with geometry algorithms and their asymptotic analyses. This dissertation investigates the geometry in a specialized set of GIS problems, namely finding river network centrelines and finding watershed boundaries. Our goal is to create robust and consistent algorithms that solve these problems efficiently. When finding river network centrelines, the main issue is the robustness of the algorithm. The medial axis is an excellent centreline for a river or lake, but few robust implementations exist. Moreover, the medial axis uses parabolic segments, which are harder to represent accurately than line segments. We approximate the medial axis with a piecewise-linear structure that we compute with a robust algorithm for point Voronoi diagrams. Our approximation provides estimates of river area and associates the points on the centreline with the nearest river bank points, much like the medial axis. In turn, we use this association to identify opposite points along river banks. When finding watershed boundaries on triangulated terrains, we focus on finding an algorithm that is consistent with the terrain. In previous work, Nelson et al. [66] locate regions that drain to a common location, but their solution can be disconnected in degenerate cases. We propose a vector algorithm whose watersheds are consistent with the assumption on how water flows on the terrain; the algorithm guarantees one polygon per watershed. Our algorithm finds the watershed boundaries for local minima in the terrain in O(n log n + k) worst-case time where n is the number of points that model the terrain and k is the complexity of the watershed boundaries. We apply our solutions for these GIS problems to data in the British Columbia TRIM (Terrain Resource Inventory Mapping) format. For river networks, we find centrelines for the Fraser River in British Columbia and for a subset of its tributaries. We link these centrelines into a single river network. We have used this network to model the migration of salmon. For watersheds, we identify the boundaries of watersheds in the mountains north of Vancouver, British Columbia and compare the boundaries with manually-digitized watersheds of the same region.

Sharing and Privacy using Untrusted Storage
Ofir, Jacob
URI : http://hdl.handle.net/2429/10736
Degree : Master of Science - MSc
Graduation Date : 2000-11
Supervisor : Dr. Feeley

Automatic measurement and modelling of contact sounds
Richmond, Joshua Lee
URI : http://hdl.handle.net/2429/10736
Degree : Master of Science - MSc
Graduation Date : 2000-11
Supervisor : Dr. Pai

Evaluating and Improving the Accuracy of Computational Gene-Finding on Mammalian DNA Sequences
Rogic, Sanja
URI : http://hdl.handle.net/2429/10747
Degree : Master of Science - MSc
Graduation Date : 2000-11
Supervisor : Dr. Mackworth

The enhanced rate proportional differentiation model for the future internet differentiated services
Shi, Xizheng
URI : http://hdl.handle.net/2429/10967
Degree : Master of Science - MSc
Graduation Date : 2000-11
Supervisor : Dr. Vuong

Invariant Representation of Image Functions under Gamma Correction and Similarity Transformations
Siebert, Andreas
URI : http://hdl.handle.net/2429/11216
Degree : Doctor of Philosophy - PhD
Graduation Date : 2000-11
Supervisor : Dr. Woodham

This work focuses on image retrieval and recognition in environments where the images are subject to a non-linear brightness change known in image processing as gamma correction. Our empirical data shows that gamma correction changes images significantly, resulting in poor retrieval results if not addressed. The proposed solution is based on a novel differential invariant under this kind of radiometric transformation. Since imaged objects are often subject not only to radiometric changes but also to variations of the scene geometry, we propose a representation of two-dimensional image functions that is simultaneously invariant under gamma correction and some geometric transformations, namely translation, rotation, and scaling. An implementation of the proposed invariants based on derivatives of the Gaussian is given. For gamma correction without geometric scaling, improved image retrieval performance based on the invariant representation is demonstrated in both a template matching scenario and a histogram based retrieval system. The proposed invariants perform unsatisfactorily under scaling. The key reasons for this behavior are discussed, and empirical data on the accuracy of the proposed invariants are provided.

Source-Level Transformations for Improved Formal Verification
Winters, Brian Douglas
URI : http://hdl.handle.net/2429/11014
Degree : Master of Science - MSc
Graduation Date : 2000-11
Supervisor : Dr. Hu

Knowledge Discovery of Temporal Database
Yi, Xiaodong
URI : http://hdl.handle.net/2429/10512
Degree : Master of Science - MSc
Graduation Date : 2000-05
Supervisors : Dr. Tsiknis, Dr. Ng