CS Theses & Dissertations 2012

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

Information flow identification in large email datasets
Akuney, Arseniy
DOI : 10.14288/1.0052116
URI : http://hdl.handle.net/2429/39847
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisors : Dr. Aiello, Dr. Warfield

Object persistence in 3D for home robotics
Alimi, Parnian
DOI : 10.14288/1.0052154
URI : http://hdl.handle.net/2429/42108
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. Little

Dynamic explicit surface meshes and applications
Brochu, Tyson
DOI : 10.14288/1.0052148
URI : http://hdl.handle.net/2429/42829
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-11
Supervisor : Dr. Bridson

Explicit surface tracking encompasses the discretization of moving surfaces in 3D with triangle meshes. This thesis presents key contributions towards making explicit surface tracking tractable. I first deal with the topology change problem (the merging and splitting of mesh surfaces), introducing a framework for guaranteeing intersection-free surfaces while handling these topological changes. I then introduce new methods for continuous collision detection which are “exact” in the sense of returning the same results as they would if computed with symbolic or exact arithmetic, but which are implemented using faster, floating-point arithmetic. The thesis also showcases several application domains in which explicit surface tracking can offer improvements over traditional methods: geometric flows, adaptive cloth simulation, and passive visualization of smoke simulation. It also presents two simulation techniques which take advantage of the explicit surface mesh representation and would not be possible with traditional methods: vortex sheet smoke and adaptive liquid simulation with high-resolution surface tension.

Supporting a process-oriented model in MPI through fine-grain mapping
Brown, Cody Ryan
DOI : 10.14288/1.0052160
URI : http://hdl.handle.net/2429/42152
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. Wagner

Approximating barrier resilience and related notions for disk sensors in a two-dimensional plane
Chan, David Yu Cheng
DOI : 10.14288/1.0052170
URI : http://hdl.handle.net/2429/43455
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisor : Dr. Kirkpatrick

Improvisational interfaces for visualization construction and scalar function sketching
Chao, William O.
DOI : 10.14288/1.0052161
URI : http://hdl.handle.net/2429/41982
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. van de Panne

Query processor for the conceptual integration modeling framework
Chen, Zhaohong
DOI : 10.14288/1.0072550
URI : http://hdl.handle.net/2429/40276
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. Pottinger

Non-linear contextual bandits
Chia, John
DOI : 10.14288/1.0052153
URI : http://hdl.handle.net/2429/42191
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisors : Dr. Wagner, Dr. de Freitas

Equilibrium policy gradients for spatiotemporal planning
Crowley, Mark Anthony
DOI : 10.14288/1.0052093
URI : http://hdl.handle.net/2429/38971
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-05
Supervisor : Dr. Poole

In spatiotemporal planning, agents choose actions at multiple locations in space over some planning horizon to maximize their utility and satisfy various constraints. In forestry planning, for example, the problem is to choose actions for thousands of locations in the forest each year. The actions at each location could include harvesting trees, treating trees against disease and pests, or doing nothing. A utility model could place value on sale of forest products, ecosystem sustainability or employment levels, and could incorporate legal and logistical constraints such as avoiding large contiguous areas of clearcutting and managing road access. Planning requires a model of the dynamics. Existing simulators developed by forestry researchers can provide detailed models of the dynamics of a forest over time, but these simulators are often not designed for use in automated planning. This thesis presents spatiotemoral planning in terms of factored Markov decision processes. A policy gradient planning algorithm optimizes a stochastic spatial policy using existing simulators for dynamics. When a planning problem includes spatial interaction between locations, deciding on an action to carry out at one location requires considering the actions performed at other locations. This spatial interdependence is common in forestry and other environmental planning problems and makes policy representation and planning challenging. We define a spatial policy in terms of local policies defined as distributions over actions at one location conditioned upon actions at other locations. A policy gradient planning algorithm using this spatial policy is presented which uses Markov Chain Monte Carlo simulation to sample the landscape policy, estimate its gradient and use this gradient to guide policy improvement. Evaluation is carried out on a forestry planning problem with 1880 locations using a variety of value models and constraints. The distribution over joint actions at all locations can be seen as the equilibrium of a cyclic causal model. This equilibrium semantics is compared to Structural Equation Models. We also define an algorithm for approximating the equilibrium distribution for cyclic causal networks which exploits graphical structure and analyse when the algorithm is exact.

Trace Based Slicing for Program Specialization
Dadizadeh, Sara
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisors : Dr. Warfield, Dr. Hutchinson

A functional framework for evaluating visualization applications, with a focus on financial analysis problems
Dang, Luan Quang
DOI : 10.14288/1.0052120
URI : http://hdl.handle.net/2429/42313
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisors : Dr. Rensink, Dr. Lemieux (SLAIS)

BackSpace : formal analysis for post-silicon debug
De Paula, Flavio Miana
DOI : 10.14288/1.0052119
URI : http://hdl.handle.net/2429/42322
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-11
Supervisor : Dr. Hu

