CS Theses & Dissertations 2013

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

Revisiting recommendations: From customers to manufacturers
Agarwal, Shailendra
DOI : 10.14288/1.0052183
URI : http://hdl.handle.net/2429/45116
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisor : Dr. Lakshmanan

Acquisition of transparent refractive media
Atcheson, Bradley
DOI : 10.14288/1.0052220
URI : http://hdl.handle.net/2429/43621
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-05
Supervisor : Dr. Heidrich

Transparent refractive media are invisible but for the distortions they impart upon a background scene. Computerised acquisition of such media can therefore often not be performed via traditional scanning methods. By capturing refracted backgrounds rather than reflections off the target media itself, we develop techniques for reconstructing the intervening refractive index distribution for both static and time-varying media. The approach is based on tracking optical distortions and then performing tomographic reconstruction. For multi-view tomography we first require a suitably calibrated camera array. To this end we show how to temporally synchronise and geometrically calibrate an array of consumer-grade video cameras that can scale to larger sizes, and at lower cost, than a comparative array of machine vision cameras. For media of low dynamic refractive index range, such as mixing gases, we show how to acquire data and formulate a linear least-squares problem to solve for the refractive index distribution. Unlike traditional methods of fluid flow measurement, ours is non-invasive and fully volumetric. For materials of higher dynamic refractive index range, we develop an alternative acquisition method based on temporally-encoded structured light patterns. Media causing significant distortion of light rays give rise to a large, nonlinear inverse problem. Results indicate that grid resolution relative to the minimum refractive feature size is a key factor limiting the accuracy of reconstructions.

[no title]
Babanezhad Harikandeh, Reza
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisor : Dr. Wohlstadter

TaTAMi: Taint Tracking for Application Migration
Beckman, Lee Alexander
DOI : 10.14288/1.0052192
URI : http://hdl.handle.net/2429/44702
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisors : Dr. Wohlstadter, Dr. Lea (MAGIC)

Capturing fast motion with consumer grade unsynchronized rolling-shutter cameras
Chen, Xing
DOI : 10.14288/1.0052112
URI : http://hdl.handle.net/2429/43538
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisors : Dr. Woodham, Dr. Heidrich

A multi-agent security system for Android platform
Cheng, Zhiyong
DOI : 10.14288/1.0052211
URI : http://hdl.handle.net/2429/43775
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. Vuong

User modeling and data mining in intelligent educational games: Prime Climb a case study
Davoodi, Alireza
DOI : 10.14288/1.0052185
URI : http://hdl.handle.net/2429/45274
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisor : Dr. Conati

Recklessly approximate sparse coding
Denil, Misha
DOI : 10.14288/1.0052215
URI : http://hdl.handle.net/2429/43662
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. de Freitas

Managing on-line submission and marking of programming assignments
Dindar, Nuray
DOI : 10.14288/1.0052207
URI : http://hdl.handle.net/2429/43763
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. Booth

Isossurface stuffing improved: Acute lattices and feature matching
Doran, Crawford
DOI : 10.14288/1.0052176
URI : http://hdl.handle.net/2429/45378
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisor : Dr. Bridson

Herded Gibbs and discretized herded Gibbs sampling
Eskelinen, Mareija
DOI : 10.14288/1.0052182
URI : http://hdl.handle.net/2429/44896
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisor : Dr. de Freitas

Eulerian finite volume method for musculoskeletal simulation and data-driven activation
Fan, Ye
DOI : 10.14288/1.0052197
URI : http://hdl.handle.net/2429/44645
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisor : Dr. Pai

On multi-robot area and boundary coverage
Fazli, Pooyan
DOI : 10.14288/1.0052190
URI : http://hdl.handle.net/2429/44894
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-11
Supervisor : Dr. Mackworth

