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

Receive updates for this collection

Generating natural language summary for image sets

Author: 
Date created: 
2018-05-31
Abstract: 

We address the problem of summarizing an image set with a natural language caption. We present PlacesCap, a new dataset for image set summarization. Our dataset consists of 11,661 image sets with a total of 116,113 images, where each set is summarized by a 3 sentence caption. We propose novel pooling operators for permutation invariant sets of feature maps, and empirically evaluate image set summarization models based on those operators. We also conduct experiments of image set classification and show competitive performance for the proposed set pooling operators.

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

Online density bursting subgraph detection from temporal graphs

Author: 
Date created: 
2018-05-07
Abstract: 

Given a temporal weighted graph that consists of a potentially endless stream of updates, we are interested in finding density bursting subgraphs (DBS), where a DBS is a subgraph that accumulates its density at the fastest speed. Online DBS detection enjoys many novel applications. At the same time, it is challenging since the time duration of a DBS can be arbitrarily long but a limited size storage can buffer only up to a certain number of updates. To tackle this problem, we observe the critical decomposability of DBSs and show that a DBS with a large time duration can be decomposed into a set of indecomposable DBSs with equal or larger burstiness. We further prove that the time duration of an indecomposable DBS is upper bounded and propose an efficient method TopkDBSOL to detect indecomposable DBSs in an online manner. Extensive experiments demonstrate the effectiveness, efficiency, and scalability of TopkDBSOL in detecting significant DBSs from temporal graphs.

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

Exploring behavioral data in online social media with focus on user connectivity and mobility

Author: 
Date created: 
2018-04-23
Abstract: 

With the booming development of online social media in recent years, massive and variety of behavioral data, such as social interactions data and user's E-travel sharing data, are generated by the users throughout the world everyday. Exploring and analyzing such data helps to understand users' preferences, unearth the contained tremendous knowledge, and identify new problems and business opportunities, thus is beneficial for social media users, service providers, etc. In this thesis, we are specifically interested in the user connectivity/interaction behaviors, e.g., friendship creation, and the mobility behaviors, e.g., check-in sequence at Point-of-Interest (POIs), that involve rich semantic information on nodes and edges of the social networks, and study three practical problems in different applications. We first analyze users' social connectivity behaviors from a new angle and study a problem of mining non-homophily social ties, aiming at discovering interesting but unexpected group-level social ties that do not follow the homophily phenomenon. We propose a novel ranking metric to identify such social ties and develop an efficient mining algorithm specifically for the new metric. In our second work, we explore users' check-in sequences or travel routes, and study a problem of personalized trip recommendation meets real-world constraints, by considering personalized rating on POIs and multiple constraints such as the time budget, the time window for the POI availability, the uncertainty of traveling time between POIs. We develop two efficient optimal solutions and two heuristic solutions for finding "good trips" with a significantly better runtime. Finally, in consideration of the sparsity of users' historical rating data and people's dynamically changed mind over time, we further study an on-demand route search problem with personalized diversity requirement on POIs, where users can specify their preferred features for the route and a personalized quantity (number of POIs) and variety (the coverage of the specified features) trade-offs. We propose to model users' personalized route diversity requirement by submodular functions that support the diminishing marginal utility property. We design generic and elegant optimal algorithm as well as heuristic algorithms. Comprehensive empirical evaluations on real life data sets demonstrate the effectiveness and efficiency of our methods.

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

Enabling autonomous mobile robots in dynamic environments with computer vision

Date created: 
2018-04-19
Abstract: 

Autonomous mobile robots are becoming more prevalent in our society as they become more useful. Often the environments we would like to see robots working in will be dynamic, with objects like people moving throughout. This thesis explores methods to make autonomous mobile robots more effective in the presence of dynamic objects. Specifically, two applications are developed on top of existing computer vision techniques where robots interact directly with moving objects. The first application involves multiple robots collaboratively sensing and following an arbitrary moving object. This is the first demonstration of its kind where robots jointly localize themselves and an object of interest while planning motion that is sympathetic to the vision system. Live robot experiments are conducted demonstrating the efficacy of the proposed system. The second application is a novel human-robot interaction system based on face engagement applied to an unmanned aerial vehicle (UAV). A unique use of facial recognition software enables an uninstrumented user to command a UAV with only their face. A series of experiments demonstrate the effectiveness of the interaction system for sending UAVs on a variety of flight trajectories.

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

Structured label inference for visual understanding

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

Visual data such as images and videos contain a rich source of structured semantic labels as well as a wide range of interacting components. Visual content could be assigned with fine-grained labels describing major components, coarse-grained labels depicting high level abstractions, or a set of labels revealing attributes. Such categorization over different, interacting layers of labels evinces the potential for a graph-based encoding of label information. In this thesis, we exploit this rich structure for performing graph-based inference in label space for a number of tasks: multi-label image and video classification and action detection in untrimmed videos. We consider the use of the Bidirectional Inference Neural Network (BINN) and Structured Inference Neural Network (SINN) for performing graph-based inference in label space and propose a Long Short-Term Memory (LSTM) based extension for exploiting activity progression on untrimmed videos. The methods were evaluated on (i) the Animal with Attributes (AwA), Scene Understanding (SUN) and NUS-WIDE datasets for multi-label image classification, (ii) the first two releases of the YouTube-8M large scale dataset for multi-label video classification, and (iii) the THUMOS’14 and MultiTHUMOS video datasets for action detection. Our results demonstrate the effectiveness of structured label inference in these challenging tasks, achieving significant improvements against baselines.

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

