Theory and Algorithms Commons^™

A Fast And Simple Algorithm For Computing M-Shortest Paths In State Graph, M. Sherwood, Laxmi P. Gewali, Henry Selvaraj, Venkatesan Muthukumar

Electrical & Computer Engineering Faculty Research

We consider the problem of computing m shortest paths between a source node s and a target node t in a stage graph. Polynomial time algorithms known to solve this problem use complicated data structures. This paper proposes a very simple algorithm for computing all m shortest paths in a stage graph efficiently. The proposed algorithm does not use any complicated data structure and can be implemented in a straightforward way by using only array data structure. This problem appears as a sub-problem for planning risk reduced multiple k-legged trajectories for aerial vehicles.

Unidirectional Cordic For Efficient Computation Of Trigonometric And Hyperbolic Functions, Satish Ravichandran

Electrical & Computer Engineering Theses & Dissertations

CORDIC (Coordinate Rotation Digital Computer) is an iterative algorithm to compute values of trigonometric, logarithmic and transcendental functions by performing vector rotations, which can be implemented with only shift and add operations in a digital system. CORDIC algorithms are extensively used in the areas of digital signal processing, digital image processing and artificial neural networks. A new technique, named unidirectional CORDIC, for efficient computation of trigonometric and hyperbolic functions is presented in this thesis. In the conventional CORDIC algorithm, the vector rotations are performed in both clockwise and counterclockwise directions, but in the unidirectional CORDIC the vectors are rotated only …

Yet Another Algorithm For Pitch Tracking (Yaapt), Kavita Kasi

Electrical & Computer Engineering Theses & Dissertations

This thesis presents a pitch detection algorithm that is extremely robust for both high quality and telephone speech. The kernel method for this algorithm is the Normalized Cross Correlation (NCCF) reported by David Talkin [16]. Major innovations include: processing of the original acoustic signal and a nonlinearly processed version of the signal to partially restore very weak F0 components; intelligent peak picking to select multiple F0 candidates and assign merit factors; and, incorporation of highly robust pitch contours obtained from smoothed versions of low frequency portions of spectrograms. Dynamic programming is used to find the ''best" pitch track among all …

Study Of Transport Properties Of Inas Using Monte Carlo Simulation, Satyanadh Gundimada

Electrical & Computer Engineering Theses & Dissertations

The present research is aimed at ascertaining the usefulness of InAs semiconductor material for single photon avalanche photo detectors operating in the Geiger mode at 2 μm wavelengths. InAs is considered as the material suitable for the purpose because of its less bandgap and lower effective mass of the electrons when compared to other semiconductor materials presently in use. Hence, theoretically transient transport properties of bulk InAs are superior and the velocity overshoot phenomena stronger. InAs is a relatively less explored material when compared to other materials like GaAs. The choice of the material is justified with thorough exploration of …

On The Area Of Hypercube Layouts, Ronald I. Greenberg, Lee Guan

Computer Science: Faculty Publications and Other Works

This paper precisely analyzes the wire density and required area in standard styles for the hypercube. It shows that the most natural, regular layout of a hypercube of N^2 nodes in the plane, in a NxN grid arrangement, uses floor(2N/3)+1 horizontal wiring tracks for each row of nodes. (In the process, we see that the number of tracks per row can be reduced by 1 with a less regular design, as can also be seen from an independent argument of Bezrukov et al.) This paper also gives a simple formula for the wire density at any cut position and a …

Translation And Rotation Invariant Multiscale Image Registration, Jennifer L. Manfra

Theses and Dissertations

The most recent research involved registering images in the presence of translations and rotations using one iteration of the redundant discrete wavelet transform. We extend this work by creating a new multiscale transform to register two images with translation or rotation differences, independent of scale differences between the images. Our two-dimensional multiscale transform uses an innovative combination of lowpass filtering and the continuous wavelet transform to mimic the two-dimensional redundant discrete wavelet transform. This allows us to obtain multiple subbands at various scales while maintaining the desirable properties of the redundant discrete wavelet transform. Whereas the discrete wavelet transform produces …

Real-Time Travel Time Estimation Using Macroscopic Traffic Flow Models, Pushkin Kachroo, Kaan Ozbay, Antoine G. Hobeika

Electrical & Computer Engineering Faculty Research

This paper presents the estimation of travel time on highways based on macroscopic modelling. The focus is on real-time values as compared to average or static values. The macroscopic models are used for distributed and time/space lumped settings and corresponding travel time estimation functions and algorithms are developed. The implications of these algorithms for the implementation of various incident management and traffic control strategies are also discussed.

