# PS3

### Instructions

For this problem set, you should use the april.vis visualization library and the april.jmat linear algebra library again. Relevant files for this project are attached below.

tar -xzvf eecs568-ps3.tar.gz cd april/java <update .bashrc CLASSPATH and LD_LIBRARY_PATH values to point at PS2 files> ant

**Submitting**

Your problem set should be emailed in the following format:

TO: eecs568-staff@april.eecs.umich.edu SUBJECT: PS3: <uniqname1>, <uniqname2>, <uniqname3>, (<uniquename4>) CC: <all of your team members>

Your email should contain exactly three attachments.

- A PDF of your write up. All equations must be typeset and figures must be rendered by april.vis. We will not accept any other formats (including .doc). We encourage you to use latex, since it will make typesetting math easy.
- A .tar.gz file containing a directory of source code. It must include a build.xml and a README with instructions on how to invoke your software.
- A photo of your collaboration certification, signed by all team members. It is acceptable for this to be hand written.
**Do not send us large, hi-res photos. Otherwise, the e-mail server may bounce your submission.**Aim for less than 200kB for the photo.

Deviations from this format will be penalized. You may receive a "moderation pending" message; this is harmless.

### Task 1 - Matrix Sparsity and Exact Minimum Degree Ordering (EMD)

Exploiting the sparsity in our matrices can improve performance tremendously. EMD methods reorder our variables to increase sparsity, boosting our overall performance.

**A** Consider a graph with 8 poses, a, b, c, d, e, f, g, and h. Suppose there are links between (a,b), (b,c), (c,d), (d,e), (e,f), (g,h), (a,h), (a,c), (c,e), and (h,f). Draw the adjacency matrix (ASCII art is fine here.)

**B** What node has the largest node degree? Draw the adjacency matrix when that node is marginalized out.

**C** The minimum degree ordering is one of the best ways of ordering variables. In what order would you eliminate variables (using the graph from **A**) using the minimum degree heuristic? (Break ties alphabetically).

**D** Provide an asymptotic complexity estimate for computing the minimum degree ordering. Explain the origin of this estimate, particularly if you use any exotic data structures. That said, you need only consider a straight-forward algorithm. Make sure you define any of the letters (e.g. in O(N), what is N?) that you use.

**E** Suppose the minimum degree ordering is too slow for your application. Suggest an approximation of the minimum degree ordering that would reduce the run time. (Hint: The idea of picking low-degree nodes is still a good one... you needn't come up with a radically new approach! Consider deriving a simpler problem from your input problem, or a method that doesn't compute the minimum degree ordering *exactly*, but saves time.) Pseudo code may make your answer easier to understand.

### Task 2 - RGB-D sensing

As discussed in class, RGB-D sensors provide both depth and color data that may be used to create colored 3D point clouds of the current scene. In this task, you will be processing colored 3D data from a Kinect viewing a tabletop scene. File:Tabletop.log.tar.gz We've given you some boilerplate code to get you started (see team.KinectProcessing).

**A** Oftentimes, we can exploit advanced knowledge of our domain when processing data. For example, in the supplied log of Kinect data, there is a scene of objects were are interested in on a table top. The table and everything below it are not of interest, so we should be able to discard those points from the scene before running more advanced point-cloud processing steps.

For this task, use RANSAC to fit a ground plane to the tabletop in this scene. Once you have found this plane, use it to "throw away" the points making up the table and everything below it. Provide a screenshot of a point cloud, your plane fit to the table's surface, and clearly distinguish which points you are keeping and which ones you are discarding (for example, by coloring good points as green and bad points as red). In your write up, talk about how many RANSAC iterations you ended up needing and what you based your consensus score on.

**B** Once you have removed the uninteresting points from the scene, identify which groups of 3D points make up the individual objects in the scene. Use a Union Find style clustering method to group points into clusters based on the distances separating them. Provide a screenshot clearly indicating your final clusters by coloring each "object" differently and explain your clustering algorithm and any parameters it has. (HINT: Check out april.util.UnionFindSimple and april.vis.ColorUtil). You may use our implementation of UnionFindSimple, but a modest amount of extra credit will be awarded to teams which implement it themselves (in which case you should not refer to our implementation, but may refer to pseudo-code e.g. on wikipedia.)

**C** You may notice the American flag dominating a large portion of your ground plane. This image (including the white bordering portion) is 21 in x 16 in (0.5334 m x 0.4064 m) in size. Use a homography to project the distored image of the flag in the camera's scene and reproject it to its undistorted rectangular form. Provide a screenshot of the rectangular image of the flag as it would be viewed from directly above.

**BONUS TASK** If you want an extra bit of fun, write code to classify the objects in the scene as either triangular or cylindrical. In your write up, explain how your method works and provide several screenshots of successful identifications. Your visualization should clearly distinguish between the two shapes, demonstrating that you know what is a triangle vs. what is a cylinder (vs. whatever objects are neither!)