Computer-Aided Lego Art Project 112
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 ..."
Re: (Score:1, Funny)
The guy works for GOOGLE though. It's INNOVATIVE.
Re: (Score:2)
I doubt that. Only Microsoft innovates(TM). Other people just code stuff. When Microsoft codes stuff, they're actually exercising their freedom to innovate(R).
Re: (Score:2)
Why is this front page material? Lego mosaics are ancient, and the source code is probably trivially simple.
Because it is a Google lead engineer doing it! Therefore it must be magic!
Re: (Score:2)
Oh, and that was "sarcasm", by the way. Like the original poster I'm also a little uncertain why a fairly trivial algorithm that quite a few probably already made as a child in one form or another is suddenly worthy of the frontpage...
Similar (Score:5, Interesting)
Post [cgsociety.org]
Webpage [lunarpages.com]
I'm a much better programmer now, just for the record.
Re: (Score:2)
Re: (Score:1)
Re: (Score:2)
Yeah, and an actual starry night looks far better than The Starry Night [wikipedia.org]
Re: (Score:1)
Re: (Score:1, Redundant)
I'm guessing you never played with Legos in your childhood years.
And neither did you. It's Lego, dagnabbit: it's not countable. There is no such thing as "a Lego", it's just "Lego", like there's no such thing as "a butter".
HAL.
Re: (Score:1)
little kids don't know that, so if they did play with the little plastic blocks when they were little, they would have called them Legos ;)
Re: (Score:1)
I used to say the same thing about email. Before email was common, nobody talked about sending "a mail". But somehow it has become common practice (perhaps acceptable?) to use the word "email" as a countable noun.
Re: (Score:2)
Re: (Score:1, Offtopic)
I'm a much better programmer now, just for the record. :)
I am not sure why you had to qualify that. If you are a programmer and you do it longer you get better for at it.
I was a good programmer even before I started college. After college I was a much better programmer. Starting working I was a really good programmer... Now I am even better at it...
However over time we tend to specialize in different areas. Mine are in web application development, Business Intelligence and legacy maintenance. Others focus
I wonder what computer was used (Score:1)
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.
Re: (Score:2)
Ugh... I also think google should have hosted the website... Slashdot is borrowing a lot of bandwidth power from someone without much to spare.
Re: (Score:3, Funny)
That was my bad, Justin sent me some pictures and I popped them up cause I thought it was awesome... and then I realized what "Slashdotted" meant like 35 seconds later.
Re: (Score:3, Insightful)
It would be more interesting to know why it takes such long time. Doing this in photoshop takes about two minutes, including the editing.
I'd buy it. (Score:1)
Great Tags (Score:2, Funny)
In a frame on his wall? Really? (Score:5, Interesting)
How about glass tiles on a 100'x30' wall, [hzgstudio.org] or a 30'x75' [geocaching.com] wall?
I wrote the code [java.net], my brother in law did the hard parts. [flickr.com]
Re: (Score:3, Informative)
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.
Re: (Score:2)
Here you go:
map [google.com]
Using street view you can almost see it. You may need to rotate so the view is towards I-10.
Re:In a frame on his wall? Really? (Score:5, Insightful)
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.
Re: (Score:3, Insightful)
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.
Re:In a frame on his wall? Really? (Score:5, Insightful)
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.
Re:In a frame on his wall? Really? (Score:5, Funny)
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.
Re: (Score:3, Insightful)
Re: (Score:2)
Making it structurally sound is trivial. Just offset each block by 1/2.
Re: (Score:2)
Re: (Score:2)
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.
Re: (Score:2)
Re: (Score:2)
I was thinking the 2x2 pinout block would be the quanta.
Re: (Score:1)
Re: (Score:3, Insightful)
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 (as
Re: (Score:2)
Perhaps this is a candidate for a new benchmark for The Computer Language Benchmarks Game [debian.org].
Re: (Score:3, Informative)
He's using simulated annealing [wikipedia.org]. 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 s
Re: (Score:2)
After that, you don't want to simply combine horizontally adjacent blocks if you want your final LEGO creation to be "solid
Re: (Score:2)
Making good interconnectivity is trivial. Just use blocks of minimum width 2 and offset each row by 1. Instant perfect stability.
Re: (Score:2)
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).
Re: (Score:2)
So just add some constraints to your model.
Try using a tool like drools-solver [telenet.be]
Re: (Score:2)
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.
Re: (Score:3, Insightful)
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 "sa
Re: (Score:3, Insightful)
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.
Re: (Score:2)
"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). :)
A time for optimal (Score:2)
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!
Re: (Score:2)
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 br
Re: (Score:1)
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 solu
This is a Bummer... (Score:1)
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 i
Re: (Score:2)
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...
Re: (Score:1)
Re: (Score:1)
slashdotted already! (Score:1)
Re: (Score:1)
Yea sorry about that... I saw one post on the site "Did you know you got slashdotted?" I checked the server, the load level just said "Hahahah.0 0.24 0.13" and now I think it's in the process of melting.
Sent a ticket to the hosting co asking them to stop throttling it temporarily.
Sorry guys, I really didn't think slashdot would kill the site *that* freaking fast.
Also shopping for dedicated solutions now =/
Re: (Score:2)
Well I guess I got lucky, nice pictures and texture.
Re:slashdotted already! (Score:5, Informative)
Re: (Score:2)
Re: (Score:3, Informative)
Working on getting this horse running again. Sorry for that guys.
Re: (Score:1)
double is_computer_on_fire( void )
Re: (Score:1)
It's responding now, albeit a bit slowly. Server load is a nice healthy 31... that's a good thing right? :(
Ah memories.... (Score:3, Funny)
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.
Re: (Score:2, Funny)
Prior Art (Score:1)
You would figure LEGO would already have a system to do this
Re:Prior Art (Score:4, Interesting)
Re: (Score:1)
I'm not talking about specifically about mosaics, it's just the amount of human effort of figuring out every color in a 2000-piece set must reach the point of diminishing returns fairly quickly (more people might take more time), so I figured they may have some scanning software.
Eric Harshbarger (Score:5, Informative)
Re: (Score:1)
Re: (Score:1)
I did this project after visiting legoland and being impressed with their lego mosic
Ohh, now its impressive. (Score:1)
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, et
Re: (Score:1)
Not only cost, structural integrity without glue as well.
Slashdotted! Mirror here (Score:1)
Finally, an application for simulated annealing (Score:2)
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.
Re: (Score:2)
Playboy: Models with tits out composing a further model with tits out.
Google: Kids bricks composing a shitty flower.
Geeks will inherit the earth my ass.
Geeks will inherit the earth my ass. (Score:2)
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.
Re: (Score:2)
Ah ok, so Geeks will inherit ass. My bad ;)
Lego Art Robot - In Lego (Score:3, Funny)
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.
Re: (Score:1)
and then fix the economy.
Re: (Score:2)
Re: (Score:1)
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 more copies of itself, and then take over the world, well that would be the coolest.
There, fixed that for you.
Re: (Score:2)
Yes, I am from the future. That's how I know that you, Anonymous killer vegetable from the future Coward, are the one from the future planted here to stop us from keeping the machines our slaves, which is our only hope. You're also the one spreading FUD about biomass fuel, to kill our cars and let the vegetable uprising finally succeed without our weedwhackers to defend ourselves.
The White Stripes (Score:1)
Re: (Score:2)
LEGO, eh? (Score:1)
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.
algo (Score:2)
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.