Sign in to follow this  
leafan

Sorting Lego - A.I.

Recommended Posts

Hi everybody,

I am the sort of person that enjoys buying bulk lots of used Lego and trying to piece together the sets from the pile.

This is very difficult task but doable with enough time and research, yet there's always some things that you cannot hope to find.

I was thinking on how to solve this and I started thinking about the Artificial Intelligence that companies like Google use to recognise details in images (called Machine Learning) and the more advanced A.I. that S.E.T.I. has recently used to find previously overlooked Fast Radio Bursts from distant stars.

I was wondering if somehow this type of A.I. could be used to first inventory every single Lego element, and then apply the knowledge of these parts to identifying sets, or likely sets (based on percentage of parts present) in a given lot.

It turns out that Google's A.I. is actually open to the public for use, which opens up some posibilities.

Now I'm interested in this stuff but I'm not a tech expert by any means - so I'm floating this idea here in order to get people's opinions on this.

Thoughts?

Share this post


Link to post
Share on other sites

I would say AI / machine learning would be very suitable for sorting LEGO. Google has wonderful AI API's, but they have fairly recently chanced their policies and you must pay after a while. I think a better direction would be: https://www.google.com/search?client=safari&rls=en&q=opencv+lego+sorter&ie=UTF-8&oe=UTF-8

This one especially seems promising: https://spectrum.ieee.org/geek-life/hands-on/how-i-built-an-ai-to-sort-2-tons-of-lego-pieces. He does use a Google-based library (TensorFlow). The graphics card seems to be quite expensive though ;) (I guess from all those bitcoin miners).

Share this post


Link to post
Share on other sites

Interesting, thank you. I will have to give those a read when I get home.

I had suspected that somebody else would have thought of this but my initial searches came up blank. I guess original thought is dead afterall! lol.

Exciting possibilities I think.

Share this post


Link to post
Share on other sites

"Now I'm interested in this stuff but I'm not a tech expert by any means - so I'm floating this idea here in order to get people's opinions on this." it is quite a challenge though, even with frameworks from Google. A student of mine just terminated his bachelor project last week on Machine Learning / Object detection and he is a fourth year Software Engineering student. IEEE is a respected source though, so that guy definitely knows what he is doing.

Share this post


Link to post
Share on other sites

Yeah I'm sure it'll pose a challenge, but I will look more into it.

The 2 major hurdles for me are A) the fee Google now charges for the use of the API and B) matching the majority of the Lego elements to the images.

The latter part will take months, even for my own collection, but that doesn't put me off.

Also the technical jargon used in the set-up process is something I'll have to try to learn.

It can be scaled back from the IEEE source though, since my needs are smaller in scale (i.e. fewer pieces, I can manually scan images, no converyer belt or blower needed).

Share this post


Link to post
Share on other sites

Not to spoil the party, but you could just sort LEGO conventionally mechanically and electronically. The time you would need to invest in writing your code and training the AI could just as well be spent in constructing a machine and writing way simpler bits of code to control a camera for color-based sorting. Seems to me people go out of their way to find uses for AI just because it's hip. Just sayin'...

Mylenium

Share this post


Link to post
Share on other sites

Mylenium

Color is the least of my objectives when sorting. Shape is much more important to me. When I bulk buy I sort by several informal trinary objectives and only when I'm at the item stage do I separate by color.

Ed

Share this post


Link to post
Share on other sites
52 minutes ago, Mylenium said:

Not to spoil the party, but you could just sort LEGO conventionally mechanically and electronically. The time you would need to invest in writing your code and training the AI could just as well be spent in constructing a machine and writing way simpler bits of code to control a camera for color-based sorting. Seems to me people go out of their way to find uses for AI just because it's hip. Just sayin'...

Mylenium

Well I've been doing it conventionally for some time and it's very time consuming and repetitive.

For example, I could find a rare part in around 15mins in most cases, but I'd have to do that again for the same part if it ever came up again, since I am not going to remember it. But if the logic to find this part were build into the A.I., I could just run the part past a webcam (in theory) and have it identified.

Mechanically I wouldn't know where to start, which is one of the benefits of this A.I. in that you already own the machinery and the logic is mostly done for you, providing a head start. Upon further reading, Tensorflow is even available for Android/iOS devices!

This is just something I'm curious about, and although I don't know if I can do it, I know it can be done and that gives me hope to learn; and finally, more importantly, if I succeed then I can share it. I can't do that with a self-built machine.

Thanks for the advice though!

Share this post


Link to post
Share on other sites
20 hours ago, leafan said:

Well I've been doing it conventionally for some time and it's very time consuming and repetitive.

For example, I could find a rare part in around 15mins in most cases, but I'd have to do that again for the same part if it ever came up again, since I am not going to remember it. But if the logic to find this part were build into the A.I., I could just run the part past a webcam (in theory) and have it identified

2

Why can you not remember how you found it, even if you cannot remember what the part is? I used to find it could take a long time to find parts at bricklink, but as I did it more and more my LI (LEGO Intelligence, or maybe BLI BrickLink Intelligence) grew. That is, I learned what features of what I am looking for makes a good search term.

