Homework 10: Image Stitching

NB – you may not use late days on this assignment.

A. Goals

The purpose of the Edit Distance assignments is to synthesize everything that you learned in the course. The specific goals of Part II are to:

Learn about computational photography
Work with images
Use external libraries and understand how to use API documentation

At the end of this assignment, you will have created a new application of CostMatrix.java from Part I to stitch two images together along a least visible seam. This is an algorithm used often in digital photography.

B. End-of-semester evaluation

Thank you for joining us this semester in CIS 110. We would like to ask you to fill out an anonymous evaluation to help us improve the course. This helps us improve our teaching for future semesters. This evaluation is more detailed than the Penn course evaluation.

C. Your program

In Part I of the Edit Distance assignment, you wrote the CostMatrix class to generate optimal string alignments. In Part II, you will use the same CostMatrix class to find least visible seams across two images.

You will write an ImageSeam class that contains two Picture objects for which CostMatrix can compute the minimum-cost seam. Below is the API:

public class ImageSeam implements Matchable
-------------------------------------------
public ImageSeam(Picture left, Picture right)      // constructs an ImageSeam object with
                                                   // the Picture objects left, right where left
                                                   // and right are of the same size
public ImageSeam(String left, String right)        // constructs an ImageSeam object with
                                                   // the images at filenames left, right
                                                   // where left and right are of the same size
public int height()                                // returns the height of left
public int width()                                 // returns the width of left
public int matchCost(int row, int col, char direction) // returns the squared color difference
                                                   // between the pixels at (row, col) of left
                                                   // and right
public void showSeam(Path p)                       // displays the seam represented by the
                                                   // Path object p
public Picture getStitchedPicture(Path p)          // returns a new Picture with left and
                                                   // right stitched along the seam p

As a reminder, we repeat the APIs for CostMatrix and Path.

public class CostMatrix
-----------------------
public static Path costRecursive(Matchable m)      // computes the minimum-cost alignment
                                                   // recursively and returns a linked list
                                                   // of Path objects representing the
                                                   // minimum-cost alignment
public static Path costIterative(Matchable m)      // computes the minimum-cost alignment
                                                   // iteratively and returns a linked list
                                                   // of Path objects representing the
                                                   // minimum-cost alignment

public class Path
-----------------
public Path(int row, int col, int cost, Path next) // constructs a Path object that represents
                                                   // the cost of matching
                                                   // the Matchable objects at (row, col); next
                                                   // points to the Path object
                                                   // that provided the minimum cost for this match

In addition, we provide a client program Stitcher.java that preprocesses the images to stitch only the overlapping areas.

D. Getting started

Download Stitcher.java. You may also need Picture.java, although the introcs installer should have set it up for you already.

Because this assignment depends upon hw09: Edit Distance, you will need to copy the following files into your directory for this assignment: CostMatrix.java, Path.java, and Matchable.java. If you have implemented CostMatrix.java correctly in hw09, you should not need to make any changes to these files for this assignment to work.

You will submit CostMatrix.java to run our tests for the ImageSeam.java class. You are welcome to update CostMatrix.java to correct bugs in CostMatrix.costIterative() and add tests, but you shouldn't need to if it is already working properly. You will not be graded for style on your CostMatrix.java code. Nevertheless, your CostMatrix class must compile, and your CostMatrix.costIterative() function should be correct, for all of our tests to pass; otherwise, you may lose points. (We will not use CostMatrix.costRecursive() for any of our grading on this assignment, so it does not matter if your recursive implementation doesn't work.) Your CostMatrix class must also be your own work, and you must record any help or outside resources in you help log as usual.

You will not submit EditDistance.java. If you used your EditDistance class to test CostMatrix, you can leave any references to EditDistance in your CostMatrix.main(), since we will compile your CostMatrix with a "dummy" EditDistance class on the server.

This assignment was created by Benedict Brown. It was adapted by Arvind Bhusnurmath, Max Tromanhauser, Neera Thavornvanit, and Scott Wang.

1. ImageSeam

A. Image stitching

