Music Information Retrieval
"Without music life would be a mistake."
- Friedrich Nietzsche
1. Introduction to Pattern Recognition and Image Processing
Notes on Methods of Proof
Image Processing Basic Operators
Optical character recognition (brief introduction)
Magnetic Ink Character Recognition Fonts
Bank Check Recognition System with E-13B Font (PostScript - 70 pages)
Tessellation Resources
Tessellation Tutorials
Grids:
Grids, connectivity and contour tracing
(PostScript)
Contour Tracing Algorithms: Tutorial by Abeer Ghuneim
M.I.T. reading machine for the blind
What is
hysteresis
?
Zacharia Nkgau's tutorial on hysteresis smoothing of monotonic polygons
(with interactive Java applet)
Image Segmentation:
Image segmentation tutorial
2. Smoothing, Approximation, Data-Compression and Fitting
Minkowski addition and subtraction (dilation and erosion)
Gaussian smoothing
More about
Carl Friedrich Gauss
Polygonal Approximation:
Midpoint smoothing
Tutorial and Interactive Java applet by Ziad Hafed and Diana Hernandez
Ramer-Douglas-Peucker algorithm (Iterative End-Points Fit):
Guirlyn Olivar's interactive Java applet
Relative Convex Hull Smoothing:
Computing the Relative Convex Hull and other geodesic properties in a polygon (PostScript)
Tutorial on polygonal approximation (Iri-Imai algorithm, Melkman-O'Rourke algorithm)
3. Differentiation, Sharpening, Enhancement, Caricatures and Shape Morphing
Differentiation and Edge Detection:
The Sobel operator
Edge detection tutorial (Wolfram Research)
Roberts cross operator
More on the Roberts operator
Enhancement and Lateral Inhibition:
The retina and lateral inhibition
Limulus-the horseshoe crab
The Laplacian:
The Laplacian in edge detection
Laplacian edge detector applet
Fundamentals of Visual Perception:
The Joy of Visual Perception
Shape Morphing:
Mark Grundland's morphing bibliography
4. Measurement of Shape
Affine Geometry
More on affine transformations
Affine and Other Geometric Transformations
Fourier Descriptors:
Fourier synthesis (Java applet)
5. Distance, Medial Axis Transforms and Skeletons
What is Distance?
Manhattan Metric (Taxicab Geometry)
Pascal Tesson's tutorial on taxicab geometry
(with Java applet)
Minkowski metrics
More about
Hermann Minkowski
Distance between sets:
Distance between strings
The Hausdorff Distance
Normand Gregoire & Mikael Bouillot's Tutorial on the Hausdorff distance and its applications
(with interactive Java applet)
Dynamic programming algorithm for edit-distance between strings
Discrete Fourier Transforms made very easy!
Skeletons
Hilditch's algorithm
Danielle Azar's tutorial
Skeletonization software
Medial Axis of Polygonal Sets
(prairie-fire transformation)
Martin Held's Fire Propagation Algorithm
Medial axis in 3D with applications
Medial axis software
Medial Axis of Pont Sets
6. Shape Decomposition, Geometric and Topological Features
Polygon Decomposition:
Star-shaped decompositions (compressed PostScript: star.ps.gz)
Convex hulls, concavities and enclosures:
Interactive Java convex hull algorithms in 2D
Clarkson's code for 2D convex hulls
Geometric Feature Extraction Methods
7. Processing Line Drawings
Basics of Freeman Chain Coding
(PostScript)
More about Herbert Freeman
Square, circular, and grid-intersect quantization
Probability of obtaining diagonal elements
Geometric Probability
Bertrand's paradox.
More on Bertrand's paradox
(with Java applet simulations)
More about
Joseph Bertrand
Difference encoding & chain correlation functions
Minkowski metric quantization
8. Detection of Structure in Noisy Pictures and Dot Patterns
What is a line?
Point-to-curve transformations (Hough transform)
Point-Line duality
Interactive Java Demo
Hough Transforms:
Hough Transform tutorial
Improving the Hough Transform (paper by M. Cohen and G. Toussaint)
Line and circle detection
Hypothesis testing approach
Maximum-entropy quantization
Hough Transform home page
(and software)
Hough Transform publications
More Hough Transform code
Interactive histogram with Java applet
Another nice tutorial on the Hough transform
GraphTheory:
Graphs
Graph theory terminology
Basic Graph Theory
Proximity graphs:
A Survey of Proximity Graphs
Minimal spanning tree (MST) of a dot pattern
MST interactive Java applet
Delaunay Triangulations and Voronoi diagrams
More about
Boris Delaunay
The shape of a set of points:
The relative neighbourhood graph of a finite planar set
Sphere-of-influence graphs and applet
Alpha shapes
François Bélair's Tutorial on Alpha Shapes
(with interactive Java applet and a super-duper automated guided-tour demo)
Introduction to alpha shapes
Gallery of alpha shapes
Code for computing alpha-shapes (and convex hulls)
Beta skeletons:
Xiaoming Zhong's Tutorial on Beta Skeletons
(with interactive Java applet)
Voronoi Diagram Based Methods:
The Crust of set of points
9. Simple Classifiers, Neural Networks, and Machine Learning
Simple Classifiers
Template matching
Minimum-distance classifiers
Minkowski metric classifiers
Inner products
Linear discriminant functions
Decision boundaries
Mahalanobis Distance Classifiers
Learning from Examples
Neural Networks:
A Brief Tour of the Brain
Introduction to Neural Networks
Another Introduction to Neural Networks
Dr. Gurney's course on neural networks
Real and artificial neurons
Threshold logic units, perceptrons and simple learning rules
A brief history of Neural Networks
Neural Network Basics
(FAQ's)
Formal neurons, linear machines & perceptrons
Separability:
Linear separability
Separating points with circles
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
Bayesian Decision Theory with Gaussian Distributions
- A tutorial by Erin Mcleish
Bayes Theory: Discrete Features
Introductory Statistics Course
Another Introduction to Probability and Statistics
Bayes' Theorem
More about
Thomas Bayes
A Bayesian Puzzle
The three-door puzzle (Monty Hall problem)
Basics of Statistical Pattern Recognition
(by Richard O. Duda)
More about
Richard Duda
Minimum risk classification
Minimum error classification
Discriminant functions (linear, quadratic, polynomial)
Quadric surfaces
Geometry formulas and facts
Discriminant analysis code in MATLAB
The bivariate Gaussian probability density function
Multivariate statistics
Lecture Notes on Statistical Pattern Recognition
Occam's Razor:
Jacob Eliosoff's Tutorial on Occam's Razor in Decision Rules (with JAVA applet)
Occam's Razor
Occam's Razor and Machine Learning
Simplicity, Cross-Validation and Occam's Razor
More about William of Occam
11. Feature Selection: Independence of Measurements, Redundancy, and Synergism
Independent and conditionally independent events
Class-conditional and unconditional independence assumptions in pattern recognition
(Tutorial by Simon-Pierre Desrosiers)
Independence, uncorrelation and Gaussian distributions
(PostScript notes by Julio Peixoto)
Information theory:
A primer on information theory
(PostScipt)
Basic properties of Shannon's entropy and mutual informatio
n
Relative entropy and mutual information
From Euclid to entropy
(PostScript)
Shannon's equivocation and the Fano bound
More about
Claude Shannon
The
Claude Shannon
Home Page
Calculating Information and Complexity
Feature Selection:
Independence, Redundancy and Synergism: A Tutorial
by Irina Kezele
Feature Selection: Evaluation, Application, and Small Sample Performance
(PostScipt)
Toward Optimal Feature Selection
(PostScipt)
Dimensiobality Reduction: Francois Labelle's tutorial
(with interactive Java applets)
Simon Plain's tutorial on feature selection
(with interactive Java applets)
Feature evaluation criteria:
Kullback-Liebler information
The Divergence
The Affinity
The Mutual-Information criterion
(PDF file)
Discrimination information and Kolmogorov variational distance
(PDF file)
The Fisher Information
More about Sir Ronald Fisher
Pictures of Fisher
Feature selection methods (Richard Duda's course notes)
A survey of feature selection methods
The best K independent measurements are not the K best
(PDF file)
Models of spatial dependence between features
Space-filling curves (Hilbert and Peano)
Sierpinski curves
12. Non-parametric Machine Learning
General Learning Resources
Perceptrons:
Simple perceptrons and the exclusive OR problem
Applet for Perceptron learning in the exclusive OR problem
Non-parametric training of linear machines
(Nilsson's book - Chapter 4)
Error-correction procedures
Rosenblatt's Perceptron Learning Algorithm
(an interactive Java applet)
The fundamental learning theorem
Multi-layer networks
Competitive Learning:
Applet illustrating many competitive learning algorithms
13. Estimation of Density Functions, Parameters and Classifier Performance
Estimation of Parameters:
Robust estimators of location
(Tutorial by Greg Aloupis)
Bias and variance of estimators
Maximum likelihood estimation
Density Estimation:
Kernel density estimation applet
Estimators and Bias (Wolfram Research)
Dimensionality and sample size
Estimation of the probability of misclassification
Estimation of misclassification before 1974
Resubstitution
Holdout
Data Shuffling
Leave-One-Out
Bootstrap Methods
Ensembles of Classifiers
Boosting
Comparing the performance of several classifiers (the pitfalls)
14. Nearest Neighbor Decision Rules and Instance-Based Learning
Nearest Neighbor Decision Rules:
The nearest neighbor rule: a tutorial
The nearest neighbor rule with a reject option
The k-nearest neighbor rule applet
The Cover-Hart bounds and Jensen's inequality:
Convexity and Jensen's inequality
(proof by induction)
A Visual Explanation of Jensen's Inequality
Convexity and Jensen's Inequality
A Simple Proof of the Jensen-Steffensen Inequality
More about
Johan Ludwig William Valdemar Jensen
More about
Thomas Cover
More about
Peter Hart
Efficient search methods for nearest neighbors:
The projection method for searching nearest neighbors (algorithm of Friedman, Baskett and Shustek)
More about Jerome Friedman
Nearest neighbor searching papers
Approximate nearest neighbor searching
Editing nearest neighbor rules to reduce storage:
Reducing the size of training sets with proximity graphs
(PostScript)
Sergei Savchenko's tutorial on nearest neighbor condensing rules
Chris Cocosco's tutorial on nearest neighbor editing rules for smoothing decision rules
Nearest neighbor editing and condensing tools
(PostScript)
Nearest neighbor computation software
Bibliography on Nearest Neighbor Methods
15. Using Contextual Information in Pattern Recognition
Using Context in Visual Perception
Infinite Monkey Theorem
Introduction to Markov Processes
More about
Andrei Markov
Forward dynamic programming and the Viterbi algorithm:
A tutorial on the Viterbi algorithm
Viterbi algorithm demo
for sentence recognition
Combined bottom-up and top-down algorithms
16. Unsupervised Machine Learning and Cluster Analysis
Unsupervised Learning:
Decision-directed learning (the K-means algorithms)
K-Means Interactive Java Applet by Laurent Bonnefille and Nicolas Didier.
Graph-theoretic methods:
Minimal spanning tree methods
Tutorial and Java applet by Mike Soss and Chrislain Razafimahefa
Hierarchical clustering:
Pascal Poupart's tutorial with interactive Java applet
Phylogenetic Trees
(A Tutorial)
Clustering software on the Web
Cluster Analysis: What is it? (Fantastic tutorial!)
Clustering Calculator
17. Support Vector Machines
Support Vector Classifiers: A First Look
Tutorial on Support Vector Machines and Vapnik-Chervonenkis (VC) Dimension for Pattern Recognition (PostScript)
Support Vector Applet and References
18. Music Information Retrieval
Measures of Rhythmic Similarity
Measures of Melodic Similarity
Features for Music Classification
Phylogenetic Analysis Tools