Vjeux

When displaying images naively, you may end up losing image quality because of a relatively unknown phenomena. If you happen to display an image with a dimension that is one pixel off the real image dimension, the resizing operation (which is costly in the browser) is going to be the equivalent of a blur. See the following example:

130×130	129×129

When you look at it from an external perspective, it seems to be very intentional to display and image with a dimension that is one pixel off. However it can happen for many reasons, some are bugs and some are legitimate.

Grid Sizes

Let’s say the content area where you want to display a 4-columns image grid has a width of 500 pixels. And you want to have the same padding in the edges as in-between the images.

[4 * image{ }width + 5 * padding = 500][image{ }width = frac{(500 – 5 * padding)}{4}]

The only padding value between 2px and 8px that give an integer number for the image width are 4px and 8px. But unfortunately, none of them look good, you really want 6px padding.

In this case, you want to cheat and don’t have all the same width and padding but make some of them 1 pixel smaller.

You can for example say that edges will have 5 pixel and inside 6 pixels. However this is a bad idea because it is going to be visually visible. By changing from 5 to 6 you are doing a variation of 17%.

[5 + 118 + 6 + 118 + 6 + 118 + 6 + 118 + 5 = 500]

Instead you want to borrow a pixel from the images. Having two with 127px width and two with 128px width. The difference is not visible by the eye.

[6 + 117 + 6 + 118 + 6 + 117 + 6 + 118 + 6 = 500]

So now we are in a situation where we want to display an image with 1 less pixel. In order to do that without bluring the image, the trick is to use a container with the size you want to display with overflow: hidden; and inside the properly sized image.

<div style="overflow: hidden; width: 129px; height: 129px;">
  <img src="130x130.png" width="130" height="130" />
</div>

130×130	129×129

Chrome bug

Being one pixel off is really easy, the main cause is different rounding. One one part of the code you use round() and in another part you use floor(). If the number is decimal, you have half chances to get a wrong result. For example, there is currently a bug in Chrome where hardware accelerated rendering has similar issue.

In order to get good scrolling performance, we enable hardware acceleration using transform: translateZ(0); on all the visible images on the viewport. However, when we mouse over an image, we display some overlay and therefore decide to remove hardware acceleration for it to avoid thrashing GPU memory.

To display images, we use a container as described above with the CSS property left: -7.92%; to position the image properly in the viewport. The result is that the image is moving around when you mouse hover it on Chrome. There is probably a different rounding applied between the CPU and the GPU code. The net effect is the image being resized by one pixel and blurry by default. When you mouse over, the image has the correct size.

#hover_hardware_acceleration { -webkit-transform: translateZ(0); } #hover_hardware_acceleration:hover { -webkit-transform: none; } #hover_hardware_acceleration:hover #hover_label { display: block; } #hover_label { display: none; }

In order to fix the issue, we can use integer number in pixel left: -24px; instead. This way the browser doesn’t have to round anything.

#hover_hardware_acceleration { -webkit-transform: translateZ(0); } #hover_hardware_acceleration:hover { -webkit-transform: none; } #hover_hardware_acceleration:hover #hover_label { display: block; } #hover_label { display: none; }

This is only one of the many similar issues with the browsers handling rounding differently. People implementing fluid layout suffer a lot because of browser inconsistencies. If this is happening in browser implementations, there is also a high probability that this issue is going to appear in your own code if you didn’t make sure it was rounding as expected.

Conclusion

This problem is very common and comes from many different sources, but always because of the same root cause: rounding issues. Since sub-pixel rendering is not widely implemented, it is not going to disappear. I hope that you are now aware of it and will address it to avoid affecting image quality of your thumbnails 🙂

I contacted the CEO of Lightbox to share some thoughts about its layout algorithm and he told me this wasn’t the only one they made. Here is the description of another interesting algorithm 🙂

How does it work?

The golden nugget in the whole equation being the square root of two! Anything with the aspect ratio of 1.41421 (square root of two) can be divided in half and produce two more with the same aspect ratio. And as this was close enough to 4:3 (or 3:4) we were able to crop the photos in the collage view to this aspect ratio without it being too noticeable. This way we could have an arbitrary list of landscape and portrait photos and still generate a suitable layout. — Nilesh Patel

Let’s take an example, we have an image where the height is 1 and width is square root of 2.

Let’s split it in half horizontally and calculate the aspect ratio of both the new and old images.

They are both the same 🙂 It means that you can split the image as many time as you want and you will always keep the same aspect ratio:

How much do you crop?

