Решатель судоку с использованием OpenCV и DL - Часть 2

Если вы нетерпеливы, прокрутите до конца сообщения репозиторий Github.

Это часть 2 решения Sudoku Solver. Убедитесь, что вы мельком ознакомились с Частью 1. Итак, забегая вперед, до сих пор мы предварительно обрабатывали изображение, то есть берем изображение и выполняем перспективное преобразование кадрирования и деформации. Теперь нам нужно извлечь числа и решить судоку.

B: извлеките каждое число, присутствующее на изображении

Итак, наша следующая задача - извлечь каждое число из изображения, идентифицировать число и сохранить его в 2D-матрице.

Для распознавания цифр мы будем обучать нейронную сеть на наборе данных MNIST, содержащем 60 000 изображений цифр от 0 до 9.

Начнем с импорта всех библиотек.

import numpy
import cv2from keras.datasets 
import mnistfrom keras.models 
import Sequentialfrom keras.layers 
import Densefrom keras.layers 
import Dropoutfrom keras.layers 
import Flattenfrom keras.layers.convolutional 
import Conv2Dfrom keras.layers.convolutional 
import MaxPooling2Dfrom keras.utils 
import np_utilsfrom keras 
import backend as K
import matplotlib.pyplot as plt

Мы исправим случайное начальное число для воспроизводимости.

K.set_image_dim_ordering('th')
seed = 7numpy.random.seed(seed)
(X_train, y_train), (X_test, y_test) = mnist.load_data()

Теперь давайте изменим форму изображений так, чтобы они были сэмплами * пикселями * шириной * высотой, и нормализуем входные данные от 0–255 до 0–1. После этого мы будем горячо кодировать выходные данные.

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

Далее мы создадим модель для предсказания рукописной цифры.

model = Sequential()
model.add(Conv2D(32, (5, 5), input_shape=(1, 28, 28),
          activation='relu'))
model.add(MaxPooling2D(pool_size=(2, 2)))model.add(Conv2D(16, (3,
          3), activation='relu'))
model.add(MaxPooling2D(pool_size=(2, 2)))
model.add(Dropout(0.2))
model.add(Flatten())
model.add(Dense(128, activation='relu'))
model.add(Dense(64, activation='relu'))
model.add(Dense(num_classes, activation='softmax'))

После создания модели давайте скомпилируем ее, поместим в набор данных и оценим.

model.compile(loss='categorical_crossentropy', optimizer='adam',
               metrics=['accuracy'])
model.fit(X_train, y_train, validation_data=(X_test, y_test),
               epochs=10, batch_size=200)
scores = model.evaluate(X_test, y_test, verbose=0)
print("Large CNN Error: %.2f%%" % (100-scores[1]*100))

Теперь мы протестируем созданную выше модель.

test_images = X_test[1:5]
test_images = test_images.reshape(test_images.shape[0], 28, 28)
print ("Test images shape: {}".format(test_images.shape))
for i, test_image in enumerate(test_images, start=1):
    org_image = test_image
    test_image = test_image.reshape(1,1,28,28)
    prediction = model.predict_classes(test_image, verbose=0)
    print ("Predicted digit: {}".format(prediction[0]))
    plt.subplot(220+i)
    plt.axis('off')
    plt.title("Predicted digit: {}".format(prediction[0]))
    plt.imshow(org_image, cmap=plt.get_cmap('gray'))
plt.show()

Точность нейронной сети составила 98,314%. Наконец, мы сохраним последовательную модель, чтобы нам не приходилось тренировать ее снова и снова, когда мы хотим ее использовать.

# serialize model to JSON
model_json = model.to_json()
with open("model.json", "w") as json_file:
    json_file.write(model_json)
# serialize weights to HDF5
model.save_weights("model.h5")
print("Saved model to disk")

Чтобы узнать больше о распознавании рукописных цифр https://github.com/aakashjhawar/Handwritten-Digit-Recognition

Нашим следующим шагом будет загрузка предварительно обученной модели и весов.

json_file = open('model.json', 'r')
loaded_model_json = json_file.read()
json_file.close()
loaded_model = model_from_json(loaded_model_json)
loaded_model.load_weights("model.h5")

Затем мы изменим размер изображения и разделим его на маленькие изображения 9x9. На каждом маленьком изображении будет цифра от 1 до 9.

sudoku = cv2.resize(sudoku, (450,450))
grid = np.zeros([9,9])
for i in range(9):
    for j in range(9):
        image = sudoku[i*50:(i+1)*50,j*50:(j+1)*50]
        if image.sum() > 25000:    
            grid[i][j] = identify_number(image)
        else:
            grid[i][j] = 0    
