Theory and Algorithms Commons^™

An Efficient Partial Shape Matching Algorithm For 3d Tooth Recognition, Zhiyuan Zhang, Xin Zhong, Sim Heng Ong, Kelvin W. C. Foong

Research Collection School Of Computing and Information Systems

As a new biometric strategy, tooth recognition has drawn much attention in recent years. However, most existing work focus mainly on 2D dental radiographs which are less informative and vulnerable to noise and pose variance. Although there are already several attempts on 3D tooth recognition, the results are still inaccurate and performance is inefficient. Moreover, existing methods cannot recognize precisely when the post-mortem data contains incomplete teeth. In this work, we propose an efficient and accurate partial shape matching algorithm to recognize 3D teeth for human identification. Given the ante-mortem and post-mortem teeth models which were taken from patients using …

Algorithms For Grid Graphs In The Mapreduce Model, Taylor P. Spangler

School of Computing: Dissertations, Theses, and Student Research

The MapReduce programming paradigm has seen widespread use in analyzing large data sets. Often these large data sets can be formulated as graphs. Many algorithms, such as filtering based algorithms, are designed to work efficiently for dense graphs - graphs with substantially more number of edges than the number of vertices. These algorithms are not optimized for sparse graphs - graphs where the number of edges is of the same order as the number of vertices. However, sparse graphs are also common in big data sets. In this thesis we present algorithms for maximal matching, approximate edge covering, and approximate …

Parallel Implementations Of The Frank-Wolfe Algorithms For The Traffic Assignment Problem, Shawn Eugene Allen

Computational Modeling & Simulation Engineering Theses & Dissertations

Transportation planners seek to understand how to best invest limited resources for future transportation network development. The traffic assignment problem is one algorithm of great importance to planners because it provides insight into how traffic will flow within the network. The Frank-Wolfe algorithm is a traditional solution method for this optimization problem, but it has been characterized by its slow rate of convergence and poor computational performance. This thesis examines and implements several modern advancements in this algorithm which are designed to improve the rate of convergence.

In addition to algorithm changes, another method to improve the performance of an …

Todmis: Mining Communities From Trajectories, Siyuan Liu, Shuhui Wang, Kasthuri Jayarajah, Archan Misra, Rammaya Krishnan

Research Collection School Of Computing and Information Systems

Existing algorithms for trajectory-based clustering usually rely on simplex representation and a single proximity-related distance (or similarity) measure. Consequently, additional information markers (e.g., social interactions or the semantics of the spatial layout) are usually ignored, leading to the inability to fully discover the communities in the trajectory database. This is especially true for human-generated trajectories, where additional fine-grained markers (e.g., movement velocity at certain locations, or the sequence of semantic spaces visited) can help capture latent relationships between cluster members. To address this limitation, we propose TODMIS: a general framework for Trajectory cOmmunity Discovery using Multiple Information Sources. TODMIS combines …

Consistent Stereo Image Editing, Tao Yan, Shengfeng He, Rynson W.H. Lau, Yun Xu

Research Collection School Of Computing and Information Systems

Stereo images and videos are very popular in recent years, and techniques for processing this media are attracting a lot of attention. In this paper, we extend the shift-map method for stereo image editing. Our method simultaneously processes the left and right images on pixel level using a global optimization algorithm. It enforces photo consistence between the two images and preserves 3D scene structures. It also addresses the occlusion and disocclusion problem, which may enable many stereo image editing functions, such as depth mapping, object depth adjustment and non-homogeneous image resizing. Our experiments show that the proposed method produces high …

A Robust Rgbd Slam System For 3d Environment With Planar Surfaces, Po-Chang Su, Ju Shen, Sen-Ching S. Cheung

Computer Science Faculty Publications

With the increasing popularity of RGB-depth (RGB-D) sensors such as the Microsoft Kinect, there have been much research on capturing and reconstructing 3D environments using a movable RGB-D sensor. The key process behind these kinds of simultaneous location and mapping (SLAM) systems is the iterative closest point or ICP algorithm, which is an iterative algorithm that can estimate the rigid movement of the camera based on the captured 3D point clouds. While ICP is a well-studied algorithm, it is problematic when it is used in scanning large planar regions such as wall surfaces in a room. The lack of depth …

Computing The Grounded Semantics In All The Subgraphs Of An Argumentation Framework: An Empirical Evaluation, Pierpaolo Dondio

