Rather than write a completely new program for image stitching, you will modify your existing Match.java and EditDistance.java so that specific penalties are contained in EditDistance and Match will work for any problem that takes this form. You will then write an ImageSeam program that uses your modified Match class to stitch two images together.

Standard Libraries. In order to complete this assignment, you may need copies of StdIn.java and Picture.java in the same directory as your program.

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. Many recent cameras are capable of building panoramas out of individual pictures automatically. Surprisingly, a key part of the process involves the same kind of optimization as sequence alignment. The core if this program will therefore be the Match class that you wrote in Part 1. You will not need to modify this class at all.

The Problem. 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 gives a solution to the problem by taking two overlapping images and "stitching" them together into a single, large image. The same technique can be used to insert part of one image into another, for instance yourself into a historic picture.

Unless the images overlap perfectly, we need to combine them together cleverly so they appear to be one single image. One of the most successful way to do this is to find a "seam" where the two image are very similar. Everything to the left of that seam is taken from the left-hand image, and everything from the right is taken from the right-hand image. As long as the two images are nearly identical along that seam, it won't be visible even if the images are very different on either side of it:

First input image	Second input image	Two images stitched along the black line

First input image	Second input image	Two images stitched along the least visible seam

Finding the optimal seam. Let us start with the simple case where the images overlap perfectly, and we would like to fine a seam that runs from the upper-left corner to the lower-right corner (as in the red and green images above). Every pixel in the output image that is on the seam or to the right of it should come from the first image. Every pixel that is to the left of the seam should come from the second image. We will also restrict the seam to move right, down, or diagonally right and down. The seam is not allowed to wiggle back and forth like an S.

Along an optimal seam, the pixel values in the two images will be identical. When we can't find such a seam, we would like the seam to pass through locations where the pixel values in the two images are as similar as possible. Recalling that a pixel color is a combination of red, green, and blue values, we define the squared pixel difference to be: D = (R₁ - R₂)² + (G₁ - G₂)² + (B₁ - B₂)² .

If we take the squared pixel difference to be the penalty for letting the seam run through a particular location in the images, and the cost of a particular seam as the sum of squared differences of all pixels along the seam, we end up with the same dynamic programming problem as with sequence alignment, and we can solve it using a modified version Match.match(). Location (i, j) in the optimization matrix will track the cost of letting the seam run through pixel location (i, j) rather than the cost of matching character i in the first string to character j in the second string. But this difference in interpretation of the data has no effect on the process, so the same algorithm works for both problems.

Updating Match and EditDistance Rather than make two separate versions of Match, we can create one version that will work for both problems. The idea is to separate the process of finding the optimal path from determining the exact penalties for moving in any given direction. To do this, each program will need to provide Match.match() with a set of methods that it can call to compute penalties; EditDistance and a new class called ImageSeam will each provide Match.match() a different set of methods. This is where the power of interfaces and object-oriented programming in general starts to become apparent: we will define an interface that lists the methods Match.match() will need in order to compute penalties. EditDistance and ImageSeam will each implement this interface. Match will then be able to solve both problems without knowing which problem it is solving or what the data means.

