Re: 2 rotated images
As someone mentioned before, if you're trying to recover the angle of rotation, such that the two images align with respect to corresponding features, then that's called "image registration". Image registration has important applications in medical imagery. Several methods have been developed to accomplish image registration, you might try googling 'survey image registration', read about the different techniques, then try to implement one of them.
One really robust and interesting technique for image registration is maximization of mutual information (MMI) of the two images (google for it), you'll find several papers on the topic. The papers might be a bit hard to digest, so here's a brief idea of how it works. (I'm assuming here that the point of rotation is the centre of the image - i.e. there are no x- or y-displacements involved).
Assuming your images are grayscale, you'll first have to determine the histogram of each image and then normalize by divide by total number of pixels, imagining this normalised histogram to represent probability distributions of pixels in the images.
Let one of your images be fixed, and rotate the other by a small angle, the point of rotation being the centre of the image. (Whilst carrying out rotation, you will have to handle interpolation concerns, for your case, nearest neighbour interpolation might be enough - read about it). Now imagine your rotated image to be superposed on the fixed image, and calculate the mutual information defined by the formulas you'll find in the MMI research papers. Store the value of θ and corresponding value of MMI in a table. Repeat by incrementally increasing θ (say by 1 or 2 degrees) and calculating the MMI every time, as described above, covering the whole range of θ from 0 to 360 degrees.
In the end, find the theta corresponding to the largest value of MMI. If you did everything right, you should end up with the value of the angle that the 2nd image has to be rotated so that it corresponds to the first.
I hope this helps you understand the papers better (you'll still have to read them though). If you don't want to use MMI, you can use the same procedure as above but use some other measure, such as cross-correlation or entropy.
Cheers,
AK