Vjeux

I'm working a lot with URLs that contain ids and very often, I made a mistake in one digit of the long id and end up with a completely different element. If I don't pay attention, then I end up looking at two elements thinking they are the same and am intrigued until I find out the mistake.

In order to avoid that, I wanted to know if I could make a sequence of ids where making one mistake would not give a valid id. For example, if you have the id 473, then you have to black list all the ids where the first digit is wrong (073, 173, 273, 373, 573, 673, 773, 873, 973) and the second being wrong (403, 413, 423, 433, 443, 453, 463, 483, 493) and the last one (470, 471, 472, 474, 475, 476, 477, 478, 479).

Here is the list of the first pseudo-numbers:

1. 011
2. 022
3. 033
4. 044
5. 055
6. 066
7. 077
8. 088
9. 099
10. 101
11. 110
12. 123
13. 132
14. 145
15. 154
16. 167
17. 176
18. 189
19. 198
20. 202
21. 213
22. 220
23. 231
24. 246
25. 257
26. 264
27. 275
28. 303
29. 312
30. 321
31. 330
32. 347
33. 356
34. 365
35. 374
36. 404
37. 415
38. 426
39. 437
40. 440
41. 451
42. 462
43. 473
44. 505
45. 514
46. 527
47. 536
48. 541
49. 550
50. 563
51. 572
52. 606
53. 617
54. 624
55. 635
56. 642
57. 653
58. 660
59. 671
60. 707
61. 716
62. 725
63. 734
64. 743
65. 752
66. 761
67. 770
68. 808
69. 819
70. 880
71. 891
72. 909
73. 918
74. 981
75. 990

And here is a visual representation of those numbers:

For each digit in the number, we blacklist 9 other numbers. For a 5 digits number (eg 12345), that means blacklisting 45 numbers. For a 10 digits number (eg 1234567890), that means blacklisting 90 numbers. The number of blacklisted numbers only grows at a logarithmic scale.

In order to see how many numbers we lose, I plotted the ratio of pseudo numbers count compared to the real numbers. We can roughly keep one number every fifteen. But the good news is that the ratio doesn't fall off the chart as the numbers grow.

Looking at the numbers, they looked like to go from 10 to 10 but with some huge spikes and sometimes they were closer. So I plotted the difference between two consecutive numbers in a chart and it looks like the difference is centered around 10. But the variance is getting higher and higher as you move further.

I'm not really sure if this sequence can be really useful in practice but that was a fun week-end experiment. I hope it'll give you some, hopefully useful, ideas 🙂

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.

​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 4x2 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