役立つ情報 | 115 行のコードで数独パーサーを作成する方法を段階的に説明します。

あなたも数独愛好家ですか?

Aakash Jhawar さんは、多くの人と同じように、新しい困難な課題に取り組むことを楽しんでいます。彼は学生時代、毎朝数独をやっていました。私たちが成長し、テクノロジーが進歩すれば、コンピューターを使って数独を解くことができるようになります。数独の画像をクリックするだけで、9 つのマス目がすべて埋められます。

ディン～ここに数独分析チュートリアルがありますので、チェックしてください～ハードコアな乾物を集めるのが好きな友達は、ぜひ見てください～

数独は 9×9 のグリッドで構成され、各行、列、宮殿には 1 から 9 までの数字を入力する必要があり、各行、列、宮殿の数字は重複してはならないことは誰もが知っています。

数独を解くプロセス全体は、3 つのステップに分けられます。

ステップ1: 画像から数独を抽出する

ステップ2: 画像に表示される各数字を抽出する

ステップ3: アルゴリズムを使用して数独の解を計算する

ステップ1: 画像から数独を抽出する

まず、画像処理が必要です。

1. 画像を前処理する

まず、カーネル サイズ (高さ、幅) が 9 の画像にガウス ブラーを適用します。カーネル サイズは正の奇数でなければならず、カーネルは正方形でなければならないことに注意してください。次に、最も近い 11 個のピクセルを使用して適応しきい値が適用されます。

 proc = cv2.GaussianBlur (img.copy(), (9, 9), 0)  
 proc = cv2.adaptiveThreshold (proc, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY, 11, 2)

グリッド線のピクセル値がゼロにならないようにするには、色を反転します。また、画像を拡大すると、グリッド線のサイズが大きくなります。

 proc = cv2.bitwise_not (proc, proc)  
カーネル= np.array ([[0., 1., 0.], [1., 1., 1.], [0., 1., 0.]], np.uint8)  
 proc = cv2.dilate (proc、カーネル)

閾値処理後の数独画像

2. 最大の多角形の角度を求める

次のステップは、画像内の最大の輪郭の 4 つの角を見つけることです。したがって、すべての等高線を見つけて、面積の降順で並べ替え、面積が最大のものを選択する必要があります。

 _、輪郭、 h = cv2.findContours (img.copy()、cv2.RETR_EXTERNAL、cv2.CHAIN_APPROX_SIMPLE)  
輪郭=ソート済み(輪郭、キー= cv2.contourArea 、逆順= True )  
ポリゴン=輪郭[0]

使用する演算子。 max と min を持つ itemgetter を使用すると、そのポイントのインデックスを取得できます。各ポイントは 1 つの座標を持つ配列であり、[0] と [1] はそれぞれ x と y を取得するために使用されます。

右下隅には最大 (x + y) 値があり、左上隅には最小 (x + y) 値があり、左下隅には最小 (x - y) 値があり、右上隅には最大 (x - y) 値があります。

 bottom_right、 _ = max (enumerate([pt[0][0] + pt[0][1] ptの場合 
                      ポリゴン])、キー= operator.itemgetter (1))  
 top_left、 _ = min (enumerate([pt[0][0] + pt[0][1] ptの場合 
                  ポリゴン])、キー= operator.itemgetter (1))  
 bottom_left、 _ = min (enumerate([pt[0][0] - pt[0][1] ptの場合 
                     ポリゴン])、キー= operator.itemgetter (1))  
 top_right、 _ = max (enumerate([pt[0][0] - pt[0][1] ptの場合 
                   ポリゴン])、キー= operator.itemgetter (1))

4 つのポイントの座標がわかったので、インデックスを使用して 4 つのポイントの配列を返す必要があります。各ポイントは独自の座標配列内にあります。

 [ポリゴン[左上][0]、ポリゴン[右上][0]、ポリゴン[右下][0]、ポリゴン[左下][0]]

最大の多角形の4つの角

3. 画像の切り抜きと変形

数独パズルの 4 つの座標がわかったので、1 つの画像から長方形の部分を切り取って、同様のサイズの正方形に曲げる必要があります。左上、右上、右下、左下の点によって表される長方形。

注意: データ型を明示的に float32 または 'getPerspectiveTransform' に設定すると、エラーが発生します。

