从图像中分类和提取填字游戏网格的算法

Question

鉴于包含填字游戏的图像,我正在寻找算法

1. 将图像裁剪为填字游戏
2. 区分常规和禁止的填字游戏
3. 提取网格大小和黑色方块/条的位置

填字游戏本身可以被认为是规则的(即我对由某些程序生成并作为图像发布的填字游戏感兴趣,而不是扫描基于纸张的填字游戏),我希望程序在不需要任何输入的情况下运行除了图像位图.

我可以想到一些蛮力的多通道方法来做到这一点(基本上使用imagemagick的命中过滤器的变体,然后在图像上循环寻找剩余的点)但我希望实际的人能有更好的想法了解图像处理.

Answer 1

这是一个非常广泛的问题,但我会尝试给你一些指示.这些是您需要采取的步骤:

1. 检测填字游戏的位置.
2. 检测填字游戏的网格.为此,您需要一些计算机视觉算法(例如霍夫线检测器).
3. 对于每个单元格,您需要查找它是否有字符.要做到这一点,你只需简单地分析细胞所具有的白色"量"
4. 对于包含角色的单元格,您需要识别它.为此,您需要一个OCR,我建议您使用Tesseract.
5. 创建自己的算法来解决填字游戏.你可以用它.

在这里,(1,2,3)你有一个数独解算器在Python中的一个例子.第一步是您的问题所共有的,因此您可以使用OpenCV来解决它:

import cv2
import numpy as np

#Load the Black and White image
img =  cv2.imread('sudoku.jpg')
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
gray = cv2.GaussianBlur(gray,(5,5),0)
thresh = cv2.adaptiveThreshold(gray,255,1,1,11,2)

#Detect the lines of the sudoku
contours, hierarchy = cv2.findContours(thresh, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)

#Detect the square of the Sudoku
biggest = None
max_area = 0
for i in contours:
        area = cv2.contourArea(i)
        if area > 100:
                peri = cv2.arcLength(i,True)
                approx = cv2.approxPolyDP(i,0.02*peri,True)
                if area > max_area and len(approx)==4:
                        biggest = approx
                        max_area = area

Answer 2

使用链接填字游戏的屏幕截图作为示例，我假设：

• 填字游戏网格清晰，即水平和垂直网格线以恒定的深色精确像素绘制，并且网格单元内没有噪音，
• 填字游戏是黑色或其他相对较深的颜色（“黑色”），白色或浅灰色（“白色”），
• 线索编号写在左上角，
• 填字游戏是矩形且规则的。

然后，您可以从上到下扫描图像以找到足够长度的水平黑线。一条线以黑色像素开始，以白色像素结束。其他像素表明它不是一条线。（这是为了清除文本和按钮。）对垂直线执行相同的操作。

理想情况下，您现在已经有了填字游戏线。如果您的图像未裁剪为填字游戏，则可能会出现误报，例如按钮边框。要找到填字游戏线，请按长度对它们进行排序，并查找相同长度的最大连续块。这些应该是你的填字游戏线，除非你有一些退化的情况

现在做一个水平线和垂直线的嵌套循环，但跳过第一行。查看线交点西北方向两到三个像素的位置。如果像素是暗的，那就是空白。如果有光，那就是细胞。这种启发式似乎很有效。我在这里说深色和浅色，因为一些填字游戏在打印时使用灰色单元格来节省墨水，并且某些单元格在屏幕截图中突出显示。

如果最后没有空格，那么你就有了一个禁止填字游戏。您可以通过检查单元格边框左侧和右侧的像素之一是否为黑色来找到这些条。

最后，提示：如果您想使用算法来查找填字游戏编译器生成的填字游戏中的单元格，请查看源代码。您将找到一个 Javascript 文件的链接/puzzles/sample/cryptic_demo/cryptic_demo_xml.js，其中包含 XML 字符串形式的填字游戏，这也为您提供了额外的线索。

填字游戏编译器的旧版本（例如用于Independent Cryptic 的编译器）将其数据隐藏在从小程序加载的文件中。该文件的格式是二进制的，但如果您知道原始数据，则不难阅读。