CS644B Pattern Recognition
Lecture Descriptions, Exams, Homework and Play
Week: 1
 2  3  4  5
 6  7  8  9
 10 
11  12 
13  14
 15
Week 1January 3
Lecture #1:

Introduce course

Introduction to pattern recognition via Optical Character Recognition

Bank check processing example

Transducers, digital pictures, pixels, preprocessing

Feature space

Classifiers and decisions regions

Midpoint smoothing
Problem Assignment #1 (due January 17)

Connecteness and contour tracing

Hysteresis smoothing

Midpoint smoothing
Reading Assignment

Web: 1.1  Notes on method of proof

Web: 1.2  Introduction to pattern recognition

Web: 1.3  Digital images

Web: 1.5  Introduction to optical character recognition

Web: 1.9.1  Grids, connectivity and contour tracing

Web: 2.8.1  Midpoint smoothing (for polygons)
Suggested Play

Web: 1.3.1  Java applet for scan converting polygons

Web: 2.8.1  Java applet for midpoint smoothing
Week 2January 8 and
10
Lecture #2:

Discuss class projects

Grids (square, triangular and hexagonal)

Borders (4 and 8)

Connectivity (4 and 8)

Contour tracing:

Square tracing

Moore tracing
Lecture #3:

MIT reading machine for the blind

Smoothing:

Hysteresis smoothing
Reading Assignment

Handout: Digital Geometry by Rosenfeld and Melter

Web: 1.9.5  Contour tracing tutorial

Web:  1.9.2  Contour tracing by radial sweep

Web: 1.11  M.I.T. Reading machine for the blind

Web: 1.12  What is hysteresis?

Web: 1.13  Tutorial on hysteresis smoothing

Web: 2.8.2  Tutorial on RamerDouglasPeucker algorithm

Web: 2.9  Pixelbased smoothing basics

Web: 2.8.4.1  Relative convex hull smoothing tutorial of Steve Robbins
Suggested Play

Web: 1.13  Hysteresis smoothing applet

Web: 2.8.2  Applet for RamerDouglasPeucker algorithm

Web: 2.8.4.2  Relative convex hull applet of Steve Robbins
Week 3January 15 and
17
Lecture #4:

Pixelbased smoothing:

Regularization of functions

Saltandpepper noise

Local averaging

Median filtering

More Polygonal Smoothing:

Relative convex hull smoothing (minimum perimeter polygons)

RamerDouglasPeucker algorithm (iterative endpoints fit)
Lecture #5:

More Polygonal Smoothing:

Graphtheoretic methods of Iri and Imai

MelkmanO'Rourke algorithm

Image Sharpening:

Caricature generation and morphing

Spatial differentiation

Distance and Minkowski metrics
Problem Assignment #2 (due January 31)

RamerDouglasPeucker algorithm

Analog medial axis

Skeletons

Minkowski metrics
Reading Assignment

