Theory and Algorithms Commons^™

Dynamically Parallel Camshift: Gpu Accelerated Object Tracking In Digital Video, Matthew J. Perry

EWU Masters Thesis Collection

"The CAMSHIFT algorithm is widely used for tracking dynamically sized and positioned objects in real-time applications. In spite of its extensive study on the platform of sequential CPU, its research on massively parallel Graphical Processing Unit (GPU) platform is quite limited. In this work, we designed and implemented two different parallel algorithms for CAMSHIFT using CUDA. The first design performs calculations on the GPU, but requires iterative data transfers back to the host CPU for condition checking, which bottlenecks the entire program. In the second design, we propose an enhanced parallel reduction-based CAMSHIFT using dynamic parallelism to reduce overhead of …

Topics On Register Synthesis Problems, Weihua Liu

Theses and Dissertations--Computer Science

Pseudo-random sequences are ubiquitous in modern electronics and information technology. High speed generators of such sequences play essential roles in various engineering applications, such as stream ciphers, radar systems, multiple access systems, and quasi-Monte-Carlo simulation. Given a short prefix of a sequence, it is undesirable to have an efficient algorithm that can synthesize a generator which can predict the whole sequence. Otherwise, a cryptanalytic attack can be launched against the system based on that given sequence.

Linear feedback shift registers (LFSRs) are the most widely studied pseudorandom sequence generators. The LFSR synthesis problem can be solved by the Berlekamp-Massey algorithm, …

On Detecting Maximal Quasi Antagonistic Communities In Signed Graphs, Ming Gao, Ee-Peng Lim, David Lo, Philips Kokoh Prasetyo

Research Collection School Of Computing and Information Systems

Many networks can be modeled as signed graphs. These include social networks, and relationships/interactions networks. Detecting sub-structures in such networks helps us understand user behavior, predict links, and recommend products. In this paper, we detect dense sub-structures from a signed graph, called quasi antagonistic communities (QACs). An antagonistic community consists of two groups of users expressing positive relationships within each group but negative relationships across groups. Instead of requiring complete set of negative links across its groups, a QAC allows a small number of inter-group negative links to be missing. We propose an algorithm, Mascot, to find all maximal quasi …

Mining Human Activity Using Dimensionality Reduction And Pattern Recognition, Ismail El Moudden, Mounir Ouzir, Badreddine Benyacoub, Souad El Bernoussi

Research and Infrastructure Service Enterprise (RISE) Faculty Publications

Human activity recognition (HAR) is an emerging research topic in pattern recognition, especially in computer vision. The main objective of human activity recognition is to automatically detect and analyze human activities from the information acquired from different sensors. Human activity prediction using big data remains a challengingly open problem. Several approaches have recently been developed in order to find practical ways to solve high dimensionality of data problems. The aim of this study is to attempt, using data mining techniques, to deal with HAR modeling involving a significant number of variables in order to identify relevant parameters from data and …

K-D Tree-Segmented Block Truncation Coding For Image Compression, Proceso L. Fernandez Jr, Ryan Rey M. Daga

Department of Information Systems & Computer Science Faculty Publications

Block truncation coding (BTC) is a class of image compression algorithms whose main technique is the partitioning of an image into pixel blocks that are then each encoded using a representative set of pixel values. It is commonly used because of its simplicity and low computational complexity. The Quadtree-segmented BTC (QTS-BTC), which utilizes a dynamic hierarchical segmentation technique, is among the most efficient in the BTC class. In this study, we propose a new BTC variant that introduces two ideas: (1) the use of a k-d tree for segmentation and (2) the use of a Mean Squared Error (MSE) threshold …

Identifying Parameters For Robust Network Growth Using Attachment Kernels: A Case Study On Directed And Undirected Networks, Ahmed F. Abdelzaher

Theses and Dissertations

