CS Theses & Dissertations 2004

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

Voronoi diagrams of semi-algebraic sets
Anton, Francois
DOI : 10.14288/1.0051543
URI : http://hdl.handle.net/2429/15860
Degree : Doctor of Philosophy - PhD
Graduation Date : 2004-05

Most of the curves and surfaces encountered in geometric modelling are denned as the set of solutions of a system of algebraic equations and inequalities (semialgebraic sets). Many problems from different fields involve proximity queries like finding the (nearest) neighbours or quantifying the neighbourliness of two objects. The Voronoi diagram of a set of sites is a decomposition of space into proximal regions. The proximal region of a site is the locus of points closer to that site than to any other one. Voronoi diagrams allow one to answer proximity queries after locating a query point in the Voronoi zone it belongs to. The dual graph of the Voronoi diagram is called the Delaunay graph. Only approximations by conies can guarantee a proper order of continuity at contact points, which is necessary for guaranteeing the exactness of the Delaunay graph. The theoretical purpose of this thesis is to elucidate the basic algebraic and geometric properties of the offset to an algebraic curve and to reduce the semialgebraic computation of the Delaunay graph to eigenvalues computations. The practical objective of this thesis is the certified computation of the Delaunay graph for low degree semi-algebraic sets embedded in the Euclidean plane. The methodology combines interval analysis and computational algebraic geometry. The central idea of this thesis is that a (one time) symbolic preprocessing may accelerate the certified numerical evaluation of the Delaunay graph conflict locator. The symbolic preprocessing is the computation of the implicit equation of the generalised offset to conies. The reduction of the Delaunay graph conflict locator for conies from a semi-algebraic problem to a linear algebra problem has been possible through the use of the generalised Voronoi vertex (a concept introduced in this thesis). The certified numerical computation of the Delaunay graph has been possible by using an interval analysis based library for solving zero-dimensional systems of equations and inequalities (ALIAS). The certified computation of the Delaunay graph relies on theorems on the uniqueness of a root in given intervals (Kantorovitch, Moore-Krawczyk). For conies, the computations get much faster by considering only the implicit equations of the generalised offsets.

D'Groove - A Novel Digital Haptic Turntable for Music Control
Beamish, Timothy Mark Edward
DOI : 10.14288/1.0051459
URI : http://hdl.handle.net/2429/15212
Degree : Master of Science - MSc
Graduation Date : 2004-05

Speeding up cloth simulation
Boxerman, Edward Aaron
DOI : 10.14288/1.0051455
URI : http://hdl.handle.net/2429/14973
Degree : Master of Science - MSc
Graduation Date : 2004-05

MILQ
Brochu, Eric
DOI : 10.14288/1.0051458
URI : http://hdl.handle.net/2429/15130
Degree : Master of Science - MSc
Graduation Date : 2004-05

The Summarization of Hierarchical Data with Exceptions
Bu, Shaofeng
DOI : 10.14288/1.0051743
URI : http://hdl.handle.net/2429/15511
Degree : Master of Science - MSc
Graduation Date : 2004-11

Bidirectional Importance Sampling for Illumination from Environment Maps
Burke, David William
DOI : 10.14288/1.0051747
URI : http://hdl.handle.net/2429/16236
Degree : Master of Science - MSc
Graduation Date : 2004-11

Design and Analysis of a Connected Dominating Set Algorithm for Mobile Ad Hoc Network
Cai, Kan
DOI : 10.14288/1.0051731
URI : http://hdl.handle.net/2429/15472
Degree : Master of Science - MSc
Graduation Date : 2004-05

Indexing Spatiotemporal Trajectories with Chebyshev Polynomials
Cai, Yuhan
DOI : 10.14288/1.0051331
URI : http://hdl.handle.net/2429/15433
Degree : Master of Science - MSc
Graduation Date : 2004-05

Topological Manipulation of Isosurfaces
Carr, Hamish
DOI : 10.14288/1.0051287
URI : http://hdl.handle.net/2429/15871
Degree : Doctor of Philosophy - PhD
Graduation Date : 2004-05

