Homework 2
16-311 Introduction to Robotics
Prof. Howie Choset

• (10%) Orthogonal Matrices:
  An orthogonal matrix is one whose inverse is equal to its transpose. So, if A is an orthogonal matrix and A^T its transpose, then A * A^T is the identity matrix.

  Do the following:

  • Come up with an orthogonal matrix A (you may not use the identity matrix)
  • Calculate it's transpose A^T
  • Use your program from last week to show A*A^T is the identity matrix.

• (40%) Where's Waldo?

  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 find Waldos in images such as this.

  

  In every image there will be the following kinds of Waldo:

  • 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 herring chunks that contain values near zero, but are not waldos.

  Write a program to automatically find as many Waldos as you can in these images. It should return the row and column of the center of the Waldo. For example, the position of the red pixel in this image

  

  is [2,4].

  Your program must read the input image from either "findWaldo.png" or "findWaldo.pgm" (both files will correspond to the same scene). 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 of the image, a space, and then the second index, 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.
  Credit will be awarded for this portion of the assignment as follows.
  • 50%: find at least one Waldo.
  • 80%: find all 5 exact copies.
  • 90%: 5 exact copies, plus any one other.
  • 95%: 5 exact copies, at least one from of any two other types.
  • 100%: all Waldos of at least 3 types.
  • -5% per inacurate position reported (min score 0%).
  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. To grade your code we will run it on images generated the same way.

  • Sample 1: (pgm/png)
  • Sample 2: (pgm/png)
  • Sample 3: (pgm/png)
  • Sample 4: (pgm/png)
  • Waldo: (pgm/png)

  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.

  The following are useful links for working with pgm images.

  Here are two new samples and ground truth results for testing:
  New sample 1: [PNG] [PGM] answers
  New sample 2: [PNG] [PGM] answers
  NOTE: be careful about confusion with the order of the answers. Pixels are counted from (0,0) at the top left, wheres most other things, such as the "plot" function in matlab, consider (0,0) to be bottom left

  Useful Links

  PGM specification ImageMagick (converts PGM) Open Office PGM conversion program for MATLAB PGM reader for MATLAB (handles negative numbers)

  You may also want to use some of the starter code for Lab 2, which contains read and write functions for PGM images.
  
  

• (50%) Group:
  Lab 1 (Rube Goldberg Machine)

  Remember to create a URL that

  • Depicts your Group's name and members' names.
  • Contains pictures of your Rube Goldberg Machine.
  • Lists the energy tranfers.

Turn in:

Email the lab TA for Rube Goldberg lab.
• The URL for webpage of the Rube Goldberg lab.
Email the head TA:
• The output of the program run for part 1 of the individual assignment (showing the input matrices and the result).
• A copy of your source code for part 2 of the individual assignment (where's Waldo?).
• An AFS path to the executable of your code. As with homework 1, make sure the permissions on your executable are properly set.