IC technology continues to closely follow Moore's Law, while the ability to verify designs lags behind. The International Technology Roadmap for Semiconductors (ITRS) predicts production of chips using 16nm technology already by 2015, but the verification gap, i.e., advancements in verification technology not keeping up with advancements in design technology, seems to be also increasing at a fast pace. A recent study shows a drop of more than 10 percentage points in the number of 1st-silicon success from 2002 through 2009. By 2007, more than 2/3 of chips had to be respun due to bugs. The increasing verification gap is to blame. Unfortunately, because more bugs are slipping into the fabricated chip, post-silicon debug is the only way to catch them. Post-silicon debug is the problem of determining what's wrong when the fabricated chip of a new design behaves incorrectly. The focus of post-silicon debug is design errors, whereas traditional VLSI test focuses on random manufacturing defects on each fabricated chip. Post-silicon debug currently consumes more than half of the total verification schedule on typical large designs, and the problem is growing worse. The general problem of post-silicon debug is broad and multi-faceted, spurring a diverse variety of research. In this thesis, I focus on one of the most fundamental tasks: getting an execution trace of on-chip signals for many cycles leading up to an observed bug or crash. Until such a trace is obtained, further debugging is essentially impossible, as there is no way to know what happened on the chip. However, the ever-increasing chip complexity compounded with new features that add non-determinism makes computing accurate traces extremely difficult. Thus, to address this issue, I present a novel post-silicon debug framework, which I call BackSpace. From theory to practice, I have methodically developed this framework showing that BackSpace effectively computes accurate traces leading up to a crash state, has low cost (zero-additional hardware overhead), and handles non-determinism. To support my claims, I demonstrated BackSpace with several industrial designs using simulation models, hardware prototypes, and on actual silicon.

Link scheduling directed graphs using undirected edge colours
d'Oliveira, Kyle Nicholas
DOI : 10.14288/1.0052143
URI : http://hdl.handle.net/2429/42329
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisor : Dr. Kirkpatrick

Real-time support for interactive multimedia applications
Erbad, Aiman M.
DOI : 10.14288/1.0052149
URI : http://hdl.handle.net/2429/42878
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-11
Supervisor : Dr. Hutchinson

Emerging interactive multimedia applications, such as real-time visualizations, animations, on-line games, virtual reality, and video conferencing have low latency interactions and continuous high resource (e.g., CPU processing and network bandwidth) demands. The combination of latency sensitive interactions and high resource demands is challenging for best-effort platforms, such as the Internet, general-purpose operating systems and Web browsers because these platforms have no timing or resource guarantees and tend to favor high utilization. When demands exceed available resources, it is impossible to process all computations and data in a timely fashion resulting in diminished perceived quality (e.g., frame rate) and brittle real-time performance. The mismatch between application demands and available resources is observed to varying degrees in all resources including network, processing, and storage. To deal with the volatility and shortage of resources, we build upon and extend the Priority-Progress quality adaptation model. Our approach enables applications to scale demands (up or down) based on available resources and to utilize the limited resources in processing the computations and data with more influence over perceived quality. We develop enhancement layers to improve timeliness and guarantee more consistent quality using quality adaptation while maintaining the strengths of the existing best-effort transports and execution platforms. DOHA, our execution layer, extends the Priority-Progress CPU adaptation to work in games and across multiple execution threads. The modified game has better timing, higher perceived quality, and linearly scalable quality with a small number of cores. Our transport layer, Paceline, introduces low latency techniques over TCP and exposes Priority-Progress adaptation as an essential transport feature improving upon TCP's end-to-end latency while preserving its fairness and utilization.

Herded Gibbs sampling
Fang, Jing
DOI : 10.14288/1.0052124
URI : http://hdl.handle.net/2429/43188
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisor : Dr. de Freitas

Sensing and recognizing affective touch in a furry zoomorphic object
Flagg, Anna Purna
DOI : 10.14288/1.0052123
URI : http://hdl.handle.net/2429/43071
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisor : Dr. MacLean

[no title]
Ginestra, Marcos
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisor : Dr. Evans

Ildl factorizations for sparse skew-symmetric matrices
He, Shiwen
DOI : 10.14288/1.0103449
URI : http://hdl.handle.net/2429/42185
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. Greif

Tralfamadore : memory reconstruction, declarative dependency resolution, and parallelism
Head, Christopher Charles David
DOI : 10.14288/1.0052091
URI : http://hdl.handle.net/2429/39075
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisors : Dr. Warfield, Dr. Aiello

Embodied object recognition
Helmer, Scott
DOI : 10.14288/1.0052118
URI : http://hdl.handle.net/2429/42481
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-11
Supervisor : Dr. Lowe