In this thesis, I show how to use the topological information encoded in an abstraction called the contour tree to enable interactive manipulation of individual contour surfaces in an isosurface scene, using an interface called the flexible isosurface. Underpinning this interface are several improvements and extensions to existing work on the contour tree. The first, and most critical, extension, is the path seed: a new method of generating seeds from the contour tree for isosurface extraction. The second extension is to compute geometric information called local spatial measures for contours and store this information in the contour tree. The third extension is to use local spatial measures to simplify both the contour tree and isosurface displays. This simplification can also be used for noise removal. Lastly, this thesis extends work with contour trees from simplicial meshes to arbitrary meshes, interpolants, and tessellation cases.

Bluetooth Scatternet Formation and Internetworking with 802.11 and GPRS
Chakrabarti, Satyajit
DOI : 10.14288/1.0051058
URI : http://hdl.handle.net/2429/15546
Degree : Master of Science - MSc
Graduation Date : 2004-11

Designing Haptic Icons to Support an Urgency-Based Turning-Taking Protocol
Chan, Andrew
DOI : 10.14288/1.0051630
URI : http://hdl.handle.net/2429/15550
Degree : Master of Science - MSc
Graduation Date : 2004-11

From Tree Patterns to Generalized Tree Patterns:  On Efficient Evaluation of XQuery
Chen, Zhimin
DOI : 10.14288/1.0051223
URI : http://hdl.handle.net/2429/15489
Degree : Master of Science - MSc
Graduation Date : 2004-05

Parallel Computation of High Demensional Robust Correlation and Covariance Matrices
Chilson, James Caleb
DOI : 10.14288/1.0051624
URI : http://hdl.handle.net/2429/15177
Degree : Master of Science - MSc
Graduation Date : 2004-05

Activism and the Internet:  a socio-policial analysis of how the use of electronic mailing lists affects mobilization in social movement organizations
Cronauer, Katja
DOI : 10.14288/1.0076788
URI : http://hdl.handle.net/2429/15942
Degree : Doctor of Philosophy - PhD
Graduation Date : 2004-05

The main research questions in this thesis are whether use of electronic mailing lists by activist groups furthers or hinders the mobilization of list subscribers, and what role lists play in fostering subscribers' involvement with social activist groups. Two public electronic mailing lists were studied over several months for effects of list use on mobilization. The first was created and predominantly used by the student group APEC-Alert to mobilize against the 1997 APEC Economic Leaders' Meeting in Vancouver, Canada. The second, established by a group in Cologne, Germany, was used by many groups from Cologne and elsewhere who organized against European Union and Great 7 summits in Cologne in 1999. I collected messages posted to these lists, obtained subscribers' responses to questionnaires that I designed, and conducted interviews with subscribers. I used a combination of quantitative and qualitative analyses and drew on concepts from social movement theories. I examined how movement organizers used lists and what effects list messages had on subscribers. I examined whether and how list messages changed subscribers' perceptions of movement organizations and the issues they were concerned with, and whether and how list use prompted movement involvement of inactive subscribers and facilitated continued involvement of already active participants. On both lists, some subscribers were more mobilized to support movement goals, group views, aims and tactics, and to become active. These subscribers had the most personal contact with anti-globalization activists, the most previous experience with activism, and in case of the Cologne list, longer and more recent experiences with activism. Least mobilized subscribers were female and those most deterred by negative movement dynamics. I show that effectiveness of list use for mobilization depends on social location of those in the target pool for subscribers, personal contact between subscribers and movement actors, movement dynamics, organizers' framing efforts, presence of collective identities (which seem difficult to develop without face-to-face contact), degree of trust prevalent between subscribers, and availability of resources to movement actors. I recommend that activists increase online framing efforts, explain how subscribers can become active, facilitate personal contact, improve movement dynamics, and broaden access to list content.

APHIDS:  A Mobile Agent-based Programmable Hybrid Intrnsion Detection and Analysis System
Deeter, Ken
DOI : 10.14288/1.0051224
URI : http://hdl.handle.net/2429/15497
Degree : Master of Science - MSc
Graduation Date : 2004-11

