Visually Appealing Image Layout Algorithm

Let me pose a problem.  If I were to give you a number of randomly sized images that needed to be  displayed in order, in a row with a set width, how would you do it?  To make things slightly more complicated, you're not allowed to crop the images either.  What's the most visually appealing way to arrange and size the images?

This question came about as I was trying to display the results of another program I wrote.  My goal was to take a number of images, scale and place them in rows in a specified order to fill an image of a certain size.  My first attempt was based on a blog post theorizing about how the image layout algorithm for Google Plus works.  The described algorithm is quite simple.  Start with a single image and scale it to fill the required width.  After scaling, it will have a certain height.  If the resulting row is too high, add another image and scale them so that they are the same height and their total width is what you require.  Keep repeating this process until the row is the right height.  The equation below describes how to find the height of the row.

You can see from this that as you add another image, you add another w/h term to the denominator of the fraction.  As this will always be a positive number, the row height will decrease each time you add an image.  Let's have a look at my first attempt using this method.

Image Gallery Test

Pretty snazzy huh?  Wait a minute, what's going on in the first couple of rows?  All of those dots are actually images, and do you know why they look like that?  Remember how adding a new w/h term decreased the row height?  Adding an image with a large aspect ratio adds a very large w/h term.  In this case, the long thin image added last causes the row size to drop to around a single pixel high.  That's far from ideal.  On the plus side, for images with relatively normal aspect ratios, this algorithm does a good job.  It seems to be the basis for the jQuery plugin, flexImages from Pixabay.  I should add that the images above need to be padded better to make sure that they line up on the right hand side, but that's a trivial step for later.

Where do we go from here?  The dimensions still satisfy our requirements that all images have the same height, and that the total width be a specific number of pixels.  After looking at a lot of image galleries online and thinking about it intensely for a week, I came up with a formal definition of the problem.

Formal definition of the problem

It doesn't look like much, but it gives us a framework to solve the problem.  One subtle point to notice is that alpha is between 0 and 1.  This means that images should never be enlarged.  I believe that enlarging images to fill empty space is the wrong way to go.  If a 1x1 pixel image was added, enlarging it to fill a 100 pixel high row doesn't add any information, all it does is take up 100 pixels of horizontal space that could be used for images that do have information.  Besides, enlarged images never look good, they always come out blurry, regardless of the interpolation method used.

Looking at the definition above it becomes clear that we are trying to solve for the values of alpha.  We know alpha is bound by the values 0 and 1.  We also have to obey the constraint that the total width of the scaled images is equal to some value W.  Conveniently this is easily fed into the minimise function of the scipy.optimise Python library.  Using the SLSQP method, non linear constrained optimization problems can be solved.

Some of you may have rightly noticed that my definition of the problem doesn't solve anything.  Optimization algorithms require an objective function.  This is the function that is minimised in the optimisation process. This is the part I've been struggling with.  The best that I've come up with so far is to try and minimise the sum of the standard deviation of the heights of the scaled images and the standard deviation of the widths of the scaled images.  i.e. (std(heights)) + (std(widths)).  To test this method I've written a program that takes images sizes and tries to make a row out of the dimensions.  The output is displayed as black images on a white background.  The results aren't too bad.

Image row optimization first pass

You can see in the image above that none of the images dominate the row and all get a reasonably fair proportion of the display.  The tiny image at the end remains that size because it hasn't been scaled up, which is one of the bounds.  Ideally I'd like all the image to be the same height.  So I took the results of the first pass and fed them back thought the optimisation process.  This time however, the bounds are set to be within 85 to 115 percent of each of the values of alpha for the first round, still bound by 1 on the high side.  The optimisation function has also been changed only to minimize the standard deviation of the height, not the width.

Image row optimization second pass

That's as far as I got.  I think the second layout looks better.  I may need to walk away from this one for a while and think about what I'm trying to optimise.  That's the trick, coming up with the right optimisation parameters.

I've really enjoyed playing around with this.  This is one of those experiments that I can indulge in because I'm not doing this as a job.  I can take the occasional detour and explore interesting topics just because I want to.

Get the Code

In case anyone else is interested in this problem I've collected some links to sites that have relevant information.

A good description of the different types of layouts used
http://blog.vjeux.com/2012/image/image-layout-algorithm-facebook.html

http://blog.vjeux.com/2012/image/image-layout-algorithm-lightbox.html

http://blog.vjeux.com/2012/image/image-layout-algorithm-lightbox-android.html

http://blog.vjeux.com/2012/image/image-layout-algorithm-500px.html

http://blog.vjeux.com/2013/image/image-gallery-left-and-right-areas.html

http://blog.vjeux.com/2014/image/google-plus-layout-find-best-breaks.html

A different layout that can use snapping
http://www.greentreelabs.net/isotope-masonry-tiles-gallery-and-final-tiles-gallery/

A layout algorithm that uses cropping
http://www.techbits.de/2011/10/25/building-a-google-plus-inspired-image-gallery/