Algorithm to effectively find perspective transform in motion estimation

Question

I've shot a series of photographs in a sort of stop-motion fashion, and although the camera was mounted on a tripod, there are tiny motions between each two successive photos.

After some experimentation, I figured that using a perspective transform would be appropriate to apply a correction to a photo so that the difference frame is minimised. This transform basically just moves the four corners of a picture by a given offset, allowing for a trapezoid distortion.

To do this process by hand is impossible in this case, as it takes me like half an hour for each frame. So I am looking for an effective algorithm to estimate the transform parameters (the four corner offsets). I would give the algorithm the maximum magnitude of the offset, and it should then find, as quickly as possible, the parameters (eight values).

Is such an efficient algorithm known? The photos are in colour but could be converted to grey scale, although the lighting changes also over time, so taking a difference image and summing the pixels is not enough, but probably one needs to auto-adjust the contrast and brightness as well.

Answer 1

Assumptions

From your question, I assume you already have an algorithm that does produce the transformation you want, but you have to play with the parameters manually.

Proposed solution

First, convert the images to grayscale (this is mainly for convenience). You might play around a bit with the channels of your images - do you need all channels, or do some only contribute noise? Is it a good idea to have a certain channel overrepresented, e.g. the red one because there is least distracting information in it, and so on.

Secondly, check if you can find threshold on the values that drops most parts of the noise and leaves you mainly with desired information. In the image you posted, there is this kind of rainbow band... I assume this is something unwanted and you could get rid of it in this step.

Define an objective function to minimize, e.g.

$\sum\limits_{(x,y)}(I_\textrm{ref}(x,y) - T(I(x,y),\vec{\zeta}))^2$.

Here, $I_\textrm{ref}(x,y)$ is your reference image, and $I(x,y)$ is the image to be transformed to match the reference as closely as possible. $T(I(x,y),\vec{\zeta})$ is your image correction transformation applied to the image $I(x,y)$, and its (eight you say) parameters are summarized in the vector $\vec{\zeta}$.

Now, take an optimization algorithm of your choice. Probably it is best to take one that does not depend on the derivative of your objective function, or one that automatically estimates the derivative numerically. An very well-studied algorithm of the first kind is the Downhill-Simplex-algorithm (or also called Nelder-Mead-algorithm, see https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method). Give your objective function to it and let it play with the parameters $\vec{\zeta}$ until it finds an optimum (i.e. a minimum).

Depending on how your transformation handles edges, it might be necessary to modify the objective function a bit, so that it does not sum over all pixels $(x,y)$, but only over the central part of your image.

Also, if you would like the letters to match as well as possible, it might be an idea to invert your images, so that the background is mainly black (i.e. zero). In theory, this should not make a difference, but it might in practice due to numerical reasons.

Further improvement

If you do have slight differences in the illumination in your images, you could use Mutual Information as a cost function. This is very often done in medical imaging, when registering two images with different contrasts.

I hope that helps.

Answer 2

The suggested technique seems to be to gather points of interest, calculate a feature vector for them, and then find matching pairs of points in both images, followed by a calculation of the transform.

Here is a sample project: http://www.codeproject.com/Articles/95453/Automatic-Image-Stitching-with-Accord-NET

Here is a paper that claims improvement by preparing through a phase correlation stage: http://www3.nd.edu/~kwb/ThomasKareemBowyerIGARSS_2012.pdf