The first step to generalizing Match is defining the interface it will use. Match.match() needs to know how many rows and columns the matrix should have, and it needs to know how to fill in the values and compute penalties. The value to put in each matrix entry is the minimum of the value if the path will continue on to the right, down, or diagonally, so the interface must include a way to obtain each of these three penalties. Furthermore, the lower-right corner is a special, base case where the path ends (i.e. it doesn't move any direction at all). There must be a way to get this information too. This leads to the following DataPair interface:

public interface DataPair
--------------------------------------------------------------------------------
  public int rows();                 // number of rows in the matrix
  public int cols();                 // number of columns in the matrix

  public int penalty(int row, int col, int dir);
                                     // penalty computes the cost of a path running
                                     // through (col, row) assuming it is coming
                                     // from the direction specified by dir
                                     //
                                     // if dir is -1 we are moving horizontally
                                     //    (i.e. from (col - 1, row) to (col, row)
                                     // if dir is +1 we are moving vertically
                                     //    (i.e. from (col, row - 1) to (col, row)
                                     // if dir is 0, we are moving diagonally



  public int basePenalty(int row, int col);
                                     // basePenalty computes the cost of a
                                     // path running through (col, row)
                                     // without considering the direction
                                     // the path took to get there

The method signature for Match.match() also needs to change, because it should accept any object that implements the DataPair interface rather than accepting two strings:

public class Match
--------------------------------------------------------------------------------
  static Path match(DataPair dp)  // return the optimal match between
                                  // the items specified by dp
                                  //
                                  // return null if dp == null or
                                  // if dp.rows() == 0 or dp.cols() == 0

  static void main(String[] args) // method to test Match (see Checklist)

                               
public class Path
--------------------------------------------------------------------------------
  public int row, col;          // the row and column this node represents
  public int cost;              // the matching cost from this point on
  public Path next;             // the next node in the optimal path

Once your new Match class is working, you will need to update EditDistance to work with it. To do this, have EditDistance extend the DataPair interface and add all the necessary methods and (private) instance variables. This means you will have to create an EditDistance object to keep track of the strings you are matching, and pass it as an argument to Match.match(). However your code to print out the optimal alignment will remain virtually unchanged.

public class EditDistance implements DataPair
--------------------------------------------------------------------------------
  public int rows()                  // length of the first string + 1
                                     // (i.e. number of rows in the
                                     //  alignment matrix)

  public int cols()                  // length of the second string + 1
                                     // (i.e. number of columns in the
                                     //  alignment matrix)

  public int penalty(int row, int col, int dir)
                                     // The penalty of matching at position
                                     // (col, row) in the alignment matrix
                                     // assuming we are following the direction
                                     // specified by dir

  public int basePenalty(int row, int col)
                                     // The penalty of matching at position
                                     // (col, row) without regard to direction
                                     // For EditDistance this is the same
                                     // as the penalty assuming we are moving
                                     // diagonally.
  public EditDistance(String x, String y)
                                     // create an EditDistance object
                                     // for the strings x and y

  static void main(String[] args)    // read 2 strings from standard input.
                                     // compute and print the edit distance
                                     // between them and output an optimal
                                     // alignment and associated penalties.
                               

Writing the ImageSeam Class With a generalized version of Match and updated EditDistance, we can return to the problem of image stitching. The problem as we described it above assumes the two images are exactly the same size and overlap exactly. The more common case where the images only partially overlap is shown in the sea image. We can reduce this to the simple case by ignoring the non-overlapping portions. The seam could run from upper-left to lower-right or from upper-right to lower-left depending on how the images overlap, but we can deal with this by flipping the images so that the seam always runs from upper-left to lower-right:

Figuring out how to crop out the overlapping portions of the images and flip them so the seam runs from upper-left to lower-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, rotates them so the seam runs from upper-left to lower-right, calls the ImageSeam class that you will write to stitch these together, then inserts the result into a combined panorama. The stitched sea images were created with the following command that specifies the two input images and number of pixels to shift the second image relative to the first image (positive numbers shift the second image right and down, negative numbers shift it left and up):

% java Stitcher sea1.png sea2.png 318 -7

Program and API Specification. Write a class ImageSeam to compute the optimal seam between two Pictures using Match.match(). Your class should compute the optimal path in the constructor, and store it and the two Pictures instance variables. Client programs can then call getStitched() to retrieve a new, stitched image. You class must conform to the following API:

public class ImageSeam implements DataPair
--------------------------------------------------------------------------------
  public int rows();                 // number of rows in the images
  public int cols();                 // number of columns in the images

  public int penalty(int row, int col, int dir);
                                     // return the base penalty of a seam running
                                     // through (col, row); ignore dir because
                                     // the direction the seam runs does not
                                     // affect the total cost in this application

  public int basePenalty(int row, int col);
                                     // return the squared pixel difference
                                     // between the two images at (col, row)

  public Picture getStitched();      // return a new image stitched along the
                                     // optimal seam between a and b based
                                     // on the path computed in the constructor
                                     //
                                     // if the optimal path is null, return null

  public ImageSeam(Picture a, Picture b)
                                     // compute the optimal path between a and b
                                     // using Match.match()
                                     //
                                     // if a or b is null, or the width or height
                                     // of a or b is zero, or if the width or
                                     // height of a and b differ, set the optimal
                                     // path to null

Because you will be working with Color objects, you should include the statement

import java.awt.Color;

at the top of your file, before the class declaration. You can test this program using Stitcher.java, but you can also write your own main() method in ImageSeam that runs simpler tests if you wish.

Testing. You can use the images from the stitched examples above (example-green.png, example-red.png, example-stitched.png, sea1.png, sea2.png, and sea-stitched.png) to test your ImageSeam class. We generated the stitched version by running the following commands:

% java Stitcher example-green.png example-red.png 0 0
% java Stitcher sea1.png sea2.png 318 -7

Stitcher.java also contains a testing mode to help you test your ImageSeam. You can optionally specify a reference image as the last argument, and it will show where your stitched version differs from the reference images. For instance,

% java Stitcher sea1.png sea2.png 318 -7 sea-stitched.png

will display an all white image if your stitched version is identical to our "ground truth" image sea-stitched.png. Any pixels that are different will be colored black. Note that you may get some black pixels even if the program is correct because there are sometimes more than one seam that have the same total cost.

In addition to your ImageSeam.java you should submit a zip file containing at least two pairs of test images that you used to test your program (and the result of stitching them). You may use existing images or create your own. We will award one point of extra credit if at least one of your image pairs is particularly clever or creative. Include instructions in your readme_dynprog.txt file for running Stitcher with your image pairs.

Checklist.   Don't forget to read the checklist.

Submission.   Submit the files Match.java, EditDistance.java, ImageSeam.java, a zip archive images.zip containing your images, and your readme_dynprog.txt. Your images must be contained in a zip archive, not in any other format (e.g. rar), or you will receive a significant deduction for breaking our testing scripts.