Distributed coverage aims to deploy a team of robots to move around a target area to perform sensing, monitoring, data collection, search, or distributed servicing tasks. This thesis investigates three variations of the coverage problem. First, we address the multi-robot single coverage of a target area. The aim is to guarantee that every accessible point in the area is visited in a finite time. The proposed algorithm supports heterogeneous robots having various maximal speeds, and is robust to robot failure. It also balances the workload distribution among the robots based on their maximal speeds. The obtained results on the coverage time are scalable to workspaces of different sizes, and robots of varied visual ranges. Second, we tackle the multi-robot repeated coverage of a target area. The objective is to visit all the accessible points of the area repeatedly over time, while optimizing some performance criteria. We introduce four repeated coverage algorithms, and evaluate them under a comprehensive set of metrics including the sum of the paths/tours generated for the robots, the frequency of visiting the points in the target area, and the degree of balance in workload distribution among the robots. We also investigate the effects of environment representation, and the robots' visual range on the performance of the proposed algorithms. The results can be used as a framework for choosing an appropriate combination of repeated coverage algorithm, environment representation, and the robots’ visual range based on the particular workspace and the metric to be optimized. Third, we focus on the multi-robot repeated coverage of the boundaries of a target area and the structures inside it. Events may occur at any position on the boundaries, and the robots are not a priori aware of the event distribution. The goal is to maximize the total detection reward of the events. The reward a robot receives for detecting an event depends on how early the event is detected. To this end, we introduce an online, distributed algorithm and investigate the effects of robots' visual range, communication among the robots, and the event frequency on the performance of the algorithm.

Variant view: visualizing sequence variants in their gene context
Ferstay, Joel Adam
DOI : 10.14288/1.0052187
URI : http://hdl.handle.net/2429/44824
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisors : Dr. Munzner, Dr. Neilsen (Pathology and Laboratory Medicine)

Social influence and its applications : an algorithmic and data mining study
Goyal, Amit
DOI : 10.14288/1.0052213
URI : http://hdl.handle.net/2429/43935
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-05
Supervisor : Dr. Lakshmanan

Social influence occurs when one's actions are affected by others. If leveraged carefully, social influence can be exploited in many applications like viral marketing (or targeted advertising in general), recommender systems, social network analysis, events detection, experts finding, link prediction, ranking of feeds etc. One of the fundamental problems in this fascinating field is the problem of influence maximization, primarily motivated by the application of viral marketing. The objective is to identify a small set of users in a social network, who when convinced to adopt a product will influence others in the network leading to a large number of adoptions. The vision of our work is to take the algorithmic and data mining aspects of viral marketing out of the lab. We organize ours goals and contributions into four categories: (i) With the ever-increasing scale of online social networks, it is extremely important to develop efficient algorithms for influence maximization. We propose two algorithms -- CELF++ and SIMPATH that significantly improve the scalability. (ii) We remark that previous studies often make unrealistic assumptions and rely on simulations, instead of validating models against real world data. For instance, they assume an arbitrary assignment of influence probabilities in their studies, which focused more on algorithms than on validity with respect to real data. We attack the problem of learning influence probabilities. In another work, we propose a novel data driven approach to influence models and show that it predicts influence diffusion with much better accuracy. (iii) Next, we propose alternative problem formulations -- MINTSS and MINTIME and show interesting theoretical results. These problem formulations capture the problem of deploying viral campaigns on budget and time constraints. In an additional work, we take a fresh perspective on identifying community leaders using a pattern mining approach. (iv) Finally, we examine applications of social influence. We begin with the application of viral marketing. We show that product adoption is not exactly influence. Given this, we develop a product adoption model and study the problem of maximizing product adoption. Furthermore, we propose and investigate a novel problem in recommender systems, for targeted advertising -- RECMAX.

East is not west : is there validity in cross-cultural usability?
Haddad, Shathel Yacoub
DOI : 10.14288/1.0052193
URI : http://hdl.handle.net/2429/44699
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisor : Dr. McGrenere

[no title]
Han, Baipeng
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisor : Dr. Pottinger

A survey on tree edit distance for ordered trees
Hazar, Nima
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. Evans

Decision making with inference and learning methods
Hoffman, Matthew William
DOI : 10.14288/1.0052214
URI : http://hdl.handle.net/2429/44083
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-05
Supervisors : Dr. Doucet, Dr. de Freitas

