Alumni Dissertations

 

Alumni Dissertations

Filter Dissertations By:

 
 
  • 3D SCENE MODELING AND UNDERSTANDING FROM IMAGE SEQUENCES

    Author:
    Hao Tang
    Year of Dissertation:
    2013
    Program:
    Computer Science
    Advisor:
    Zhigang Zhu
    Abstract:

    A new method for 3D modeling is proposed, which generates a content-based 3D mosaic (CB3M) representation for long video sequences of 3D, dynamic urban scenes captured by a camera on a mobile platform. In the first phase, a set of parallel-perspective (pushbroom) mosaics with varying viewing directions is generated to capture both the 3D and dynamic aspects of the scene under the camera coverage. In the second phase, a unified patch-based stereo matching algorithm is applied to extract parametric representations of the color, structure and motion of the dynamic and/or 3D objects in urban scenes, where a lot of planar surfaces exist. Multiple pairs of stereo mosaics are used for facilitating reliable stereo matching, occlusion handling, accurate 3D reconstruction and robust moving target detection. The outcome of this phase is a CB3M representation, which is a highly compressed visual representation for a dynamic 3D scene, and has object contents of both 3D and motion information. In the third phase, a multi-layer based scene understanding algorithm is proposed, resulting in a planar surface model for higher-level object representations. Experimental results are given for both simulated and several different real video sequences of large-scale 3D scenes to show the accuracy and effectiveness of the representation. We also show the patch-based stereo matching algorithm and the CB3M representation can be generalized to 3D modeling with perspective views using either a single camera or a stereovision head on a ground mobile platform or a pedestrian. Applications of the proposed method include airborne or ground video surveillance, 3D urban scene modeling, traffic survey, transportation planning and the visual aid for perception and navigation of blind people.

  • Efficient Communication Through Structured Node Labeling in Peer-to-Peer Networks

    Author:
    Andi Toce
    Year of Dissertation:
    2013
    Program:
    Computer Science
    Advisor:
    Abbe Mowshowitz
    Abstract:

    Peer to Peer (P2P) networks have become increasingly popular in recent years as administrators are choosing to move away from monolithic centralized networks. These networks, while offering significant advantages in a variety of applications, are presented with a new set of challenges, from communication efficiency to network vulnerability and security. Numerous researchers have proposed a variety of solutions to improve the quality of service in P2P networks. A critical factor in maintaining an acceptable level of service quality is the efficiency and reliability of communication among nodes. One way of improving communication is to assign identifiers (labels) to each node and then use these labels to facilitate and improve message routing. This proposed work introduces two labeling schemata for P2P networks. Each participating node is assigned a label set. Labels are then used to determine node positions within an engineered logical overlay and identify routing paths during communication. We prove that the assignment of labels reduces the overall cost of communication thus saving valuable network resources. These theoretical findings are confirmed by experimental results with randomly selected P2P networks of various sizes. Detailed statistics on the performance of each protocol are provided which show clearly the practical utility of the labeling approach.

  • AUTOMATED LEARNER CLASSIFICATION THROUGH INTERFACE EVENT STREAM AND SUMMARY STATISTICS ANALYSIS

    Author:
    Edgar Troudt
    Year of Dissertation:
    2014
    Program:
    Computer Science
    Advisor:
    Danny Kopec
    Abstract:

    Reading comprehension is predominately measured through multiple choice examinations. Yet, as we will discuss in this thesis, such exams are often criticized for their inaccuracies. With the advent of "big data" and the rise of ITS (Intelligent Tutoring Systems), increasing focus will be placed on finding dynamic, automated ways of measuring students' aptitude and progress. This work takes the first step towards automated learner classification based on the application of graphic organizers. We address the following specific problem experimentally: How effectively can we measure task comprehension via human translation of written text into a visual representation on a computer? Can an algorithm employ data from user interface (UI) interaction during the problem solving process, to classify the user's abilities? Specifically, from the data we show machine learning predictions of what a human expert would say about the: 1. integrity of the visual representation produced; 2. level of logical problem solving strategy the user applies to the exercise; 3. level of effort the user gives to the exercise. The core of the experiment is a software system that allows a human subject to read a preselected text and then "draw" a diagram by manipulating icons on a grid-canvas using standard transforms.

  • Algorithms and Hypothesis Selection in Dynamic Homology Phylogenetic Analysis

    Author:
    Andres Varon
    Year of Dissertation:
    2010
    Program:
    Computer Science
    Advisor:
    Amotz Bar-Noy
    Abstract:

    Phylogeny and alignment estimation are two important, and closely related biological problems. In the typical alignment problem, insertions, deletions, and substitutions need to be inferred, to understand the evolutionary patterns of life. With the technological advances of the last 20 years, phylogenetic analyses will grow to include complete chromosomes and genomes. With these data sets, not only insertions, deletions, and substitutions, but also rearrangements such as duplications, translocations, transpositions, and inversions must be taken into consideration. In this study, phylogenetic analysis is explored at three different levels. At the first level, new heuristic algorithms for the joint estimation of phylogenies and alignments under the Maximum Parsimony optimality criterion are described. Our experimental study showed that the new algorithms perform dramatically better when compared to previous heuristics. These new algorithms will allow biologists to analyze larger data sets in shorter periods of time. At the second level, new and existing algorithms where implemented in the computer program POY version 4. POY has had a significant impact in the biology community, and is used by hundreds of biologists around the world. POY will serve as a platform for long term research both in algorithm engineering, and biology. At the third level, the problem of parameter and model selection in complete chromosome analyses is explored. We propose and describe the use of Kolmogorov Complexity (KC) as optimality criterion, as a unifying criterion for phylogenetic analysis. Our evaluation using simulations showed that KC correctly identifies phylogeny and model with high frequency. These results are evidence that KC is very well suited for the difficulties posed by the phylogenetic analysis of complete genomes.

  • Timed Modal Epistemic Logic

    Author:
    Ren-June Wang
    Year of Dissertation:
    2012
    Program:
    Computer Science
    Advisor:
    Sergei Artemov
    Abstract:

    There will be three parts in this thesis. The first part is a survey of epistemic logic. Epistemic logic was first introduced by philosophers, and later found its applications in fields such as Computer Science and Economics. The survey will cover both the philosophical debates and applications of epistemic logic, and then discussions of the logical omniscience problem will follow. The second part is the introduction of a new logical framework timed Modal Epistemic Logic. tMEL. tMEL is extended from ordinary modal epistemic logic, MEL, by adding numerical labels to knowledge statement to indicate when the statement is known. We will argue how a logical framework reasoning about both knowledge and the time of reasoning can help to resolve the problem of logical omniscience, and tMEL serves well as a logically non-omniscient epistemic system. Finally, we will discuss the syntactical relations between MEL, tMEL, and Justification Logic, from which the study of MEL is originated. Our focus will be on the relations between axiomatic proofs of these logical frameworks. We will first determine a proper subclass of modal logical proofs called non-circular, and prove that this class of proofs is complete. And then we will show that every non-circular MEL proof can be turned into a tMEL proof by finding suitable number labels, and prove that there is a two-way translation between proofs in tMEL and Justification Logic. Combining these results, a formal connection between non-circular proofs and proofs in Justification Logic is established, and the whole procedure gives us an alternative algorithm for the realization between theorems in modal logic and Justification Logic. This is the end of the abstract.

  • AN ADAPTIVE AND INTEGRATED MULTIMODAL SENSING AND PROCESSING FRAMEWORK FOR LONG RANGE MOVING OBJECT DETECTION AND CLASSIFICATION

    Author:
    Tao Wang
    Year of Dissertation:
    2013
    Program:
    Computer Science
    Advisor:
    Zhigang Zhu
    Abstract:

    In applications such as surveillance, inspection and traffic monitoring, long-range detection and classification of targets (vehicles, humans, etc) is a highly desired feature for a sensing system. A single modality will no longer provide the required performance due to the challenges in detection and classification with low resolutions, noisy sensor signals, and various environmental factors due to large sensing distances. Multimodal sensing and processing, on the other hand, can provide complementary information from heterogeneous sensor modalities, such as audio, visual and range sensors. However, there is a lack of effective sensing mechanisms and systematic approaches for sensing and processing using multimodalities. In this thesis, we described a systematical framework for Adaptive and Integrated Multimodal Sensing and Processing (thereafter, the AIM-SP framework) that integrates novel multimodal long-range sensors, adaptive feature selection and learning-based object detection and classification for achieving the goal of adaptive and integrated multimodal sensing and processing. Based on the AIM-SP framework, we have made three unique contributions. First, we have designed a novel multimodal sensor system called Vision-Aided Automated Vibrometry (VAAV), which is capable of automatically obtaining visual, range and acoustic signatures for moving object detection at a large distance. Second, multimodal data, acquired from multiple sensing sources, are integrated and represented in a Multimodal Temporal Panorama (MTP) for easy alignment and fast labeling. Accuracy of target detection can be improved using multimodalities. Further, a visual reconstruction method is developed to remove occlusions, motion blurs and perspective distortions of moving vehicles. With various types of features extracted on aligned multimodal samples, we made our third contribution on feature modality selection using two approaches. The first approach uses multi-branch sequential-based feature searching (MBSF) and the second one uses boosting-based feature learning (BBFL).

  • A Parametrization-Based Surface Reconstruction System for Triangular Mesh Simplification with Application to Large Scale Scenes

    Author:
    Adriana Wise
    Year of Dissertation:
    2014
    Program:
    Computer Science
    Advisor:
    Ioannis Stamos
    Abstract:

    The laser scanner is nowadays widely used to capture the geometry of art, animation maquettes, or large architectural, industrial, and land form models. It thus poses specific problems depending on the model scale. This thesis provides a solution for simplification of triangulated data and for surface reconstruction of large data sets, where feature edges provide an obvious segmentation structure. It also explores a new method for model segmentation, with the goal of applying multiresolution techniques to data sets characterized by curvy areas and the lack of clear demarcation features. The preliminary stage of surface segmentation, which takes as input single or multiple scan data files, generates surface patches which are processed independently. The surface components are mapped onto a two-dimensional domain with boundary constraints, using a novel parametrization weight coefficient. This stage generates valid parameter domain points, which can be fed as arguments to parametric modeling functions or surface approximation schemes. On this domain, our approach explores two types of remeshing. First, we generate points in a regular grid pattern, achieving multiresolution through a flexible grid step, which nevertheless is designed to produce a globally uniform resampling aspect. In this case, for reconstruction, we attempt to solve the open problem of border reconciliation across adjacent domains by retriangulating the border gap between the grid and the fixed irregular border. Alternatively, we straighten the domain borders in the parameter domain and coarsely triangulate the resulting simplified polygons, resampling the base domain triangles in a 1-4 subdivision pattern, achieving multiresolution from the number of subdivision steps. For mesh reconstruction, we use a linear interpolation method based on the original mesh triangles as control points on local planes, using a saved triangle correspondence between the original mesh and the parametric domain. We also use a region-wide approximation method, applied to the parameter grid points, which first generates data-trained control points, and then uses them to obtain the reconstruction values at the resamples. In the grid resampling scheme, due to the border constraints, the reassembly of the segmented, sequentially processed data sets is seamless. In the subdivision scheme, we align adjacent border fragments in the parameter space, and use a region-to-fragment map to achieve the same border reconstruction across two neighboring components. We successfully process data sets up to 1,000,000 points in one pass of our program, and are capable of assembling larger scenes from sequential runs. Our program consists of a single run, without intermediate storage. Where we process large input data files, we fragment the input using a nested application of our segmentation algorithm to reduce the size of the input scenes, and our pipeline reassembles the reconstruction output from multiple data files into a unique view.

  • OPTIMIZATION ALGORITHMS FOR PROXY PLACEMENT IN CONTENT DISTRIBUTION NETWORKS

    Author:
    Jun Wu
    Year of Dissertation:
    2011
    Program:
    Computer Science
    Advisor:
    Kaliappa Ravindran
    Abstract:

    Popular web sites receive an enormous share of Internet traffic. These sites have a competitive motivation to offer better service to their clients at lower cost. One of the solutions is to using content distribution network (CDN). When we optimize proxy placement in content distribution network we want to maximize the user experience in the mean time to minimize the resource consumption. We are dealing with a multi-objective optimization problem for CDNs in the thesis: the content latency experienced by users and the system resources expended to deliver content. After the topology model for content distribution network, we listed metrics to evaluate content distribution network. Then we defined the objective function for optimizing proxy placement. After reviewing the existing proxy placement algorithms we used genetic algorithm to solve the proxy placement problem. We first apply the genetic algorithms to a simple network, and find that the results are better than greedy algorithm and identical to the global optimal. Then we apply the genetic algorithm to a realistically larger network topology. The genetic algorithm can find good solutions to the proxy placement problem. But compared to greedy algorithm, it is less efficient. So when response time is important, genetic algorithm is not the best choice. To optimize the genetic algorithm we found if we choose higher mutation rate and step size at the beginning of the genetic operation and decrease the mutation rate and step size as we go through the genetic operation, the results are much better. For the initial populations, if we want quick response to the sudden change of client access we can choose smaller initial population, if we have sufficient response time especially in initial setting up the network we should choose larger initial populations. Under optimized genetic algorithm, we experiment three different network examples with their sizes between the simple network and large network. Since the network sizes are smaller we are able to run the exhaustive search to find the global optimal. In all cases the results from genetic algorithm outperform greed algorithm and close to global optimal. Although it is not guaranteed to find the global optimal solution as the simple network did, a robust good solution is enough to solve real world problems.

  • A SIMULATION STUDY ON USING THE VIRTUAL NODE LAYER TO IMPLEMENT EFFICIENT AND RELIABLE MANET PROTOCOLS

    Author:
    Jiang Wu
    Year of Dissertation:
    2011
    Program:
    Computer Science
    Advisor:
    Nancy Griffeth
    Abstract:

    The Virtual Node Layer (VNLayer) is a cluster based programming abstraction for a Mobile Ad-Hoc Network. VNLayer defines fixed or predictably mobile geographical regions. In each region, a number of mobile nodes collectively emulate a virtual node, which provides services and relays packets for client processes. As a clustering scheme with state replication, the VNLayer approach can theoretically improve the efficiency and reliability of MANET protocols. As a general programming abstraction, the VNLayer hides underlying complexities from protocol developers and can be shared by multiple applications. However, the VNLayer also introduces extra control overhead and prolongs data forwarding delay, which could be prohibitively expensive in terms of performance. Based on an existing VNLayer implementation [1], we developed an ns-2 based software package, VNSim. VNSim can be used to simulate VNLayer based applications in a MANET of up to a few hundred mobile nodes, in order to better understand the impact of the VNLayer approach on efficiency and reliability. With VNSim, we did our first case study on a VNLayer based MANET address allocation protocol, VNDHCP. Simulation results proved that the VNLayer approach can be used to adapt a wireline protocol to MANET. We also did an extensive simulation study on VNLayer based MANET routing. A wireline routing protocol, RIP, was adapted to run over the VNLayer. With the support provided by the VNLayer, the adapted protocol, VNRIP, was implemented very quickly and can provide reasonable performance. During the study of VNLayer based MANET routing, we identified a number of major performance limitations in the existing VNLayer implementation and the models it is based on. To tackle the limitations, we created a more realistic link layer model, extended the VNLayer model and optimized our VNLayer implementation. With the optimized VNLayer implementation, we implemented VNAODV, an adapted version of AODV, over the new link and VNLayer models. Simulation results indicate that VNAODV delivers more packets and creates more stable routes than standard AODV in a dense MANET with high node motion rate and moderate data traffic. This research validated the intuition that the VNLayer approach can be used to adapt wireline protocols quickly to MANET and to improve the performance of MANET protocols. This research also provided us some insights on how to implement and optimize cluster based MANET protocols.

  • Piecewise Surface Reconstruction from Range Data

    Author:
    Gene Yu
    Year of Dissertation:
    2010
    Program:
    Computer Science
    Advisor:
    George Wolberg
    Abstract:

    Geometric modeling from range data is a long-standing problem in the field of computer graphics. It remains challenging even when the data is replete with simple surfaces such as planes and polynomials, as is common in urban scenes. The need to represent such scenes requires us to segment the data into its components. The collection of these components constitutes the final geometric model. This thesis introduces a method of piecewise surface reconstruction that fits a scene with a model composed of disjoint surfaces. The contribution of this work is the introduction of a surface evaluation method based on quantitative entropy measurements for balancing the tradeoff between accuracy and efficiency. Integrated surface evaluation enables us to produce output models that are accurate to within user-specified tolerances. Since our algorithm minimizes global criteria, it is robust to holes, occlusions, nonplanar surfaces, and missing data. Compared to methods that operate on unorganized point clouds and utilize no segmentation, our approach provides the user with greater control over the final appearance and error characteristics of the output model. A range of shape approximations such as plane, polynomial, and spline mesh surfaces can be used interchangeably. This flexibility is applicable to all scenes involving piecewise models.