Physical Sciences and Mathematics Commons^™

On Image Segmentation Using Neural Networks And Fuzzy Sets., Ashish Ghosh Dr.

Doctoral Theses

During the last five decades or even more a large number of researchers are trying to design intelligent systems to perform tasks at which human beings are more efficient at present. One of the most important behavioral tasks in which human beings show their expertise is image analysis or recognition; where a large amount of pictorial data is processed in a very small amount of time (called real time). Widespread attempts have been made to develop intelligent systems (under different names, like pattern recognition system, image under- standing system, computer vision system etc.) for pictorial pattern analysis and recognition. The …

Genetic Algorithms For Stochastic Flow Shop No Wait Scheduling, Harpal Maini, Ubirajara R. Ferreira

Electrical Engineering and Computer Science - Technical Reports

ln this paper we present Genetic Algorithms - evolutionary algorithms based on an analogy with natural selection and survival of the fittest - applied to an NP Complete combinatorial optimization problem: minimizing the makespan of a Stochastic Flow Shop No Wait (FSNW) schedule. This is an important optimization criteria in real-world situations and the problem itself is of practical significance. We restrict our applications to the three machine flow shop no wait problem which is known to be NP complete. The stochastic hypothesis is that the processing times of jobs are described by normally distributed random variables. We discuss how …

Design And Implementation Of Two Text Recognition Algorithms, Madhumathi Yendamuri

Theses

This report presents two algorithms for text recognition. One is a neural-based orthogonal vector with pseudo-inverse approach for pattern recognition. A method to generate N orthogonal vectors for an N-neuron network is also presented. This approach converges the input to the corresponding orthogonal vector representing the prototype vector. This approach can restore an image to the original image and thus has error recovery capacility. Also, the concept of sub-networking is applied to this approach to enhance the memory capacity of the neural network. This concept drastically increases the memory capacity of the network and also causes a reduction of the …

Multiple-Length Division Revisited: A Tour Of The Minefield, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

Long division of natural numbers plays a crucial role in Cobol arithmetic, cryptography, and primality testing. Only a handful of textbooks discuss the theory and practice of long division, and none of them do it satisfactorily. This tutorial attempts to fill this surprising gap in the literature on computer algorithms. We illustrate the subtleties of long division by examples, define the problem concisely, summarize the theory, and develop a complete Pascal algorithm using a consistent terminology.

Numerical Solution Of Laplace's Equation, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial discusses Laplace's equation for steady state heat flow in a two-dimensional region with fixed temperatures on the boundaries. The equilibrium temperatures are computed for a square grid using successive overrelaxation with parity ordering of the grid elements. The numerical method is illustrated by a Pascal algorithm. We assume that the reader is familiar with elementary calculus.

Parallel Cellular Automata: A Model Program For Computational Science, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

We develop a model program for parallel execution of cellular automata on a multicomputer. The model program is then adapted for simulation of forest fires and numerical solution of Laplace's equation for stationary heat flow. The performance of the parallel program is analyzed and measured on a Computing Surface configured as a matrix of transputers with distributed memory.

Minimum Separation For Single-Layer Channel Routing, Ronald I. Greenberg, F. Miller Maley

Computer Science: Faculty Publications and Other Works

We present a linear-time algorithm for determining the minimum height of a single-layer routing channel. The algorithm handles single-sided connections and multiterminal nets. It yields a simple routability test for single-layer switchboxes, correcting an error in the literature.

Formal Generation Of Executable Assertions For Application-Oriented Fault Tolerance, Hanan Lutfiyya, Martina Schollmeyer, Bruce M. Mcmillin

Computer Science Technical Reports

Executable assertions embedded into a distributed computing system can provide run-time assurance by ensuring that the program state, in the actual run-time environment, is consistent with the logical stage specified in the assertions; if not, then an error has occurred and a reliable communication of this diagnostic information is provided to the system such that reconfiguration and recovery can take place. Application- oriented fault tolerance is a method that provides fault detection using executable assertions based on the natural constraints of the application.

This paper focuses on giving application-oriented fault tolerance a theoretical foundation by providing a mathematical model for …

