Alumni Dissertations and Theses

 
 

Alumni Dissertations and Theses

Filter Dissertations and Theses By:

 
 
  • Low-rank Based Algorithms for Rectification, Repetition Detection and De-noising in Urban Images

    Author:
    Juan Liu
    Year of Dissertation:
    2015
    Program:
    Computer Science
    Advisor:
    Ioannis Stamos
    Abstract:

    In this thesis, we aim to solve the problem of automatic image rectification and repeated patterns detection on 2D urban images, using novel low-rank based techniques. Repeated patterns (such as windows, tiles, balconies and doors) are prominent and significant features in urban scenes. Detection of the periodic structures is useful in many applications such as photorealistic 3D reconstruction, 2D-to-3D alignment, facade parsing, city modeling, classification, navigation, visualization in 3D map environments, shape completion, cinematography and 3D games. However both of the image rectification and repeated patterns detection problems are challenging due to scene occlusions, varying illumination, pose variation and sensor noise. Therefore, detection of these repeated patterns becomes very important for city scene analysis. Given a 2D image of urban scene, we automatically rectify a facade image and extract facade textures first. Based on the rectified facade texture, we exploit novel algorithms that extract repeated patterns by using Kronecker product based modeling that is based on a solid theoretical foundation. We have tested our algorithms in a large set of images, which includes building facades from Paris, Hong Kong and New York.

  • Data-Driven Synthesis of Animations of Spatially Inflected American Sign Language Verbs Using Human Data

    Author:
    Pengfei Lu
    Year of Dissertation:
    2014
    Program:
    Computer Science
    Advisor:
    Matt Huenerfauth
    Abstract:

    Techniques for producing realistic and understandable animations of American Sign Language (ASL) have accessibility benefits for signers with lower levels of written language literacy. Previous research in sign language animation didn't address the specific linguistic issue of space use and verb inflection, due to a lack of sufficiently detailed and linguistically annotated ASL corpora, which is necessary for modern data-driven approaches. In this dissertation, a high-quality ASL motion capture corpus with ASL-specific linguistic structures is collected, annotated, and evaluated using carefully designed protocols and well-calibrated motion capture equipment. In addition, ASL animations are modeled, synthesized, and evaluated based on samples of ASL signs collected from native-signer animators or from signers recorded using motion capture equipment. Part I of this dissertation focuses on how an ASL corpus is collected, including unscripted ASL passages and ASL inflecting verbs, signs in which the location and orientation of the hands is influenced by the arrangement of locations in 3D space that represent entities under discussion. Native signers are recorded in a studio with motion capture equipment: cyber-gloves, body suit, head tracker, hand tracker, and eye tracker. Part II describes how ASL animation is synthesized using our corpus of ASL inflecting verbs. Specifically, mathematical models of hand movement are trained on animation data of signs produced by a native signer. This dissertation work demonstrates that mathematical models can be trained and built using movement data collected from humans. The evaluation studies with deaf native signer participants show that the verb animations synthesized from our models have similar understandability in subjective-rating and comprehension-question scores to animations produced by a human animator, or to animations driven by a human's motion capture data. The modeling techniques in this dissertation are applicable to other types of ASL signs and to other sign languages used internationally. These models' parameterization of sign animations can increase the repertoire of generation systems and can automate the work of humans using sign language scripting systems.

  • Efficient Processing of Very Large XML Documents in Small Space

    Author:
    Matthew Meyer
    Year of Dissertation:
    2012
    Program:
    Computer Science
    Advisor:
    Ira Rudowsky
    Abstract:

    The focus of this research was to develop a highly efficient serialized data structure for use in Document Object Model (DOM) query systems of Extensible Markup Language (XML) documents, which are increasingly the dominant model for data representation across the World Web. The space efficiency of the serialized data structure developed is shown to improve query response time and eliminates the need to rebuild the DOM representation each time it is desired to query an existing XML document. Moreover, this serialized data structure enables DOM modeling of extremely large XML documents at a low and fixed memory cost. New algorithms and software tools for working with these data structures have been developed and this allows for compatibility with standard DOM modeling. The structures, tool and techniques presented can be readily adapted for use on the Semantic Web as it becomes a more prominent feature of the internet. The improved performance of the XML database storage and retrieval application developed in this thesis helps close the gap between relational database application performance and XML Document (NXD) database application performance. In addition, the novel DOM querying technique that we have developed in this thesis has potential application on hand held devices, autonomous robots, and other devices which have limited memory.

  • The Computational Complexity of Some Games and Puzzles With Theoretical Applications

    Author:
    Vasiliki Mitsou
    Year of Dissertation:
    2014
    Program:
    Computer Science
    Advisor:
    Amotz Bar-Noy
    Abstract:

    The subject of this thesis is the algorithmic properties of one- and two-player games people enjoy playing, such as Sudoku or Chess. Questions asked about puzzles and games in this context are of the following type: can we design efficient computer programs that play optimally given any opponent (for a two-player game), or solve any instance of the puzzle in question? We examine four games and puzzles and show algorithmic as well as intractability results. First, we study the wolf-goat-cabbage puzzle, where a man wants to transport a wolf, a goat, and a cabbage across a river by using a boat that can carry only one item at a time, making sure that no incompatible items are left alone together. We study generalizations of this puzzle, showing a close connection with the Vertex Cover problem that implies NP-hardness as well as inapproximability results. Second, we study the SET game, a card game where the objective is to form sets of cards that match in a certain sense using cards from a special deck. We study single- and multi-round variations of this game and establish interesting con- nections with other classical computational problems, such as Perfect Multi- Dimensional Matching, Set Packing, Independent Edge Dominating Set, and Arc Kayles. We prove algorithmic and hardness results in the classical and the parameterized sense. Third, we study the UNO game, a game of colored numbered cards where players take turns discarding cards that match either in color or in number. We extend results by Demaine et. al. (2010 and 2014) that connected one- and two-player generaliza- tions of the game to Edge Hamiltonian Path and Generalized Geography, proving that a solitaire version parameterized by the number of colors is fixed param- eter tractable and that a k-player generalization for k greater or equal to 3 is PSPACE-hard. Finally, we study the Scrabble game, a word game where players are trying to form words in a crossword fashion by placing letter tiles on a grid board. We prove that a generalized version of Scrabble is PSPACE-hard, answering a question posed by Demaine and Hearn in 2008.

  • Panorama Generation for Stereoscopic Visualization of Large-Scale Scenes

    Author:
    Edgardo Molina
    Year of Dissertation:
    2015
    Program:
    Computer Science
    Advisor:
    Zhigang Zhu
    Abstract:

    In this thesis, we address the problem of modeling and stereoscopically visualizing large-scale scenes captured with a single moving camera. In many applications that image large-scale scenes the critical information desired is the 3D spatial information of stationary objects and movers within the scene. Stereo panoramas, like regular panoramas, provide a wide field-of-view that can represent the entire scene, with the stereo panoramas additionally representing the motion parallax and allowing for 3D visualization and reconstruction of the scene. The primary issue with stereo panorama construction methods is that they are constrained for a particular camera motion model; typically the camera is constrained to move along a linear or circular path. Here we present a method for constructing stereo panoramas for general camera motion, and we develop a (1) Unified Stereo Mosaic Framework that handles general camera motion models. To construct stereo panoramas for general motion we created a new (2) Stereo Mosaic Layering algorithm that speeds up panorama construction enabling real-time applications. In large-scale scene applications it is often the case that the scene will be imaged persistently by passing over the same path multiple times or two or more sensors of different modalities will pass over the the same scene. To address these issues we developed methods for (3) Multi-Run and Multi-Modal Mosaic Alignment. Finally, we developed an (4) Intelligent Stereo Visualization that allows a viewer to interact and stereoscopically view the stereo panoramas developed from general motion.

  • A Tiling Approach to Producing High Quality Solutions to Real World Timetabling Problems

    Author:
    Douglas Moody
    Year of Dissertation:
    2011
    Program:
    Computer Science
    Advisor:
    Amotz Bar-Noy
    Abstract:

    The problem of constructing timetables in a fast and efficient manner is faced by a wide variety of scheduling practitioners. These timetables may specify the weekly calendar of university courses for a semester or contain the dates and times of games for a sports league. Current areas of research in timetabling have focused on problem instances that are small and often not representative of the real world challenges. Hence, the solution approaches proposed often do not solve the needs of the scheduling practitioner. This thesis describes a robust and efficient technique using a new approach, referred to as "tiling, "to provide high quality solutions for a variety of timetabling problems. The tiling method is an efficient and flexible method capable of managing the size and complexity of real world timetables. The tiles in this method represent conjectures about the relationship among the events to be scheduled within a timetabling problem. A constructive approach is used to create an initial solution in phase one of the tiling method. A second phase of local search is used to tune the solution. We demonstrate the flexibility of the approach through its application to large and small problems in various timetabling areas. By applying our method to problems in previous studies, we are able to demonstrate how our tiles are found within the best known solutions to date, and are comparable in quality with respect to the objective function. Yet the tiling approach only uses a small fraction of the computing resources used in the best approaches. Using our tiling approach, we directly address real world timetables to demonstrate its adaptability to real world scenarios. For example, the tiling approach has successfully been applied to sports leagues containing over five hundred teams for a youth sports league. In addition to the number of teams involved, this scheduling problem has other layers of complexity not previously addressed in other studies. Importantly, these leagues are more numerous than the professional sports, which have been the subject of most research to date. We introduce and define a new sports scheduling problem to encourage the further study of more common real world timetabling challenges.

  • 2D DIctionary Matching in Small Space

    Author:
    Shoshana Neuburger
    Year of Dissertation:
    2012
    Program:
    Computer Science
    Advisor:
    Dina Sokol
    Abstract:

    The dictionary matching problem seeks all locations in a given text that match any of the patterns in a given dictionary. Efficient algorithms for dictionary matching scan the text once, searching for all patterns simultaneously. There are many scenarios in which storage capacity is limited or the data sets are exceedingly large. The added constraint of performing efficient dictionary matching using little or no extra space is a challenging and practical problem. This thesis focuses on the problem of performing dictionary matching on two-dimensional data in small space. We have developed the first efficient algorithms for succinct 2D dictionary matching in both static and dynamically changing data. Although time and space optimal dictionary matching algorithms for one-dimensional data have recently been developed, they have not yet been implemented. Since our two-dimensional algorithms employ one-dimensional dictionary matching, we created software to solve one-dimensional dictionary matching in small space. This is a first step towards developing software for succinct dictionary matching in two-dimensional data.

  • AUTOMATED AUCTION MECHANISM DESIGN WITH COMPETING MARKETPLACES

    Author:
    Jinzhong Niu
    Year of Dissertation:
    2011
    Program:
    Computer Science
    Advisor:
    Simon Parsons
    Abstract:

    Resource allocation is a major issue in multiple areas of computer science. Auctions are commonly used in optimizing resource allocation in these areas, since well designed auctions achieve desirable economic outcomes including high allocative efficiency and fast response to supply and demand changes. This dissertation presents a grey-box approach to automated auction mechanism design using reinforcement learning and evolutionary computation methods. In contrast to the traditional approaches that try to design complete auction mechanisms manually, which is tedious and error-prone, the grey-box approach solves the problem through an automated search in a parameterized space of auction mechanisms. This space is defined by a novel, parameterized structure for auction mechanisms — a big white box — and a set of auction rules — each as a small black box — that can fit into the structure. The grey-box approach uses reinforcement learning to explore the composition of the structure, relates the performance of auction mechanisms to that of auction rules that form the mechanisms, and utilizes a Hall of Fame, a technique from evolutionary computation, to maintain viable auction mechanisms. The evaluation of auction mechanisms in the grey-box approach is conducted through a new strategic game, called CAT, which allows multiple marketplaces to run in parallel and compete to attract traders and make a profit. The CAT game helps to address the imbalance between prior work in this field that studied isolated auctions and the actual competitive situation that marketplaces face. Experiments were carried out to examine the effectiveness of the grey-box approach. A comparison against the genetic algorithm approach showed that the grey-box approach was able to produce mechanisms with significantly better overall performance. The best produced mechanisms from the grey-box experiments were able to outperform both the standard mechanisms which were used in evaluating sampled mechanisms during the grey-box search and carefully hand-coded mechanisms which won tournaments based on the CAT game. These best mechanisms also exhibited better performance than some existing mechanisms from the literature even when the evaluation did not take place in the context of CAT games.

  • Computer-Aided Reasoning about Knowledge and Justifications

    Author:
    Natalia Novak
    Year of Dissertation:
    2009
    Program:
    Computer Science
    Advisor:
    Sergei Artemov
    Abstract:

    The dissertation consists of two Chapters. In the first Chapter we compare two well-known type-based computer frameworks for computer aided logical reasoning and verification: MetaPRL and Coq. In particular, we implement in MetaPRL the Calculus of Inductive Constructions which is the theoretical base for Coq. This work has shown the common points of MetaPRL and Coq, and revealed their principal methodological differences. A possible application of this work is a possibility to perform re-validation in MetaPRL of the existing library of Coq proofs which could help to build more trust in the latter. Chapter 2 is the main contribution of the dissertation. It contains the description and testing results of an implementation of realization algorithm in epistemic modal logic that converts cut-free derivations in multi-agent epistemic modal logic into derivations in the corresponding Justification Logic where witnesses of knowledge (justification terms) are recovered for all instances of common knowledge. We also apply this algorithms to several well-known epistemic puzzles, such as Muddy Children, Wise Men, Wise Girls, etc.

  • Cancer Progression: Model, Therapy & Extraction

    Author:
    Loes Olde Loohuis
    Year of Dissertation:
    2013
    Program:
    Computer Science
    Advisor:
    Rohit Parikh
    Abstract:

    In this thesis we develop Cancer Hybrid Automata (CHAs), a modeling framework based on hybrid automata, to model the progression of cancers through discrete phenotypes. Both transition timing between states as well as the effect of drugs and clinical tests are parameters in the framework, thus allowing for the formalization of temporal statements about the progression as well as timed therapies. Using a game theoretical formulation of the problem we show how existing controller synthesis algorithms can be generalized to CHA models, so that (timed) therapies can be automatically generated. In the second part of this thesis we connect this formal framework to cancer patient data, focusing on copy number variation (CNV) data. The underlying process generating CNV segments is generally assumed to be memory-less, giving rise to an exponential distribution of segment lengths. We provide evidence from TCGA data suggesting that this generative model is too simplistic, and that segment lengths follow a power-law distribution instead. We show how an existing statistical method for detecting genetic regions of relevance for cancer can be improved through more accurate (power-law) null models. Finally, we develop an algorithm to extract CHA-like progression models from cross-sectional patient data. Based on a performance comparison on synthetic data, we show that our algorithm, which is based on a notion of probabilistic causality, outperforms an existing extraction method.