An Objective Evaluation Of Four Sar Image Segmentation Algorithms, Jason B. Gregga

Theses and Dissertations

Because of the large number of SAR images the Air Force generates and the dwindling number of available human analysts, automated methods must be developed. A key step towards automated SAR image analysis is image segmentation. There are many segmentation algorithms, but they have not been tested on a common set of images, and there are no standard test methods. This thesis evaluates four SAR image segmentation algorithms by running them on a common set of data and objectively comparing them to each other and to human segmentors. This objective comparison uses a multi-metric a approach with a set of …

Video Compression Using Wavelets And Hierarchical Motion Estimation, Andrew Peter Byrne

Theses : Honours

This thesis investigates the benefits and the significant compression that can be obtained from data that has been decomposed using a wavelet transform. A video compression algorithm was developed that employs the wavelet transform and a hierarchical motion estimation algorithm which itself utilises benefits of the wavelet transform. Using MATLAB, a popular software tool for matrix based computation and analysis, several functions were developed which together formed the video compression algorithm. A variety of tests were conducted on a sample video sequence to ascertain the strengths and weaknesses of the techniques employed. The results, although not the same as the …

Isolated Ramp Metering Feedback Control Utilizing Mixed Sensitivity For Desired Mainline Density And The Ramp Queues, Pushkin Kachroo, Kaan Ozbay, Donald E. Grove

Electrical & Computer Engineering Faculty Research

This paper presents a feedback control design for isolated ramp metering control. This feedback control design, unlike the existing isolated feedback ramp controllers, also takes into account the ramp queue length. Using a nonlinear H∞ control design methodology, we formulate the problem in the desired setting to be able to utilize the results of the methodology.

Vhdl Design And Simulation For Embedded Zerotree Wavelet Quantisation, Hung Huynh

Theses : Honours

This thesis discusses a highly effective still image compression algorithm – The Embedded Zerotree Wavelets coding technique, as it is called. This technique is simple but achieves a remarkable result. The image is wavelet-transformed, symbolically coded and successive quantised, therefore the compression and transmission/storage saving can be achieved by utilising the structure of zerotree. The algorithm was first proposed by Jerome M. Shapiro in 1993, however to minimise the memory usage and speeding up the EZW processor, a Depth First Search method is used to transverse across the image rather than Breadth First Search method as initially discussed in Shapiro's …

Newton Parameter Update Algorithm For Recurrent Neural Networks Applied To Adaptive System Identification And Control, Donald Allen Gates

Electrical & Computer Engineering Theses & Dissertations

This paper shows that the combination of a second-order neural network parameter update algorithm and internal network feedback can be effectively used for adaptive, nonlinear, dynamical system identification and control. Adaptive neural identification and control algorithms are typically utilized for real-time applications where the rate of adaptation is often critical. A fast, adaptive network parameter update algorithm is presented.

Simulation results show that this algorithm is capable of quickly identifying and adapting to changes in system parameters, making it feasible to use for real-time control and fault accommodation applications.

Nonlinear Constrained Optimizer And Parallel Processing For Golden Block Line Search, Duc T. Nguyen, Wilson H. Tang, Yeou K. Tung, Hakizumwami B. Runesha

Civil & Environmental Engineering Faculty Publications

Generalized exponential penalty functions are constructed for the multiplier methods in solving nonlinear programming problems. The non-smooth extreme constraint Gext is replaced by a single smooth constraint Gs by using the generalized exponential function (base a>1). The well-known K.S. function is found to be a special case of our proposed formulation. Parallel processing for Golden block line search algorithm is then summarized, which can also be integrated into our formulation. Both small and large-scale nonlinear programming problems (up to 2000 variables and 2000 nonlinear constraints) have been solved to validate the proposed algorithms.

Automatic Target Cueing Of Hyperspectral Image Data, Terry A. Wilson

Theses and Dissertations

Modern imaging sensors produce vast amounts data, overwhelming human analysts. One such sensor is the Airborne Visible and Infrared Imaging Spectrometer (AVIRIS) hyperspectral sensor. The AVIRIS sensor simultaneously collects data in 224 spectral bands that range from 0.4µm to 2.5µm in approximately 10nm increments, producing 224 images, each representing a single spectral band. Autonomous systems are required that can fuse "important" spectral bands and then classify regions of interest if all of this data is to be exploited. This dissertation presents a comprehensive solution that consists of a new physiologically motivated fusion algorithm and a novel Bayes optimal self-architecting classifier …

Representations, Approximations, And Algorithms For Mathematical Speech Processing, Laura R. Suzuki

Theses and Dissertations

