Assignment 1: Triangulation Matting Solution

In this assignment you will implement and experiment with Smith and Blinn’s triangulation matting technique to be discussed in class next week. Your task is to implement a command-line version of the technique using Python, Numpy and the OpenCV library.

Goals: The goals of the assignment are to (1) get you familiar with OpenCV and NumPy; (2) learn how to formulate and solve linear systems of equations involving image measurements; (3) experiment with a very basic image analysis and manipulation technique; and (4) learn how to assess the technique’s failure points.

Bonus components: The assignment also includes a couple of \bonus" questions for those of you who want to dig a bit deeper into either the programming or on the conceptual side of the technique. You should only tackle these components if you are con dent with the rest of your submission.

Important: While the due date for the assignment is almost 3 weeks away, you are strongly advised to start immediately. It will take quite some time to familiarize yourself with OpenCV, Numpy and the starter code. Once you \get the hang of it," the programming component of the assignment should not be too hard as there is relatively little python coding to do. What will take time is internalizing exactly what you have to do, and how.

Triangulation Matting (100 Marks)

The technique is covered in Week 2’s lecture slides and is described in full detail in the following paper (included on website under readings):

A. R. Smith and J. F. Blinn, \Blue Screen Matting," Proc. ACM SIGGRAPH, pp. 259{268, 1996.

You are strongly encouraged to read the paper’s rst few pages (up to page 262) to understand the technique’s broader context. Those pages, however, are not required for implementing the tech-nique. You should also read the the Week 2 lecture slides now in order to get started and to have questions/clari cation requests ready when the technique is discussed in class.

Part 0. Starter code & the reference solution

Use the following sequence of commands on CDF to unpack the starter code:

    • cd ~

    • tar xvfz matting.tar.gz

    • rm matting.tar.gz

Consult the le 320/A1/partA/README 1st.txt for details on how the code is structured and for guidelines about how to navigate it. In addition to the starter code, I am providing a fully-featured reference solution in compiled, statically-linked binary format (OS X and CDF/Linux only). You should run this binary to see how your own implementation should behave, and to make sure that



1

your implementation produces the correct output.

320/A1/CHECKLIST.txt: Please read this form carefully. It includes information on the course’s Academic Honesty Policy and contains details on the distribution of marks in the assignment. You will need to complete this form prior to submission, and will be the rst le markers look at when grading your assignment.

Part 1.1 The triangulationMatting() method (50 Marks)

This is the key function you must write, which implements the triangulation matting technique. The (skeleton) method is contained in le 320/A1/partA/matting/algorithm.py.

Its behavior should be as follows. The method takes as input four color images: two images of the same foreground object against two di erent backgrounds (called compA and compB in the starter code), and images of the backgrounds by themselves (called backA and backB, respectively). If these four input images have been loaded in memory already, triangulationMatting() computes one grayscale and one color image|alphaOut and colOut|which hold the foreground object’s alpha and color values, respectively. The method returns True if it succeeds in creating these outputs and False, along with an error string, if it does not (e.g., if one or more of the four input images are not loaded already).

In addition to this method, you must also implement the associated image-loading and image-writing methods: readImage() and writeImage(). See the starter code for details on their input and output arguments, how they are called, and what values they should return.

E ciency considerations: You should pay attention to the e ciency of the code you write, as it is easy to write highly-ine cient image analysis code with python. Solutions whose timings are signi cantly higher than the reference implementation (which is not optimized for speed) will lead to mark deductions.


Part 1.2. The createComposite() method (10 Marks)

This method, which you must also write, implements the matting equation. The method takes as input three images: a grayscale image alphaIn for the foreground object’s alpha; a color image colIn for its color; and a background color image backIn. If these three images have already been loaded in memory, createComposite() computes computes one color composite, compOut, according to the matting equation. Return values follow the conventions of the triangulationMatting() method.

Part 2. Bonus component: E  cient implementation (up to 10 Marks)

Implementations that beat the reference solution’s speed by a signi cant amount|without compro-mizing correctness|will receive up to 10 bonus marks. To get these marks you must include in your submitted report (see below) what optimizations you used, and your timings will be veri ed by the TAs.

Part 3. Experimental evaluation & report (25 Marks)

Your task here is to put the triangulation matting method to the test by conducting your own experiments: use your a camera you own to capture images suitable for triangulation matting, and then run the technique on them. Any camera will do|cellphone, point-and-shoot, action camera, etc. You are welcome to use the reference implementation for these experiments (i.e., you don’t need


2

to have your code fully functional in order to get started on this part of the assignment).

