The algorithm for a perfectly balanced photo gallery

Since I&#x27;m a CS theory person, I can offer some theoretical improvements on the running time and make the problem even more general...<p>Instead of minimize the linear difference of partition, we might want to minimize the standard deviation, or basically any convex function, and still do it in the same time bound.<p>One can reduce this problem to find a k-edge path of minimum weight on a complete DAG. The naive algorithm will run in O(kn^2), but we can improve the running time to O(kn) by realize the weight on this DAG has the Monge property. This is very practical to implement.<p>I posed it as a problem on daily haskell exercise <a href="http://dailyhaskellexercise.tumblr.com/post/58060450750/the-minimum-weight-path-of-length-k-in-a-dag-with" rel="nofollow">http:&#x2F;&#x2F;dailyhaskellexercise.tumblr.com&#x2F;post&#x2F;58060450750&#x2F;the-...</a>.<p>In this application, k is very large. n is just a constant multiple of k. We can use a <i>theoretically</i> better algorithm that takes n2^O(sqrt(log n loglog n)) time. (this is almost O(n^(3&#x2F;2))). I doubt it will ever be implemented with speed comparible to the O(kn) solution. See <a href="http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/sdarticle_204.pdf" rel="nofollow">http:&#x2F;&#x2F;www.cs.ust.hk&#x2F;mjg_lib&#x2F;bibs&#x2F;DPSu&#x2F;DPSu.Files&#x2F;sdarticle_...</a><p>I shall post a solution tomorrow since I&#x27;m currently touring NYC with my gf...

WordPress recently added &#x27;Tiled&#x27; galleries via their JetPack plugin. It seems like a similar approach. You can see an example gallery here:<p><a href="http://ma.tt/2013/07/jay-z-picasso/" rel="nofollow">http:&#x2F;&#x2F;ma.tt&#x2F;2013&#x2F;07&#x2F;jay-z-picasso&#x2F;</a><p>Additional info: <a href="http://jetpack.me/support/tiled-galleries/" rel="nofollow">http:&#x2F;&#x2F;jetpack.me&#x2F;support&#x2F;tiled-galleries&#x2F;</a><p>Code: <a href="https://github.com/crowdfavorite-mirrors/wp-jetpack/tree/master/modules/tiled-gallery" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;crowdfavorite-mirrors&#x2F;wp-jetpack&#x2F;tree&#x2F;mas...</a>

It like how it looks, but much like Flickr I dislike how it&#x27;s biased towards landscape pictures. Some of my best photos are portrait, but they get overshadowed by the landscape ones.<p>I imagine the algorithm to cater to both is much harder, because you wouldn&#x27;t be able to treat each row in isolation, can it actually be solved to a good standard?

Side-topic. Shooting Holi [1] without putting your camera in an airtight sealed enclosure is a good way to ruin your equipment.<p><a href="http://en.wikipedia.org/wiki/Holi" rel="nofollow">http:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Holi</a><p><a href="http://www.lensrentals.com/blog/2013/05/how-to-ruin-your-gear-in-5-minutes-without-water" rel="nofollow">http:&#x2F;&#x2F;www.lensrentals.com&#x2F;blog&#x2F;2013&#x2F;05&#x2F;how-to-ruin-your-gea...</a>

I just implemented pretty much the same thing from scratch for my wedding gallery¹.<p>For each row, it tries 3-10 images, sums their aspect ratios, divides the total row width by the sum to get a candidate height, then picks the height that&#x27;s closest to the average of the existing rows.<p>To make things look a bit nicer, it rejects candidate rows with the same number of images as the last row.<p>I might release the code on Github if I can make it modular enough. Currently it depends on jQuery but that&#x27;s really only for element creation.<p>¹ <a href="http://mattandsophiegetmarried.com" rel="nofollow">http:&#x2F;&#x2F;mattandsophiegetmarried.com</a>, I&#x27;m the guy with the waistcoat, purple cravat and massive grin.

What&#x27;s just as impressive is the full size view of the image. The background brings the ambient colour of the photo to make it more immersive. Very nice!

It looks nice (much like Google Image results) but IMO it&#x27;s not &quot;equally distributed&quot;. For example, an image that has dimensions 800x531 gets ~2.3x the space as one with dimensions 531x800. That arbitrarily incentivizes&#x2F;rewards landscape photos w.r.t. portraits. &quot;Equally-distributed&quot; would probably require an algorithm that works mosaically (without row constraints) and couldn&#x27;t achieve &quot;taking up all the space available [in a rectangular region]&quot;.<p>Still, looks nice.

Maybe I&#x27;m missing the point but why is this an achievement? I&#x27;ve seen Google images do this for years (from the backend, sends the users viewport dimensions and then automatically calculates the optimum filling). For years (Warning NSFW!) vusker.com has been doing this client-side in their thumbnail and gallery view. Plus look at the vertically stacked posts from Pinterest.<p>It seems more a marketing ploy to get attention to the great service chromatic.io is providing?

he writes an excellent example of why &quot;all that computer sciency stuff&quot; is usefull in day to day programming, yet still wants to take pride in his ignorance, like this is some strange sort of fluke.

The demo [0] is pretty impressive. Photo sites like Instagram and 500px give a fixed ratio, while flikr does nothing quite appealing as this. Nice work.<p>[0] <a href="http://www.chromatic.io/FQrLQsb" rel="nofollow">http:&#x2F;&#x2F;www.chromatic.io&#x2F;FQrLQsb</a>

