Извлеките и решите судоку из изображения.
Мне, как и многим другим, нравится решать новые головоломки и вопросы. В школьные годы каждое утро я решала судоку в «Таймс оф Индия». Все знают, как решать судоку, но задумывались ли вы, что вы можете найти решение, даже не почесав голову. Вам просто нужно щелкнуть изображение судоку, и он должен рассчитать решение для вас.
Питер Норвиг в своей книге Решая каждую головоломку судоку дает красивое изложение правила игры всего в одном предложении.
Загадка решена, если квадраты в каждой единице заполнены перестановкой цифр от 1 до 9.
Правила игры:
Все дело в том, чтобы поместить цифры от 1 до 9 в квадрат 9x9, разделенный на 9 полей. Но значение ячейки не может быть повторено ни среди одного из ее сверстников.
Теперь, когда вы знаете правила, давайте сделаем тяжелую работу, чтобы вам не приходилось тратить минуты или, может быть, часы на решение судоку. Опять же, что нам делать? Возьмите это изображение, извлеките из него судоку и вычислите решение.
Мы разделим весь процесс на 3 этапа.
A: извлеките судоку из изображения
B: извлеките каждое число, присутствующее на изображении
C: вычислить решение судоку, используя алгоритм
A: извлеките судоку из изображения
Прежде чем продолжить, нам нужно немного обработать изображение.
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) kernel = np.array([[0., 1., 0.], [1., 1., 1.], [0., 1., 0.]],np.uint8) proc = cv2.dilate(proc, kernel)
2. Найдите углы самого большого многоугольника.
Следующий шаг - найти 4 крайних угла самого большого контура на изображении. Таким образом, мы найдем все контуры, отсортируем по площади в порядке убывания и выберем тот, у которого самая большая площадь.
_, contours, h = cv2.findContours(img.copy(), cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE) contours = sorted(contours, key=cv2.contourArea, reverse=True) polygon = contours[0]
Использование `operator.itemgetter` с` max` и `min` позволяет нам получить индекс точки. Каждая точка представляет собой массив с 1 координатой, следовательно, геттер [0], затем [0] или [1] используется для получения x и y соответственно.
Нижняя правая точка имеет наибольшее (x + y) значение. В верхнем левом углу указано наименьшее значение точки (x + y). Левая нижняя точка имеет наименьшее значение (x - y). Верхняя правая точка имеет наибольшее значение (x - y).
bottom_right, _ = max(enumerate([pt[0][0] + pt[0][1] for pt in
polygon]), key=operator.itemgetter(1))
top_left, _ = min(enumerate([pt[0][0] + pt[0][1] for pt in
polygon]), key=operator.itemgetter(1))
bottom_left, _ = min(enumerate([pt[0][0] - pt[0][1] for pt in
polygon]), key=operator.itemgetter(1))
top_right, _ = max(enumerate([pt[0][0] - pt[0][1] for pt in
polygon]), key=operator.itemgetter(1))
Теперь, когда у нас есть все 4 координаты. Мы вернем массив всех 4 точек, используя индексы. Каждая точка находится в собственном массиве одной координаты.
[polygon[top_left][0], polygon[top_right][0], polygon[bottom_right][0], polygon[bottom_left][0]]
3: Обрезка и деформация изображения
Теперь, когда у нас есть все 4 координаты судоку, мы обрежем и деформируем прямоугольную часть изображения в квадрат аналогичного размера. Прямоугольник, описываемый верхней левой, верхней правой, нижней правой и нижней левой точками.
Примечание. Явно задайте тип данных float32, иначе `getPerspectiveTransform` выдаст ошибку.
top_left, top_right, bottom_right, bottom_left = crop_rect[0], crop_rect[1], crop_rect[2], crop_rect[3]
src = np.array([top_left, top_right, bottom_right, bottom_left], dtype='float32')
side = max([ distance_between(bottom_right, top_right),
distance_between(top_left, bottom_left),
distance_between(bottom_right, bottom_left),
distance_between(top_left, top_right) ])
Функция distance_between () возвращает скалярное расстояние между двумя точками.
def distance_between(p1, p2):
a = p2[0] - p1[0]
b = p2[1] - p1[1]
return np.sqrt((a ** 2) + (b ** 2))
Мы опишем квадрат со стороной рассчитанной длины, это новая перспектива, к которой мы хотим деформироваться. Следующее, что нужно сделать, это получить матрицу преобразования для перекоса изображения, чтобы она соответствовала квадрату, сравнивая 4 точки до и после. В конце мы выполним трансформацию исходного изображения.
dst = np.array([[0, 0], [side - 1, 0], [side - 1, side - 1], [0, side - 1]], dtype='float32') m = cv2.getPerspectiveTransform(src, dst) cv2.warpPerspective(img, m, (int(side), int(side)))
4: вывести сетку из квадратного изображения
Выводит сетку из 81 ячейки из квадратного изображения. Мы меняем местами j и i, чтобы прямоугольники сохранялись в списке, читаемом слева направо, а не сверху вниз.
squares = []
side = img.shape[:1]
side = side[0] / 9
for j in range(9):
for i in range(9):
p1 = (i * side, j * side) #Top left corner of a box
p2 = ((i + 1) * side, (j + 1) * side) #Bottom right corner
squares.append((p1, p2)) return squares
5. Получите каждую цифру
Следующим шагом будет извлечение цифр из их ячеек и построение массива.
digits = []
img = pre_process_image(img.copy(), skip_dilate=True)
for square in squares:
digits.append(extract_digit(img, square, size))
extract_digit - это функция, которая извлекает цифру (если она есть) из квадрата судоку. Он получает цифровую рамку из всего квадрата, используйте функцию нахождения объекта заливки, чтобы получить самый большой объект в середине квадрата. Мы ожидаем найти пиксель, принадлежащий цифре на поле, который используется для определения области посередине. Затем мы масштабируем и дополняем цифру так, чтобы она соответствовала квадрату размера цифры, которую мы используем для машинного обучения. Кроме того, мы должны игнорировать любые маленькие ограничивающие рамки.
def extract_digit(img, rect, size):
digit = cut_from_rect(img, rect)
h, w = digit.shape[:2]
margin = int(np.mean([h, w]) / 2.5)
_, bbox, seed = find_largest_feature(digit, [margin, margin], [w
- margin, h - margin])
digit = cut_from_rect(digit, bbox)
w = bbox[1][0] - bbox[0][0]
h = bbox[1][1] - bbox[0][1]
if w > 0 and h > 0 and (w * h) > 100 and len(digit) > 0:
return scale_and_centre(digit, size, 4)
else:
return np.zeros((size, size), np.uint8)
Теперь у нас есть окончательное предварительно обработанное изображение судоку, наша следующая задача - извлечь каждую цифру из изображения, сохранить ее в матрице и вычислить решение судоку с помощью некоторого алгоритма.
Мы обсудим эти 2 процесса в следующей части.
Для ленивых из вас, кто пропустил чтение или выполнение учебника самостоятельно, вот ссылка на исходный код.