Moving from XML Documents to XML Databases
Du, Fengdong
DOI : 10.14288/1.0051219
URI : http://hdl.handle.net/2429/15239
Degree : Master of Science - MSc
Graduation Date : 2004-05

Dynamic Feature Tracing:  finding Features in Unfamiliar Code
Eisenberg, Andrew David
DOI : 10.14288/1.0051333
URI : http://hdl.handle.net/2429/15520
Degree : Master of Science - MSc
Graduation Date : 2004-11

Comparing Static, Adaptable and Adaptive Menus
Findlater, Leah
DOI : 10.14288/1.0051320
URI : http://hdl.handle.net/2429/15499
Degree : Master of Science - MSc
Graduation Date : 2004-11

Intelligent Support of Interactive Manual Control: Design, Implementation and Evaluation of Look-Ahead haptic Guidance
Forsyth, Benjamin Alexander Charles
DOI : 10.14288/1.0051113
URI : http://hdl.handle.net/2429/16270
Degree : Master of Science - MSc
Graduation Date : 2004-11

Shortest Paths on Uncertain Terrains
Gray, Christopher
DOI : 10.14288/1.0051736
URI : http://hdl.handle.net/2429/15691
Degree : Master of Science - MSc
Graduation Date : 2004-11

Improving Menu Placement Strategies for Pen Input
Hancock, Mark
DOI : 10.14288/1.0051221
URI : http://hdl.handle.net/2429/15253
Degree : Master of Science - MSc
Graduation Date : 2004-05

Object Recognition with Many Local Features
Helmer, Scott
DOI : 10.14288/1.0051737
URI : http://hdl.handle.net/2429/15695
Degree : Master of Science - MSc
Graduation Date : 2004-11

Decision Theoretic Learning of Human Facial Displays and Gestures
Hoey, Jesse
DOI : 10.14288/1.0051546
URI : http://hdl.handle.net/2429/15910
Degree : Doctor of Philosophy - PhD
Graduation Date : 2004-05

We present a vision-based, adaptive, decision-theoretic model of human facial displays and gestures in interaction. Changes in the human face occur due to many factors, including communication, emotion, speech, and physiology. Most systems for facial expression analysis attempt to recognize one or more of these factors, resulting in a machine whose inputs are video sequences or static images, and whose outputs are, for example, basic emotion categories. Our approach is fundamentally different. We make no prior commitment to some particular recognition task. Instead, we consider that the meaning of a facial display for an observer is contained in its relationship to actions and outcomes. Agents must distinguish facial displays according to their affordances, or how they help an agent to maximize utility. To this end, our system learns relationships between the movements of a person's face, the context in which they are acting, and a utility function. The model is a partially observable Markov decision process, or POMDP. The video observations are integrated into the POMDP using a dynamic Bayesian network, which creates spatial and temoral abstractions amenable to decision making at the high level. The parameters of the model are learned from training data using an a-posteriori constrained optimization technique based on the expectation-maximization algorithm. The training does not require labeled data, since we do not train classifiers for individual facial actions, and then integrate them into the model. Rather, the learning process discovers clusters of facial motions and their relationship to the context automatically. As such, it can be applied to any situation in which non-verbal gestures are purposefully used in a task. We present an experimental paradigm in which we record two humans playing a collaborative game, or a single human playing against an automated agent, and learn the human behaviors. We use the resulting model to predict human actions. We show results on three simple games.

Using Structural Context to Recommend Source Code Examples
Holmes, Reid
DOI : 10.14288/1.0103854
URI : http://hdl.handle.net/2429/15619
Degree : Master of Science - MSc
Graduation Date : 2004-11

Tools for Exploring and Editing Crosscutting
Janzen, Doug
DOI : 10.14288/1.0051628
URI : http://hdl.handle.net/2429/15557
Degree : Master of Science - MSc
Graduation Date : 2004-11

Low Dimensional Search for Efficient Texture Synthesis
Kimberley, Fred Albert
DOI : 10.14288/1.0051742
URI : http://hdl.handle.net/2429/15561
Degree : Master of Science - MSc
Graduation Date : 2004-11