In this work we consider probabilistic approaches to sequential decision making. The ultimate goal is to provide methods by which decision making problems can be attacked by approaches and algorithms originally built for probabilistic inference. This allows us to directly apply a wide variety of popular, practical algorithms to these tasks. In Chapter 1 we provide an overview of the general problem of sequential decision making and a broad description of various solution methods. Much of the remaining work of this thesis then proceeds by relying upon probabilistic reinterpretations of the decision making process. This strategy of reducing learning problems to simpler inference tasks has been shown to be very fruitful in much of machine learning, and we expect similar improvements to arise in the control and reinforcement learning fields. The approaches of Chapters 2–3 build upon the framework of [Toussaint and Storkey, 2006] in reformulating the solution of Markov decision processes instead as maximum-likelihood estimation in an equivalent probabilistic model. In Chapter 2 we utilize this framework to construct an Expectation Maximization algorithm for continuous, linear-Gaussian models with mixture-of-Gaussian rewards. This approach extends popular linear-quadratic reward models to a much more general setting. We also show how to extend this probabilistic framework to continuous time processes. Chapter 3 further builds upon these methods to introduce a Bayesian approach to policy search using Markov chain Monte Carlo. In Chapter 4 we depart from the setting of direct policy search and instead consider value function estimation. In particular we utilize least-squares temporal difference learning to reduce the problem of value function estimation to a more standard regression problem. In this chapter we specifically tackle the use of regularization methods in order to encourage sparse solutions. In Chapters 5–6 we consider the task of optimization as a sequential decision problem. In the first of these chapters we introduce the bandit framework and discuss a number of variations. Then in Chapter 6 we discuss a related approach to optimization utilizing Bayesian estimates of the underlying, unknown function. We finally introduce a novel approach to choose between different underlying point selection heuristics.

Practical considerations for Dimensionality Reduction : user guidance, costly distances, and document data
Ingram, Stephen
DOI : 10.14288/1.0052184
URI : http://hdl.handle.net/2429/45175
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-11
Supervisor : Dr. Munzner

In this thesis, we explore ways to make practical extensions to Dimensionality Reduction, or DR algorithms with the goal of addressing challenging, real-world cases. The first case we consider is that of how to provide guidance to those users employing DR methods in their data analysis. We specifically target users who are not experts in the mathematical concepts behind DR algorithms. We first identify two levels of guidance: global and local. Global user guidance helps non-experts select and arrange a sequence of analysis algorithms. Local user guidance helps users select appropriate algorithm parameter choices and interpret algorithm output. We then present a software system, DimStiller, that incorporates both types of guidance, validating it on several use-cases. The second case we consider is that of using DR to analyze datasets consisting of documents. In order to modify DR algorithms to handle document datasets effectively, we first analyze the geometric structure of document datasets. Our analysis describes the ways document datasets differ from other kinds of datasets. We then leverage these geometric properties for speed and quality by incorporating ideas from text querying into DR and other algorithms for data analysis. We then present the Overview prototype, a proof-of-concept document analysis system. Overview synthesizes both the goals of designing systems for data analysts who are DR novices, and performing DR on document data. The third case we consider is that of costly distance functions, or when the method used to derive the true proximity between two data points is computationally expensive. Using standard approaches to DR in this important use-case can result in either unnecessarily protracted runtimes or long periods of user monitoring. To address the case of costly distances, we develop an algorithm framework, Glint, which efficiently manages the number of distance function calculations for the Multidimensional Scaling class of DR algorithms. We then show that Glint implementations of Multidimensional Scaling algorithms achieve substantial speed improvements or remove the need for human monitoring.

Blog comments classification using tree structured conditional random fields
Jin, Wei
DOI : 10.14288/1.0052167
URI : http://hdl.handle.net/2429/43571
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. Carenini

FG-MPI: Fine-Grain MPI
Kamal, Humaira
DOI : 10.14288/1.0052194
URI : http://hdl.handle.net/2429/44668
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-11
Supervisor : Dr. Wagner