Let’s say we have an image of 300 pixels in width, the image would be 300/(4/3) = 225px in height but instead is 300/sqrt(2) = 212.12px. It’s a 12ish pixels difference, 6 pixels on each side. Let’s look at how it looks in practice. The dark part is the full image and light one is the viewport.

#outer-lightbox-android {
width: 300px;
height: 219px;
background-color: #666;
padding-top: 6px;
margin: 0 auto;
}
#inner-lightbox-android {
width: 300px;
height: 213px;
background-color: #ccc;
}

​If you want to be rigorous, you also have to remove few pixels of padding every time you split the image in half. But that’s only another 2 or 3 pixels per split, that’s still a pretty good approximation.

Image Sizes

In order to keep images good looking, you have to set a minimum and maximum allowed size. Every time a split happens, the resulting image is half the size. Portrait and landscape images alternate at every split. This means that the next image with the same orientation is going to be a quarter of the previous image.

In practice, you can only have two sizes for each orientation or the images are either way too big or way too small. You end up with two different sizes for each orientation. This is good, each image must now only be labelled by “big” or “small” by the algorithm.

Another thing to keep in mind is that two images with a different orientation cannot have the same area. The closest setup you can have is one being two times bigger (or smaller) than the other one. The tricky thing is that this choice is not per image basis but global to the layout. At the beginning, you have to chose one orientation that is going to be twice as big as the other, this choice may not be easy to do.

Conclusion

Check out the Demo!

Pros:

• Works with both landscape and portrait
• Can chose between two sizes for each orientation
• No holes

Cons:

• Having to chose an orientation that is going to be twice as big as the other
• Ordering isn’t really respected when there are many sizes and orientations
• Small cropping
• End of stream is tricky to implement

In Facebook image layout algorithm, we use square viewport to display the images. Since images are not usually square, we have an issue to solve.

Contain Cover

There are two possible ways to deal with it. You make the image fit entirely in the viewport and add black borders (think about viewing 4/3 movies in a wide screen). Or you can make the viewport fit entirely in the image. Instead of having black bars, you are going to remove some parts of the image.

In CSS, the names for those two concepts are implemented with background-size property that has two values: contain and cover.

In our case, we display images in a grid. The cover version works best because the images align nicely in the grid. It makes the edges much more visible that gives a structure to the page.

Set up the problem

The choice we made raises another issue: we are no longer displaying the entire photo but only a subset of it. Therefore we have to know what parts of the image we want to keep, and what parts we want to hide.

The first thing to notice, is that there is only one degree of freedom. You can either pan the image horizontally or vertically depending on the aspect ratio of the image and viewport.

In order to make that decision, we need to have an idea of what is important in the image. Thankfully, at Facebook, people can tag the images and tell us where the people and other point of interests are. We also know that people are important so we also use detected faces. In the future we could automatically find more such as text, animals …

Now we have a clearer view of the inputs. We have a set of point of interests aligned in one dimension. We also have a window that we can slide on this dimension. Here’s an example:

Find maximal window

The idea of the algorithm is to find the position of the window that maximizes the number of point of interests it contains.

A window can be defined only by its starting position since its width is constant. This makes the search space to be the number of pixels in a column/line of the image (minus the size of the window as it must not go outside). Then for each position, you have to compute how many points are inside.

A naive implementation is going to be in the order of O(p * n) where p is the number of pixels and n the number of point of interests. For a typical image with people this means 960 * 3 = 2880 checks. This is way too costly because the number of pixels is an order of magnitude higher than the number of point of interests.

We want to approach the problem the starting from the point of interests. A window can contain, or not, a point of interest. Two windows next to each other that contain the same point of interests can be considered equivalent. With this definition, we can find all the windows much quicker.

We are going to iterate on all the point of interests and consider that they are in the left-most edge of the window. This is the boundary between it between inside and outside of the window. We compute how many points are in that window and keep it if it’s bigger than what we had before.

In order to implement this effectively, we can iterate on all the point of interests in O(n). Using binary search, we find the right-most point in O(log(n)), if the points of interests are sorted. It’s a O(n * log(n)) to sort them at the beginning.

The total complexity is therefore O(n * log(n)), where n is the number of point of interests. Since most of our images have less than 10 point of interests, our algorithm is essentially free.

Center the window

With a window aligned on the left element, we can balance the right padding equally across left and right to center the window.

The previous algorithm can return multiple windows that have the same number of points of interest. In this case, we use the window that has the bigger amount of padding. This ensures that heads are less likely to be cut-off in half.

Force someone inside

When you are viewing all the photos someone is tagged in, you would like to make sure that the person isn’t being cropped out by the algorithm. Previously, what was done was to center the image on that person. We could instead keep using the current algorithm but force the person in.