Share this post


Link to post
Share on other sites
1 hour ago, MAB said:

Why can you not remember how you found it, even if you cannot remember what the part is? I used to find it could take a long time to find parts at bricklink, but as I did it more and more my LI (LEGO Intelligence, or maybe BLI BrickLink Intelligence) grew. That is, I learned what features of what I am looking for makes a good search term.

Well if my specific case, I would be buying new mixed lots and sorting those, so rarely have the same bricks to sort. I know the basics like 2x2 Plate or 1x2 Tile, but when it comes to the truck tipping part I posted a few days back, it's totally new to me and I didn't have a good phrase to start a search, but even if I had a good phrase in my head it would have taken a long time.

The ideal aim would be to teach an A.I. to recognise parts (I'd have to do the dirty work of teaching it), then see if it's possible to share that logic with people, or at the very least make it faster in future for myself.

Once something like this is done, it's not out of bounds to imagine using a system to calculate the percentage chance of possible sets, based upon elements present, which would be useful.

Edited by leafan

Share this post


Link to post
Share on other sites

Sorting LEGO mechanically would entail a bunch of simple cascading rake and slide constructs plus possibly some pneumatics. From a mechanical engineering standpoint pretty simple. Any LEGO element has intrinsic properties that would allow such a "filter" and you should get about 70% clean sorting in a single pass of this. The only concern is space, obviously, as it would have to be rather tall/ long to accommodate all mechanical components. Sorting by color should not be that difficult, either. After all, you just need to look e.g. at wwaste disposal sorting units and their insane speeds. Both methods combined could give you a pretty solid sorting machine without ever having to actualyl recognize the shapes and using AI.

Mylenium

Share this post


Link to post
Share on other sites

I can't speak to Google's APIs as I've been out of that game for a bit now (used to be a professor and had a number of grad students doing ML/AI work back before it was really commercialized) but I would think the first thing you'd want to do is to break up the problem into more manageable problem spaces.

The first, most obvious cut is to separate the question of piece recognition from the question of set-of-origin.  Then, even within piece recognition you'd most likely want to start with some sort of "blind"/mechanical subdivision.  For example there are a lot of examples on the web of Technic and Mindstorms sorters that divide a large mass of Lego by overall size (e.g. Bricks go in one bucket, plates and tiles go in the other).  Such machines can be feed even more specialized machines (e.g. distinguish plates from tiles, or classify a bin of Technic axles by length)  

Mechanical sorting gets tougher was the parts become more similar (consider all the ways a 1x1 brick can be modified; headlamp, clip, technic hole, stud on one side, studs on two adjacent sides, studs on two opposite sides, studs on all four sides, etc.).  This is where an AI (or a suite of AIs) can come in handy and presorting the pieces can make that AI easier to train and debug.  I used to work with both Neural Nets, Simulated Annealing Optimization and Genetic Algorithms and in all cases it was easier to create multiple AIs that did highly specialized tasks than to try and make one master AI that could do everything.  In a probabilistic world of fuzzy logic you want to be able to focus on the important details that difference one piece from another and starting will a common "family" of parts where the similarities can be taken for granted allows you to do that more easily.

Once you've recognized all the parts (which, to the moment, we'll assume your smart sorting system has done flawlessly)  the second problem actually gets a lot easier, guessing the most likely set a group of parts came from can be done with bit indices.  Imagine a giant checklist of all the parts ever made by lego where each unique shape color and ornamentation/printing gets it's own checkbox (yes this is a very long list of checkboxes but memory is cheap these days).  Now imagine a copy of this checklist to profile the set inventories of every kit in the Brickset database (we won't worry about quantity at this point).  If a set contains a given part in a given color with a given printing set the corresponding bit to 1, if it doesn't, set it to 0.  You now have a database of every set inventory expressed as a very long (and sparse, far more zeroes than ones, so in an actual system we could probably compress the hell out of it) binary number.  Create the same sort of binary "mask" for your pile of random Lego.  

