Функция для сортировки контуров судоку сверху вниз и слева направо?

Мой метод подойдет для любого изображения судоку без какого-либо процесса рисования контуров. В моем примере я буду использовать судоку с сайта sudoku.com, но он прекрасно работает и с вашим изображением.

В своем подходе я буду использовать более надежный способ обнаружения, извлечения и сортировки 81 квадрата судоку в любой картинке судоку.

Изображение судоку, которое я буду использовать:

1. прочитайте изображение в оттенках серого:

import cv2
import numpy as np
from matplotlib import pyplot as plt

# reading the image directly in grayscale
image = cv2.imread(image, cv2.IMREAD_GRAYSCALE)

2. Обнаружение краев и преобразование изображения из серых тонов в бинарное черно-белое.

# Edge detection with Canny function
img_bin = cv2.Canny(image,50,110)
dil_kernel = np.ones((3,3), np.uint8)
# dilatation of the edges
img_bin=cv2.dilate(img_bin,dil_kernel,iterations=1)

Результат img_bin:

3. Выбор только горизонтальных ребер

line_min_width = 40 # minimum width of the selected lines

kernel_hprizontal = np.ones((1,line_min_width), np.uint8) # mask
img_bin_h = cv2.morphologyEx(img_bin, cv2.MORPH_OPEN, kernel_hprizontal)

Результат img_bin_h:

4. Выбор только вертикальных ребер

kernel_vertical = np.ones((line_min_width,1), np.uint8)
img_bin_v = cv2.morphologyEx(img_bin, cv2.MORPH_OPEN, kernel_vertical)

Результат img_bin_v:

5. Объединение вертикальных и горизонтальных линий

img_bin_final=img_bin_h|img_bin_v
final_kernel = np.ones((3,3), np.uint8)
# Dilatting the edges for easier shape detection
img_bin_final=cv2.dilate(img_bin_final,final_kernel,iterations=1)

Результат img_bin_final:

6. Разделение сетки судоку на разные регионы

ret, labels, stats, centroids = cv2.connectedComponentsWithStats(~img_bin_final, connectivity=8, ltype=cv2.CV_32S)

# THIS CODE IS ONLY USED TO SHOW THE REGIONS IN DIFERENT COLORS ########
# Map component labels to hue val
label_hue = np.uint8(179*labels/np.max(labels))
blank_ch = 255*np.ones_like(label_hue)
labeled_img = cv2.merge([label_hue, blank_ch, blank_ch])

# cvt to BGR for display
labeled_img = cv2.cvtColor(labeled_img, cv2.COLOR_HSV2BGR)

# set bg label to black
labeled_img[label_hue==0] = 0
########################################################################

Результат labeled_img:

7. Выбор только 81 квадрата судоку

percentage_limit = 0.15 # percentatge of error for the area of the sudoku squares

# Selecting the shapes with more than 1000 of area and with a square shape (height and width (h and w) must be similar by and error of 10)
boxes = [[x,y,w,h, w*h] for x,y,w,h,_ in stats if w*h>1000 and abs(w - h) < 10]
# median of the areas of the selected squares
median = np.median(np.array(boxes)[:,4])
# using the median to choose the 81 squares corresponding to each cell of the sudoku with an error of 'percentage_limit'
boxes = [x for x in boxes if x[4] > median*(1-percentage_limit) and x[4] < median*(1+percentage_limit)]
if len(boxes) != 81: # Simple error check
    print('Error: The number of cells is not 81')

8. Наконец сортируем все квадраты. Результатом будет матрица с соответствующим квадратом каждой позиции судоку.

boxes = sorted(boxes, key=lambda x: x[0])
result = []
for row in range(9):
    result.append(sorted(boxes[row*9:(row+1)*9], key=lambda x: x[1]))

Например, box[0] вернет первую строку судоку, а box[0][1] вернет квадрат в первой строке и втором столбце.

Надеюсь, поможет!

