24

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.

Peter O.
  • 32,158
  • 14
  • 82
  • 96
Thomaschaaf
  • 17,847
  • 32
  • 94
  • 128
  • 1
    Have you seen any examples for which Picasa does not yield the correct result? Have you tried loading synthetic images to see how Picasa handles them? Also, could you post a few sample images? – Rethunk Feb 06 '12 at 23:35
  • 1
    duplicate: http://stackoverflow.com/q/1141928 – ergosys Feb 07 '12 at 22:50
  • 1
    I found several papers (and the above duplicate) with the google query "image orientation detection algorithm". – ergosys Feb 07 '12 at 22:58

6 Answers6

29

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!]

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 :)

Community
  • 1
  • 1
Steffen Opel
  • 63,899
  • 11
  • 192
  • 211
15

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.

ChrisF
  • 134,786
  • 31
  • 255
  • 325
  • 4
    NOTE: I added this answer **before** the question was updated to specify that EXIF information wasn't always available. – ChrisF Feb 09 '12 at 11:08
7

I don't know of a specific implementation, but here are some thoughts:

  1. The sky is blue. Look for blue along an edge. More blue = more likely to be up.
  2. The upper regions of an image tend have less detail (sky, clouds) than lower regions.
  3. Do an edge detection and look for long horizontal lines. If they're not horizontal, its possible the image is on its side. Combine with #1 and #2 to see if you are 180 degrees out or not.

Note that there is a rotation field in the EXIF data, which is from the camera's orientation sensor. Always use this data first, as the rest is an image processing guess.

Yann Ramin
  • 32,895
  • 3
  • 59
  • 82
5

I don't know a ready made solution for this problem but it is a classification problem and there are many classic algorithms that can be used. Pattern Recognition and Neural Networks by B.D. Ripley is a good read on the subject.

openCV has a machine learning module that can be used for this.

The solution will probably involve heuristics like 1-3 in Yann Ramin's answer but quantified as numbers between 0 and 1 and put in a vector. You can use imags with exif data about orientation to make a training set for the classifier.

mfrellum
  • 169
  • 3
4

Dominant light sources are usually up, whether or not it is night or day, and whether or not there are people in the scene. Combining highlight detection with edge detection you can identify likely locations of the scene's light sources and judge which way is up.

EDIT: Great question - I just spent 5 minutes on Google Scholar and failed to even find the correct problem domain.

EDIT: Got it. It's called 'image orientation detection' -- not too obscure a title.

EDIT: A quick review suggests that there are two major approaches:

  1. Combined classifiers - train lots of different classifiers and combine the results, a classic 'throw everything you got at it' shotgun approach. Here, most of the innovative contribution of papers appears to be on how to design new ways for different classifiers to be combined.
  2. Specific features - pick a specific (or small set of specific) feature and use these to classify, detect orientation. Some examples are : facial recognition + edge detection, local binary pattern overlap (relative: only works between two images of same subject).

Anyway it is certainly an interesting field, and there seem to be more patents than papers, which makes it even more interesting. However I did not find anything that explicates the Picasa method. However I did find this:

S. Baluja (from Google) has published the following papers:

From this, one might conclude that the methods therein are indicative of what Google uses.

Cris Stringfellow
  • 3,714
  • 26
  • 48
0

Picasa has facial recognition, which may be helping even if it's not actually tagging known people.

izb
  • 50,101
  • 39
  • 117
  • 168