Again, we are going to look at the boundaries. The person can be from the left edge to the right one. So we are going to place the person at the left and right of the viewport and remove all the points that cannot be in the same screen.

Then, we have the guarantee that all the sets of points we are going to chose also contain the person. We run the algorithm again with that limited set of points to find the window.

Conclusion

The current heuristic is to have images horizontally centered and vertically centered at the first third of the photo, where most faces at. Those are empiric values that work surprisingly well. Also, most images are 4:3, therefore cropping to a 1:1 ratio removes 25% of the photo total, which is only 12.5% on each side.

In order to test the algorithm, we use more extreme viewports. A quick run on my photos and some friends photos shows that it either leaves the crop as is or improves it. It is going to be interesting to test it on Facebook views.

With the new Facebook image gallery redesign, images are displayed using white padding as separation. It works well most of the time but fails for images with a light background.

To get around it, a 1px semi-transparent border is applied inside the image. This way it doesn’t affect dark images and makes a cleaner separation for light ones.

Without border

With border

How to

Here’s the CSS magic:

.image:after {	
  border: 1px solid rgba(0, 0, 0, 0.1);
  content: '';
 
  position: absolute;
  top: 0;
  right: 0;
  bottom: 0;
  left: 0;
}

Conclusion

It’s a very small change but it makes the gallery look a lot better. If you are displaying images in a white background without borders, you might consider using this trick too 🙂

500px‘s front-page uses an interesting image layout algorithm. It stands out from the other ones as it does not use any algorithm nor mathematical properties to be computed. Instead it is based on patterns.

How does it work?

Basic shapes

The idea behind the layout is to use a 4×2 canvas and 4 basic shapes. The game is to fill the canvas with those shapes without any hole. The page is just a succession of those canvas with different shapes combination. Here are some examples:

The choice of which combination of shapes to use can be driven by the images you want to display. If you are displaying an image that you want to highlight, you’re going to chose the big square, whereas a portrait image is going to use the vertical bar and so on.

Combination

If you are curious, there are 90 possible combinations:

oooo  oooo  oooo  oooo	oooo  ooo|  ooo|  ooo|	oo##  oo##  oo|o  oo|o  oo||  oo||  oo--
oooo  oo--  o--o  --oo	----  ooo|  o--|  --o|	oo##  --##  oo|o  --|o  oo||  --||  oooo
 
oo--  oo--  oo--  oo--  o##o  o##|  o|oo  o|oo  o|o|  o|##  o||o  o|||  o|--  o|--  o--o
oo--  o--o  --oo  ----  o##o  o##|  o|oo  o|--  o|o|  o|##  o||o  o|||  o|oo  o|--  oooo
 
o--o  o--o  o--o  o--o  o--|  o--|  o--|  ##oo  ##oo  ##o|  ####  ##|o  ##||  ##--  ##--
oo--  o--o  --oo  ----  ooo|  o--|  --o|  ##oo  ##--  ##o|  ####  ##|o  ##||  ##oo  ##--
 
|ooo  |ooo  |ooo  |oo|  |oo|  |o##  |o|o  |o||  |o--  |o--  |o--  |##o  |##|  ||oo  ||oo
|ooo  |o--  |--o  |oo|  |--|  |o##  |o|o  |o||  |ooo  |o--  |--o  |##o  |##|  ||oo  ||--
 
||o|  ||##  |||o  ||||  ||--  ||--  |--o  |--o  |--o  |--|  |--|  --oo  --oo  --oo  --oo
||o|  ||##  |||o  ||||  ||oo  ||--  |ooo  |o--  |--o  |oo|  |--|  oooo  oo--  o--o  --oo
 
--oo  --o|  --o|  --o|  --##  --##  --|o  --|o  --||  --||  ----  ----  ----  ----  ----
----  ooo|  o--|  --o|  oo##  --##  oo|o  --|o  oo||  --||  oooo  oo--  o--o  --oo  ----

If you are to implement this algorithm, you may want to keep only the combinations that are visually interesting. Only horizontal images could be boring for example.

Crop

The main issue with this layout is the use of unusual aspect ratios. Most photographic images are taken with cameras and therefore have an aspect ratio close to 4/3. As soon as you want to fit a 4/3 image in a narrower aspect ratio, you will have to cut a large part of the image.

Since 500px is all about high quality images, they let the users define all the different crops in use. Because of this, they only use this algorithm in their front-page where they display few images every day. The reason is that badly cropped images can ruin the preview. Here is an example with different cropping values (using CSS percentage values for position):

To reduce the impact of this issue, they don’t use square sizes as I presented in the examples. Instead, they use sizes that are closer to 4/3, both vertically and horizontally, as well as panorama.

