Pattern Recognition Applications

CSC 558

 

Audience: CISC859 is an introductory course in pattern recognition, geared toward students who have some background in computer science. The course material is relevant to many areas of research, including artificial intelligence, computer vision, signal processing, data mining, visual languages, and geographic information systems. In past years, this course has been taken by graduate students from computing, electrical engineering, mechanical

engineering, geology, chemistry, and mathematics.
 

General Description
 

Many applications involve recognition of patterns in data. Data can be one-dimensional (speech, electrocardiograms, seismic measurements) or two-dimensional (document images, medical images satellite images) or three-dimensional (image sequences, crystallography, tomography). The field of pattern recognition provides general, domain-independent techniques for data analysis. In this course, we study statistical pattern recognition and structural pattern recognition. Statistical pattern recognition is applied to classification problems. These involve assigning a sample to one of aprespecified set of classes. For example, signature validation classifies a signature into one of the two categories “real” or “forgery”. An English character recognizer classifies a pattern into one of about 80 categories (lower-case and upper-case letters, digits, punctuation); in contrast, Chinese character recognition involves thousands of categories. The following general steps are used in statistical pattern recognition:
 

(1) Choose a set of features that can be measured from the input data. For character recognition, we might measure symmetry, number of holes, average stroke direction etc.
 

(2) Characterize the feature values that are observed on training data. For character recognition, we collect data on the feature values observed for samples from class “a”, class “b”, class “c” etc. This is called training the classifier.
 

(3) Classify an unknown pattern by measuring its feature values, and comparing them to the results of step (2): compare the features of the unknown pattern to the feature values that we expect for “a”, for “b”, for “c”, etc. This comparison can be done in many different ways. We will study the Bayes classifier, nearest neighbour classifier, decision tree, and other approaches.

(4) Test the classifier to obtain an estimate of its performance. We discuss how to make good use of the available data, so that both training and testing are well supported. The test data should be distinct from the training data; otherwise the test produces a falsely high estimate of the performance of the classifier. Structural pattern recognition builds a description of the internal structure of a pattern (in contrast to statistical pattern recognition, which classifies the pattern into one of several prespecified categories). For example, in analyzing an image obtained by a mobile robot, we need to produce a description of the objects in the image and their spatial arrangement. Syntactic pattern recognition is one form of structural pattern recognition; it uses grammatical techniques to describe and analyze the structure of a pattern. Grammars and parsing methods for strings (as used in compilers) are extended in various ways to apply to two-dimensional and three-dimensional patterns. Other structural pattern recognition techniques use fuzzy graph matching, Hidden Markov Models, blackboards, etc. The treatment of errors and uncertainty is a subject of ongoing research in all of these approaches.
 

Lectures reflect my interest in document-image recognition: the interpretation of scanned images of documents containing text and/or figures. Pattern recognition problems arising in this area include character recognition, both for small alphabets (Roman, Cyrillic) and large alphabets (Chinese), layout analysis (separation of figures from text, recognition of reading order), and recognition of diagrams (math notation, chemical structures, music notation, UML diagrams, etc). There is ongoing interest in document-image analysis because of the many situations in which people need to convert paper-based records into on-line information that is suitable for algorithmic searching and processing. This is an on-going need. Predictions of a "paperless office" are not coming true; instead we are facing a proliferation of both electronic and paper documents. Document image analysis is an important element in creating a convenient transition between paper and electronic forms of documents.
 

Course Materials
 

Textbook Pattern Classification, Second Edition, by Duda, Hart, and Stork, Wiley 2001. This book is well established as the standard reference book in pattern recognition. 

.

Prerequisites
 

Familiarity with the following subjects is helpful. Students missing this background have successfully taken the course,

sometimes with extra reading. Review is provided in lectures.

Elementary calculus – Integrals, and how they relate to the area under a curve.

Elementary probability theory – Probability distribution, probability density, random variables. I provide review.

Elementary formal languages – Context free grammars, and how they define a language. I provide a review.

Programming – For the course project, you are expected to write code to implement a classifier.

Information about suggested projects is provided on the course website. Most students

implement a digit classifier; this entails writing code to modify images, i.e. to modify

two-dimensional arrays of pixel values. Any programming language can be used,

provided you know how to perform image I/O. Sample code is provided in C and Java.
 

Marking

Assignments 5% There are five assignments, posted on the course web page.

Project 20% Write critiques of other students' oral presentations, to provide constructive feedback. I photocopy

these critiques and give them to the presenting student; I do not use your critique in assigning a

mark to the presenting student.

Mid-Term exams 30%
Quizes 5%

Final Exam 40% The test will be closed book. I will provide a summary sheet of formulas and definitions.

 

Topics
 

We do not study all of these topics in depth. We concentrate on stating the major problems within each area, as well as

approaches to their solution. This provides sufficient background so that you can communicate with experts in the area,

should your research require it. DHS is an abbreviation for the textbook by Duda, Hart, and Stork.
 

1. Introduction to pattern recognition. Processing of pictorial data [Course Notes].
 

2. Introduction to statistical pattern recognition. Feature extraction and the feature space. Bayes' decision rule. The Normal density [DHS Chapters 1, 2]. Estimating the performance of a classifier [DHS Section 9.6].
 

3. Overview of topics in statistical pattern recognition. Estimation of probability densities (supervised learning): estimating parameters when the form of the density is known [DHS Ch. 3], and estimating the density in general [DHS Sections 4.1 to 4.4]. Nearest-neighbor classifiers [DHS Sections 4.5 and 4.6]. Estimation of discriminant functions [CHS Chapter 5].
 

Unsupervised learning and clustering [DHS Chapter 10]. Decision trees for multistage pattern recognition [DHS Section 8.2 and 8.3]. Combining the results of multiple classifiers [DHS Section 9.7].
 

4. Introduction to structural pattern recognition. Document image analysis. Recognition of mathematical notation. [Notes]

5. Syntactic pattern recognition. Quick review of formal languages [DHS Sec 8.6]. Programmed grammars. String languages for pattern description. Primitives representing boundaries and regions. Examples of pattern grammars; PDL (Picture Description Language). Transformational grammars. Attributed grammars. [Notes; Fu Chapters 2, 3]
 

6. Generalizing "string" grammars for multidimensional patterns: Array, tree, plex, and graph grammars. [Notes]
 

7. Noisy and distorted patterns. Image defect models. Clustering of structural patterns. Fuzzy matching of structural descriptions (fingerprint identification). Stochastic grammars and fuzzy grammars. Document image decoding using Markov source models. [Notes]ecognition Applications