Theory and Algorithms Commons^™

A Wavelet Based Complementary Approach For Image Enhancement, Ismail Kosum

Electrical & Computer Engineering Theses & Dissertations

Detail in an image means more meaningful information that is very important in many computer vision and pattern recognition applications. The object region visibility in an image plays an important role in obtaining accurate and desired information from the original image. In particular, image processing techniques developed for region segmentation and object classification have better results depending on the visibility in images. There are several enhancement techniques available which are capable of obtaining clear images with balanced lighting and contrast. In this thesis, a completely image dependent approach to enhance the luminance of images under extreme lighting conditions and a …

Performance Analysis Of Ieee 802.11b Devices In The Presence Of Interference Aware Scheduling-Adaptive Frequency Hopping Enabled Bluetooth Devices, Deepthi Gopalpet

Electrical & Computer Engineering Theses & Dissertations

Wireless Local Area networks (WLAN) and Wireless Personal Area Networks (WPAN) provide complimentary services using the same unlicensed radio frequency band of operation. The 802.11b WLAN operates in the 2.4 GHz band and uses a Direct Sequence Spread Spectrum technique. It is designed to cover large areas ranging up to 100 meters in diameter, which may connect hundreds of computers. Bluetooth (BT) WPAN also operates in the same frequency band as the IEEE 802.lib and it uses a Frequency Hopping Spread Spectrum technique. BT is primarily used for communications between notebooks, palm units and other personal computing devices within relatively …

Long-Range Target Classification In A Cluttered Environment Using Multi-Sensor Image Sequences, Cenk Yaman

Electrical & Computer Engineering Theses & Dissertations

Accurate identification of unknown contacts is crucial in military intelligence. Automated systems which quickly and accurately determine the identity of a contact could be a benefit in backing up electronic signal identification methods such as Identification Friend and Foe (IFF) systems. Radio Detection and Ranging (RADAR) images are often undesirable in military applications since they reveal the location of the imaging system. So we explore the use of visible and infrared images of which are generally more consistent than RADAR images and for which it is easy to compensate for environmental effects. Recent advances in visible and IR imaging technology …

Use Of Tabu Search In A Solver To Map Complex Networks Onto Emulab Testbeds, Jason E. Macdonald

Theses and Dissertations

The University of Utah's solver for the testbed mapping problem uses a simulated annealing metaheuristic algorithm to map a researcher's experimental network topology onto available testbed resources. This research uses tabu search to find near-optimal physical topology solutions to user experiments consisting of scale-free complex networks. While simulated annealing arrives at solutions almost exclusively by chance, tabu search incorporates the use of memory and other techniques to guide the search towards good solutions. Both search algorithms are compared to determine whether tabu search can produce equal or higher quality solutions than simulated annealing in a shorter amount of time. It …

Percentage-Based Hybrid Pattern Training With Neural Network Specific Cross Over, Sheng-Uei Guan, Kiruthika Ramanathan

Research Collection School Of Computing and Information Systems

In this paper, a new weight-setting method is proposed to improve the training time and generalization accuracy of feed-forward neural networks. This method introduces a percentage-based hybrid pattern training (PHP) scheme and aims to provide a solution to the problem dependency of other Genetic Algorithm (GA)-based Neural Network weight-setting methods. A neural network is trained using a neural network specific GA until a certain percentage of the training patterns is learned. The weights thus obtained are used as the initial weights for backpropagation (BP) training, which is then applied to complete the network training. Further improvement to the method was …

Quality Of Service Routing Strategy Using Supervised Genetic Algorithm, Zhaoxia Wang, Yugeng Sun, Zhiyong Wang, Huayu Shen

Research Collection School Of Computing and Information Systems

A supervised genetic algorithm (SGA) is proposed to solve the quality of service (QoS) routing problems in computer networks. The supervised rules of intelligent concept are introduced into genetic algorithms (GAs) to solve the constraint optimization problem. One of the main characteristics of SGA is its searching space can be limited in feasible regions rather than infeasible regions. The superiority of SGA to other GAs lies in that some supervised search rules in which the information comes from the problems are incorporated into SGA. The simulation results show that SGA improves the ability of searching an optimum solution and accelerates …

