# 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:
1. Introduce course
2. Introduction to pattern recognition via Optical Character Recognition
3. Bank check processing example
4. Transducers, digital pictures, pixels, preprocessing
5. Feature space
6. Classifiers and decisions regions
7. Midpoint smoothing
##### Problem Assignment #1 (due January 17)
1. Web: 1.1 - Notes on method of proof
2. Web: 1.2 - Introduction to pattern recognition
3. Web: 1.3 - Digital images
4. Web: 1.5 - Introduction to optical character recognition
5. Web: 1.9.1 - Grids, connectivity and contour tracing
6. Web: 2.8.1 - Midpoint smoothing (for polygons)
##### Suggested Play
1. Web: 1.3.1 - Java applet for scan converting polygons
2. Web: 2.8.1 - Java applet for midpoint smoothing

### Week 2-January 8 and 10

##### Lecture #2:
1. Discuss class projects
2. Grids (square, triangular and hexagonal)
3. Borders (4 and 8)
4. Connectivity (4 and 8)
5. Contour tracing:
1. Square tracing
2. Moore tracing
Lecture #3:
1. MIT reading machine for the blind
2. Smoothing:
1. Hysteresis smoothing
1. Handout: Digital Geometry by Rosenfeld and Melter
2. Web: 1.9.5 - Contour tracing tutorial
3. Web: - 1.9.2 - Contour tracing by radial sweep
4. Web: 1.11 - M.I.T. Reading machine for the blind
5. Web: 1.12 - What is hysteresis?
6. Web: 1.13 - Tutorial on hysteresis smoothing
7. Web: 2.8.2 - Tutorial on Ramer-Douglas-Peucker algorithm
8. Web: 2.9 - Pixel-based smoothing basics
9. Web: 2.8.4.1 - Relative convex hull smoothing tutorial of Steve Robbins
##### Suggested Play
1. Web: 1.13 - Hysteresis smoothing applet
2. Web: 2.8.2 - Applet for Ramer-Douglas-Peucker algorithm
3. Web: 2.8.4.2 - Relative convex hull applet of Steve Robbins

### Week 3-January 15 and 17

