問題描述

我正在嘗試使用 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)

這篇關于使用 OpenCV 和 Python 查找數獨網格的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！