An Algorithm For Two-Dimensional Density Reconstruction In Proton Computed Tomography (Pct), Jihad Tafas

Theses Digitization Project

The purpose of this thesis is to develop an optimized and effective iterative reconstruction algorithm and hardware acceleration methods that work synonymously together through reconstruction in proton computed tomography, which accurately maps the electron density.

Parallelizing A Nondeterministic Optimization Algorithm, Sammy Raymond D'Souza

Theses Digitization Project

This research explores the idea that for certain optimization problems there is a way to parallelize the algorithm such that the parallel efficiency can exceed one hundred percent. Specifically, a parallel compiler, PC, is used to apply shortcutting techniquest to a metaheuristic Ant Colony Optimization (ACO), to solve the well-known Traveling Salesman Problem (TSP) on a cluster running Message Passing Interface (MPI). The results of both serial and parallel execution are compared using test datasets from the TSPLIB.

Modular Exponentiation Via The Explicit Chinese Remainder Theorem, Daniel J. Bernstein, Jonathan P. Sorenson

Scholarship and Professional Work - LAS

In this paper we consider the problem of computing xe mod m for large integers x, e, and m. This is the bottleneck in Rabin’s algorithm for testing primality, the Diffie-Hellman algorithm for exchanging cryptographic keys, and many other common algorithms.

Solving The Teacher Assignment-Course Scheduling Problem By A Hybrid Algorithm, Aldy Gunawan, Kien Ming Ng, Kim Leng Poh

Research Collection School Of Computing and Information Systems

This paper presents a hybrid algorithm for solving atimetabling problem, which is commonly encountered in manyuniversities. The problem combines both teacher assignment andcourse scheduling problems simultaneously, and is presented as amathematical programming model. However, this problem becomesintractable and it is unlikely that a proven optimal solution can beobtained by an integer programming approach, especially for largeproblem instances. A hybrid algorithm that combines an integerprogramming approach, a greedy heuristic and a modified simulatedannealing algorithm collaboratively is proposed to solve the problem.Several randomly generated data sets of sizes comparable to that ofan institution in Indonesia are solved using the proposed algorithm.Computational results …

Mining Frequent Patterns From Sequences: Theory, Algorithm, Implementation, And Performance, Markus Petteri Turkia

Theses and Dissertations

Mining frequent patterns from sequences is an important data mining problem which has direct applications in many areas. In this thesis, we make three contributions to the state-of-the-art of the sequential frequent pattern mining. First of all, we propose a fast pattern-growth mining algorithm using a novel sequence database representation called First-Occurrence Linked WAP-tree (FLWAP-tree). The pattern-growth mining algorithm using the Pre-Order Linked WAP-tree (PLWAP-tree) was reported in the literature to be faster than other algorithms. We show that our pattern-growth using our FLWAP-tree outperforms the PLWAP-tree mining significantly and consistently. Secondly, we extend the pattern-growth algorithm with partial enumeration …

A Study Of The Parallelisation Of Multiobjective Evolutionary Algorithms In A Cluster Environment, Sadeesha Gamhewa

Theses : Honours

The two main issues relating to the use of Multiobjective Evolutionary Algorithms (MOEAs) are the efficiency and effectiveness of the algorithms. As a result of the multiobjective and multi dimensional nature of MOEAs, the overall execution time that is taken to solve real world problems with MOEAs can be significant. Therefore, a few studies have recently been completed to address these performance issues by the use of parallelisation methods. The most widely known parallel Multiobjective Evolutionary Algorithm (pMOEA) models are the Master-slave, the Island, and the Diffusion models. The Master-slave and the Island models are generally implemented using message passing …

Dual Constraint Problem Optimization Using A Natural Approach: Genetic Algorithm And Simulated Annealing, James P. Sweeney

UNF Graduate Theses and Dissertations

Constraint optimization problems with multiple constraints and a large solution domain are NP hard and span almost all industries in a variety of applications. One such application is the optimization of resource scheduling in a "pay per use" grid environment. Charging for these resources based on demand is often referred to as Utility Computing, where resource providers lease computing power with varying costs based on processing speed. Consumers using this resource have time and cost constraints associated with each job they submit. Determining the optimal way to divide the job among the available resources with regard to the time and …