Network growing mechanisms are used to construct random networks that have structural behaviors similar to existing networks such as genetic networks, in efforts of understanding the evolution of complex topologies. Popular mechanisms, such as preferential attachment, are capable of preserving network features such as the degree distribution. However, little is known about such randomly grown structures regarding robustness to disturbances (e.g., edge deletions). Moreover, preferential attachment does not target optimizing the network's functionality, such as information flow. Here, we consider a network to be optimal if it's natural functionality is relatively high in addition to possessing some degree of robustness …

Evaluating And Improving The Efficiency Of Software And Algorithms For Sequence Data Analysis, Hugh L. Eaves

Theses and Dissertations

With the ever-growing size of sequence data sets, data processing and analysis are an increasingly large portion of the time and money spent on nucleic acid sequencing projects. Correspondingly, the performance of the software and algorithms used to perform that analysis has a direct effect on the time and expense involved. Although the analytical methods are widely varied, certain types of software and algorithms are applicable to a number of areas. Targeting improvements to these common elements has the potential for wide reaching rewards. This dissertation research consisted of several projects to characterize and improve upon the efficiency of several …

Using Genetic Algorithms To Evolve Artificial Neural Networks, William T. Kearney

Honors Theses

This paper demonstrates that neuroevolution is an effective method to determine an optimal neural network topology. I provide an overview of the NeuroEvolution of Augmenting Topologies (NEAT) algorithm, and describe how unique characteristics of this algorithm solve various problem inherent to neuroevolution (namely the competing conventions problem and the challenges associated with protecting topological innovation). Parallelization is shown to greatly speed up efficiency, further reinforcing neuroevolution as a potential alternative to traditional backpropagation. I also demonstrate that appropriate parameter selection is critical in order to efficiently converge to an optimal topology. Lastly, I produce an example solution to a medical …

On The Limits And Practice Of Automatically Designing Self-Stabilization, Alex Klinkhamer

Dissertations, Master's Theses and Master's Reports

A protocol is said to be self-stabilizing when the distributed system executing it is guaranteed to recover from any fault that does not cause permanent damage. Designing such protocols is hard since they must recover from all possible states, therefore we investigate how feasible it is to synthesize them automatically. We show that synthesizing stabilization on a fixed topology is NP-complete in the number of system states. When a solution is found, we further show that verifying its correctness on a general topology (with any number of processes) is undecidable, even for very simple unidirectional rings. Despite these negative results, …

Press: Personalized Event Scheduling Recommender System (Demonstration), Hoong Chuin Lau, Aldy Gunawan, Pradeep Varakantham, Wenjie Wang

Research Collection School Of Computing and Information Systems

This paper presents a personalized event scheduling recom-mender system, PRESS, for a large conference setting with multiple parallel tracks. PRESS is a mobile application that gathers personalized information from a user and recommends talks/demos to be attend. The input from a user include a list of keyword preferences and (optionally) preferred talks. We use the MALLET topic model package to analyze the set of conference papers and classify them based on automatically identified topics. We propose an algorithm to generate a list of recommended papers based on the user keywords and the MALLET topics. An optimization model is then applied …

Online Arima Algorithms For Time Series Prediction, Chenghao Liu, Hoi, Steven C. H., Peilin Zhao, Jianling Sun

Research Collection School Of Computing and Information Systems

Autoregressive integrated moving average (ARIMA) is one of the most popular linear models for time series forecasting due to its nice statistical properties and great flexibility. However, its parameters are estimated in a batch manner and its noise terms are often assumed to be strictly bounded, which restricts its applications and makes it inefficient for handling large-scale real data. In this paper, we propose online learning algorithms for estimating ARIMA models under relaxed assumptions on the noise terms, which is suitable to a wider range of applications and enjoys high computational efficiency. The idea of our ARIMA method is to …

An Efficient Method For Optimizing Segmentation Parameters, Jacob D' Avy, Wei-Wen Hsu, Chung-Hao Chen, Andreas F. Koschan, Mongi Abidi

Electrical & Computer Engineering Faculty Publications

