**COMP-644A:
Pattern Recognition**

*"You cannot teach a man anything; you can only help him find
it
within himself."*

**Galileo
**

Course:COMP-644A

Title:Pattern Recognition (4 credits, 3 hours (2 lectures) per week)

Time & Place:

Instructor:Godfried Toussaint

Phone:

Office hours:

Teaching Assistant:

- Basic knowledge of
*data structures*and*algorithms* - Basic knowledge of
*probability*and*statistics*. - Basic knowledge of
*linear algebra*. - Basic knowledge of
*geometry*.

- Two
**in-class exams**(75 minutes each) at 24% each. If the mark obtained on the second midterm exam is higher than that on the first, then the course-exam-mark will be the mark obtained on the second midterm exam. Otherwise the course-exam-mark will be the average of the two midterm exam marks. - One
**Web project**(35%). The HTML document is worth 15% and the JAVA applet is worth 20%. See**Student Projects**// 1997 // 1998 // 1999 // 2000 // 2001 // 2002 // 2003 // 2004 // 2005 // for examples. - One
**oral presentation**of a journal paper concerned with an*application*of pattern recognition theory (17%).*Note that the oral presentation will be marked by the students.* - Five practice problem-solving
assignments
that do
**not**count towards the final mark. Assignments are**not**collected. Solutions are posted on the web on "due" dates, and the TA will give tutorials on them before exams. - About 70 reading assignments.

- Much of the material is found on the Course Web Page. The rest is very well treated in the first two books below. The third book contains much of the material concerning proximity graphs.
- Richard O. Duda and Peter
E. Hart and
David G. Stork,
*Pattern Classification*, John Wiley Interscience, 2001. - Nils J. Nilsson,
*The Mathematical Foundations of Learning Machines*, Morgan Kaufman, San Mateo, 1990. - David J. Marchette,
*Random Graphs for Statistical Pattern Recognition*, Wyley Series in Probability and Statistics, John Wiley & Sons, Inc., Hoboken, New Jersey, 2004. - Richard O. Duda and Peter
E.
Hart,
*Pattern Classification and Scene Analysis*, John Wiley & Sons, Inc., 1972. - Geoffrey J. McLachlan,
*Discriminant Analysis and Statistical Pattern Recognition*, John Wiley & Sons, Inc., 1992. - Godfried T. Toussaint,
Ed.,
*Computational Morphology*, North-Holland, 1988. - Marvin Minsky and Seymour
Papert,
*Perceptrons: An Introduction to Computational Geometry*, MIT Press, 1969. - Luc Devroye, Laszlo
Gyorfi
and Gabor
Lugosi,
*A Probabilistic Theory of Pattern Recognition*, Springer-Verlag New York, Inc., 1996. - Dana Ballard and
Christopher
Brown,
*Computer Vision*, Prentice-Hall, 1982.

Introduction to pattern recognition via character recognition: grids, connectivity and contour tracing. Smoothing: regularization, local averaging, median filtering and polygonal approximation. Differentiation: image enhancement, the Laplacian operator and unsharp masking. Moments of area and perimeter for shape measurement. Medial axis transforms: skeletonization algorithms and medial axis algorithms. Topological feature extraction: convex hulls and convex deficiencies. Processing line drawings: Freeman chain coding and geometric probability. Detecting structure in noisy pictures: Hough transforms, proximity graphs, relative neighborhood graphs, sphere-of-influence graphs, alpha-hulls, crusts and beta-skeletons. Neural networks: non-parametric learning and error-correction rules. Bayesian decision theory: discrete and continuous case, Gaussian density functions, Mahalanobis distance. Feature selection: independence of measurements, redundancy and synergism, information theory and feature evaluation criteria and feature selection search strategies. Measuring string similarity. Estimation of parameters: maximum likelihood and Bayesian estimation. Estimation of misclassification: generalization, substitution, leave-one-out and bootstrap. Nearest neighbor decision rules: editing, condensing and efficient nearest neighbor search. Cluster analysis and unsupervised learning: decision-directed learning, graph-theoretic methods, agglomerative and divisive methods. Using context in pattern recognition: Markov methods and the Viterbi algorithm. Support Vector Machines. Music Information Retrieval.

McGill University values academic integrity. Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offences under the Code of Student Conduct and Disciplinary Procedures (see www.mcgill.ca/integrityfor more information).