The ability to localize and categorize objects via imagery is central to many potential applications, including autonomous vehicles, mobile robotics, and surveillance. In this thesis we employ a probabilistic approach to show how utilizing multiple images of the same scene can improve detection. We cast the task of object detection as finding the set of objects that maximize the posterior probability given a model of the categories and a prior for their spatial arrangements. We first present an approach to detection that leverages depth data from binocular stereo by factoring classification into two terms: an independent appearance-based object classifier, and a term for the 3D shape. We overcome the missing data and the limited fidelity of stereo by focusing on the size of the object and the presence of discontinuities. We go on to demonstrate that even with off-the-shelf stereo algorithms we can significantly improve detection on two household objects, mugs and shoes, in the presence of significant background clutter and textural variation. We also present a novel method for object detection, both in 2D and in 3D, from multiple images with known extrinsic camera parameters. We show that by also inferring the 3D position of the objects we can improve object detection by incorporating size priors and reasoning about the 3D geometry of a scene. We also show that integrating information across multiple viewpoints allows us to boost weak classification responses, overcome occlusion, and reduce false positives. We demonstrate the efficacy of our approach, over single viewpoint detection, on a dataset containing mugs, bottles, bowls, and shoes in a variety of challenging scenarios.

Participatory design of a biometrically-driven portable audio player
Himmetoğlu, Hikmet Gökhan
DOI : 10.14288/1.0052092
URI : http://hdl.handle.net/2429/38752
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisors : Dr. MacLean, McGrenere

Robot Navigation in a Social Context
Hofmann, Tomas Michael
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisors : Dr. Little, Dr. Woodham

Representing and reasoning with large games
Jiang, Xin
DOI : 10.14288/1.0052175
URI : http://hdl.handle.net/2429/39951
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-05
Supervisor : Dr. Leyton-Brown

In the last decade, there has been much research at the interface of computer science and game theory. One important class of problems at this interface is the computation of solution concepts (such as Nash equilibrium or correlated equilibrium) of a finite game. In order to take advantage of the highly-structured utility functions in games of practical interest, it is important to design compact representations of games as well as efficient algorithms for computing solution concepts on such representations. In this thesis I present several novel contributions in this direction: The design and analysis of Action-Graph Games (AGGs), a fully-expressive modeling language for representing simultaneous-move games. We propose a polynomial-time algorithm for computing expected utilities given arbitrary mixed strategy profiles, and leverage the algorithm to achieve exponential speedups of existing algorithms for computing Nash equilibria. Designing efficient algorithms for computing pure-strategy Nash equilibria in AGGs. For symmetric AGGs with bounded treewidth our algorithm runs in polynomial time. Extending the AGG framework beyond simultaneous-move games. We propose Temporal Action-Graph Games (TAGGs) for representing dynamic games and Bayesian Action-Graph Games (BAGGs) for representing Bayesian games. For certain subclasses of TAGGs and BAGGs we gave efficient algorithms for equilibria that achieve exponential speedups over existing approaches. Efficient computation of correlated equilibria. In a landmark paper, Papadimitriou and Roughgarden described a polynomial-time algorithm ("Ellipsoid Against Hope") for computing sample correlated equilibria of compactly-represented games. Recently, Stein, Parrilo and Ozdaglar showed that this algorithm can fail to find an exact correlated equilibrium. We present a variant of the Ellipsoid Against Hope algorithm that guarantees the polynomial-time identification of exact correlated equilibrium. Efficient computation of optimal correlated equilibria. We show that the polynomial-time solvability of what we call the deviation-adjusted social welfare problem is a sufficient condition for the tractability of the optimal correlated equilibrium problem.

Noisy optimal control strategies for modelling saccades
Jones, Garrett Livingston
DOI : 10.14288/1.0052155
URI : http://hdl.handle.net/2429/39845
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisors : Dr. Pai, Dr. Ascher

Automatic Context-Free Parser Generation
Joo, Anseok
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. Evans

Optimal planning with approximate model-based reinforcement learning
Kao, Hai Feng
DOI : 10.14288/1.0052158
URI : http://hdl.handle.net/2429/39889
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. Mackworth

A cluster-based framework for contrast preservation during color space transformations
Lau, Cheryl S.
DOI : 10.14288/1.0052137
URI : http://hdl.handle.net/2429/41858
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-05
Supervisor : Dr. Heidrich

Common tasks such as printing, displaying, and visualizing images may require a transformation of the input image from its source color space to a target color space. Such transformations include converting color images to grayscale for printing, mapping images to the gamuts of target display devices, preparing images for color deficient viewers, and fusing multispectral or multiprimary data into tristimulus images. Each of these transformations has a straightforward, standard mapping, but it often involves a loss of information due to dimensionality reduction or differing constraints for the source and target spaces. In the extreme case, contrast is completely lost when different colors in the source space map to the same color in the target space, an effect known as metamerism. We present a framework for mapping an image from a source color space to a target color space in a way that preserves as much of the local contrast from the source image as possible while staying as faithful as possible to the standard mapping. We adopt a cluster-based approach in which the clusters represent local areas in the image, and the differences between the clusters represent local contrasts between neighboring areas. Our optimization translates clusters optimally to enhance local contrast without making the result seem unnatural. We apply our method to color to gray conversion, gamut mapping, image optimization for color deficient viewers, and conversion of multispectral and multiprimary images to tristimulus images. In each application, our method produces realistic, detail-preserving output images within their target spaces.

Composable and reusable whole-system offline dynamic analysis
Lefebvre, Geoffrey
DOI : 10.14288/1.0052156
URI : http://hdl.handle.net/2429/39935
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-05
Supervisors : Dr. Feeley, Dr. Warfield