Segmenting an image into meaningful regions is an important step in many computer vision applications such as facial recognition, target tracking and medical image analysis. Because image segmentation is an ill-posed problem, parameters are needed to constrain the solution to one that is suitable for a given application. For a user, setting parameter values is often unintuitive. We present a method for automating segmentation parameter selection using an efficient search method to optimize a segmentation objective function. Efficiency is improved by utilizing prior knowledge about the relationship between a segmentation parameter and the objective function terms. An adaptive sampling of …

Java Based Visualization And Animation For Teaching The Dijkstra Shortest Path Algorithm In Transportation Networks, Ivan Makohon, Duc T. Nguyen, Masha Sosonkina, Yuzhong Shen, Manwo Ng

Civil & Environmental Engineering Faculty Publications

Shortest path (SP) algorithms, such as the popular Dijkstra algorithm has been considered as the "basic building blocks" for many advanced transportation network models. Dijkstra algorithm will find the shortest time (ST) and the corresponding SP to travel from a source node to a destination node. Applications of SP algorithms include real-time GPS and the Frank-Wolfe network equilibrium.

For transportation engineering students, the Dijkstra algorithm is not easily understood. This paper discusses the design and development of a software that will help the students to fully understand the key components involved in the Dijkstra SP algorithm. The software presents an …

Performance Based Contracting For The Manufacturing Industry By Using Integrated Platform And Dynamic Pricing Model, Lindawati, Aldy Gunawan

Research Collection Lee Kong Chian School Of Business

Although Performance Based Contracting (PBC) concept is not totally new, the PBC adaptation in Industrial Machinery and Components (IMC) manufacturing, which produces high-value and long life machineries, is rather slow and it is done with extra caution. Three main concerns for manufacturers to implement PBC are the investment cost, the maintenance cost and possible revenue loss. To handle these concerns and accelerate the PBC implementation, we propose an integrated platform that consists of three components: dynamic pricing, sensor data feeding and machinery monitoring. We model the dynamic pricing as an optimization problem and propose Genetic Algorithm to solve the problem. …

An Improved Smote Algorithm Based On Genetic Algorithm For Imbalanced Data Collection, Qiong Gu, Xian-Ming Wang, Zhao Wu, Bing Ning, Chun-Sheng Xin

Electrical & Computer Engineering Faculty Publications

Classification of imbalanced data has been recognized as a crucial problem in machine learning and data mining. In an imbalanced dataset, minority class instances are likely to be misclassified. When the synthetic minority over-sampling technique (SMOTE) is applied in imbalanced dataset classification, the same sampling rate is set for all samples of the minority class in the process of synthesizing new samples, this scenario involves blindness. To overcome this problem, an improved SMOTE algorithm based on genetic algorithm (GA), namely, GASMOTE was proposed. First, GASMOTE set different sampling rates for different minority class samples. A combination of the sampling rates …

Simulation Of Nuclear Fusion Using A One Dimensional Particle In Cell Method, Steven T. Margell

Cal Poly Humboldt theses and projects

In this thesis several novel techniques are developed to simulate fusion events in an isotropic, electrostatic three-dimensional Deuterium-Tritium plasma. These techniques allow us to accurately predict three-dimensional collision events with a one-dimensional model while simultaneously reducing compute time via a nearest neighbor algorithm. Furthermore, a fusion model based on first principles is developed that yields an average fusion reactivity which correlates well with empirical results.

Battle Bot Ai – Patriot Bot, James Johnston

Computer Engineering

An entry in the the 'Battle Block AI' competition hosted by 'The AI Games'.

Positive Influence Dominating Set Generation In Social Networks, Akshaye Dhawan, Matthew Rink

Mathematics, Computer Science & Statistics Faculty Publications

Current algorithms in the Positive Influence Dominating Set (PIDS) problem domain are focused on a specific type of PIDS, the Total Positive Influence Dominating Set (TPIDS). We have developed an algorithm specifically targeted towards the non-total type of PIDS. In addition to our new algorithm, we adapted two existing TPIDS algorithms to generate PIDS. We ran simulations for all three algorithms, and our new algorithm consistently generates smaller PIDS than both existing algorithms, with our algorithm generating PIDS approximately 5% smaller than the better of the two existing algorithms.

