I work for a mill that cleans and sorts grains and beans (taking the rocks out, stems out, etc.), and it's fascinating to see the parallel invention of something really similar! We have a bunch of different steps:
1) Air is blown through the product and any dust is taken out.
2) The product is run through a bunch of screens that take out anything too big or too small.
3) The product is put through a gravity separator to separate based on mass.
4) Finally, the product is put through an optical sorter (https://www.youtube.com/watch?v=O0gWUeqzk_o) which uses blasts of air to push out unwanted materials from a stream of falling product.
I'm sure you could use the same process for Legos. Not sure about how to distinguish between branded and unbranded Legos though.
What is the %age by weight of 'trash' versus 'good stuff' for such a sorter?
I do use screens for various pre-sorting stages, not shown in the article. The sorter is only good for parts up to 40 mm and anything that isn't a wheel or round so it will roll away while being imaged.
That's by far the bulk though so for me if it does that part well it is already more than worth it.
Branded/unbranded: spectrum is different (far more different than you would say by looking at it with the naked eye), weight does not match for the part (though this can be very close with really good fakes), logo on the studs is different.
I've been thinking about doing that gravity thing, but a bit more fancy, rather than just a binary sort to shoot parts in several directions, an alternative is a spiral slide under a steep angle where parts are fed in at the top and ejected when they reach the right bin.
That's a lot more complicated to make than what I have right now mechanically and also the time available for a classification operation would be much shorter, but it would allow for a much larger number of output bins without taking up a whole lot of space. So maybe a next generation, if I still need it (this one is going through piles of lego now).
> How many bins are you organizing your Lego into?
Seven, so it takes multiple passes before it is done.
> Or was this more just a proof of concept thing?
Tough question :) No, it's for real it really has to sort through the 2000 kg, but if it needs to be beefed up or changed to get to the end then I'll do it. The next step 'up' would be a machine designed from scratch incorporating all the lessons learned with essentially unchanged software. There are still some limitations that could be addressed but then you'd lose the training set and you'd have to start all over from scratch. That might be worth it to get the last 1% error or so, so if this ever becomes 'real' then I'd have to do that. I highly doubt it will get to that though. time will tell.
> Plans to launch a Lego sorting service? ;-)
Not at present, though you're not the first person to think of that, parents with kids are suggesting I should make it mobile to visit people at their homes for $x / shot :) Still, that will only happen if I really have nothing better to do, which means likely never.
> Still, that will only happen if I really have nothing better to do, which means likely never.
Don't sell yourself short. You built the thing, after all. Could be some fun road trips with, I'm sure, gracious hosts to entertain you during Lego sort. That could be a whole retirement life right there ! ;-)
Problem with that is the "errors" in the real output bins will be encoded into the next generation of neural net and no progress will be made. On the other hand, the dataset could be used as a starting point that could be one-time filtered and improved by a human.
OP is familiar with the secondary marketplaces and knows if he could classify and sort well enough to make sets, then could potentially make money buying bulk and reselling sets on these marketplaces.
It could be a real business. He's already proven he has the chops to design it. If he doesn't, I don't doubt someone else will try.
Obviously Lego itself could do this but probably make more money from melting and recycling their own parts under their brand as new, like Apple does with its recyclers. Do we know if Lego is recyclable as new Lego by melting?
No, Lego does not recycle. But there is a very lively secondary market.
There was a short period that Lego allowed people to design their own sets and order them through Lego but it was so popular they had to shut it down.
People even buy new sets to sort them out just to get new bricks to combine into their own creations without having to buy them in bulk and not being able to use half of what they buy.
Well then, it sounds like Lego isn't interested in furthering either a custom or secondary market which could undercut their new sales. That is a business opportunity, no?
Could you make money just buying bulk, sorting out rare parts, and reselling those?
Lego definitely likes the secondary market, because the Lego market turns out to be pretty efficient.
The price of buying a new (or used) box vs. the price of "Bricklink"ing the parts is usually pretty much in favor of the former, which makes sense since the latter involves more S&H fees.
In additions, new moulds or new colors for existing moulds come up all the time (yet new moulds are all designed in the same system, so that they increase the versatility of Lego rather than Playmobil-izing them[0]). Therefore, advanced fans who design their own creations and buy bricks in bulk do get lots of new Lego boxes. For example the VW Beetle model[1], besides being really cool in itself, had a lot of azure bricks, including many shapes that had never been realised in that color. Likewise for some Architecture boxes.
[0] "New bricks are too specialized" is the Lego version of "HN is turning into Reddit"
Cool. I know some folks in Taiwan who would be very interested in this sort of thing. If you ever come through this way, I'm happy to show you around! Understood that your consulting work pays more and takes priority. Still crossing my fingers for part 2 tho :-D
> Lego isn't interested in furthering either a custom or secondary market
Once Lego's patent expired it tried a fairly shady legal theory that the interconnect shapes were trademarked/trademarkable. They pursued this all the way to the Canadian Supreme Court where they lost unanimously.
It seems like the wheel problem could be solved by a dowel rod that would keep things rolling along until they fell over? I suppose that unfortunately gives another way for the thing to get clogged up?
I'm surprised that this strategy isn't more quicksort-ish, I was expecting a first pass into warm or cool colors, then another pass into large or small lego, etc.
Everybody that hasn't sorted lego in bulk says the same thing :) The color sort would not help because in the end the idea is to get the same shaped parts in to a bin, not the same colored parts. Our brains are much better at picking a red part out of a background of similar shaped parts than they are at picking out a red part of a certain shape from a background of other red parts with different shapes.
As for the multiple passes, that's actually how it works, the first pass sorts into the 7 most common categories and then quickly works down from there. But the 'runoff' bin is by far the largest at the end of every run. After 3 passes the bulk has completely disappeared and most of the remains are sufficiently rare to be dumped into the right container individually. It goes pretty quickly: first pass: 7 bins, second pass: 7 bins again, but 49 if you put the first seven through again (but in larger volume accumulated from several runs on smaller lots). And so on. Since the bulk of the lego is in those first 49 and the value is in the remainder it doesn't take long to add value to a pile.
As for the mechanics, any obstruction, no matter how well intended will immediately become a point for a bridge to anchor to.
What is the back of the enveloper calculation of doing it by hand? Doesn't seem like it would take a few high school students that long to go through the 2000kg and come out with a very nicely sorted set of Lego bricks.
I work in a steel mill we use a similar setup with an optical camera to size streams of Ore and Coke particles. One thing you could look into is using a vibrating feeder (sometimes called a 'vibro') this is what we use to stop screens from 'pegging' - similar issue to the bridging problem mentioned in the article.
High-speed optical sorters are the sort of behind-the-scenes tech that make me feel like I'm living in the future. I have vivid memories as a child watching people winnow rice by hand using wide, flat bamboo baskets.
Had I seen something like the optical sorter back then, I would have thought it (Arthur C. Clarkeian) magic!
> it's fascinating to see the parallel invention of something really similar!
This isn't parallel invention - the principal of optical sorting and air ejection are well known and understood. (Which is not to lessen the achievement in building this, but building and inventing are not the same thing.)
Dunno who here is old enough to remember but back in the day every bag of chips used to contain a few burnt chips. Well, thanks to those computer vision air blasting sorting machines theres no more burnt ones in the bag! They all get air blasted out and now chips are uniform.
Sorting beans was the exact thing I was thinking of when watching this. I process a lot of chickpeas at home, and the quality of the dried chickpeas going in is quite mixed. There are some split ones (not good for sprouting), and some duds which won't soak or sprout even though they're whole.
I think that people might pay for the convenience of getting a bag full of proper chickpeas with no duds and no stones (I've heard of this, but never really seen it).
Maybe some day Suraj and NuPak will go a little further with their cleaning and get rid of damaged beans and not just stones.
Though, frankly I think they could do better than average with a specific gravity/densimetric sorter; it would probably require fewer passes through the optical sorter as well.
Sorting beans is a well-solved problem using a sort of waterfall (of beans) where computer vision selects the bad beans and air jets eject them.
The equipment costs money; and reduces the volume of "product" left for sale. Your problem is capitalism - the companies don't do that because it lowers their profit.
Thanks for sharing such a cool build and helping keep alive a hope of mine. I dream of a day I have enough time/capital to build/buy a Lego sorter, a robotic Lego brick separator (perhaps using high-resolution ultrasound/radar to detect where to insert the separator and where to push), pair that with an automated storage system in a subterranean vertical tunnel with robot arms similar to a robotic tape library keeping track of all detected parts and minifigs according to BrickLink categorization. Let the system keep it all organized (for example, bin overflows into multiple bins are automatically tracked as a single part and color combination), and I even have the choice to have it dump a random assortment into a big laundry-size bin, and build like a kid again, yet have it clean up after itself once I'm done.
There are a lot. There are two main specialized marketplaces, Bricklink and Brickowl, with hundreds of sellers (most of them operate on both sites). Most sellers also have a brick and mortar shop, others only operate online.
How do you deal with parts that are stuck together? I actually noticed one in your demo video, and was curious. This seems like it would be very difficult to classify, even in a sense to sort them into a "take these apart" bin.
They have a category all by themselves, get taken apart after the first run and then simply made to go through again in the next batch. The neural net is surprisingly good at classifying 'mess' as a category!
That's a nice solution. I'm reminded of a short video I watched on the Lego factory. One segment of it discussed the machine that put the minifigs' heads on their bodies. There's a big hopper of bodies that get drawn up onto a belt and then a camera makes sure each body is facing the right direction before putting the head on.
What do they do with bodies that are facing backwards? Is there a little side channel that flips them around? Nope, they just get tossed back into the hopper to try again. It's effectively random which way they'll be facing when they get picked up, so they'll eventually get through.
I thought that was a nice illustration of keeping things simple and taking advantage of processes you already have, and seems similar in spirit to this.
That's exactly what I love about this whole project. It's an endless series of seemingly simple puzzles. Then you start solving them and they turn out to be much more complicated than you thought. Until you hit the solution and then it's simple again.
And because it's effectively a coin toss, the average number of passes through the machine is just 2!
Just a remark from a Lego nerd: it's attaching arms to bodies, not heads. The neck has a stripe on the front, so that is where the camera looks at to determine which side is facing up.
Now you've got me thinking of Frank Abagnale (from Catch Me If You Can). He forged checks where the computer-readable routing number written in magnetic ink didn't match the bank the check was supposedly from, which resulted in the checks cycling nonstop back and forth through the Federal Reserve's system. They only caught on to it because one of the checks went through so many times it started to fall apart and got flagged as unreadable.
Maybe there's some defective minifig body with a mechanical flaw that causes it to always get picked up facing backwards, that's spent years being picked up and rejected over and over.
What about pieces that, put together, equal another larger piece? Say, a few "flat" pieces of the same color to make a larger 1 unit tall brick? Can you see the seams on these?
No, it would miserably fail at that unless I fed a whole bunch of such composites in and tried to teach it the difference between the two. Even then I'm not sure if it would work but it doesn't happen often enough to be a problem.
Lego makes two 'removal' tools, those are handy, then, I have a very sharp naked 4" blade that will take care of the hardest cases, baseplates will flex the tiniest bit and that will usually give you enough space to flip the top part off. Finally, a regular plate pushed at a 45 degree angle into the space between two other plates will separate the two without damage to any of the parts if you do it 'just so'.
From experience, Lego are nowhere near water-tight, say nothing about air-tight. The air between the pieces will leak out before you can build a high enough vacuum to pop them apart. I suspect this is by design: air-tight connections probably create enough of an internal vacuum that doesn't come apart with hand-force.
If the push-in joints were air-tight they would be harder to put together as you would be pressurizing the air in each connection. Then the internal pressure would be working against the friction fit to pop them apart again.
I made a mould out of Lego (to make Lego-shaped gummy candies) and with a thin coating of vaseline on the outside, it was indeed water-tight (and silicone-goop-tight too).
I think there were there were beads of water on the outside of the mould, but it was much closer to water-tight than I had imagined, even without the vaseline.
They're astonishingly well made for a children's toy.
They're astonishly well-made for anything. Making bricks that hold together firmly and come apart easily requires micrometer tolerances, and Lego is basically on the cutting edge of plastic manufacturing even today. That's why non-Lego brand bricks are always kinda crappy; no one else can make them as precise as Lego can.
This is being pedantic, but I imagine they probably could, but they don't because it's expensive. An upstart hitting the marketplace without the incredible brand of Lego, plus higher prices would be a monstrous risk.
There are one or two that come close but the precision and variance of Lego blocks is the stuff of myth that professional mold makers talk about on their lunch breaks. You have to really get close to the parts to see how incredible they really are, with the naked eye you won't see enough detail. The trick is repeat accuracy and that's where Lego is far better than their competition.
That said, they've been cutting quality, moving production to China, using cheaper formulation plastic. That's a bad move imnsho. The brand image is quality and people pay for that, if they ever seriously let that go it's going to be game over for them.
Obviously it's easy to say without knowing how frustrating poor quality parts would feel, but I'd take the quality reduction alongside a price reduction, I think. My 4yo loves sets like 31052 (3-in-1 camper), but the next step up in challenging, brand-neutral sets are around AU$400 which is hefty.
Of course, chances are they'll reduce their production costs but maintain the high prices.
I would like to challenge him with the creator expert set of modular buildings. 10246, 10255, etc. But 10255 is US$399 for example.
He already has 31052 and 31051 which I think are excellent 3-in-1 sets. Would love to see more like those. They are about AU$80-120 which is a workable birthday/xmas pricepoint.
That's really not that much (1-999 μm). Keep in mind that sub-1mm is micrometer, and 1mm is a huge distance. I'm sure that LEGO bricks have tolerances of single or low double digits of micrometers...
Wall shapes -- pushing them through rollers may exert enough force to start splitting them apart. Do this multiple times and they may fall apart.
For odd shapes -- clamping both ends then vibrating the grippers (just a little) could split bits.
It's an interesting problem. What percentage is still connected? May be better to pay a slightly higher price for bits are that not connected (distribute the job out to the sellers)
Are "mess" and "unknown" the same bin? I would expect that they get grouped together as a "human intervention" bin. It would be very surprising if you went so far as to train the neural net to recognize pieces stuck together as something different than an unrecognized piece.
Question: Were you able to utilise any data about Lego parts from Lego's own catalogues (current and historal) or technical specifications? It sounds like you trained the classifier manually. I imagine if you want to sort into sets you need to know what makes up a particular set.....does Lego provide an API or anything regarding parts/sets?
Further to that, if you have pricing data on sets you have a nice little optimisation problem - given my metric ton of parts, what are the most valuable complete sets I can make?
> Were you able to utilise any data about Lego parts from Lego's own catalogues (current and historal) or technical specifications?
I tried, but in the end a straight up train-correct-retrain loop took care of all the edge cases much quicker and much more reliable than any feature engineering and database correlation that I tried before. This is roughly the fourth incarnation of the software and by far the most clean and effective. HN pointed me in the direction of Keras a few weeks ago, that coupled with Jeremy Howard's course gave me the keys to finally crack the software in a decisive way.
> It sounds like you trained the classifier manually.
Only the first batch, after that it was mostly corrections. What it does is while it classifies one batch it saves a log which gives me more data to feed the classifier with for the next training session. There are so few errors now that I can add another 4K images to the training set in half an hour or so.
> Further to that, if you have pricing data on sets you have a nice little optimisation problem - given my metric ton of parts, what are the most valuable complete sets I can make?
I'm on that one :) And a few others that are not so obvious. There is a lot to know about lego. Far more than you'd think at first glance.
> I tried, but in the end a straight up train-correct-retrain loop took care of all the edge cases much quicker and much more reliable than any feature engineering and database correlation that I tried
I'd love to hear more about what you tried specifically. I'm considering doing this myself, and I was thinking of building a very large labeled dataset of 3d rendered images using the LDraw parts library and training on that. I could include hundreds of images per part by using different viewing angles, zoom levels, focus, etc in the rendering process. Did you try anything like that?
That's fairly pointless for me. There are some intricacies in the optics that would need to be modeled as well as the specifics of the camera and the light path, and then you'd still have all the weird gravity related trickery: parts that end up on top of each other, parts that can only be found in one or two ways on the belt and so on.
After endless messing around I finally bit the bullet and trained a neural net, from 0 to 100 in a few weeks and it is rapidly getting more usable now.
The feature detection code may get a second life though: as a meta-data vector to be embedded in to the net. But only if it is really necessary.
I'm quite curious though if you can get your method to work, especially for the parts that are very rare and rare colors.
I was assuming that at minimum I'd need to do a lot of filtering in order to get the camera images and renders into a state where they are similar enough to work for training.
Any chance that you'll be releasing source code for this project and/or your labeled dataset?
> Any chance that you'll be releasing source code for this project and/or your labeled dataset?
Yes, but not yet. It needs to get a lot better before I'm going to stamp my name on it as a release. Right now it is rather embarrassing from a code quality point of view, it has been ripped apart and put together several times now and every time it gets a lot better but we're not there yet.
Sounds like a great learning opportunity for beginners and people who haven't even started with machine learning yet, like me. I'm looking forward to it. If you're so inclined, a new blog post focusing on the machine learning process would be much appreciated, it's always interesting to read about the process of how somebody solved a real problem and implemented the solution.
Just so I understand the process correctly, did you manually sort some pieces to get a labeled training set, feed those through the machine, train the NN with that, and then manually correct the errors when sorting unknown pieces, added all those pictures to the same training set and then finally run the full training again? How many labeled images do you need to start getting acceptable performance? Are you training the NN continuously with every new image, or from scratch with an increasing data set?
Do you think a stereo camera would improve the classification in a meaningful way, or maybe a second camera from a different angle?
> did you manually sort some pieces to get a labeled training set, feed those through the machine, train the NN with that, and then manually correct the errors when sorting unknown pieces, added all those pictures to the same training set and then finally run the full training again?
Yes, but that cycle repeats every day. So the training never really stops, it just runs at night and the machine runs during the day. Today it sorted close to 10K parts and those images will now be added to the training set and then I'll start the training overnight so tomorrow morning my error rate should be much better than it was today and so on.
> How many labeled images do you need to start getting acceptable performance?
Good question! Answer: I don't really know but judging by how fast the error rate is improving between 100 and 200 per 'class' so that will be 200K images or so when it is one with the 1000 most commonly found parts.
> Are you training the NN continuously with every new image, or from scratch with an increasing data set?
From scratch with every expanded set. I suspect that's the better way but I have no proof. My intution is that it is hard to make a neural net learn something entirely new that it has not seen before and every day totally new stuff gets added. So I re-train all the way from noise.
> Do you think a stereo camera would improve the classification in a meaningful way, or maybe a second camera from a different angle?
I guess my lack of knowledge in the field shines through. Continuous learning is apparently under active research at the moment, and this blog post about it [0] is less than two months old, so your intuition was right.
If I were to guess the secret sauce I'd say that a mirror might be involved. Is depth information not worth the trouble for these kinds of classification problems?
> If I were to guess the secret sauce I'd say that a mirror might be involved.
You might be right there :)
> Is depth information not worth the trouble for these kinds of classification problems?
Yes, it would be, but there's much more to it than that. Also keep in mind that there are parts that are almost transparent and that no matter what background color you come up with there will be a bunch of lego parts that match it.
Would it help to get multiple images from the pieces on the belt, each illuminated from a different direction by some kind of strobe? Then the shadows could be incorporated in detecting some shape information. Might even help with translucent pieces.
Colored strobes may also help separating out different color pieces, although I expect that would be overkill.
One thing that I think could work is generating imagery from the catalogue for parts you've not seen before. Initialize a random starting position, and use bullet to have them fall into a realistic position on a plane. then raytrace from the top.
This way you could also cross-reference with part seller sites to see the going rate for a part and determine whether it's worth your time to separate it manually. Have a bin for rare parts worth separating by hand.
did you first download and use the pretrained net of an different classification task and use that as a default ? also, did you use batch normalization? also, did you try ResNets? you probably don't care at this point, but all of this would __massively__ decrease training time
My 9yo son is willing to give you his life savings of $41.56 to have an at home kit of this machine :)
I've played with OpenCV and tried for fun to train a HAAR cascade classifier to recognise a minifigure. It didn't work which made me realise one has to really understand under the hood of machine learning like this in order to give it good training data.
L(ego)S(sorting)ASAS would be very popular with the families I know, a little van that pulls up outside, dump the lot in and get back the bits sorted by kits :)
Lots of comments on here about the software, but I'm really fascinated by the hardware. Where did you get the conveyor belts and how much did they cost?
For the belt that lifts item up out of the hopper, I notice there's a little white hook (or platform, not sure what to call that) jutting out that does the actual lifting of the legos. How did you get the size of that right? Did you install that jutting-out part, or did it come pre-attached to the belt?
What tools are you using to make a computer do the actual belt rotation? I'm wondering how low-level it is - are you spinning the steppers directly or did the conveyor belts come with some kind of API? I'm guessing the belts don't have a USB port for easy control.
If you look closely at the belt you can see the traces of many failed experiments before I found a shape that worked without accidentally getting stuck on a part.
It is attached with super glue to the belt. I use the narrowest parts because that way it doesn't end up fighting with the curvature of the belt when it goes over the roller.
The belt rotation is done with a 3 phase AC motor hooked up to an inverter for the vertical belt, the camera belt is driven by a DC motor hooked up to a variable power supply.
So no steppers, that would have made life a bit easier because then I'd know (modulo some slippage) where the belt is positioned. So now I have to reconstruct that optically, hence the wavy line on the belt.
Can you publish the details of the h/w-s/w interface...the only piece I grokked was the vgg classifier. How do you go from a physical Lego on the hopper to jpg to class label to the lego in the correct physical bin ? I'd like to do this myself. I don't have 2 tons but definitely some 10k pieces. Thanks.
Hopper belt to camera belt is just a speed difference that causes the parts to become nicely spread out (at least, you hope so!), the camera stitches together frames to scan the part so a part larger than a frame can be scanned. Once the end of the part is detected it gets fed into the classifier which returns part id, category and color. Depending on what sort is set up a part then gets pushed into one of 7 bins, these periodically are emptied into larger bins and bags.
If necessary a lot can be pushed through the machine twice for instance to sort parts by length or to pick out sets (that last bit works in theory but in practice there are a lot of problems to overcome because of the limited number of bins to deposit into).
As for the hardware, there is a nifty little camera with a macro lens that connects to the USB port (noname Asian stuff), it has a 10x magnifying lens, a pololu servo/gpio to USB card to drive the relays and a Sainsmart 16 port relay board to drive the solenoids for the air valves.
The software is all in python with a generous amount of help from the people who wrote numpy, opencv, keras and theano.
The error rate is between 3 and 5% depending on how fast I set the machine, there are a number of sources for the errors, obviously classification errors, also sometimes two parts are too close to each other and even if the classifier got them right the airpuff for one pushes the other of the belt as well. To minimize this effect I keep the airpuff super short, on the order of 10 ms, which is about as fast as the solenoids can open and close reliably, but it does mean that if it misses even by a bit there is nothing to be done about it and that part will land in the 'other' bin.
That error rate is still too high but with every run the classification errors go down and that's the main component.
One nasty little problem was that I spaced the puffers too regular in the first iteration which meant that sometimes the parts would line up just so in the order in which they came under the camera so that more than one puffer would be active at once leading to a reduction on pressure and no parts would be pushed off the belt. That was a tricky one!
This is one of the greatest, most HN comments of all time! I'd love to do some hardware stuff but it always seems so inapproachable for a software-only person.
"more than one puffer would be active at once" — sounds like a job for prime numbers!
And that's exactly how it was solved. The puffers are now spaced prime distances apart and that took care of that, it would be harder for a longer belt because then you'd start wasting an awful lot of space next to the belt.
This is an interesting problem. I'm trying to visualize this and I must be thinking about the problem incorrectly; perhaps you can help me wrap my head around it.
Since the pieces fall onto the faster conveyor belt with random spacing, isn't it possible that two consecutive pieces will have the spacing of the puffers they are destined for (within margins), regardless of the puffer placements?
The spacing of the conveyor 'traps' is equal, the conveyor belt speeds are a constant. If the puffers are equidistant the chances of overlap are substantially higher than if they don't. Most conveyor traps take only one or two parts along. If there are many more parts they tend to fall in a clump and won't be classified so then there also is no problem.
In the end the error rate went down a lot because of a less predictable spacing. But you are right that if the pieces would fall with random spacings that it would not matter what the distance between the puffer stations would be.
The funny thing is that I spent a lot of time measuring out the vertical spacing on the conveyor in the hopper. If I had done that more sloppily it would have worked better :)
I had to think for some time on this one. Finally it occurred to me, that the pieces are some x distance apart on an average.
At any snapshot, the pieces are lying with a Gaussian distribution around x multiples along the belt i.e having sigma at x, 2x, 3x,...nx....
So for the bins to not overlap:
1) their width/span-along-the-belt should be lesser than x
2) And they can be placed at x, 3x/2, 5x/2, 7x/2 (i.e. prime multiples of x/2)
Wow! Learnt something useful today. Thank you. :)
Edit: I realize after posting that, my solution won't work! If somebody can explain how the prime thing works will be great. I can imagine, though, that the bin placements should be such that, at any given time the piece is only in front of a single bin. Meaning, no pair of bins should have a distance of x-multiple. I can guess, perhaps heuristics which work well, can be devised. But it will be great to know the mathematical solution for this.
What is the name of the hardware parts that are connected to the relay? I think you've called them "puffers", but searching on that didn't bring up any results. Are you able to provide a link to where I might purchase a couple?
They're simply 12V solenoids with an air valve attached, to that I've run a small 1/8th" tube to a piece of thin copper tubing that's open on one end. Nothing fancy or branded, the air valves are all attached to a manifold that divides the pressure from the compressor across all the valves.
12V on the valve -> air streams out of the corresponding tube.
Thank you very much for this fascinating post, nice work.
Did you use any other resources to learn about deep learning besides http://course.fast.ai/? I'm looking to get started learning, and wondered what the best way forward would be.
That was my starting point but I'd already played with neural nets when they first came out so that helped and I also did a lot of opencv stuff without any neural nets.
After that it was mostly googling each and every term that I didn't understand until it all started to make sense.
course.fast.ai is probably the fastest way to get something concrete going which is very useful if you need that instant gratification kick to keep going.
Another path: start doing Kaggle. Pick whatever competition looks interesting to you and just join in. In worst case you will learn a lot, and there will be people working on the same problems as you will.
EDIT: but some initial level of knowledge is advisable so you know how to pick a competition.
Awesome. Do you have a video of it running at full speed? Also, the bin at the end is for all the pieces save the fake/discolored/technic ones & see statistics on the PC or is there a more elaborate sorting scheme? Watching the belt go I was kind of expecting the pieces to be sorted by color or something, which would look neat but isn't very practical, I assume.
Sorting by color is useless unless you want to go and sort directly into sets (it can do that too but that's very much experimental, also it would take lots of bins and there are some details that are important to get right that are almost invisible to the camera).
A full speed video is super hard to shoot because you can't follow the parts as they move, they basically disappear because of the air puff being so short that a part is there one frame and gone the next. Right now classification takes about 30 ms, that's the limiting factor because that belt keeps moving during that 30 ms so you need to be 'back' at the camera before it moves so far that you can't stitch the next image to the previous one.
Another limiting factor is the relationship between the two belts, the second belt can only go so fast before the precision of the puffers starts to be insufficient to aim the parts into the right bin, they also carry too much forward momentum, and the second belt needs to go many times faster than the first in order to spread out the parts sufficiently. Yet another problem related to that: if you look at the video you'll notice that one of the little parts grabbers on the belt can push ahead of it quite a bit of stuff, if fortune is against you all of that lands on the belt in one go. By making that belt go slow it creates just enough pause between parts to be able to separate them with air without pushing the wrong part off the belt. It pays off to leave some safety margin there so I tend to set the second belt a bit faster than optimum and the first one a bit slower. That way the accuracy goes up quite a bit.
It took lots of experimenting and tweaking to get to this stage.
About 1 part per second is a practical upper limit right now, it can go way faster than that but then it starts dumping stuff all over the room :)
I'll see if I can shoot a video at a higher speed than the one in the post right now.
>also it would take lots of bins and there are some details that are important to get right that are almost invisible to the camera).
I wonder if you could build something that would use a small number of bins (maybe just two) and multiple passes.
The first pass could just get an inventory and just show you what sets it could build toward (with emphasis on sets that are the most profitable, closest to completion, or your favorites). The second pass would split off legos that are a part of the set(s) that are trying to be built.
You could also pass along what you think was a completed set again at the end to check for mistakes.
The number of bins is of course directly related to the number of passes. 7 is the largest that I can still fit on my desk so that's why it is 7 right now, I'd love to take it up to 13 that would make things much faster. Two would be so slow that it probably would be quicker to sort by hand because of the number of passes you'd have to make.
Thanks for writing this up and adding all these detailed notes! Super awesome work on this, it's very cool.
The air puffs seem like the most unreliable parts at the moment?
Maybe if you could have some manual labour, one thing to do would be to mount a project above the setup to shine a graphic you generate onto it.
If you have bins labeled, you could project the label next to or on top of the part as it's moving on the conveyor. That way if you have human pickers, you're not constrained by the number of bins with each needing its own air-puff solenoid.
> The air puffs seem like the most unreliable parts at the moment?
Yes, absolutely. There are ways to improve on that but nothing simple.
> Maybe if you could have some manual labour, one thing to do would be to mount a project above the setup to shine a graphic you generate onto it.
I don't follow you, what do you mean?
> If you have bins labeled, you could project the label next to or on top of the part as it's moving on the conveyor. That way if you have human pickers, you're not constrained by the number of bins with each needing its own air-puff solenoid.
Ah I see, no, the airpuffs are reliable enough for now even if they are the most unreliable part, besides humans would not keep up with the machine at speed. But it is a solvable problem, just not the most interesting one at the moment. The most interesting one is the hopper feeder belt because if I can make that work just a little bit better it will speed things up by a factor of 4 to 10 depending on how well it will work.
I tried faster but then it is pointless you simply can't track the camera fast enough from the hopper to the bin where it will end up. Hope that is satisfactory :)
I'm not sure you need to track. Why not some "how it's made" style slowmo videos? Don't forget the super generic soothing music and occasionally narrating.
Heh, that looks like a ton of fun, sorry you lost your van though! Also interesting to know that the pile of Lego Technic parts I've got from my lego bot building days actually might have some resale value :-).
Lots of interesting questions come to mind though, in that if you have two bits of Lego that are attached, what bin do you put them into? And have you looked at ways to automatically disassemble Legos? And did any of your purchases have Legos that were superglued together? (as is done in some displays.)
Most fun I've had programming in years. Finally something where I don't have to worry right from the get-go if it is secure or not.
> sorry you lost your van though!
So am I. I had a ton of work in that thing and even if the insurance covered the value they did not give me back the many weeks I spent building it.
> Also interesting to know that the pile of Lego Technic parts I've got from my lego bot building days actually might have some resale value :-).
It'd be better if you had some really nice boxed sets from the 60's ;)
> if you have two bits of Lego that are attached, what bin do you put them into?
'Other', then pick them apart and run them through again
> And have you looked at ways to automatically disassemble Legos?
Yes, but this is very hard to do without damage.
> And did any of your purchases have Legos that were superglued together?
I've seen a few bit here and there but for the most part that doesn't happen. Kids are pretty destructive though so you have to count with a good %age of damaged / unusable parts.
I would imagine that this is a hobby project and you're losing cash on it. But what would be the parameters of a profitable business? At what level of scale (if any) would it have to operate? And is there a lot of competition in this space?
Well, yes. It is definitely not going to make money if I count my time. But I learned an awful lot about machine learning and the present state of computer vision, far more than if I had tried to do that on something abstract. And when I look at the Lego bought-and-sold it seems to work out ok.
As for competition, yes, plenty, but all manual. Scaling up now that I have the software working is definitely an option but I have a good set of very well paying customers and not much can compete with that.
Frankly, the "present state of cv" as you call it, is far far ahead of the 5% classification errors you are running into on a standardized textbook problem such as this - the Legos are all blocky discrete plastic with super-saturated colors and very distinct features. You can easily drop the error by taking multiple pictures from different angles, using ImageDataGenerator during training ( since you are using Keras), especially with horiz and vert flips, and the usual set of tuning tricks - going deeper, dropout, l2 etc.
No, the real takeaway is that you have built something very impressive - a tangible physical classifier that uses vgg to get the error down to 5% with very little effort. Going from there to 0.5% would be quite easy if you post the training set so a bunch of people can try different things, see what works best for this situation.
Last week I trained a car to drive around a circular track with just a stupid mnist classifier, only 9 classes, 10 lines of Keras! State of cv is very far ahead these days.
That 5% is based on a relatively small set of images that is expanding rapidly (4K or so per run), so I expect that error to get lower quickly. Also, these images are stitched and so are far from perfect, the colors are all over the map due to discoloration and so on. Then there are certain nasty aliasing effects where a part will look exactly like another part from the angles the camera can look at the part. This is fixable but will require (yet) another redesign of the optics.
Dropout is at .5 both for conv and connected layers.
All those things you mention have already been done and yet the error is as high as it is. But this does not surprise me at all, the difference is that the pre-trained models actually do very poorly on this dataset and so I'm having to train them up from scratch. That's getting there though, another week or two and I should be in the tens of thousands of images to train with and then life will get a lot easier.
Data augmentation works well and has been enabled right from the get-go.
I'll definitely do another write-up in a while about the software end of things, once it crystalizes to something a bit more stable, I'm still hacking on it daily.
I will post the training set at some point, first it needs to become large enough. But with the machine helping now that is getting there, rapidly.
> Also, these images are stitched and so are far from perfect
Maybe you could use a push broom scanner? I don't know if there's any hardware available for consumers, otherwise that seems ideal for a conveyor belt application.
This is a very rough equivalent of that. The area outside the stitched part is used to keep the belt synchronized if there are not parts in view, hence that wavy line on the belt in the video.
thoughts on tumbling/turning the parts on the belt once identified for more pictures? It wouldn't add anything to the sort speed but it'd get you way more pictures. Thinking of that machine that tumbled dice automatically. Does the addition/removal of the belt in the background come into the recognition? Otherwise in air shots from a tumble tower or belt with trip on it would get you a lot more images.
The belt movement is continuous, parts that do roll around on the belt are coming out crazily warped because in each image the belt has moved 3 to 5 mm and the part has moved the same but probably in a different direction than the one the belt is moving in. Those images are useless. This scheme would work if you could always get the parts out of a single frame on the camera but they're much too long for that (24 studs long is the maximum).
What cameras are you using? I couldn't see it very well in the writeup. Also thanks very much for this post it's very cool. You should cross post to hackaday blog.
Because the details between some of the parts are only very minor and yet that can the difference between the part in its normal version or (for instance) its technic version.
> I haven't done any of the nn cv stuff yet, can you pair different image sources of the same item?
I took a chance on that and it seems to work. I just stack the images and present them as one larger image. Quite possibly that's 'wrong' and I should present the two images separately to two different nets which are then recombined at the end but this trick seems to work.
Huh I would have tried a 20mp dslr with a nice lens instead figuring it could pick up the differences. You can get Canon ones for about $450 on cl with lenses now.
Good to know it worked on the composite. Thanks for the info!
We have a local Lego re-seller (https://bricksandminifigs.com/) which I visit occasionally. One time I spoke to the owner about the business economics. They try to buy complete kits. It is not economical to re-create kits from parts if you sort manually. When they buy unsorted Lego collections from collectors/enthusiasts, they do a limited manual sort to pull out the most valuable pieces and then they store the leftovers. When I spoke to her, I believe she said she had 2 storage units filled with Lego that aren't economical to sort further. Run-of-the-mill bricks and pieces have no value other than scrap. The value is primarily in mini-figs and rare specialty pieces like clear acrylic canopies. Obviously, kits are valuable, but only if you don't have to create them by manually sorting. Also, used kits are much more valuable if they are sold already assembled as proof that all of the pieces are included. This assembly labor must be factored into the business model.
Buying lots off of Ebay, it seems like you risk buying presorted Lego which have already been picked over for the most valuable pieces.
2) the 1000 most common lego parts, 'other' and 'mess'. In the end the idea is to get to 20K classes and to sort directly into sets. This is very much a pipe dream at the moment but I think it is doable given a large enough set of samples. The problem is that you have to see all those parts at least a hundred times or so before it gets detected reliably.
3) too little :( The training data is still woefully insufficient but it is now good enough to bootstrap the rest. This took a while to achieve because without any sorted lego to begin with you have nothing to train with. So the first 20Kg or so were sorted by hand and imaged on the sorter without any actual sorting happening (everything into the run-off bin), then labeling the results by hand until the accuracy of the test set (500 parts or so) went over 80%. That was a week ago and since then it's been improving steadily day-by-day.
4) one training run per night, typically a few 100 epochs on the current set but, this will change soon. The machine is now expanding the training set rapidly with associated improvement in accuracy. This means that the training sessions are taking longer and longer but I'll be running fewer of them. What I'll probably do is offload training to one machine which will drop off a new set once per week or so and inference on another which is doing the sorting and capturing the new training data.
Checking the logged images for errors still takes up a bit of time though, but with the current error rate that is very well manageable. (Before it was an endless nightmare).
For more training data, I wonder if you could make Lego parts in Sketchup or some 3D program, then render them in a 'scene' similar to your camera setup using a renderer like Maxwell or V-Ray or whatever. Then you could maybe be able to generate unlimited numbers of sample images to train on.
I'm doing a similar experiment now to train a model to parse out an image of a blood pressure monitor that's a 7-segment LCD display. To do it I separated out each segment of the display as masks with Gimp/Photoshop and then I can create my own images by just overlaying them on top of an image of a blank LCD display. That gets me basically unlimited training photos.
If you could render the 3D parts from various angles, colours, etc then something similar might be possible.
Also, you said you're doing modified VGG and into 20k classes. That works, but another thing to maybe try is use binary_crossentropy as the loss function and a sigmoid (instead of softmax) on the final activation layer, to be able to do multiclass classification.
Then your labels could be a vector of shape possibilities, colour possibilities, or whatever you could divide your 20k classes into.
I've tried the rendering trick but it didn't work well enough, the real pictures seem to give much better results when used on unseen data.
> Also, you said you're doing modified VGG and into 20k classes. That works,
Right now there are 1002 classes, the 1000 most common lego parts, 'mess' and 'other'.
> but another thing to maybe try is use binary_crossentropy as the loss function and a sigmoid (instead of softmax) on the final activation layer, to be able to do multiclass classification. Then your labels could be a vector of shape possibilities, colour possibilities, or whatever you could divide your 20k classes into.
Tagging/multi-label classification is useful because it'll help tame your explosion of classification if you want to expand. For example, it can then handle stuck-together parts by tagging it as both parts rather than putting them into a generic 'other' classification, or you could include separate tags for colors or fakeness or damagedness, avoiding the need for 100,000 categories of 'fake damaged red square brick' etc. It might also improve learning since it's a more natural way of describing the data.
By expanding the training set you mean that a each new sample is added to next training set by default?
Do you use artificial augmentation of the training set (random rotations, translations)?
Somewhat related aside: I have also worked on a classification task (albeit, much simpler one): detect the direction of grain in a piece of wood. I built the first version by manually extracting features (essentially, a few direction sensitive Gabor filters) so that I could collect a training dataset for CNN.
Turned out that accuracy of manual version was more than enough (~98%) so I didn't get to play with fun stuff :(
> By expanding the training set you mean that a each new sample is added to next training set by default?
Every part that passes through the machine is logged and will be made part of the training set for the next round of training.
> Do you use artificial augmentation of the training set (random rotations, translations)?
Yes, quite a bit. But this is not of the same quality as really having more samples though it is definitely useful.
> Somewhat related aside: I have also worked on a classification task (albeit, much simpler one): detect the direction of grain in a piece of wood. I built the first version by manually extracting features (essentially, a few direction sensitive Gabor filters) so that I could collect a training dataset for CNN.
> Turned out that accuracy of manual version was more than enough (~98%) so I didn't get to play with fun stuff :(
Thanks for the responses! I have a feeling that projects involving vision will become more common with the fall in camera and image processing so I'm interested to learn from other's experiences.
> Slick! Do you use that to determine orientation prior to lamination so the laminate does not warp when it ages?
In this specific case- to reduce surface defects during planing. Interestingly, client forgot to specify this requirement when we designed the equipment which feeds planer. Feeding the boards in correct orientation was something the operators had learned from each other as they improved reject rates in downstream scanner but nobody in management knew about that.
I am kinda boggled that you thought "Huh, Lego, think I'll get into that" and immediately ordered two metric tons of Lego. o_O
I get that you thought (for some reason) that you would only win some small fraction of your bids, but ordering, say, a quarter-ton of Lego at a go isn't reasonable either. The whole episode is pretty hilarious.
You should have seen my face. Also, try to explain to your s.o. that you're about to buy an extra garage solely to house something that you have no idea how it will all work out and when - and if - it will ever go away again. And that was two years ago.
It really is hilarious. For me it's more or less business as usual though, I take lots of chances. Some work out and some don't. This one is still undecided.
Fascinating. It touches on the discolored and counterfeit parts but doesn't say how they are detected – I assume there was a lot of manual training of the neural net?
It's basically bootstrapped. Use the machine to sort a few kilos, pick out the mistakes, update the training set, let it train overnight, rinse, repeat. After many such cycles it is getting pretty good. The best part is when I think it has made a mistake but actually it is right and I'm wrong :)
The annoying part is that I can't always figure out by looking at the image what makes it make the right decision. That's a feeling I don't normally have with software, I can usually trace back the reason why.
One thought: I'd think creating a similar solution would make an amazing semester course for University students.
Maybe you package stuff up nicely and give it away as a course, or try and sell the plans as a course to one of the coding schools or large Education companies?
Building from scratch a sorting machine that works (however accurately) is no small feat for a student. It would be a great multidisciplinary project.
Imagine a group of student only had the rough scheme: which pieces do they need, maybe some templates, but then it's up to them to actually implement / build the thing.
Heck a university could even host a competition, where the machine with the fastest throughput + lowest % of errors wins :)
Exactly what I was thinking. For less advanced students, you could even provide more templates, etc. There's something to be said for long multidisciplinary projects.
This is amazing ! I am currently struggling to sort properly a few Technic sets (roughly equivalent to 5-6 shoeboxes), and one of the biggest challenge besides sorting, is to find boxes that are large enough to store the individual types of pieces. Any ideas ?
Every collector of Lego sooner or later becomes a collector of storage systems :) (Don't ask me how I know that...).
I use some relatively cheap plastic sliders stacked 10 high, parts go by length from the top down and by width left to right. Then there are departments for minifigs and associated parts as well as irregular stuff like base-plates and so on. Storage could easily be another blog post all by itself! It's a crazy problem.
For technic, which is many small parts I use small bins and bags inside the larger bins, but you probably could use a raaco rack or equivalent if you don't have too much of it.
Really awesome. What Im dying to know though is some stats on the profitability. On average what sort of groupings of parts do you get from the bulk Lego and what do they sell for vs what you paid for them? Is there a variance is the quality of the bulk lots? I presume once you've sorted out the rare Lego you could just resell the common stuff as another bulk lot, but if everyone does that how do you avoid buying stuff that has already had the rare pieces filtered out?
Bootstrapting rocks to speed manual labeling. I got to full unsupervised on coin designs and angles by augmenting with many different lighting angles with ws8211 led strips and correlating the angles. I almost can with the dates, but it's so easy to finish with bootstrapping. See http://www.GemHunt.com/dates for the 100% unsupervised classes.
Is this proof that Lego is the best educational toy for creating engineers?
What about an initial bucket for pieces that are too close to be reliablely puffed? Maybe you already do that, I couldn't tell.
On the issue pressure drop from simultaneous puffs, if you add a buffer tank with a pressure regulator for every two puffers, you'd probably avoid that problem. Like the little capacitors that used to sit by every 74xx IC.
There is a 'default' bucket (#7) to the side of the machine that catches everything that it does not pick out in that particular run.
The simpler solution was to just stagger the tubes a bit, that way all I needed to do was drill a few new holes. I see what you mean though, that's also a clever way but the 'feed' to the air valves is a single 6 way manifold that they bolt straight on to. It would be very hard to put a buffer between the manifold and the valves.
I see. So right now, if two pieces are too close together on the belt, they just go into the default bucket?
What is the limiting factor determining how many buckets you can operate with?
And I may have missed this detail, but you must perform a multi stage sort since you just have a few buckets? What is the level of the final sort, and what becomes of the parts at that time?
> So right now, if two pieces are too close together on the belt, they just go into the default bucket?
Yep. But this fortunately does not happen often.
> What is the limiting factor determining how many buckets you can operate with?
Belt length, measurement precision during the stitching, cumulative errors in the math determining how far the belt has moved.
> And I may have missed this detail, but you must perform a multi stage sort since you just have a few buckets?
Yes.
> What is the level of the final sort, and what becomes of the parts at that time?
A single part category in multiple colors, or and that's the next level, all (or at least most) of the parts required to make 6 sets + remainder.
That final stage is a bit tricky, it also interfaces with a database that keeps track of the lot id of that set and what parts are still missing. I have most of the pieces for that second idea ready now but they are not yet tied together.
A simpler way to maintain steady pressure with simultaneous puffs would be to use a oversized manifold, and put the valves on the end of the copper air lines, perhaps mounted on a board or something. Maybe you could gang up a number of puffers for larger parts.
And what about doubling the bins by placing them on both sides of the belt, with puffers blowing in both directions?
Or a laser trip sensor to get a more precise belt location measurement?
> A simpler way to maintain steady pressure with simultaneous puffs would be to use a oversized manifold, and put the valves on the end of the copper air lines, perhaps mounted on a board or something. Maybe you could gang up a number of puffers for larger parts.
That's an option. But the problem is solved so that part is ok now.
> And what about doubling the bins by placing them on both sides of the belt, with puffers blowing in both directions?
It does that, you can see it in the video if you look closely and also in one of the pictures. There are two bins at the back and four in the front (that's the easiest way to fit them right now).
> Or a laser trip sensor to get a more precise belt location measurement?
Or a gray code printed on the belt! That would give you absolute positioning.
That feature engineering is mostly dead, that ML is now accessible even to noobs like me (thanks to http://course.fast.ai/ and other), that you don't need to build stuff like this in C or C++ any more to get decent speed.
The machine learning itself: models are hard to train, harder than you'd think at first glance, that you need a lot of data for training and if your particular application does not have any samples then you're going to have to come up with clever ways of making images because the quantities needed are not something you can just go and shoot by hand.
Also, that bootstrapping is a viable method, that way the machine does the hard part and you only have to correct, this takes the sting out of 90% or so of the work of labeling a dataset.
Yes, for one the weights are totally new, second I dropped a bunch of layers because vgg16 is way too powerful for this task. As I get into more kinds of parts I may have to put those back in though. Finally, I added dropout after the convolutional layers as well as after the fully connected layers, that seems to help a lot with the accuracy. All this was arrived at empirically, I don't know enough about neural net topology to go about that in a more analytical way but it does the job.
As for opensourcing it, yes, but then likely lego would have a trademark case so I would probably use another name. The whole thing would make for a pretty neat Kaggle competition.
Several years ago I designed an industrial machine that is used untangle and sort nails, screws, etc for feeding robots in automatic product lines. Main elements were vibration beds (using eccentric), slopes with geometry to sort out and pneumatic cylinders - to untangle items in high speed.
I've watched hours of videos of industrial equipment to figure out how best to tackle this problem. It's absolutely incredible what is out there in industry both for sorting, feeding and handling. Hypnotizing.
Yeah they're insane, recently saw a video of bean sorting machine that did spectroscopy on every single bean to see if it had mold or fungus and was crazy fast.
if you leave them covered in a dry room eventually the shit ton will be lighter. Though in the long run it will all be destroyed when the sun burns up the earth.
1) Air is blown through the product and any dust is taken out. 2) The product is run through a bunch of screens that take out anything too big or too small. 3) The product is put through a gravity separator to separate based on mass. 4) Finally, the product is put through an optical sorter (https://www.youtube.com/watch?v=O0gWUeqzk_o) which uses blasts of air to push out unwanted materials from a stream of falling product.
I'm sure you could use the same process for Legos. Not sure about how to distinguish between branded and unbranded Legos though.