Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 6 of 6
Full-Text Articles in Physical Sciences and Mathematics
A Systolic Image Difference Algorithm For Rle-Compressed Images, Fikret Erçal, Mark Allen, Hao Feng
A Systolic Image Difference Algorithm For Rle-Compressed Images, Fikret Erçal, Mark Allen, Hao Feng
Computer Science Faculty Research & Creative Works
A new systolic algorithm which computes image differences in run-length encoded (RLE) format is described. The binary image difference operation is commonly used in many image processing applications including automated inspection systems, character recognition, fingerprint analysis, and motion detection. The efficiency of these operations can be improved significantly with the availability of a fast systolic system that computes the image difference as described in this paper. It is shown that for images with a high similarity measure, the time complexity of the systolic algorithm is small and, in some cases, constant with respect to the image size. A formal proof …
Systolic Algorithm For Processing Rle Images, Hao Feng, Fikret Erçal, Filiz Bunyak
Systolic Algorithm For Processing Rle Images, Hao Feng, Fikret Erçal, Filiz Bunyak
Computer Science Faculty Research & Creative Works
Image difference operation is commonly used in on-line automated printed circuit board (PCB) inspection systems as well as many other image processing applications. In this paper, we describe a new systolic algorithm and its system architecture which computes image differences in run-length encoded (RLE) format. The efficiency of this operation greatly affects the overall performance of the inspection system. It is shown that, for images with a high similarity measure, the time complexity of the systolic algorithm is a small constant. A formal proof of correctness for the algorithm is also given in the paper.
Rmesh Algorithms For Parallel String Matching, Hsi-Chieh Lee, Fikret Erçal
Rmesh Algorithms For Parallel String Matching, Hsi-Chieh Lee, Fikret Erçal
Computer Science Faculty Research & Creative Works
String matching problem received much attention over the years due to its importance in various applications such as text/file comparison, DNA sequencing, search engines, and spelling correction. Especially with the introduction of search engines dealing with tremendous amount of textual information presented on the world wide web and the research on DNA sequencing, this problem deserves special attention and any algorithmic or hardware improvements to speed up the process will benefit these important applications. In this paper, we present three algorithms for string matching on reconfigurable mesh architectures. Given a text T of length n and a pattern P of …
Relaxing Synchronization In Distributed Simulated Annealing, Bruce M. Mcmillin, Chul-Eui Hong
Relaxing Synchronization In Distributed Simulated Annealing, Bruce M. Mcmillin, Chul-Eui Hong
Computer Science Faculty Research & Creative Works
This paper presents a cost error measurement scheme and relaxed synchronization method, for simulated annealing on a distributed memory multicomputer, which predicts the amount of cost error that an algorithm will tolerate. An adaptive error control method is developed and implemented on an Intel iPSC/2
Parallel Error Tolerance Scheme Based On The Hill Climbing Nature Of Simulated Annealing, Bruce M. Mcmillin, Chul-Eui Hong
Parallel Error Tolerance Scheme Based On The Hill Climbing Nature Of Simulated Annealing, Bruce M. Mcmillin, Chul-Eui Hong
Computer Science Faculty Research & Creative Works
In parallelizing simulated annealing in a multicomputer, maintaining the global state S involves explicit message traffic and is a critical performance bottleneck. One way to mitigate this bottleneck is to amortize the overhead of these state updates over as many parallel state changes as possible. Using this technique introduces errors in the calculated cost C(S) of a particular state S used by the annealing process. Analytically derived bounds are placed on this error in order to assure convergence to the correct result. The resulting parallel simulated annealing algorithm dynamically changes the frequency of global updates as a function of the …
Expectations For Associative-Commutative Unification Speedups In A Multicomputer Environment, Ralph W. Wilkerson, Bruce M. Mcmillin
Expectations For Associative-Commutative Unification Speedups In A Multicomputer Environment, Ralph W. Wilkerson, Bruce M. Mcmillin
Computer Science Faculty Research & Creative Works
An essential element of automated deduction systems is unification algorithms which identify general substitutions and when applied to two expressions, make them identical. However, functions which are associative and commutative, such as the usual addition and multiplication functions, often arise in term rewriting systems, program verification, the theory of abstract data types and logic programming. The introduction to the associative and commutative equality axioms together with standard unification brings with it problems of termination and unreasonably large search spaces. One way around these problems is to remove the troublesome axioms from the system and to employ a unification algorithm which …