Designing Efficient Maximum-Likelihood Soft-Decision Decoding Algorithms For Linear Block Codes Using Algorithm A*, Yunghsiang S. Han, Carlos R.P. Hartmann

Electrical Engineering and Computer Science - Technical Reports

In this report we present a class of efficient maximum-likelihood soft-decision decoding algorithms for linear block codes. The approach used here is to convert the decoding problem into a search problem through a graph which is a trellis for an equivalent code of the transmitted code. Algorithm A*, which uses a priority-first search strategy, is employed to search through this graph. This search is guided by an evaluation function f defined to take advantage of the information provided by the received vector and the inherent properties of the transmitted code. This function f is used to drastically reduce the search …

Primality Testing, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial describes the Miller-Rabin method for testing the primality of large integers. The method is illustrated by a Pascal algorithm. The performance of the algorithm was measured on a Computing Surface.

Simulated Annealing, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial describes simulated annealing, an optimization method based on the principles of statistical mechanics. Simulated annealing finds near-optimal solutions to optimization problems that cannot be solved exactly because they are NP-complete. The method is illustrated by a Pascal algorithm for the traveling salesperson problem. The performance of the algorithm was measured on a Computing Surface.

New Algorithms For Mid-Crack Codes In Image Processing, Wai-Tak Wong

Theses

The chain code is a widely-used description for a contour image. Recently, a mid-crack code algorithm has been proposed as another more precise method for image representation. New algorithms using this new mid-crack code for image representation, restoration, and skeletonization are developed. The efficiency and accuracy can be increased obviously.

Firstly, the conversion of a binary image with multiple regions into the mid-crack codes is presented. A fast on-line implementation can be achieved using tables look-up. The input binary image may contain several object regions and their mid-crack codes can be extracted at the same time in a single-pass row-by-row …

A Probabilistic Analysis Of A Locality Maintaining Load Balancing Algorithm, Kishan Mehrotra, Sanjay Ranka, Jhy-Chun Wang

Electrical Engineering and Computer Science - Technical Reports

This paper presents a simple load balancing algorithm and its probabilistic analysis. Unlike most of the previous load balancing algorithms, this algorithm maintains locality. We show that the cost of this load balancing algorithm is small for practical situations and discuss some interesting applications for data remapping.

Some Aspects Of Multi Source Satellite Image Processing., L. Lalitha Dr.

Doctoral Theses

The observation of a target by a device plaoed at some distance from it is cal.led remote sensing as ngainst in situ sensing where the sensor is kept in contact with the target. Usually physical emanations such as the electr omagnetic radiation from the target s observed by the sensing device. Sensors mounted on aircraft or satallite platforms measure the amount of energy reflected from or emitted by the earth's surface. Sensors scan the ground below a nd to either side of the satellite platform and as the platform noves forward, an image of the earths surface is formed.A satellite …

Scheduling Regular And Irregular Communication Patterns On The Cm-5, Ravi Ponnusamy, Rajeev Thakur, Alok Choudhary, Geoffrey C. Fox

Northeast Parallel Architecture Center

In this paper, we study the communication characteristics of the CM-5 and the performance effects of scheduling regular and irregular communication patterns on the CM-5. We consider the scheduling of regular communication patterns such as complete exchange and broadcast. We have implemented four algorithms for complete exchange and studied their performances on a 2D FFT algorithm. We have also implemented four algorithms for scheduling irregular communication patterns and studied their performance on the communication patterns of several synthetic as well as real problems such as the conjugate gradient solver and the Euler solver.

The Fast Fourier Transform, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial discusses the fast Fourier transform, which has numerous applications in signal and image processing. The FFT computes the frequency components of a signal that has been sampled at n points in O( n log n) time. We explain the FFT and illustrate it by examples and Pascal algorithms. We assume that you are familiar with elementary calculus.

On Some Problems In Analysis Of Covariance Structure., Sadhan Samar Maiti Dr.

Doctoral Theses