An Improvement Heuristic For The Timetabling Problem, Aldy Gunawan, Kien Ming Ng, Kim Leng Poh

Research Collection School Of Computing and Information Systems

This paper formulates a timetabling problem, which is often encountered in a university, as a mathematical programming model. The proposed model combines both teacher assignment and course scheduling problems simultaneously, which causes the entire model to become more complex. We propose an improvement heuristic algorithm to solve such a model. The proposed algorithm has been tested with several randomly generated datasets of sizes that are comparable to those occurring in a university in Indonesia. The computational results show that the improvement heuristic is not only able to obtain good solutions, but is also able to do so within reasonable computational …

All Minimal Prime Extensions Of Hereditary Classes Of Graphs, Vassilis Giakoumakis, Stephan Olariu

Computer Science Faculty Publications

The substitution composition of two disjoint graphs G₁ and G₂ is obtained by first removing a vertex x from G₂ and then making every vertex in G₁ adjacent to all neighbours of x in G₂. Let F be a family of graphs defined by a set Z* of forbidden configurations. Giakoumakis [V. Giakoumakis, On the closure of graphs under substitution, Discrete Mathematics 177 (1997) 83–97] proved that F∗, the closure under substitution of F, can be characterized by a set Z∗ of forbidden configurations — the minimal prime extensions of Z. He also …

Validating Pareto Optimal Operation Parameters Of Polyp Detection Algorithms For Ct Colonography, Jiang Li, Adam Huang, Nicholas Petrick, Jianhua Yao, Ronald M. Summers, Maryellen L. Giger (Ed.), Nico Karssemeijer (Ed.)

Electrical & Computer Engineering Faculty Publications

We evaluated a Pareto front-based multi-objective evolutionary algorithm for optimizing our CT colonography (CTC) computer-aided detection (CAD) system. The system identifies colonic polyps based on curvature and volumetric based features, where a set of thresholds for these features was optimized by the evolutionary algorithm. We utilized a two-fold cross-validation (CV) method to test if the optimized thresholds can be generalized to new data sets. We performed the CV method on 133 patients; each patient had a prone and a supine scan. There were 103 colonoscopically confirmed polyps resulting in 188 positive detections in CTC reading from either the prone or …

Exploration Of Computational Methods For Classification Of Movement Intention During Human Voluntary Movement From Single Trial Eeg, Ou Bai, Peter Lin, Sherry Vorbach, Jiang Li, Steve Furlani, Mark Hallett

Electrical & Computer Engineering Faculty Publications

Objective: To explore effective combinations of computational methods for the prediction of movement intention preceding the production of self-paced right and left hand movements from single trial scalp electroencephalogram (EEG).

Methods: Twelve naïve subjects performed self-paced movements consisting of three key strokes with either hand. EEG was recorded from 128 channels. The exploration was performed offline on single trial EEG data. We proposed that a successful computational procedure for classification would consist of spatial filtering, temporal filtering, feature selection, and pattern classification. A systematic investigation was performed with combinations of spatial filtering using principal component analysis (PCA), independent component analysis …

Using Pareto Fronts To Evaluate Polyp Detection Algorithms For Ct Colonography, Adam Huang, Jiang Li, Ronald M. Summers, Nicholas Petrick, Amy K. Hara

Electrical & Computer Engineering Faculty Publications

We evaluate and improve an existing curvature-based region growing algorithm for colonic polyp detection for our CT colonography (CTC) computer-aided detection (CAD) system by using Pareto fronts. The performance of a polyp detection algorithm involves two conflicting objectives, minimizing both false negative (FN) and false positive (FP) detection rates. This problem does not produce a single optimal solution but a set of solutions known as a Pareto front. Any solution in a Pareto front can only outperform other solutions in one of the two competing objectives. Using evolutionary algorithms to find the Pareto fronts for multi-objective optimization problems has been …

Cosign: A Parallel Algorithm For Coordinated Traffic Signal Control, Shih-Fen Cheng, Marina A. Epelman, Robert L. Smith