This thesis describes the design, implementation, and evaluation of a dynamic program analysis framework called Tralfamadore. Three key aspects differentiate Tralfamadore from traditional dynamic analysis frameworks. First, analyses execute offline based on detailed CPU traces. This approach enables multiple analyses on the same execution, and analyses not foreseen at the time of execution. Using detailed traces also decouples analysis from instrumentation, simplifying the design of analyses and of the framework. Second, Tralfamadore supports the analysis of operating system execution. Third, the architecture of the analysis engine promotes the construction of analyses that are composable and reusable. New analyses can be written by mostly reusing existing components. Although these aspects have been investigated in isolation in the past, Tralfamadore is the first dynamic analysis framework to address all three at once.

Towards dynamic, patient-specific musculoskeletal models
Levin, David Isaac William
DOI : 10.14288/1.0052165
URI : http://hdl.handle.net/2429/41963
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-05
Supervisor : Dr. Pai

This thesis focuses on the development of tools to aid in producing dynamic simulations from patient specific volumetric data. Specifically, two new computational methods have been developed, one for image acquisition and one for simulation. Acquiring patient-specific musculoskeletal architectures is a difficult task. Our image acquisition relies on Diffusion Tensor Imaging since it allows the non-invasive study of muscle fibre architecture. However, musculoskeletal Diffusion Tensor Imaging suffers from low signal-to-noise ratio. Noise in the computed tensor fields can lead to poorly reconstructed muscle fibre fields. In this thesis we detail how leveraging a priori knowledge of the structure of skeletal muscle can drastically increase the quality of fibre architecture data extracted from Diffusion Tensor Images. The second section of this thesis describes a simulation technique that allows the direct simulation of volumetric data, such as that produced by the denoising algorithm. The method was developed in response to two key motivations: first, that the medical imaging data we acquire is volumetric and can be difficult to discretize in a Lagrangian fashion, and second that many biological structures (such as muscle) are highly deformable and come into close contact with each other as well as the environment. In response to these observations we have produced an Eulerian simulator that can simulate volumetric objects in close contact. The algorithm intrinsically handles large deformations and potential degeneracies that can result in contacting scenarios. Extending the simulator to produce complex musculoskeletal simulations is also discussed. These two algorithms address concerns in two stages of a proposed pipeline for generating dynamic, patient specific musculoskeletal simulations.

A Reference Implementation for Planar Physics-based Biped Locomotion Using SIMBICON
Li, Li
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. van de Panne

Dynamic analysis for graphical user interface editors
Li, Peng
DOI : 10.14288/1.0052168
URI : http://hdl.handle.net/2429/40521
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-05
Supervisor : Dr. Wohlstadter

WYSIWYG (What You See Is What You Get) graphical editors, for example, Swing Designer and Dreamweaver, are widely used to help GUI developers in developing and maintaining GUIs (Graphical User Interface) of desktop and Web applications. GUI editors allow developers to work directly with a graphical design view instead of scattered source elements. This feature helps developers in addressing one particular difficulty for GUI development and maintenance: a large amount of GUI code can be scattered across many different source modules. However, traditional GUI editors have two major defects. First, GUI code is normally tangled with some dynamic computation code. Traditional GUI editors are limited by their ability to statically reconstruct this dynamic GUI code, creating an incomplete design view for developers. Second, some parts of a user interface are stateful and reactive. Their appearance and behavior vary over time, based on mutations of state made from code. Currently, there are no existing GUI editors that can assist developers in understanding how a UI behavior is implemented. To deal with the first defect, I built a tool called FreezeFrame. This tool uses a dynamic reverse-engineering approach to bridge the gap between the rendering view of a user interface and its corresponding implementation, by providing a design/code hyper-linking on a complete dynamic view. To deal with the second defect, I created a tool called ScriptInsight. This tool provides a custom control flow model to bridge a live UI behavior with a set of source elements that control the UI behavior. Developers can use this model to understand the implementation of a UI behavior. To evaluate FreezeFrame, I first show that user interface code can be spread across the decomposition of applications. Next, I demonstrate that the reverse-engineering capabilities of a traditional GUI editor can be improved by using my dynamic reverse-engineering approach. To evaluate ScriptInsight and the usefulness of the custom control flow model, I first evaluate this tool by presenting several case studies. Second, I justify the relevance of this model by the complexity of JavaScript implementations for the UIs from several existing Web applications.

Efficient extraction of ontologies from domain specific text corpora
Li, Tianyu
DOI : 10.14288/1.0052152
URI : http://hdl.handle.net/2429/39686
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisors : Dr. Pottinger, Dr. Lakshmanan

Elevating search results from flat lists to structured expansions
Liang, Xueyao
DOI : 10.14288/1.0052122
URI : http://hdl.handle.net/2429/39933
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. Lakshmanan

Learning to track and identify players from broadcast sports videos
Lu, Wei-Lwun
DOI : 10.14288/1.0052129
URI : http://hdl.handle.net/2429/39956
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-05
Supervisor : Dr. K. Murphy, Dr. Little

