This assignment has natural links with the previous one , in that you could use the shape features you developed for your binary blob domain to classify blobs. Binary data could be produced by thresholding or by an editor, even.
If you have a different domain in mind, then you can substitute its features for the ones suggested in the previous assignment and carry on. Sample domains and classes might be (strictly off the cuff, just a few first thoughts).
|color patches||red, yellow, blue, brown (not easy)...||(hsv, rgb...)|
|texture image patches||grass, sand, concrete, bricks, hair, plaid,...||Laws texture energy, edge density and direction...|
|faces||(old- young) or (male- female) or (happy, sad, scared, angry, bored...).||pixel values of whole input (!), region shapes & relations|
|digits||0,1,...9||shape measures, holes, st. lines, terminations, etc.|
|kids' blocks||arch, bar, brick, half-round, star||shape measures|
|toys||plane, doll, snake, car...||shape measures|
|photos||(inside - outside) or (rightside up - upside down) or (party, christmas, vacation, sunset, portrait,...).||color, texture, relations of color patches, shapes...|
OK, you get the idea.
Clustering isn't mysterious. If you have N features, each with a real-number output (e.g. density of 1's, or number of diagonal edges in the upper left quarter of the images, or the B values of a B-binned edge-orientation histogram, or Fourier components of boundary shapes, or (R,G B) (or (H,S,V) or other color space coordinatees), or WHATEVER N features, they're just an N-vector. You may want to normalize the values so that the amount they contribute to the distance metric will be scaled right. Scaling by their individual standard deviations is a good start.
Anyway, during training you can just keep the average of these vectors for each class and that will be the mean vector (centroid) for that cluster. Then to test, you get a new vector and calculate its Euclidean distance from these class-representative mean vectors and the nearest one is your classification.
Alternately, remember all the training vectors (in an array say) along with their classification (in a parallel array). For a new test vector, calculate which of all the training vectors is closest, and its class is your answer. This is ``nearest-neighbor''. K-nearest neighbor is simple too, and you may want to try other tricks like principal component analysis (PCA) to throw out useless features, etc. etc. PCA isn't that hard, you just need to multiply your data matrix by itself and give it to a one-line MatLab command. See me if you need more info.
If you think about decision trees you'll see that they ask a sequence of questions, each of which divides feature space into two pieces. So they are another way of getting a decision surface in feature space. My guess is that it takes a fair amount of ingenuity to devise a tree that can cope with oddly-shaped or closely-intertwined clusters.
In any event your choice of features should reflect the characteristics you are trying to separate. Ideally you can do well by just thinking, but sometimes one just heaves all possible features into the mix and then prunes out those that don't perform (using PCA). The features are the computer vision part of the work, and can be found in your text in the relevant chapter.
For some domains you may want to consider features that offer invariance to systematic geometric variations, like: Translation, Rotation, Size variation (zoom), Skew (say italics vs. roman or different handwriting slants).
You may want to use preprocessing to deal with noise: high-frequency (speckle in the background), low-frequency (blotchy low-contrast background variation), dropout (holes where there should be letter).
There is a lot written on pattern recognition, and if you want to cite some of the literature to compare your algorithm to other existing ideas, fine. However, this is not meant to be a library research exercise as much as a thinking exercise.
Also turn in a README document that outlines the structure of your code: who calls what, names of modules and what they do, information on how to run the programs (arguments, data file formats, etc.).
This page is maintained by CB.
Last update: 15.8.02