Research Collection School Of Computing and Information Systems

The problem of finding optimal coordinated signal timing plans for a large number of traffic signals is a challenging problem because of the exponential growth in the number of joint timing plans that need to be explored as the network size grows. In this paper, the game-theoretic paradigm of fictitious play to iteratively search for a coordinated signal timing plan is employed, which improves a system-wide performance criterion for a traffic network. The algorithm is robustly scalable to realistic-size networks modeled with high-fidelity simulations. Results of a case study for the city of Troy, MI, where there are 75 signalized …

Modeling Heterogeneous User Churn And Local Resilience Of Unstructured P2p Networks, Zhongmei Yao, Derek Leonard, Dmitri Loguinov, Xiaoming Wang

Computer Science Faculty Publications

Previous analytical results on the resilience of unstructured P2P systems have not explicitly modeled heterogeneity of user churn (i.e., difference in online behavior) or the impact of in-degree on system resilience. To overcome these limitations, we introduce a generic model of heterogeneous user churn, derive the distribution of the various metrics observed in prior experimental studies (e.g., lifetime distribution of joining users, joint distribution of session time of alive peers, and residual lifetime of a randomly selected user), derive several closed-form results on the transient behavior of in-degree, and eventually obtain the joint in/out degree isolation probability as a simple …

Fast Tracking Of Near-Duplicate Keyframes In Broadcast Domain With Transitivity Propagation, Chong-Wah Ngo, Wan-Lei Zhao, Yu-Gang Jiang

Research Collection School Of Computing and Information Systems

The identification of near-duplicate keyframe (NDK) pairs is a useful task for a variety of applications such as news story threading and content-based video search. In this paper, we propose a novel approach for the discovery and tracking of NDK pairs and threads in the broadcast domain. The detection of NDKs in a large data set is a challenging task due to the fact that when the data set increases linearly, the computational cost increases in a quadratic speed, and so does the number of false alarms. This paper explores the symmetric and transitive nature of near-duplicate for the effective …

Audio Similarity Measure By Graph Modeling And Matching, Yuxin Peng, Chong-Wah Ngo, Cuihua Fang, Xiaoou Chen, Jianguo Xiao

Research Collection School Of Computing and Information Systems

This paper proposes a new approach for the similarity measure and ranking of audio clips by graph modeling and matching. Instead of using frame-based or salient-based features to measure the acoustical similarity of audio clips, segment-based similarity is proposed. The novelty of our approach lies in two aspects: segment-based representation, and the similarity measure and ranking based on four kinds of similarity factors. In segmentbased representation, segments not only capture the change property of audio clip, but also keep and present the change relation and temporal order of audio features. In the similarity measure and ranking, four kinds of similarity …

Mining Rdf Metadata For Generalized Association Rules, Tao Jiang, Ah-Hwee Tan

Research Collection School Of Computing and Information Systems

In this paper, we present a novel frequent generalized pattern mining algorithm, called GP-Close, for mining generalized associations from RDF metadata. To solve the over-generalization problem encountered by existing methods, GP-Close employs the notion of generalization closure for systematic over-generalization reduction. Empirical experiments conducted on real world RDF data sets show that our method can substantially reduce pattern redundancy and perform much better than the original generalized association rule mining algorithm Cumulate in term of time efficiency.

Wireless Indoor Positioning System With Enhanced Nearest Neighbors In Signal Space Algorithm, Quang Tran, Juki Wirawan Tantra, Ah-Hwee Tan, Ah-Hwee Tan, Kin-Choong Yow, Dongyu Qiu

Research Collection School Of Computing and Information Systems

With the rapid development and wide deployment of wireless Local Area Networks (WLANs), WLAN-based positioning system employing signal-strength-based technique has become an attractive solution for location estimation in indoor environment. In recent years, a number of such systems has been presented, and most of the systems use the common Nearest Neighbor in Signal Space (NNSS) algorithm. In this paper, we propose an enhancement to the NNSS algorithm. We analyze the enhancement to show its effectiveness. The performance of the enhanced NNSS algorithm is evaluated with different values of the parameters. Based on the performance evaluation and analysis, we recommend some …