Articles

Given an argumentation framework – with a finite set of arguments and the attack relation identifying the graph – we study how the grounded labelling of a generic argument a varies in all the subgraphs of . Since this is an intractable problem of above-polynomial complexity, we present two non-naïve algorithms to find the set of all the subgraphs where the grounded semantic assigns to argument a specific label . We report the results of a series of empirical tests over graphs of increasing complexity. The value of researching the above problem is two-fold. First, knowing how an argument behaves …

Reaper – Toward Automating Mobile Cloud Communication, Daniel R. Ward

LSU New Orleans Theses and Dissertations

Mobile devices connected to cloud based services are becoming a mainstream method of delivery up-to-date and context aware information to users. Connecting mobile applications to cloud service require significant developer effort. Yet this communication code usually follows certain patterns, varying accordingly to the specific type of data sent and received from the server. By analyzing the causes of theses variations, we can create a system that can automate the code creation for communication from a mobile device to a cloud server. To automate code creation, a general pattern must extracted. This general solution can then be applied to any database …

Using Contracts To Guide The Search-Based Verification Of Concurrent Programs, Christopher M. Poskitt, Simon Poulding

Research Collection School Of Computing and Information Systems

Search-based techniques can be used to identify whether a concurrent program exhibits faults such as race conditions, deadlocks, and starvation: a fitness function is used to guide the search to a region of the program’s state space in which these concurrency faults are more likely occur. In this short paper, we propose that contracts specified by the developer as part of the program’s implementation could be used to provide additional guidance to the search. We sketch an example of how contracts might be used in this way, and outline our plans for investigating this verification approach.

Applying Search In An Automatic Contract-Based Testing Tool, Alexey Kolesnichenko, Christopher M. Poskitt, Bertrand Meyer

Research Collection School Of Computing and Information Systems

Automated random testing has been shown to be effective at finding faults in a variety of contexts and is deployed in several testing frameworks. AutoTest is one such framework, targeting programs written in Eiffel, an object-oriented language natively supporting executable pre- and postconditions; these respectively serving as test filters and test oracles. In this paper, we propose the integration of search-based techniques—along the lines of Tracey—to try and guide the tool towards input data that leads to violations of the postconditions present in the code; input data that random testing alone might miss, or take longer to find. Furthermore, we …

Near-Duplicate Video Retrieval: Current Research And Future Trends, Jiajun Liu, Zi Huang, Hongyun Cai, Heng Tao Shen, Chong-Wah Ngo, Wei Wang

Research Collection School Of Computing and Information Systems

The exponential growth of online videos, along with increasing user involvement in video-related activities, has been observed as a constant phenomenon during the last decade. User's time spent on video capturing, editing, uploading, searching, and viewing has boosted to an unprecedented level. The massive publishing and sharing of videos has given rise to the existence of an already large amount of near-duplicate content. This imposes urgent demands on near-duplicate video retrieval as a key role in novel tasks such as video search, video copyright protection, video recommendation, and many more. Driven by its significance, near-duplicate video retrieval has recently attracted …

An Empirical Analysis Of A Network Of Expertise, Le Truc Viet, Minh Thap Nguyen

Research Collection School Of Computing and Information Systems

In this paper, we analyze the network of expertise constructed from the interactions of users on the online questionanswering (QA) community of Stack Overflow. This community was built with the intention of helping users with their programming tasks and, thus, questions are expected to be highly factual. This also indicates that the answers one provides may be highly indicative of one's level of expertise on the subject matter. Therefore, our main concern is how to model and characterize the user's expertise based on the constructed network and its centrality measures. We used the user's reputation established on Stack Overflow as …

Vigilance Adaptation In Adaptive Resonance Theory, Lei Meng, Ah-Hwee Tan, Donald C. Winsch

Research Collection School Of Computing and Information Systems

Despite the advantages of fast and stable learning, Adaptive Resonance Theory (ART) still relies on an empirically fixed vigilance parameter value to determine the vigilance regions of all of the clusters in the category field (F 2 ), causing its performance to depend on the vigilance value. It would be desirable to use different values of vigilance for different category field nodes, in order to fit the data with a smaller number of categories. We therefore introduce two methods, the Activation Maximization Rule (AMR) and the Confliction Minimization Rule (CMR). Despite their differences, both ART with AMR (AM-ART) and with …