Tracking and identifying players in sports videos filmed with a single pan-tilt-zoom camera has many applications, but it is also a challenging problem. This thesis introduces the first intelligent system that tackles this difficult task. The system possesses the ability to detect and track multiple players, estimates the homography between video frames and the court, and identifies the players. The tracking system is based on the tracking-by-detection philosophy. We first localize players using a player detector, categorize detections based on team colors, and then group them into tracks of specific players. Instead of using visual cues to distinguish between players, we instead rely on their short-term motion patterns. The homography estimation is solved by using a variant of the Iterated Closest Points (ICP). Unlike most existing algorithms that rely on matching robust feature points, we propose to match edge points in two images. In addition, we also introduce a technique to update the model online to accommodate logos and patterns in different stadiums. The identification system utilizes both visual and spatial cues, and exploits both temporal and mutual exclusion constraints in a Conditional Random Field. In addition, we propose a novel Linear Programming Relaxation algorithm for predicting the best player identification in a video clip. In order to reduce the number of labeled training data required to learn the identification system, we pioneer the use of weakly supervised learning with the assistance of play-by-play texts. Experiments show promising results in tracking, homography estimation, and identification. Moreover, weakly supervised learning with play-by-play texts greatly reduces the number of labeled training data required. Experiments show that we can use weakly supervised learning with merely 200 labels to achieve similar accuracies to a strongly supervised approach, which requires at least 20000 labels.

Digital micrography
Maharik, Ron Israel
DOI : 10.14288/1.0052114
URI : http://hdl.handle.net/2429/38864
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. Sheffer

Automatic initialization for broadcast sports videos rectification
Mohammadi Tari, Shervin
DOI : 10.14288/1.0052173
URI : http://hdl.handle.net/2429/39969
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. Little

Prime Climb : an analysis of attention to student-adaptive hints in an educational game
Muir, Mary Anne Midori
DOI : 10.14288/1.0052147
URI : http://hdl.handle.net/2429/42140
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. Conati

SNbR : Social Networks-based Forwarding in Delay Tolerant Networks
Nguyen, Nguyet Minh
DOI : 10.14288/1.0052142
URI : http://hdl.handle.net/2429/42275
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisors : Dr. Vuong, Dr. Feeley

Active exploration of training data for improved object detection
Okuma, Kenji
DOI : 10.14288/1.0052169
URI : http://hdl.handle.net/2429/40520
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-05
Supervisors : Dr. Lowe, Dr. Little

This thesis concerns the problem of object detection, which is defined as finding all instances of an object class of interest and fitting each of them with a tight bounding window. This seemingly easy task for humans is still extremely difficult for machines. However, recent advances in object detection have enabled machines to categorize many classes of objects. Statistical models are often used for representing an object class of interest. These models learn from extensive training sets and generalize with low error rates to unseen data in a highly generic manner. But, these statistical methods have a major drawback in that they require a large amount of training data. We approach this problem by making the process of acquiring labels less tedious and less costly by reducing human labelling effort. Throughout this thesis, we explore means of efficient label acquisition for realizing cheaper training, faster development time, and higher-performance of object detectors. We use active learning with our novel interface to combine machine intelligence with human interventions, and effectively improve a state-of-the-art classifier by using additional unlabelled images from the Web. As the approach relies on a small amount of label input from a human oracle, there is still room to further reduce the amount of human effort. An ideal solution is, if possible, to have no humans involved in labelling novel data. Given a sparsely labelled video that contains very few labels, our novel self-learning approach achieves automatic acquisition of additional labels from the unlabelled portion of the video. Our approach combines colour segmentation, object detection and tracking in order to discover potential labels from novel data. We empirically show that our self-learning approach improves the performance of models that detect players in broadcast footage of sports games.

Variants of the Consecutive-Ones Property motivated by the reconstruction of ancestral species
Patterson, Murray Dan
DOI : 10.14288/1.0052159
URI : http://hdl.handle.net/2429/40128
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-05
Supervisors : Dr. Gupta, Dr. Manuch

