ルービックキューブを解く（その１：画像認識して解く）

ルービックキューブの写真を撮って、色を認識して解く。
そんなことが出来ればと思い、格闘。

一面づつ写真を撮ってというやりかたは、面白くないので、3面づつまとめて。

最初はPHPでがりがり書いたが、画像認識に限界があり、C++とOpenCVの組み合わせに乗り替え。

まずは、写真の撮り方。画像処理をやりやすくするために、背景は100均で買ったフェルト生地を置いて撮影。
ルービックキューブの配置は、以下の面の位置で。
最終的には各面に番号を付け、行列（配列）に色を代入する。

左の写真 左手前の面：Front面（中央が白）→0 上の面：Up面（中央が赤）→1 右手前の面：Right面（中央が緑）→5

右の写真 左手前の面：Back面（中央が青）→2 上の面：Down（中央がオレンジ）→3 右手前の面：Left面（中央が黄）→4

写真をアップロードして、C++のプログラムで色の認識を行う。

【手順】

1. 白黒画像に変換
   void cvCvtColor(const CvArr* src, CvArr* dst, int code)
2. 確率的ハフ変換による線分の検出
   CvSeq* cvHoughLines2(CvArr* image, void* storage, int method, double rho, double theta, int threshold, double param1=0, double param2=0)
3. 3点透視図として扱い消失点を求める
4. 面に変換するためのホモグラフィ行列の推定
   void cvFindHomography(const CvMat* srcPoints, const CvMat* dstPoints, CvMat* H int method=0, double ransacReprojThreshold=3, CvMat* status=NULL)
5. ホモグラフィ変換で各面（正方形）の画像を生成
   void cvWarpPerspective(const CvArr* src, CvArr* dst, const CvMat* mapMatrix, int flags=CV_INTER_LINEAR+CV_WARP_FILL_OUTLIERS, CvScalar fillval=cvScalarAll(0))
6. 重み付け最小二乗法（Biweight推定法）で各キューブを推定
7. HSV色空間に変換し、色相（H:Hue）を昇順ソート、彩度（S:Saturation、白）は降順ソートし、それぞれの色を推定
8. 6x9の行列（面[6] × キューブ数[9]）に色を設定

という感じで処理する。

各キューブの色行列ができたところで、3点透視図で再現。

1. アフィン変換行列を算出
   CvMat* cvGetPerspectiveTransform(const CvPoint2D32f* src, const CvPoint2D32f* dst, CvMat* mapMatrix)
   
   
2. 各ポイントをアフィン変換し、画像を生成

とりあえず、画像認識で色を判別し、配列に代入。
さて、ルービックキューブを解きましょう。

まずは、回転の軸の設定

というような感じで各面を正面から見た時に、右回転を1に、左回転を-1に設定。
ルービックキューブ攻略サイトなどを参考にしながら、ステップごとにプログラミング。
メガハウスの６面完成攻略書を参考に。

【手順】

1. クロスを作って上面（Up）を揃える（最小の手数で揃えられる面を選ぶ）
2. 中段を揃える
3. 裏（Down）のクロスを作る
4. 裏（Down）を揃える
5. コーナー、サブキューブを揃える

脳ミソがよじれる感じで計算し、回転方向を図示。
以下、抜粋。

 

クロスを作る。クロスの面は裏（Back）面なのでこの図では見えません。

以下が最終局面。 

で完成。
でも、120手が必要。う〜ん。