##### Lecture #4:
1. Pixel-based smoothing:
1. Regularization of functions
2. Salt-and-pepper noise
3. Local averaging
4. Median filtering
2. More Polygonal Smoothing:
1. Relative convex hull smoothing (minimum perimeter polygons)
2. Ramer-Douglas-Peucker algorithm (iterative endpoints fit)
Lecture #5:
1. More Polygonal Smoothing:
1. Graph-theoretic methods of Iri and Imai
2. Melkman-O'Rourke algorithm
2. Image Sharpening:
1. Caricature generation and morphing
2. Spatial differentiation
3. Distance and Minkowski metrics
##### Problem Assignment #2 (due January 31)
1. Handout - Polygonal curve approximation (Melkman-O'Rourke paper)
2. Web: 2.1 - Minkowski addition and subtraction
3. Web: 3.1.1 - Edge detection
4. Web: 3.1.5 - Roberts Cross Operator
5. Web: 3.2.1 - Sharpening, the Laplacian and lateral inhibition
6. Web: 3.2.2 - Eye and retina
7. Web: 3.2.3 and 3.2.4 - Mach bands and lateral inhibition
8. Web: 3.3.1 - The Laplacian in edge detection
##### Suggested Play
1. Web: 2.8.5.1 - Applet for Iri-Imai algorithm
2. Web: 2.1.1 - Applet for Minkowski operations
3. Web: 3.2.5 and 3.2.6 - Lateral inhibition applets
4. Web: 3.3.2 - Laplacian edge detector applet
5. Web: 3.3 - Caricature applet

### Week 4-January 22 and 24

##### Lecture #6:
1. Medial Axis:
1. Prairie-fire transformation
2. Skeletal pair
3. Quench velocity
1. Smoothing and sharpening with medial axis
2. Skeletons:
1. Hilditch's algorithm
##### Lecture #7:
1. Skeletons:
1. Rosenfeld's algorithm
2. Edge detection:
1. The Laplacian
1. Web: 5.1 - Distance
2. Web: 5.1.1 - Manhattan metric
3. Web: 5.1.2 - Tutorial on taxicab geometry
4. Web: 5.4 - Skeletons
5. Web: 5.4.1 - Hilditch's algorithm
6. Web: 5.4.2 - Rosenfeld's algorithm
7. Web: 5.5.1 - Morphological shape analysis (congruence of shapes)
8. Web: 5.5.2 - Medial axis tutorial
9. Web: 5.6 - Distance transforms
##### Suggested Play
1. Web: 5.1.2 - Applet for taxicab geometry
2. Web: 5.5.2 - Applet for medial axis grassfire algorithm

### Week 5-January 29 and 31

##### Lecture #8:
1. Lateral inhibition and neural networks
2. More medial axis:
1. Medial axis transform
2. Medial axis pruning for noise removal
3. Discriminant functions:
1. Linear
1. Threshold logic units
##### Problem Assignment #3 ( February 28)
1. Handout: Medial axis and skeletal pair
2. Handout: Mathematical foundations of learning machines
3. Web: 9.1 - Simple classifiers
4. Web: 9.4.4.1 - Real and artificial neurons
5. Web: 9.4.4.2 - Threshold logic units, perceptrons and learning rules
##### Suggested Play
1. Web: 5.12.1 - Applet for medial axis of points (Voronoi diagram) in the plane
2. Web: 5.12.2 - Applet for medial axis of points (Voronoi diagram) on the sphere
3. Web: 12.4.1 - Applet for Rosenblatt's perceptron learning algorithm

## Week 6 - February 5 and 7

### Week 7 - February 12 and 14

##### Lecture #12:
1. Minimum Euclidean distance classifier
2. Bayesan decision theory (general case)
1. Bayes rule
2. Bayes (optimal) probability of error
3. Bounds on Bayes error
1. Distance measures between probability distributions
2. The Bhattacharya coefficient
3. The Kolmogorov variational distance
##### Lecture #13:
2. Polynomial discriminant functions
3. The multivariate normal (Gaussian) probability density function
4. The divergence between probability distributions
5. The Mahalanobis distance
6. Bayes Discriminant functions for Gaussian densities:
1. Case #1 - Uncorrelated equal variance measurements
2. Case #2 - Equal class covariance matrices
3. Case #3 - General covariance matrices
1. Handout on Bayes decision theory (Chapter 2 of Duda and Hart)
2. Web: 10.1 - Erin McLeish's tutorial on Bayes decision theory for Gaussian densities
3. Web: 10.12.1 - Tutorial on Occam's razor
4. Web: 9.2 - Mahalanobis distance classifiers
5. Web: 9.3 - Learning from examples
Suggested Play
1. Web: 10.12.1 - Applet for Occam's razor in decision rules
2. Web: 10.3.3 - A Bayesian puzzle
3. Web: 10.3.4 - The three-door puzzle

### Week 9 - February 26 and 28

##### Lecture #16:
1. Loss matrices and minimum risk classification
2. The normal-form equation of linear discriminant functions with Gaussian densities
3. Feature extraction by moment invariants:
1. Moments of marginal distributions
2. Moments of area
3. Moments of perimeter
4. Affine transformations
##### Lecture #17:
1. Perceptrons:
1. Diameter-limited perceptrons
2. Order-limited perceptrons
3. Gamba perceptrons
4. Random perceptrons
5. Bounded perceptrons (finite memory)
2. Bayes decision theory in the discrete case
1. Binary features
2. Class-conditional independence
3. Kolmogorov variational distance
3. Independence, redundancy and synergism
1. Independence and uncorrelation of measurements
##### Problem Assignment #4 (due Monday, March 19)
1. Web: 10.3 - Basics of statistical pattern recognition
2. Web: 10.7.1 - Quadric surfaces
3. Web: 4.1 - Affine transformations
4. Web: 4.2 - Affine Geometry
5. Web: 4.3 - More on affine transformations
6. Web: 4.4 - Moment invariants
7. Web: 4.5 - Moments in pattern recognition
8. Web: 4.6 - Adam Ramadan's tutorial on moments in pattern recognition
9. Web: 11.1 - Independent and conditionally independent events
10. Web: 11.2 - Class-conditional and unconditional independence assumptions in pattern recognition
11. Web: 11.3 - Independence and uncorrelation for Gaussian distributions
##### Suggested Play
1. 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
1. Independence and uncorrelation of measurements
1. Characterization of independence in terms of expected values
2. The divergence for Gaussian distributions
1. Redundancy and synergism
3. Estimation of Parameters:
1. Maximum likelihood estimation
2. Properties of estimators
1. Robustness
2. Bias
3. Consistency
4. Recognizing structure in dot patterns:
1. Cluster analysis or unsupervised learning
2. Shape skeletons and proximity graphs
1. Minimum spanning tree
2. Relative neighborhood graph
3. Gabriel graph
4. Delaunay triangulations and Voronoi diagrams
##### Lecture #19:
1. Decision rules with estimated parameters
1. Robust estimators of location
1. Onion peeling
2. Oja median
3. Simplicial median
2. Image segmentation via clustering
3. Shape hulls
1. Gabriel hull
1. Alpha-hull and alpha-shape
2. Furthest-point Voronoi diagrams
3. Sphere-of-influence graph
1. Web: 11.2 - Class-conditional and unconditional independence assumptions in pattern recognition
2. Web: 11.3 - Independence and uncorrelation for Gaussian distributions
3. Web: 8.7.1 - The relative neighborhood graph
4. Web: 8.6.1 - A survey of proximity graphs
5. Web: 8.7.3.1 - Alpha-shape tutorial
##### Suggested Play
1. Web: 8.6.3 - Minumum spanning tree applet
2. Web: 8.6.4 - Delaunay triangulation and Voronoi diagram applet
3. Web: 8.7.3.1 - Alpha-shape applet
4. Web: 8.7.2 - Sphere-of-influence graph applet

### Week 11 - March 12 and 14

##### Lecture #20: HTML project due March 12
1. Introduction to nearest neighbor decision rules
2. Non-parametric estimation of probability of error from training data:
1. Plug-in estimators
2. Resubstitution
3. Holdout
4. Pi method
5. Leave-one-out method
6. Bootstrap methods
##### Lecture #21:
1. The problem of good generalization
1. Ocam's razor
2. Number of features
3. Number of parameters
4. Vapnik-Chervonenkis (VC) dimension
5. Support-vectors and support-vector machines
2. Nearest neighbor decision rules:
1. The Cover-Hart error bounds
2. Jensen's inequality
1. Handout: Annotated bibliography on estimation of misclassification
2. Web: 13.1.1 - Robust estimators of location (Tutorial by Greg Aloupis)
3. Web: 17.1 - Support-vector classifiers: a first look
4. Web: 17.2 - Vapnik-Chervonenkis dimension
5. Web: 14.1.1 - The nearest neighbor rule tutorial
##### Suggested Play
1. Web: 17.3 - Support-vector applet

### Week 12 - March 19 and 21

##### Lecture #22:
1. Nearest neighbor decision rules:
1. Choosing the value of k in k-nearest neighbor rules
2. Proximity graph nearest neighbor rules
2. Efficient implementation of nearest neighbor decision rules:
1. Searching nearest neighbors efficiently:
1. Voronoi diagram methods
1. Projection methods
2. Space-partition trees
1. Edited nearest neighbor rules for reduced storage requirements
1. Hart's condenced NN-rule
2. Optimal Voronoi editing
3. Proximity-graph-theoretic editing methods
##### Lecture #23:
1. Error-correction learning methods
2. The perceptron convergence theorem
1. Web: 14.1.1 - Nearest neighbor decision rule tutorial
2. Web: 14.1.4.1 - Jensen's inequality introduction
3. Web: 14.1.4.2 - Convexity and Jensen's inequality
4. Web: 14.2.1 - Searching nearest neighbors via projections
5. Web: 14.3.1 - Proximity graph methods for editing nearest neighbor decision rules
6. Web: 14.3.2 - Tutorial for proximity graph NN-rule editing
7. Handout - Error correction learning
8. Handout - Proof of perceptron convergence theorem
##### Suggested Play
1. Web: 14.1.1 - The nearest neighbor rule applet
2. Web: 14.1.3 - The k-NN decision rule applet
3. Web: 14.3.2 - Applets for proximity graph editing of NN-rules

### Week 14 - April 2 and 4

##### Lecture #26: Student Oral Presentations
1. Course Evaluations