Homework 1

16-311: Introduction to Robotics

Professor Howie Choset

Learning Objectives

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:

Come find me!

Each image contains the following kinds of Waldos:

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)!


Your assignment will be graded as follows:

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.


L1. Lab 1: Rube Goldberg (50 points) - Group


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.