Conclusion

Check out the Demo!

This layout is good if you have many portrait and panorama images and want to make some of them bigger. However, it introduces many cropping issues. If you want to use it, make sure you allow users to chose the crops before they are displayed or you risk ruining their photos.

Pros:

• Can make any images bigger
• Can chose between 4 image dimensions
• Can chose between a lot of combinations
• No holes

Cons:

• Important cropping
• Need some tweaks to handle the end of stream
• Fixed number of columns

In this article, we are going to see how to support dynamic updates to Facebook Image Layout Algorithm. Beware, this is not an easy task and there are many special cases to handle 🙂

Making images bigger

To make images bigger we just run the algorithm all over again with the new image being big. For example, making b big will lead to the following layout.

In order to make it a better user experience, we want to smoothly transition the images positions and sizes. We do it using CSS Transitions. In Javascript, we update the size and dimension of all the elements and add 2 lines of CSS to get the magic.

transition-property: top, left, width, height;
transition-duration: 500ms;

Reordering

Let’s start with a small example. We want to move b where d is.

The first thing we do is to remove b from the list of elements. Then, we rerun layout algorithm until we are about to add a block at the spot where we want b to be.

Insert Before

At this point, we realize that b needs to be at the spot where e is. The natural answer is to insert b right before e and re-run the layout algorithm.

However this is not working as expected. Adding b before e groups them together before F.

Insert and canonicalize

The previous method tried to change the past. One knows that changing the past also changes the future 🙂 Instead, what we want to do is to fix the present and let time go on. We are going to insert b to the temporary block, layout that block and insert g (that was previously in the temporary block) right after in the list. This way, we get the layout we wanted.

At this point, we completely blew up the sequence that lead to this layout. Instead of trying hard to move elements around to get a valid sequence, we’re going to be smarter. We managed to get the layout we wanted. Well, let’s just read that layout and build a valid sequence out of it. I call this a canonical sequence.

Handle all the cases!

Now that we have the general framework, we need to see how to “fix the present” in all the different cases.

Small -> Small

As seen in the example, we insert the small element at the right position in the block and move the last element of the block back into the list of elements to be processed.

Big -> Small | Big -> Top of Big

Those two cases are also really easy. We layout the big element we are trying to insert and then layout the block without any modification.

Small -> Top of Big

This one is more tricky. We want to find another small image so that we’ve got two to form a small block.

• If at this point, there’s a temporary small block that is not empty, then perfect, we add the small image we want to insert at the end of the block and layout it.
• If not, we’re going to look for the first small image in the list of elements left to be processed. With this image, we’re going to form a small block and layout it. Note: if there are many big images, the small image can be pulled from quite a long distance.
• If there’s no small image left, we’re going to layout a small block with only the image we want to insert. We’ll discuss why it is okay later.

Small -> Bottom of Big | Big -> Bottom of Big

And now comes the hard part. First, you’ve got to be warned, there isn’t always a solution for this problem. For example, whatever ordering you chose, you are never going to be able to move D at the bottom of A.

Let’s take an example where it is actually possible. We want to move D at the bottom of A.

We start the algorithm and run into the conflicting situation on the first element.

The idea here is to pull small elements from the rest of the list in order to make a small block at this position. Once it is done, the other column is going to be filled with the big block that was conflicting and we’re back to the column we were initially. Only this time, we are one row lower. And this makes a big difference. Whatever we are about to layout here is either a small block or the top of a big block. We already know how to handle those two cases.

If there isn’t enough small elements remaining in the stream to form a small block, we’re not able to find a solution. There may be a solution if we allow to update the past, but as we’ve seen earlier, this is a tricky business.

We cannot just stop here and raise an error: no solution found. Instead, a trade-off we can make is to put the element we are trying to insert at the top of the big block instead of the bottom. This is obviously not perfect but is the best user experience I was able to find.

Last small element

The last issue we’re going to cover in this article is how to handle the last small element. Imagine we’re in the situation where there are 2 images, one big and one small. You are trying to move the small element before the big one.

With the algorithm I explained, you are never going to be able to handle this case. There are only two possible ordering: Ab and bA. But both put the big image first and the small image second.

Priority on small blocks

The main issue here is that the big block has the priority over the small one. You can change the algorithm such that as soon as you see a small element, you pull the next small one from the list to make a block. This fixes the issue here but introduces a side effect when making photos bigger.

In a canonical stream, when you make an image bigger, you’ve got a nice property that it always expand in the same column and to the bottom.