Adaptive Collective Routing Using Gaussian Process Dynamic Congestion Models, Siyuan Liu, Yisong Yue, Ramayya Krishnan

Research Collection School Of Computing and Information Systems

We consider the problem of adaptively routing a fleet of cooperative vehicles within a road network in the presence of uncertain and dynamic congestion conditions. To tackle this problem, we first propose a Gaussian Process Dynamic Congestion Model that can effectively characterize both the dynamics and the uncertainty of congestion conditions. Our model is efficient and thus facilitates real-time adaptive routing in the face of uncertainty. Using this congestion model, we develop an efficient algorithm for non-myopic adaptive routing to minimize the collective travel time of all vehicles in the system. A key property of our approach is the ability …

Linear Programming Algorithm With Mixed Real-Integer Variables In Matlab Environments, Gelareh Bakhtyar

Civil & Environmental Engineering Theses & Dissertations

Efficient numerical procedures for solving general Linear Programming (LP) problems with mixed real-integer variables are developed in this work. The proposed algorithms employ the revised dual simplex with Branch and Bound (B&B) algorithms, with special procedures for limited search of subsequent branches. Computational time can be significantly reduced by incorporating the updated inverse formulas into the developed procedures. Both generic LP problems and deterministic pavement maintenance and rehabilitation (M&R) problems are used in this study to vaiidate the developed procedures. Medium to large-scale examples ( 11 pavement M&R) presented in this work have demonstrated that the developed numerical procedures consistently …

Optimization Of Solar Cell Arrays Using The Fibonacci Search Algorithm, Felicia Tyyan Farrow

Electrical & Computer Engineering Theses & Dissertations

In our energy hungry world, there is a growing demand to develop creative mechanisms to extract, conserve, and use energy from different resources. The use of solar cells to extract and convert solar energy into electrical energy is a growing and popular field of study because solar energy is clean, free, and renewable. One limitation for photovoltaic (PU) or solar technology is its loss in efficiency and availability as a result of shading or partial shading. Shading or partial shading decreases the total capable output power that the PV system can produce because the array is receiving irradiation from the …

Guidance In Feature Extraction To Resolve Uncertainty, Boris Kovalerchuk, Michael Kovalerchuk, Simon Streltsov, Matthew Best

Computer Science Faculty Scholarship

Automated Feature Extraction (AFE) plays a critical role in image understanding. Often the imagery analysts extract features better than AFE algorithms do, because analysts use additional information. The extraction and processing of this information can be more complex than the original AFE task, and that leads to the “complexity trap”. This can happen when the shadow from the buildings guides the extraction of buildings and roads. This work proposes an AFE algorithm to extract roads and trails by using the GMTI/GPS tracking information and older inaccurate maps of roads and trails as AFE guides.

Protocases, Christopher M. Polis

Computer Engineering

Design and implementation of a 3D printing web application.

Integrated Collision Avoidance System Sensor Evaluation Final Design Project, Alex F. Graebe, Bridgette S. Kimball, Drew T. Lavoise

Mechanical Engineering

Following the development of Aircraft Collision Avoidance Technology (ACAT) by the National Aeronautics and Space Administration (NASA), a need arose to transition the life-saving technology to aid the general aviation community. Considering the realistic cost of implementation, it was decided that the technology should be adapted to function on any smartphone, using that device as an end-to-end solution to sense, process, and alert the pilot to imminent threats. In September of 2012, the SAS (Sense and Survive) Senior Project Team at California Polytechnic University (Cal Poly), San Luis Obispo was assigned the task of using smartphone technology to accurately sense …

Visual Tracking Via Locality Sensitive Histograms, Shengfeng He, Qingxiong Yang, Rynson W.H. Lau, Jian Wang, Ming-Hsuan Yang

Research Collection School Of Computing and Information Systems

This paper presents a novel locality sensitive histogram algorithm for visual tracking. Unlike the conventional image histogram that counts the frequency of occurrences of each intensity value by adding ones to the corresponding bin, a locality sensitive histogram is computed at each pixel location and a floating-point value is added to the corresponding bin for each occurrence of an intensity value. The floating-point value declines exponentially with respect to the distance to the pixel location where the histogram is computed, thus every pixel is considered but those that are far away can be neglected due to the very small weights …