Computer Vision Rubik's Cube Solver

• 

  Example of an input image for our program

• 

  Input image, but blurred

• 

  Hough line detection on filtered image

• 

  Identified set of 3 corners of face

• 

  Cube face, after an affine transform to remove all non-face content

• 

  Visualization of colors sampled from affine transformation output

• 

  Program output!

Rubik's Cube Solver

There are two distinct components to our Rubik's Cube Solver: the input code that transforms a set of images into a cube data structure, and the solving algorithm that takes that input and produces the optimal solution. This solution is then given as instructions to the user so that they can solve their IRL cube.

Computer Vision Cube Input

The images shown above illustrate some parts of the process used to find the necessary cube colors. First, code is used to filter out noise and find linear edges, and almost all of this step is done with openCV functions, Canny edge detection and randomized Hough transform in particular. The next step, using the longest found line segments to determine corner points on the cube, was implemented manually in C++. Here we found the slope of all mostly horizontal (larger change in x coordinates than in y) lines, and used that value to determine the points furthest left, top, right, and bottom based on the cube's axes, not on the axes of the image. Later, we implemented another portion of that code to remove outliers from the found lines to improve overall robustness of the algorithm. Once we had located the corners of the face, the final step was to take an affine transform and sample at the expected centers of each of the nine square to get color values.

Optimal Solution Output

There no similar available visuals for the side of the code that computes the actual solution, but it is of equal if not greater in complexity. The approach is based on a 1997 paper [1] by Dr. Korf of U.C.L.A. The solution given there is a enhancement of iteratively-deepening A* (IDA*) search with the usage of some precomputed lookup tables. In our case, the lookup tables gave the number of moves required to solve the corners (position and orientation) of the cube. This is equivalent to story all possible solutions for any state of a 2x2x2 cube. That allows us to form a better estimate on the total number of moves required from any given position in our 3x3x3 cube.

[1] Korf, Richard E. Finding Optimal Solutions to Rubik's Cube Using Pattern Databases, 1997

Built With

• c++
• opencv