Computing Science - Theses, Dissertations, and other Required Graduate Degree Essays

Receive updates for this collection

Generating and streaming immersive sports video content

Author: 
Date created: 
2017-08-18
Abstract: 

Stereoscopic 3D videos have already become popular in movie theaters with most productions being released in this format. More recently, with the availability of commodity Virtual Reality (VR) products, immersive video content is receiving even more interest. A wide spread adoption of immersive devices and displays is hindered by the lack of content that matches the user expectations. Producing immersive videos is far more costly and time-consuming than regular 2D videos, which makes it challenging and thus rarely attempted, especially for live events, such as sports games. In addition, immersive content needs to be adapted for viewing on different displays/devices. To address these challenges, we first propose a new system for 3D video streaming that provides automatic depth adjustments as one of its key features. Our system takes into account both the content and the display type in order to customize 3D videos and optimize the viewing experience. Our stereoscopic video streaming system was implemented, deployed and tested with real users. Results show that between 60% to 70% of the shots can benefit from our system and more than 25% depth enhancement can be achieved. Next, we propose a novel, data-driven method that converts 2D videos to 3D by transferring depth information from a database of similar 3D videos. Our method then reconstructs the depth map while ensuring temporal coherency using a spatio-temporal formulation of Poisson reconstruction. Results show that our method produces high-quality 3D videos that are almost indistinguishable from videos shot by stereo cameras, while achieving up to 20% improvement in the perceived depth compared to the current state-of-the-art method. Furthermore, we extend our work in the direction of VR, and propose using video feeds from regular broadcasting cameras to generate sports VR content. We generate a wide-angle panorama by utilizing the motion of the main camera. We then use various techniques to remove the parallax, align all video feeds, and overlay them on the panorama. Subjective studies show that our generated content provides an immersive experience similar to ground-truth content captured using a 360 camera, with most subjects rating their sense of presence from Good to Excellent.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Mohamed Hefeeda
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) Ph.D.

Classification in the presence of heavy label noise: A Markov chain sampling framework

Author: 
Date created: 
2017-06-19
Abstract: 

Heavy label noise is often present in many practical scenarios where observed labels of instances are corrupted. Classification with heavy label noise has great significance and attracts a lot of attention, since label noise may lead to many potential negative consequences. Many state-of-the-art approaches assume that label noise is class-dependent, and thus cannot be generalized to situations without this assumption. In this thesis, we propose a Markov chain sampling framework, MCS, to conquer the limitations of the existing methods in the binary classification problem. The main idea is to utilize the predictions of a sequence of classifiers in an ensemble way to detect mislabeled instances, the sequence of classifiers is trained on different subsets of the training data by sampling the states of a carefully designed Markov chain with random walk. Our proposed MCS framework is general and can entertain a wide spectrum of classification algorithms. We theoretically prove the correctness and effectiveness of the MCS framework. We further present experimental results showing the effectiveness and efficiency of the proposed framework and derivative algorithms.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Jian Pei
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Virtualization Empowered Resource Management and Content Distribution in the Cloud

Author: 
Date created: 
2017-06-01
Abstract: 

Virtualization is the cornerstone technology of cloud computing. Advancements in virtualization enable researchers to tackle key challenges in today's cloud. The first part of this thesis delves into the emerging container virtualization and how leveraging containers we address resource management and pricing challenges in the cloud. We try calling for an end to the constant battle between public cloud providers and users over the pricing options of cloud instances: the users generally have to pay for the entire billing cycle even on fractional usage. Ideally, idle cloud instances with residual billing cycle should be resalable by their users. Such trading demands efficient resource consolidation and multiplexing, because the revenue and use cases are confined by the transient nature of the instances. This thesis presents HARV, a novel cloud service that facilitates the management and trade of cloud instances. The platform relies on hybrid virtualization, an infrastructure layout integrating both the hypervisor-based virtual machines and lightweight containers, incorporating a truthful online auction mechanism for instance trading and resource allocation. Our design achieves efficient resource consolidation with no need for provider-level support, and we have deployed a prototype of HARV on the Amazon EC2 public cloud. Our evaluations reveal that applications experience negligible performance overhead when hosted on HARV; trace-driven simulations further show that HARV can achieve substantial cost savings. The second part of the thesis explores the emerging Network Function Virtualization (NFV). Virtualization and cloud computing constitute a major driving force for Internet innovations. In today's Internet, multimedia content traffic accounts for the largest share of all traffic. Downstream towards the consumers, multimedia traffic often traverse through middleboxes, undergoing additional data processing imposed by content distributors. With NFV, middleboxes are embedded in general-purpose, off-the-shelf servers, allowing content distributors to conveniently borrow existing cloud technologies to process traffic. Despite these benefits, we find NFV incurs an undue amount of energy consumption when carrying out high packet forwarding performance. We identify the energy inefficiency issue in the NFV dataplane which can be exacerbated if not handle properly. We outline a power management framework that exploits CPU frequency scaling to save energy.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Jiangchuan Liu
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Using Womb Grammars for inducing the grammar of a subset of Yorùbá noun phrases

Date created: 
2016-08-30
Abstract: 

We address the problem of inducing the grammar of an under-resourced language, Yorùbá, from the grammar of English using an efficient and linguistically savvy, constraint solving model of grammar induction- Womb Grammars (WG).Our proposed methodology employs Womb Grammars in parsing a subset of noun phrases of the target language Yorùbá, from the grammar of the source language English, which is described as properties between pairs of constituents. Our model is implemented in CHRG (Constraint Handling Rule Grammars) and has been used for inducing the grammar of a useful subset of Yorùbá noun phrases. Interesting extensions to the original Womb Grammar model are presented, motivated by the specific needs of Yorùbá and similar tone languages.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Veronica Dahl
Fred Popowich
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Examining the Impact of Propagating and Partitioning for Mutation Analysis of C Programs

