我正在寻找算法,以便在给定包含填字游戏的图像的情况下:
可以假设填字游戏本身是规则的(即我对由某些程序生成并作为图像发布的填字游戏感兴趣,而不是扫描纸质填字游戏),并且我希望该程序在除图像位图之外不需要任何输入的情况下运行。
我可以想到一些暴力多通道的方法来完成这个任务(基本上使用imagemagick的hit-and-miss filter的变体,然后循环查找剩余的点),但我希望从实际了解图像处理的人那里获得更好的想法。
我正在寻找算法,以便在给定包含填字游戏的图像的情况下:
可以假设填字游戏本身是规则的(即我对由某些程序生成并作为图像发布的填字游戏感兴趣,而不是扫描纸质填字游戏),并且我希望该程序在除图像位图之外不需要任何输入的情况下运行。
我可以想到一些暴力多通道的方法来完成这个任务(基本上使用imagemagick的hit-and-miss filter的变体,然后循环查找剩余的点),但我希望从实际了解图像处理的人那里获得更好的想法。
在这里(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
然后,您可以从上到下扫描图像,找到足够长的水平黑线。一条线从黑色像素开始,以白色像素结束。其他像素表示它不是一条线。(这是为了筛选掉文本和按钮。)对于垂直线也是如此。
理想情况下,现在您已经有了填字游戏的线条。如果您的图像未裁剪到填字游戏,则可能会出现误报,例如按钮边框。要找到填字游戏的线条,请按长度排序并查找相同长度的最大连续块。这些应该是您的填字游戏线条,除非您有一些退化情况。
现在做一个嵌套的水平和垂直线循环,但跳过第一行。看一下交叉点向西北两三个像素的位置。如果像素是暗的,那就是一个空白。如果是亮的,那就是一个单元格。这种启发式方法似乎效果很好。这里说“暗”和“亮”,因为有些填字游戏在打印时使用灰色单元格来节省墨水,而有些单元格在屏幕截图中会被突出显示。/puzzles/sample/cryptic_demo/cryptic_demo_xml.js
,其中包含填字游戏的 XML 字符串,也作为奖励提供了提示。考虑另一种方法来完成这个任务。
在很多方面上,这与对象识别、计算机视觉相似。
一种方法是使用像openCV这样的框架,通过训练一些要检测的样本,可以检测出任何类似的结果。
(一个基于Viola-Jones算法的对象检测javascript库,也被openCV使用,我是HAAR.js的作者)
除此之外(或者类似的替代方案),还可以构建一个“视觉”模板来检测你想要的填字游戏(以尺度不变的方式)。
并扫描图像,寻找与模板的图像部分相关联的相关性(复杂度为O(N*M),其中N是图像的大小,M是模板的大小)。
由于填字游戏网格具有相对恒定的形状(特别是填字游戏编译器的固定输出),因此应该相对容易创建一个原型模板,并成功匹配(和对齐)检测到的区域以提取形状信息。