使用OpenCV和Python查找数独网格 [英] Find sudoku grid using OpenCV and Python

问题描述

我正在尝试使用OpenCV在数独谜题中检测网格，但是我在最后几个步骤上遇到了麻烦(我想).

I'm trying to detect the grid in sudoku puzzles using OpenCV but I'm having troubles with the last steps (I guess).

我正在做的是:

• 缩小图像
• 模糊
• 应用高通滤波器(双向)
• 使用自适应阈值对图像进行阈值处理
• 一些膨胀和侵蚀

所有这些为我提供了以下图像:

All this gives me the following images:

从现在开始，我需要检测网格，并且发现了几种方法来实现这一点，但是没有一种方法使我有足够的信心来保持足够的健壮性.

From now on, I need to detect the grid, and I found a few methods of how to do that but none of them gave me the confidence of being robust enough.

第一个是使用霍夫变换来找到线，但是我发现了很多虚假的线.

The first one is to find lines using Hough transform but I find a lot of spurious lines.

另一种方法是使用连接的组件，这给了我最好的结果.我尝试实现RANSAC作为获得正确质心的一种方法，但是效果不佳，并且还需要一段时间才能得到答案(一会儿"少于2秒，但是稍后我想在其中使用它实时视频).

The other is using connected components, which gives me the best results. I tried to implement RANSAC as a way to get the right centroids, but I'm not having good results and also takes a while to get the answer ("a while" is less than 2 seconds, but later I want to use it in real time video).

有什么想法可以做到吗?我的意思是，我该如何丢弃错误的质心并开始求解数独?

Any idea how this can be done? I mean, how can I discard the wrong centroids and start solving the sudoku?

推荐答案

霍夫变换绝对是必经之路.实际上，在引入此技术时，网格检测是最受欢迎的示例之一(请参见此处和此处).

Hough transform is definitely the way to go. In fact grid detection is one of the most popular example when introducing this tehcnique (see here and here).

我建议执行以下步骤:

• 下采样
• 模糊
• 应用Canny(从使用的角度出发，您应该很好地猜测网格线的最小/最大可能长度)
• 扩大边缘图像(canny在网格中发现分隔符的两个边界为不同的边缘，扩大将使这些边缘再次合并)
• 腐蚀(现在我们的边框太粗了，霍夫会发现太多的线)
• 应用HoughLines
• 合并相似的行

在最后一步，您有许多可行的方法，这在很大程度上取决于您随后要对结果进行的处理.例如，您可以使用找到的图像创建新的边缘图像，然后再次施加腐蚀和磨损，可以使用基于傅立叶的方法，也可以仅通过一些任意阈值(仅举几例)对线进行过滤.我实现了最后一个(从概念上讲，这是最容易做到的)，这就是我所做的(尽管我不确定这是否是最好的方法):

At the last step you have many possible ways to go and it strongly depends on what you want to do with the results afterwards. For example you could create a new edge image with the found images and apply erosion and hough again, you could use something Fourier-based, or you could just simply filter the lines by some arbitrary threshold values (just to mention a few). I implemented the last one (since conceptually that is the easiest one to do), here is what i did (although i am not at all sure whether this is the best approach or not):

• 为rho和theta值定义了一个任意阈值
• 检查边缘在另一个阈值中有多少次
• 从最相似的一行开始，我删除与之相似的行(这样，在某种意义上，我们将保持相似组中的中间"行)
• 其余的几行是最终的候选人

看代码，玩得开心:

import cv2
import numpy as np


filter = False


file_path = ''
img = cv2.imread(file_path)

gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
edges = cv2.Canny(gray,90,150,apertureSize = 3)
kernel = np.ones((3,3),np.uint8)
edges = cv2.dilate(edges,kernel,iterations = 1)
kernel = np.ones((5,5),np.uint8)
edges = cv2.erode(edges,kernel,iterations = 1)
cv2.imwrite('canny.jpg',edges)

lines = cv2.HoughLines(edges,1,np.pi/180,150)

if not lines.any():
    print('No lines were found')
    exit()

if filter:
    rho_threshold = 15
    theta_threshold = 0.1

    # how many lines are similar to a given one
    similar_lines = {i : [] for i in range(len(lines))}
    for i in range(len(lines)):
        for j in range(len(lines)):
            if i == j:
                continue

            rho_i,theta_i = lines[i][0]
            rho_j,theta_j = lines[j][0]
            if abs(rho_i - rho_j) < rho_threshold and abs(theta_i - theta_j) < theta_threshold:
                similar_lines[i].append(j)

    # ordering the INDECES of the lines by how many are similar to them
    indices = [i for i in range(len(lines))]
    indices.sort(key=lambda x : len(similar_lines[x]))

    # line flags is the base for the filtering
    line_flags = len(lines)*[True]
    for i in range(len(lines) - 1):
        if not line_flags[indices[i]]: # if we already disregarded the ith element in the ordered list then we don't care (we will not delete anything based on it and we will never reconsider using this line again)
            continue

        for j in range(i + 1, len(lines)): # we are only considering those elements that had less similar line
            if not line_flags[indices[j]]: # and only if we have not disregarded them already
                continue

            rho_i,theta_i = lines[indices[i]][0]
            rho_j,theta_j = lines[indices[j]][0]
            if abs(rho_i - rho_j) < rho_threshold and abs(theta_i - theta_j) < theta_threshold:
                line_flags[indices[j]] = False # if it is similar and have not been disregarded yet then drop it now

print('number of Hough lines:', len(lines))

filtered_lines = []

if filter:
    for i in range(len(lines)): # filtering
        if line_flags[i]:
            filtered_lines.append(lines[i])

    print('Number of filtered lines:', len(filtered_lines))
else:
    filtered_lines = lines

for line in filtered_lines:
    rho,theta = line[0]
    a = np.cos(theta)
    b = np.sin(theta)
    x0 = a*rho
    y0 = b*rho
    x1 = int(x0 + 1000*(-b))
    y1 = int(y0 + 1000*(a))
    x2 = int(x0 - 1000*(-b))
    y2 = int(y0 - 1000*(a))

    cv2.line(img,(x1,y1),(x2,y2),(0,0,255),2)

cv2.imwrite('hough.jpg',img)

这篇关于使用OpenCV和Python查找数独网格的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！