The Message Passing Interface (MPI) is widely used to write sophisticated parallel applications ranging from cognitive computing to weather predictions and is almost universally adopted for High Performance Computing (HPC). Many popular MPI implementations bind MPI processes to OS-processes. This runtime model has closely matched single or multi-processor compute clusters. Since 2008, however, clusters of multicore nodes have been the predominant architecture for HPC, with the opportunity for parallelism inside one compute node. There are a number of popular parallel programming languages for multicore that use message passing. One notable difference between MPI and these languages is the granularity of the MPI processes. Processes written using MPI tend to be coarse-grained and designed to match the number of processes to the available hardware, rather than the program structure. Binding MPI processes to OS-processes fails to take full advantage of the finer-grain parallelism available on today's multicore systems. Our goal was to take advantage of the type of runtime systems used by fine-grain languages and integrate that into MPI to obtain the best of these programming models; the ability to have fine-grain parallelism, while maintaining MPI's rich support for communication inside clusters. Fine-Grain MPI (FG-MPI) is a system that extends the execution model of MPI to include interleaved concurrency through integration into the MPI middleware. FG-MPI is integrated into the MPICH2 middleware, which is an open source, production-quality implementation of MPI. The FG-MPI runtime uses coroutines to implement light-weight MPI processes that are non-preemptively scheduled by its MPI-aware scheduler. The use of coroutines enables fast context-switching time and low communication and synchronization overhead. FG-MPI enables expression of finer-grain function-level parallelism, which allows for flexible process mapping, scalability, and can lead to better program performance. We have demonstrated FG-MPI's ability to scale to over a 100 million MPI processes on a large cluster of 6,480 cores. This is the first time any system has executed such a large number of MPI processes, and this capability will be useful in exploring scalability issues of the MPI middleware as systems move towards compute clusters with millions of processor cores.

The pairwise heuristic : a method for treating uncertainty in planning and robot localization
Khalvati, Koosha
DOI : 10.14288/1.0052218
URI : http://hdl.handle.net/2429/43747
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. Mackworth

Variational learning for latent Gaussian model of discrete data
Khan, Mohammad
DOI : 10.14288/1.0052219
URI : http://hdl.handle.net/2429/43640
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-05
Supervisors : Dr. K. Murphy, Dr. de Freitas

This thesis focuses on the variational learning of latent Gaussian models for discrete data. The learning is difficult since the discrete-data likelihood is not conjugate to the Gaussian prior. Existing methods to solve this problem are either inaccurate or slow. We consider a variational approach based on evidence lower bound optimization. We solve the following two main problems of the variational approach: the computational inefficiency associated with the maximization of the lower bound and the intractability of the lower bound. For the first problem, we establish concavity of the lower bound and design fast learning algorithms using concave optimization. For the second problem, we design tractable and accurate lower bounds, some of which have provable error guarantees. We show that these lower bounds not only make accurate variational learning possible, but can also give rise to algorithms with a wide variety of speed-accuracy trade-offs. We compare various lower bounds, both theoretically and experimentally, giving clear design guidelines for variational algorithms. Through application to real-world data, we show that the variational approach can be more accurate and faster than existing methods.

Flexible and efficient exploration of rated datasets
Kolloju, Naresh Kumar
DOI : 10.14288/1.0052206
URI : http://hdl.handle.net/2429/44028
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. Lakshmanan

Reconstruction of bubble trajectories and velocity estimation
Krimerman, Michael
DOI : 10.14288/1.0052212
URI : http://hdl.handle.net/2429/43919
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. Heidrich

Probabilistic reasoning with undefined properties in ontologically-based belief networks
Kuo, Chia-Li
DOI : 10.14288/1.0052177
URI : http://hdl.handle.net/2429/45338
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisor : Dr. Poole

Data coordination
Lawrence, Michael
DOI : 10.14288/1.0052209
URI : http://hdl.handle.net/2429/44046
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-05
Supervisor : Dr. Pottinger