Randomized Algorithms For Approximating A Connected Dominating Set In Wireless Sensor Networks, Akshaye Dhawan, Michelle Tanco, Aaron Yeiser

Mathematics, Computer Science & Statistics Faculty Publications

A Connected Dominating Set (CDS) of a graph representing a Wireless Sensor Network can be used as a virtual backbone for routing through the network. Since the sensors in the network are constrained by limited battery life, we desire a minimal CDS for the network, a known NP-hard problem. In this paper we present three randomized algorithms for constructing a CDS. We evaluate our algorithms using simulations and compare them to the two-hop K2 algorithm and two other greedy algorithms from the literature. After pruning, the randomized algorithms construct a CDS that are generally equivalent in size to those constructed …

Co-Rotational Finite Element Solid Simulation With Collisions, Patrick Riordan

Computer Science and Software Engineering

This paper is a tutorial on how to implement a deformable solid simulation with collisions based off of Matthias Mueller's Real Time Physics Course Notes. It covers the topics continuum mechanics, finite element analysis, implicit Euler integration, and handling collision.

An Immersive Telepresence System Using Rgb-D Sensors And Head-Mounted Display, Xinzhong Lu, Ju Shen, Saverio Perugini, Jianjun Yang

Computer Science Faculty Publications

We present a tele-immersive system that enables people to interact with each other in a virtual world using body gestures in addition to verbal communication. Beyond the obvious applications, including general online conversations and gaming, we hypothesize that our proposed system would be particularly beneficial to education by offering rich visual contents and interactivity. One distinct feature is the integration of egocentric pose recognition that allows participants to use their gestures to demonstrate and manipulate virtual objects simultaneously. This functionality enables the instructor to effectively and efficiently explain and illustrate complex concepts or sophisticated problems in an intuitive manner. The …

Differentially Private Subspace Clustering, Yining Wang, Yu-Xiang Wang, Aarti Singh

Research Collection School Of Computing and Information Systems

Subspace clustering is an unsupervised learning problem that aims at grouping data points into multiple “clusters” so that data points in a single cluster lie approximately on a low-dimensional linear subspace. It is originally motivated by 3D motion segmentation in computer vision, but has recently been generically applied to a wide range of statistical machine learning problems, which often involves sensitive datasets about human subjects. This raises a dire concern for data privacy. In this work, we build on the framework of differential privacy and present two provably private subspace clustering algorithms. We demonstrate via both theory and experiments that …

Multiple Instance Fuzzy Inference., Amine Ben Khalifa

Electronic Theses and Dissertations

A novel fuzzy learning framework that employs fuzzy inference to solve the problem of multiple instance learning (MIL) is presented. The framework introduces a new class of fuzzy inference systems called Multiple Instance Fuzzy Inference Systems (MI-FIS). Fuzzy inference is a powerful modeling framework that can handle computing with knowledge uncertainty and measurement imprecision effectively. Fuzzy Inference performs a non-linear mapping from an input space to an output space by deriving conclusions from a set of fuzzy if-then rules and known facts. Rules can be identified from expert knowledge, or learned from data. In multiple instance problems, the training data …

Extending The Teknomo-Fernandez Background Image Generation Algorithm On The Hsv Colour Space, Patricia Angela R. Abu, Proceso L. Fernandez Jr

Department of Information Systems & Computer Science Faculty Publications

Background subtraction, a procedure required in many video analysis applications such as object tracking , is dependent on the model background image. One efficient algorithm for background image generation is the Teknomo-Fernandez (TF) Algorithm, which uses modal values and a tournament-like strategy to produce a good background image very quickly. A previous study showed that the TF algorithm can be extended from the original 3 frames per tournament (T F 3) to T F 5 and T F 7, resulting in increased accuracies at a cost of increased processing times. In this study, we explore extending the T F 3, …