Bayesian Formulations of Multiple Instance Learning with Applications to General Object Recognition
Kueck, Hendrik
DOI : 10.14288/1.0051335
URI : http://hdl.handle.net/2429/15680
Degree : Master of Science - MSc
Graduation Date : 2004-11

A Software Framework for Developing High Quality Control Systems for Autonomous Robots
Lahey, Darrell Matthew
DOI : 10.14288/1.0051658
URI : http://hdl.handle.net/2429/15094
Degree : Master of Science - MSc
Graduation Date : 2004-05

Fast Methods for Inference in Graphical Models
Lang, Dustin
DOI : 10.14288/1.0051390
URI : http://hdl.handle.net/2429/15604
Degree : Master of Science - MSc
Graduation Date : 2004-11

Description, Analysis and Prediction of Player Actions in Selected Hockey Game Situations
Li, Fahong
DOI : 10.14288/1.0051170
URI : http://hdl.handle.net/2429/16771
Degree : Master of Science - MSc
Graduation Date : 2004-05

On-line Visual Tracking with Feature-based Adaptive Models
Li, Long
DOI : 10.14288/1.0051115
URI : http://hdl.handle.net/2429/16237
Degree : Master of Science - MSc
Graduation Date : 2004-11

Designing Technology For and with Special Populations:  An Exploration of Participatory Design with People with Aphasia
Moffatt, Karyn Anne
DOI : 10.14288/1.0051334
URI : http://hdl.handle.net/2429/15367
Degree : Master of Science - MSc
Graduation Date : 2004-05

Patchlets: A Method of Interpreting correlation stereo 3D Data
Murray, Don Ray
DOI : 10.14288/1.0051745
URI : http://hdl.handle.net/2429/15995
Degree : Doctor of Philosophy - PhD
Graduation Date : 2004-05

This thesis describes methods for fitting local planar surface elements, that we call patchlets, to 3D data obtained from correlation stereo images. We use these patchlets to robustly extract and estimate bounded planar surfaces from complex and noisy stereo scenes. The patchlet element is a small planar surface the size of a pixel projected onto a world surface. It has a position, a normal direction, a size, and confidence metrics on its position and orientation. The confidence metrics are generated from the noise model of the stereo vision system, which are propagated to 3D point data and then to the patchlet parameters. The patchlets are used to extract larger bounded planar surfaces that are useful for environment modeling. We use a region-growing approach to identify how many surfaces exist in a stereo image and an initial estimate of the surface parameters. We then use Expectation-Maximisation (EM) to refine these surface parameters to an optimal estimate using a probability maximisation approach. The confidence metrics of the patchlet parameters allow proper weighting of patchlet contributions to the probability maximisation solution. We verify by experimental means the accuracy of correlation stereo matching and demonstrate that the patchlet confidence metrics obtained from that accuracy fit expected normal distributions. We compare the results of the patchlet-based surface segmentation to manually constructed ground-truth segmentation and find the segmentation accuracy for a scene ranged from 82% to 93%. We also present a method for filtering noise from correlation stereo disparity images.

Prioritized Constraints in the Design of a Situated Robot
Muyan-Ozcelik, Pinar
DOI : 10.14288/1.0051059
URI : http://hdl.handle.net/2429/15761
Degree : Master of Science - MSc
Graduation Date : 2004-11

Generating Dynamic Verification Tools for Generalized Symbolic Trajectory Evaluation (GSTE)
Ng, Kelvin Kwok Cheung
DOI : 10.14288/1.0051057
URI : http://hdl.handle.net/2429/15772
Degree : Master of Science - MSc
Graduation Date : 2004-11

P2P-HGKM: An Efficient Hierarchical Group Key Management Protocol for Mobile Ad-Hoc Networks
Peng, Peng
DOI : 10.14288/1.0051627
URI : http://hdl.handle.net/2429/15687
Degree : Master of Science - MSc
Graduation Date : 2004-05

Linear time algorithm for parsing RNA secondary structure
Rastegari, Baharak
DOI : 10.14288/1.0051394
URI : http://hdl.handle.net/2429/15658
Degree : Master of Science - MSc
Graduation Date : 2004-05