The polynomial-time decidable Consecutive-Ones Property (C1P) of binary matrices, formally introduced in 1965 by Fulkerson and Gross, has since found applications in many areas. In this thesis, we propose and study several variants of this property that are motivated by the reconstruction of ancestral species. We first propose the Gapped C1P, or the (k,delta)-C1P: a binary matrix M has the (k,delta)-C1P for integers k and delta if the columns of M can be permuted such that each row contains at most k blocks of 1's and no two neighboring blocks of 1's are separated by a gap of more than delta 0's. The C1P is equivalent to the (1,0)-C1P. We show that for every bounded and unbounded k ≥ 2, delta ≥ 1, (k,delta)≠ (2,1), deciding the (k,delta)-C1P is NP-complete [Golberg et al., 1995]. We also provide an algorithm for a relevant case of the (2,1)-C1P. We then study the (k,delta)-C1P with a bound d on the maximum number of 1's in any row (the maximum degree) of M. We show that the (d,k,delta)-C1P is polynomial-time decidable when all three parameters are fixed constants. Since fixing d also fixes k (k ≤ d), the only case left to consider is the (d,k,infinity)-C1P (when delta is unbounded). We show that for every d > k ≥ 2, deciding the (d,k,infinity)-C1P is NP-complete. We also study the C1P with Multiplicity (mC1P), introduced by Wittler and Stoye [2010]: a binary matrix M on columns S = {1,..,n} has the mC1P for multiplicity vector m:S→ ℕ if there is a sequence sigma on S such that (i) sigma contains each s ∈ S at most m(s) times, and (ii) for each row r of M, the set of columns that have entry 1 in r form at least one subsequence of sigma. We show that deciding the mC1P, and two restricted variants thereof, are NP-complete, for M having maximum degree 3 (6 for one of the variants), and for m(s) ≤ 2 for all s ∈ S. We also give a tractability result for the mC1P that is motivated by handling telomeres in the reconstruction of ancestral species. Finally, we study the Generalized Cladistic Character Compatibility (GCCC) Problem, a generalization of the Perfect Phylogeny Problem [Semple and Steel, 2003] introduced by Benham et al. [1995]. We use the structure of the PQ-tree [Booth and Leuker, 1976] associated with the C1P to give algorithms for several cases of the GCCC Problem.

A Framework for Schema Understanding
Radu, Anca Simona
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisor : Dr. Pottinger

Designing adaptive interfaces for children : a preliminary study on the effect of age and gender on children’s interaction in the context of dialoguing with computers
Rajamanickam, Mohan Raj
DOI : 10.14288/1.0052139
URI : http://hdl.handle.net/2429/39441
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. McGrenere

A visual interface for browsing and summarizing conversations
Rashid, Shama
DOI : 10.14288/1.0052130
URI : http://hdl.handle.net/2429/42237
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. Carenini

Perceptual considerations for displays under varying ambient illumination
Rempel, Allan Gilbert
DOI : 10.14288/1.0052163
URI : http://hdl.handle.net/2429/40367
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-05
Supervisor : Dr. Heidrich

The capabilities of visual display devices such as television sets and computer monitors have advanced dramatically over the past decade. In particular, prototype high dynamic range (HDR) displays have emerged during that time, which provide significantly greater output brightness and dynamic range than conventional currently available displays. These increased capabilities open up two new avenues of research: investigating how to take advantage of the characteristics of these displays to improve the appearance of images and video, and observing and characterizing the responses of the human visual system to the new kinds of imagery these displays are capable of producing. The contributions of this dissertation advance our understanding along both of these lines. We present a set of experiments in which subjects viewed video content on HDR displays, and observe that subjects preferred higher display brightness settings in higher ambient illumination environments, and that subjects generally preferred the highest contrast available, irrespective of brightness, with effectively no visual fatigue (compared to conventional displays) during extended viewing sessions. We then present a novel technique for enhancing the contrast of low dynamic range (LDR) legacy content to take advantage of the capabilities of HDR displays, which is an underconstrained problem with several solutions of varying effectiveness. Our technique boosts the brightness of saturated image regions while keeping darker image regions dark. Next, we present a set of experiments in which we use a prototype display with precise colour control to determine the effect of different colours of glare on vision in low-light environments. The data from these experiments provide insight into human vision in low-light environments which can improve the design of displays for such environments. Finally, we present a set of experiments showing the effect of contrast on depth perception in monocular viewing environments, and how this effect can be enhanced by adjusting the contrast between highlights and mid-tones in HDR imagery. Collectively, these contributions advance our ability to display imagery on new generations of high-contrast and high-brightness displays for more satisfying viewing experiences, and can aid in the design of future displays.

On fully characterizing terrain visibility graphs
Saeedi Bidokhti, Noushin
DOI : 10.14288/1.0052141
URI : http://hdl.handle.net/2429/41902
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. Evans

Reverb: dynamic bookmarks for developers
Sawadsky, Nicholas Justin
DOI : 10.14288/1.0052117
URI : http://hdl.handle.net/2429/42752
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisor : Dr. G. Murphy

Sensing gait on smartphones to support mobile exercise applications and games
Schneider, Oliver Stirling
DOI : 10.14288/1.0052125
URI : http://hdl.handle.net/2429/43129
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisor : Dr. MacLean

TAMER : touch-guided anxiety management via engagement with a robotic pet efficacy evaluation and the first steps of the interaction design
Sefidgar, Yasaman Sadat
DOI : 10.14288/1.0052145
URI : http://hdl.handle.net/2429/42135
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. MacLean

Computational techniques for flow cytometry : the application for automated analysis of innate immune response flow cytometry data
Shooshtari, Parisa
URI : http://hdl.handle.net/2429/42179
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-05
Supervisor : Dr. Gupta

