Решайте судоку с помощью компьютерного зрения и алгоритма ограничения ограничений
В этой статье описывается программа на Python 2.7 для решения судоку 9 × 9 в Android-приложении «Судоку» с сайта genina.com. Чтобы решить судоку Android-приложения «Судоку» на сайте genina.com, делается снимок экрана игры (получается изображение 720 × 1280), затем число, найденное в каждом из 81 квадрата, получается с использованием алгоритма KNN один раз. Каждый элемент определяется, судоку решается с использованием алгоритма удовлетворения ограничений с возвратом.
Как это работает?
Шаг 1. Предварительная обработка изображения
Первый шаг, предварительная обработка изображения: извлеките каждый квадрат судоку по отдельности и сохраните их последовательно как фото # .png (где # идет от 0 до 80). Получаются изображения размером 80 × 75 пикселей.
Код:
Код:
#/Preprocessing.py / import cv2 import numpy as np Functions import # Relative path path = "./Screenshots/" # Image to analize number = input ( "Enter image number: " ) globalPath = path + "photo" + str (number) + ".png" image = cv2.imread(globalPath) # Save the name of the image to analize after in Main.py file = open ( "image.txt" , "w" ) file .write(globalPath) file .close() # MAIN if __name__ = = '__main__' : # PREPROCESSING -> Crop the edges, ads and all # the images outside the sudoku board image = Functions.cropImage(image, 218 ) image = Functions.rotateImage(image, 180 ) image = Functions.cropImage(image, 348 ) image = Functions.rotateImage(image, 180 ) # Crop each box in the sudoku board cont = 0 w = 0 for j in range ( 9 ): h = 0 for i in range ( 9 ): nombre = "image" + str (cont) + ".png" image1 = Functions.cropBox(image, w, h, 75 , 80 ) # Save the image Functions.saveImage(image1, nombre) h = h + 80 cont = cont + 1 # Position of the pixel where start the image w = 80 * (j + 1 ) |
Код: создайте библиотеку с функциями только для предварительной обработки и преобразования изображений под названием «Функции».
Шаг 2: преобразование изображения
Вырежьте границы каждого блока, если есть какие-то черные границы, которые можно вывести в нашем анализе. Каждое изображение имеет размер 56 × 51 пиксель.
Код:
#/Transformation.py / import cv2 import numpy as np Functions import # Relative path path = "./Images/" if __name__ = = '__main__' : for x in range ( 81 ): # Image to analize nameImage = "image" + str (x) + ".png" image = cv2.imread(path + nameImage) image = Functions.cropBorder(image) Functions.saveImage(image, nameImage) |
Шаг 3: Классификация KNN
Проанализируйте, какое число в коробке. В этом случае алгоритм Кэнни используется, чтобы определить, есть ли число или это пустое поле. Затем с помощью алгоритма KNN определяется, какой номер находится в коробке. Для извлечения характеристик использовались моменты Hu: 1 и 2, фильтр Гаусса для фильтрации и неконтролируемая пороговая обработка.
Код:
#/Main.py / import numpy as np from matplotlib import pyplot as plt import matplotlib.patches as mpatches plt.rcParams[ 'image.cmap' ] = 'gray' from mpl_toolkits.mplot3d import Axes3D from skimage import io, color, img_as_float, filters from skimage.feature import hog import cv2 import mahotas # Function to extract characteristics of the images # to later use them in the Knn algorithm def extraction(image): # PREPROCESSING -> Convert image to grayscale aux = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY) # FILTERING -> Apply Gauss Filter aux = cv2.GaussianBlur(aux, ( 3 , 3 ), 0 ) # SEGMENTATION -> Apply Thresholding simple ret, th = cv2.threshold(aux, 0 , 255 , cv2.THRESH_BINARY + cv2.THRESH_OTSU) aux = th # FEATURE EXTRACTION -> Obtain Hu Moments hu = cv2.HuMoments(cv2.moments(aux)).flatten() # Analysis the features (Hu Moments) return aux, [hu[ 0 ], hu[ 1 ]] # Training Data Base (YTrain) # Load all images of each numbers that appears in sudoku board number1 = io.ImageCollection( './Images / Train / Y1/*.png:./Images / Train / Y1/*.jpg' ) number2 = io.ImageCollection( './Images / Train / Y2/*.png:./Images / Train / Y2/*.jpg' ) number3 = io.ImageCollection( './Images / Train / Y3/*.png:./Images / Train / Y3/*.jpg' ) number4 = io.ImageCollection( './Images / Train / Y4/*.png:./Images / Train / Y4/*.jpg' ) number5 = io.ImageCollection( './Images / Train / Y5/*.png:./Images / Train / Y5/*.jpg' ) number6 = io.ImageCollection( './Images / Train / Y6/*.png:./Images / Train / Y6/*.jpg' ) number7 = io.ImageCollection( './Images / Train / Y7/*.png:./Images / Train / Y7/*.jpg' ) number8 = io.ImageCollection( './Images / Train / Y8/*.png:./Images / Train / Y8/*.jpg' ) number9 = io.ImageCollection( './Images / Train / Y9/*.png:./Images / Train / Y9/*.jpg' ) # Create a class for each element Element: class def __init__( self ): self .number = None self .image = None self .feature = [] self .distance = 0 # Analize data data = [] i = 0 # Analize number 1 iter = 0 for object in number1: data.append(Element()) data[i].number = '1' data[i].image, data[i].feature = extraction( object ) i + = 1 iter + = 1 print ( "number1 is OK" ) # Analize number 2 iter = 0 for object in number2: data.append(Element()) data[i].number = '2' data[i].image, data[i].feature = extraction( object ) i + = 1 iter + = 1 print ( "number2 is OK" ) # Analize number 3 iter = 0 for object in number3: data.append(Element()) data[i].number = '3' data[i].image, data[i].feature = extraction( object ) i + = 1 iter + = 1 print ( "number3 is OK" ) # Analize number 4 iter = 0 for object in number4: data.append(Element()) data[i].number = '4' data[i].image, data[i].feature = extraction( object ) i + = 1 iter + = 1 print ( "number4 is OK" ) # Analize number 5 iter = 0 for object in number5: data.append(Element()) data[i].number = '5' data[i].image, data[i].feature = extraction( object ) i + = 1 iter + = 1 print ( "number5 is OK" ) # Analize number 6 iter = 0 for object in number6: data.append(Element()) data[i].number = '6' data[i].image, data[i].feature = extraction( object ) i + = 1 iter + = 1 print ( "number6 is OK" ) # Analize number 7 iter = 0 for object in number7: data.append(Element()) data[i].number = '7' data[i].image, data[i].feature = extraction( object ) i + = 1 iter + = 1 print ( "number7 is OK" ) # Analize number 8 iter = 0 for object in number8: data.append(Element()) data[i].number = '8' data[i].image, data[i].feature = extraction( object ) i + = 1 iter + = 1 print ( "number8 is OK" ) # Analize number 9 iter = 0 for object in number9: data.append(Element()) data[i].number = '9' data[i].image, data[i].feature = extraction( object ) i + = 1 iter + = 1 print ( "number9 is OK" ) print ( "Complete analysis of the Train database" ) # KNN print ( "
Initialization KNN" ) # Element to analize # Remember to apply Transformation.py when you # want to evaluate a new image. test = Element() for aux in range ( 81 ): name = './Images / image' + str (aux) + '.png' image = io.imread(name) # COUNTING OBJECTS WITHIN THE IMAGE WITH CANNY ALGORITHM borders = cv2.Canny(image, 10 , 140 ) # OpenCV4 ctns, _ = cv2.findContours(borders, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE) contours = len (ctns) # If it is different from an empty box -> in empty boxes the algorithm # marks zero because it does not find anything if (contours ! = 0 ): test.image, test.feature = extraction(image) test.number = '1' # label initial i = 0 sum = 0 for ft in data[ 0 ].feature: sum = sum + np.power(np. abs (test.feature[i] - ft), 2 ) i + = 1 d = np.sqrt( sum ) for element in data: sum = 0 i = 0 for ft in (element.feature): sum = sum + np.power(np. abs ((test.feature[i]) - ft), 2 ) i + = 1 element.distance = np.sqrt( sum ) if ( sum < d): d = sum test.number = element.number else : test.number = '.' if (aux = = 0 ): vector = str (test.number) else : vector = vector + str (test.number) print (vector) # Save in a string all the boxes in the sudoku board archivo = open ( "vector.txt" , "w" ) archivo.write(vector) archivo.close() |
Vector.txt содержит все элементы, извлеченные из скриншота (где квадраты прокручивались слева направо, сверху вниз). В этом проекте эффективность алгоритма KNN составила 97% по отношению ко всем изображениям, проанализированным в тесте. В случае ошибки в распознавании чисел есть возможность вручную изменить предсказание поля в vector.txt .
Шаг 4: Теперь решите судоку!
Для решения судоку представлен алгоритм удовлетворения ограничений с возвратом.
Код:
#/Solver.py / import numpy as np # Dictionary with grid numbers def solverGrid(grid): values = valuesGrid(grid) return searchValues(values) # Exchange of items def exchangeValues(A, B): return [a + b for a in A for b in B] # Define initial values def initialValues(grid): return dict ( zip (sections, grid)) # Define values in the grid def valuesGrid(grid): numbers = [] for c in grid: if c = = '.' : numbers.append( '123456789' ) elif c in '123456789' : numbers.append(c) return dict ( zip (sections, numbers)) # Delete the values that are already inside the grid def eliminateValues(numbers): solved_values = [box for box in numbers.keys() if len (numbers[box]) = = 1 ] for box in solved_values: digit = numbers[box] for vecino in neighbors[box]: numbers[vecino] = numbers[vecino].replace(digit, '') return numbers def onlyOption(numbers): for unit in unitlist: for digit in '123456789' : dplaces = [box for box in unit if digit in numbers[box]] if len (dplaces) = = 1 : numbers[dplaces[ 0 ]] = digit return numbers def reduceSudoku(numbers): stalled = False while not stalled: # Check how many boxes have a determined value solved_values_before = len ([box for box in numbers.keys() if len (numbers[box]) = = 1 ]) # Set the Eliminate Strategy numbers = eliminateValues(numbers) # Use the Only Choice Strategy numbers = onlyOption(numbers) # Check how many boxes have a determined value, to compare solved_values_after = len ([box for box in numbers.keys() if len (numbers[box]) = = 1 ]) # If no new values were added, stop the loop. stalled = solved_values_before = = solved_values_after # Sanity check, return False if there is a box with zero available values: if len ([box for box in numbers.keys() if len (numbers[box]) = = 0 ]): return False return numbers def searchValues(numbers):
РЕКОМЕНДУЕМЫЕ СТАТЬИ |