Homework 3, Due Thursday, April 6. (final! please stop checking back!)

Choose 1 of the 2 projects. If you choose the first project, you must do one of the optional parts. The second project is more fixed. Groups of up to 2 are allowed. Due April 11.
Secure ftp site:

to download images from crunchy.
sftp: crunchy.cs.wustl.edu
username: cse559
Password: Pl3ss559  (as in Pless559, in 'leet speak)

lands you in a directory with one subfolder, named webcams,
which has folders names 1 through 39.

avi files are also available for camera 
camera 04 and
camera 33.

Project 1. PCA++
In the project you are going to write a pca algorithm that identifies the principle components and the coefficients for a set of images.
Base Option. Take a set of images, show the first 10 principle component images. Challenges that you need to solve and then write about:
1. How are you displaying your component images (is gray 0? if there are color, how are you mapping the negative rgb values into things you can image?
2. Show the reconstruction of one of your original images using 2, 4, 6, 8, 10 principle components.
3. Measure the reconstruction error, and show a plot of reconstruction error vs. number of principle components used.
4. Choose any set of images you want, one set of images is available at: http://crunchy.cs.wustl.edu/webcams
5. (math question) The (svd decomposition) used in PCA returns 3 matrices, U,S,V, where U contains principle components, V the coefficients, and S are singular values. What is the relationship between the i-th singular value s(i) and the sum of the reconstruction errors for all the images using i-1 principle components? You can answer this mathematically or by finding patterns in multiple different data sets.
- Option 1: Data sets on crunchy are time series data sets, (pictures taken every 5 minutes). Here we are going to look at different ways to do PCA with time series data (as opposed to an unordered collection of images). You are free to subsample these images to make them easier to compute with.
  - PCA over the whole image set,
  - PCA on the set of images where you *first* average together every 3 frames
  - PCA on the set of images where you *first* average together every 12 frames,
  - PCA on the set of images where you *first* take the difference of every consecutive frame
  - PCA with some other pre-processing of your choice
  What features are highlighted by these principle components? Why?
  For the 3 most important components, plot the coefficients as a function of time. Do these coefficient plots have the same pattern? Why or why not?
- Option 2: Mixed Up Recognition
  Find a data set at least as interesting as: 40 people times 10 images each.
  1. First, build a PCA recognition system. Choose 35 of the people, and 8 images of each of them as the training set, and build the PCA model for those people. The test set includes 2 images of each person, and the 10 images of the 5 people you didn't choose.
    For each image in the test set, use a nearest neighbor classifier in order to classify it. (that is, project it onto your basis set, compute the distance to the coefficients of the training images, and give it the label of the closest image). Define a threshold so that if the new coefficients are not "close enough" to any training image coefficients, then you label that image as not in the training set. Show the error rates including (a) images in database correctly defined, (b) images in the database mis-recognized, (c) images in the database not recognized (believed to not be in the database), and (d) images of people not in the training set incorrectly matched to a person in the database. Show this chart as a function of the number of principle components used (perhaps using 2,4,6,8,10 pc's).
  2. Do the same thing as part 1, but take *any* collection of about 100 natural images (100 random images, 100 images of doors, anything), and use these 100 images to define the PCA basis matrix U. Then repeat part (a) using this new set of basis images, and show the same results. (compute the coefficients by projecting the face images onto U, and do the recognition the same way). Discuss your results. Are they as good (or almost as good?) as when using the basis functions defined by the relevant data set? If not, why not? If so, what does that mean about the PCA basis set?
- Option 3, Visualization of PC's.
  The principle components captured from a fixed camera highlight related areas of a scene. This option is open ended and asks you to explore ways of visualizing these principle components in a single image, rather than showing several images. One way I've done this is to take three principle components, and make a "false color" image using one of the PC's to define the red component, one to define the blue component and so on. Here you can present a "diary" format of alternative approaches that you explore to visualize several basis images at once, and discuss how each addresses the goal of "visualizing the variation in the scene".
Project 2: Scene Recognition
For any interesting collection of images with at least 4 categories, such as: http://www.paaonline.net/benchmarks/minerva/
1. Implement the texton based classification scheme, using either:
  a) universal textons, or sift features, or frequency response surfaces and
  b) a nearest neighbor classifier, or other classifier of your choice.
  Show:
  1. Your data set,
  2. Your classification confusion matrix
  3. Detail exactly what pre-processing you do (ie, do you scale all the images to be the same size? are you making all images grayscale?)
  4. Give a pseudocode algorithm of how you compute textons or sift feature responses, and how you implement your classifier.
  5. Give a complexity analysis that lists the computational complexity of your approach (both for building the representation, and, again for using the representation to classify a new image), as a function of:
    
    the size of the data set (both number of images and size of each)
    the number of categories in the data set
  There are no optional parts to this project.