Flow cytometry (FCM) is a technique for measuring physical, chemical and biological characteristics of individual cells. Recent advances in FCM have provided researchers with the facility to improve their understanding of the tremendously complex immune system. However, the technology is hampered by current manual analysis methodologies. In this thesis, I developed computational methods for the automated analysis of immune response FCM data to address this bottleneck. I hypothesized that highly accurate results could be obtained through learning from the patterns that a biology expert applies when doing the analysis manually. In FCM data analysis, it is often desirable to identify homogeneous subsets of cells within a sample. Traditionally, this is done through manual gating, a procedure that can be subjective and time-consuming. I developed SamSPECTRAL, an automated spectral-based clustering algorithm to identify FCM cell populations of any shape, size and distribution while addressing the drawbacks of manual gating. A particularly signi cant achievement of SamSPECTRAL was its successful performance in nding rare cell populations. Similarly, in most FCM applications, it is required to match similar cell populations between di erent FCM samples. I developed a novel learning-based cluster matching method that incorporates domain expert knowledge to nd the best matches of target populations among all clusters generated by a clustering algorithm. Immunophenotyping of immune cells and measuring cytokine responses are two main components of immune response FCM data analysis. I combined the SamSPECTRAL algorithm and cluster matching to perform automated immunophenotyping. I also devised a method to measure cytokine responses automatically. After developing computational methods for each of the above analysis components separately, I organized them into a semi-automated pipeline, so they all work together as a uni ed package. My experiments on 216 FCM samples con rmed that my semi-automated pipeline can reproduce manual analysis results highly accurately both for immunophenotyping and measuring cytokine responses. My other main contributions were correlation analysis of intracellular and secreted cytokines, and developing a formula called GiMFI to improve measuring functional response of cytokine-producing cells using ow cytometry assay.

Globally consistent space-time reconstruction
South-Dickinson, Ian James
DOI : 10.14288/1.0052157
URI : http://hdl.handle.net/2429/43207
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisor : Dr. Sheffer

Fibre based modeling of wood dynamics and fracture
Sutherland, Sean Meiji
DOI : 10.14288/1.0052128
URI : http://hdl.handle.net/2429/43457
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisor : Dr. Bridson

Computing functions of imprecise inputs using query models
Suyadi, Simon Aloysius
DOI : 10.14288/1.0052151
URI : http://hdl.handle.net/2429/42133
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. Evans

The design and field observation of a haptic notification system for timing awareness during oral presentations
Tam, Diane Karen
DOI : 10.14288/1.0052134
URI : http://hdl.handle.net/2429/43397
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisor : Dr. MacLean, Dr. McGrenere

Adaptive pipelined work processing for GPS trajectories
Tjia, Andrew Hung Yao
DOI : 10.14288/1.0052162
URI : http://hdl.handle.net/2429/43288
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisor : Dr. Vuong

Manipulating scale-dependent perception of images
Trentacoste, Matthew Michael
DOI : 10.14288/1.0052094
URI : http://hdl.handle.net/2429/39251
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-05
Supervisor : Dr. Heidrich

The purpose of most images is to effectively convey information. Implicit in this assumption is the fact that the recipient of that information is a human observer, with a visual system responsible for converting raw sensory inputs into the perceived appearance. The appearance of an image not only depends on the image itself, but the conditions under which it is viewed as well as the response of human visual system to those inputs. This thesis examines the scale-dependent nature of image appearance, where the same stimulus can appear different when viewed at varying scales, that arises from the mechanisms responsible for processing spatial vision in the brain. In particular, this work investigates changes in the perception of blur and contrast resulting from the image being represented by different portions of the viewer's visual system due to changes in image scale. These methods take inspiration from the fundamental organization of spatial image perception into multiple parallel channels for processing visual information and employ models of human spatial vision to more accurately control the appearance of images under changing viewing conditions. The result is a series of methods for understanding the blur and contrast present in images and manipulating the appearance of those qualities in a perceptually-meaningful way.

Navigation and Obstacle Avoidance Help (NOAH) for elderly wheelchair users with cognitive impairment in long-term care
Viswanathan, Pooja
DOI : 10.14288/1.0052150
URI : http://hdl.handle.net/2429/42950
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-11
Supervisors : Dr. Mackworth, Dr. Little

Cognitive impairments prevent older adults from using powered wheelchairs because of safety concerns, thus reducing mobility and resulting in increased dependence on caregivers. An intelligent powered wheelchair system (NOAH) is proposed to help restore mobility, while ensuring safety. Machine vision and learning techniques are described to help prevent collisions with obstacles, and provide reminders and navigation assistance through adaptive audio prompts. The intelligent wheelchair is initially tested in various controlled environments and simulated scenarios. Finally, the system is tested with older adults with mild-to-moderate cognitive impairment through a single-subject research design. Results demonstrate the high diversity of the target population, and highlight the need for customizable assistive technologies that account for the varying capabilities and requirements of the intended users. We show that the collision avoidance module is able to improve safety for all users by lowering the number of frontal collisions. In addition, the wayfinding module assists users in navigating along shorter routes to the destination. Prompting accuracy is found to be quite high during the study. While compliance with correct prompts is high across all users, we notice a distinct difference in the rates of compliance with incorrect prompts. Results show that users who are unsure about the optimal route rely more highly on system prompts for assistance, and thus are able to improve their wayfinding performance by following correct prompts. Improvements in wheelchair position estimation accuracy and joystick usability will help improve user performance and satisfaction. Further user studies will help refine user needs and hopefully allow us to increase mobility and independence of several elderly residents.