This works well when the photos are not time sequential. I find it harder to follow the story when the photos are ordered by the partition fit instead of the time taken. It would be neat to optionally incorporate time into the algorithm.

This looks like a pretty slick, mobile-compatible photo gallery, but without the code it isn&#x27;t very useful. They talk about Chromatic like a real product, but &quot;free web service&quot; basically means &quot;demo&quot;.

&quot;Remember the days in college when you learned all about the big Oh!&#x27;s and re-implemented all these sort-algorithms for the hundredth time? If you are a web developer like me, chances are you never had to touch a single one of these algorithms ever again.&quot; +1<p>It&#x27;s a good start, but when the window is shrunk, the result isn&#x27;t as impressive.

This is why I always preferred vertical masonry. Sites such as VKontakte, Google Image Search, and the recent Flickr app tile things horizontally, but this sometimes means you have to crop the images to fit into your masonry. Not so with vertical masonry, which you can just resize to have constant width.

Why not use Masonry or Isotope?<p><a href="http://masonry.desandro.com/" rel="nofollow">http:&#x2F;&#x2F;masonry.desandro.com&#x2F;</a><p><a href="http://isotope.metafizzy.co/" rel="nofollow">http:&#x2F;&#x2F;isotope.metafizzy.co&#x2F;</a>

Given that clear textbook explanation and he decided to port a Python implementation instead of writing it from scratch? What a waste of an opportunity for a fun day at work...

It is hard not to mention series of articles [0] on the same topic by Christopher &#x27;vjeux&#x27; Chedeau [1] in this context.<p>[1] <a href="http://blog.vjeux.com/?s=%22Image+Layout+Algorithm%22" rel="nofollow">http:&#x2F;&#x2F;blog.vjeux.com&#x2F;?s=%22Image+Layout+Algorithm%22</a> [0] <a href="https://news.ycombinator.com/user?id=vjeux" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;user?id=vjeux</a>

I too made something similar recently. I decided to use dynamic programming. This way it&#x27;s easy to ensure that you don&#x27;t end up with a half row at the end. It also doesn&#x27;t require changes to the ordering of the images. <a href="http://fangel.github.io/packing-images-in-a-grid/" rel="nofollow">http:&#x2F;&#x2F;fangel.github.io&#x2F;packing-images-in-a-grid&#x2F;</a>

Great post with gorgeous results. The service is really very nice too! Fantastic work.<p>Question: will you ever implement profiles or permanent galleries?

I made something similar a while back to generate backgrounds on a music website. I took a different approach, and it&#x27;s not as clean. If anyone is interested to see a different attempt, take a look at the JS.<p><a href="http://wwwstu.tcu.edu/baerbradford/tiles.html" rel="nofollow">http:&#x2F;&#x2F;wwwstu.tcu.edu&#x2F;baerbradford&#x2F;tiles.html</a>

Interestingly when I load up their demo gallery at: <a href="http://www.chromatic.io/FQrLQsb" rel="nofollow">http:&#x2F;&#x2F;www.chromatic.io&#x2F;FQrLQsb</a> and click on one of the images to enlarge it, then click again to drop back into the gallery view, the gallery breaks horribly (about 1&#x2F;3 of the images vanish).<p>FF 22 on Windows 8

I&#x27;ve studied this a great deal, and developed a custom masonry type layout to mitigate the row&#x2F;column bias. I believe it is a much more balanced layout than the article shows. Using it in Imagist, a paid app. Open to a few beta testers for iOS 7 as well, if you want to judge for yourself.

Since when it is ok to suppose visitors know to click the escape key to go back. And where is the link to go up to the gallery. I had to mess with the url or I was gone for a long back button session. Morevoer it is very slow.<p>Just to add some negativeness to the generaly positive comments here.

I really like this, made a quick one with snaps from Angkor Wat in Cambodia: <a href="http://www.chromatic.io/lTOfsdP" rel="nofollow">http:&#x2F;&#x2F;www.chromatic.io&#x2F;lTOfsdP</a>

Can sombody tell me why this uses the photos as background images for divs? It seems to me like this gallery could also use img tags (which is semantic, crawlable, yadda..)

For some reason I was expecting (perfectly) balanced files of a photo gallery on disk. What I actually got was equally interesting though.

that looks very good, but navigating with the &#x27;back&#x27; button breaks the app. tested on FF24 &#x2F; opera 15.

The gallery layout can be seen in G+ for a while now. But the ambient effect in full-screen mode is awesome!

I would love to see chromatic as a service I can pay for, maybe sell me a wordpress plugin?

Is there some kind of static gallery generation software that can do something like this?

Is it supposed to reload previously viewed images when the user scrolls up or down?

Anyone else in this thread think that this blog post covers a painfully trivial calculation problem? What&#x27;s next - someone&#x27;s going to write a full blog post to explain to me how to perfectly toast my toast using these visual sensor things that seem to be built into my head (eyes)?

Counting down to when Marissa Meyer pulls the acquisition trigger ... :)

i made a library for this:<p><a href="https://github.com/jonathanong/horizontal-grid-packing" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;jonathanong&#x2F;horizontal-grid-packing</a>

Only the title loads on Chrome in Android 4.2.2

btw this breaks zoom.