Optimal correspondence of string subsequences
IEEE Transactions on Pattern Analysis and Machine IntelligencePublished 1 January 1990
Y.P. Wang, T. Pavlidis
Citations60
SJR quartileQ1
SJR score3.91
SNIP5.99
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The authors prove that the string distance derived from OCS is a metric and the feasibility of applying OCS to UPC bar-code recognition is investigated, showing the elegance of string-to-regular-expression OCS compared to the relaxation and elastic matching techniques.
Abstract
The definition of optimal correspondent subsequence (OCS), which extends the finite alphabet editing error minimization matching to infinite alphabet penalty minimization matching, is given. The authors prove that the string distance derived from OCS is a metric. An algorithm to compute the string-to-string OCS is given. The computational complexity of OCS is analyzed. OCS is more efficient than relaxation and elastic matching for 1D problems. An algorithm combining syntactic information in template matching is given to show the ease of integrating regular grammar into the OCS technique. Since in different applications different penalty functions may be required, two of them are discussed: one pointwise and the other piecewise. The pointwise application consists of a stereo epipolar line matching problem solved by using string-to-string OCS. The feasibility of applying OCS to UPC bar-code recognition is investigated, showing the elegance of string-to-regular-expression OCS compared to the relaxation and elastic matching techniques.>
Keywords
Computer Science
Medical Entomology and ZoologyHandbook of theoretical computer science
4,202 Citations1990Jan Van Leeuwen
Robot Vision
3,632 Citations1986Berthold K. P. Horn
This book presents a coherent approach to the fast-moving field of computer vision, using a consistent notation based on a detailed understanding of the image formation process, and will provide a useful and current reference for professionals working in the fields of machine vision, image processing, and pattern recognition.
Journal of the ACMThe String-to-String Correction Problem
3,063 Citations1974Robert A. Wagner, Michael J. Fischer
An algorithm is presented which solves the string-to-string correction problem in time proportional to the product of the lengths of the two strings.
The American Journal of PsychologyFoundations of Cyclopean Perception
2,414 Citations1973Whitman Richards, Béla Julesz
ScienceCooperative Computation of Stereo Disparity
1,380 Citations1976David Marr, Tomaso Poggio
It is shown that this algorithm successfully extracts information from random-dot stereograms, and its implications for the psychophysics and neurophysiology of the visual system are briefly discussed.
Formal Languages and Their Relation to Automata
1,341 Citations1969John E. Hopcroft, Jeffrey D. Ullman
The theory of formal languages as a coherent theory is presented and its relationship to automata theory is made explicit, including the Turing machine and certain advanced topics in language theory.
Communications of the ACMA linear space algorithm for computing maximal common subsequences
1,108 Citations1975D. S. Hirschberg
The problem of finding a longest common subsequence of two strings has been solved in quadratic time and space and an algorithm is presented which will solve this problem in QuadraticTime and in linear space.
Nuclear Science and EngineeringFormal Languages and their Relation to Automata
1,004 Citations1970James B. Morris
IEEE Transactions on Pattern Analysis and Machine IntelligenceStereo by Intra- and Inter-Scanline Search Using Dynamic Programming
930 Citations1985Yuichi Ohta, Takeo Kanade
This paper presents a stereo matching algorithm using the dynamic programming technique that uses edge-delimited intervals as elements to be matched, and employs the above mentioned two searches: one is inter-scanline search for possible correspondences of connected edges in right and left images and the other is intra-scanlines search for correspondence of edge-Delimited interval on each scanline pair.
ACM Computing SurveysComputational Stereo
710 Citations1982Stephen T. Barnard, Martin A. Fischler
The criteria that are important for evaluating the effectiveness of various computational stereo techniques are presented and a representative sampling of computational stereo research is provided.
ACM Computing SurveysApproximate String Matching
586 Citations1980Patrick A. V. Hall, Geoff R. Dowling
SIAM Journal on ComputingGeneralized String Matching
310 Citations1987Karl Abrahamson
A generalization of string matching, in which the pattern is a sequence of pattern elements, each compatible with a set of symbols, is investigated, which shows that generalized string matching requires a time-space product of $\Omega ({{n^2 } / {\log n}})$ on a powerful model of computation, when the alphabet is restricted to n symbols.
IEEE Transactions on Pattern Analysis and Machine IntelligenceShape Matching Using Relaxation Techniques
265 Citations1979Larry S. Davis
This approach was tested on a data base consisting of digitized coastlines in various map projections and found that in nearly all cases, all matches except the correct one were eliminated by the relaxation processes.
Journal of the ACMBounds on the Complexity of the Longest Common Subsequence Problem
248 Citations1976Jeffrey D. Ullman, Alfred V. Aho +1 more
It is shown that unless a bound on the total number of distinct symbols is assumed, every solution to the problem can consume an amount of time that is proportional to the product of the lengths of the two strings.
The International Journal of Robotics ResearchIdentification of Partially Obscured Objects in Two and Three Dimensions by Matching Noisy Characteristic Curves
231 Citations1987Jacob T. Schwartz, Micha Sharir
Efficient methods for smoothing the noisy data and for matching portions of the observed object boundaries (or of characteristic curves lying on bounding surfaces of 3-D objects) to prestored models are described.
IEEE Transactions on Pattern Analysis and Machine IntelligenceElastic Matching of Line Drawings
184 Citations1981Dc Burr
Examples are shown on handprint and animation, suggesting the use of dynamic matching for shape recognition and for motion correspondence, and extending the model to line drawings.
Medical Entomology and ZoologyAlgorithms for finding patterns in strings
156 Citations1990Alfred V. Aho
Communications of the ACMOrder- <i>n</i> correction for regular languages
110 Citations1974Robert A. Wagner
The method presented requires time proportional to the number of characters in α.
Communications of the ACMSpelling correction in systems programs
106 Citations1970Howard L. Morgan
By using systems which perform spelling correction, the number of debugging runs per program has been decreased, saving both programmer and machine time.
IEEE Transactions on Pattern Analysis and Machine IntelligenceParallel Algorithms for Syllable Recognition in Continuous Speech
50 Citations1985Renato De Mori, Pietro Laface +1 more
A distributed rule-based system for automatic speech recognition is described and experiments on the automatic segmentation and recognition of phrases, made of connected letters and digits, are described and discussed.
Pattern Recognition LettersStereo matching using intra- and inter-row dynamic programming
27 Citations1986S.A. Lloyd
A stereo matching algorithm based on dynamic programming that produces a set of candidate matches for each row separately and uses continuity constraints to choose the best matches.
IBM Systems JournalThe characteristics and decodability of the Universal Product Code symbol
24 Citations1975D. Savir, G. J. Laurer
Decodability is shown to depend on the structure of the code and symbol, the size of the symbols, the precision with which the symbol is printed, the technique of scanning employed, the accuracy with which measurements are made, the decoding logic, and the physical operation of scanning.
Theoretical Computer ScienceMatching patterns in strings subject to multi-linear transformations
24 Citations1988Tali Eilam-Tzoreff, Uzi Vishkin
Problem: Find all occurrences of the pattern in the text where the pattern may appear subject to any one of these transformations.
IEEE Transactions on Pattern Analysis and Machine IntelligenceThe Use of a Syntactic Shape Analyzer for Contour Matching
14 Citations1979Theodosios Pavlidis
Pattern Recognition LettersString matching for stereo vision
8 Citations1989Hua Zhi Dan, Bernard Dubuisson
A new approach to the problem of stereo matching essentially based on the comparison of two strings, which consists of two parts: first the Global Matching, which deals with the vertical columns, provides an interval; secondly, the Local Matching works between the horizontal epipolar lines to find the corresponding point precisely in this interval.