Project 3: Homography

Jordan Kaye, 11/06/10

Main idea:

The goal of this assignment was to write an algorithm to apply a homography projection of one image onto another. As we learned in class, a homography is a transformation matrix that can be determined from a two sets of four corresponding points. By treating these four points as a convex quadrilateral region, we can choose two quadrilaterals on two different pictures, and project one of the regions onto the other picture. This allows us to created interesting combinations of pictures without any noticeable artifacts.

Algorithm:

The algorithm to accomplish the homography projection is fairly straightforward. First, the sets of points must be determined from user input. Once the points have been supplied, the homography is computed and then applied to the first input image. Once the homography has been applied, all that's left is to combine the two images. To complete the projection without artifacts, two bitmasks are created: one to isolate the projection from the first image, and the other to remove the projection area from the second image. The bitmasks can then be applied to their respective images (through simple multiplication). After the masks have been applied, the two images can be added to complete the projection.

Psuedocode:

Get sets of points from the user
Compute homography
Determine area over which homography should be applied
Apply homography over the given area of the first image (set over a zeroes matrix with the same size as the second image)
Get a bitmask of the convex hull of the four points supplied for the second image
Get the inverse of the convex hull bitmask
Apply the convex hull bitmask to the result of the homography
Apply the inverse convex hull bitmask to the second image
Add the second image to the result of the homography

Results:

The results using this algorithm were very good. Because the set of points is forced into the convex hull before the bitmask is extracted by using poly2mask, the problem on concave quadrilaterals was resolved. Even if points are given in non-corresponding order, the algorithm simply interprets this as an intentional attempt to rotate the projection and applied the homography accordingly. This allows for even more interesting results than originally intended. Some examples:

The first image (quadrilateral to be projected):

Applying the points in corresponding order:

Applying the points in reverse order:

As we see, even though the points were technically applied in an incorrect order, the homography could still be calculated the the projection was applied without any problems.
Different portions of the first image can be used as well:

Using this as our initial image:

We can create projections like:

Limitations:

There are two main limitations to this algorithm. One is shown in the last example image: if the projection is from a small area to a large area, the projected region becomes very pixelated due to the enlargement. This is mostly unavoidable, although some smoothing or other corrective measure could be applied. The second limitation is somewhat more serious: if the user inputs points in a way that doesn't make sense (for the homography calculation), the projection becomes completely useless. A good example of this can be seen here:

First image:

Projected image:

This happens because the homography is ruined by the point selection. The first quadrilateral was selected in clockwise order, but the second was chosen as upper-left, lower-right, upper-right, lower-left. This causes a bad calculation. It is impossible for the algorithm to detect something like this because it can never tell what the user is trying to do; it is up to the user to avoid this situation.

The algorithm is successful. Although it is not perfect (in the case of the bad homography), it fully accomplishes the original goal in a fast and efficient manner.

Source code:

homograph.m
compH.m (supplied by professor)