Red displacement: (-1, 8)
Green displacement: (0, 3)
The goal of this assignment is to align three slightly offset photos that were taken with a red, green, and blue lens filter. To accomplish this, I created a base implementation which rolled each red and green image to align with the blue image. This base implementation checked the L2 loss between the pixels of the two images to determine if the values were close, acting as a proxy measure of similarity between the images.
After the base implementation, I implemented a more efficient pyramid-based approach. This approach first downsamples the images into an image pyramid, computing the alignment at coarser levels before moving to more fine-grained levels. This approach saves computation cost by reducing the number of pixels to compare at each level.
After this, I implemented iterative "bells and whistles" improvements:
In this implementation, I would roll the red and green images to find the lowest L2 loss with the blue image. To reduce the runtime, I only calculated the L2 loss between two images within a certain offset range, ranging from [-15,15] in both the x and y directions.
I originally tried using padding along the edges and displacing the image instead of rolling, but I found that the loss contributed by padding was either too high (when padding by 0) or too low (when extending edges), resulting in no image displacement or entirely too much displacement.
For larger images, it is inefficient to compare every pixel in the image. Instead, I implemented a pyramid-based approach, where each higher level of the pyramid is 1/4 the size of the previous level (accomplished by blurring, then subsampling every other row). Now, we can perform coarse alignment using the lower resolution levels, and perform fine-grained alignment at the higher resolution levels.
In my personal implementation, each level checks displacement of range [-4,4]. Theoretically, we should only need a range of 2, but I found that giving slightly more wiggle room in the higher resolution images tended to improve image quality without much sacrifice in runtime. Additionally, I changed my L2 loss to only include the central region of the image. This should reduce computation time and also reduce the influence of the messy edges of the images.
When performing automatic contrasting, I first checked to see if I could rescale image intensites from some small intervals to the full range of 0 to 255. However, the image ranges are already very close, so changes would have minimal impact.
Instead, I tried a few different piecewise scalings to see if any would work well. I ended up creating a mapping where the lowest and highest 40 pixel intensities would be reduced to 25% and the rest of the intensity ranges would scale to fill in the extra details.
Rather than aligning based on translation or rotation, or using gradients or edges for the features, I decided to implement SIFT to find keypoints. Then, I matched keypoints using RANSAC and found the homography matrix to transform from one image to the other.
I then used openCV's cv.warpPerspective() to transform the images to the same
alignment as the blue image. This method can handle more complex transformations, can
search globally instead of a local search, and is fairly fast thanks to optimizations made
made by the openCV library.
The alignment clearly works to align better than the original image, but what about when comparing to our earlier alignment algorithm? It turns out that the result is very good. There are very few artifacts that come from misalignment. This makes sense as we can account for any type of affine transformation, and we are very intelligently using features along with RANSAC's "voting-based" system to select the best transformation.
Automatic cropping turns out to be extremely difficult. I tried several different attempts including using SIFT features, color gradients, among other methods. I finally settled on a more conservative approach, so sometimes, artifacts remain. However, the cropping algorithm doesn't overcrop semantically important regions.
The current algorithm starts at the edge and moves inward, line by line, until it encounters a large enough change in color channels. If the change is large enough, it will crop away every line that it has passed so far. Then, it begins again with the new color. The algorithm continues until it reaches a region with a lot of color changes in rapid succession, or it continues for a long time without any changes in color. By doing this, the algorithm searches for uniform color bands and crops them away. The minimum and maximum lengths of the color bands to be cropped were set by me to be on the conservative side.
There is also a minor offset, where after a band ends, the cropping algorithm will automatically skip a few lines before continuing to check for boundaries. This prevents the cropping algorithm from detecting the same band edge multiple times, since most boundaries are not perfectly straight.
To do a color mapping, I had to perform an intelligent crop first to reduce the number of noisy color pixels that contribute to the color scheme. After that, I used openCV's white balance algorithm to adjust the color channels. In particular, the white balance algorithm assumes that the color channels should add up to a gray value, so it adjust the color channels to fit this assumption. I included all pixel intensities in the calculation, as I have cropped out most of the unnecessary pixels from the image.
