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

Receive updates for this collection

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.

Quality-aware 3D video delivery

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

Three dimensional (3D) videos are the next natural step in the evolution of digital media technologies. In order to provide viewers with depth perception and immersive experience, 3D video streams contain one or more views and additional information describing the scene's geometry. This greatly increases the bandwidth requirements for 3D video transport. In this thesis, we address the challenges associated with delivering high quality 3D video content to heterogeneous devices over both wired and wireless networks. We focus on three problems: energy-efficient multicast of 3D videos over 4/5G networks, quality-aware HTTP adaptive streaming of free-viewpoint videos, and achieving quality-of-experience (QoE) fairness in free-viewpoint video streaming in mobile networks. In the first problem, multiple 3D videos represented in the two-view-plus-depth format and scalably coded into several substreams are multicast over a broadband wireless network. We show that optimally selecting the substreams to transmit for the multicast sessions is an NP-complete problem and present a polynomial time approximation algorithm to solve it. To maximize the power savings of mobile receivers, we extend the algorithm to efficiently schedule the transmission of the chosen substreams from each video. In the second problem, we present a free-viewpoint video streaming architecture based on state-of-the-art HTTP adaptive streaming protocols. We propose a rate adaptation method for streaming clients based on virtual view quality models, which relate the quality of synthesized views to the qualities of the reference views, to optimize the user's quality-of-experience. We implement the proposed adaptation method in a streaming client and assess its performance. Finally, in the third problem, we propose an efficient radio resource allocation algorithm in mobile wireless networks where multiple free-viewpoint video streaming clients compete for the limited resources. The resulting allocation achieves QoE fairness across the streaming sessions and it reduces quality fluctuations.

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

Color Constancy for RGB and Multispectral Images

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

The problem of inferring the light color for a scene is called Illuminant Estimation. This step forms the first task in many workflows in the larger task of discounting the effect of the color of the illuminant, which is called Color Constancy. Illuminant Estimation is typically used as a pre-processing step in many computer vision tasks. In this thesis, we tackle this problem for both RGB and multispectral images. First, for RGB images we extend a moments based method in several ways: firstly by replacing the standard expectation value, the mean, considering moments that are based on a Minkowski p-norm; and then secondly by going over to a float value for the parameter p and carrying out a nonlinear optimization on this parameter; and finally by considering a different expectation value, generated by using the geometric mean. We show that these strategies can drive down the median and maximum error of illuminant estimates. And then for multispectral images, we formulate a multiple-illuminants estimation problem as a Conditional Random Field (CRF) optimization task over local estimations. We then improve local illuminant estimation by incorporating spatial information in each local patch.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Mark S. Drew
Ze-Nian Li
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

2-Median Problems in Tree Networks

Date created: 
2017-03-29
Abstract: 

Facility Location Problems have a great significance for allocating resources efficiently in a network. The interaction mainly involves a price which depends on the distances between the objects and the order of significance of the objects(clients). The applications of such problems are immense in many application areas such as medical and transportation. In this project, we consider the p-median facility location problem in tree-networks. This p-median problem in general tree-networks is NP-hard. In this project, we have looked at efficiently solving the 2-median problem in tree networks. Using simple techniques of computational geometry, we give a O(n log s) time solution to the 2-median of a tree with s number of leaves. Our technique is then applied to solve other variants of the 2-median problem with the same complexity

Document type: 
Graduating extended essay / Research project
File(s): 
Senior supervisor: 
Binay Bhattacharyya
Ramesh Krishnamurthi
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Project) M.Sc.

Interactive extraction of 3D trees from medical images supporting gaming and crowdsourcing

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

Analysis of vascular and airway trees of circulatory and respiratory systems is important for a wide range of clinical applications. Automatic segmentation of these tree-like structures from 3D image data remains challenging due to complex branching patterns, geometrical diversity, and pathology. Existing automated techniques are sensitive to parameters setting, may leak into nearby structures, or miss true bifurcating branches; while interactive methods for segmenting vascular trees are hard to design and use, making them impractical to extend to 3D and to vascular trees with many branches (e.g., tens or hundreds). We propose SwifTree, an interactive software to facilitate this tree extraction task while exploring crowdsourcing and gamification. Our experiments demonstrate that: (i) aggregating the results of multiple SwifTree crowdsourced sessions can achieve more accurate segmentation; (ii) using the proposed game-mode can reduce time needed to achieve a pre-set tree segmentation accuracy; and (iii) SwifTree outperforms automatic segmentation methods especially with respect to noise robustness.

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

