Visual Rubiks Cube Solver

[Swoncen]

Hi!

I don't know in what forum I should post this thread, but I think hardware is just fine.


I developed a visual rubiks cube solver by taking one camera (can be ANY camera with a resoultion at least 320x240) and my knowledge of image processing and pattern recognition. The solution is yet very very very long because I implemented the basic layer by layer algorithms. Ok, I just embed a video of it.

If anyone is interested in helping me for shortening the solution, just tell me. I will work on it anyway but I have a presentation in the university in an hour and next week I have 7 examinations and in the first week of february I'm on a researchers conference, after that I will be in amsterdam for 4 month doing my master thesis and so on...... you see I have less time, so any help is appriciated.

 

[Lucas Garron]

Just implement Kociemba?

 

[GerrySly]

Cube Explorer already has this built in, but J. Brown created an OCX which implements the Kociemba algorithm to find the optimal solution at X depth, the source can be find here and the compiled OCX can be find here. Otherwise I would imagine just try to decompile Mark Reid's optimal solver written in C to your language, the source can be found here

 

[Swoncen]

I didn't know Kociemba. Thank you!

 

[AvGalen]

I didn't know Kociemba. Thank you!

People just start programming without looking at other peoples solutions, now don't they. I hope you had fun and learned a lot though.

Also, when you come studying in Amsterdam, don't forget to become a "member" of the (in)famous Dutch Cubing Community (™). Just contact any Dutch cuber if you feel like meeting someday

 

[Swoncen]

People just start programming without looking at other peoples solutions, now don't they. I hope you had fun and learned a lot though.

Usually I don't do that but I had two days without Internet a week ago and I decided to implement the algorithms. It wasn't to hard and it was not the big part of the software.

I have to say something: Such a visual system is already implemented for Cube Explorer you said but I tell you the difference:

Cube Explorer:
1. Setting up the camera (camera parameters etc.)
2. Configuration of colors (red-orange problem etc.)
3. Turn the cube so that it exactly matches with the rectangles in the display.
4. Click on which face to scan
5. Click "scan"
6. Click "Solve"
7. Do that for all faces

My solution:
1. Turn on the camera (haha )
2. Place the Cube on front of the camera
3. Do that for all faces


Done. Everything is done automatically. You can use ANY color scheme, you can place the cube wherever you want into the image, it will be recognized, you don't have to define colors and you don't have to click something. This was the main goal and not calculating the best solution. =)

It was a small project for a image processing course and they liked it.

btw.: If someone knows optimal solutions for big cubes - I can easily extend that algorithm to big cubes. I think that would be cool.

Also, when you come studying in Amsterdam, don't forget to become a "member" of the (in)famous Dutch Cubing Community (™). Just contact any Dutch cuber if you feel like meeting someday

Yes, that would be really nice! I want to decrease my times while these month in Amsterdam. =)

 

[AvGalen]

People just start programming without looking at other peoples solutions, now don't they. I hope you had fun and learned a lot though.

Usually I don't do that but I had two days without Internet a week ago and I decided to implement the algorithms. It wasn't to hard and it was not the big part of the software.

I have to say something: Such a visual system is already implemented for Cube Explorer you said but I tell you the difference:

Cube Explorer:
1. Setting up the camera (camera parameters etc.)
2. Configuration of colors (red-orange problem etc.)
3. Turn the cube so that it exactly matches with the rectangles in the display.
4. Click on which face to scan
5. Click "scan"
6. Click "Solve"
7. Do that for all faces

My solution:
1. Turn on the camera (haha )
2. Place the Cube on front of the camera
3. Do that for all faces


Done. Everything is done automatically. You can use ANY color scheme, you can place the cube wherever you want into the image, it will be recognized, you don't have to define colors and you don't have to click something. This was the main goal and not calculating the best solution. =)

It was a small project for a image processing course and they liked it.

btw.: If someone knows optimal solutions for big cubes - I can easily extend that algorithm to big cubes. I think that would be cool.

Also, when you come studying in Amsterdam, don't forget to become a "member" of the (in)famous Dutch Cubing Community (™). Just contact any Dutch cuber if you feel like meeting someday

Yes, that would be really nice! I want to decrease my times while these month in Amsterdam. =)

Both these projects use Cube Explorer at least for the calculating part, but I also think they use the image processing

Rubot II
Deep Cube Robot

No machine can calculate an optimal solution for 4x4x4 or bigger. The best that exists is a method that uses 5 suboptimal steps.

And coming to Amsterdam to "decrease your cubing times"??? That's the first time I heard that one

 

[GerrySly]

Both these projects use Cube Explorer at least for the calculating part, but I also think they use the image processing

Rubot II
Deep Cube Robot

I'm pretty sure DeepCube doesn't use Cube Explorer for the calculating part, he says in his project report, "An implementation of the Thistlethwaite algorithm was written to solve the Rubik's cube.", whilst Mark Reid's Optimal Solver and Cube Explorer both use the Kociemba algorithm.