Data coordination is the problem of updating a contingent database C as a result of changes to a database B on which it depends. For example, a general contractor’s construction cost estimate (C) needs to be updated in response to changes made by an architect to a building design (B). Although these two databases are related in a very specific way, they contain information about fundamentally different types of objects: the cost estimate is composed of items which represent work results, and the building design is composed of physical objects. Motivated by scenarios such as design-cost coordination, we propose an approach to coordinating data between autonomous, heterogeneous sources which have a base-contingent relationship. We propose the use of declarative mappings to express exact relationships between the two. Using materialized views to maintain state, we give an overall approach for coordinating sets of updates from B to C through view differencing and view update translation. We adopt ideas from data exchange and incomplete information to generate the set of all possible updates which satisfy a mapping. We propose methods for assisting a user (C’s administrator) in choosing amongst the possible updates, and experimentally evaluate these methods, as well as the overall benefit of semiautomatic data coordination, in a usability study. We then discuss practical challenges in applying our general techniques to the domain of architecture, engineering and construction, by interviewing practitioners and analyzing data from two construction projects.

Biomechanical simulation of the hand musculoskeletal system and skin
Li, Duo
DOI : 10.14288/1.0052208
URI : http://hdl.handle.net/2429/44027
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. Pai

A parallel active-set method for solving frictional contact problems
Litven, Joshua Alexander
DOI : 10.14288/1.0052205
URI : http://hdl.handle.net/2429/43934
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisors : Dr. Greif, Dr. Pai

Runtime migration of browser sessions for JavaScript web applications
Lo, Teng Kin
DOI : 10.14288/1.0052216
URI : http://hdl.handle.net/2429/43748
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. Wohlstadter

Dynamic facial appearance capture using six primaries
Mahmud, Anika
DOI : 10.14288/1.0052144
URI : http://hdl.handle.net/2429/43560
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. Heidrich

Visual object recognition for mobile platforms
Meger, David Paul
DOI : 10.14288/1.0052195
URI : http://hdl.handle.net/2429/44682
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-11
Supervisor : Dr. Little

A robot must recognize objects in its environment in order to complete numerous tasks. Significant progress has been made in modeling visual appearance for image recognition, but the performance of current state-of-the-art approaches still falls short of that required by applications. This thesis describes visual recognition methods that leverage the spatial information sources available on-board mobile robots, such as the position of the platform in the world and the range data from its sensors, in order to significantly improve performance. Our research includes: a physical robotic platform that is capable of state-of-the-art recognition performance; a re-usable data set that facilitates study of the robotic recognition problem by the scientific community; and a three dimensional object model that demonstrates improved robustness to clutter. Based on our 3D model, we describe algorithms that integrate information across viewpoints, relate objects to auxiliary 3D sensor information, plan paths to next-best-views, explicitly model object occlusions and reason about the sub-parts of objects in 3D. Our approaches have been proven experimentally on-board the Curious George robot platform, which placed first in an international object recognition challenge for mobile robots for several years. We have also collected a large set of visual experiences from a robot, annotated the true objects in this data and made it public to the research community for use in performance evaluation. A path planning system derived from our model has been shown to hasten confident recognition by allowing informative viewpoints to be observed quickly. In each case studied, our system demonstrates significant improvements in recognition rate, in particular on realistic cluttered scenes, which promises more successful task execution for robotic platforms in the future.

Scalable nearest neighbour methods for high dimensional data
Muja, Marius Constantin
DOI : 10.14288/1.0052198
URI : http://hdl.handle.net/2429/44402
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-11
Supervisor : Dr. Lowe

