WarmupLab

From EECS467
Jump to: navigation, search

Overview

Your deliverables consist of:

  • A lab report, due 1/21

Submitting

Your problem set should be emailed in the following format:

TO: eecs467-submit@april.eecs.umich.edu
SUBJECT: WarmupLab: <uniqname>

Your email should contain exactly one attachment.

  1. A PDF of your typeset write up. We will not accept any other formats (including .doc). We encourage you to use LaTeX, since it will make typesetting math easy. (Your write-up should briefly restate the question being answered so that is "self-contained".) The use of figures, screenshots, code snippets, etc., is strongly encouraged and is generally critical in obtaining full marks.

NB: Your files should not exceed 3 MB in size. If you cannot reduce the file below this size, our mail server may reject it. Instead, post your file on your UMICH web space and email us a link AND the md5sum of the PDF. This will serve to timestamp your submission.

Deviations from this format will be penalized. You should receive a "moderation pending" message; this indicates successful receipt of your email.

This is an individual assignment. You may discuss your work with other students, but each student must write their own solution. Please review the course collaboration policy, and as always, feel free to ask the staff if you have any questions.

You may find this introduction to Vx helpful. Be warned that it is a living document, still, and is subject to change. Likewise, suggestions and fixes are welcome.

Task 1

Objective: Read and understand the course policies, and set up a repository for your software.

Q1.1. Subscribe to the course mailing list by visiting http://april.eecs.umich.edu/mailman/listinfo/eecs467-discuss. Your "Welcome to the eecs467 mailing list" email will tell you the answer to this question (look in the first paragraph).


Q1.2. If you email your lab report at 2am on January 22nd, what is the maximum percentage you can earn?


Q1.3. Which of the following are permissible forms of collaboration on this lab? (More than one may apply).

A) Dividing the work up between two students and combining the results.

B) Using a solution from another student to get "unstuck".

C) Referring to pseudo-code from wikipedia.

D) Discussing the problems and strategies for solving them over lunch with classmates.

E) Using an open-source software package as part of your solution.

F) Getting help from a classmate in understanding a compiler error.


You should not store any important documents on the machines in lab, both because they are not backed up, and because the files created on one machine will not be accessible from another. Instead, we recommend doing all of your work in a revision control system whose primary repository is stored in your UMICH AFS space.

Q1.4. Configure a software revision control system in your UMICH AFS space (we recommend git, but SVN is okay too.) How did you check out this repo from the machines in lab? (Provide the specific command line that you used.)


Task 2. Template Matching

First, a quick note on installing the software. You can check out and build the git repository by typing:

cd $HOME
git clone git://april.eecs.umich.edu/home/ebolson/eecs467
cd eecs467/src
make
export VX_SHADER_PATH=$HOME/eecs467/src/vx/shaders
export VX_FONT_PATH=$HOME/eecs467/src/vx/fonts

A good program to run as a sanity test is "vx_zoo", which will be copied to the bin folder. It shows examples of the various objects that you can add to a vx_world. The example code we showed in class lives in the src/apps folder. You may also find it convenient to put the two export commands in your $HOME/.bashrc file.

Objective: Understand how to detect an object with known appearance by using template matching.

You can implement a Waldo detector using template matching: using a known image of Waldo, scan the image looking for sub-images that like similar. (Suppose the template is twidth by theight pixels. You could compute how such a section of an input image looks like the template by iterating over the pixels in the template and computing an error metric. E.g., the error associated with matching the template with the image at (image_offset_x, image_offset_y) could be written:

double error = 0;

for (int ty = 0; ty < theight; ty++) {
  for (int tx = 0; tx < twidth; tx++) {
    int t_idx = ty*template->stride + tx;
    int im_idx = (image_offset_y+ty)*image->stride + (image_offset_x+tx);
    int template_abgr = template->buf[t_idx];
    int image_abgr = image->buf[im_idx];

    int template_red = (template_abgr >> 0)&0xff;
    int image_red = (image_abgr >> 0)&0xff;
    int template_green = (template_abgr >> 8)&0xff;
    int image_green = (image_abgr >> 8)&0xff;
    int template_blue = (template_abgr >> 16)&0xff;
    int image_blue = (image_abgr >> 16)&0xff;

    error +=  sqrt(pow(template_red - image_red,2) +
                   pow(template_green - image_green,2) +
                   pow(template_blue - image_blue,2));
  }
}
Q2.1. Create a user interface using vx and getopt that allows a user to select a template image (media:waldo_template.ppm) of Waldo and an image (media:waldo_search.ppm) to search for Waldo in. Match the template against the image, rendering a rectangle around the best match. Provide a screenshot of the output of your template matcher, and include the template-matching portion of your code in your writeup.


Q2.2. What is the asymptotic cost of template matching in terms of the template width and height (Tw and Th) and the image width and height (Iw and Ih)? Empirically measure the performance of your system, varying the size of the image and template, and provide a plot of runtime as a function of the template size. (Make sure to vary the template size over a wide variety of values, from 1x1 pixel to 100x100 pixels or more). Does your empirical data match your prediction? Briefly discuss.


Template matching is often slow. One way of making template matching run faster is to stop iterating over tx/ty (as in the code above) as soon as the error exceeds the error of the best match found so far. Another is to reduce the resolution of the input image (and presumably the template). Another is to not use all three color channels (or even to convert the image to another color space). Another is to "hand optimize" the code by unrolling loops, performing strength reductions, rewriting the function using SSE, or changing the error metric so that is less expensive to compute.

Q2.3. Improve the performance of your code by implementing several different optimizations. For each optimization, be sure to comment on whether your method produces identical results to the naive template matching approach, or whether some approximation error could result. Empirically measure the performance impact of each optimization, and provide an appropriate figure. Full marks will be given for those who implement and document the results of three (substantially different) strategies.