Image Alignment and Stitching
Today, we're going to talk about making panoramas. Panoramas sound simple enough, since they are implemented in most consumer cellphones. The question was, "How difficult can it be"? It turns out there are many, many components under the hood, each with a specific subset of details.
Many tools are not just to make panoramas, but have a lot of broader applications.
We want to put multiple images in a single larger photograph.
Panorama of Shanghai, China. Great city by the way. :)
Camera representation of a panorama.
All of these images have overlapping regions, indicating that we cannot directly align them.
We can use SIFT features to find corresponding points that correspond to the same real world scene point, then we can find the geometric relationship between the locations of these corresponding points. For each point in the image, we find a mapping that maps one location to a corresponding location in another image.
SIFT Feature mapping.
Eventuall we want to warp all the pixels in the image after using SIFT for different 3D images.
Then we want to make blended images, to remove hard seams. Image warping is a way to manipulate images.
The coordinates of an image can change, or Warp.
g(x,y) = f(Td(x,y))
We define a mapping from original pixel coordinates to final coordinates. Each pixel can be matched to any arbitrary shape including circles, trapezoids, etc.
T can be represented by a matrix. A 2x2 matrix happens because of linear 2D coordinates.
For scaling an image by a factor of a in the X axis and a factor of B in the y axis, perform the following operation:
Just inverse the values to 1/a and 1/b if you want to reverse the image back.
For 2d rotation, x1 = r cos φ and y1 = r sin φ. Imagine a triangle. If you get new coordinates with angle theta, x2 = r cos (φ + θ) and y2 = r sin (φ + θ).
So for forward rotation, x2 = x1 cos θ + -y1 sin θ and y2 = x1 sin θ + y1 cos θ.
For inverse rotation, x1 = x2 cos θ + y2 sin θ and y1 = -x2 sin θ + y2 cos θ.
For horizontal skew, x2 = x1 + my1 and y2 = y1.
This is different and inverse for the vertical skew. x2 = x1 and y2 = y1 + mx1.
If I want to flip the mirror about the Y axis, x2 = -x1 and y2 = y1. It is almost the identity matrix, except the first element is -1.
If I want to flip about line y = x, I get the transpose of the identity matrix.
All these transformations will:
1. Preserve the position of the origin
2. Have the lines map to lines
3. Have the parallel lines remain parallel
4. Is closed under composition.
The homogeonous representation of a 2D point is basically a 3D point (x tilde, y tilde, z tilde) where x = xt
8 Unknowns, 2 equations for a corresponding pair, and 4 pairs of matching points minimum. 
(2,4,2) is a homogenous relationship to (1,2), due to factorization.
Below I will illustrate very clearly how to convert from homogeneous coordinates.
The following is a list of transformations.
Affine transformation can be used for translation, rotation, scaling, etc. This is where the third row is 0, 0, and 1. and the other rows are a11 a12 a13 a21 a22 a23, etc. Affine transformations do not necessarily map to the origin. They can do anything that linear transformations can do, but also translation.
Affine transformation preserves lines and parallelism. Projected transformation doesn't have to preserve anything at all.
The lines are still connected, but the lines don't necessarily preserve parallelism.
A geometric way of mapping is to define a pinhole and shoot rays through the pinhole.
Convert the pixel to a homogenous matrix and multiply a new vector with the homography matrix. For final values, divide by the first z value. If q = (1, 2, 3) the coordinates are (1/3, 2/3).
The matrix is defined only up to a scale. If we scale a homography matrix, it really doesn't change anything, since they only have 8 degrees of freedom despite having 9 entries.
We want to fix the sum of squares of all the entries of the matrix to 1.
This means that we cannot arbitrarily change individual entries of the homography matrix.
We compute homography and using these images we can compute the plane and figure out stuff so thn we finally are able to know where the scene is for real.
Warping and blending are the next steps.
Original and warped image.
The final step is to smartly blend images to remove the seams.
A homography has 8 degrees of freedom because the matrix is defined only up to a scale.
Scaling a matrix does not change the coordinate at all.
How do we compute a homography given a pair of images?
We want to find a homography such that the red points are mapped to the corresponding green points.
This is sufficient information to compute the homography between these 2 matrices.
We can rearrange the image into a linear equation after some computations and combine the following equations.
The matrix dimensions are 2n * 9. There are 9 unknowns and n variables, each with 2 equations.
Solve Ah = 0 such that ||h||^2(2) = 1
So the following is our final equation.
To compute the eigenvalue perform eig(A' * A). Set up a linear system of equations.
Atranspose * Ah = λh.
You can use this equation if you have at least 4 pairs of matching pixels. However, there could be a problem.
One issue is that we assume that all of the images lie on a single plane.
This method assumes that all point pairs are correct. Unfortunately in practice, this would not be true. So we need some type of robustness for these incorrect options.
If the number of outliers are less than 50%, then RANSAC will still very likely give me the correct transformation.
Unfortunately the Least squares program tries to fit to the outliers. We want to make the line fit the most amount of points with RANSAC iterations. Repeat process, and pick pairs of points randomly, and find the line that passes through points, count the number of inliers and number of outliers.
It can be mathematically shown if you repeat this process enough times, they you will find a line with a large enough number of inliers. It works extremely well in practice.
Works mainly for noisy data.
The RANSAC algorithm.
1. Randomly choose s sample pairs (4 mostly). Typically is the minimum samples to fit a model.
2. Use the least squares approach, fit the model to these samples
3. Count the number of inliers that fit the model with a measurement error ε.
4. Choose the model that has the largest number of inliers.
5. Repeat step 1-4 N times.
The higher the votes in the model, the better the model usually is.
ε depends, a lot of noise in the center has ε much larger, and vice versa.
At every iteration you only see the best model so far. If there are inliers, there is a very high likelihood that the model will converge. Discard the worst, keep the best.
Stopping criteria:
Based on prior knowledge on outliers, we choose N times if there are more outliers, and vice versa.
Comments
Post a Comment