For many computer vision and machine learning problems, large training sets are key for good performance. However, the most computationally expensive part of many computer vision and machine learning algorithms consists of finding nearest neighbour matches to high dimensional vectors that represent the training data. We propose new algorithms for approximate nearest neighbour matching and evaluate and compare them with previous algorithms. For matching high dimensional features, we find two algorithms to be the most efficient: the randomized k-d forest and a new algorithm proposed in this thesis, the priority search k-means tree. We also propose a new algorithm for matching binary features by searching multiple hierarchical clustering trees and show it outperforms methods typically used in the literature. We show that the optimal nearest neighbour algorithm and its parameters depend on the dataset characteristics and describe an automated configuration procedure for finding the best algorithm to search a particular dataset. In order to scale to very large datasets that would otherwise not fit in the memory of a single machine, we propose a distributed nearest neighbour matching framework that can be used with any of the algorithms described in the thesis. All this research has been released as an open source library called FLANN (Fast Library for Approximate Nearest Neighbours), which has been incorporated into OpenCV and is now one of the most popular libraries for nearest neighbour matching.

[no title]
Mukherjee, Suman
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisor : Dr. Poole

Feasibility of supporting pointing on large wall displays using off-the-shelf consumer-grade tracking equipment
Muradov, Orkhan
DOI : 10.14288/1.0052180
URI : http://hdl.handle.net/2429/45379
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisor : Dr. Booth

Interaction with large stereoscopic displays : Fitts and multiple object tracking studies for virtual reality
Rajendran, Vasanth Kumar
DOI : 10.14288/1.0052210
URI : http://hdl.handle.net/2429/43788
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. Booth

Summarizing software artifacts
Rastkar, Sarah
DOI : 10.14288/1.0052199
URI : http://hdl.handle.net/2429/44482
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-11
Supervisor : Dr. G. Murphy

To answer an information need while performing a software task, a software developer sometimes has to interact with a lot of software artifacts. This interaction may involve reading through large amounts of information and many details of artifacts to find relevant information. In this dissertation, we propose the use of automatically generated natural language summaries of software artifacts to help a software developer more efficiently interact with software artifacts while trying to answer an information need. We investigated summarization of bug reports as an example of natural language software artifacts, summarization of crosscutting code concerns as an example of structured software artifacts and multi-document summarization of project documents related to a code change as an example of multi-document summarization of software artifacts. We developed summarization techniques for all the above cases. For bug reports, we used an extractive approach based on an existing supervised summarization system for conversational data. For crosscutting code concerns, we developed an abstractive summarization approach. For multi-document summarization of project documents, we developed an extractive supervised summarization approach. To establish the effectiveness of generated summaries in assisting software developers, the summaries were extrinsically evaluated by conducting user studies. Summaries of bug reports were evaluated in the context of bug report duplicate detection tasks. Summaries of crosscutting code concerns were evaluated in the context of software code change tasks. Multi-document summaries of project documents were evaluated by investigating whether project experts find summaries to contain information describing the reason behind the corresponding code changes. The results show that reasonably accurate natural language summaries can be automatically produced for different types of software artifacts and that the generated summaries are effective in helping developers address their information needs.

Enhancing particle methods for fluid simulation in computer graphics
Schechter, Hagit
DOI : 10.14288/1.0052201
URI : http://hdl.handle.net/2429/44212
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-05
Supervisor : Dr. Bridson

We introduce novel methods for enriched Lagrangian fluid simulation in three distinct areas: smoke animation, liquid animation, and surfacing of simulation particle data. The techniques share a common goal, to efficiently enhance realism of natural-phenomena animations in particle simulation framework. Sub-Grid Turbulence adds synthesized small scale detail to large scale smoke simulation. The transport, diffusion and spectral cascade of turbulent energy are captured, whereas they are left unresolved on a typical simulation grid. Ghost-SPH handling of free-surface and solid boundary conditions in Smoothed Particle Hydrodynamics liquid simulation captures realistic cohesion for the first time and avoids the spurious numerical errors of previous approaches. Ghost particles are carefully seeded in the air and solid regions near the fluid and are assigned with extrapolated fluid quantities to reach correct boundary conditions. The Beta Mesh is a new method for reconstructing mostly temporally coherent surface meshes from particles representing the volume of a liquid. While current particle surfacing techniques address the geometrical characteristics of the surface, the focus in Beta Mesh is producing a surface which varies smoothly in time, outside of topological changes, while preserving essential geometrical properties.

