Introduction to Image Processing - Solving the Rubik’s Cube from pictures

This presentation is an introduction to some of the computation and image processing capabilities of Mathematica. I show how one can  take a couple of pictures of a Rubik’s cube and have Mathematica generate a high resolution animation showing a minimal set of moves to bring the cube back to its initial orientation. Image processing is used as a fast input method for capturing the cube’s position. The solver is using the well known two phase solver. The movie is then made by using Export.

Luc Barthelet

Special thanks to Herbert Kociemba for the two phase algorithm

<<ComputationalGeometry`

Quick Overview

Input 2 pictures (taken by phone)

Image processing using Mathematica on the pictures:

Rotate to canonical representation prefered by solver

Solve using TwoPhase solver written in Mathematica

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}}}

Output Movie

Button[Image[ ,ImageSize->800],SystemOpen[FileNameJoin[{ParentDirectory[ParentDirectory[ParentDirectory[NotebookDirectory[]]]],"Rubik Image Processing","Test_Image_Pairs","2011","12","0001","solvedCube.mov"}]]]

Typical Development Environment

built using Mathematica and its Workbench,  constant interaction between a notebook and workbench

Button[Image[,ImageSize->1225],SystemOpen["/Applications/Wolfram Workbench.app"]]

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

Partition[Partition[inputImages,2],4]

Image Processing - Finding the cube - Experiments

Sample images

Simple processes:

Color Reduction

Erosion

Edge Detection

ImageLines

Actual Implementation - Space

testImage=;

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

Some key kernels

kernelsForCenter={,,,};

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"]];

getMatchLocations[greyImage,]

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

For example:

(Row)}

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

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

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]];

img=;
temp = DeleteSmallComponents[Binarize[ImageAdjust[ImageAdd[GradientFilter[makeGrey256[img],1],GradientFilter[img,1]]]],100]

Manipulate[
Show[temp,Graphics[{Thick, Yellow,Line[ImageLines[temp,t,d]]}]],
{{t,.3},0,1},
{{d,0.0342},0,.1}]

Apply texture mapping again...

Apply magical color reduction...

Image Processing - Color

Typical Problem in color space:

Color space visualizations

in RGB

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

{"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 *)
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 *)
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

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

Opacity[.8],White,
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.

The movie is build using the Export function

The end...