左上、右上、右下、左下=クロップ矩形[0]、クロップ矩形 [1]、クロップ矩形 [2]、クロップ矩形 [3]  
 src = np .array([左上、右上、右下、左下]、 dtype = float32 )  
サイド=最大([ 距離_between(bottom_right, top_right),  
            距離(左上、左下)、  
            距離(右下、左下)、  
            distance_between(top_left, top_right) ])

正方形をその辺の長さで表現することは、新たな視点です。次に行う必要があるのは、前後の 4 つのポイントを比較して、画像を傾斜させるための変換行列を取得することです。最後に、元の画像が変換されます。

 dst = np .array([[0, 0], [side - 1, 0], [side - 1, side - 1], [0, side - 1]], dtype = float32 )  
 m = cv2.getPerspectiveTransform (ソース、dst)  
 cv2.warpPerspective(画像, m, (int(サイド), int(サイド)))

切り取られて変形された数独画像

4. 正方形の画像からグリッドを推測する

正方形の画像から 81 個のセルが推測されました。ここで j と i を入れ替えて、四角形が上から下ではなく左から右に読み取られるリストに格納されるようにします。

正方形= []  
サイド= img .shape[:1]  
サイドサイド= サイド[0] / 9
 jが範囲内(9)の場合:  
    iが範囲内(9)の場合:  
 p1 = (i * 辺、j * 辺) #ボックスの左上隅 
 p2 = ((i + 1) * 辺、(j + 1) * 辺) #右下隅
         squares.append((p1, p2))は正方形を返す

5. すべての数字を取得する

次のステップは、セルから数字を抽出し、配列を構築することです。

数字= []  
 img = pre_process_image (img.copy(), skip_dilate = True )  
正方形の正方形の場合:  
    digits.append(extract_digit(画像、正方形、サイズ))

extract_digit は、数独のマス目から数字（ある場合）を抽出する関数です。ボックス全体から数字ボックスを取得し、塗りつぶし特徴検索を使用してボックスの中央の最大の特徴を取得し、数字に属するエッジのピクセルを見つけて中央の領域を定義します。次に、数値をスケーリングしてパディングし、機械学習での使用に適した平方にする必要があります。同時に、小さな境界は無視する必要があります。

 def extract_digit(画像、矩形、サイズ):  
数字= cut_from_rect (画像、rect)  
    h, w =数字の形状[:2]  
マージン= int (np.mean([h, w]) / 2.5)  
    _, bbox, seed = find_largest_feature (digit, [margin, margin], [w  
    - マージン、h - マージン])  
数字= cut_from_rect (数字、ボックス)  
 w = bbox [1][0] - bbox[0][0]  
 h = bbox [1][1] - bbox[0][1]  
    w > 0 かつ h > 0 かつ (w * h) > 100 かつ len(digit) > 0 の場合:  
        scale_and_centre(数字、サイズ、4) を返します 
    それ以外：  
        np.zeros((size, size), np.uint8) を返します

最後の数独の画像

これで、最終的な前処理済みの数独画像ができました。次のタスクは、画像内の各数字を抽出してマトリックスに保存し、何らかのアルゴリズムを使用して数独の解を計算することです。

ステップ2: 画像に表示される各数字を抽出する

数字認識では、0 から 9 までの数字の画像 60,000 枚を含む MNIST データセットでニューラル ネットワークをトレーニングします。まず、すべてのライブラリをインポートします。

 numpyをインポートする 
 keras.datasetsからcv2をインポートする 
 keras.modelsからmnistをインポートする 
 keras.layersからSequentialをインポートする 
 keras.layersからDenseをインポートする 
 keras.layersからDropoutをインポートする 
 keras.layers.convolutional から Flatten をインポートします 
 keras.layers.convolutional から Conv2D をインポートします 
 keras.utilsからMaxPooling2Dをインポートします 
 kerasからnp_utilsをインポートする 
バックエンドをKとしてインポートする 
 matplotlib.pyplot を plt としてインポートします。

再現性を確保するには、ランダム シードを固定する必要があります。

 K.set_image_dim_ordering( 番目 )  
シード= 7numpy.random.seed (シード)  
 (X_train, y_train)、(X_test, y_test) = mnist.load_data()