Modelling and prediction of neurodevelopment in preterm infants using structural connectome data

Date created: 
2017-04-04
Abstract: 

Each year worldwide, millions of babies are born very preterm (before 32 weeks postmenstral age). Very preterm birth puts infants at higher risk for delayed or altered neurodevelopment. While the mechanisms causing these alterations are not fully understood, it has been shown that image-based biomarkers of the fragile connective white matter brain tissue are correlated with neurodevelopmental outcomes. Diffusion MRI (dMRI) is a non-invasive imaging modality that allows in-vivo analysis of an infant's white matter brain network (known as a structural connectome) and can be used to better understand neurodevelopment. The purpose of this thesis is to study how the structural connectome can be used for analysis of development and early prediction of outcomes for better informed care. The thesis begins with a thorough examination of the literature on studies that have applied machine learning to brain network data from MRI. It proceeds with a connectome based analysis of the early neurodevelopment of normative preterm infants. Finally, this thesis tackles the problem of early prediction of cognitive and motor neurodevelopmental outcomes using machine learning on connectome data. Three novel prediction methods are proposed for this task, which are found to be able to accurately predict the 18-month neurodevelopmental outcomes of a cohort of preterm infants from the BC Childrens' Hospital. The thesis concludes with a discussion of how the proposed models may be applicable to a broader set prediction problems and of important future directions for research.

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

Design and Implementation of a Smartphone Application for Estimating Foot Clearance during Walking

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

Maximum Foot Clearance (MaxFC) is the maximal foot height during the swing phase relative to the ground, and is a gait variable that is highly associated with tripping and falling. An iPhone mobile application is designed to analyze the MaxFC in real time using the iPhone’s built-in accelerometer and gyroscope to collect data when the phone is attached to the shank of the leg. Our method is based on double integration and drift cancellation of foot acceleration signals. An optical motion capture system was used as gold standard, and the results show the mean error over all strides is less than 10.3%. The findings illustrate the feasibility of using an iPhone application to estimate MaxFC. The application is designed and implemented to display the foot clearance results conveniently. A user study was conducted and feedbacks indicate that this application can be suitable to self-monitor risk of falls to prevent falling.

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

Generalized methods for application specific hardware specialization

Author: 
Date created: 
2016-11-21
Abstract: 

Since the invention of the microprocessor in 1971, the computational capacity of the microprocessor has scaled over 1000x with Moore and Dennard scaling. Dennard scaling ended with a rapid increase in leakage power 30 years after it was proposed. This ushered in the era of multiprocessing where additional transistors afforded by Moore's scaling were put to use. The breakdown of Moore's law indicates the start of a new era for computer architects. With the scaling of computational capacity no longer guaranteed every generation, application specific hardware specialization is an attractive alternative to sustain scaling trends. Hardware specialization broadly refers to the identification and optimization of recurrent patterns, dynamic and static, in software via integrated circuitry. This dissertation describes a two-pronged approach to architectural specialization.First, a top down approach uses program analysis to determine code regions amenable for specialization. We have implemented a prototype compiler tool-chain to automatically identify, analyze, extract and grow code segments which are amenable to specialization in a methodical manner. Second, a bottom up approach evaluated particular hardware enhancements to enable the efficient data movement of specialized regions. We have devised and evaluated coherence protocols and flexible caching mechanisms to reduce the overhead of data movement within specialized regions. The former workload centric approach analyses programs at the path granularity. We enumerate static and dynamic program characteristics accurately with low overhead. Our observations show that analysis of amenability for specialization along the path granularity yield different conclusions than prior work. We show that analyses at coarser granularities tend to smear program characteristics critical to specialization. We analyse the potential for performance and energy improvement via specialization at the path granularity. We develop mechanisms to extract and merge amenable paths into segments called Braids. Braids are constructed from the observation that oft-executed program paths have the same start and end point. This allows for increased offload opportunity while retaining the same interface as path granularity specialization. To address the challenges of data movement, the latter micro-architecture first approach, proposes a specialized coherence protocol tailored for accelerators and an adaptive granularity caching mechanism. The hybrid coherence protocol localizes data movement to a specialized accelerator-only tile reducing energy consumption and improving performance. Modern workloads have varied program characteristics where fixed granularity caching often introduces waste in the cache hierarchy. Frequently cache blocks are evicted before all words in the fetched line are touched by the processor. We propose a variable granularity caching mechanism which reduces energy consumption while improving performance via better utilization of the available storage space.

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

