15-463: Project 1: Colorizing the Russian Empire

Student: Kristin Siu (kasiu)

Implementation

Implementation Details

My implementation for this was in Matlab (a venture into more unknown math software territory)!

I implemented template matching using the sum of squared differences method such that the sum was minimized. I then extended this to work with image pyramids. Overzealous variable clearing was used to keep out-of-memory errors from occuring.

Even with this naive implementation, it was not enough to align the images perfectly. This is because the borders do not allow for adequate difference checking. My solution to this (attempted many times and finally solved) was to circshift the image and then run SSD only the middlemost portion of the image. In addition to being faster (summing a smaller image), it also takes advantage of the fact more stuff is in the center of the picture, which means the difference check is more accurate.

Results!

.jpg images

These were run on the recursive image pyramid algorithm with depth 2 on. With the original implementation, only about half of these actually looked this good.

Red offset:(13,1)
Green offset:(5,1)
Red offset:(10,1)
Green offset:(5,2)
Red offset:(-4,1)
Green offset:(-3,1)
Red offset:(10,0)
Green offset:(1,0)
Red offset:(13,-4)
Green offset:(6,-2)
Red offset:(11,3)
Green offset:(6,2)
Red offset:(14,3)
Green offset:(6,2)
Red offset:(12,1)
Green offset:(6,2)
Red offset:(16,1)
Green offset:(7,1)
Red offset:(17,-1)
Green offset:(8,0)
Red offset:(18,1)
Green offset:(8,1)
Red offset:(12,3)
Green offset:(5,2)
Red offset:(13,0)
Green offset:(8,0)

.tif images

The first five .tif images were run on depth 4. They have been downsized to .jpg images of width ~600 for this website.

You're properly wondering why the sixth image looks so utterly miserable? I've been wondering why it looks so miserable too, as it's been run on different depths with different windows and everything. My theory is that either recursing too far is causing one of the layers to have an initial alignment that was radically off such that no good window could be established.

The last image needed a run on depth 5 to achieve proper alignment.

Just in case you don't believe they're aligned, here's a bit of detail on the on 4th image at its full resolution. This was chosen because the detail was nice!

And now for the actual images!

Red offset:(86,32)
Green offset:(42,6)
Red offset:(134,-13)
Green offset:(13,-8)
Red offset:(129,13)
Green offset:(60,13)
Red offset:(77,33)
Green offset:(24,19)
Red offset:(114,12)
Green offset:(55,8)
Red offset:(60,-60)
Green offset:(60,44)
Red offset:(147,62)
Green offset:(70,38)