What side is up? - Automatic Image rotation algorithm

Question

Software like Google Picasa demonstrate very well that software can figure out which way a photo was taken without Exif-Data as it is not available in every camera.

Is there a documented algorithm which outputs whether or not an image has to be rotated or not? I want to find out the rotation without the use of EXIF Data. If at all possible I would want to do this with ImageMagick.

Answer 1

This is a complex problem and subject to ongoing research accordingly. Yann's answer is basically pointing towards the usual approaches already (+1) and mfrellum's hint towards the subject of Pattern Recognition likewise applies as well (+1) - for a more in depth analysis you might want to read through a couple of the following papers (subjective selection from past research of mine):

[Please note: most of the PDF links below have been deduced from Google Scholar - Google is naturally good at finding the matching PDF elsewhere for publicly available abstracts of papers, where the actual content is more often than not hidden behind paywalls. The legality of this is subject to heated discussions of course, and so is shielding regularly publicly financed scientific research like so in the first place - make your own judgement!]

• One of the older and most widely cited papers is probably Automatic Image Orientation Detection (Hongjiang Zhang, Aditya Vailaya, and Anil Jain - 1999).
  • A more elaborate, but less official update from 2002 is currently available as an IEEE Proof PDF.
    
    

• One of Hongjiang Zhang many follow up papers is Content-Based Image Orientation Detection with Support Vector Machines (Yongmei Wang and Hongjiang Zhan - 2001)

• Another (though less illustrative) one is Boosting Image Orientation Detection with Indoor vs. Outdoor Classification (Lei Zhang, Mingjing Li, Hongjiang Zhang - 2002)

  • See e.g. coauthor Lei Zhang's Microsoft Research Publications to get an idea of the many image related algorithmic challenges eventually involved here one way or another as well ;)
    
    

• Accordingly, a summary of the aforementioned approaches is Detecting image orientation based on low-level visual content (Yongmei Michelle Wang and Hongjiang Zhang - 2003)

• A quite sophisticated one is A Probabilistic Approach to Image Orientation Detection via Confidence-Based Integration of Low-Level and Semantic Cues (Jiebo Luo and Matthew Boutel - 2004)

• The best match regarding your question title is actually Image orientation detection with integrated human perception cues (or which way is up) (Lei Wang, Xu Liu, Lirong Xia, Guangyou Xu, Alfred Bruckstein - 2003) ;)

• Finally, you might want to have a look at a respective patent regarding a system and method for automatic digital photo orientation detection (2008) - the basic algorithm is summarized with great detail in Figure 8 ;)

Unfortunately I'm not aware of any readily available implementations/libraries, though I'd be surprised if there wouldn't be a few bits available at least.

Have fun :)

Answer 2

It probably reads the exif information stored in the jpg header, when that's available. This gives the orientation of the camera when the photo was taken. This is a far simpler approach than trying to analyse the photo to see which way is up.

There are eight possible orientations. The flags tell you which way is up:

EXIF Orientation Value  Row #0 is:  Column #0 is: 1                       Top         Left side 2*                      Top         Right side 3                       Bottom      Right side 4*                      Bottom      Left side 5*                      Left side   Top 6                       Right side  Top 7*                      Right side  Bottom 8                       Left side   Bottom  NOTE: Values with "*" are uncommon since they represent "flipped" orientations. 

This will reduce the number of photos where image recognition has to be used.