Isometrically deforming cloth with simultaneous collision handling
Wang, Zheng
DOI : 10.14288/1.0072605
URI : http://hdl.handle.net/2429/40948
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. Bridson

Predictive adaptation of hybrid Monte Carlo with bandits
Wang, Ziyu (Steven)
DOI : 10.14288/1.0052146
URI : http://hdl.handle.net/2429/43362
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisor : Dr. de Freitas

The animation canvas : a sketch-based visual language for motion editing
Welsman-Dinelle, Michael Charles
DOI : 10.14288/1.0052136
URI : http://hdl.handle.net/2429/39815
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. van de Panne

Scalable Database Management System (DBMS) architecture with Innesto
Wijesekera, Primal Ruwan
DOI : 10.14288/1.0052131
URI : http://hdl.handle.net/2429/43363
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisors : Dr. Krasic, Dr. Warfield

IQ : a whole-system instrumentation framework for post analysis
Xu, Wenhao
DOI : 10.14288/1.0052166
URI : http://hdl.handle.net/2429/43473
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisors : Dr. Warfield, Dr. Hutchinson

The Haptic Creature : social human-robot interaction through affective touch
Yohanan, Steven John
DOI : 10.14288/1.0052135
URI : http://hdl.handle.net/2429/43144
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-11
Supervisor : Dr. MacLean

Emotion communication is an important aspect of social interaction. Affect display research from psychology as well as social human-robot interaction has focused primarily on facial or vocal behaviors, as these are the predominant means of expression for humans. Much less attention, however, has been on emotion communication through touch, which, though unique among the senses, can be methodologically and technologically difficult to study. Our thesis investigated the role of affective touch in the social interaction between human and robot. Through a process of design and controlled user evaluation, we examined the display, recognition, and emotional influence of affective touch. To mitigate issues inherent in touch research, we drew from interaction models not between humans but between human and animal, whereby the robot assumes the role of companion animal. We developed the Haptic Creature, a small, zoomorphic robot novel in its sole focus on touch for both affect sensing and display. The robot perceives movement and touch, and it expresses emotions through ear stiffness, modulated breathing, and vibrotactile purring. The Haptic Creature was employed in three user studies, each exploring a different aspect of affective touch interaction. Our first study examined emotion display from the robot. We detail the design of the Haptic Creature's affect display, which originated from animal models, then was enhanced through successive piloting. A formal study demonstrated the robot was more successful communicating arousal than valence. Our second study investigated affect display from the human. We compiled a touch dictionary from psychology and human-animal interaction research. Participants first rated the likelihood of using these touch gestures when expressing a variety of emotions, then performed likely gestures communicating specific emotions for the Haptic Creature. Results provided properties of human affect display through touch and high-level categorization of intent. Our final study explored the influence of affective touch. Results empirically demonstrated the human's emotional state was directly influenced from affective touch interactions with the robot. Our research has direct significance to the field of socially interactive robotics and, further, any domain interested in human use of affective touch: psychology, mediated social touch, human-animal interaction.

Automatic basketball tracking in broadcast basketball video
Yu, Shuang
DOI : 10.14288/1.0052127
URI : http://hdl.handle.net/2429/43072
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisor : Dr. Little

Automatic analysis of flow cytometry data and its application to lymphoma diagnosis
Zare, Habil
DOI : 10.14288/1.0052140
URI : http://hdl.handle.net/2429/39660
Degree : Doctor of Philosophy - PhD
Graduation Date : 2012-05
Supervisor : Dr. Gupta

Flow cytometry has many applications in clinical medicine and biological research. For many modern applications, traditional methods of manual data interpretation are not efficient due to the large amount of complex, high dimensional data. In this thesis, I discuss some of the important challenges towards automatic analysis of flow cytometry data and propose my solutions. To validate my approach on addressing real life problems, I developed an automatic pipeline for analyzing flow cytometry data and applied it to clinical data. My pipeline can potentially be useful for improving quality check on diagnosis, assisting discovery of novel phenotypes, and making clinical recommendations. Furthermore, some of the challenges that I studied are rooted in more general areas of computer science, and therefore, the tools and techniques that I developed can be applied to a wider range of problems in data mining and machine learning. Enhancement to spectral clustering algorithm and proposing a novel scheme for scoring features are two examples of my contributions to computer science that were developed as part of this thesis.

Attribute based encryption made practical
Zhang, Long
DOI : 10.14288/1.0052132
URI : http://hdl.handle.net/2429/42138
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. Aiello

Impacts on the I/O performance of the virtual disk in Xen
Zhang, Quan
DOI : 10.14288/1.0052121
URI : http://hdl.handle.net/2429/39998
Degree : Master of Science - MSc
Graduation Date : 2012-05
Supervisor : Dr. Warfield, Dr. Hutchinson

Regret bounds for Gaussian process bandits without observation noise
Zoghi, Masrour
DOI : 10.14288/1.0052133
URI : http://hdl.handle.net/2429/42865
Degree : Master of Science - MSc
Graduation Date : 2012-11
Supervisor : Dr. de Freitas