How do I detect and rotate a square?
Since you asked for algorithms, I suggest you look at the Hough transform and other techniques for finding lines in an image.  I suspect this will help you determine where the lines are, where the intersections are, and how much to rotate to recover the original image.