Introduction
In this assignment, I implemented an image-aligning algorithm to align three grayscale photos of the same scene (taken using a red, green and blue lens respectively) into a color image. For high-resolution images, I sped up processing time by using an image pyramid. In addition, I also implemented an automated cropping feature that removed, with varying success, the borders of low-resolution images.
The images were taken from the Prokudin-Gorskii collection owned by the Library of Congress. Sergei Miklhailovich Prokudin-Gorskii was commissioned by the Tsar to travel around Russia in the early 20th century to photograph various scenes of the empire. He took three shots of each scene, in red, green and blue respectively, and combined them together to achieve a color photo.
Here are some examples of the photos taken:
Image Alignment Algorithm
The image alignment algorithm takes in four parameters - the former two are the images to be aligned (A and B), and the latter two are the number of pixels we wish to check for along the x and y direction respectively to achieve the alignment (X and Y).
We first crop A and B, since their borders will make it impossible for us to get the best-possible alignment. Then, we use two for loops, one varying the shift in the x direction, the other varying the shift in the y direction, and calculate the sum of squared differences each time. If this is lower than a variable which keeps track of the lowest sum after each iteration, we update the value of the variable. Finally, we return the shift vector that gives us the lowest sum.
Here are some of the low-resolution images that have been aligned and cropped (see Border Cropping Algorithm):
Image Pyramid Algorithm
This algorithm allows us to align higher-resolution images more quickly. It takes in the same four parameters as the above algorithm. Both images are shrunk several times, each time by an order of magnitude ("scale") determined by a variable, till they are smaller than a pre-determined height. This is the same as "going up" the pyramid. As we move up the pyramid, we store the smaller copies of both images in cell arrays.
After shrinking the images, we start at the top step of the pyramid and slowly work our way down. At each step, we use the image alignment algorithm described above to align both images. We then move down one step, and shift image B by a shift vector that is the shift vector returned by the image alignment algorithm in the previous step multiplied by the scale variable. We then align both images again, this time checking fewer pixels in each direction than we did in the previous step, and we also adjust the shift vector. This continues until we finally reach the bottom step.
These are some of the high-resolution images that have been aligned using this algorithm:
Border Cropping Algorithm (Extra Credit)
This algorithm crops the borders of low-resolution images. It takes in the image and a user-determined threshold for border detection (the higher the figure, the more sensitive the method is to a border, to the extent that it might crop away some parts of the photo that are not borders).
To determine how much of the top border of the red image to crop, we move down the rows from the top row. At each row, we calculate the average of the intensity of the pixels. If this is darker or fairer than our threshold allows, we continue to the next row. We keep iterating in such a manner until we go within our threshold. We then return the number of rows that we have advanced, to be removed from our image. The same logic applies for the other three directions, and the other two color tints. We make sure that the same crop is applied to each color layer by using the maximum figure returned across each layer in each direction.
As you can see, this algorithm has had varying success across the different images tested. It managed to crop out a good amount of the border for some images, but for others, it did not remove much of the border.
Here are some of the low-resolution images that have been aligned and cropped (see Border Cropping Algorithm):