Handout  Polygonal curve approximation (MelkmanO'Rourke paper)

Web: 2.1  Minkowski addition and subtraction

Web: 3.1.1  Edge detection

Web: 3.1.5  Roberts Cross Operator

Web: 3.2.1  Sharpening, the Laplacian and lateral inhibition

Web: 3.2.2  Eye and retina

Web: 3.2.3 and 3.2.4  Mach bands and lateral inhibition

Web: 3.3.1  The Laplacian in edge detection
Suggested Play

Web: 2.8.5.1  Applet for IriImai algorithm

Web: 2.1.1  Applet for Minkowski operations

Web: 3.2.5 and 3.2.6  Lateral inhibition applets

Web: 3.3.2  Laplacian edge detector applet

Web: 3.3  Caricature applet
Week 4January 22 and
24
Lecture #6:

Medial Axis:

Prairiefire transformation

Skeletal pair

Quench velocity

Smoothing and sharpening with medial axis

Skeletons:

Hilditch's algorithm
Lecture #7:

Skeletons:

Rosenfeld's algorithm

Edge detection:

The Laplacian

Unsharp masking
Reading Assignment

Web: 5.1  Distance

Web: 5.1.1  Manhattan metric

Web: 5.1.2  Tutorial on taxicab geometry

Web: 5.4  Skeletons

Web: 5.4.1  Hilditch's algorithm

Web: 5.4.2  Rosenfeld's algorithm

Web: 5.5.1  Morphological shape analysis (congruence of shapes)

Web: 5.5.2  Medial axis tutorial

Web: 5.6  Distance transforms
Suggested Play

Web: 5.1.2  Applet for taxicab geometry

Web: 5.5.2  Applet for medial axis grassfire algorithm
Week 5January 29 and
31
Lecture #8:

Lateral inhibition and neural networks

More medial axis:

Medial axis transform

Medial axis pruning for noise removal

Discriminant functions:

Linear

Threshold logic units
Lecture #9: Tutorial on Assignments
Problems
Problem Assignment #3 ( February 28)

Morphological congruence
of shapes

Discriminant functions

Geometric probability

The Bhattacharya
coefficient
Reading Assignment

Handout: Medial axis and skeletal pair

Handout: Mathematical foundations of learning machines

Web: 9.1  Simple classifiers

Web: 9.4.4.1  Real and artificial neurons

Web: 9.4.4.2  Threshold logic units, perceptrons and learning rules
Suggested Play

Web: 5.12.1  Applet for medial axis of points (Voronoi diagram) in the
plane

Web: 5.12.2  Applet for medial axis of points (Voronoi diagram) on the
sphere

Web: 12.4.1  Applet for Rosenblatt's perceptron learning algorithm
Week 6  February 5 and 7
Lecture #10: First
Midterm Exam
Lecture #11: To
be rescheduled
Reading Assignment
Suggested Play
Week 7  February 12
and 14
Lecture #12:

Minimum Euclidean distance classifier

Bayesan decision theory (general case)

Bayes rule

Bayes (optimal) probability of error

Bounds on Bayes error

Distance measures between probability distributions

The Bhattacharya coefficient

The Kolmogorov variational distance
Lecture #13:

Quadratic discriminant functions

Quadric processors

Polynomial discriminant functions

The multivariate normal (Gaussian) probability density
function

The divergence between probability distributions

The Mahalanobis distance

Bayes Discriminant functions for Gaussian densities:

Case #1  Uncorrelated equal variance measurements

Case #2  Equal class covariance matrices

Case #3  General covariance matrices
Reading Assignment

Handout on Bayes decision theory (Chapter 2 of Duda and Hart)

Web: 10.1  Erin McLeish's tutorial on Bayes decision theory for Gaussian
densities

Web: 10.12.1  Tutorial on Occam's razor

Web: 9.2  Mahalanobis distance classifiers

Web: 9.3  Learning from examples
Suggested Play

Web: 10.12.1  Applet for Occam's razor in decision
rules

Web: 10.3.3  A Bayesian puzzle

Web: 10.3.4  The threedoor puzzle
Week 8  February 19 and 21  Study
Break
Lecture #14:
No class
Lecture #15:
No
class
Week 9  February 26
and 28
Lecture #16:

Loss matrices and minimum risk classification

The normalform equation of linear discriminant functions
with Gaussian densities

Feature extraction by moment invariants:

Moments of marginal distributions

Moments of area

Moments of perimeter

Affine transformations
Lecture #17:

Perceptrons:

Diameterlimited perceptrons

Orderlimited perceptrons

Gamba perceptrons

Random perceptrons

Bounded perceptrons (finite memory)

Bayes decision theory in the discrete case

Binary features

Classconditional independence

Kolmogorov variational distance

Independence, redundancy and synergism

Independence and uncorrelation of measurements
Problem Assignment #4 (due Monday, March 19)

Diameter limited
perceptrons

Moment invariants

Independence and
uncorrelation of Gaussian features

Loss matrices and
minimum risk classification
Reading Assignment

Web: 10.3  Basics of statistical pattern recognition

Web: 10.7.1  Quadric surfaces

Web: 4.1  Affine transformations

Web: 4.2  Affine Geometry

Web: 4.3  More on affine transformations

Web: 4.4  Moment invariants

Web: 4.5  Moments in pattern recognition

Web: 4.6  Adam Ramadan's tutorial on moments in
pattern recognition

Web: 11.1  Independent and conditionally independent
events

Web: 11.2  Classconditional and unconditional independence
assumptions in pattern recognition

Web: 11.3  Independence and uncorrelation for Gaussian
distributions
Suggested Play

Web: 10.1  Erin McLeish's applet on Bayes decision theory for Gaussian
densities
Week 10  March 5
and 7
Lecture #18: 3hour lecture

Independence and uncorrelation of measurements

Characterization of independence in terms of expected
values

The divergence for Gaussian distributions

Redundancy and synergism

Estimation of Parameters:

Maximum likelihood estimation

Properties of estimators

Robustness

Bias

Consistency

Recognizing structure in dot patterns:

Cluster analysis or unsupervised learning

Shape skeletons and proximity graphs

Minimum spanning tree

Relative neighborhood graph

Gabriel graph

Delaunay triangulations and Voronoi diagrams
Lecture #19:

Decision rules with estimated parameters

Robust estimators of location

Onion peeling

Oja median

Simplicial median

Image segmentation via clustering

Shape hulls

Gabriel hull

Alphahull and alphashape

Furthestpoint Voronoi diagrams

Sphereofinfluence graph
Reading Assignment

Web: 11.2  Classconditional and unconditional independence
assumptions in pattern recognition

Web: 11.3  Independence and uncorrelation for Gaussian
distributions

Web: 8.7.1  The relative neighborhood graph

Web: 8.6.1  A survey of proximity graphs

Web: 8.7.3.1  Alphashape tutorial
Suggested Play

Web: 8.6.3  Minumum spanning tree applet

Web: 8.6.4  Delaunay triangulation and Voronoi diagram applet

Web: 8.7.3.1  Alphashape applet

Web: 8.7.2  Sphereofinfluence graph applet
Week 11  March 12
and 14
Lecture #20:
HTML
project due March 12

Introduction to nearest neighbor decision rules

Nonparametric estimation of probability of error
from training data:

Plugin estimators

Resubstitution

Holdout

Pi method

Leaveoneout method

Bootstrap methods
Lecture #21:

The problem of good generalization

Ocam's razor

Number of features

Number of parameters

VapnikChervonenkis (VC) dimension

Supportvectors and supportvector machines

Nearest neighbor decision rules:

The CoverHart error bounds

Jensen's inequality
Reading Assignment

Handout: Annotated bibliography on estimation of
misclassification

Web: 13.1.1  Robust estimators of location (Tutorial
by Greg Aloupis)

Web: 17.1  Supportvector classifiers: a first look

Web: 17.2  VapnikChervonenkis dimension

Web: 14.1.1  The nearest neighbor rule tutorial
Suggested Play

Web: 17.3  Supportvector applet
Week 12  March 19
and 21
Lecture #22:

Nearest neighbor decision rules:

Choosing the value of k in knearest neighbor rules

Proximity graph nearest neighbor rules

Efficient implementation of nearest neighbor decision
rules:

Searching nearest neighbors efficiently:

Voronoi diagram methods

Projection methods

Spacepartition trees

Edited nearest neighbor rules for reduced storage
requirements

Hart's condenced NNrule

Optimal Voronoi editing

Proximitygraphtheoretic editing methods
Problem Assignment #5

Maximum likelihood
estimation of parameters

The 1NearestNeighbor
and Bayes error rates

The 2NearestNeighbor
decision rule

The kNearestNeighbor
decision rule

The jth NearestNeighbor
decision rule
Lecture #23:

Errorcorrection learning methods

The perceptron convergence theorem
Reading Assignment

Web: 14.1.1  Nearest neighbor decision rule tutorial

Web: 14.1.4.1  Jensen's inequality introduction

Web: 14.1.4.2  Convexity and Jensen's inequality

Web: 14.2.1  Searching nearest neighbors via projections

Web: 14.3.1  Proximity graph methods for editing
nearest neighbor decision rules

Web: 14.3.2  Tutorial for proximity graph NNrule
editing

Handout  Error correction learning

Handout  Proof of perceptron convergence theorem
Suggested Play

Web: 14.1.1  The nearest neighbor rule applet

Web: 14.1.3  The kNN decision rule applet

Web: 14.3.2  Applets for proximity graph editing of NNrules
Week 13  March 26
and 28
Lecture #24:
2nd
Midterm Exam
Lecture #25:
Student
Oral Presentations
Week 14  April 2
and 4
Lecture #26:
Student
Oral Presentations

Course Evaluations
Lecture #27: Student
Oral Presentations
Week 15  April 9
Lecture #28: Student
Oral Presentations