Учитывая количество красного цвета на границах ячеек, вы можете найти ячейки, извлекая пиксели с ярко выраженным красным цветом. Это можно найти, вычитая из красного канала среднее значение синего и зеленого каналов, а затем обрезая его до нуля. Затем дискретизируйте оставшийся красный канал, чтобы создать черно-белую карту.

imgage_bgr = cv2.imread('path/to/image.jpg', cv2.IMREAD_COLOR)
img_very_red = (
    image_bgr[:,:,2].astype(np.int32) - image_bgr[:,:,:2].sum(axis=-1)//2
).clip(0).astype(np.uint8)
_, img_bw = cv2.threshold(img_very_red, 128, 255, cv2.THRESH_BINARY | cv2.THRESH_OTSU)

Затем вы можете найти контуры в виде списка, получить ограничивающие рамки и вычислить площади и соотношения сторон.

ctrs, _ = cv2.findContours(img_bw, cv2.RETR_LIST, cv2.CHAIN_APPROX_SIMPLE)
bounding_boxes = [cv2.boundingRect(c) for c in ctrs]
areas = [w*h for _,_,w,h in bounding_boxes]
aspects = [h/w for _,_,w,h in bounding_boxes]

Мы ожидаем, что области будут иметь 81 примерно одинаковое значение, а соотношения сторон будут близки к 1. Сначала мы находим границы областей, глядя на гистограмму журнала областей (в противном случае большие области затмевают биннинг).

counts, log_edges = np.histogram(np.log(areas), bins=10)
area_ix = (counts==81).argmax()
area_min, area_max = np.exp(log_edges)[ix:ix+2]

cell_bboxes = [
    bbox for bbox, area, aspect in zip(bounding_boxes, areas, aspects)
    if (area_min < area < area_max) and (0.95 < aspect < 1.05)
]

Сортировать ячейки L по R и T по B не так просто, как простой вызов sorted. Местоположение x,y может отклоняться от ячейки на 1 или 2 пикселя. Я бы использовал алгоритм кластеризации, такой как кластеризация k-средних или средний сдвиг, чтобы сгруппировать позиции x и позиции y.

from sklearn.cluster import KMeans

mean_width = np.mean([c[3] for c in cell_bboxes]).round()
initial_cluster_centers = np.arange(9).reshape(-1,1) * mean_width
x_kmeans = KMeans(9, init=initial_cluster_centers )
y_kmeans = KMeans(9, init=initial_cluster_centers )
x_labels = x_kmeans.fit_predict(np.array([[b[0]] for b in cell_bboxes]))
y_labels = y_kmeans.fit_predict(np.array([[b[1]] for b in cell_bboxes]))

# L to R then T to B -> y first, then x
sorted_cell_bboxes = [
    bbox for _,_,bbox in 
    sorted(zip(y_labels, x_labels, cell_bboxes))
]

Когда я запускаю это, я получаю следующий результат для sorted_cell_bboxes:

[(11, 11, 91, 92),
 (106, 11, 95, 92),
 (205, 11, 91, 91),
 (307, 11, 92, 91),
 (403, 11, 94, 91),
 (502, 10, 91, 92),
 (604, 10, 91, 92),
 (798, 10, 92, 91),
 (700, 10, 94, 92),
 (11, 107, 91, 95),
 (106, 107, 95, 95),
 (205, 107, 91, 94),
 (307, 106, 92, 95),
 (403, 106, 94, 95),
 (502, 106, 91, 95),
 (604, 106, 91, 95),
 (798, 106, 92, 95),
 (700, 106, 94, 95),
 (11, 206, 91, 91),
 (107, 206, 94, 91),
 (205, 206, 91, 91),
 (307, 206, 92, 91),
 (403, 205, 94, 92),
 (502, 205, 91, 92),
 (604, 205, 91, 92),
 (798, 205, 92, 91),
 (700, 205, 94, 92),
 ...
]