Like many, I have been fascinated by the Rubik’s cube since its introduction in 1979.

In 2011, I decided to leverage some of the image processing capabilities in Mathematica to solve the cube from 2 pictures. Here is what this will cover. (I gave this talk at the conference in October)

First let me summarize the key steps:

**Quick Overview**

## Input 2 pictures (taken by phone)

## Then we do some image processing with Mathematica:

## Then we rotate the cube to a canonical representation preferred by the solver

Then solve using a TwoPhase solver written in Mathematica (Special thanks to Herbert Kociemba for the two phase algorithm…)

< wlcode >solveCube c={{{7,2,1,6,8,3,4,5},{1,2,1,0,0,1,2,2}},{{2,10,4,6,7,11,8,12,9,5,3,1},{0,0,0,0,1,0,0,0,0,1,0,0}}}

## Then, output a movie using Mathematica

## Let’s talk a bit about the process to get this to work:

The image processing solution is an optimization => collection of pictures to get a good sample

I got as many pictures as possible of cubes…

# Then I started experiments in image processing:

A sample image:

Color reduction:

Erosion:

Edge Detection:

Image Lines:

# Actual Implementation:

< wlcode >makeGrey256[img_] := Module[{step1},

step1 = ImageApply[Max[#] &, ImageResize[ImageAdjust[img, {.25, 0}], 256]];

ImageFilter[Min, ImageAdjust[step1,

Quantile[Flatten[ImageData[step1]], {0.05, .95}], {0, 1}], 2]];

greyImage = makeGrey256[testImage]

## ImageCorrelate, MorphologicalComponents, ComponentMeasurements

< wlcode >ImageApply[{1, 0, 1} &, ImageResize[testImage, 256],

Masking ->Dilation[ImageApply[1 – # &,

Binarize[ImageAdjust[ImageCorrelate[ greyImage, #,

NormalizedSquaredEuclideanDistance]], .05]], 5]

] & /@ kernelsForCenter

getMatchLocations[img_, kernel_] := Module[{matchPointImage, components, level = 0.022},(*0.022*)

matchPointImage = ColorNegate[ Binarize[ ImageAdjust[

ImageCorrelate[img, kernel, NormalizedSquaredEuclideanDistance]], level]];

components = MorphologicalComponents[matchPointImage];

Round[Last[#]] & /@ ComponentMeasurements[components, “Centroid”]];

## Add some graphs: DelaunayTriangulation, then select and orient the edges.

For example:

## Solve the projection Matrix (using Solve to find rotations and FindMinimum to find the Cube distance and Focal Length)

## Use simple texture mapping to extract and renormalize the side views

< wlcode >Graphics[{Texture[img],Polygon[Map[Reverse,Flatten[Table[{{x, y}, {x, y + 1}, {x + 1, y + 1}, {x + 1, y}}, {x, 0,2}, {y, 0, 2}], 1], {2}],VertexTextureCoordinates -> Map[(origin + pjct[mat . #])/resizedDimentions &,

Flatten[Table[{{x, y, 0, 1}, {x, y + 1, 0, 1}, {x + 1, y + 1, 0,

1}, {x + 1, y, 0, 1}}, {x, 0, 2}, {y, 0, 2}], 1], {2}]]},

PlotRangePadding -> None, ImagePadding -> None, AspectRatio -> 1,

ImageSize -> {256, 256}]

## Use GradientFilter and ImageLines to optimize the side views

< wlcode >makeGrey256[img_] :=Module[{step1},step1 = ImageApply[Max[#] &, ImageResize[ImageAdjust[img, {.25, 0}], 256]];

ImageFilter[Min,ImageAdjust[step1, Quantile[Flatten[ImageData[step1]], {0.05, .95}], {0, 1}], 2]];

< wlcode >temp = DeleteSmallComponents[

Binarize[ImageAdjust[ImageAdd[GradientFilter[makeGrey256[img], 1],

GradientFilter[img, 1]]]], 100]

Get the ImageLines:

## Apply texture mapping again

## Apply magical color reduction…

# Image Processing – Color

## Typical Problem in color space:

Because of lighting, color identification is quite a difficult problem:

Here are some examples:

Color space visualization:

In HSB:

### Solution is to extract all 6 faces, and then adjust the color matching

# The two phase algorithm (written by Herbert Kociemba)

all details are at http://kociemba.org/cube.htm

Group of cubic moves is divided by G1 generated by U,D,R2,L2,F2,B2

Requires the Cube to be rotated in special position (Cube permutations to rotate in position)

Solver returns a series of moves

< wlcode >{“U1 “, “U2 “, “U3 “, “R1 “, “R2 “, “R3 “, “F1 “, “F2 “, “F3 “, “D1 \

“, “D2 “, “D3 “, “L1 “, “L2 “, “L3 “, “B1 “, “B2 “, “B3 “}

# Build Movie from the solution

## Cube rendering and animation

rendered as a series of move then transform…

### The cube itself

mini cubes are ContourPlot3D

Label on faces are a single polygon

Cube itself is rendered by GeometricTransformation and Rotations

Example: a rotation of the front face

Table[GeometricTransformation[{

(* the labels on the cube *)

< wlcode >Table[{If[x == -1, {ColorList[[3*z – y + 41]], GeometricTransformation[$aFace, {RotationMatrix[ Pi/2, {0, 1, 0}], {-1.5, y, z}}]}, {}], If[x == 1, {ColorList[[3*z + y + 14]],

GeometricTransformation[$aFace, {RotationMatrix[Pi/2, {0, 1, 0}], {1.5,y, z}}]}, {}],

If[y == -1, {ColorList[[3*z + x + 32]], GeometricTransformation[$aFace, {RotationMatrix[ Pi/2, {1, 0, 0}], {x, -1.5, z}}]}, {}], If[y == 1, {ColorList[[3*z – x + 23]],

GeometricTransformation[$aFace, {RotationMatrix[Pi/2, {1, 0, 0}], {x,1.5, z}}]}, {}],

If[z == -1, {ColorList[[-3*y + x + 50]], GeometricTransformation[$aFace, {IdentityMatrix[3], {x, y, -1.5}}]}, {}], If[z == 1, {ColorList[[3*y + x + 5]],

GeometricTransformation[$aFace, {IdentityMatrix[3], {x, y,1.5}}]}, {}]}, {y, -1, 1}, {z, -1, 1}],

(* the mini cubes themselves *)

< wlcode >GeometricTransformation[{cube3DObject[[1]]},

Flatten[Table[{IdentityMatrix[3], {x, y, z}}, {y, -1, 1}, {z, -1, 1}],

1]]}, {{IdentityMatrix[3]}, {IdentityMatrix[

3]}, {RotationMatrix[-angle, {1, 0, 0}]}}[[{x + 2}]]]

, {x, -1, 1}],

### The Scene

The scene itself is a series of GeometricTransformation

< wlcode >GeometricTransformation[

…

{{IdentityMatrix[3], {0, 0, 0}},

{ReflectionMatrix[{1, 0, 0}], {-7, 0, 0}},

{ReflectionMatrix[{0, 1, 0}], {0, 7, 0}},

{ReflectionMatrix[{0, 0, 1}], {0, 0, -7}}

}

]

The reflections are seen through low transparency polygons, which give the illusion of reflection

Polygon[{center, center + {maxAxes, 0, 0}, center + {maxAxes, 0, maxAxes},

center + {0, 0, maxAxes}}], Polygon[{center, center + {maxAxes, 0, 0},

center + {maxAxes, -maxAxes, 0},

center + {0, -maxAxes, 0}}], Polygon[{center, center + {0, -maxAxes, 0},

center + {0, -maxAxes, maxAxes}, center + {0, 0, maxAxes}}],

The moves as Text are added as an Epilog.