次に、画像はサンプル*ピクセル*幅*高さに再形成され、入力は 0 ～ 255 から 0 ～ 1 に正規化されます。この後、出力はワンホットエンコードされます。

 X_train X_train = X_train.reshape(X_train.shape[0], 1, 28,  
                           28).astype( float32 )  
 X_test X_test = X_test.reshape(X_test.shape[0], 1, 28,  
                           28).astype( float32 )  
 X_train X_train = X_train / 255  
 X_テストX_テスト= X_テスト / 255
 y_train = np_utils.to_categorical (y_train)  
 y_test = np_utils.to_categorical (y_test)  
 num_classes = y_test.shape [1]

次に、手書きの数字を予測するモデルを作成します。

モデル=シーケンシャル()  
モデルを追加します(Conv2D(32, (5, 5), input_shape =(1, 28, 28),  
アクティベーション= relu ))  
 model.add(MaxPooling2D( pool_size =(2, 2)))model.add(Conv2D(16, (3,  
          3)、活性化= relu ))  
モデルを追加します(MaxPooling2D(プールサイズ=(2, 2)))
モデルを追加します(ドロップアウト(0.2))  
モデルを追加します(フラット化())  
 model.add(Dense(128, activation = relu ))  
 model.add(Dense(64, activation = relu ))  
 model.add(Dense(num_classes, activation = softmax ))

モデルの概要

モデルを作成したら、それをコンパイルし、データセットに適合させて評価する必要があります。

 model.compile(損失= categorical_crossentropy 、オプティマイザー= adam 、  
メトリクス=[精度])  
モデル.fit(X_train, y_train,検証データ=(X_test, y_test),  
エポック= 10 、バッチサイズ= 200 )  
スコア=モデル.evaluate(X_test, y_test, verbose = 0 )  
 print("大きなCNNエラー: %.2f%%" % (100-スコア[1]*100))

ここで、上記で作成したモデルをテストします。

テスト画像= X_テスト[1:5]  
 test_images test_images = test_images.reshape(test_images.shape[0], 28, 28)  
 print ("テスト画像の形状: {}".format(test_images.shape))  
 i、test_image を enumerate(test_images、 start = 1 ) します:  
 org_image =テストイメージ   
 test_image test_image = test_image.reshape(1,1,28,28)  
予測=モデル.predict_classes(test_image, verbose = 0 )  
    print ("予測された数字: {}".format(prediction[0]))  
    plt.サブプロット(220+i)  
    plt.axis( オフ )  
    plt.title("予測された数字: {}".format(prediction[0]))  
    plt.imshow(org_image, cmap = plt .get_cmap( グレー ))  
 plt.show()

手書き数字分類モデルから予測された数字

ニューラルネットワークの精度は 98.314% です!最後に、シーケンス モデルを保存して、使用する必要があるときに何度もトレーニングする必要がないようにしておきます。

 # モデルをJSONにシリアル化する 
モデルmodel_json = model.to_json()  
 open("model.json", "w") を json_file として実行します:  
    json_file.write(モデルjson)
 # 重みを HDF5 にシリアル化します 
モデル.save_weights("model.h5")  
 print("モデルをディスクに保存しました")

手書き数字認識に関する詳細情報:

https://github.com/aakashjhawar/手書き数字認識

次のステップは、事前トレーニング済みのモデルをロードすることです。

 json_file =開く(model.json, r)  
 loaded_model_json = json_file .read()  
 json_file.close()  
 loaded_model = model_from_json (読み込まれたモデルjson)  
 loaded_model.load_weights("model.h5")

画像のサイズを変更し、9x9 の画像に分割します。それぞれの小さな画像には 1 から 9 までの番号が付いています。

数独= cv2.resize (数独, (450,450))  
グリッド= np.zeros ([9,9])  
 iが範囲内(9)の場合:  
    jが範囲内(9)の場合:  
画像=数独[i*50:(i+1)*50,j*50:(j+1)*50]  
        image.sum() > 25000の場合:  
            grid[i][j] = 識別番号(画像)  
        それ以外：  
            グリッド[i][j] = 0  
グリッドグリッド= grid.astype(int)