In recent years, the teahniques of struotural analynie of covarianoe and correlation matrioes have frequently be en employed espeed ally in the s ooial and behavioural soieno es for analysing multivariate data. Analysis of covarlance structures (ACOVS) lea; generie tem describing a variety of statistioal procedures for testing and measuring the goodnese-of-fit of certain types of struotures postulated a priori for the cova- riance matrix by plaoing al temative restriotione on the para- neter natrioes of the general model" [Mukherjee, 1976, p. 132].The aoronyn AOOVS' standa for; analyeis of covarianoe atructurea; and waa firat proposed by Book (1960) as a …

Indifference Graphs And The Single Row Routing Problem, Peter J. Looges

Computer Science Theses & Dissertations

This thesis investigates the subclass of interval graphs known as indifference graphs. New optimal algorithms for recognition, center, diameter, maximum matching, Hamiltonian path and domination in indifference graphs are presented. The recognition algorithm produces a linear order with properties which allow the solution of the other problems in linear time. Indifference graphs are further applied to the single row routing problem which results in both sequential,. and parallel routing algorithms.

On Image Information Measures And Object Extraction., Nikhil Ranjan Pal Dr.

Doctoral Theses

The field of image processing deals with the manipulation of data which are inherently two-dimensional in nature. techniques of image processing sten from two principal application The areas, namely, Improvement of pictorial information for human interpretation and processing of scene data for automatic machine perception. These areas together have experienced a vigorous growth in recent years because they have offered a number of important applications in solving scientific and engineering problems. In biological and medical sciences, we are interested in automatie analysis and interpretation of radiographs, cell images micrographs. In netallurgical, geological and and tissue environmental sciences, we are concerned …

Three--Dimensional Medical Imaging: Algorithms And Computer Systems, M. R. Stytz, G. Frieder, O. Frieder

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

This paper presents an introduction to the field of three-dimensional medical imaging It presents medical imaging terms and concepts, summarizes the basic operations performed in three-dimensional medical imaging, and describes sample algorithms for accomplishing these operations. The paper contains a synopsis of the architectures and algorithms used in eight machines to render three-dimensional medical images, with particular emphasis paid to their distinctive contributions. It compares the performance of the machines along several dimensions, including image resolution, elapsed time to form an image, imaging algorithms used in the machine, and the degree of parallelism used in the architecture. The paper concludes …

Generalized Gradient Methods For Solving Locally Lipschitz Feasibility Problems, Dan Butnariu

Mathematics Technical Papers - Archive

In this paper we study the behavior of a class of iterative algorithms for solving feasibility problems, that is finite systems of inequalities [see pdf for notation], where each [see pdf for notation] is a locally Lipschitz functional on a Hilbert space X. We show that, under quite mild conditions, the algorithms studied in this note, if converge, then they approximate a solution of the feasibility given problem, provided that the feasibility problem is consistent. We prove several convergence criteria showing that, when the envelope of the functionals [see pdf for notation], is sufficiently "regular", then the algorithms converge. The …

A Software Design Tool For Predictable Performance In Real-Time, Data Flow Architectures, Brij Mohan V. Mandala

Electrical & Computer Engineering Theses & Dissertations

A software design tool which aids in the performance evaluation and selection of operating points for an algorithm implemented in ATAMM defined data flow architectures is presented in this thesis. ATAMM (Algorithm To Architecture Mapping Model) is a new graph theoretic model developed by researchers at Old Dominion University and the NASA-Langley Research Center. ATAMM is capable of modeling the execution of large-grained algorithms on distributed data flow architectures. A software tool is required for predicting the performance, determining the resource requirements and for selecting suitable operating points for an ATAMM based system. The ATAMM Design Tool presented in this …

Some Contributions To Generalized Inverse And The Linear Complementarity Problem., N. Eagambaram Dr.

Doctoral Theses

A generalized inverse (g-inverse) of a matrix A is a solution x to the matrix equationA XA = A(1.1.1)A g-inverse of A can be defined alternatively as a matrix x such that x = Xb is a solution to the linear equation Ax -b for any b that makes - b consistent. There is a vast literature on g-inverse. For a number of results on g-inverses and their applications one may refer to the well known books in the literature by Rao and Mitra (1971); and by Ben Israel and Greville (1974).Another inverse that lies hidden in the definition of …