Realistic Mobility for Manet Simulation
Ray, Suprio
DOI : 10.14288/1.0051707
URI : http://hdl.handle.net/2429/15058
Degree : Master of Science - MSc
Graduation Date : 2004-05

Representing concerns in source code
Robillard, Martin
DOI : 10.14288/1.0051530
URI : http://hdl.handle.net/2429/16009
Degree : Doctor of Philosophy - PhD
Graduation Date : 2004-05

Many program evolution tasks involve source code that is not modularized as a single unit. Furthermore, the source code relevant to a change task often implements different concerns, or high-level concepts that a developer must consider. Finding and understanding concerns scattered in source code is a difficult task that accounts for a large proportion of the effort of performing program evolution. One possibility to mitigate this problem is to produce textual documentation that describes scattered concerns. However, this approach is impractical because it is costly, and because, as a program evolves, the documentation becomes inconsistent with the source code. The thesis of this dissertation is that a description of concerns, representing program structures and linked to source code, that can be produced cost-effectively during program investigation activities, can help developers perform software evolution tasks more systematically, and on different versions of a system. To validate the claims of this thesis, we have developed a model for a structure, called concern graph, that describes concerns in source code in terms of relations between program elements. The model also defines precisely the notion of inconsistency between a concern graph and the corresponding source code, so that it is possible to automatically detect and repair inconsistencies between a description of source code and an actual code base. To experiment with concern graphs, we have developed a tool, called FEAT, that allows developers to iteratively build concern graphs when investigating source code, to view the code related to a concern, and to perform analyses on a concern representation. Using FEAT, we have evaluated the cost and usefulness of concern graphs in a series of case studies involving the evolution of five systems of different size and style. The results show that concern graphs are inexpensive to create during program investigation, can help developers perform program evolution tasks more systematically, and are robust enough to represent concerns in different versions of a system.

Delivering Messages in Disconnected Mobile Ad-Hoc Networks
Shah, Ritesh
DOI : 10.14288/1.0051626
URI : http://hdl.handle.net/2429/15180
Degree : Master of Science - MSc
Graduation Date : 2004-05

Synthesis of Stylized walking controllers for Planar bipeds
Sharon, Dana
DOI : 10.14288/1.0051738
URI : http://hdl.handle.net/2429/15702
Degree : Master of Science - MSc
Graduation Date : 2004-11

Understanding stochastic local search algorithms: An empirical analysis of the relationship between search space structure and algorithm behaviour
Smyth, Kevin
DOI : 10.14288/1.0051395
URI : http://hdl.handle.net/2429/15656
Degree : Master of Science - MSc
Graduation Date : 2004-11

Modelling of Feather Coat Morphogenesis for Computer Graphics
Streit, Lisa Marie
DOI : 10.14288/1.0051558
URI : http://hdl.handle.net/2429/16037
Degree : Doctor of Philosophy - PhD
Graduation Date : 2004-05

This thesis addresses the problem of modelling realistic looking feather coats and their morphogenesis over the lifespan of the bird, for computer graphics. Modelling of feather coats is interesting aesthetically simply because of the prominence of birds in our daily 'lives', as well as the texture, pattern and shape diversities of feathers and feather coats. From a computer graphics point of view it becomes an interesting problem due to the shear detail and complexity of the model that must be managed in a changing environment. Not only is it desirable to simulate changes in the feather coat, but there is also a need for the feathers to respond appropriately when the skin surface moves or is animated. In this thesis three aspects which adversely affect the feather coat's appearance are explored and modelled: feather structure, follicle distribution and feather arrangement. Each aspect takes its basis from attributes of real feather coats, and the results created are compared with real feather coats. In addition to the static creation of feather coats, their change over time (morphogenesis) is also explored and shown to have an adverse affect on the resulting appearance of the coat. The results of feather moulting are included in the morphogenesis and the methodology is both based on real feather coats and the results compared with real feather coats. The focus of this thesis is on modelling the structure of the feather coat, rather than rendering. However, since an adequate rendering methodology is required to assess to results of the structural model a rendering methodology is also investigated. Synthesis of the patterns in feathers is also an interesting problem and is an entire area of research in areas such as Chemistry, Mathematics and Mathematical Biology [Har93]. Since pattern synthesis in feathers is currently an active area of research in these fields, it is deemed outside the scope of this thesis. In order to preserve the realism of our results, acquired patterns are used in this work.