identify_number 関数は、数字の画像を取得し、画像内の数字を予測します。

 def identify_number(画像):  
 image_resize = cv2.resize (image, (28,28)) # plt.imshowの場合 
 image_resize image_resize_2 = image_resize.reshape(1,1,28,28) # model.predict_classesへの入力用 
 # cv2.imshow( 数値 , image_test_1)  
 loaded_model loaded_model_pred = loaded_model.predict_classes(image_resize_2  
                                                      、詳細= 0 )  
    loaded_model_pred[0]を返す

上記の手順を完了すると、数独グリッドは次のようになります。

抽出された数独

ステップ3: バックトラッキングアルゴリズムを使用して数独の解を計算する

バックトラッキング アルゴリズムを使用して、数独の解を計算します。

グリッドでまだ割り当てられていないエントリを検索します。参照パラメータ row が見つかった場合、col は未割り当ての位置にセットされ、true が返されます。割り当てられていないエントリが残っていない場合は false を返します。 「l」は、増加する行と列を追跡するためにsolve_sudoku関数に渡されるリスト変数です。

 def find_empty_location(arr,l):  
    範囲(9)内の行の場合:  
        範囲(9)内の列の場合:  
            （arr[行][列]==0の場合）  
                l[0]=行 
                l[1]=列 
                Trueを返す 
    Falseを返す

指定された行に割り当てられた項目のいずれかが指定された番号と一致するかどうかを示すブール値を返します。

使用中の行を定義します(arr,行,数値):  
    iが範囲内(9)の場合:  
        if(arr[行][i] == num):  
            Trueを返す 
    Falseを返す

指定された列に割り当てられた項目のいずれかが指定された番号と一致するかどうかを示すブール値を返します。

使用される列を定義します(arr、列、数値):  
    iが範囲内(9)の場合:  
        if(arr[i][col] == num):  
            Trueを返す 
    Falseを返す

指定された 3x3 ボックス内の割り当てられた項目のいずれかが指定された番号と一致するかどうかを示すブール値を返します。

 def used_in_box(arr,row,col,num):  
    iが範囲(3)内にある場合:  
        jが範囲(3)内にある場合:  
            if(arr[i+行][j+列] == 数値):  
            Trueを返す
     Falseを返す

指定された (行、列) に num を割り当てることが正当かどうかを確認します。 'num' が現在の行、現在の列、現在の 3x3 ボックスにまだ配置されていないかどうかを確認します。

 def check_location_is_safe(arr,row,col,num):  
    used_in_row(arr,row,num)を返さず、  
           used_in_col(arr,col,num) ではなく、  
           not used_in_box(arr,row - row%3,col - col%3,num)

部分的に埋められたグリッドを取得し、数独の解答要件（行、列、ボックス間で重複しない）を満たすすべての未割り当ての位置に値を割り当てようとします。 「l」は、find_empty_location 関数の行レコードと列レコードを保持するリスト変数です。上記の関数から取得した行と列をリストの値に割り当てます。

数独を解く定義(arr):  
 l = [0,0]  
    find_empty_location(arr,l) が存在しない場合には:  
        Trueを返す 
行= l [0]  
列=l[1]  
    numが範囲(1,10)の場合:  
        check_location_is_safe(arr,row,col,num) の場合:  
            arr[行][列]=数値 
            (solve_sudoku(arr))の場合:  
                Trueを返す 
            # 失敗、元に戻して再試行 
            arr[行][列] = 0  
    Falseを返す

最後にグリッドを印刷します。

 def print_grid(arr):  
    iが範囲内(9)の場合:  
        jが範囲内(9)の場合:  
            印刷 (arr[i][j]) 
         印刷 ( )

最後に、すべての関数をメイン関数に統合します。

定義 sudoku_solver(グリッド):  
    （数独を解く（グリッド））の場合：  
        印刷(---)  
    それ以外：  
        print ("解決策は存在しません")  
グリッドグリッド= grid.astype(int) 
     リターングリッド

この関数の出力は、最終的に解かれた数独になります。

最終解決策

もちろん、このソリューションは決して完璧というわけではなく、解析できない画像や、誤って解析されて処理できない画像を処理するときに、依然としていくつかの問題が発生します。しかし、私たちの目標は新しい技術を探求することであり、この観点からすると、このプロジェクトは依然として価値があります。