Implementing Google Image Search Style Grid

I love design principles of Google. The way they present things is really awesome. One such presentation is Google Image Search.

Look at the way they arrange images. Each row has a fixed width, but their are no columns. The images have arranges themselves, intelligently, just enough to fit the row. I always wondered, what algorithm they must have used to achieve this.

What I thought

So my search began. Initially I thought they might have used some kind of knapsack algorithm to fit images to the row width. It means rearragning the positions of images, shifting them from one row to another. But if you inspect, the images don't change their positions, yet they can fit in the row, amazing!

I searched the internet to find whats behind the amazing grid. It turns out that, the technique which is used is far simpler than knapsack and yet brilliant. So, here I present you a really simple technique to achive the Google Image Search style grid

NOTE: This post does not provide any 'ready to copy+paste' code. I will only provide pseudo code, you are free to implement it in any language you prefer.

Initial intuition

If we look closely, we can see that the images in a row have equal height. Also, the heights of rows are not same. So the first intuition is to make the heights of images equal. Lets say we have list of images which stores height and width of each image.

Set CONST_HEIGHT := 160
For each image in images:
    Resize image to height CONST_HEIGHT, constraint ratio

Building a Row

So now that we have normalized the image heights, let's build a row. First we'll have a look at the pseudo code, explanation is on the way...

/**
 * Procedure to build a single row
 * parameter: images - list of images
 * returns: row - list of images in the built row
 */
BUILD_ROW(images):
    SET row_width := 0
    Initialize row_list
    While row_width < MAX_WIDTH AND images.size > 0:
        Dequeue an image from images
        Append image to row_list
        row_width := row_width + image.width
    If row_width > MAX_WIDTH:
        Create new image row_image, with height = CONST_HEIGHT and width = row_width
        Resize row_image to width MAX_WIDTH, constraint ratio
        For each image in row_list:
            Resize image to height row_image.height, constraint ratio
    return row_list

So let's see whats happening here. First we intialized row_list which stores the images in that particular row, and a variable row_width which will store the total width of the row. Now we keep adding images to row from original list until the row_width exceeds the MAX_WIDTH, which is maximum width of the screen. Now we have a row which looks something like this.

Now comes the trick. We won't try to fit the images in row, instead we will try to fit our created row in the maximum width of the screen. So we create an dummy row_image, which represents the entire row, with height equal to CONST_HEIGHT and width equal to row_width. Now we resize the row_image to width equal to MAX_WIDTH and then we resize all the images in row_list to height equal to the new height of row_image. Here's a depiction of the process...

Building the Grid

Now that we know how to build a row, building the grid is easy.

/**
 * Procedure to build the grid
 * parameter: images - list of images
 * returns: grid - list of rows
 */
BUILD_GRID(images):
    Initialize grid
    While images.size > 0:
        SET row := BUILD_ROW(images)
        Append row to grid
    return grid

Nice, we just made a Google Image Search style grid, where images fit in a row, intelligently.

There's more

Hold on, there's little more. While resizing the images, due to floating point divisions and floor operations, we lose some units in the row. If we neglect them, the rows won't have equal widths. To overcome this, we just need to know the units we have lost and divide them equally among the images.

BUILD_ROW(images):
    ...
    // After resizing the images
    // Calculate width of resized row
    SET row_width := 0
    For each image in row_list:
        row_width := row_widt-h + image.width
    // Calculate the lost units
    SET delta := MAX_WIDTH - row_width
    // Divide the lost units among the images
    While delta > 0:
        For each image in row_list:
            image.width := image.width + 1
            delta := delta - 1
    return row_list

You might be thinking that, aren't we changing image aspect ratio here? Yes, but one can lose a single unit in a single division. So the maximum number of lost units is equal to number of images in row. So width of each image will be increased by atmost one, which isn't a big deal. Also you can center crop the images, so that there isn't any empty space left out.

Go ahead, try implementing it in your next web or mobile app. If you find any issues, you can always mail me...

That's it guys, until then, This is hrily signing of...