Решайте судоку с помощью компьютерного зрения и алгоритма ограничения ограничений

Опубликовано: 4 Января, 2022

В этой статье описывается программа на Python 2.7 для решения судоку 9 × 9 в Android-приложении «Судоку» с сайта genina.com. Чтобы решить судоку Android-приложения «Судоку» на сайте genina.com, делается снимок экрана игры (получается изображение 720 × 1280), затем число, найденное в каждом из 81 квадрата, получается с использованием алгоритма KNN один раз. Каждый элемент определяется, судоку решается с использованием алгоритма удовлетворения ограничений с возвратом.

Слева наш ввод: снимок экрана, который мы собираемся проанализировать. Справа - решение.

Как это работает?
Шаг 1. Предварительная обработка изображения
Первый шаг, предварительная обработка изображения: извлеките каждый квадрат судоку по отдельности и сохраните их последовательно как фото # .png (где # идет от 0 до 80). Получаются изображения размером 80 × 75 пикселей.

Код:


Вход: photo0.png. Это фото, которое мы собираемся проанализировать.

Код:

#/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()

Показать производительность алгоритма KNN

Vector.txt содержит все элементы, извлеченные из скриншота (где квадраты прокручивались слева направо, сверху вниз). В этом проекте эффективность алгоритма KNN составила 97% по отношению ко всем изображениям, проанализированным в тесте. В случае ошибки в распознавании чисел есть возможность вручную изменить предсказание поля в vector.txt .

Результат распознавания всех цифр решетки судоку изображения photo0.jpg

Шаг 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):