Towards A Bound For The Compression Of The Lzw Algorithm, Anoop Kumar Srivastava, Shinu Gupta

Theses

The LZW algorithm is a well known efficient adaptive compression algorithm. It is based on constructing a dictionary containing character strings from the text. A number of researchers have attempted to add variations to the original algorithm to achieve higher compression values. In this thesis we attempt to find a bound for the LZW approach. That is, we build a dictionary which gives maximum compression and satisfies prefix property of LZW algorithm.

In order to build such an optimum dictionary, the dynamic programming technique is applied. The final dictionary selected consists of entries which give maximum overall compression and also …

Performance Modeling And Enhancement For The Atamm Data Flow Architecture, Sukhamoy Som

Electrical & Computer Engineering Theses & Dissertations

Algorithm To Architecture Mapping Model (ATAMM) is a new marked graph model from which the rules for data and control flow in a homogeneous, multicomputer, data flow architecture may be defined. This research is concerned with performance modeling and performance enhancement for periodic execution of large-grain, decision-free algorithms in such an ATAMM defined architecture. Performance measures and bounds are established. Algorithm transformation techniques are identified for performance enhancement and reduction of computing element requirements. Operating strategies are developed for optimum time performance and for sub-optimum time performance under limited availability of computing elements. An ATAMM simulator is used to test …

On Consisten Estimation Of Classes In R2 In The Context Of Cluster Analysis., C. A. Murthy Dr.

Doctoral Theses

Brief reviow of oluater analysis. The literature on oluater analy ste is baaically orianted touerda the development of algori thme 1,2,3, 4, 5]. Andaxberg [1] gives the verloue stepo in aluster analy al a starting from the chai ce of data pointa to interpreting the results. Harti gan 5] desoribes veari oun cluatering algo- ri thms in hin book. He also states the ueos of tho ae methoda in vari oue fielde. Jardines end Sibaon [6] dovelopa meaoures of di ssimilarity and regerde a alustor mothod as a funotion from di andmilori tymatrlces to trees. Clustering tochniquos can ba broadly …

A Color-Exchange Algorithm For Exact Graph Coloring, Thomas J. Sager, Shi-Jen Lin

Computer Science Technical Reports

DEXCH, a color-exchange exact graph coloring algorithm is presented. On many classes of graphs, DEXCH can, in the mean, find the chromatic number of a graph considerably faster than the DSATUR algorithm. The improvement over DSATUR stems from the ability to reorganize the subset of colored vertices and to detect in certain instances the existence of a complete subgraph of cardinality equal to the number of colors used in the best coloring found so far. The mean improvement over DSATUR is greatest on high edge-density graphs attaining the value of 42% on random graphs of edge-density 0.7 on 64 vertices.

Weak Bipolarizable Graphs, Stephan Olariu

Computer Science Faculty Publications

We characterize a new class of perfectly orderable graphs and give a polynomial-time recognition algorithm, together with linear-time optimization algorithms for this class of graphs.

Implementing Ray Tracing Algorithm In Parallel Environment, Tjah Jadi

Dissertations and Theses

Ray tracing is a very popular rendering algorithm in the field of computer graphics because it can generate highly-realistic images from three-dimensional models. Unfortunately, the computational cost is very expensive. To speed up the rendering process we present both static and dynamic scheduling (balancing) strategies for a multiprocessor system. Hence, the load balancing among the processors is the most important problem in parallel processing. The implementation of the algorithm is based on a modified octree structure.

On A Class Of Stochastic Approximation -Type Parameter-Learning Algorithms For Pattern Recognition., Amita Pal Dr.

Doctoral Theses

The first tank can involve one or more subtasks. For instance, it may require the design of a classifier on the basis of whatever prior knowledge there is of the feature space, or given the design, to estimate efficiently the parameters of the classifier. The latter might involve the estimation of the density function itself if very little is known about the class-conditional fenture distribution, or it may necessitate the entimation of the parameters of the fenture distribution, if one can assume it to have some known form. It may also involve estimating the boundaries of the classes, if even …