Guidelines for Assignment 5
Learn about representing images as vectors, calculating distances using Euclidean and Manhattan methods, and classifying images with the nearest neighbor algorithm. Understand the vector representation of images and the concepts of Euclidean and Manhattan distances. Explore the nearest neighbor classifier for image classification tasks.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Guidelines for Assignment 5 CSE 4310 Computer Vision Vassilis Athitsos Computer Science and Engineering Department University of Texas at Arlington
Vector Representation of Images Let ? be the space of all images of some specific size ? ?. ? is the number of rows. ? is the number of cols. Then, an image ?1 from ? can be written as a ?- dimensional vector, where D = ? ?. In Matlab, we can write: vector_v1 = v1(:); Mathematically, we denote ?1 as a vector by writing: ?1= ?1,1,?1,2, ,?1,? 2
?? Distance Let ?1,?2 be two objects in ?. Each of them is a ?-dimensional vector. In general, the ?? distance between ?1 and ?2 is defined as: ? ? ? ???1,?2 = ?1,? ?2,? ?=1 From the above definition, obviously the Euclidean distance is just the ?? distance for ? = 2. 3
Euclidean Distance: ?2 Distance The Euclidean distance is simply the ?2 distance: ? 2 2 ?2?1,?2 = ?1,? ?2,? ?=1 4
Manhattan Distance Another popular distance measure is the ?1 distance measure, also known as the Manhattan distance: ? ?1?1,?2 = ?1,? ?2,? ?=1 You should NOT use the Manhattan distance in your assignment. 5
The Nearest Neighbor Classifier The nearest neighbor classifier can be used to classify an image ? as belonging to a certain class. To use the nearest neighbor classifier, you must define a distance measure?. In Tasks 1, 2, 3, ? will be the Euclidean distance. In Tasks 4, 5, 6, ? will be the chamfer distance. To use the nearest neighbor classifier, you also need to have a training set of examples T = ?1, , ??. For each training example ??, we assume that we know the class label. 6
The Nearest Neighbor Classifier For nearest neighbor classification, given test image ?, we first find its nearest neighbor C(?) in the training set. C(?) = argmin? ?1, , ??? ?,? Then, the output is the class label of C(?). In short, each test pattern ? is assigned the class of its nearest neighbor in the training data. 7
The Nearest Neighbor Classifier The nearest neighbor classifier can be used to classify an image ? as belonging to a certain class. In your assignment, there are 10 classes. The nearest neighbor classifier works by template matching. It uses training templates, which are one or more examples for each of the classes it should recognize. 8
The Nearest Neighbor Classifier Given an image ? to classify, and given a set of ? training templates ?1, ,??, the nearest neighbor classifier works as follows: Measure distances from ? to each training example ??. Find the example ?? that has the smallest distance to ?. Output the class label of ?? as the estimate for the class label of ?. 9
Example Suppose we have a problem where: We have three classes (red, green, yellow). Each pattern is a two-dimensional vector. Suppose that the training data is given below: Suppose we have a test pattern ?, shown in black. How is ? classified by the nearest neighbor classifier? 0 1 2 3 4 5 6 y axis 0 1 2 3 4 5 6 7 8 x axis 10
Example Suppose we have a problem where: We have three classes (red, green, yellow). Each pattern is a two-dimensional vector. Suppose that the training data is given below: Suppose we have a test pattern ?, shown in black. How is ? classified by the nearest neighbor classifier? C(?): Class of C(?): red. Therefore, ? is classified as red. 0 1 2 3 4 5 6 y axis 0 1 2 3 4 5 6 7 8 x axis 11
Example Suppose we have a problem where: We have three classes (red, green, yellow). Each pattern is a two-dimensional vector. Suppose that the training data is given below: Suppose we have another test pattern ?, shown in black. How is ? classified by the nearest neighbor classifier? 0 1 2 3 4 5 6 y axis 0 1 2 3 4 5 6 7 8 x axis 12
Example Suppose we have a problem where: We have three classes (red, green, yellow). Each pattern is a two-dimensional vector. Suppose that the training data is given below: Suppose we have another test pattern ?, shown in black. How is ? classified by the nearest neighbor classifier? C(?): Class of C(?): yellow. Therefore, ? is classified as yellow. 0 1 2 3 4 5 6 y axis 0 1 2 3 4 5 6 7 8 x axis 13
Example Suppose we have a problem where: We have three classes (red, green, yellow). Each pattern is a two-dimensional vector. Suppose that the training data is given below: Suppose we have another test pattern ?, shown in black. How is ? classified by the nearest neighbor classifier? 0 1 2 3 4 5 6 y axis 0 1 2 3 4 5 6 7 8 x axis 14
Example Suppose we have a problem where: We have three classes (red, green, yellow). Each pattern is a two-dimensional vector. Suppose that the training data is given below: Suppose we have another test pattern ?, shown in black. How is ? classified by the nearest neighbor classifier? C(?): Class of C(?): green. Therefore, ? is classified as green. 0 1 2 3 4 5 6 y axis 0 1 2 3 4 5 6 7 8 x axis 15
The ?-Nearest Neighbor Classifier Instead of classifying the test pattern based on its nearest neighbor, we can take more neighbors into account. This is called ?-nearest neighbor classification. Using more neighbors can help avoid mistakes due to noisy data. In the example shown on the figure, the test pattern is in a mostly yellow area, but its nearest neighbor is red. If we use the 3 nearest neighbors, 2 of them are yellow. Note: in your assignment K=1. You will do 1-nearest neighbor classification. 16
Choice of Distance Measure To use the nearest neighbor classifier, you need to decide what distance measure you want to use. In the assignment, you will use and evaluate two different measures: The Euclidean distance. The chamfer distance. 17
Tasks 1 and 2 In Task 1, you simply need to implement the Euclidean distance. Remember, the inputs are images, they need to be vectorized. In Task 2, you implement the nearest neighbor classifier using the Euclidean distance. Your input is a test image. You need to compare it to the 150 training examples that you are given. You find the nearest neighbor to the test image among the training templates. The class of the nearest neighbor is what your function should return. 18
Filenames and Class Labels Each training example is saved in a filename that follows this format: labelX_trainingY.png. In that format, X is the class label. For example: For filename label8_training3.png, the class label is 8. For filename label9_training2.png, the class label is 9. Values Y in the filename range from 1 to 15. This way, you can generate all 150 filenames for the training examples, by doing a double for-loop, for label = 0:9, and for example = 1:15. 19
Confusion Matrix A confusion matrix is a standard way to evaluate a classifier. If we have N classes, the confusion matrix is of size NxN. The value at position (i,j) is the percentage of test objects of class i that were classified as class j. In the assignment, what will be the size of the confusion matrix? 20
Confusion Matrix A confusion matrix is a standard way to evaluate a classifier. If we have N classes, the confusion matrix is of size NxN. The value at position (i,j) is the percentage of test objects of class i that were classified as class j. In the assignment, what will be the size of the confusion matrix? 10x10, since we have 10 classes. 21
Confusion Matrix A confusion matrix is a standard way to evaluate a classifier. If we have N classes, the confusion matrix is of size NxN. The value at position (i,j) is the percentage of test objects of class i that were classified as class j. What does the confusion matrix look like if we have a perfect classifier? It is the identity matrix. For every class i, the value at position (i,i) is 1, indicating that 100% of the test objects belonging to class i were classified correctly as belonging to class i. 22
Indexing the Confusion Matrix If we have N classes, the confusion matrix is of size NxN. In this assignment, if you use Matlab, there is a slight indexing problem: We have a class label 0 . However, matrix indices start with 1. To solve this, we will use index 10 for class label 0. 23
Confusion Matrix Example Suppose we have 200 test images. For 20 of those images, the true class label is 2 . Out of those 20 images, for 5 images the system outputs 8 . (Obviously, this means that the system was wrong for those cases). Where in the confusion matrix is this information stored, and how? 24
Confusion Matrix Example Suppose we have 200 test images. For 20 of those images, the true class label is 2 . Out of those 20 images, for 5 images the system outputs 8 . (Obviously, this means that the system was wrong for those cases). Where in the confusion matrix is this information stored, and how? Where: row 2, column 8 (2 is the correct class, 8 is the output of the system). How: Confusion_Matrix(2,8) = 0.25, since 25% (5 out of 20) of images with true label 2 were classified as having label 8 . 25
Directed Chamfer Distance Input: two sets of points. ? is the set of red points. ? is the set of red points. For each red point ??: Identify the green point ?? that is the closest to ??. The directed chamfer distance ?(?,?) is the average distance from each red point to its nearest green point. For the two sets shown on the figure: Each red point is connected by a link to its nearest green point. ?(?,?) is the average length of those links. 26
Directed Chamfer Distance Input: two sets of points. ? is the set of red points. ? is the set of red points. For each green point ??: Identify the red point ?? that is the closest to ??. The directed chamfer distance ?(?,?) is the average distance from each green point to its nearest red point. For the two sets shown on the figure: Each green point is connected by a link to its nearest red point. ?(?,?) is the average length of those links. 27
Chamfer Distance Input: two sets of points. ? is the set of red points. ? is the set of red points. ?(?,?): Average distance from each red point to nearest green point. ?(?,?): Average distance from each green point to nearest red point. The chamfer distance? ?,? is simply the sum of the two directed chamfer distances ?(?,?) and ?(?,?): ? ?,? = ? ?,? + ?(?,?) 28
Chamfer Distance Example ? = ? = First, we compute the directed distance ?(?,?): For 12,5 , the closest point in ? is 5,7 . 12,5 , 8,6 , 5,13 5,7 , 6,11 Distance: (12 5)2+(5 7)2= 7.28. For 8,6 , the closest point in ? is 5,7 . Distance: (8 5)2+(6 7)2= 3.16. For 5,13 , the closest point in ? is 6,11 . Distance: (5 6)2+(13 11)2= 2.24. ? ?,? =7.28+3.16+2.24 3 = 4.23. 29
Chamfer Distance Example ? = ? = Second, we compute the directed distance ?(?,?): For 5,7 , the closest point in ? is 8,6 . 12,5 , 8,6 , 5,13 5,7 , 6,11 Distance: (5 8)2+(7 6)2= 3.16. For 6,11 , the closest point in ? is 5,13 . Distance: (6 5)2+(11 13)2= 2.24. ? ?,? =3.16+2.24 2 = 2.70. 30
Chamfer Distance Example ? = ? = Third, we compute the undirected chamfer distance ?(?,?): The undirected chamfer distance is the sum of the two directed distances. 12,5 , 8,6 , 5,13 5,7 , 6,11 ? ?,? = ?(?,?) + ?(?,?) = 4.23 + 2.70 = 6.93 31
Extracting a Set of Points In your assignment, every image (in the test set and the training set) should be treated as binary. To compute the chamfer distance, you need to convert the image to a set of points. This set of points should include all pixels where the image has a non-zero value. 32
Using the Distance Transform You can alternatively compute the chamfer distance using the distance transform. If b1 is a binary image, then the distance transform d1 is computed in Matlab as: d1 = bwdist(b1); d1(i,j) is the distance of pixel (i,j) from the closest non-zero pixel in image b1. Binary image b1 Distance transform d1 33
Using the Distance Transform If you have two images im1 and im2, the directed chamfer distance from im1 to im2 can be computed using the distance transform, with the following Matlab code: im1_binary = (im1 ~= 0); im2_binary = (im2 ~= 0); n1 = sum(im1_binary); dt2 = bwdist(im2_binary); chamfer_im1_to_im2 = sum(sum(im1_binary .* dt2)) / n1; The first two lines convert im1 and im2 to binary images with values 0 and 1. The third line computes the number of non-zero pixels in im1. The fourth line computes the distance transform of im2_binary. 34
Using the Distance Transform If you have two images im1 and im2, the directed chamfer distance from im1 to im2 can be computed using the distance transform, with the following Matlab code: im1_binary = (im1 ~= 0); im2_binary = (im2 ~= 0); n1 = sum(im1_binary(:)); dt2 = bwdist(im2_binary); chamfer_im1_to_im2 = sum(sum(im1_binary .* dt2)) / n1; The fifth line: Sums up the distances of each non-zero pixel of im1 to its closest non-zero pixel at im2. Divides that sum by n1, so that it computes the average distance from each non-zero pixel of im1 to the closest non-zero pixel at im2. 35