I may be wrong as I haven't gone through his code and to be honest can't be bothered right now lol

 

[AvGalen]

Both these projects use Cube Explorer at least for the calculating part, but I also think they use the image processing

Rubot II
Deep Cube Robot

I'm pretty sure DeepCube doesn't use Cube Explorer for the calculating part, he says in his project report, "An implementation of the Thistlethwaite algorithm was written to solve the Rubik's cube.", whilst Mark Reid's Optimal Solver and Cube Explorer both use the Kociemba algorithm.

I may be wrong as I haven't gone through his code and to be honest can't be bothered right now lol

Kociemba's algorithm (2-step) is based (but extremely optimised) on the Thistlethwaite idea of reducing to subgroups with optimal tables. Thistlethwaite used more steps so the optimal tables could be found "manually". The video and report links don't seem to work anymore, but the video showed a very short solution way beyond Thistlethwaite.

 

[GerrySly]

Both these projects use Cube Explorer at least for the calculating part, but I also think they use the image processing

Rubot II
Deep Cube Robot

I'm pretty sure DeepCube doesn't use Cube Explorer for the calculating part, he says in his project report, "An implementation of the Thistlethwaite algorithm was written to solve the Rubik's cube.", whilst Mark Reid's Optimal Solver and Cube Explorer both use the Kociemba algorithm.

I may be wrong as I haven't gone through his code and to be honest can't be bothered right now lol

Kociemba's algorithm (2-step) is based (but extremely optimised) on the Thistlethwaite idea of reducing to subgroups with optimal tables. Thistlethwaite used more steps so the optimal tables could be found "manually". The video and report links don't seem to work anymore, but the video showed a very short solution way beyond Thistlethwaite.

The report link got changed but not updated on the page, it can be found http://www.deepcube.net/reports/alkjshdfuianeun.pdf <-- there

 

[Swoncen]

And coming to Amsterdam to "decrease your cubing times"??? That's the first time I heard that one

That's not the reason why I come to Amsterdam but I will definitely have more time for cubing then here. =)

 

[AvGalen]

Both these projects use Cube Explorer at least for the calculating part, but I also think they use the image processing

Rubot II
Deep Cube Robot

I'm pretty sure DeepCube doesn't use Cube Explorer for the calculating part, he says in his project report, "An implementation of the Thistlethwaite algorithm was written to solve the Rubik's cube.", whilst Mark Reid's Optimal Solver and Cube Explorer both use the Kociemba algorithm.

I may be wrong as I haven't gone through his code and to be honest can't be bothered right now lol

Kociemba's algorithm (2-step) is based (but extremely optimised) on the Thistlethwaite idea of reducing to subgroups with optimal tables. Thistlethwaite used more steps so the optimal tables could be found "manually". The video and report links don't seem to work anymore, but the video showed a very short solution way beyond Thistlethwaite.

The report link got changed but not updated on the page, it can be found http://www.deepcube.net/reports/alkjshdfuianeun.pdf <-- there

I have found several video's. He seems to have made software changes:
97 moves (40 something seconds): http://youtube.com/watch?v=ia5NAGnq_U4
12 seconds (video down?): http://youtube.com/watch?v=EjL4FgVI3Bc

 

[Herbert Kociemba]

Usually I don't do that but I had two days without Internet a week ago and I decided to implement the algorithms. It wasn't to hard and it was not the big part of the software.

I have to say something: Such a visual system is already implemented for Cube Explorer you said but I tell you the difference:

Cube Explorer:
1. Setting up the camera (camera parameters etc.)
2. Configuration of colors (red-orange problem etc.)
3. Turn the cube so that it exactly matches with the rectangles in the display.
4. Click on which face to scan
5. Click "scan"
6. Click "Solve"
7. Do that for all faces

My solution:
1. Turn on the camera (haha )
2. Place the Cube on front of the camera
3. Do that for all faces


Done. Everything is done automatically. You can use ANY color scheme, you can place the cube wherever you want into the image, it will be recognized, you don't have to define colors and you don't have to click something. This was the main goal and not calculating the best solution. =)

It was a small project for a image processing course and they liked it.

btw.: If someone knows optimal solutions for big cubes - I can easily extend that algorithm to big cubes. I think that would be cool.

Yes, that would be really nice! I want to decrease my times while these month in Amsterdam. =)

Surely the color recognition is far superior to the one implemented in Cube Explorer. This is not the main purpose of my program. Nevertheless it really would be nice to implement something similar into my program. Can you give some hints about the used algorithms for the image processing?

 

[panyan]

cant wait for this to be released, seems really cool

 

[GalPro]

wow man that's really cool, you can publish the software that connects to internet camera.

you can try different method, or the method "cube explorer" uses