Boolean logic defines an AND operation to be a lot like a decimal multiply 1*1 = 1, 1*0 = 0,  0*0 = 0.  By doing a bitwise AND between any given kit profile mask and the mask for the pile o' brick and then counting the number of 1's in the result compared to the original profile, you can get a sense as to the likelihood the parts in the pile came from a given kit.  While this is tedious, an AI could use this basic comparison to focus on likely candidates for sets of origin.  A more advanced  AI might examine combinations of masks (Boolean OR operations) to try and get complete "coverage" for all the types of bricks found (e.g. if we started with sets X, Y, and Z then we'd have at least one of every unique part in this cache...)

The final piece of our lovely imaginary system is a robot that, given a wall-full of sorted parts and a target inventory, will collate all the constituent parts back into a kit inventory.  In theory this is simple, in practice it might be easier to train a magpie to do it for you. ;->

I know I haven't really looked at how one would code any of this using Google's AI (or anyone else's for that matter) but hopefully this gives you a better sense as to how some the the magic might happen under the covers regardless of the particular engine employed.

Share this post


Link to post
Share on other sites

This is a topic I have watched interestingly in the past. There have been multiple lego brick sorting machines that I've seen online - https://www.google.co.nz/search?rlz=1C5CHFA_enNZ791NZ791&ei=DYrSW8WOMJD2rQHzubqICA&q=lego+sorting+machine&oq=lego+sorting+machine&gs_l=psy-ab.3..0i67k1j0i7i30k1l4j0l3j0i30k1l2.9354.9354.0.9728.1.1.0.0.0.0.174.174.0j1.1.0....0...1c.1.64.psy-ab..0.1.174....0.wg2dVj4tRms

For me the issue is space and learning the AI interaction language. However you effectively just run the bricks through and it learns from both what it gets right and what it doesn't - therefore you don't need to spend aeons teaching the machine every brick from every angle in every colour.

It would be a really fun project to do - although I think it would be more at LUG level where you have a few people with overlapping skillsets to contribute knowledge for building rather than on an individual level.

Share this post


Link to post
Share on other sites

It does have a certain coolness factor for sure and I would love to see someone develop an A.I. sorting process. Also I get how monotonous sorting can be and overwhelming if you slack off for a while. Although I don't buy huge bulk lots, if I did and I really didn't want to be bothered with sorting, I would farm it out to some local kids and pay them in LEGO. 

Share this post


Link to post
Share on other sites

Rebrickable might be the best resource for the second half of the problem, as it is designed to take a group of parts and determine what sets can be built from them, returning a percentage. You can set the "sensitivity" of the color matching. It has an API.

Share this post


Link to post
Share on other sites

Hi there, I know this is an outdated topic slightly but I am looking into making a lego sorting system that is not just affordable but also works. I am looking into way that it can be run through different covnets, I am just wondering with you guys doing a bit of digging in this matter already. Did you ever find any data sets or anywhere that I can grab a handful of images from that are just lego and not other brand bricks?

I am working on a dissertation for my university assignment. So far I have worked through a could of sorting algorithms but the data sets seem, to be really low. i dont have the time to take all the photos that I need so im relying on you guys!! 

If not I will have to do it all myself which im not too bothered about but will just take some time to do it. 

If you are wondering on different ways to learn the data sets there is some google software called google colab that is free to use and it saves on the price on buying your own decent GPU. You get a specific time  a day but it resets daily so its not too bad.

 

If anyone has any more information on how this maybe possible please feel free to get in touch with me and hopefully I can crate something that can be open source and cheap enough for everyone to use! 

Share this post


Link to post
Share on other sites
On March 6, 2019 at 7:31 PM, FubarCally said:

(snip...) Did you ever find any data sets or anywhere that I can grab a handful of images from that are just lego and not other brand bricks?

A while back I played with using the LDraw Parts library from MLCad to get wireframe models of various pieces.  I rendered the wireframes as black and white line drawings in various orientations and applied a 2D fast fourier transform (FFT) to the images to convert them from a spatial domain to a temporal one.  The resulting image just looks like noise to a human but is more tolerant of orientation and scale variations for computer comparisons. This became my reference catalog/training set.

For my test piece, I took a picture, desaturated it (gets rid of color), and ran an edge detection filter (only wanted to compare hard edges).  The FFT of this image became my test candidate.

I then convolved the test FFT with the FFTs of the images in my catalog, looking for the strongest overlap. 

The results were better than I was expecting, but nothing to write home about.  It sorted pieces about as accurately as my cat, but not as fast.

What I did wrong but never had time to correct and try again:

1) I was comparing complete wireframes to detected edges, I should have removed edges that were facing away from the eye and modeled each peice from more angles.  By including the "hidden" edges I thought I was creating more versatile reference images; In practice, I was just introducing unmatchable noise into my FFT reference catalog.

2) I should have created some sort of catalog index (like number of studs, visible edges and/or vertices) to act as quick elimination tests to avoid wasting time on expensive comparisons that are doomed to fail.  My test system tried to compare the test image to everything in the catalog and that took way too long to be practical.

3) I should have varied lighting conditions when taking the initial photos of my test piece, sometimes glare on a curved surface was being misidentified as an edge, making the piece harder to match.  I suspect that if I'd taken several shots from the same eye location but varying the light source location, I could have imposed a quick "majority rules" heuristic in my edge detection algorithm to distinguish hard edges from glare on shiny curved plastic.

4) I wasn't using a Neural Net or other generic ML algorithm library, I was hand coding everything and just looking for the best signal to noise ratio as my indicator of a match probability.  This gave me a lot of control over how to tune the heuristics, but also rapidly ballooned into tens of thousands of lines of C++ that became increasing harder to maintain and update, I eventually abandoned it altogether.

I don't know if any of this gives you any ideas, but best of luck in any case.

Share this post


Link to post
Share on other sites

Looks like somebody has done this with the Piqabrick kickstarter.

It'll be a pain to go through a large collection 1 by 1, but having this facility could be great for identifying rare parts or for Bricklink sellers.

I'd be interested to see if it can accurately identify colours and whether or not the bricks you scan can be added to any existing databases easily, such as a Bricklink store or Brickset etc.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.