使用OpenCV和Python查找数独网格

Question

我正在使用OpenCV尝试检测数独谜题中的网格，但是我在最后几个步骤（我猜）遇到了问题。

我所做的是：

• 对图像进行下采样
• 模糊处理
• 应用高通滤波器（双边滤波）
• 使用自适应阈值对图像进行阈值化
• 一些膨胀和侵蚀运算

所有这些步骤都给我提供了以下图片：

从现在开始，我需要检测出网格，并且我找到了一些方法来实现这一目标，但没有一个能让我有足够的信心认为它足够稳健。

第一个方法是使用霍夫变换来找线，但我发现很多冗余线。

另一个方法是使用连通组件，这给了我最好的结果。我试图实现RANSAC作为获取正确质心的方法，但是结果不好，并且需要一段时间才能得到答案（“一段时间”小于2秒，但后来我想在实时视频中使用它）。

有什么办法可以做到这一点吗？我的意思是，我该如何舍弃错误的中心点并开始解决数独问题？

- fferrin

---

你的输入图像总是倾斜的吗？期望一个数独的正面照片是一个合理的要求。 - DarkCygnus

我知道，但我想要让它足够灵活，以便能够跳转到实时视频检测。你认为这不是一个好主意还是一个起点？ - fferrin

你已经了解了网格，并且有足够的点来适应它。没有必要完美地识别所有交叉点。 - Piglet

我建议先从正面图像开始（或尽可能正面而不倾斜的图像），在满意后再尝试倾斜的图像，并提高您的算法鲁棒性。我认为Hough变换可以给您带来良好的结果（在我看来，您所得到的结果看起来很有前途）。您也可以尝试其概率版本。另一个可能有效的想法是对图像进行OCR，从而获得数字的“重心”（以及网格方块的中心）。将Hough与这些质心相结合，您肯定可以更精确地过滤它。 - DarkCygnus

我不知道有概率版本。我正在学习OpenCV和图像处理，所以这似乎是一个不错的选择。谢谢！ - fferrin

你是如何进行数字识别的？我还没有找到可靠的方法。 - pm100

Answer 1

霍夫变换绝对是可行的方法。实际上，当引入这种技术时，网格检测是最受欢迎的示例之一（请参见此处和此处）。

我建议按照以下步骤进行：

• 下采样
• 模糊处理
• 应用Canny算法（您应该对使用视角的网格线的最小/最大可能长度有一个很好的猜测）
• 膨胀边缘图像（Canny找到网格分隔符的两个边框作为不同的边缘，膨胀将使这些边缘再次合并）
• 侵蚀（现在我们有了太厚的边框，霍夫会找到太多的线）
• 应用HoughLines算法
• 合并相似的线条

在最后一步中，您有许多可能的方法，并且它强烈取决于之后您想要做什么。例如，您可以使用找到的图像创建一个新的边缘图像，并再次应用侵蚀和Hough，您可以使用基于傅里叶变换的方法，或者您可以通过某些任意阈值过滤线条（仅举几个例子）。我实现了最后一个（因为从概念上讲这是最容易做到的），以下是我的做法（尽管我完全不确定这是否是最佳方法）：

• 定义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)

- user2986898

---

哇，这正是我想做的事情。我打算自己试着实现它，如果遇到困难，我会参考你的代码。我想知道这种方法是否也适用于其他谜题，但我得等一下。谢谢！ - fferrin

很好！我在代码中添加了一些注释，以使其更易于理解，如果你遇到困难，请不要犹豫，随时问我。 - user2986898