Dictionary Pair Learning On Grassmann Manifolds For Image Denoising, Xianhua Zeng, Wei Bian, Wei Liu, Jialie Shen, Dacheng Tao

Research Collection School Of Computing and Information Systems

Image denoising is a fundamental problem in computer vision and image processing that holds considerable practical importance for real-world applications. The traditional patch-based and sparse coding-driven image denoising methods convert 2D image patches into 1D vectors for further processing. Thus, these methods inevitably break down the inherent 2D geometric structure of natural images. To overcome this limitation pertaining to the previous image denoising methods, we propose a 2D image denoising model, namely, the dictionary pair learning (DPL) model, and we design a corresponding algorithm called the DPL on the Grassmann-manifold (DPLG) algorithm. The DPLG algorithm first learns an initial dictionary …

Prediction: The Quintessential Model Validation Test, Wayne Wakeland

Systems Science Friday Noon Seminar Series

It is essential to objectively test how well policy models predict real world behavior. The method used to support this assertion involves the review of three SD policy models emphasizing the degree to which the model was able to fit the historical outcome data and how well model-predicted outcomes matched real world outcomes as they unfolded. Findings indicate that while historical model agreement is a favorable indication of model validity, the act of making predictions without knowing the actual data, and comparing these predictions to actual data, can reveal model weaknesses that might be overlooked when all of the available …

An Incremental Phylogenetic Tree Algorithm Based On Repeated Insertions Of Species, Peter Revesz, Zhiqiang Li

School of Computing: Conference and Workshop Papers

In this paper, we introduce a new phylogenetic tree algorithm that generates phylogenetic trees by repeatedly inserting species one-by-one. The incremental phylogenetic tree algorithm can work on proteins or DNA sequences. Computer experiments show that the new algorithm is better than the commonly used UPGMA and Neighbor Joining algorithms.

Modeling Flood Risk For An Urban Cbd Using Ahp And Gis, Proceso L. Fernandez Jr, Generino P. Siddayao, Sony E. Valdez

Department of Information Systems & Computer Science Faculty Publications

The Central Business District (CBD) of a city is the activity center of the city, typically locating the main commercial and cultural establishments, as well as acting as the center point of the city’s transportation network. Flood risk assessment for a CBD is crucial for proper city planning and maintenance. In this study, we model the flood risk for the CBD of Tuguegarao City, which is located in northern Philippines. To accomplish this, we identified important flood-related factors whose data are either easily available or may be collected through some automated process that we developed. We then surveyed experts to …

The Effectiveness Of Using A Modified “Beat Frequent Pick” Algorithm In The First International Roshambo Tournament, Proceso L. Fernandez Jr, Sony E. Valdez, Generino P. Siddayao

Department of Information Systems & Computer Science Faculty Publications

In this study, a bot is developed to compete in the first International RoShamBo Tournament test suite. The basic “Beat Frequent Pick (BFP)” algorithm was taken from the supplied test suite and was improved by adding a random choice tailored fit against the opponent's distribution of picks. A training program was also developed that finds the best performing bot variant by changing the bot's behavior in terms of the timing of the recomputation of the pick distribution. Simulation results demonstrate the significantly improved performance of the proposed variant over the original BFP. This indicates the potential of using the core …

Functional Requirements Identification Using Item-To-Item Collaborative Filtering, Proceso L. Fernandez Jr, Reynald Jay F. Hidalgo

Department of Information Systems & Computer Science Faculty Publications

One of the most difficult tasks in the development of software is the identification of the functional requirements. A well-defined functional requirement will eventually map the success of a software project. A support tool that can recommend candidate functional requirements for a software project being developed will help software engineers to deliver the right software to the clients.
The purpose of this study is to determine whether a collection of previously developed software applications can serve as basis for the development of a model to identify functional requirements of a project to be developed. Completed software project documentations of Master …