Voronoi Ball Models for Computational Shape Applications
Tam, Roger
DOI : 10.14288/1.0051559
URI : http://hdl.handle.net/2429/16090
Degree : Doctor of Philosophy - PhD
Graduation Date : 2004-05

This thesis evaluates the suitability of Voronoi ball models (VBMs) as a multipurpose shape representation for applications in computer graphics, scientific visualization, and computer vision. The effectiveness of VBMs is judged with respect to six key properties, namely stability, flexibility, accuracy, complexity, efficiency, and intuitiveness. These properties have a significant impact on the range of applicability of a computational shape model. The ability of VBMs to support a number of core shape-driven operations, in particular shape extraction, simplification, matching, interpolation, manipulation, and surface reconstruction, is examined by determining the strength of the key properties in the representation. The general approach is to use VBMs in a number of representative applications, each requiring several of the shape operations being considered. These applications include image matching and interpolation, shape model extraction from image data, two and three-dimensional shape simplification, and polygonal surface reconstruction. The performance of VBMs in these applications is indicative of the extent to which each key property is present. The results of the experiments are very positive. They indicate that a VBM-based shape similarity measure can be effectively applied to quantify 2D shape differences and solve the 2D/3D shape correspondence problem. The findings also show that the VBM and the medial axis can be used together to take advantage of their complementary properties; the VBM gives the medial axis greater stability, while the axis adds connectivity and topological information to the VBM representation. The preservation of the topology of 3D shapes during processing is a particularly strong contribution of the thesis. In addition, the medial axis is shown to enhance the capabilities of the VBM for performing shape simplification and partitioning an object into parts. The experimental results also reveal that VBMs can be effectively used to extract shape information from images and reconstruct polygonal surfaces from point sample data. The primary conclusion made in this thesis is that VBMs are demonstrably capable of supporting a wide variety of shape operations. Additional research is warranted to further exploit the potential of the representation.

An Inexpensive, High Resolution Scan Camera
Wang, Shuzhen
DOI : 10.14288/1.0051621
URI : http://hdl.handle.net/2429/15037
Degree : Master of Science - MSc
Graduation Date : 2004-05

Bayesian Ultrasound Image Analysis on Graphics Hardware
Wei, Qi
DOI : 10.14288/1.0051226
URI : http://hdl.handle.net/2429/15345
Degree : Master of Science - MSc
Graduation Date : 2004-05

QuestVis and Mdsteer: The Visualization of High-Dimensional Environmental Sustainability Data
Williams, Matthew
DOI : 10.14288/1.0051552
URI : http://hdl.handle.net/2429/15921
Degree : Master of Science - MSc
Graduation Date : 2004-05

Enhancing Collaborative Content Delivery with Helpers
Wong, Joseph
DOI : 10.14288/1.0051633
URI : http://hdl.handle.net/2429/16973
Degree : Master of Science - MSc
Graduation Date : 2004-11

Sketch-based Instancing of Parameterized 3D Models
Xiao, Dan
DOI : 10.14288/1.0051323
URI : http://hdl.handle.net/2429/15812
Degree : Master of Science - MSc
Graduation Date : 2004-11

Animation Palette:  An Interface for Prototyping Dynamic Aerial Motions
Zhao, Peng
DOI : 10.14288/1.0051538
URI : http://hdl.handle.net/2429/15851
Degree : Master of Science - MSc
Graduation Date : 2004-11



Find us on Twitter

a place of mind, The University of British Columbia

 

ICICS/CS Building 201-2366 Main Mall
Vancouver, B.C. V6T 1Z4 Canada
Tel: 604-822-3061 | Fax: 604-822-5485
General: help@cs.ubc.ca
Undergrad program: undergrad-info@cs.ubc.ca
Graduate program: grad-info@cs.ubc.ca

Emergency Procedures | Accessibility | Contact UBC | © Copyright The University of British Columbia