Author: 
Date created: 
2017-05-11
Abstract: 

Mutation analysis is a technique for assessing the quality of test suites by seeding artificial defects into a program. The application of this method is still limited as it places a high demand on computational resources.There are techniques called infection, propagation, and partitioning that leverage the information available at run-time to reduce the execution time of mutation analysis. Although the effectiveness of these techniques has been investigated for Java, it is not known how they behave on programs written in low-level languages such as C. This thesis makes contributions toward investigating the effectiveness and efficiency of infection, propagation, and partitioning optimizations for programs written in C. It also explores the impact of statically pruning redundant mutants on these optimizations. The analysis of five real-world applications, with 402,000 lines of code in total, suggests that while infection might have the same effectiveness in C and Java, propagation and partitioning could be more effective for C. Additionally, it shows that static pruning reduces the impact of infection, propagation, and partitioning by around 5%, 7.29%, and 11.90% respectively.

Document type: 
Thesis
File(s): 
Senior supervisor: 
William (Nick) Sumner
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Extended exclusive graph search

Author: 
Date created: 
2017-05-12
Abstract: 

Graph search is an important research area in both mathematics and computer science with many practical applications such as eliminating a malicious software in a computer network. The graph search problem can be intuitively described as follows: given a set of searchers and a fugitive in a graph, the searchers and fugitive move from vertices to vertices in the graph alternatively and the searchers try to capture the fugitive which tries to escape from the searchers. A major optimization problem in graph search is to find the minimum number of searchers (called search number) to capture the fugitive. There are several well known graph models: node-search, edgesearch, mixed-search and exclusive search. In this thesis, we propose a new search model which is an extension of the exclusive search. We prove the extended exclusive search number for trees. We give the search numbers for the well known graph search models and the extended exclusive search on trees of rings. We also propose heuristic search algorithms for power law graphs based on these models.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Qianping Gu
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

A Gaze-based Attention System for Multi-human Multi-robot Interaction

Author: 
Date created: 
2017-04-03
Abstract: 

This thesis presents a computer vision based attention system for interaction between multiple humans and multiple robots. The study contains three parts. In the first part each human can “select” (obtain the undivided attention of) a ground robot and interact with it by simply gazing (looking directly) at it. This extends previous work whereby a single human can select one or more robots from a population. In the second part, a feature which allows robots to be selected by people they cannot see is introduced. This is the first demonstration of many-to-many robot-selection HRI. Humans are detected, tracked, and allocated to robots partners in a two-step linear assignment problem. In the third part, we demonstrate the attention system with flying robots. The “micro-feedback” method which allows users to pre-select, select and de-select robots is introduced. This is the first demonstration of multiple UAV interacting with multiple human using face engagement.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Richard Vaughan
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Similar image retrieval for dermoscopy images using interest point detection

Author: 
Date created: 
2017-03-28
Abstract: 

Providing physicians with a set of pathology-confirmed similar images to a new difficult case can efficiently assist towards a more confident diagnosis; this concept is called Content-Based Image Retrieval. We used SURF interest point detection to find and match similar dermoscopy images from a labeled dermoscopic image database. SURF automatically finds points of interest with the shape of blobs, dots. Haar - wavelet responses and local color histograms are locally extracted from each detected key point. The similarity of two images is decided by matching their key points and finding the Euclidean distance between them. We evaluated our system’s performance based on its ability for retrieving images with the same texture features and similar diagnosis. For query images containing a pigment network the precision with retrieval of 9 images, P(9), is 75%; for dots and globules, the precision P(9) is 80%. The precision P(9) for Melanoma diagnosis is 72%, which is acceptable forsuch systems.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Stella Atkins
Mark Drew
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Learning Person Trajectory Representations for Team Activity Analysis

Author: 
Date created: 
2017-04-18
Abstract: 

Activity analysis in which multiple people interact across a large space is challenging due to the interplay of individual actions and collective group dynamics. We propose an end-to-end generic approach for learning person trajectory representations for group activity analysis. The learned representations encode rich spatio-temporal dependencies and capture useful motion patterns for recognizing individual events, as well as characteristic group dynamics that can be used to identify groups from their trajectories alone. We develop our deep learning approach in the context of team sports, which provide well-defined sets of events (e.g. pass, shot) and groups of people (teams). We evaluate our model on NBA basketball and NHL hockey games datasets. Analysis of events and team formations using these two sports datasets demonstrate the generality of our approach. Experiments show that our model is capable of (1) capturing strong spatio-temporal cues for recognizing events in hockey dataset (2) capturing distinctive group dynamics for identifying group identity.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Greg Mori
Luke Bornn
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

Activity monitoring using topic models

Author: 
Date created: 
2017-03-29
Abstract: 

Activity monitoring is the task of continual observation of a stream of events which necessitates the immediate detection of anomalies based on a short window of data. For many types of categorical data, such as zip codes and phone numbers, thousands of unique attribute values lead to a sparse frequency vector. This vector is then unlikely to be similar to the frequency vector obtained from the training set collected from a longer period of time. In this work, using topic models, we present a method for dimensionality reduction which can detect anomalous windows of categorical data with a low rate of false positives. We apply nonparametric Bayesian topic models to address the variable nature of data, which allows for updating the model parameters during the continual observation to capture gradual changes of the user behavior. Our experiments on several real-life datasets show that our proposed model outperforms state-of-the-art methods for activity monitoring in categorical data with large domains of attribute values.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Martin Ester
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.