Benchmarking the performance of application startup for AspectJ-aware Java virtual machines
Selby, Vincent
DOI : 10.14288/1.0052191
URI : http://hdl.handle.net/2429/44750
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisor : Dr. Kiczales

Improve classroom interaction and collaboration using i>clicker
Shi, Junhao
DOI : 10.14288/1.0052178
URI : http://hdl.handle.net/2429/45365
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisor : Dr. Booth

Improving object detection using 3D spatial relationships
Southey, Tristram
DOI : 10.14288/1.0052189
URI : http://hdl.handle.net/2429/44786
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-11
Supervisor : Dr. Little

Reliable object detection is one of the most significant hurdles that must be overcome to develop useful household robots. Overall, the goal of this work is to demonstrate how effective 3D qualitative spatial relationships can be for improving object detection. We show that robots can utilize 3D qualitative spatial relationships to improve object detection by differentiating between true and false positive detections. The main body of the thesis focuses on an approach for improving object detection rates that identifies the most likely subset of 3D detections using seven types of 3D relationships and adjusts detection confidence scores to improve the average precision. These seven 3D qualitative spatial relationships are adapted from 2D qualitative spatial reasoning techniques. We learn a model for identifying the most likely subset using a structured support vector machine [Tsochantaridis et al., 2004] from examples of 3D layouts of objects in offices and kitchens. We produce 3D detections from 2D detections using a fiducial marker and images of a scene and show our model is successful at significantly improving overall detection rates on real world scenes of both offices and kitchens. After the real world results, we test our method on synthetic detections where the properties of the 3D detections are controlled. Our approach improves on the model it was based upon, that of [Desai et al., 2009], by utilizing a branch and bound tree search to improve both training and inference. Our model relies on sufficient true positive detections in the training data or good localization of the true positive detections. Finally, we analyze the cumulative benefits of the spatial relationships and determine that the most effective spatial relationships depend on both the scene type and localization accuracy. We demonstrate that there is no one relationship that is sufficient on its own or always outperforms others and that a mixture of relationships is always useful.

[no title]
Sun, Wei
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. Pottinger

Dialogue act recognition in synchronous and asynchronous conversations
Tavafi, Maryam
DOI : 10.14288/1.0052186
URI : http://hdl.handle.net/2429/44874
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisors : Dr. Ng, Dr. Carenini

Cachekata: memory hierarchy optimization via dynamic binary translation
Taylor, Nathan Bryan
DOI : 10.14288/1.0052202
URI : http://hdl.handle.net/2429/44335
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. Warfield

Space and energy efficient molecular programming and space efficient text indexing methods for sequence alignment
Thachuk, Christopher Joseph
DOI : 10.14288/1.0052204
URI : http://hdl.handle.net/2429/44172
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-05
Supervisor : Dr. Condon

Nucleic acids play vital roles in the cell by virtue of the information encoded into their nucleotide sequence and the folded structures they form. Given their propensity to alter their shape over time under changing environmental conditions, an RNA molecule will fold through a series of structures called a folding pathway. As this is a thermodynamically-driven probabilistic process, folding pathways tend to avoid high energy structures and those which do are said to have a low energy barrier. In the first part of this thesis, we study the problem of predicting low energy barrier folding pathways of a nucleic acid strand. We show various restrictions of the problem are computationally intractable, unless P=NP. We propose an exact algorithm that has exponential worst-case runtime, but uses only polynomial space and performs well in practice. Motivated by recent applications in molecular programming we also consider a number of related problems that leverage folding pathways to perform computation. We show that verifying the correctness of these systems is PSPACE-hard and in doing so show that predicting low energy barrier folding pathways of multiple interacting strands is PSPACE-complete. We explore the computational limits of this class of molecular programs which are capable, in principle, of logically reversible and thus energy efficient computation. We demonstrate that a space and energy efficient molecular program of this class can be constructed to solve any problem in SPACE ---the class of all space-bounded problems. We prove a number of limits to deterministic and also to space efficient computation of molecular programs that leverage folding pathways, and show limits for more general classes. In the second part of this thesis, we continue the study of algorithms and data structures for predicting properties of nucleic acids, but with quite different motivations pertaining to sequence rather than structure. We design a number of compressed text indexes that improve pattern matching queries in light of common biological events such as single nucleotide polymorphisms in genomes and alternative splicing in transcriptomes. Our text indexes and associated algorithms have the potential for use in alignment of sequencing data to reference sequences.