Robust real-time hands-and-face detection for human robot interaction

Date created: 
2018-04-27
Abstract: 

With recent advances, robots have become more affordable and intelligent, which expands their application domain and number of consumers. Having robots around us in our daily lives creates a demand for an interaction system for communicating humans' intentions and commands to robots. We are interested in interactions that are easy, intuitive, and do not require the human to use any additional equipment. We present a robust real-time system for visual detection of hands and faces in RGB and gray-scale images based on a Deep Convolutional Neural Network. This system is designed to meet the requirements of a hands-free interface to UAVs described below that could be used for communicating to other robots equipped with a monocular camera using only hands and face gestures without any extra instruments. This work is accompanied by a novel hands-and-faces detection dataset gathered and labelled from a wide variety of sources including our own Human-UAV interaction videos, and several third-party datasets. By training our model on all these data, we obtain qualitatively good detection results in terms of both accuracy and speed on a commodity GPU. The same detector gives state-of-the-art accuracy and speed in a hand-detection benchmark and competitive results in a face detection benchmark. To demonstrate its effectiveness for Human-Robot Interaction we describe its use as the input to a novel, simple but practical gestural Human-UAV interface for static gesture detection based on hand position relative to the face. A small vocabulary of hand gestures is used to demonstrate our end-to-end pipeline for un-instrumented human-UAV interaction useful for entertainment or industrial applications. All software, training and test data produced for this thesis is released as an Open Source contribution.

Document type: 
Thesis
File(s): 
A demonstration of our system for un-instrumented Human-UAV interaction
Senior supervisor: 
Richard Vaughan
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.

On some nonlinear assignment problems

Author: 
Date created: 
2018-02-27
Abstract: 

Linear assignment problem (commonly referred to as just assignment problem) is a fundamental problem in combinatorial optimization. The goal is to assign n workers to do n jobs so that the linear sum of corresponding costs is minimized. The linear assignment problem is thoroughly studied and has a O(n^3) solution with Hungarian algorithm. Nevertheless, a wide range of applications involving assignments are naturally modeled with more complex objective functions (for example quadratic sum as in quadratic assignment problem), and are much more computationally challenging. In this thesis we discuss our results on the bilinear assignment problem, which generalizes the quadratic assignment problem, and is also motivated by several unique applications. The focus is on computational complexity, solvable special cases, approximations, linearizations as well as local search algorithms and other heuristic approaches for the problem. We also present our results on few applied projects, where modelling the underlying problem as a nonlinear assignment was instrumental.

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

Model trees for identifying exceptional players in the NHL and NBA draft

Author: 
Date created: 
2018-04-10
Abstract: 

Drafting players is crucial for a team’s success. We describe a data-driven interpretable approach for assessing prospects in the National Hockey League and National Basketball Association. Previous approaches have built a predictive model based on player features, or derived performance predictions from comparable players. Our work develops model tree learning, which incorporates strengths of both model-based and cohort-based approaches. A model tree partitions the feature space according to the values or learned thresholds of features. Each leaf node in the tree defines a group of players, with its own regression model. Compared to a single model, the model tree forms an ensemble that increases predictive power. Compared to cohort-based approaches, the groups of comparables are discovered from the data, without requiring a similarity metric. The model tree shows better predictive performance than the actual draft order from team's decision. It can also be used to highlight strongest points of players.

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

When learning meets RFIDs: The case of activity identification

Author: 
Date created: 
2018-04-04
Abstract: 

Over the past decades have seen booming interests in human activity identification that is widely used in a range of Internet-of-Things applications, such as healthcare and smart homes. It has attracted significant attention from both academia and industry, with a wide range of solutions based on cameras, radars, and/or various inertial sensors. They generally require the object of identification to carry sensors/wireless transceivers, which are not negligible in both size and weight, not to mention the constraints from the battery. Radio frequency identification (RFID) is a promising technology that can overcome those difficulties due to its low cost, small form size, and batterylessness, making it widely used in a range of mobile applications. The information offered by today's RFID tags however are quite limited, and the typical raw data (RSSI and phase angles) are not necessarily good indicators of human activities (being either insensitive or unreliable as revealed by our realworld experiments). As such, existing RFID-based activity identification solutions are far from being satisfactory. It is also well known that the accuracy of the readings can be noticeably affected by multipath, which unfortunately is inevitable in an indoor environment and is complicated with multiple reference tags. In this thesis, we first reviewed the literature and research challenges of multipath effects in activity identification with RFIDs. Then we introduced three advanced RFID learning-based activity identification frameworks, i.e., i2tag, TagFree and M2AI, for tag mobility profiling, RFID-based device-free activity identification and tag-attached multi-object activity identification, respectively. Our extensive experiments further demonstrate their superiority on activity identification in the multipath-rich environments.

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

Improving software quality for regular expression matching tools using automated combinatorial testing

Date created: 
2017-12-19
Abstract: 

Regular expression matching tools (grep) match regular expressions to lines of text. However, because of the complexity that regular expressions can reach, it is challenging to apply state of the art automated testing frameworks to grep tools. Combinatorial testing has shown to be an effective testing methodology, especially for systems with large input spaces. In this dissertation, we investigate the approach of a fully automated combinatorial testing system for regular expression matching tools CoRE (Combinatorial testing for Regular Expressions). CoRE automatically generates test cases using combinatorial testing and measures correctness using differential testing. CoRE outperformed AFL and AFLFast in terms of code coverage testing icGrep, GNU grep and PCRE grep.

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