Abstract
Most of the developments in pattern recognition research during the past decade deal with the decision-theoretic approach [1.1–11] and its applications. In some pattern recognition problems, the structural information which describes each pattern is important, and the recognition process includes not only the capability of assigning the pattern to a particular class (to classify it), but also the capacity to describe aspects of the pattern which make it ineligible for assignment to another class. A typical example of this class of recognition problem is picture recognition, or more generally speaking, scene analysis. In this class of recogniton problems, the patterns under consideration are usually quite complex and the number of features required is often very large which makes the idea of describing a complex pattern in terms of a (hierarchical) composition of simpler subpatterns very attractive. Also, when the patterns are complex and the number of possible descriptions is very large, it is impractical to regard each description as defining a class (for example, in fingerprint and face identification problems, recognition of continuous speech, Chinese characters, etc.). Consequently, the requirement of recognition can be satisfied only by a description for each pattern rather than the simple task of classification.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
K.S. Fu: Sequential Methods in Pattern Recognition and Machine Learning (Academic Press, 1968)
G.S. Sebestyen: Decision Process in Pattern Recognition (Macmillan, New York 1962)
N.J. Nilsson: Learning Machines-Foundations of Trainable Pattern-Classifying System (McGraw-Hill, 1965)
J.M. Mendel, K.S. Fu: Adaptive, Learning and Pattern Recognition Systems: Theory and Applications (Academic Press, 1970)
W. Meisel: Computer-Oriented Approaches to Pattern Recognition (Academic Press, 1972)
K. Fukunaga: Introduction to Statistical Pattern Recognition (Academic Press, 1972)
E. A. Patrick: Fundamentals of Pattern Recognition (Prentice-Hall, 1972)
H.C. Andrews: Introduction to Mathematical Techniques in Pattern Recognition (Wiley, 1972)
R.O. Duda, P.E. Hart: Pattern Classification and Scene Analysis (Wiley, 1973)
C.H. Chen: Statistical Pattern Recognition (Hayden Book Company, Washington, D. C. 1973)
T.Y. Young, T.W. Calvert: Classification, Estimation, and Pattern Recognition (American Elsevier, 1973)
K.S. Fu: Syntactic Methods in Pattern Recognition (Academic Press, 1974)
W.F. Miller, A.C. Shaw: Proc. AFIPS Fall Joint Computer Conference (1968)
R. Narasimhan: Rpt. 121, (Digital Computer Laboratory, University of Illinois, Urbana, Illinois 1962)
Special Issues of PATTERN RECOGNITION on Syntactic Pattern Recognition, Vol. 3, No. 4, 1971 and Vol. 4, No. 1, 1972
N.V. Zavalishin, I.B. Muchnik: Automatika i Telemekhanika 86 (1969)
Ya.Z. Tsypkin: Foundations of the Theory of Learning System (Nauka, Moscow 1970)
M.A. Aiserman, E.M. Braverman, L.I. Rozonoer: Potential Function Method in Theory of Learning Machines (Nauka, Moscow 1970)
K.S. Fu: Pattern Recognition and Machine Learning (Plenum Press, 1971)
A.G. Arkadev, E.M. Braverman: Learning in Pattern Classification Machines (Nauka, Moscow 1971)
R.L. Grimsdale, F.H. Summer, C.J. Tunis, T. Kilburn: Proc. IEEE, Vol. 106, Part B, No. 26, March, 1959, pp. 210–221; reprinted in Pattern Recognition ed. by L.Uhr, (Wiley, 1966) pp. 317–338
M. Eden, M. Halle: Proc. 4th London Symp. on Information Theory (Butterworth, London 1961) pp. 287–299
L.D. Earnest:Information Processing, ed. by C.M. Poplewell(North Holland Publishing Co., Amsterdam 1963) pp. 462–466
P. Mermelstein, M. Eden: Information and Control 7, 255 (1964)
M. Eden, P. Mermelstein: Proc. 16th Ann. Conf. on Engineering in Medicine and Biology (1963), pp. 12–13
H. Freeman: IEE Trans. EC-10, 260 (1961)
H. Freeman: Proc. National Electronics Conf. 18, 312 (1962)
P.J. Knoke, R.G. Wiley: Proc. IEEE Comp. Conf., 142 (1967)
J. Feder: Information and Control 13, 230 (1968)
H. Freeman, S.P. Morse: J. of Franklin Inst. 284, 1 (1967)
J. Feder and H. Freeman: IEEE Intern. Convention Record, Part 3, 1966, pp. 69–85
C.T. Zahn: SLAC Rpt. 72 (Stanford Linear Accelerator Center, Stanford, Calif. 1966)
H. Freeman, J. Garder: IEEE Trans. EC-13, 118 (1964)
R. Narasimhan: Comm. ACM 9, 166 (1966)
R.J. Spinrad: Information and Control 8, 124 (1965)
J.F. O’Callaghan: “Problems in On-Line Character Recognition”, Picture Language Machines, ed. by S. Kaneff (Academic Press, 1970)
A.C. Shaw: SLAC-Rpt. 84 (Stanford Linear Accelerator Center, Stanford, Calif. March, 1968)
B.K. Bhargava, K.S. Fu: Tech. Rpt. TR-EE 72–30, School of Electrical Engineering, Purdue University, West Lafayette, Ind. (1972)
M. Nir: Ph. D. thesis, Moore School of Electrical Engineering, University of Pennsylvania, (1967)
R. Narsimhan: Information and Control 7, 151 (1964)
R.S. Ledley, L.S. Rotolo, T.J. Golab, J.D. Jacobsen, M.D. Ginsburg, J.B. Wilson: Optical and Electro-Optical Information Processing, ed. by J.T. Tippett, D. Beckowitz, L. Clapp, C. Koester, A. Vanderburgh, Jr. (MIT Press, Cambridge, Mass. 1965), p. 591
J.W. Butler, M.K. Butler, A. Stroud: “Automatic Classification of Chromosomes”, Proc. Conf. on Data Acquisition and Processing in Biology and Medicine, New York (1963)
H.C. Lee, K.S. Fu: “A Syntactic Pattern Recognition System with Learning Capability”, Proc. COINS-72 (1912)
M. Nagao: “Picture Recognition and Data Structure”, in Graphic Languages, ed. by F. Nake, A. Rosenfeld (North-Holland Publishing Co., Amsterdam, London 1972)
M.D. Kelley: Ph. D. thesis, Dept. of Computer Science, Stanford University, Stanford, Calif. (1970)
L.G. Roberts: Optical and Electro-Optical Information Processing, ed. by J.T. Tippett, D. Beckowitz, L. Clapp, C. Koester, A. Vanderburgh, Jr. (MIT Press, Cambridge, Mass. 1965), p. 159
R.O. Duda, P.E. Hart: “Experiments in Scene Analysis”, Proc. 1st Nat. Symp. on Industrial Robots, Chicago (1970)
J.A. Feldman, G.M. Feldman, G. Falk, G. Grape, J. Pearlman, I. Sobel, J.M. Tenenbaum: “The Stanford Hand-Eye Project”, Proc., 1st Intern. Joint Conf. on Artificial Intelligence, Washington D.C., (1969)
T. Pavlidis: Pattern Recognition 1, 165 (1968)
A. Rosenfeld, J.P. Strong: “A Grammar for Maps”, Software Engineering (2 ed. by J.T. Tou, Academic Press 1971)
T. Pavlidis: Pattern Recognition 4, 5 (1972)
T. Pavlidis: “Structural Pattern Recognition: Primitives and Juxtaposition”, Frontiers of Pattern Recognition, ed. by S. Watanabe (Academic Press, 1972)
M.L. Minsky, S. Papert: Project MAC Progress Rpt. IV (MIT Press, Cambridge, Mass. 1967)
A. Guzman: Proc. AFIPS FJCC 33, Pt. 1, 291 (1968)
C.R. Brice, C.L. Fennema: Artificial Intelligence 1, 205 (1970)
K.S. Fu, T.L. Booth: “Grammatical Inference—Introduction and Survey”. IEEE Trans. SMC-5, 95 and 409 (1975)
R. Narasimhan: “On the Description, Generation, and Recognition of Classes of Pictures”, in Automatic Interpretation and Classification of Images, ed. by A. Grasselli (Academic Press, 1969)
J. Feder: Information Sciences 3, 225 (1971)
A.W. Laffan, R.C. Scott: “A New Tool for Automatic Pattern Recognition: A Context-Free Grammar for Plane Projective Geometry”, Proc. Ind. Intern. Joint Conf. on Pattern Recognition, Lyngby-Copenhagen, Denmark, 1974
M.C. Clowes: “Transformational Grammars and the Organization of Pictures”, in Automatic Interpretation and Classification of Images, ed. by A. Grasselli (Academic Press, 1969)
Laveen Kanal, B. Chandrasekaran: “On the Linguistic, Statistical and Mixed Models for Pattern Recognition”, in Frontiers of Pattern Recognition, ed. by S. Watanabe (Academic Press, 1972)
R. Narsimhan: “Picture Languages”, in Picture Language Machines, ed. by S. Kaneff (Academic Press, 1970)
W.E. Underwood, L.N. Kanal: “Structural Description, Transformational Rules and Pattern Analysis”, Proc. 1st Intern. Joint on Pattern Recognition, Washington, D.C. (1973)
M.L. Minsky: Proc. IRE 49, 8 (1961)
T.G. Evans: “A Formalism for the Description of Complex Objects and Its Implementation”, Proc. 5th Intern. Congress on Cybernetics, Namur, Belgium (1967)
M.B. Clowes: “Pictorial Relationships—A Syntactic Approach”, in Machine Intelligence IV, ed. by B. Meltzer, D. Michie (American Elsevier, New York 1969)
T.G. Clowes: “Descriptive Pattern Analysis Techniques”, in Automatic Interpretation and Classification of Images, ed. by A. Grasselli (Academic Press, 1969)
H.G. Barrow, J.R. Popplestone: Machine Intelligence 6, ed. by B. Meltzer, D. Michie (Edinburgh University Press, 1971) pp. 377–396
R.A. Kirsch: IEEE Trans. EC-13, 363 (1964)
M.F. Dacey: Pattern Recognition 2, 11 (1970)
D.M. Milgram, A. Rosenfeld: IFIP Congress 71, (North-Holland, Amsterdam 1971) pp. 166–173
A.C. Shaw: Information and Control 14, 9 (1969)
A.C. Shaw: J.ACM 17, 453 (1970)
J.L. Pfaltz, A.Rosenfeld: Proc. 1st Intern. Joint Conf. on Artificial Intelligence, Washington D.C. (1969), pp. 609–619
A.C. Shaw: “Picture Graphs, Grammars, and Parsing”, in Frontiers of Pattern Recognition, ed. by S. Watanabe (Academic Press, 1972)
J.L. Pfaltz: Tech. Rpt. 70–138, Computer Science Center, University of Maryland, College Park, Md. (1970)
J.M. Brayer, K.S. Fu: Rpt. 75–1, School of Electrical Engineering, Purdue University, W.Lafayette, Ind. (1975)
T. Pavlidis: Jour. of ACM 19, 11 (1972)
A. Rosenfeld: “Picture Automata and Grammars: An Annotated Bibliography”, Proc. Symp. on Computer Image Processing and Recognition, Columbia, Mo. (1972), Vol. 2
T. Pavlidis: “Graph Theoretic Analysis of Pictures”, in Graphic Languages, ed. by F. Nake and A. Rosenfeld (North-Holland, Amsterdam 1972)
W.S. Brainerd: Information and Control 14, 217 (1969)
J.E. Donar: “Tree Acceptors and Some of Their Applications”, J. of Computer and System Sciences 4, (1970)
K.S. Fu, B.K. Bhargava: IEEE Trans. C22, 1087 (1973)
B.K. Bhargava, K.S. Fu: “Transformation and Inference of Tree Grammars for Syntactic Pattern Recognition”, Proc. IEEE Intern. Conf. on Systems, Man and Cybernetics, Dallas, Tex. (1974)
J. Gips: Pattern Recognition 6, 189 (1974)
J.M. Foster: Automatic Syntactic Analysis, (American Elsevier 1970)
A.V. Aho, J.D. Ullman: The Theory of Parsing, Translation, and Compiling, Vol. 1, Parsing (Prentice-Hall 1972)
F.W. Blackwell: “Combining Mathematical and Structural Pattern Recognition”, Proc. 2nd Intern. Joint Conf. on Pattern Recognition, Copenhagen, Denmark (1974)
V. Grenander: Tech. Rpt., Division of Applied Math., Brown University, Providence, R.I.
K.S. Fu: “Syntactic Pattern Recognition and Stochastic Languages”, in Frontiers of Pattern Recognition, ed. by S. Watanabe (Academic Press 1972)
V.A. Kovalevsky: “Sequential Optimization in Pattern Recognition and Pattern Description”, Proc. IFIP Congress, Amsterdam (1968)
K.S. Fu: Computer Graphics and Image Processing 2, 433 (1973)
L. W. Fung, K. S. Fu: “Stochastic Syntactic Classification of Noisy Patterns”, Proc. 2nd Intern. Joint Conf. on Pattern Recognition, Copenhagen, Denmark (1974)
V. Dimitrov: “Multilayered Stochastic Languages for Pattern Recognition”, Proc. 1st Intern. Joint Conf. on Pattern Recognition, Washington, D.C. (1973)
H.C. Lee, K.S. Fu: “A Stochastic Syntax Analysis Procedure and Its Application to Pattern Classification”, IEEE Trans. C-21, 660 (1972)
T. Huang, K.S. Fu: Computer Graphics and Image Processing, 1, 257 (1972)
A.V. Aho, T.G. Peterson: “A Minimum Distance Error-Correcting Parser for Context-Free Languages”, SIAM J. Compt., 1, No. 4, 305 (December, 1972)
L.W. Fung, K.S. Fu: IEEE Trans. C-24, 662 (1975)
M.G. Thomason, R.C. Gonzalez: “Classification of Imperfect Syntactic Pattern Structures”, Proc. 2nd Intern. Joint Conf. on Pattern Recognition, Copenhagen, Denmark (1974)
K.S. Fu: “Error-Correcting Parsing for Syntactic Pattern Recognition”, in Data Structures in Pattern Recognition and Computer Graphics, ed. by A. Klinger, K.S. Fu, T. Kunii (Academic Press, 1977)
M.G. Thomason: IEEE Trans. C-24, 1211 (1975)
D.E. Knuth: Math. Syst. Theory 2, 127 (1968)
W.T. Wilson: “Formal Semantic Definition Using Synthesized and Inherited Attributes”, in Formal Semantics of Programming Languages, ed. by R. Rustin (Prentice-Hall, 1972)
D.L. Milgram, A. Rosenfeld: “A Note on Grammars with Coordinates”, in Graphic Languages, ed. by F. Nake, A.Rosenfeld (North-Holland Publ. 1972)
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1977 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Fu, K.S. (1977). Introduction to Syntactic Pattern Recognition. In: Fu, K.S. (eds) Syntactic Pattern Recognition, Applications. Communication and Cybernetics, vol 14. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-66438-0_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-66438-0_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-66440-3
Online ISBN: 978-3-642-66438-0
eBook Packages: Springer Book Archive