Representing speech signals such that specific characteristics of speech are included is essential in many Air Force and DoD signal processing applications. A mathematical construct called a frame is presented which captures the important time-varying characteristic of speech. Roughly speaking, frames generalize the idea of an orthogonal basis in a Hilbert space, Specific spaces applicable to speech are L₂(R) and the Hardy spaces H_p(D) for p> 1 where D is the unit disk in the complex plane. Results are given for representations in the Hardy spaces involving Carleson's inequalities (and its extensions), …

Building Lms Adaptive Filters With Register-Based Fpgas, Li Ding

Electrical & Computer Engineering Theses & Dissertations

In this thesis, an 8-bit least mean squares (LMS) adaptive digital filter with 16 coefficients is implemented on a single FPGA, using the MaxPlus+2 design environment. The system is constructed as a hierarchical structure, using four different levels of design hierarchy. Subdesigns at each level of the hierarchy project are complied, fitted and simulated to test and verify their functional correctness. The complete system is tested and verified by checking the MaxPlus+2 simulator results against fixed-point integer arithmetic simulations written in Matlab. The resulting adaptive filter is subsequently mapped to the Alters FLEX I OK20TC144-3 device, resulting in a 14,500 …

Breast Cancer Mass Detection Using Difference Of Gaussians And Pulse Coupled Neural Networks, Donald A. Cournoyer

Theses and Dissertations

CAD, serving as a second reader, has been shown to improve the success of radiologists at detecting breast cancer. This thesis will develop a new algorithm to identify masses in mammograms. The system developed for this thesis will be capable of assisting a radiologist in making decisions.

Applications Of Unsupervised Clustering Algorithms To Aircraft Identification Using High Range Resolution Radar, Dzung Tri Pham

Theses and Dissertations

Identification of aircraft from high range resolution (HRR) radar range profiles requires a database of information capturing the variability of the individual range profiles as a function of viewing aspect. This database can be a collection of individual signatures or a collection of average signatures distributed over the region of viewing aspect of interest. An efficient database is one which captures the intrinsic variability of the HRR signatures without either excessive redundancy typical of single-signature databases, or without the loss of information common when averaging arbitrary groups of signatures. The identification of 'natural' clustering of similar HRR signatures provides a …

Feedback Control Solutions To Network Level User-Equilibrium Real-Time Dynamic Traffic Assignment Problems, Pushkin Kachroo, Kaan Ozbay

Electrical & Computer Engineering Faculty Research

A new method for performing dynamic traffic assignment (DTA) is presented which is applicable in real time, since the solution is based on feedback control. This method employs the design of nonlinear H∞ feedback control systems which is robust to certain class of uncertainties in the system. The solution aims at achieving user equilibrium on alternate routes in a network setting.

Investigating The Use Of Kalman Filtering Approaches For Dynamic Origin-Destination Trip Table Estimation, Pushkin Kachroo, Kaan Ozbay, Arvind Narayanan

Electrical & Computer Engineering Faculty Research

This paper studies the applicability of Kalman filtering approaches for network wide traveler origin-destination estimation from link traffic volumes. The paper evaluates the modeling assumptions of the Kalman filters and examines the implications of such assumptions.

Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

We give algorithms to minimize density for VLSI channel routing problems with terminals that are movable subject to certain constraints. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, we improve previous results for running time and space by a factor of L/\lgn and L, respectively, where L is the channel length, and n is the number of terminals.

Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

We provide efficient parallel algorithms for the minimum separation, offset range, and optimal offset problems for single-layer channel routing. We consider all the variations of these problems that are known to have linear- time sequential solutions rather than limiting attention to the "river-routing" context, where single-sided connections are disallowed. For the minimum separation problem, we obtain O(lgN) time on a CREW PRAM or O(lgN / lglgN) time on a (common) CRCW PRAM, both with optimal work (processor- time product) of O(N), where N is the number of terminals. For the offset range problem, we obtain the same time and processor …

Resource/Dataflow Graph Operating System Development, Sriram J. Coimbatore

Electrical & Computer Engineering Theses & Dissertations

Implementation of a new dataflow schedule model is the objective of this thesis. The dataflow model algorithm called the resource/dataflow graph model is implemented on a peer-to-peer communication network comprising of six personal computers. This dataflow model is implemented making use of an earlier dataflow model called ATAMM (Algorithm to Architecture Mapping Model) developed by ODU and National Aeronautics and Space Administration (NASA). Development issues include modification of the RDFG testbed operating system and a scheme to transfer data buffers using the ethernet channel from one processor to another processor. This, in turn, equips each sub-module of an application with …