When you change the priority, the other small image of the block is going to take precedence. Therefore the (now bigger) image is going to move to the other column. This is not a good user experience.

We could reorder the stream and move the image at the right position using the algorithms we’ve seen previously. However, not all the streams are reorderable. In Facebook case, only the photos in an album are reorderable. All the other streams are sorted by time, so reordering is not acceptable.

Priority on small blocks with only one image

The solution is to change the priority but only for a special case: when there are no more small images left to make a full small block. We still maintain all the benefits of having small blocks having a lower priority than big blocks, but at the same time fix the issue with the last lonely small block.

Bigger Images and Ordering

When making images bigger, we change the order of the stream as seen previously. For example, let’s make b bigger in the following example.

So far so good, B expanded in its column and below. Now we are going to make a bigger.

And … it’s unexpected … A and B just swapped behind our eyes for no apparent reason. You have to understand the algorithm to figure out what is going on. a when small was put after B because it didn’t have the precedence. But, when you make A big, it gets back its precedence.

Canonicalize

A solution is to canonicalize the stream every time you highlight an image. This fixes the issue we described but introduces another one. Making a photo bigger is intuitively an operation that is reversible. When we make an image bigger and right after make it smaller, we expect that we get back to the original position. If you canonicalize after making it bigger, this property no longer holds true.

In the following example, a and b get inverted after making b bigger then smaller.

Since we cannot reorder images in the stream in Facebook, we did not try to find a better solution. We just stay with the unexpected behavior.

Conclusion

Check out the Demo! (Note: this is an earlier version, the most obscure tricks are not handled the same way and don’t work all the time)

The transition from a static layout algorithm to a dynamic one was not an easy task. But in the end, we’ve been able to figure out all the edge cases and have a solution for each of them.

The issues arise when there are many big images and not enough small ones to do the various balancing operations. Hopefully the user are going to be moderate and don’t make all the images of their stream big 🙂

For the redesign of the Photo Section of Facebook we wanted to highlight some photos by making them bigger. It all started with the following mock by Andy Chung:

Layout

Alternated Blocks

My first shot at the problem was to make a fixed layout where we would alternate big images on the left and on the right.

With this scheme, you have one big image every 9. We started brainstorming about putting the one with the most number of likes and comments there. However, this felt to be very arbitrary.

Emily Grewal, the Product Manager of the project wanted something better: being able to make any (and all) image bigger. Automatic selection of images to be bigger was also discarded as we wanted the user to feel in control of this space.

Big and Small Blocks

In the next iteration, I tried to give more control by reducing the size of the blocks. Now it is either one big image or 4 small ones.

One constraint we had at the time was that the columns could start at an arbitrary height. With this layout, we can make the block display: inline-block; and the browser is going to reorder them automatically as the columns initial height are changing.

However, this wasn’t all shiny. One nasty side effect is the fact that the ordering of two small blocks next to each other is awkward. Instead of being from left to right they are in zig-zag. You could linearize those but you would lose the layout from CSS.

Smaller Small Blocks

The next (and final) idea is to shrink the small blocks from 4 to 2 elements. It solves our zig-zag issue and feels more natural.

Algorithm

The idea behind the algorithm is to have temporary blocks that serve as buffer. We iterate over all the input elements and put them into the temporary block of the corresponding size. Once a temporary block is full, we add it into the grid in the smallest column.

Here’s an example where we try to layout AbcdEf:

And there’s the pseudo-code implementation of the algorithm:

function layout(elements) {
  var columns = [new Column(/*height */ 0), new Column(/*height */ 0)];
  var stash = [];
 
  elements.forEach(function (element) {
    if (element.isBig()) {
      var column = columns.getSmallestColumn();
      column.renderBigBlock(element);
      column.height += 2;
 
    } else /* element.isSmall() */ {
      stash.push(element);
      if (stash.length === 2) {
        var column = columns.getSmallestColumn();
        column.renderSmallBlock(stash[0], stash[1]);
        column.height += 1;
        stash = [];
      }
    }
  });
 
  if (stash.length > 0) {
    var column = columns.getSmallestColumn();
    column.renderSmallBlock(stash[0], stash[1] /* can be undefined */);
    column.height += 1;
  }
}

Conclusion

Check out the Demo!

This is the layout algorithm we ended up using for Facebook photos. We found a way to let the user make all the images he wants bigger minimizing the risk of the result being ugly.

Pros:

• Can make any/all image bigger
• No holes
• Order is mostly respected
• Need to store only two sizes per image

Cons:

• All images have the same dimension
• Cropping required to display both landscape and portrait images
• Only works for a number of column that is a multiple of 2

If you want to know how reordering works, read the follow-up article 😉