Lecture 1 (Wed. Jan. 5) : introduction, preview

Lecture 2 (Mon. Jan.10) : contour tracing, polygonal smoothing

• Intro to pattern recognition
• Contour tracing tutorial
• Contour tracing notes
• Midpoint smoothing introduction

Lecture 3 (Wed. Jan.12): "waterfall" smoothing of monotone chains, relative hulls.

• Waterfalls and monotone chains: Hysteresis tutorial
  You don't need to read the code.
• Relative hull tutorial
• Gzipped applet for relative hulls
• Geodesics in polygons
  Just read what is relevant to material mentioned in class.
• Polygon triangulations Web chapter (optional reading)
  Here you will find proofs of existence and algorithms.

• Extracting features using the hysteresis square
• Iterative endpoints fit : intro and applet.
• Applets for iterative endpoints fit and for midpoint smoothing .

• A paper (handed out at the tutorial on Jan.26) by Godfried Toussaint covers:
  • Iri-Imai algorithm
  • Faster version for parallel-strip distance (using convex hulls)
• Applet showing reduced DAG (first step of Iri-Imai algorithm).
• More info on graph methods . Focus on sections 1,2,5
• Faster computation of Iterative Endpoints Fit algorithm, using extra space. (notes given in overheads provided at top of page)
• Convex hulls:
  • Deciding if a point is inside a convex polygon, and computing new tangents
  • Computing the hull of a simple chain in linear time (optional, but you should know why this is desired) Just read the small section on Melkman's algorithm.
  • Rotating calipers tool , used often for convex hulls. For example, to merge two intersecting hulls in linear time. You should be familiar with the technique, but details are not required.

Lecture 6 (Mon. Jan. 24) : Skeletonization, Medial Axis

• Applet showing medial axis You can even modify your polygon and watch the medial axis change.
• Discussion on distances. Just understand the main ideas.
• Taxi-cab geometry
• Hilditch's algorithm
• Rosenfeld's algorithm
• Notes on skeletonization (mainly covers the two links above)
• Some notes on distance transforms: __1__ __2__
• More about the medial axis

• morops
• Godfried's intro to smoothing : smoothing binary images, and intro to material from previous lectures.

• Sobel operator
• Roberts operator
• Gaussian smoothing
• Lateral inhibition
• More notes on edge detection and lateral inhibition
• My notes that Matt used in the lecture

Lectures 9 and 10 (Mon. Feb. 7 and Wed. Feb. 9) : Data depth

• Intro to 2D medians and depth
• Algorithms and lower bounds for the computation of halfspace (Tukey) depth and simplicial depth (number of triangles).
• Lower bound for Oja depth (optional)
• No class notes available for this lecture. (blackboard used)

• Voronoi Applet ... and description of quadratic algorithm (with typos)
• The two O(nlogn) algorithms (using 3D convex hulls and sweep-line) are covered in the following two textbooks (each has a chapter dedicated to Voronoi diagrams):
  • Computational geometry : algorithms and applications, by M. de Berg [et al.]. QA448 D38 C65 1997 [Regular Loan] Schulich Science & Engineering
  • Computational geometry in C, by Joseph O'Rourke. QA448 D38 O76 1998 [Two Hour Loan] Schulich Science & Engineering Reserves
• An O(nlogn) time divide-and-conquer algorithm for computing the Voronoi diagram of a polygon (and also the medial axis) is in:
  D. T. Lee, "Medial axis transformation of a planar shape," IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-4, no. 4, pp. 363-369, July 1982.
  You can find it in the library Q327 I19 [Journal Loan] Schulich Science & Engineering.
• Euler's formula: V-E+F=2
  A corollary is that there is at most a linear number of edges and faces in a planar graph of n vertices.
• Lecture notes

• Guest lecture by Godfried Toussaint on rhythm . As usual, you are only responsible for the notes relevant to what was discussed in class.

Lecture 13 (Mon. Feb. 28): Bayesian decision theory

• Bayesian decision theory with Gaussian distributions
• No class notes for this lecture.

• Relative Neighborhood Graph and Gabriel Graph
• Sphere of Influence Graph. You can try this link too. I haven't checked out the applet yet.
• Alpha shapes and alpha hulls
• No class notes for this lecture. Blackboard used + projection of above applets.

• Erin's class notes

• Godfried's article on combining features and related web project.
• Nearest-neighbor decision rule (Note: there is a little mistake on the "probability of error" page, just before "And finally after some simplification". P(e|x) should be <= 1- the value on the right.
• Optional: if you want some more links to feature selection, see Godfried's collection of links. Section 11.5.1 contains the example with socks and eggplants (and much, much more).
• All overheads here

• Removing excess data that doesn't help
• Removing incorrect or undesired data (which will likely cause incorrect classification)
• Instance-based learning (editing that preserves classification of training data)
• A brief note on some options for evaluating your classifier: 1. train on some data, test on the rest, 2. Average of Leave-one-out, 3. Form K groups and take average of K "leave-one-group-out" tests.
• Occam's Razor
• Optional: Output-sensitive algorithms for computing nearest-neighbour decision boundaries (i.e. the useful Voronoi boundary): ps.gz
• Overheads are here

• Notes from class
• You can also check Erin's copy (link at top of this page)

• Notes from class
• You can also check Erin's copy (link at top of this page)
  Between the chopped off borders on her copies, and the white blob in the middle of my copies (from flash), you can figure things out I hope.

• Handout given in class. This is all you are responsible for.