CSC320 Visual Computing: Assignment 2: Beier-Neely Image Morphing
In this assignment you will implement and experiment with Beier-Neely image morphing, a technique for morphing between two images by interactively specifying corresponding lines in them. The technique was used for the production of Michael Jackson’s “Black or White” video back in 1991, and proved extremely influential. You can read more about its backstory here. In addition to completing the implementation of Beier-Neely morphing, you will also implement bilinear interpolation and super-sampling, both of which are essential for producing high-quality morphs. Robin Swanson covered the technique in Tutorial#5, which should be available online on Quercus on February 10.
Goals: The goals of this assignment are to (1) give you a understanding of more general forms of image warping that the linear warps in A1; (2) implement interpolation and anti-aliasing and gain first-hand experience of the rather dramatic image quality improvements they provide, and (3) last but not least, read your very first computer vision paper and learn how to turn its algorithmic descriptions into actual code!
Reference solution: We are providing a reference implementation of the algorithm that you can use to compare to your own. The reference code is encrypted, so you can only run it, not see it. Bonus: Our baseline expectation is that you will rely on for-loops for your implementation. Forloops are fine for prototyping—and you will get full marks if your implementation is correct—but they result in very, very slow code. You are welcome to take advantage of NumPy and vectorization to speed up your code; if you do so, you will receive bonus marks depending on its speed relative to the reference solution.
Important: While the due date for the assignment is 2.5 weeks away, it is strongly advised that you read Beier and Neely’s paper and go through the supplied code in the next 3-4 days, and then begin coding as soon as possible. Plan to spend some time looking at the code already supplied, as you will have to depend on it for your implementation.
Location of your code: Your implementation will wholly reside in viscomp/algos/a2.py. You will not need to make modifications to anything else in the codebase.
Testing your implementation: Your implementation will be tested on the teaching labs Linux machines, by running app/a1/a2 tests.py, possibly more tests added. Make sure you can run these tests by following the instructions below and check that your output looks fine.
Overview of Beier-Neely Image Morphing
Given two source images, I0 and I1, the user specifies a set of corresponding lines in them to establish a correspondence between “features” in one image and “features” in the other. These corresponding “line pairs” are then used to warp the input images so that pixels “follow” the lines around them. To produce an intermediate image between I0 and I1, the line pairs are linearly interpolated to create an in-between position for the lines. This is done using linear interpolation with a single interpolation parameter t. In this interpolation, t = 0 produces a set of lines whose position is identical to that of image I0 while for t = 1 they are identical to image I1. The best way to understand the technique is to try out the reference implementation. See the file README.md for instructions on how to do this.
Part A.1
Basic Field Warping Algorithm (50 Marks)
The main component of the morphing technique is an image warping algorithm called Field Warping that you will have to implement. First, read through Beier & Neely’s paper to understand the overall method and the context. An important skill that you will need to develop while reading research papers such as this one is to focus only on those parts of the paper that you must fully understand to complete the assignment—you can ignore parts of the paper that require background knowledge you don’t have, or you can ask me or the TAs to explain those parts of the paper in more detail. Specifically, read Sections 1 & 2 for background and motivation behind the work. The sections you are asked to fully understand and implement are Sections 3.2 and 3.3.
For this part of the assignment, you will implement the following functions:
1. backward mapping (10 marks): This is the top-level function you must implement by completing the skeleton provided in the starter code. This function iterates over the destination pixels, calls the single- or the multiple-line pair Field Warping algorithm to find the source pixel and performs interpolation and/or super-sampling (if enabled) to fill the destination pixel. To implement it, you should implement the following helper functions listed below. You will receive 5 marks if you implement the basic version of this routine, without super-sampling or interpolation.
2. calculate uv (5 marks): This function should implement Equations (1) and (2) from the paper.
3. calculate x prime (5 marks): This function should implement Equation (3).
What to turn in
4. single line pair algorithm (10 marks): This function should implement the pseudo-code above Figure 1 in the paper, making use of functions calculate uv and calculate x prime.
5. multiple line pair algorithm (20 marks): This function should implement the second pseudocode from the bottom right of page 37 of the paper. This can make use of the single line pair algorithm.
Part A.2
Super-Sampling (15 Marks)
Extend your implementation of function backward mapping to include super-sampling. Your implementation should densely sample the destination pixel’s footprint according to the function’s supersampling parameter; compute the floating-point coordinates in the source image that correspond to each sample; and calculate the destination pixel’s value as the average of the source image’s value at those coordinates. Note that if interpolation is enabled, the value of the source image at a floating-point coordinate should be computed using bilinear interpolation.
Part A.3
Bilinear Interpolation (15 Marks)
A reference implementation of nearest-neighbour interpolation is provided in function interpolate at x for evaluating an image at non-integer floating-point coordinates. Extend it support bilinear interpolation as well.
Attention: You are expected to include very detailed comments in the code you submit, both at the beginning of the code segments you are asked to complete, and inline throughout your code. This is so the TAs can better understand the thought process behind the code you wrote. Code submitted with few or no comments may be flagged and/or not marked at all.
Part B: Experimentation (15 Marks)
As in Assignment 1, your task is to run the algorithm on your own data, as well as to “push” the algorithm to its limits, until image quality breaks down and artifacts begin to appear. Specifically:
1. Show at least one example where image quality is poor if bilinear interpolation is disabled.
2. Show at least one example where image quality is poor if super-sampling is disabled.
3. Save the results of running your implementation on the provided test suite.
4. Take your own photos using a smartphone camera or equivalent and create an image sequence of at least 20 frames that morphs between them. Try to be creative. If you cannot get your implementation to work or it is too slow, you can use the reference solution for this task.
5. All your results, including (1) the source and destination images, (2) lines employed, and (3) the parameter settings to reproduce the morphs and/or warps, should be placed in directory app/a2/results.
Part C: Write a lab report (10 Marks)
Your report should include your name, student number, and student username along with a discussion of your experimentation results. Specifically: (a) compare the results of your implementation and the reference implementation, pointing out differences between them and their possible causes; (b) identify shortcomings of the field field morphing algorithm, ie. instances where the algorithm produces noticeable artifacts; (c) explain the reason behind the quality improvement in items (1) and (2) of your experiments when bilinear interpolation and/or supersampling are enabled. Your report should be in PDF format. LaTeX, Word or even powerpoint can be used to create the submitted PDF. Bear in mind, however, that the report should be in a readable form, not just a bunch of photos with annotations and/or a couple of sentences. Assume the marker knows the context of all questions, so do not spend time repeating material from this handout or from the lecture slides. Place your report as a file app/a2/report/report.pdf. Important: Save the report as a .pdf, not as .docx or other format!
Part D: Bonus points (5-20 Marks)
Especially creative morphs will receive 5 bonus marks. Efficient implementations that employ vectorization for field morphing, super-sampling and/or bi
linear interpolation will receive bonus marks. A fully correct implementation that is at least 75% as fast as the reference implementation will receive 10 bonus marks. Vectorized implementations that also support bilinear interpolation will receive 5 bonus marks on top of that. Implementations that are faster than the reference and support bilinear interpolation will receive 20 bonus marks. Caution: No bonus marks will be given to implementations that are fast but not fully correct.
What to turn in
You will be submitting the completed CHECKLIST form, your code, your written report and images. Use the following sequence of commands to pack everything up. Important: After uploading the tarfile to MarkUS, download it from MarkUS, unpack it and verify that your code and all other assignment components are there! Students in previous instances of the course have accidentally submitted the starter tarfile instead of their own code and results, leading to major issues with marking—and wasting a lot of time for all involved. Because of this, there will be no accommodation for such errors this term: if you submit the starter code instead of your own code and/or submit no results, you will receive a zero on those parts of the assignment; if you discover this error a day later and want to re-submit, the standard late submission policy will apply. As stated on the course website, the course’s late policy includes a
brief grace period to allow you to quickly resubmit your tarfile a few minutes after the submission deadline without any penalty if you discover omissions in your submitted tarfile.