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

Question

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

algorithmimage-processingcomputer-vision

5

我正在寻找算法，以便在给定包含填字游戏的图像的情况下：

裁剪图像以仅显示填字游戏
区分常规和有障碍的填字游戏
提取网格大小以及黑色方块/障碍的位置

可以假设填字游戏本身是规则的（即我对由某些程序生成并作为图像发布的填字游戏感兴趣，而不是扫描纸质填字游戏），并且我希望该程序在除图像位图之外不需要任何输入的情况下运行。

我可以想到一些暴力多通道的方法来完成这个任务（基本上使用imagemagick的hit-and-miss filter的变体，然后循环查找剩余的点），但我希望从实际了解图像处理的人那里获得更好的想法。

- Martin DeMello

请查看“常规”和“带杠”的链接。 - Martin DeMello

4个回答

2

使用链接的填字游戏截图作为示例，我假设以下内容：

填字游戏网格清晰，即水平和垂直网格线以恒定的深色精确绘制，且网格单元内没有噪点。
填字游戏为黑色或其他相对较暗的颜色（“黑色”），在白色或浅灰色（“白色”）上显示。
提示数字写在左上角。
填字游戏为矩形和规则的。

然后，您可以从上到下扫描图像，找到足够长的水平黑线。一条线从黑色像素开始，以白色像素结束。其他像素表示它不是一条线。（这是为了筛选掉文本和按钮。）对于垂直线也是如此。

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

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

如果没有空白，则得到了一个带条纹的填字游戏。您可以通过检查单元格边框左右的像素之一是否为黑色来找到条纹。

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

交叉字谜生成器的旧版本，例如用于独立密码的版本，将它们的数据隐藏在从小应用程序加载的文件中。该文件的格式是二进制的，但如果您知道原始数据，阅读起来并不太难。

- M Oehm

谢谢，那看起来是一个不错、简单明了的过程。关于填字游戏编译器的提示也很有用；我主要是考虑从PDF中提取图像中的填字游戏，但我会在以后添加一个选项，从网页上读取它们。 - Martin DeMello

1

尝试使用hough变换查找正方形，获取正方形后，使用直方图检查其灰度值是否为深色或白色，并使用阈值进行判定。

- Vikram Bhat

1

考虑另一种方法来完成这个任务。

在很多方面上，这与对象识别、计算机视觉相似。

一种方法是使用像openCV这样的框架，通过训练一些要检测的样本，可以检测出任何类似的结果。

（一个基于Viola-Jones算法的对象检测javascript库，也被openCV使用，我是HAAR.js的作者）

除此之外（或者类似的替代方案），还可以构建一个“视觉”模板来检测你想要的填字游戏（以尺度不变的方式）。

并扫描图像，寻找与模板的图像部分相关联的相关性（复杂度为O（N*M），其中N是图像的大小，M是模板的大小）。

由于填字游戏网格具有相对恒定的形状（特别是填字游戏编译器的固定输出），因此应该相对容易创建一个原型模板，并成功匹配（和对齐）检测到的区域以提取形状信息。

- Nikos M.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- phyrox · Accepted Answer

这是一个非常广泛的问题，但我会尝试给您一些指导意见。您需要采取以下步骤：

1. 检测填字游戏的位置。 2. 检测填字游戏的网格。为此，您需要一些计算机视觉算法（例如Hough线检测器）。 3. 对于每个单元格，您需要找出它是否有字符。为此，您只需分析单元格中白色颜色的“数量”即可。 4. 对于包含字符的单元格，您需要识别它。为此，您需要一个OCR，我建议您使用Tesseract。 5. 创建您自己的算法来解决填字游戏。您可以使用this。

在这里（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