The impact of individual differences on visualization effectiveness and gaze behaviour : informing the design of user adaptive interventions
Toker, Dereck J
DOI : 10.14288/1.0052188
URI : http://hdl.handle.net/2429/44765
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisor : Dr. Conati

Implementing a Toolbox of Level Set Methods in Python
Tomer, Nathaniel Kenneth
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. Mitchell

Modeling standing, walking and rolling skills for physics-based character animation
Torres Vidal, Ernesto
DOI : 10.14288/1.0052221
URI : http://hdl.handle.net/2429/43614
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. van de Panne

CRYPSTOR : a platform for secure storage
Totolici, Alexandru
DOI : 10.14288/1.0052196
URI : http://hdl.handle.net/2429/44603
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisors : Dr. Aiello, Dr. Warfield

Auxiliary variable transformations for intractable distributions
Vanetti, Paul Justin Cesare
DOI : 10.14288/1.0052200
URI : http://hdl.handle.net/2429/44340
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisors : Dr. Doucet, Dr. de Freitas

Design-driven quadrangulation of closed 3D curves
Wang, Caoyu
DOI : 10.14288/1.0052222
URI : http://hdl.handle.net/2429/43602
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. Sheffer

Integrating building-level and campus-level data
Wei, Lan
DOI : 10.14288/1.0052181
URI : http://hdl.handle.net/2429/45144
Degree : Master of Science - MSc
Graduation Date : 2013-11
Supervisor : Dr. Pottinger

Flowshape : 3d concept modeling from single-view design sketches
Xu, Baoxuan
DOI : 10.14288/1.0052203
URI : http://hdl.handle.net/2429/44274
Degree : Master of Science - MSc
Graduation Date : 2013-05
Supervisor : Dr. Sheffer

Computational modeling of neuromusculoskeletal systems : from filaments to behavior
Yeo, Sang Hoon
DOI : 10.14288/1.0052217
URI : http://hdl.handle.net/2429/43756
Degree : Doctor of Philosophy - PhD
Graduation Date : 2013-05
Supervisor : Dr. Pai

This thesis describes computational approaches to modeling and simulating aspects of the neuromusculoskeletal system. We make contributions to models at three different levels of detail. We first investigate the mechanics of shortening muscle and evaluate two forms of the traditional Hill-type muscle model, force scaling and f-max scaling, and show that the f-max scaling model is significantly better at predicting experimental results. We hypothesize a new model called the winding filament model that incorporates the role of titin during active force development. Based on the proposed hypothesis, we develop a computational model that is able to simulate residual force enhancement. The suggested model can qualitatively simulate the pattern of the force enhancement observed in previous studies. In order to model the higher levels of the system consisting of muscles and bones, we propose an optimal design framework for estimating parameters of the musculoskeletal model. The method finds a set of morphological and physiological parameters that can optimally simulate the measured force and moment at the point of action. We apply the suggested framework to modeling two rat hindlimb muscles, gracilis posticus and posterior part of biceps femoris, to see if the traditional line segment based muscle geometry model is valid for musculoskeletal system modeling. The result shows that even a complex muscle like biceps femoris can be well modeled as a line segment, but its estimated insertion point is far from that of the traditional model based on anatomy. Finally, this thesis addresses a behavioral aspect of biological movement; in particular, how a high level movement is planned and controlled, in coordination with perception. We present a fully generative model of object interception that can simulate realistic, human-like behavior of ball catching for given arbitrary ball trajectory. The model includes a simplified probabilistic model of vision, a model of eye movements combining saccades and pursuit, and corresponding head, hand and body movements. The movements are constructed from submovements. By combining these components, realistic interception behavior is simulated with minimal user intervention.



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