Slashdot Mirror
Computer-Aided Lego Art Project
rsk writes "Justin Voskuhl, a Google engineer, in a 2-fold bid to fight boredom and figure out something to cover a large barren wall in his living room, one weekend developed a Java program using an annealing algorithm to figure out the best layout and colors of Lego blocks to reproduce a source image exclusively in Lego blocks inside a frame. He plans to release the source code soon. I probably would have just painted the wall ..."
Why is this front page material? Lego mosaics are ancient, and the source code is probably trivially simple.
The major algorithmic difference is that lego blocks are not [always] square, and figuring out which combination of sizes to use to cover an arbitrarily shaped block of color is NP-Hard. What he has done here is seriously impressive.
Yes, but they're always rectangles, with predictable proportions, (1 by X, with a maximum X) you always stack them horizontally, and there's a very limited color palette.
If you think it's difficult to calculate you're probably modeling it wrong.
Actually, it's easier than that. :) Model with 1x1 blocks on the first pass, using standard interpolation limiting to your available palette colors, then combine horizontally adjacent blocks with the same color as 1xN blocks according to availability.
Finding any one fit of lego blocks to produce a given image is linear complexity (O(N)). It's the same algorithm used in your video card to rasterize a 3-d polygon model or in photoshop to rescale an image. Definitely not NP-hard.
Growing adjacent spaces of matching color to use larger bricks isn't tough either. Use a simple run-length encoding algorithm (second pass, also O(N)) and then when you're breaking up long stretches into brick-sized stretches in the third pass, add a constraint that within a "same color stretch", a brick edge on the current line doesn't line up with a brick edge on the previous line (this pass is also O(N)).
Final cost: 3 * O(N) = O(N)
This guy's approach of determining brick size and location using simulated annealing sounds like a hammer in search of a nail. Definitely cool and fun to write, but probably not necessary to solve the problem.
How do you resolve conflicts when the rigidity rules say one thing, while the brick value rules say another, and the color dithering rules say yet another? There should be a weighting function, and the impact of that decision will cascade down the mosaic, affecting other decisions. Finding the combination of decisions that yields the optimal (for a given set of weights) arrangement is NP.
That method will result in structurally unsound pieces (not enough interlocking). His code apparently optimizes visual accuracy against structural soundness.
You are forgetting that legos must be interlocking. That somehow is a part of the algorithom unless the guy cheated (the frame/glue holds it together). Assuming the picture is two "nubs" thick, The algorithm must combine 1x2, 2x2, and 4x2 blocks in a way where they hold on to eachother - in addition to dithering and making the photo look more realistic.
I'm willing to bet that the code isn't optomised (hey - it's java!). I bet these calculations can be done in a couple of minutes at most, not 10 hours (assuming he's not feeding it 10 megapixel images). It would also be interesting to compare implementations in different languages (C++, python, lisp, haskell, ...)
It would be more interesting to know why it takes such long time. Doing this in photoshop takes about two minutes, including the editing.
Adventure, Romance, MAD SCIENCE!