The main thing we will be looking for here is the degree to which you were able to (1) drive the method to its limits, and (2) understand what these limits are, i.e., the range of conditions under which we should expect the technique to work well. To that end, you should experiment with di erent imaging conditions|di erent foreground objects, di erent materials, di erent backgrounds, di erent light levels, etc. The speci c objects and the total number of examples you show are not as important as the conclusions they help you draw. To that end, you are encouraged to try the technique on many examples and only later decide which ones to show and discuss in your report. We expect that you will need to capture at least 5-10 sets of input images to get a sense of the triangulation technique’s strengths and weaknesses.

Your report (PDF format only): Write a report detailing your experiments and place it in the le 320/A1/partA/report/report.pdf. You may use any word processing tool to create it (Word, LaTeX, Powerpoint, html, etc.) but the report you turn in must be in PDF format. At the very least, your report should include the following: (1) the procedure(s) you used to capture your images; (2) the range of imaging conditions you tried; (3) an assessment of the technique’s limits as explained above; (4) a set of gures showing experimental results that support your conclusions; and (5) if you think that none of your experiments were successful, explain why and describe the steps you took to overcome your di culties.

When showing results from a speci c experiment, you should include (a) the four input images;

    (b) details on the camera you used and its settings, (c) the alpha and color images computed by triangulation matting; (d) any composites you created from those images (only if needed to support your conclusions); and (e) zoomed-in and cropped versions of the above (only if needed to support your conclusions). In all cases, make sure that the images in your report are large enough to view comfortably on a regular printed page (e.g., Figures 1 and 2 in Smith and Blinn’s paper are good examples to follow).

The directory 320/A1/partA/report/ should contain nothing other than your report. In particular, save the images you captured for your experiments and for your report but do not submit them with your code (this would take too much space). Be prepared, however, to supply them upon request by the TA or the instructor.

Part 4. Written question (15 Marks)

Apply triangulation matting to the images in 320/A1/partA/test images/small and save the results in tif format (so that no details are lost to compression). Observe that the alpha matte on the right side of the vase has zero or near-zero intensities whereas on its left side the intensities are low but not zero. For example, expressed as an integer in the range [0; 255], alpha[829; 520] = 0 whereas alpha[810; 40] = 29. The latter implies that there is a foreground \object" to the left of the vase, and that the object is not totally transparent (e.g., = 29=255 0:11). Why would this pixel (along with many others to the left of the vase) have non-zero alpha? Try to be as concrete as possible.


Your answer should be included in your PDF report: report.pdf









3

Part 5. Bonus component: Live matting (up to 10 Marks)

A major limitation of the basic triangulation matting technique is that the foreground object must be photographed sequentially against two di erent backgrounds while it remains motionless. As a result, using the technique to compute the alpha of a moving foreground object is highly non-trivial. In theory, one way to do this would be to somehow capture images of the foreground object against two di erent backgrounds simultaneously. Suggest techniques that might let you do this, and justify your answer. If you wish, you can do a literature search to help you solve this problem. If you do nd any related work, be sure to cite it in your report and explain how it relates to your answer.

Your answer should be included in your PDF report: report.pdf




What to turn in:  Please submit the following  les on MarkUs:


CHECKLIST.txt algorithm.py report.pdf

along with example output images from your report.



Bonus policy: You are strongly advised to nish all the required components of an assignment before tackling the bonus questions: submissions with even one required part substantially incomplete (or incorrect) will not be awarded any bonus marks.



Working on non-CDF machines: You are welcome to work on the assignment on a non-CDF machine. That being said, your implementation must run on the Linux CDF machines in order to be marked by the TAs. You should therefore test your code on CDF frequently, to make sure it has no CDF-speci c issues.

All required packages have already been installed on CDF/Linux. Here are the steps I followed to install them on OS X 10.10+ :

    1. Install NumPy and related packages for scienti c computations: http://stronginference.com/ScipySuperpack/

    2. Install OpenCV 3.1: http://blogs.wcode.org/2014/10/howto-install-build-and-use-opencv-macosx-10-10/




Freely-available resources on NumPy, OpenCV, Computer Vision Programming, etc:

    1. Short NumPy tutorial by Olessia Karpova (CSC420, 2014): https://github.com/olessia/tutorials/blob/master/numpy_tutorial.ipynb

    2. Jan Erik Solem, Programming Computer Vision with Python, O’Reilly Media, 2012 (preprint): http://programmingcomputervision.com/ (look at Chapters 1 and 10)


4

    3. OpenCV-Python documentation (Intro to OpenCV, Core Operations, Image Processing in OpenCV): http://docs.opencv.org/3.1.0/d6/d00/tutorial_py_root.html#gsc.tab=0

    4. Matplotlib User Guide (especially Chapter 5.5): http://matplotlib.org/1.5.1/Matplotlib.pdf

    5. NumPy Reference Guide (especially Chapters 1.4, 1.5, 3.17.1-3.17.5): http://docs.scipy.org/doc/numpy/numpy-ref-1.10.1.pdf

























































5