New Tracking Filter Algorithm Using Input Parameter Estimation, Corey M. Broussard

Theses and Dissertations

A new method for the design of tracking filters for maneuvering targets, based on kinematic models and input signals estimation, is developed. The input signal's level, u is considered a continuous variable and consequently the input estimation problem is posed as a purely parameter estimation problem. Moreover, the application of the new tracking filter algorithm is not contingent on distinguishing maneuvering and non-maneuvering targets, and does not require the detection of maneuver onset. The filter will automatically detect the onset of a maneuver. Furthermore, an estimate of the target's acceleration is also obtained with reasonable precision. This opens the door …

Optimizing The Replication Of Multi-Quality Web Applications Using Aco And Wolf, Judson C. Dressler

Theses and Dissertations

This thesis presents the adaptation of Ant Colony Optimization to a new NP-hard problem involving the replication of multi-quality database-driven web applications (DAs) by a large application service provider (ASP). The ASP must assign DA replicas to its network of heterogeneous servers so that user demand is satisfied and replica update loads are minimized. The algorithm proposed, AntDA, for solving this problem is novel in several respects: ants traverse a bipartite graph in both directions as they construct solutions, pheromone is used for traversing from one side of the bipartite graph to the other and back again, heuristic edge values …

Learning The Unified Kernel Machines For Classification, Steven C. H. Hoi, Michael R. Lyu, Edward Y. Chang

Research Collection School Of Computing and Information Systems

Kernel machines have been shown as the state-of-the-art learning techniques for classification. In this paper, we propose a novel general framework of learning the Unified Kernel Machines (UKM) from both labeled and unlabeled data. Our proposed framework integrates supervised learning, semi-supervised kernel learning, and active learning in a unified solution. In the suggested framework, we particularly focus our attention on designing a new semi-supervised kernel learning method, i.e., Spectral Kernel Learning (SKL), which is built on the principles of kernel target alignment and unsupervised kernel design. Our algorithm is related to an equivalent quadratic programming problem that can be efficiently …

An Adaptive Algorithm To Identify Ambiguous Prostate Capsule Boundary Lines For Three-Dimensional Reconstruction And Quantitation, Rania Yousry Hussein

Electrical & Computer Engineering Theses & Dissertations

Currently there are few parameters that are used to compare the efficiency of different methods of cancerous prostate surgical removal. An accurate assessment of the percentage and depth of extra-capsular soft tissue removed with the prostate by the various surgical techniques can help surgeons determine the appropriateness of surgical approaches. Additionally, an objective assessment can allow a particular surgeon to compare individual performance against a standard. In order to facilitate 3D reconstruction and objective analysis and thus provide more accurate quantitation results when analyzing specimens, it is essential to automatically identify the capsule line that separates the prostate gland tissue …

An Operational Model For Mobile Sensor Cloud Management, Indrajeet Kalyankar

Electrical & Computer Engineering Theses & Dissertations

Mobile sensors provide a safe, cost effective method for gathering information in hazardous environments. When the hazardous environment is either unexplored, such as the surface of Mars, or unanticipated, such as the result of chemical contamination, it is desirable for a system to gather information with a minimal amount of outside control (localization, decision control, etc.) and prepositioned sensors. If one takes a look at the number of the sensors deployed on a scale, at the lower end is the sole, multipurpose sensor unit. The upper end deals with hordes of inexpensive, expendable sensors. In the middle, a cluster of …

Apparatus And Method For Using Adaptive Algorithms To Exploit Sparsity In Target Weight Vectors In An Adaptive Channel Equalizer, Richard K. Martin, Robert C. Williamson, William A. Sethares

AFIT Patents

An apparatus and method is disclosed for using adaptive algorithms to exploit sparsity in target weight vectors in an adaptive channel equalizer. An adaptive algorithm comprises a selected value of a prior and a selected value of a cost function. The present invention comprises algorithms adapted for calculating adaptive equalizer coefficients for sparse transmission channels. The present invention provides sparse algorithms in the form of a Sparse Least Mean Squares (LMS) algorithm and a Sparse Constant Modulus Algorithm (CMA) and a Sparse Decision Directed (DD) algorithm.