Reconstruct 3D from 6 2D faces

[badmephisto]

Hey everyone,

I was just wondering:
Given colors on 6 faces, where the faces are in any rotation, is it possible to reconstruct the full 3D shape of the cube that is consistent?

Obviously there are constraints on arrangements, but there are 4^6 = 4096 possibilities for the orientations... Must there be only one that is correct? Can there be more? Are there always more?

I'm wondering because for my vision project I am extracting colors of the cube from webcam video, but I only know the faces... Now i Need to put it together, but I'm a little unsure how to do that at the moment

 

[blah]

There can be more. Trivial case.

 

[badmephisto]

Naturally, but in the trivial case the solutions are all degenerate, so it doesn't matter that they are technically distinct.

A presence of two distinct plausible solutions would be trouble

 

[qqwref]

Flip the top 4 edges, now you don't know if it's solved permutation or H permutation.

Hopefully you can find images that show (parts of) two faces at once, or find a clear relationship between the images of each face... otherwise some of the time you're just screwed.

 

[cuBerBruce]

Or consider (UF,UR,UB) and (DF,DR,DB).

 

[blah]

Naturally, but in the trivial case the solutions are all degenerate, so it doesn't matter that they are technically distinct.

A presence of two distinct plausible solutions would be trouble

M2 E2 S2.

 

[badmephisto]

Thanks. I don't think its too much trouble to require the user to tap space and do it in a pre-defined sequence rotate, rotate, rotate, flip, rotate180. It actually improves the results by a lot at a minimal cost to the user

Btw I posted results in video section if anyone is interested
http://www.speedsolving.com/forum/showthread.php?t=20933

 

[Herbert Kociemba]

Really impressing. Your color recognition is orders better than the poor webcam interface in cube explorer. It would be great if it is possible to improve this interface. I would appreciate if you have some references to the algorithms used.

 

[badmephisto]

Hi Herbert,

The approach is fairly straight forward, and I rely a lot on functionality of the OpenCV library that implements a lot of algorithms for vision.

The basic idea is to slide a Laplacian filter through the image to get edges, and then use their probabilistic Hough Transform to finds edge segments in that. This returns a lot of edge segments that go along the cube's grid.

Then I do a pass through all pairs of edge segments and look for non-even-close-to-parallel edge segments of approximately equal length that either share an end point (corner!), or they intersect each other at 1/3 or 2/3. In either instance you can use the two lines to solve for full grid using some simple vector math.

Given a grid hypothesis it is very easy to check its likelihood by iterating over all edge segments and checking how many align with the grid.

Look here for my report, and also the code (it is not pretty)
http://www.cs.ubc.ca/~andrejk/525project/

 

[Herbert Kociemba]

Thanks for the hint to the opencv library. I played around with it a bit in Visual Studio and a short c program and it is really incredible easy to get input from a webcam etc. compared to the effort to program the direct show interface directly what I did in Cube Explorer.
The only problem is that Cube Explorer is written in Delphi and interfacing with the openvc dll's is not very elegant. And it would blow up the code for the distribution file of Cube Explorer because all those openvc dll's will have to be supplied too.

 

[badmephisto]

Thanks for the hint to the opencv library. I played around with it a bit in Visual Studio and a short c program and it is really incredible easy to get input from a webcam etc. compared to the effort to program the direct show interface directly what I did in Cube Explorer.
The only problem is that Cube Explorer is written in Delphi and interfacing with the openvc dll's is not very elegant. And it would blow up the code for the distribution file of Cube Explorer because all those openvc dll's will have to be supplied too.

alternative, so that you don't have to rewrite everything, would be to execute my script from cube explorer, have it read it all in, save it in file, and read the file right away... or something like that. But that requires people to have Python & opencv. Or then maybe it could be compiled into .exe using py2exe, but then people must have windows, and it will blow up the application too.

Yet another better alternative is to forget OpenCV altogether-- implement Hough Transform yourself. It is very short, you need one big array and a single for loop through all pixels. Sliding a Laplacian of Gaussian filter through the image to detect edges is also basically just a single loop through all pixels. And OpenCV is open source so you can maybe just "copy paste" the code.

But anyway, I really don't know just how robust the approach is to different cameras and frame rates, etc... I had a pretty good fast camera and a very new laptop, so it works very well for me, but I have no idea how it scales to other people's setups in practice.