Physical Sciences and Mathematics Commons^™

Time- And Cost-Optimal Parallel Algorithms For The Dominance And Visibility Graphs, D. Bhagavathi, H. Gurla, S. Olariu, J. L. Schwing, J. Zhang

Computer Science Faculty Publications

The compaction step of integrated circuit design motivates associating several kinds of graphs with a collection of non-overlapping rectangles in the plane. These graphs are intended to capture various visibility relations amongst the rectangles in the collection. The contribution of this paper is to propose time- and cost-optimal algorithms to construct two such graphs, namely, the dominance graph (DG, for short) and the visibility graph (VG, for short). Specifically, we show that with a collection of n non-overlapping rectangles as input, both these structures can be constructed in θ (log n) time using n processors in the CREW model.

A Search Tool To Enhance The Selection And Utilisation Of Reusable Software Modules Within The Object-Oriented Paradigm, Robert H. Cross

Theses: Doctorates and Masters

The affinity for reuse within the object-oriented paradigm may enable high levels of productivity; however, gains will become realisable only if a systems developer has access to tools which aid in the selection of classes. A method for object-oriented analysis and design is detailed and its process is assisted by an object-oriented search tool based on reference and corporate library technology. The search tool contributes to the determination of suitable existing inheritable classes and an explanation of its construction and use is included. A practical demonstration of the method, using the search tool, is elaborated. The thesis demonstrates that text …

Packet Routing In Networks With Long Wires, Ronald I. Greenberg, Hyeong-Cheol Oh

Computer Science: Faculty Publications and Other Works

In this paper, we examine the packet routing problem for networks with wires of differing length. We consider this problem in a network independent context, in which routing time is expressed in terms of "congestion" and "dilation" measures for a set of packet paths. We give, for any constant ϵ > 0, a randomized on-line algorithm for routing any set of Npackets in O((C lg^ϵ(Nd) + D lg(Nd))/lg lg(Nd)) time, where C is the maximum congestion and D is the length of the longest path, both taking wire delays into …

On Texture Image Analysis Using Fractal Geometry Based Features., Nirupam Sarkar Dr.

Doctoral Theses

Visual textureTexture is a property to characterize a region of a scene. A set of natural texture images is shown in Fig. 1.1. A specific texture may be generated due to certain organization of several objects in a region, or due to the reflectance pattern caused by color variation or unevenness of an object surface. Since texture provides a lot of information of a region, texture analysis and synthesis are important components of digital image processing.It is difficult to provide a formal definition of texture although we perceive and recognize texture rather easily. According to Sklansky [152) "A region in …

Neuro-Fuzzy Models For Classification And Rule Generation., Sushmita Mitra Dr.

Doctoral Theses

Machine recognition [1, 2] of patterns can be viewed as a two-fold task, consisting of learning the invariant and common properties of a set of samples characterizing a class, and of deciding a new sample as a possible member of the class by noting that it has properties common to those of the set of samples. In other words, pattern recognition by computers can be described as a transformation from the measurenment space M to the feature space F and finally to the decision space D (1), i.e., M ⟶F⟶D.Here, the mapping 6 : F⟶D is the decision function and …

Connectionist Models For Certain Tasks Related To Object Recognition., Jayanta Basak Dr.

Doctoral Theses

