使用 OpenCV 和 Python 查找数独网格

问题描述

我正在尝试使用 OpenCV 检测数独谜题中的网格，但我在最后一步遇到了麻烦(我猜).

我正在做的是:

• 降低图像
• 模糊它
• 应用高通滤波器(双边)
• 使用自适应阈值对图像进行阈值处理
• 一些膨胀和腐蚀

所有这些都给了我以下图像:

从现在开始，我需要检测网格，我找到了一些方法来做到这一点，但它们都没有给我足够强大的信心.

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

另一个是使用连接组件，这给了我最好的结果.我试图实施 RANSAC 作为获得正确质心的一种方式，但我没有得到很好的结果，也需要一段时间才能得到答案(一段时间"不到 2 秒，但后来我想用它实时视频).

知道如何做到这一点吗?我的意思是，我怎样才能丢弃错误的质心并开始解决数独问题?

解决方案

霍夫变换绝对是要走的路.事实上，网格检测是介绍此技术时最流行的示例之一(请参阅

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

What I'm doing is:

• Downsaple the image
• Blur it
• Applying a highpass filter (bilateral)
• Thresholding the image, using adaptive threshold
• Some dilations and erosions

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.

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).

I suggest the following steps:

• downsample
• blur
• apply Canny (you should have a good guess what the min/max possible length of a grid line from the used perspective)
• dilate the edge image (canny finds both border of a separator in the grid as different edges, dilation will make these merge again)
• erode (now we have too thick borders, hough would find too many lines)
• apply HoughLines
• merge the similar lines

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):

• defined an arbitrary threshold for the rho and theta values
• checked how many times an edge is in these thresholds of another one
• starting from the most similar one I started dropping out lines that are similar to it (this way we will keep the line that is in some sense the 'middle' one among a similar group)
• the remaining lines are the final candidates

See code, have fun:

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)