Music Information Retrieval

"Without music life would be a mistake." - Friedrich Nietzsche

1. Introduction to Pattern Recognition and Image Processing

  1. Notes on Methods of Proof
  2. Image Processing Basic Operators
  3. Optical character recognition (brief introduction)
    1. Magnetic Ink Character Recognition Fonts
    2. Bank Check Recognition System with E-13B Font (PostScript - 70 pages)
  4. Tessellation Resources
  5. Tessellation Tutorials
  6. Grids:
    1. Grids, connectivity and contour tracing (PostScript)
    2. Contour Tracing Algorithms: Tutorial by Abeer Ghuneim
  7. M.I.T. reading machine for the blind
  8. What is hysteresis?
  9. Zacharia Nkgau's tutorial on hysteresis smoothing of monotonic polygons (with interactive Java applet)
  10. Image Segmentation:
    1. Image segmentation tutorial

2. Smoothing, Approximation, Data-Compression and Fitting

  1. Minkowski addition and subtraction (dilation and erosion)
  2. Gaussian smoothing
  3. More about Carl Friedrich Gauss
  4. Polygonal Approximation:
    1. Midpoint smoothing
      1. Tutorial and Interactive Java applet by Ziad Hafed and Diana Hernandez
    2. Ramer-Douglas-Peucker algorithm (Iterative End-Points Fit):
      1. Guirlyn Olivar's interactive Java applet
    3. Relative Convex Hull Smoothing:
      1. Computing the Relative Convex Hull and other geodesic properties in a polygon (PostScript)
  5. Tutorial on polygonal approximation (Iri-Imai algorithm, Melkman-O'Rourke algorithm)

3. Differentiation, Sharpening, Enhancement, Caricatures and Shape Morphing

  1. Differentiation and Edge Detection:
    1. The Sobel operator
    2. Edge detection tutorial (Wolfram Research)
    3. Roberts cross operator
      1. More on the Roberts operator
  2. Enhancement and Lateral Inhibition:
    1. The retina and lateral inhibition
    2. Limulus-the horseshoe crab
  3. The Laplacian:
    1. The Laplacian in edge detection
    2. Laplacian edge detector applet
  4. Fundamentals of Visual Perception:
    1. The Joy of Visual Perception
  5. Shape Morphing:
    1. Mark Grundland's morphing bibliography

4. Measurement of Shape

  1. Affine Geometry
  2. More on affine transformations
  3. Affine and Other Geometric Transformations
  4. Fourier Descriptors:
    1. Fourier synthesis (Java applet)

5. Distance, Medial Axis Transforms and Skeletons

  1. What is Distance?
    1. Manhattan Metric (Taxicab Geometry)
    2. Pascal Tesson's tutorial on taxicab geometry (with Java applet)
  2. Minkowski metrics
    1. More about Hermann Minkowski
  3. Distance between sets:
    1. Distance between strings
    2. The Hausdorff Distance
    3. Normand Gregoire & Mikael Bouillot's Tutorial on the Hausdorff distance and its applications (with interactive Java applet)
    4. Dynamic programming algorithm for edit-distance between strings
    5. Discrete Fourier Transforms made very easy!
  4. Skeletons
    1. Hilditch's algorithm
      1. Danielle Azar's tutorial
    2. Skeletonization software
  5. Medial Axis of Polygonal Sets (prairie-fire transformation)
    1. Martin Held's Fire Propagation Algorithm
  6. Medial axis in 3D with applications
  7. Medial axis software
  8. Medial Axis of Pont Sets

6. Shape Decomposition, Geometric and Topological Features

  1. Polygon Decomposition:
    1. Star-shaped decompositions (compressed PostScript:
  2. Convex hulls, concavities and enclosures:
    1. Interactive Java convex hull algorithms in 2D
    2. Clarkson's code for 2D convex hulls
  3. Geometric Feature Extraction Methods

7. Processing Line Drawings

  1. Basics of Freeman Chain Coding (PostScript)
    1. More about Herbert Freeman
    2. Square, circular, and grid-intersect quantization
    3. Probability of obtaining diagonal elements
    4. Geometric Probability
    5. Bertrand's paradox.
    6. More on Bertrand's paradox (with Java applet simulations)
    7. More about Joseph Bertrand
    8. Difference encoding & chain correlation functions
    9. Minkowski metric quantization

8. Detection of Structure in Noisy Pictures and Dot Patterns

  1. What is a line?
  2. Point-to-curve transformations (Hough transform)
  3. Point-Line duality
    1. Interactive Java Demo
  4. Hough Transforms:
    1. Hough Transform tutorial
    2. Improving the Hough Transform (paper by M. Cohen and G. Toussaint)
      1. Line and circle detection
      2. Hypothesis testing approach
      3. Maximum-entropy quantization
    3. Hough Transform home page (and software)
    4. Hough Transform publications
    5. More Hough Transform code
    6. Interactive histogram with Java applet
    7. Another nice tutorial on the Hough transform
  5. GraphTheory:
    1. Graphs
    2. Graph theory terminology
    3. Basic Graph Theory
  6. Proximity graphs:
    1. A Survey of Proximity Graphs
    2. Minimal spanning tree (MST) of a dot pattern
    3. MST interactive Java applet
    4. Delaunay Triangulations and Voronoi diagrams
    5. More about Boris Delaunay
  7. The shape of a set of points:
    1. The relative neighbourhood graph of a finite planar set
    2. Sphere-of-influence graphs and applet
    3. Alpha shapes
      1. François Bélair's Tutorial on Alpha Shapes (with interactive Java applet and a super-duper automated guided-tour demo)
      2. Introduction to alpha shapes
      3. Gallery of alpha shapes
      4. Code for computing alpha-shapes (and convex hulls)
    4. Beta skeletons:
      1. Xiaoming Zhong's Tutorial on Beta Skeletons (with interactive Java applet)
    5. Voronoi Diagram Based Methods:
      1. The Crust of  set of points

9. Simple Classifiers, Neural Networks, and Machine Learning

  1. Simple Classifiers
    1. Template matching
    2. Minimum-distance classifiers
      1. Minkowski metric classifiers
    3. Inner products
    4. Linear discriminant functions
    5. Decision boundaries
  2. Mahalanobis Distance Classifiers
  3. Learning from Examples
  4. Neural Networks:
    1. A Brief Tour of the Brain
    2. Introduction to Neural Networks
    3. Another Introduction to Neural Networks
    4. Dr. Gurney's course on neural networks
      1. Real and artificial neurons
      2. Threshold logic units, perceptrons and simple learning rules
    5. A brief history of Neural Networks
    6. Neural Network Basics (FAQ's)
    7. Formal neurons, linear machines & perceptrons
    8. Separability:
      1. Linear separability
      2. Separating points with circles
    9. Pierre Lang's Neural Network for Character Recognition (with interactive Java applet that recognizes the characters you draw on the screen!)

10. Bayesian Decision Theory

  1. Bayesian Decision Theory with Gaussian Distributions - A tutorial by Erin Mcleish
    1. Bayes Theory: Discrete Features
  2. Introductory Statistics Course
  3. Another Introduction to Probability and Statistics
    1. Bayes' Theorem
    2. More about Thomas Bayes
    3. A Bayesian Puzzle
    4. The three-door puzzle (Monty Hall problem)
  4. Basics of Statistical Pattern Recognition (by Richard O. Duda)
  5. More about Richard Duda
  6. Minimum risk classification
  7. Minimum error classification
  8. Discriminant functions (linear, quadratic, polynomial)
    1. Quadric surfaces
    2. Geometry formulas and facts
    3. Discriminant analysis code in MATLAB
  9. The bivariate Gaussian probability density function
  10. Multivariate statistics
  11. Lecture Notes on Statistical Pattern Recognition
  12. Occam's Razor:
    1. Jacob Eliosoff's Tutorial on Occam's Razor in Decision Rules (with JAVA applet)
    2. Occam's Razor
    3. Occam's Razor and Machine Learning
    4. Simplicity, Cross-Validation and Occam's Razor
    5. More about William of Occam

11. Feature Selection: Independence of Measurements, Redundancy, and Synergism

  1. Independent and conditionally independent events
  2. Class-conditional and unconditional independence assumptions in pattern recognition (Tutorial by Simon-Pierre Desrosiers)
  3. Independence, uncorrelation and Gaussian distributions (PostScript notes by Julio Peixoto)
  4. Information theory:
    1. A primer on information theory (PostScipt)
    2. Basic properties of Shannon's entropy and mutual information
    3. Relative entropy and mutual information
    4. From Euclid to entropy (PostScript)
    5. Shannon's equivocation and the Fano bound
    6. More about Claude Shannon
    7. The Claude Shannon Home Page
    8. Calculating Information and Complexity
  5. Feature Selection:
    1. Independence, Redundancy and Synergism: A Tutorial by Irina Kezele
    2. Feature Selection: Evaluation, Application, and Small Sample Performance (PostScipt)
    3. Toward Optimal Feature Selection (PostScipt)
    4. Dimensiobality Reduction: Francois Labelle's tutorial (with interactive Java applets)
    5. Simon Plain's tutorial on feature selection (with interactive Java applets)
    6. Feature evaluation criteria:
      1. Kullback-Liebler information
      2. The Divergence
      3. The Affinity
      4. The Mutual-Information criterion (PDF file)
      5. Discrimination information and Kolmogorov variational distance (PDF file)
      6. The Fisher Information
        1. More about Sir Ronald Fisher
        2. Pictures of Fisher
    7. Feature selection methods (Richard Duda's course notes)
    8. A survey of feature selection methods
    9. The best K independent measurements are not the K best (PDF file)
    10. Models of spatial dependence between features
      1. Space-filling curves (Hilbert and Peano)
      2. Sierpinski curves

12. Non-parametric Machine Learning

  1. General Learning Resources
  2. Perceptrons:
    1. Simple perceptrons and the exclusive OR problem
    2. Applet for Perceptron learning in the exclusive OR problem
  3. Non-parametric training of linear machines (Nilsson's book - Chapter 4)
  4. Error-correction procedures
    1. Rosenblatt's Perceptron Learning Algorithm (an interactive Java applet)
  5. The fundamental learning theorem
  6. Multi-layer networks
  7. Competitive Learning:
    1. Applet illustrating many competitive learning algorithms

13. Estimation of Density Functions, Parameters and Classifier Performance

  1. Estimation of Parameters:
    1. Robust estimators of location (Tutorial by Greg Aloupis)
    2. Bias and variance of estimators
    3. Maximum likelihood estimation
  2. Density Estimation:
    1. Kernel density estimation applet
  3. Estimators and Bias (Wolfram Research)
  4. Dimensionality and sample size
  5. Estimation of the probability of misclassification
  6. Estimation of misclassification before 1974
    1. Resubstitution
    2. Holdout
    3. Data Shuffling
    4. Leave-One-Out
    5. Bootstrap Methods
  7. Ensembles of Classifiers
  8. Boosting
  9. Comparing the performance of several classifiers (the pitfalls)

14. Nearest Neighbor Decision Rules and Instance-Based Learning

  1. Nearest Neighbor Decision Rules:
    1. The nearest neighbor rule: a tutorial
    2. The nearest neighbor rule with a reject option
    3. The k-nearest neighbor rule applet
    4. The Cover-Hart bounds and Jensen's inequality:
      1. Convexity and Jensen's inequality (proof by induction)
      2. A Visual Explanation of Jensen's Inequality
      3. Convexity and Jensen's Inequality
      4. A Simple Proof of the Jensen-Steffensen Inequality
      5. More about Johan Ludwig William Valdemar Jensen
      6. More about Thomas Cover
      7. More about Peter Hart
  2. Efficient search methods for nearest neighbors:
    1. The projection method for searching nearest neighbors (algorithm of Friedman, Baskett and Shustek)
      1. More about Jerome Friedman
    2. Nearest neighbor searching papers
    3. Approximate nearest neighbor searching
  3. Editing nearest neighbor rules to reduce storage:
    1. Reducing the size of training sets with proximity graphs (PostScript)
    2. Sergei Savchenko's tutorial on nearest neighbor condensing rules
    3. Chris Cocosco's tutorial on nearest neighbor editing rules for smoothing decision rules
    4. Nearest neighbor editing and condensing tools (PostScript)
  4. Nearest neighbor computation software
  5. Bibliography on Nearest Neighbor Methods

15. Using Contextual Information in Pattern Recognition

  1. Using Context in Visual Perception
  2. Infinite Monkey Theorem
  3. Introduction to Markov Processes
  4. More about Andrei Markov
  5. Forward dynamic programming and the Viterbi algorithm:
    1. A tutorial on the Viterbi algorithm
    2. Viterbi algorithm demo for sentence recognition
  6. Combined bottom-up and top-down algorithms

16. Unsupervised Machine Learning and Cluster Analysis

  1. Unsupervised Learning:
    1. Decision-directed learning (the K-means algorithms)
    2. K-Means Interactive Java Applet by Laurent Bonnefille and Nicolas Didier.
  2. Graph-theoretic methods:
    1. Minimal spanning tree methods
    2. Tutorial and Java applet by Mike Soss and Chrislain Razafimahefa
  3. Hierarchical clustering:
    1. Pascal Poupart's tutorial with interactive Java applet
    2. Phylogenetic Trees (A Tutorial)
    3. Clustering software on the Web
    4. Cluster Analysis: What is it? (Fantastic tutorial!)
    5. Clustering Calculator

17. Support Vector Machines

    1. Support Vector Classifiers: A First Look
    2. Tutorial on Support Vector Machines and Vapnik-Chervonenkis (VC) Dimension for Pattern Recognition (PostScript)
    3. Support Vector Applet and References

18. Music Information Retrieval

    1. Measures of Rhythmic Similarity
    2. Measures of Melodic Similarity
    3. Features for Music Classification
    4. Phylogenetic Analysis Tools