Recognition of objects in an image, according to Suetens et al. [1), relers to the task of finding and labeling parts of a two-dimensional image of a scene that correspond to the real objects in the scene. Object recognition is necessary in a variety of domains like robot navigation, aerial imagery analysis, industrial inspection and so on. Normally, different strategies for object recognition (1-(5] involve establishing some model for each object, i.e., some general description of each object, and then labeling different parts of the scene according to the knowledge about the models.Object models can have two-dimensional (2D) or three-climensional …

On Detection And Use Of Reflectional Symmetry In Computer Vision., Dipti Prasad Mukherjee Dr.

Doctoral Theses

The problems of detection and use of reflectional symmetry in the images of planar shape contours are studied. Symmetry, in general, provides important shape representation cues, some of which we utilise here, to acquire viewpoint information and, towards model based shape matching. We concentrate on local reflectional symmetries of emoothly curved planar objecta, though the methoda are equally applicable to polygonal objects; even this could be extended to certain three-dimensional shapes and for other object relations such as rotational symmetry.Under the affine or perspective approximation to image projection, properties of geometrie invariance are used to find (reflectional) symmetric contour pairs. …

Tact Volume 4 Issue 1, Touro College Department Of Academic Computing

Yearbooks and Newsletters

"Touro Academic Computing Technologies: The Newsletter of Academic Computing at Touro College"

Some Contributions To Linear Complementarity Problem., G. S. R. Murthy Dr.

Doctoral Theses

This dissertation deals with a number of problems related to linear comple- mentarity problem (LCP). Given a real square matrix A of order n and a real n-vector q, the LCP is to find a nonnegative n-vector z such that Az + q 2 0 and zt(Az + 9) = 0. There is vast literature on LCP, evolved during the last four decades. LCP plays a crucial role in the study of mathematical program- ming from the view point of algorithms as well as applications. The inherent nature of the problem has led the researchers to introduce and study a …

Polygonal Approximation And Scale-Space Analysis Of Closed Digital Curves., Bimal Kumar Roy Dr.

Doctoral Theses

This thesis presents a series of algorithms for polygonal approximation of closed digital curves followed by scale-space analysis with its application to corner detection.Approximation of a closed curve by plece straight line segments is known as polygonal approximation. Any curve can be approximated by a polygon with any desired degree of accuracy.Polygonal approximation is useful in reducing the number of points required to represent a curve and to smooth data. Such representation facilitates extraction of numerical features for description and classification of curves. Basically there are two approaches to the problem. One is to subdivide the points into groups each …

Finding Connected Components On A Scan Line Array Processor, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

This paper provides a new approach to labeling the connected components of an n x n image on a scan line array processor (comprised of n processing elements). Variations of this approach yield an algorithm guaranteed to complete in o(n lg n) time as well as algorithms likely to approach O(n) time for all or most images. The best previous solutions require using a more complicated architecture or require Omega(n lg n) time. We also show that on a restricted version of the architecture, any algorithm requires Omega(n lg n) time in the worst case.

The Fat-Pyramid And Universal Parallel Computation Independent Of Wire Delay, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

This paper shows that a fat-pyramid of area Θ(A) requires only O(log A) slowdown to simulate any competing network of area A under very general conditions. The result holds regardless of the processor size (amount of attached memory) and number of processors in the competing networks as long as the limitation on total area is met. Furthermore, the result is valid regardless of the relationship between wire length and wire delay. We especially focus on elimination of the common simplifying assumption that unit time suffices to traverse a wire regardless of its length, since the assumption becomes more and more …

Studies On Design, Routing And Fault Tolerance Of Interconnection Network., Krishnendu Mukhopadhyay Dr.

Doctoral Theses

A recent trend in computing is to distribute the computations among a set of processing elements. There are two basic appronches to this - one is to build a loosely-coupled system and the other is to form a tightly-coupled system [PS85].In a loosely-coupled system, the processors do not share common memory or a common clock; but sharing of important resources like data files, softwares, special hardware components etc., is possible without duplicating the resources themselves. The processing nodes may even be geographicully separated from each other and are connected through databuses, telephone/radio links, satellite, etc. Such loosely- coupled systems are …

A Macro Extension For The Woody Assembly Language, Lewis Barnett Iii

Department of Math & Statistics Technical Report Series

We discuss an extension to the Woody Assembly Language [Cha94] which allows new instructions to be defined. The mechanism is similar to the C language's #define macros, allowing a name to be supplied for a piece of code which will be expanded in line. Provisions are made for writing new non-destructive branching instructions as well as instructions which are simply new names for commonly used bits of code.

Optimum Continuous Sampling Plans And A Few Other Sqc Problems., D Ghosh Dr.

Doctoral Theses

The wide acceptance of Statistics as a basic tool in technölogical growth, later recog- nised as a Key technology, gained ground with the pioneering work of Shewhart in 20s, introducing Statistical Quality Control (SQC) in manufacturing industry. Around the same time a solid statistical basis was being worked out for the ageold concepts of sampling inspection for industrial products. By 1930, acceptance sam- pling for lot by lot inspection was being applied in Western Electric Company and elsewhere. Since then statistical tools have been the major technical inputs of To- tal Quality Management which has spread far and wide as …

Multivalued Approach For Uncertainty Management., Deba Prasad Mandal Dr.

Doctoral Theses

Real life problems are rarely free from uncertainty which usually emerges from the deficiencies of information available from a situation. The defi- ciencies may result from incomplete, imprecise, not fully reliable, vague or contradictory information depending on the problem. Management of uncer- tainty in a decision making system has been an important research problem for many years.Until the inception of the concept of fuzzy set theory in 1965 (1), the theory of probability and statistics was the primary mathematical tool for modeling uncertainty in a system/situation. Fuzzy set theory has shown enormous proinise in handling uncertaintics to a reasonable extent …

An Algorithmic Palette Tool, Gary R. Greenfield

Department of Math & Statistics Technical Report Series

Our algorithmic tool follows the model of RGB percentage curves, but now the control of these curves is though algorithms that indirectly, and more abstractly, create, evolve, and modify such curves. To fully explain our methods we must first introduce the topic "mutating expressions." This is done in Section Two. In Section Three we document the user-interface problems we dealt with, and finally in Section Four discuss conclusions and suggest ideas for future exploration. Before commencing with the technical details however, we wish to emphasize the nature of the "colorization" problem that led to the conception and development of our …

Merlin's Magic Square Enhanced, Gary R. Greenfield

Department of Math & Statistics Technical Report Series

This paper first considers questions about games related to Merlin's Magic Square from the point of view of group actions. At this juncture, little beyond the formal model is new, but the exposition sets the stage for considering certain "enhanced" versions of these games. The analysis of enhanced games, with the aid of semigroup actions, is carried out in complete detail for an ostensibly simpler (k = 3) game before turning to a Merlin ( k = 4) game. Concluding sections discuss various ways to generalize our games.

To review the solution to Merlin's Magic Square, we begin by introducing …

A Model Of Visual Recognition Implemented Using Neural Networks, Vincent C. Phillips

Theses: Doctorates and Masters

The ability to recognise and classify objects in the environment is an important property of biological vision. It is highly desirable that artificial vision systems also have this ability. This thesis documents research into the use of artificial neural networks to implement a prototype model of visual object recognition. The prototype model, describing a computtional architecture, is derived from relevant physiological and psychological data, and attempts to resolve the use of structural decomposition and invariant feature detection. To validate the research a partial implementation of the model has been constructed using multiple neural networks. A linear feed-forward network performs pre-procesing …

Fast Accurate Simulation Of Large Shared Memory Multiprocessors, Bob Boothe Phd

Faculty Publications

Fast computer simulation is an essential tool in the design of large parallel computers. We discuss the design and performance of our Fast Accurate Simulation Tool, FAST. We start by summarizing the tradeoffs made in the designs of this and other simulators. The key ideas used in this simulator involve execution driven simulation techniques that modify the object code of the application program being studied. This produces an augmented version of the code that is directly executed and performs much of the work of the simulation. We extend the previous work in execution driven simulation by introducing several new uses …

Applications Of Fuzzy Counterpropagation Neural Networks To Non-Linear Function Approximation And Background Noise Elimination, I. M. Wiryana

Theses: Doctorates and Masters

An adaptive filter which can operate in an unknown environment by performing a learning mechanism that is suitable for the speech enhancement process. This research develops a novel ANN model which incorporates the fuzzy set approach and which can perform a non-linear function approximation. The model is used as the basic structure of an adaptive filter. The learning capability of ANN is expected to be able to reduce the development time and cost of the designing adaptive filters based on fuzzy set approach. A combination of both techniques may result in a learnable system that can tackle the vagueness problem …

Distributed Memo: A Heterogeneously Distributed And Parallel Software Development Environment, William T. O'Connell, George K. Thiruvathukal, Thomas W. Christopher

Computer Science: Faculty Publications and Other Works

Heterogeneously distributed and parallel computing environments are highly dependent on hardware, data migration, and protocols. The result is significant difficulty in software reuse, portability across platforms, and an increased overall development effort. The appearance of a shared directory of unordered queues can be provided by integrating heterogeneous computers transparently. This integration provides a conducive environment for parallel and distributed application development, by abstracting the issues of hardware and communication. Object oriented technology is exploited to provide this seamless environment.

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 …

Feasible Offset And Optimal Offset For Single-Layer Channel Routing, Ronald I. Greenberg, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

The paper provides an efficient method to find all feasible offsets for a given separation in a VLSI channel routing problem in one layer. The prior literature considers this task only for problems with no single-sided nets. When single-sided nets are included, the worst-case solution time increases from Theta(n) to Omega(n^2), where n is the number of nets. But, if the number of columns c is O(n), one can solve the problem in time O(n^{1.5}lg n ), which improves upon a `naive' O(cn) approach. As a corollary of this result, the same time bound suffices to find the optimal offset …

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 channels 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, previous results for running time and space are improved by a factor of L/lg n and L , respectively, where L is the channel length and n is the number of terminals.

Fortran 90d/Hpf Compiler For Distributed Memory Mimd Computers: Design, Implementation, And Performance Results, Zeki Bozkus, Alok Choudhary, Geoffrey C. Fox, Tomasz Haupt

Northeast Parallel Architecture Center

Fortran 90D/HPF is a data parallel language with special directives to enable users to specify data alignment and distributions. This paper describes the design and implementation of a Fortran90D/HPF compiler. Techniques for data and computation partitioning, communication detection and generation, and the run-time support for the compiler are discussed. Finally, initial performance results for the compiler are presented which show that the code produced by the compiler is portable, yet efficient. We believe that the methodology to process data distribution, computation partitioning, communication system design and the overall compiler design can be used by the implementors of HPF compilers.

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 …

A Study Of The Methodologies Currently Available For The Maintenance Of The Knowledge-Base In An Expert System, Kai Teh

Theses: Doctorates and Masters

This research studies currently available maintenance methodologies for expert system knowledge bases and taxonomically classifies them according to the functions they perform. The classification falls into two broad categories. These are: (1) Methodologies for building a more maintainable expert system knowledge base. This section covers techniques applicable to the development phases. Software engineering approaches as well as other approaches are discussed. (2) Methodologies for maintaining an existing knowledge base. This section is concerned with the continued maintenance of an existing knowledge base. It is divided into three subsections. The first subsection discusses tools and techniques which aid the understanding of …

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 …

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 …