Combining multiple images into a larger panorama is one of the oldest techniques in the field of computational photography, which combines computer algorithms with traditional photography to create images that are difficult or impossible to achieve purely with optical lenses. Camera lenses have a much narrower field of view than human vision, so a single photograph cannot capture an entire landscape as you see it. Panoramic stitching solves the problem by taking two overlapping images and "stitching" them together along a "least visible seam" into a single, large image, where the pixels to the left of that seam are taken from the left-hand image, and the pixels to the right are taken from the right-hand image. As long as the two images are nearly identical along the least visible seam, the seam will only be barely visible in the final image.

We restrict our image stitching implementation to seams that run down, right, or diagonally. This means that finding the least visible seam uses the same type of cost optimization as sequence alignment.

B. The `ImageSeam` class and the `Picture` and `Color` libraries

You will write an ImageSeam class that provides the methods necessary to allow CostMatrix to find the least visible seam.

The ImageSeam class implements the Matchable interface from hw09. Write the skeleton of the ImageSeam class according to the API in Section 0B, making sure that it implements the Matchable interface.

The textbook's standard library, which was installed by the introcs installer you ran in hw00, provides a Picture class. The API documentation for Picture is here.

In addition, because you will be working with Color values, you will need to include the java.awt.Color library in your ImageSeam class by including the statement

import java.awt.Color;

at the top of ImageSeam.java, before your class declaration. The booksite's documentation for java.awt.Color (which is actually built into Java) is here.

C. Methods and constructors for `ImageSeam`

When implementing the following methods, refer to the API documentation for Picture.

ImageSeam(Picture left, Picture right) constructs the ImageSeam object with the two Pictures left and right. If either left or right is null, or if the dimensions of right are different from those of left, then ImageSeam() should throw an IllegalArgumentException. Your class must not modify left or right in any way.

ImageSeam(String left, String right) constructs the ImageSeam object with the images given by filenames left and right. If either left or right is null, then ImageSeam() should throw an IllegalArgumentException. Avoid duplicating code between the ImageSeam(Picture, Picture) and ImageSeam(String, String) constructors.

height() returns the height of left (which is equal to the height of right, as enforced by the constructors).

width() returns the width of left (which is equal to the width of right, as enforced by the constructors).

D. `ImageSeam.matchCost()`

The least visible seam passes through the locations where the pixel colors are as close as possible between left and right. Therefore, the cost of stitching left and right along a seam passing through a pixel (row, col) will be the difference in color between the (row, col) pixel of left and the (row, col) pixel of right.

Because a pixel's color is comprised of red, green, and blue components, we will quantify the "difference in color" between the (row, col) pixels of left and right using this expression, called the squared pixel difference: (r_L - r_R)² + (g_L - g_R)² + (b_L - b_R)², where r_L is the red value of left's pixel (row, col), r_R is the red value of the right's pixel (row, col), etc.

matchCost(int row, int col, char direction) returns the squared pixel difference between the (row, col) pixels of left and right. The direction argument is ignored, but your matchCost() should check for invalid parameter values and throw IllegalArgumentException.

Refer to the API documentation for Picture and Color to implement this method. You should use the getRed(), getGreen(), and getBlue() methods of the Color object. Be careful: we have written the pixel coordinates above in the order (row, col), but the order of arguments for the pixel methods of Picture is specified as (x, y), which is actually (col, row).

Variable name change – We have renamed the i and j variables from the Edit Distance assignment to row and col, which are less confusing. You do not need to update Matchable.java even though it still lists the matchCost parameters as i and j; just name the parameters of the matchCost function in ImageSeam.java row and col. To maintain compatibility with Edit Distance, Path.java cannot change and will still refer to i and j. If you get confused, just refer to this table:

`Path`	`ImageSeam`
`i`	`row`
`j`	`col`

E. Checkpoint

Write tests in ImageSeam.main() to test the functionality of the ImageSeam class.

Save the images example-blue.png and example-red.png. Construct an ImageSeam object with these images, and pass it into CostMatrix.costIterative(). The cost of the resulting Path should be 129211.