Monte Carlo Simulations Of Photoemission Characteristics From Gaas And Diamond, Abhishek Srivastava

Electrical & Computer Engineering Theses & Dissertations

Monte Carlo based numerical simulations were performed to study photoemission from GaAs and diamond. The central goal was to assess the potential for NEA photoemission from diamond, and to predict its characteristics. The GaAs material system was also included in the simulation study to provide: (i) calibration and validation of the numerical model developed by carefully matching the simulation results with available experimental data, and (ii) quantitative comparisons between the response characteristics of diamond and the better known GaAs system.

Predictions of the energy distribution, temporal response and angular distribution of emitted electrons were obtained. Effects of various parameters, such …

Single-Layer Channel Routing And Placement With Single-Sided Nets, Ronald I. Greenberg, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

This paper considers the optimal offset, feasible offset, and optimal placement problems for a more general form of single-layer VLSI channel routing than has usually been considered in the past. Most prior works require that every net has exactly one terminal on each side of the channel. As long as only one side of the channel contains multiple terminals of the same net, we provide linear-time solutions to all three problems. Such results are implausible if the placement of terminals is entirely unrestricted; in fact, the size of the output for the feasible offset problem may be Ω(n^2). The linear-time …

Neural Generalized Predictive Control For Real-Time Control, Donald I. Soloway

Electrical & Computer Engineering Theses & Dissertations

In this thesis a computationally efficient Generalized Predictive Control (GPC) algorithm is presented and implemented. The algorithm is more efficient than others because the number of iterations needed for convergence is significantly lower with Newton-Raphson. The main additional cost with Newton-Raphson algorithm is the calculation of the Hessian. This overhead is not a problem because of the reduced number of iterations, making the algorithm suitable for real-time control. For nonlinear control applications, a neural network is used as a dynamical system predictor leading to a Neural Generalized Predictive Control (NGPC) algorithm which is presented in detail in this thesis. An …

Visual Speech Recognition Using Multiple Deformable Lip Models, Devi Chandramohan

Electrical & Computer Engineering Theses & Dissertations

Motivated by the fact that human speech perception is a bimodal process (auditory and visual), several researchers have designed and implemented automatic speech recognition (ASR) systems consisting of both audio and visual subsystems, and shown improved performance relative to traditional purely auditory systems. Several visual speech reading approaches have used deformable templates to model the shape of a speaker's lips. Deformable templates are models of image objects, which can be deformed by adjusting a set of parameters to match the object in some optimal way, as defined by a cost function. Using a single deformable lip model has disadvantages such …

Variable Step Size Lms Adaptive Filters With Delayed Coefficient Updating, Guixian Xu

Electrical & Computer Engineering Theses & Dissertations

A new approach to delayed LMS adaptive filtering is presented, which uses a variable step size for coefficient updating to increase convergence speed and improve tracking characteristics. The new algorithm, called delayed variable step size LMS (DVLMS), is explained, analyzed, and simulated to experimentally determine performance characteristics. Three different strategies for adjusting the step size are examined, and their performance is compared. Also, simulation results are presented to show that the proposed DVLMS systems provide faster convergence and lower mis-adjustment than previously proposed DLMS systems.

Adaptive Integration Of Audio And Visual Information Using Discrete And Semi-Continuous Hidden Markov Models In Audiovisual Automatic Speech Recognition, Qin Su

Electrical & Computer Engineering Theses & Dissertations

An audiovisual semi-continuous hidden Markov model (HMM)-based Automatic Speech Recognition (ASR) system and an improved method of integrating audio and visual information in an audiovisual discrete HMM-based ASR system are investigated.

In the audiovisual discrete HMM, an adaptive integration formulation is employed, which incorporates the integration into the HMM at a pre-categorical stage. A visual weighting parameter is determined automatically, which allows the relative contribution of audio and visual information to be adjusted adaptively. Using an adaptive weight, the accuracy increased by 13% compared to the same model with no adaptive weight.

The semi-continuous HMM is a class of models …

Text Independent Speaker Verification Using Binary-Pair Partitioned Neural Networks, Claude A. Norton Iii

Electrical & Computer Engineering Theses & Dissertations

A method is presented for the application of binary-pair partitioned neural networks to the task of speaker verification. This technique is based on a previously developed neural network classifier for speaker identification.

The main focus of this research was the development and testing of the algorithms necessary to extend the binary-pair partitioning approach from speaker identification to speaker verification. The method is based on the development of a user profile which is obtained from discriminative data provided by the binary-pair partitioned neural networks.

Experimental results are provided which demonstrate the viability of this approach, using the TIMIT speech corpus for …