Multimodal Interfaces for Human-Robot Interaction

Date created: 
2016-12-23
Abstract: 

Robots are becoming more popular in domestic human environments, from service applica- tions to entertainment and education, where they share the workspace and interact directly with the general public in their everyday life. One long-term goal of human-robot inter- action (HRI) research is to have robots work with and around people, taking instructions via simple, intuitive interfaces. For a successful, natural interaction robots are expected to be observant of the human present, recognize what they are doing and act appropriately to their attention-drawing behaviors such as gaze, body posture or gestures. We call such a system by which a robot can take notice of someone or something and consider it as interesting or relevant attention system. These systems enable robots to shift their focus of attention to a particular part of the information that is relevant and meaningful in a given situation based on the motivational and behavioral state of the robot. This awareness comes from interpreting the exchanged information between humans and robots. The exchange of information through a combination of different modalities is anticipated to be of most ben- efit. Multimodal interfaces can be used to take advantage of the existing strengths of each composite modality and overcome individual weaknesses. Also, it has been argued [1] that multimodal interfaces facilitate a more natural communication as by employing integrated systems users will be less concerned about how to communicate the intended commands or which modality to use, and therefore be free to focus on the task and goals at hand. This PhD thesis presents our contributions made in designing and implementing multimodal, sensor-mediated attention systems that enable users to interact directly with physically col- located robots using natural and intuitive communication methods. We focus on scenarios when there are multiple people or multiple robots in the environment. First, we introduce two multimodal human multi-robot interaction systems for selecting and commanding an individual or a group of robots from a population. In this context, we study how spatial configuration of user and robots may affect the efficiency of these interfaces in real-world settings. Next, we present a probabilistic approach for identifying attention-drawing signals from an interested party and controlling a mobile robot’s attention toward the most promis- ing interaction partner among a group of people. Finally, we report on a user study designed to assess the performance and usability of this proposed system for finding HRI partners in a crowd when used by the non-robotics experts and compare it to manual control.

Document type: 
Thesis
File(s): 
Demonstration of a robust integrated system for selecting and commanding multiple mobile robots
Demonstration of commanding groups of robots using face engagement and indirect speech in voice commands
Demonstration of an integrated system for finding an HRI partner in a crowd
Observations of WOZ experiments for studying what untrained users do when asked “make the robot come to you”
Senior supervisor: 
Richard Vaughan
Greg Mori
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) Ph.D.

A novel colour Hessian and its applications

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

The idea of contrast at a pixel, including contrast in colour or higher-dimensional image data, has traditionally been associated with the Structure Tensor, also named the di Zenzo matrix or Harris matrix. This 2×2 array encapsulates how colour-channel first-derivatives give rise to change in any spatial direction in x, y. The di Zenzo or Harris matrix Z has been put to use in several different applications. For one, the Spectral Edge method for image fusion uses Z for a putative colour image, along with the Z for higher-dimensional data, to produce an altered RGB image which properly has exactly the same Z as that of high-D data. As well, Z has been used as the foundation for the Harris interest-point or corner-point detector. However, a competing definition for Z is the 2 × 2 Hessian matrix, formed from second-derivative values rather than first derivatives. In this thesis we develop a novel Z which in the first place utilizes the Harris Z, but then goes on to modify Z by adding some information from the Hessian. Moreover, here we consider an extension to a Hessian for colour or higher-D image data which treats colour channels not as simply to be added, but in a colour formulation that generates the Hessian from a colour vector. For image fusion, results are shown to retain more details and also generate fused images that have smaller CIELAB errors from the original RGB. Using the new Z in corner-detection, the novel colour Hessian produces interest points that are more accurate, and as well generates fewer false positive points.

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