2. showSeam() and getStitchedPicture()

We will now write utility methods to display the location of a seam, and stitch left and right into one new Picture.

A. `ImageSeam.showSeam()`

showSeam(Path p) should display the location of the pixels on the seam:

Construct a new, blank Picture
Iterate through the seam p and change the color of each pixel in p to a different color (say, white)
Display the resulting Picture

Refer to the API for Picture to find the correct method calls.

You should check whether the Path is null and throw a RuntimeException if so. However, you may assume that the cost values and pixel coordinates in p represent a valid seam.

Warning – Do not call Picture.save(). Doing so will break our test scripts, and you will receive a large point deduction.

B. `ImageSeam.getStitchedPicture()`

getStitchedPicture(Path p) should return a new Picture that stitches left and right, where the areas of left and right are overlapping. Pixels to the left of the seam and on the seam adopt the pixel colors of left; pixels to the right of the seam adopt the pixel colors of right.

Construct a new, blank Picture pic
Iterate through each pixel (row, col) in p and change the color of each pixel in pic to the left of (row, col), including (row, col), to the corresponding pixel color of left, and the color of each pixel to the right of (row, col) to the corresponding pixel color of right
Return pic

You should check whether the Path is null and throw a RuntimeException if so. However, you may assume that the cost values and pixel coordinates in p represent a valid seam.

Reminder – The i instance variable of each Path object corresponds to the row. The j instance variable corresponds to the col.

Warning – Do not call Picture.save(). Doing so will break our test scripts, and you will receive a large point deduction.

C. Checkpoint

Write tests in ImageSeam.main() to test the functionality of the showSeam() and getStitchedPicture() methods.

Construct an ImageSeam object with example-blue.png and example-red.png. The result you should obtain by calling showSeam() with the path from CostMatrix.costIterative() is shown below.

Download example-stitched.png – it is the image that you should obtain on calling getStitchedPicture().

3. Stitcher

A. Partially overlapping images

The getStitchedPicture() method of ImageSeam assumes that the stitching area overlaps completely between left and right and that the seam runs from the top left to the bottom right. The more common case is where the image stitching areas overlap only partially, and where the seam may be running in a different direction. To stitch such images together, we can specify the overlapping portion and the seam direction, and create an ImageSeam object with only this overlapping portion, flipping this image horizontally or vertically such that the seam always runs from the top left to the bottom right.

Figuring out how to crop out the overlapping portions of the images and flip them so the seam runs from the top left to the bottom right is tedious and involves a lot of trial and error. Instead, we provide the program Stitcher.java to do this cropping and stitching for you. It finds the overlapping portions of the two images, flips them so that the seam runs from the top left to the bottom right, uses an ImageSeam object to find the least visible seam for the overlapping portion, and embeds the stitched overlapping portion into the combined panorama.

B. `Stitcher`

Read the header comment for Stitcher.java to learn how to use it. To use it, you specify the two input images and the shift of the second image relative to the first image. Positive numbers for the shift coordinates shift the second image right and down; negative numbers shift it left and up.

Stitcher.java also allows you to specify a reference image; the pixels that differ between the stitched image and the reference image will be colored black. (Because of the possibility of multiple seams with the same total cost, there may still be some black pixels even if your program is correct.)

Download the images sea1.png, sea2.png, and sea-stitched.png.

Try running the following commands to test your program:

% java Stitcher example-blue.png example-red.png 0 0
% java Stitcher example-blue.png example-red.png 0 0 example-stitched.png
% java Stitcher sea1.png sea2.png 318 -7
% java Stitcher sea1.png sea2.png 318 -7 sea-stitched.png

The stitched images should look like the following:

A. Readme

Complete readme_imagestitching.txt in the same way that you have done for previous assignments.

B. Submission

Submit ImageSeam.java, CostMatrix.java, and readme_imagestitching.txt on the course website.

C. End-of-semester evaluation

If you have not yet filled out the anonymous end-of-semester evaluation, please do so now. Thank you for your valuable feedback.