The recognition of patterns is required in many application areas. The type of data that is analyzed varies greatly. Examples of one-dimensional data include speech signals, electrocardiograms, and seismic data. Examples of two-dimensional data include scanned document images, medical images, and satellite images. Three-dimensional data arises in image sequences, in crystallography, and in tomography. The goal of pattern-recognition research is to develop general, domain-independent techniques for data analysis.
This course introduces statistical and structural pattern recognition techniques. Statistical pattern recognition techniques are useful for solving classification problems. 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. To apply statistical pattern recognition, we choose a set of features and characterize the distribution of feature values for each pattern class; we then classify an unknown pattern based on its observed feature values.
Structural pattern recognition constructs descriptions of internal pattern structure. For example, image analysis often involves constructing a description, rather than just a classification, of a picture. A description contains information about the primitives in the picture and about the relations among the primitives. Syntactic pattern recognition (one form of structural pattern recognition) uses grammatical techniques to describe and analyze the structure of a pattern. Grammars and parsing methods for one-dimensional strings are extended in various ways to apply to two-dimensional and three-dimensional patterns. The syntactic treatment of errors and uncertainty is a subject of ongoing research.
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, layout analysis (e.g. separation of figures from text), and recognition of diagram notations such as used for music, chemical structures, mathematics, and engineering drawings.
Prerequisites
Schedule: due dates for assignments
Note: Assignment 2 is due Oct 13 (not Oct 10, which is Thanksgiving)
During the first two weeks of the term, you should do the following:
- Obtain a copy of the textbook: Duda, Hart, Stork, "Pattern Classification,"
second edition. I refer to this textbook as DHS.
Also obtain a copy of the course notes (at the bookstore). My last revision of the
course notes was in 2008.
- Read DHS Chapter 1, section 2.1, and section 2.2.
- Work on assignment 1, which is due at the start of week 3.
- Read instructions for the course project, and get data access working.
For the digit recognizer: read the digit recognizer instructions and get image I/O working.
For the seismic data: read the seismic data instructions and start looking at the
raw data.
Or choose your own project: make sure you have access to labeled training data,
and that you can write software that reads the data files.
- Read the course notes:
Skim pages 1-47.
Introduction on pages 1-4.
Bunke survey paper on pages 5-29.
Introduction to image processing on pages 30-41.
Typical steps in pattern recognition on pages 42-47.
Read carefully pages 49-52A and then on to pages 57A and beyond
Important: Notation summary on page 48
Classifier Project:
You can carry out one of the two projects suggested below, or you can suggest a project topic of your own.
In digit recognition, the input is a document page showing the digits 0-9 in various fonts and sizes. The classifier has to locate digits and classify them into one of the 10 classes. In the mine data, the input consists of seismic measurements taken at various points in a mine shaft. The classifier has to locate events and classify them into one of 2 classes: an event resulting from blasting, versus any other seismic event. The digit recognition project is well-established: many CISC859 students have written digit recognizers in the past. The seismic project was new last year, and two students took up the challenge of working with this noisy real-life data. You are welcome to propose your own project, if you have access to labeled data you can use to train a classifier. Past students have worked with classification of electrocardiogram data, fingerprints, face images, iris images, and remotely-sensed images from satellites.
Here are
instructions as well as sample programs and images for constructing a digit recognizer.
Here is information about
classification of seismic events.
You are required to give an oral presentation and written summary for a technical paper. Here are instructions.
Assignment 2
The "Pattern Recognition Resources" (below) include a tool for evaluating the Normal density, if you want to use that for assignment 2.
Note: Assignment 2 is due Oct 13 (not Oct 10, which is Thanksgiving)
Here is a website for evaluating the normal density. For example, you can use this in assignment 2, to obtain a numerical value for the probability of error when p(x | w) is normally distributed. Alternatively, you can leave your answer for P(error) in the form of an integral.
Here is a description of a Digit Classifier written by Henry Xiao (student in CISC859 in Fall 2004). You may find this site useful. In particular, the "Downloads" section allows you to download Henry's training and testing data.
The R project for statistical computing is a free software environment for statistical computing and graphics. A past CISC 859 student wrote to me: "R implements a lot
of the concepts that you discuss in the course, and provides many
built-in datasets (like the IRIS dataset and a car manufacturer
dataset), so it's a great way to get some fast and easy experience
with classifiers from a practical perspective. Coupled with the more
theoretical perspective provided by the lectures, I found it to be
great one-two punch."
A variety of other computing environments also provide implementations of classification algorithms. These computing environments include Weka (with graphical user interface added by RapidMiner), matlab, and OpenCV.
Here is an extensive set of links for pattern recognition and statistics.
IAPR The International Association for Pattern Recognition. Much useful information can be found at the IAPR website. In particular, I recommend taking at look at the information provided by the various Technical Committees of the IAPR, including the following committees:
Document Layout Interpretation and its Application is a site that lists research groups, conferences, data sets, software, and bibliographies.
Here is a tutorial on the Nearest Neighbor Rule for pattern classification.
Related to Pattern Recogntion: CVonline, a compendium of computer vision. Covers many topics, including Hidden Markov Models (HMMs).