grid =  grid.astype(int)

Функция identify_number берет изображение цифры и предсказывает цифру на изображении.

def identify_number(image):
    image_resize = cv2.resize(image, (28,28))    # For plt.imshow
    image_resize_2 = image_resize.reshape(1,1,28,28)    # For input to model.predict_classes
#    cv2.imshow('number', image_test_1)
    loaded_model_pred = loaded_model.predict_classes(image_resize_2 
                                                      , verbose = 0)
    return loaded_model_pred[0]

После выполнения вышеуказанных шагов наша сетка судоку будет выглядеть так:

C: вычислить решение судоку с использованием алгоритма поиска с возвратом

Мы будем использовать алгоритм обратного отслеживания, чтобы вычислить решение судоку.

Найдите в сетке запись, которая еще не назначена. Если он найден, для ссылочных параметров row, col будет установлено неназначенное местоположение, и будет возвращено значение true. Если не осталось неназначенных записей, возвращается false. «L» - это переменная списка, переданная из функции resolve_sudoku для отслеживания приращения строк и столбцов.

def find_empty_location(arr,l):
    for row in range(9):
        for col in range(9):
            if(arr[row][col]==0):
                l[0]=row
                l[1]=col
                return True
    return False

Возвращает логическое значение, которое указывает, соответствует ли какая-либо назначенная запись в указанной строке заданному номеру.

def used_in_row(arr,row,num):
    for i in range(9):   
        if(arr[row][i] == num):  
            return True
    return False

Возвращает логическое значение, которое указывает, соответствует ли какая-либо назначенная запись в указанном столбце заданному номеру.

def used_in_col(arr,col,num):
    for i in range(9):  
        if(arr[i][col] == num):  
            return True
    return False

Возвращает логическое значение, которое указывает, соответствует ли какая-либо назначенная запись в указанном поле 3x3 заданному номеру.

def used_in_box(arr,row,col,num):
    for i in range(3):
        for j in range(3):
            if(arr[i+row][j+col] == num):     
            return True 
    return False

Проверяет, будет ли допустимо присвоение num заданному (row, col). Возвращает логическое значение, которое указывает, будет ли допустимо присвоение num заданному (строка, столбец) местоположению. Проверьте, не помещено ли «число» в текущую строку, текущий столбец и текущее поле 3x3.

def check_location_is_safe(arr,row,col,num):
    return not used_in_row(arr,row,num) and 
           not used_in_col(arr,col,num) and 
           not used_in_box(arr,row - row%3,col - col%3,num)

Берет частично заполненную сетку и пытается присвоить значения всем неназначенным местоположениям таким образом, чтобы удовлетворить требованиям для решения судоку (отсутствие дублирования в строках, столбцах и полях). ‘L’ - это переменная списка, которая хранит запись строки и столбца в функции find_empty_location. Назначение значений списка строкам и столбцам, которые мы получили из вышеуказанной функции.

def solve_sudoku(arr):
    l=[0,0] 
    if(not find_empty_location(arr,l)):
        return True 
    row=l[0]
    col=l[1] 
    for num in range(1,10): 
        if(check_location_is_safe(arr,row,col,num)): 
            arr[row][col]=num 
            if(solve_sudoku(arr)): 
                return True 
            # failure, unmake & try again 
            arr[row][col] = 0 
    
    return False

Последнее, что нужно - распечатать сетку.

def print_grid(arr):
    for i in range(9):
        for j in range(9):   
            print (arr[i][j])  
        print ('\n')

Теперь давайте сшиваем все функции в главную функцию.

def sudoku_solver(grid):
    if(solve_sudoku(grid)):
        print('---')
    else:
        print ("No solution exists")
    grid = grid.astype(int)
    return grid

Результатом этой функции будет наша решенная судоку.

Заключение

Итак, нам, наконец, удалось решить сетку судоку только на основе изображения. Если вы так долго продержались ... спасибо! Надеюсь, для вас было что-то ценное. Решатель ни в коем случае не надежен; у него все еще есть проблемы с некоторыми изображениями, и он либо не сможет их проанализировать, либо проанализирует их неправильно, что приведет к невозможности их решения (потому что он мог быть проанализирован как недопустимая головоломка). Целью, конечно же, было развитие некоторых новых технологий, и проект был ценным с этой точки зрения. Исходный код доступен на Github. Напишите мне, если сочтете это полезным или у вас возникнут дополнительные вопросы.

Спасибо!