CS 97 –Computer Perception – Assignment #2Instructor: Prof. Douglas Turnbull.Due Date: Tuesday Sept. 22, 2008.Instructions You should submit your final report in as a PDF that was created using Latex. (You will alsoneed to use Latex for your research paper so this will be good practice.) I would encourageyou to finish problems 1-3 by September 15th since they will complement the material we arecovering in class. This is a long lab so please start early.Matlab Matlab is a powerful tool for signal processing, matrix manipulation & linear algebra, statistics,visualization, and optimization. It main advantage is that is can be use for rapidly prototypingyour ideas. There are number of useful tutorials online to help you get started. Part of beinga good research is you ability to learn on your own outside of the classroom.Toolboxes There are a number of publicly-available Matlab toolboxes for images signal processing (Mat-lab’s Image Processing Toolbox, Piotr’s Image & Video Toolbox for Matlab), audio signal pro-cessing (Slaney’s Auditory Toolbox, Pampalk’s MA Toolbox), and machine learning. Thesewill be helpful down the road so that you don’t have to “reinvent the wheel” when doingcutting-edge research.1. Handwritten Digits: Loading & Visualizing(a) Start Matlab by typing matlab for a linux command prompt on a CS lab machine.Load the data set of handwritten digits (load /scratch/cs97/lab1/digitImage.mat)and the associated set of labels (load /scratch/cs97/lab1/digitLabel.mat). The ledigitImage.mat consists of two matrices - imageTrain which is 28 x 28 x 5000 dimen-sional (the third dimension indexes the di?erent images) and imageTest which is 28 x28 x 500 dimensional. The le digitLabel.mat contains the ground truth label vectorslabelTrain and labelTest for the training and testing database.(b) Display the first 40 training digits together with their labels, arranged in a 4 × 10 array.(Hint: subplot(), plot(), image(), & imagesc() will be useful Matlab functions forthis task. Type help [FUNCTION NAME] to learn more about each function.)(c) Compute the prior probability of each digit in the training set. Is it uniform?2. Handwritten Digits: Measuring Similarity/Dissimilarity.Let xi∈ Rd(with d = 282) denote the ith training example concatenated as a column vector.(a) Implement the following pairwise comparison functions of the form D(xi, xj):• Lpnorm:Pdk=1|xik− xjk|p1/p• Inner product: (xi)>xj• Normalized inner product: (xi)>xj/kxikkxjk• χ2distance:12Pdk=1(xik− xjk)2/(xik+ xjk)Each is defined for x ∈ Rdexcept χ2, which requires x to be nonnegative and sum to 1.(b) Compute and display the best match (using max or min as appropriate) for the first 10training digits (excluding self matches) vs. all M training digits using L1, L2, L∞, andinner product (both normalized and raw). Use an asterisk to indicate errors (e.g., whichpairs are mismatched).(c) Which choice of D(·, ·) gave the fewest errors? Which gave the most?3. Handwritten Digits: Confusion Matrices and ROC Curves.1(a) Compute the L2distance from all N testing digits to all M training digits.(b) Assuming a 1-nearest neighbor classifier, compute the 10×10 confusion matrix for this ex-periment. Display it as an image and comment on what it reveals about the classificationbehavior for digits such as 5 and 8.(c) Compute the histogram of distances for genuine matches and for impostors. Use bins ofsize 10 on the range 0 to 250, and normalize the histograms to sum to 1. Plot the twohistograms on the same set of axes.4. Color Histogram Matching.(a) Select 10 objects from the Amsterdam Library of Object Images (ALOI) at http://staff.science.uva.nl/∼aloi. For each object, download two images captured by the same cameraunder different illumination directions; call the resulting two sets of images A and B. Thepreview thumbnail resolution of 154 × 115 is sufficient for this exercise.(b) For each of the 20 downloaded images, compute the color histogram using a color spaceof your choice with 15 equally spaced bins per channel.(c) Compute the 10 × 10 matrix of χ2distances between the color histograms from A tothose of B. Display the distance matrix, indicating the best matching entry in each row.Comment on the performance you observe, highlighting interesting successes or failures.5. Music Similarity and Genre Classification(a) You will find a collection of 92 MP3 files from 4 music festivals (Bonnarro, PhillyFolk,South Padre, & Stagecoach) in /scratch/cs97/lab1/music. Trying playing a couple ofthese songs using Audacity or XMMS.(b) Convert each audio file from a MP3 to a WAV file in matlab using mp3read (downloadfrom http://labrosa.ee.columbia.edu/matlab/mp3read.html).(c) Using the MA Toolbox (http://pampalk.at/ma/download.html), extract the MFCC fea-ture vectors for each Song and store in a file.(d) Using the symmetrized KL Divergence (see 2-page note by Mandel and Ellis - http://mr-pc.org/work/mirex05.pdf), calculate the 92 X 92 similarity matrix. For 8 songs of yourchoosing, print the 5 most and 5 least similar songs in the data set. Use an asterisk toindicate which of these 10 songs are from the same festival as the query song.(e) Classify each songs into Bonnarro, PhillyFolk, SouthPadre, or StageCoach using the K= 1-, 3-, 5-, and 7-nearest neighbor classification. Compute the overall accuracy andconfusion matrix for each K. Comment on