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.
OK, really he needs to go interact with people instead of staying home writing program for his barren wall! How's about talking to the opposite sex!
OK, I have to show off - I did something similar four years ago. :)
Post
Webpage
I'm a much better programmer now, just for the record.
"So the Java program runs for about ten hours for each image..."
It would be interesting to know how powerful the computer was, because I'm sure it would take _a lot_ of processing time to do something this complex. It seems like he did it all at home, but I think it's also plausible that he could have borrowed computing power from his work.
"Intelligence has nothing to do with politics!"
-Londo Mollari
He should sell these.
-tom
"Slashdotted"? What's next... "story"? Oh wait...
How about glass tiles on a 100'x30' wall, or a 30'x75' wall?
I wrote the code, my brother in law did the hard parts.
It's stories like this that make me realize I'm not really a geek -- for which I'm profoundly grateful.
Can someone who got the page to load copy and paste the article here?
Where in Tucson is the first mural located?
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.
Reminds me of the time my buddy and I were playing some 301 at the dart board. Both of us were pretty wasted. I discovered he couldn't subtract, and that was giving him an advantage, so I started keeping score. Then we discovered I also was too wasted to subtract.
We decided I would sit down and code a score keeping program with a text-based GUI (similar to ye olde Vitamin C Screen Utilities). Each player just entered their darts 10, 13, etc. or D20 for a double 20 T13 for triple 13, and B/DB for bullseye and double bull, then the code would do the math. Apparently writing a parser and an event loop with some event handlers taps a part of my brain unhindered by all the alcohol, etc.
cat
You would figure LEGO would already have a system to do this
This guy has been doing LEGO mosaics for years, and if you google a bit you'll find others and the code for creating them.
LOL -- now do McCain!
When I first read this I wasn't impressed that he pixelated a few pictures into lego pieces. Its obviously not that hard because the story hasn't been up long and 2 or 3 people who have ever done any pixelating or lego stuff have posted their projects in the comments.
Then I looked up how much lego pieces cost. 25,000 1x1 plates would cost around $1,750-$2,500. I'm curious how much his cost reduction the algorithm actually does. If it just searches and replaces rows of horizontal plates with 1x2, 1x3, etc plates and 3 vertical plates with a block, its pretty cool but still not THAT impressive. If it balances image quality with manufacturing costs, I'm really impressed. I'm hoping the 10hr computing time indicates it does that latter.
The Anita Barrio neighborhood. It's along I-10, on the opposite side from the freeway, facing a park. I don't know the exact address off the top of my head.
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.
If you use a less strict definition of "lego brick" that includes plates then there are also 1/3 by X proportions. Then there is the rigidity issue (the classic brick-laying arrangement of offset rows is good, while straight row/column arrangement of constant-width bricks is very bad). And finally the problem of parts cost (the easiest solution is a whole lot of 1x1 bricks, but 1x1 are rare and expensive, while 1x4 are cheap and super common).
So just add some constraints to your model.
Try using a tool like drools-solver
nobody wants to eat John McCain's turds. Hell, nobody wants to vote for him.
Mirror at http://www.spotlynx.com/node/1258
Mmmmmm, not really. Just use a standard grid, then offset every other row by 1/2 square. Rigidity issue solved. Visually there will be little difference, and less the larger the image gets.
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.
Here you go:
map
Using street view you can almost see it. You may need to rotate so the view is towards I-10.
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.
From the side view, a single unit lego width to height (assembled) ratio is about 5/6 - so take your starting image, and resize the height (uncheck constrain proportions) down 83.3%. Use the Mosaic filter (Filter -> Pixelate -> Mosaic). For large images, use a mosaic block size of 16. Reduce the image size to 1/16 its original size (do this step wise, e.g., 50%, 4 times). Change the image mode to Indexed Color, and use a Local (Perceptual) pallete, uncheck transparency, and use about 3 or 4 colors. Now go to Color Table, and change the 4 colors to the colors of your legos. You now have a pixel map to build your lego mural to. It looks squished, but your mural will not be (do not correct your aspect ratio). I have a couple variations saved as actions in Photoshop.
"Good enough" is often better than optimal when you're dealing with a real world solution to a problem. It's much better when "good enough" takes only O(N). :)
I would have thought so, but apparently not, because according to the article it took the computer 10 hours to run the program, so I must be missing something here.
You're slightly off in that the pictures appear to be stacked vertically, so you'd have to map based on the size of the smallest single-stud piece. But once you have the initial image, I'd have thought it would be fairly simple to figure out replacement pieces.
Unless it uses a complete search to try and find the "best" layout that works, trying all possible combinations.
And because I just can't resist it:
I started with some square nature images, and wrote some Java code
Oh, it's written in Java. Of course it takes 10 hours to run!
Somebody finally found a use for simulated annealing.
That's mostly one of those AI ideas from the 1980s that turned out not to be too useful. It's a very slow approach to hill-climbing.
It was cooler 20 years ago or so, when Playboy Magazine did a cover which had an image tiled from all the previous covers.
What would be really cool would be a robot arm that assembles any source image in a Lego target at a specified scale, after the software calculates exactly which and how many bricks are required in the "palette" bin.
And if that robot arm were made from Lego Mindstorms, that would be even cooler.
If a program could run a Mindstorms arm that is totally rudimentary, put together in under 15 minutes by a human, then upgrade itself into the arm required to assemble these images into Lego sculptures, and then assemble the sculpture, well that would be the coolest.
--
make install -not war
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.
FTA: "So the Java program runs for about ten hours for each image..."
Ok, so impressive yes. Still, can't help but wonder if c++ could have helped here...
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.
And then write it in C++ instead of Java.
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, ...)
Reminds me of this music video by The White Stripes.
Making it structurally sound is trivial. Just offset each block by 1/2.
There are some other complications. For example, you probably want to modify your dithering algorithm so that it's possible to heuristically swap adjacent "pixels" that changed by error diffusion to make longer contiguous horizontal blocks while still minimizing diffusion propagation (this may mean diffusing error in multiple directions or modifying diffusion propagation weightings).
After that, you don't want to simply combine horizontally adjacent blocks if you want your final LEGO creation to be "solid" - i.e. have good interconnectivity. An example of a really bad image would be the NTSC test signal vertical bars, if you built that, you would have large vertical columns that could be separated. Basically, you'd want to insure a minimal overlap of the horizaontal brick gap between adjacent rows if "solidity" was one of your goals as well.
Organic images which allow for noise introduced by the diffusion dithering also work well for avoiding hard vertical lines that decrease the strength and stability or "solidness" of the final product.
How cool would it be if the lighter parts of the image were protruding just slightly, to enhance the illusion of depth? I can't for the life of me believe this would be that hard, if the guy already came this far with his program.
Making good interconnectivity is trivial. Just use blocks of minimum width 2 and offset each row by 1. Instant perfect stability.
The dithering rules drive the brick color rules (this is the rasterizing pass), so there's no conflict there. The strength rules definitely are superseded by the color rules. There's no conflict at all.
The reason the strength rules aren't as important as the color rules is that the strength rules don't affect the structure's integrity all that much. The right way to build the image is at least two layers deep. There's the image layer and then there's a structure layer, tied together with double width bricks scattered throughout the whole. The structure layer definitely disallows vertical edges lining up and provides the actual strength of the project. The only real reason to eliminate edges lining up in the image layer is to reduce the appearance of extraneous lines in the final image.
This problem is linear complexity O(N). And if I know my future co-workers at Google at all, it will be an interview question before the week is out to demonstrate why it's O(N).
Only a google employee could afford that much lego...
"So the Java program runs for about ten hours for each image..." - aalib does almost exactly the same type of comupatation... in real time. It is true, that resolution is just 80x25 or 80x50 (characters) instead of 250x100 lego slots.
Why does it even need to be structurally sound? the pictures are mounted inside a frame.
These comments are my personal opinions and do not necessarily reflect the opinions of the other voices in my head.
Algorithm,
Didn't look at it, but the article says it's optimized for
- Rigidity (and NO it's not just, offset every row by 1/2, that's perfect rigidity, you're looking for a tradeof here !)
- Resemblance (int this case the way to go is NOT to try to match a dithered image but rather to compare the distance of a blurring of your candidate image to a blurring of the original image, at different blur width.
It's easy but no trivial.
\u262D = \u5350
That's kinda hard with the 1x1 blocks the parent suggested.
Yeah, I can't believe he wasted ten whole hours of computer time to find the optimal solution when he could have found a lesser solution in less time! Except that each image took fifteen hours of assembly time. And a less sturdy layout might take even longer to assemble. And the simple solution posted below of doubling the thickness to add a support layer would merely double the cost. Other than that, this project is a complete waste of leisure time!
Don't the 'square' Lego blocks actually have a 2x2 'pinout'? Thus greg_barton's suggestion in the GP sounds correct to me. Please correct me if I'm wrong (I want to know), but I think greg_barton is right --- his algorithm does sound both correct and simple.
Dr Superlove 300ml. I use my powers for awesome
Geeks will inherit the earth my ass.
Well, the geek who started Various, Inc., which runs "alt.com", "adultfriendfinder.com", and "friendfinder.com", recently bought Penthouse.
Perhaps this is a candidate for a new benchmark for The Computer Language Benchmarks Game.
Dr Superlove 300ml. I use my powers for awesome
If those are the questions asked during an interview, then I'm sorry for you. Not for having to endure this kind of process, but for wanting to work at such place.
Real engineering isn't about impromptu "mad skillz" at solving puzzles or problems with a single solution (as in "the interviewer thinks he is really smart so any solution better than his - considering other priorities - is wrong"). Most nerds I know, who do great at silly puzzles, suck at solving real world problems. And real problems are the ones that need more than a few minutes of smart-ass thinkering.
In fact, most people who are truly smart (and not just wannabe-geniuses- the kind who thinks he is really smart and focus on subjects considered "hard" but that are, in fact, just niches with simple, and sometimes incomplete, math formulation) feel offended by such kinds of "challenges".
But then, Google has one of the most improductive R&D departments of the planet, if you consider all other US$ 100 billion companies. It makes sense that the place is filled with quantum-physics types. Those are the ones who ruined academia, spending less than 10% of the time thinkering with math equations (and doing only that and nothing else - this kind of people never really thinks about the issues they're dealing with, they just want some factory-like work to fill their times) and 90% of the time writing their final report and acting as the lab's intern, ending up with the same title (PhD) as other people from the past. People who actually achieved something.
I blame Einstein's fame for all of this, actually. All those "omg, please tag me as genius" types are doing PhDs and working at particle accelerator projects mostly because Einstein helped to bring a good light into the act of doing academic work. The funny thing is: Einstein never focused on factory-work-like math formulations. His focus was much harder and less glamorous (considering today's values of academia) than that: he focused on thinking about how things worked. He focused on THINKING.
The US is screwed, actually: while most people hate science, the small part of society that focus on science are actually failing really hard at it. They think they're doing great, as their life is about patting each other on the back, but they're actually failing.
You can get 1xX and 2xX blocks for X=1,2,3,4,6,8. The 1x1 blocks are less common, but they are available.
Goddamn that should be +5 insightful, not +4 funny! Mod's where are you?? :-P
I work in an R&D group in a specialized field; some of the people who run the groups we interact with are amazing pieces of work, who really believe their way is the only way. Pointing up that someone's proposal violates an obvious natural law is supposed to be confined to weekend drinking with friends...Not a design review.
As a nation, we have way too many religious sects which label knowledge as bad because it includes evolution and the scientific method; critical thinking isn't good for religious institutions OR despots.
Business as a whole in the US doesn't want their workers too educated; then they would have to pay them, and give real benefits.
We are totally screwed either way the election goes; the two frontrunners are two cheeks of the same ass, unfortunately. What America needs to save itself is General Ripper (from Dr. Strangelove)hitting Washington during a joint session of Congress; thats the only way we get free of those guys. Where's Slim Pickens when you need him? (lol)
Truth isn't Truth - Guliani
I was thinking the 2x2 pinout block would be the quanta.
He's using simulated annealing. The idea is, you start with some state you can get to easily, and then either a) make a random change to the state or b) make a change that tries to improve the state. You have some variable T that determines what percentage of the time you do a. It starts out at some high percent, and then slowly goes down to 0%. The more slowly you decrease T, the closer to optimal your answer is. You can even find optimal solutions to NP complete problems if you let T decrease infinitely slowly.
Basically, this took ten hours per image because he wanted really good results.
Or the Rubik's cube art kicking around like Rubixel or the portraits the space invaders guy did.
simply, wow! that beats Google's best by an order of magnitude
can someone explain why you would use simulated annealing instead of genetic algorithms for this problem?
can someone tell me why simulated annealing is better for this problem than genetic algorithms?