CS-644B 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 1-January 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 2-January 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 Ramer-Douglas-Peucker algorithm
-
Web: 2.9 - Pixel-based 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 Ramer-Douglas-Peucker algorithm
-
Web: 2.8.4.2 - Relative convex hull applet of Steve Robbins
Week 3-January 15 and
17
Lecture #4:
-
Pixel-based smoothing:
-
Regularization of functions
-
Salt-and-pepper noise
-
Local averaging
-
Median filtering
-
More Polygonal Smoothing:
-
Relative convex hull smoothing (minimum perimeter polygons)
-
Ramer-Douglas-Peucker algorithm (iterative endpoints fit)
Lecture #5:
-
More Polygonal Smoothing:
-
Graph-theoretic methods of Iri and Imai
-
Melkman-O'Rourke algorithm
-
Image Sharpening:
-
Caricature generation and morphing
-
Spatial differentiation
-
Distance and Minkowski metrics
Problem Assignment #2 (due January 31)
-
Ramer-Douglas-Peucker algorithm
-
Analog medial axis
-
Skeletons
-
Minkowski metrics
Reading Assignment
-
Handout - Polygonal curve approximation (Melkman-O'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 Iri-Imai 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 4-January 22 and
24
Lecture #6:
-
Medial Axis:
-
Prairie-fire 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 5-January 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 three-door 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 normal-form 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:
-
Diameter-limited perceptrons
-
Order-limited perceptrons
-
Gamba perceptrons
-
Random perceptrons
-
Bounded perceptrons (finite memory)
-
Bayes decision theory in the discrete case
-
Binary features
-
Class-conditional 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 - Class-conditional 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: 3-hour 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
-
Alpha-hull and alpha-shape
-
Furthest-point Voronoi diagrams
-
Sphere-of-influence graph
Reading Assignment
-
Web: 11.2 - Class-conditional 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 - Alpha-shape 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 - Alpha-shape applet
-
Web: 8.7.2 - Sphere-of-influence graph applet
Week 11 - March 12
and 14
Lecture #20:
HTML
project due March 12
-
Introduction to nearest neighbor decision rules
-
Non-parametric estimation of probability of error
from training data:
-
Plug-in estimators
-
Resubstitution
-
Holdout
-
Pi method
-
Leave-one-out method
-
Bootstrap methods
Lecture #21:
-
The problem of good generalization
-
Ocam's razor
-
Number of features
-
Number of parameters
-
Vapnik-Chervonenkis (VC) dimension
-
Support-vectors and support-vector machines
-
Nearest neighbor decision rules:
-
The Cover-Hart 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 - Support-vector classifiers: a first look
-
Web: 17.2 - Vapnik-Chervonenkis dimension
-
Web: 14.1.1 - The nearest neighbor rule tutorial
Suggested Play
-
Web: 17.3 - Support-vector applet
Week 12 - March 19
and 21
Lecture #22:
-
Nearest neighbor decision rules:
-
Choosing the value of k in k-nearest neighbor rules
-
Proximity graph nearest neighbor rules
-
Efficient implementation of nearest neighbor decision
rules:
-
Searching nearest neighbors efficiently:
-
Voronoi diagram methods
-
Projection methods
-
Space-partition trees
-
Edited nearest neighbor rules for reduced storage
requirements
-
Hart's condenced NN-rule
-
Optimal Voronoi editing
-
Proximity-graph-theoretic editing methods
Problem Assignment #5
-
Maximum likelihood
estimation of parameters
-
The 1-Nearest-Neighbor
and Bayes error rates
-
The 2-Nearest-Neighbor
decision rule
-
The k-Nearest-Neighbor
decision rule
-
The j-th Nearest-Neighbor
decision rule
Lecture #23:
-
Error-correction 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 NN-rule
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 k-NN decision rule applet
-
Web: 14.3.2 - Applets for proximity graph editing of NN-rules
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