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

Receive updates for this collection

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.

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.