Computational Photography Programming #1

Matt Dee (medee@andrew)

At a high level, this implementation works by recursively scaling the image down to half of its size until it gets too small (in this case, when one dimension was less than or equal to 500 pixels). Then, it searches a all possible displacements of at most 20 pixels in any dimension, scoring them using the sum of squared differences for each pixel. This allows it to handle displacements of at most 4% the total image size, which was sufficient for all images I used.

Then, once it has calculated that offset, it goes back to the next larger level, applies the last offset, multiplied by two, and searches for displacements up to 4 pixels in any direction. This allows it to adjust to the smaller level being off by a bit. Once we reach the top level, we have the offset.

One trick that was necessary to get this to work was to ignore the edges of the image. In my implementation, I ignored the outer 3/4 in every dimension (3/8 on either side). This ensures that the edges of the panes do not mess with the scoring.

Another thing that helped was normalizing each of the color channels at the beginning (I divided each channel by the sum of the entire channel). This is because, in images like 00087u.tif, with a bright single-color thing (the rug in this case), it would favor putting the bright single-color area out of the image, since even when it was in the right place, the red channel would be very different.

With these two tricks, it seems to have worked on every image provided, plus a few that I chose from the library.

On the large .tif files, this implementation takes 20-30 seconds. This could probably be sped up by decreasing the displacement that we search on the larger versions, but this speed was tolerable and worked.