Project 6
Image Mosaic

Yong He

PART I & II

Time Square (From Empire State Building)

1. Introduction

In this project, I implemented an image stiching algorithm to generate a panorama. The algorithm works as follows: 1) find correspondance points of two images; 2) compute a homography transform that translates second image into the view space of the first. 3) blend the images. The correspondance points can be specified by hand or discovered automatically, both methods are implemented in the project.

2. My implementation

The project framework is written in Matlab, with core functions(e.g. matching feature points) implemented in C++ for better performance. The tricky part of this project is automatically finding correspondance points and construct a homography transformation matrix.

The correspondance points are found using following process:

1) Compute all feature points using harris corner detector in bothe images

2) Use the following automatic non-maximal supression algorithm to select a fraction(500) of most important feature points that distributes evenly in image space:

	while (ptsRs.size() < m && radius > 2.0)
	{
		double r2 = radius * radius;
		for (int i = 0; i<n; i++)
		{
			if (!inserted[i])
			{
				bool suppressed = false;
				for (int j = 0; j<ptsRs.size(); j++)
				{
					if (Distance(ptsRs[j], points[i]) < r2)
						suppressed = true;
				}
				if (!suppressed)
				{
					inserted[i] = true;
					ptsRs.push_back(points[i]);
					if (ptsRs.size() == m)
						break;
				}
			}
		}
		radius *= 0.1;
	}

3) Extract a patch for each selected feature point. This is done by taking the nearest 8*8 pixels in a 1/5 downsampled image in gray-scale. Normalize the patch by: a) compute the average; b) compute the standard deviation; c) subtract every pixel in the patch by average and divide by standard deviation.

4) Math the patches and produce correspondance pairs. Discard the feature points whose error of second best match is close to best match. I used 0.3 as discarding threshold.

To construct homography transform, I used method discribed in this article. Basically, if (x1,y1) corresponds to (x1', y1'), let