Homework 1

Professor Howie Choset

Learning Objectives

• Review basics of linear algebra.
• Manipulating and interpreting images using computer vision principles.

P1. A Bit of Math (10 points) - Individual

An orthogonal matrix is a square matrix whose columns are orthogonal (dot product with other columns is 0) and have unit norm (dot product with self is 1). From this, it can be shown that its inverse is equal to its transpose (if A is an orthogonal matrix and AT its transpose, then A * AT is the identity matrix).

Do the following:

1. Generate an orthogonal matrix A (you may not use the identity matrix).
2. Calculate its transpose AT.
3. Using the program you wrote in Homework 0, show your work to verify that A*AT is the identity matrix.

Deliverables: A text file named `p1.txt` containing your matrix, its transpose, and the output from your program.

P2. Computer Vision: Where's Waldo? (40 points) - Individual

Meet Waldo.

Waldo, as you may be aware, frequently hides, and we need to find him. Your job is to create a program which will automatically locate Waldo (and his doppelgangers) in images such as this:

Each image contains the following kinds of Waldos:

• 5 exact copies
• 4 blurred copies
• 7 copies with noise added
• 5 rotated copies
• 1 double size copy
• 2 double size blurred copies
In addition every image will contain 6 non-Waldos, such as the smiley face above. Note that the white pixels in the Waldo image are not considered part of Waldo. That is, they will not generally be white for the exact match Waldos.

Your program must read the input image from `findWaldo.png` and write the results to a file called `waldo.txt`. This file must contain one line for each Waldo identified. Each line must contain the first index (the x coordinate) of the image, a space, and then the second index (the y coordinate), followed by a newline. For example:

```        13 47
78 13
107 33
```
Your numbers need to be within 2 pixels of the center of the Waldo for the normal size Waldos and 4 pixels for the 2x size Waldos. You can output decimal numbers if you'd like. Note that in our convention, images are indexed (x,y) starting from the upper-left corner, with x increasing to the right, and y increasing downward. Be careful, as this is different from matrices, which are indexed (y,x)!

• 20 points: Find at least one Waldo
• 32.5 points: Find all 5 exact copies
• 35 points: Find all 5 exact copies, plus any one other
• 37.5 points: Find all 5 exact copies, plus one from any two other types
• 40 points: Find all Waldos of 3 types
• -2 points per inacurate position reported (min score 0)
Your code should read the input file from the path `./findWaldo.png` (./ means the current directory). You may hardcode this into your program. Your code will be run on three different maps and your grade will be the average score of the three runs. Here are several sample pictures to test your code on, and an image of Waldo himself:

Note: please do not utilize library functions that trivialize the problem. Specifically, the image processing functions, ie. imrotate, imresize, etc. should not be used.

Matlab starter code that reads PNGs is available here: WheresWaldo.m.

Deliverables:

• Your commented source code named `p2.m`
• Any supplementary files your program needs.

Submission:

Collect ONLY your deliverables into a tar archive named `[AndrewID]_hw1.tar`, where [AndrewID] is replaced by your Andrew ID, minus the brackets. For example, user with AndrewID `odb` would submit `odb_hw1.tar`. Instructions to submit the tar file TBA. Failure to follow instructions on this homework will result in an automatic zero.