Homework 2 - Mosaic Maker
Navigation Path : Home Page > Computer Vision Homeworks > Homework 2 - Mosaic Maker
Preamble...Input Data and Results - Data set #1 - A town in the mountains
| Input Data |
There is a large translation between Image 1 and Image 2, A translation and a rotation between Image 2 and Image 3, A translation, rotation and warping between Image 3 and Image 4 |
| Image Correlations (Automatically detected) |
   |
| Final Mosaic |
 |
Input Data and Results - Data set #2 - An indoor Panorama
| Input Data |
The images were taken by rotating a camera and photographing the room at different angles. |
| Image Correlations (Automatically detected) |
   |
| Final Mosaic |
 |
Input Data and Results - Data set #3 - An outdoor panorama
Source images can be provided on request... (There are simply too many.. and will clutter up this page...)
Algorithms
FindMatchingPoints (Input: Img1 = The first image, Img2 = The second image)
- Perform histogram equalization on Img1 and Img2 to adjust for lighting differences.
- GridSize = 1/8 of the smaller of the two images. This is based on the assumption that the two images have at least 12.5% of images space common.
- Repeat until 15 correspondences are found
- Randomly pick (X, Y) coordinates in the 1st image
- If (X,Y) points have been picked before go to step 3.1
- ImgBox = A portion of Img1, starting at (X, Y) with a width and height of GridSize
- Correlation = Calculate the correlation between ImgBox and Img2 using SSD.
- Range = Max (Correlation) - Min (Correlation)
- Get the maximum correlation and count the number of points which have a correlation value greater than Max(Correlation) - Range / 100
- If the number of points = 1, the pick the point otherwise discard the point as it is not a good match.
- Call CleanPoints to clean the erroneous points found during the algorithm.
- Display the point correlations to the user, so he can say how cool the algorithm is :)
CleanPoints (Input : P = Point Correspondences )
- pointCount = the number of Point Correspondences in P
- M = Create a mask with pointCount rows and pointCount * 4 columns
- For each column
- Randomly set 4 cells to 1, and set the others to 0
- For each column in M
- P2 = Select the 4 rows which have 1s, and select the set of points from P which correspond to those rows
- hom = GetHomography ( P2 )
- P3 = Use the hom on the original point set P of the first image.
- Error = The difference between P3 and the points of the second image in P.
- TotalError = TotalError + Error
- Sort the Total Error in ascending order by the value of the error, and return the 4 points with the lowest error values.
GetHomography (Input : P = Point Correspondences )
- B = A matrix created using the X, Y coordinates of the 2nd image
- A = A matrix created by applying a transformation on the X, Y coordinates of both images
- Calculate X = A\B (When there are more equations than functions, a least square errors method is used to calculate the best fit)
- Return X
Mosaic (Input : Images, Homographies between each image)
- Collect all the homographies (and inverse homographies).
- Compose them so they are in respect to the initial image.
- Use the composite homography inverses to find the coordinate points of all images in the initial image coordinates.
- Find the min & max for both axes for all the corners and create the result image so that it will contain all input images.
- Iterate over the result image, filling in as much new detail (using a mask to determine what is "new") per image is possible.
- When all images are exhausted, return the resultant image.
Strengths and Weaknesses (And how we might fix them.. hopefully.. someday.. maybe.. )
FindMatchingPoints
- As the algorithm uses a large block size and finds correspondences using SSD, this works very well even for images which have large translations.
- However since the correspondence assumes that the images are close to the same orientation, in image pairs which have very large rotations and very large warps, the correlation matches are not very accurate. In order to fix this problem, the correlation needs to be calculated at many rotations.
- As this algorithm uses a block sized 1/8 the size of the smaller image, if the two images have less than 1/8 of area in common, then the point correspondences found have a very high probability of being wrong. This can be fixed by reducing the size of the block, however this might also result in some bad matches as there can be repeating patterns of small blocks which could have high correspondence values, but are actually invalid.
- There is no guarantee on the spread of the points in the image, therefore small errors in the point detection can multiply when the homography is applied on large images. An improvement to this would be to attempt allocating points which are spread throughout the image. However, this would be limited on the amount of overlap between the images.
CleanPoints
- This algorithm is coded on the assumption that the majority of the points in the original point set are valid. However, if a significant percentage (greater than 50%) of the points in the original point set is invalid, this algorithm will return the wrong set of points. Hmm I guess the only way of fixing this problem would be to make sure that the FindMatchingPoints method has an accuracy of above 50% (which it does :)
GetHomography
- The only weakness in this method is Garbage-in-Garbage-Out :)... Other than that, it delivers its promise.
- However looking at our data sets it seems that although the points are matched perfectly, the homography does not work too well when the camera is rotated, and objects which have different depths are photographed. Our guess is that the homography cannot capture this type of motion.
Mosaic
- The Mosaic algorithm is pretty straightforward. We initially tried blending images that overlapped to produce smoother images, but the resultant images did not look very good and it took a fair amount longer. In the end, we opted to have the images take precedence in order of input. The result is that the output is very dependant on the order of the images and homographies that are input. This can be both good and bad. It can be good in the sense that we can hand tailor the output to look best given any set of images, but bad in the sense that sometimes it will take a fair amount of guesswork to determine the best sequence. It would be nice, though probably difficult, if the mosaic algorithm could determine which images to display first based on relative image positions or the certainty / quality of the generated homographies.
