如何消除数独方块的凹凸缺陷?

我正在做一个有趣的项目:使用OpenCV从输入图像中解决数独(如谷歌护目镜等)。我已经完成了任务，但在最后我发现了一个小问题，我来这里。

我使用OpenCV 2.3.1的Python API进行编程。

以下是我所做的:

  1. 阅读图片
  2. 找到轮廓
  3. 选择面积最大的一个，(也有点相当于正方形)。

  4. 找到角点。

    例如:

    enter image description here

    (注意这里的绿线正确地与数独的真实边界重合，因此数独可以正确地弯曲。检查下一张图片)

  5. 将图像扭曲为完全正方形

    如图片:

    enter image description here

  6. 执行OCR(为此我使用了我在 OpenCV-Python中的简单数字识别OCR )

这个方法效果很好。

问题:

查看这张图片。

在这张图片上执行第4步的结果如下所示:

enter image description here

所绘制的红线为原轮廓线，即数独边界的真实轮廓线。

所画的绿色线是近似的轮廓线，这将是扭曲图像的轮廓线。

当然，数独游戏上边缘的绿线和红线是有区别的。所以在扭曲的过程中，我并没有得到数独游戏的原始边界。

我的问题:

我如何在数独的正确边界上扭曲图像，即红线或我如何删除红线和绿线之间的差异?OpenCV中有这种方法吗?

43411 次浏览
小开

您可以尝试使用某种基于网格的任意扭曲建模。由于数独已经是一个网格，这应该不会太难。

所以你可以尝试检测每个3x3子区域的边界，然后分别扭曲每个区域。如果探测成功，它会给你一个更好的近似。

小开
最佳答案

我有一个可行的解决方案，但你得自己把它翻译成OpenCV。它写在Mathematica上。

第一步是调整图像中的亮度，通过将每个像素与关闭操作的结果分开:

src = ColorConvert[Import["http://davemark.com/images/sudoku.jpg"], "Grayscale"];
white = Closing[src, DiskMatrix[5]];
srcAdjusted = Image[ImageData[src]/ImageData[white]]

enter image description here

下一步是找到数独区域，所以我可以忽略(掩码)背景。为此，我使用连通分量分析，并选择凸面积最大的分量:

components =
ComponentMeasurements[
ColorNegate@Binarize[srcAdjusted], {"ConvexArea", "Mask"}][[All,
2]];
largestComponent = Image[SortBy[components, First][[-1, 2]]]

enter image description here

通过填充这张图片，我得到了一个数独网格的蒙版:

mask = FillingTransform[largestComponent]

enter image description here

现在，我可以使用二阶导数滤波器在两个独立的图像中找到垂直线和水平线:

lY = ImageMultiply[MorphologicalBinarize[GaussianFilter[srcAdjusted, 3, {2, 0}], {0.02, 0.05}], mask];
lX = ImageMultiply[MorphologicalBinarize[GaussianFilter[srcAdjusted, 3, {0, 2}], {0.02, 0.05}], mask];

enter image description here

我再次使用连接分量分析从这些图像中提取网格线。网格线比数字长得多，因此我可以使用卡尺长度只选择网格线连接的组件。按位置排序，我得到了图像中每个垂直/水平网格线的2x10掩码图像:

verticalGridLineMasks =
SortBy[ComponentMeasurements[
lX, {"CaliperLength", "Centroid", "Mask"}, # > 100 &][[All,
2]], #[[2, 1]] &][[All, 3]];
horizontalGridLineMasks =
SortBy[ComponentMeasurements[
lY, {"CaliperLength", "Centroid", "Mask"}, # > 100 &][[All,
2]], #[[2, 2]] &][[All, 3]];

enter image description here

接下来，我取每对垂直/水平网格线，展开它们，计算逐像素的交集，并计算结果的中心。这些点是网格线的交点:

centerOfGravity[l_] :=
ComponentMeasurements[Image[l], "Centroid"][[1, 2]]
gridCenters =
Table[centerOfGravity[
ImageData[Dilation[Image[h], DiskMatrix[2]]]*
ImageData[Dilation[Image[v], DiskMatrix[2]]]], {h,
horizontalGridLineMasks}, {v, verticalGridLineMasks}];

enter image description here

最后一步是定义两个通过这些点进行X/Y映射的插值函数，并使用这些函数对图像进行转换:

fnX = ListInterpolation[gridCenters[[All, All, 1]]];
fnY = ListInterpolation[gridCenters[[All, All, 2]]];
transformed =
ImageTransformation[
srcAdjusted, {fnX @@ Reverse[#], fnY @@ Reverse[#]} &, {9*50, 9*50},
PlotRange -> \{\{1, 10}, {1, 10}}, DataRange -> Full]

enter image description here

所有的操作都是基本的图像处理功能，所以这在OpenCV中也应该是可能的。基于样条的图像转换可能比较困难，但我认为你并不真的需要它。在每个单元格上使用您现在使用的透视图转换可能会得到足够好的结果。

小开

尼基的答案解决了我的问题，但他的答案在《数学》杂志上。所以我想我应该在这里给出它的OpenCV改编。但在实现之后，我可以看到OpenCV代码比尼基的mathematica代码大得多。而且，我在OpenCV中找不到由nikie完成的插值方法(尽管可以使用scipy完成，我会在时间到来时告诉它)。

1. 图像预处理(关闭操作)

import cv2
import numpy as np


img = cv2.imread('dave.jpg')
img = cv2.GaussianBlur(img,(5,5),0)
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
mask = np.zeros((gray.shape),np.uint8)
kernel1 = cv2.getStructuringElement(cv2.MORPH_ELLIPSE,(11,11))


close = cv2.morphologyEx(gray,cv2.MORPH_CLOSE,kernel1)
div = np.float32(gray)/(close)
res = np.uint8(cv2.normalize(div,div,0,255,cv2.NORM_MINMAX))
res2 = cv2.cvtColor(res,cv2.COLOR_GRAY2BGR)

结果:

关闭结果

2. 寻找数独方块和创建掩码图像

thresh = cv2.adaptiveThreshold(res,255,0,1,19,2)
contour,hier = cv2.findContours(thresh,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)


max_area = 0
best_cnt = None
for cnt in contour:
area = cv2.contourArea(cnt)
if area > 1000:
if area > max_area:
max_area = area
best_cnt = cnt


cv2.drawContours(mask,[best_cnt],0,255,-1)
cv2.drawContours(mask,[best_cnt],0,0,2)


res = cv2.bitwise_and(res,mask)

结果:

enter image description here

3.寻找垂直线

kernelx = cv2.getStructuringElement(cv2.MORPH_RECT,(2,10))


dx = cv2.Sobel(res,cv2.CV_16S,1,0)
dx = cv2.convertScaleAbs(dx)
cv2.normalize(dx,dx,0,255,cv2.NORM_MINMAX)
ret,close = cv2.threshold(dx,0,255,cv2.THRESH_BINARY+cv2.THRESH_OTSU)
close = cv2.morphologyEx(close,cv2.MORPH_DILATE,kernelx,iterations = 1)


contour, hier = cv2.findContours(close,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)
for cnt in contour:
x,y,w,h = cv2.boundingRect(cnt)
if h/w > 5:
cv2.drawContours(close,[cnt],0,255,-1)
else:
cv2.drawContours(close,[cnt],0,0,-1)
close = cv2.morphologyEx(close,cv2.MORPH_CLOSE,None,iterations = 2)
closex = close.copy()

结果:

enter image description here

4. 寻找水平线

kernely = cv2.getStructuringElement(cv2.MORPH_RECT,(10,2))
dy = cv2.Sobel(res,cv2.CV_16S,0,2)
dy = cv2.convertScaleAbs(dy)
cv2.normalize(dy,dy,0,255,cv2.NORM_MINMAX)
ret,close = cv2.threshold(dy,0,255,cv2.THRESH_BINARY+cv2.THRESH_OTSU)
close = cv2.morphologyEx(close,cv2.MORPH_DILATE,kernely)


contour, hier = cv2.findContours(close,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)
for cnt in contour:
x,y,w,h = cv2.boundingRect(cnt)
if w/h > 5:
cv2.drawContours(close,[cnt],0,255,-1)
else:
cv2.drawContours(close,[cnt],0,0,-1)


close = cv2.morphologyEx(close,cv2.MORPH_DILATE,None,iterations = 2)
closey = close.copy()

结果:

enter image description here

当然，这个不太好。

5. 寻找网格点

res = cv2.bitwise_and(closex,closey)

结果:

enter image description here

6. 纠正缺陷

这里，妮基做了一些插值，关于这个我不太了解。我找不到这个OpenCV对应的函数。(也许它就在那里，我不知道)。

看看这个SOF，它解释了如何使用SciPy来做到这一点，我不想使用:OpenCV中的图像变换

所以，在这里我取了每个子正方形的4个角，并应用翘曲透视每个角。

首先，我们找到质心。

contour, hier = cv2.findContours(res,cv2.RETR_LIST,cv2.CHAIN_APPROX_SIMPLE)
centroids = []
for cnt in contour:
mom = cv2.moments(cnt)
(x,y) = int(mom['m10']/mom['m00']), int(mom['m01']/mom['m00'])
cv2.circle(img,(x,y),4,(0,255,0),-1)
centroids.append((x,y))

但是得到的质心不会被排序。看看下面的图片，看看他们的顺序:

enter image description here

我们从左到右，从上到下排序。

centroids = np.array(centroids,dtype = np.float32)
c = centroids.reshape((100,2))
c2 = c[np.argsort(c[:,1])]


b = np.vstack([c2[i*10:(i+1)*10][np.argsort(c2[i*10:(i+1)*10,0])] for i in xrange(10)])
bm = b.reshape((10,10,2))

下面是他们的顺序:

enter image description here

最后，我们应用转换并创建一个大小为450x450的新图像。

output = np.zeros((450,450,3),np.uint8)
for i,j in enumerate(b):
ri = i/10
ci = i%10
if ci != 9 and ri!=9:
src = bm[ri:ri+2, ci:ci+2 , :].reshape((4,2))
dst = np.array( [ [ci*50,ri*50],[(ci+1)*50-1,ri*50],[ci*50,(ri+1)*50-1],[(ci+1)*50-1,(ri+1)*50-1] ], np.float32)
retval = cv2.getPerspectiveTransform(src,dst)
warp = cv2.warpPerspective(res2,retval,(450,450))
output[ri*50:(ri+1)*50-1 , ci*50:(ci+1)*50-1] = warp[ri*50:(ri+1)*50-1 , ci*50:(ci+1)*50-1].copy()

结果:

enter image description here

结果与nikie的几乎相同，但代码长度较大。也许有更好的方法，但在那之前，这是可行的。

< p >的问候 柜。< / p >
小开

我想补充的是，上述方法只适用于数独板直立时，否则高度/宽度(反之亦然)比值测试很可能会失败，你将无法检测到数独的边缘。(我还想补充一点，如果直线不垂直于图像边界，sobel操作(dx和dy)仍然有效，因为直线仍然有关于两个轴的边。)

为了能够检测直线，你应该进行轮廓线或像素级分析，如contourArea/boundingRectArea，左上和右下的点…

编辑:我试图通过线性回归和检查误差来检查一组轮廓是否构成一条直线。然而，当直线斜率太大(即>1000)或非常接近0时，线性回归表现不佳。因此，在线性回归之前应用上面的比率检验(在得到最多好评的答案中)是合乎逻辑的，对我来说确实有效。

小开

为了移除未被感染的角落，我应用了gamma修正，gamma值为0.8。

Before gamma correction

红色圆圈表示缺失的角落。

After gamma correction

代码是:

gamma = 0.8
invGamma = 1/gamma
table = np.array([((i / 255.0) ** invGamma) * 255
for i in np.arange(0, 256)]).astype("uint8")
cv2.LUT(img, table, img)

这是在阿比德·拉赫曼的答案之外，如果一些角点缺失。

小开

我认为这是一个伟大的帖子，ARK的一个伟大的解决方案;写得很好，解释得很清楚。

我当时也在研究一个类似的问题，并建立了整个系统。有一些变化(即xrange到range, cv2.findContours中的参数)，但这应该是开箱即用的(Python 3.5, Anaconda)。

这是上述元素的编译，添加了一些缺失的代码(即，标记点)。

'''


https://stackoverflow.com/questions/10196198/how-to-remove-convexity-defects-in-a-sudoku-square


'''


import cv2
import numpy as np


img = cv2.imread('test.png')


winname="raw image"
cv2.namedWindow(winname)
cv2.imshow(winname, img)
cv2.moveWindow(winname, 100,100)




img = cv2.GaussianBlur(img,(5,5),0)


winname="blurred"
cv2.namedWindow(winname)
cv2.imshow(winname, img)
cv2.moveWindow(winname, 100,150)


gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
mask = np.zeros((gray.shape),np.uint8)
kernel1 = cv2.getStructuringElement(cv2.MORPH_ELLIPSE,(11,11))


winname="gray"
cv2.namedWindow(winname)
cv2.imshow(winname, gray)
cv2.moveWindow(winname, 100,200)


close = cv2.morphologyEx(gray,cv2.MORPH_CLOSE,kernel1)
div = np.float32(gray)/(close)
res = np.uint8(cv2.normalize(div,div,0,255,cv2.NORM_MINMAX))
res2 = cv2.cvtColor(res,cv2.COLOR_GRAY2BGR)


winname="res2"
cv2.namedWindow(winname)
cv2.imshow(winname, res2)
cv2.moveWindow(winname, 100,250)


#find elements
thresh = cv2.adaptiveThreshold(res,255,0,1,19,2)
img_c, contour,hier = cv2.findContours(thresh,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)


max_area = 0
best_cnt = None
for cnt in contour:
area = cv2.contourArea(cnt)
if area > 1000:
if area > max_area:
max_area = area
best_cnt = cnt


cv2.drawContours(mask,[best_cnt],0,255,-1)
cv2.drawContours(mask,[best_cnt],0,0,2)


res = cv2.bitwise_and(res,mask)


winname="puzzle only"
cv2.namedWindow(winname)
cv2.imshow(winname, res)
cv2.moveWindow(winname, 100,300)


# vertical lines
kernelx = cv2.getStructuringElement(cv2.MORPH_RECT,(2,10))


dx = cv2.Sobel(res,cv2.CV_16S,1,0)
dx = cv2.convertScaleAbs(dx)
cv2.normalize(dx,dx,0,255,cv2.NORM_MINMAX)
ret,close = cv2.threshold(dx,0,255,cv2.THRESH_BINARY+cv2.THRESH_OTSU)
close = cv2.morphologyEx(close,cv2.MORPH_DILATE,kernelx,iterations = 1)


img_d, contour, hier = cv2.findContours(close,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)
for cnt in contour:
x,y,w,h = cv2.boundingRect(cnt)
if h/w > 5:
cv2.drawContours(close,[cnt],0,255,-1)
else:
cv2.drawContours(close,[cnt],0,0,-1)
close = cv2.morphologyEx(close,cv2.MORPH_CLOSE,None,iterations = 2)
closex = close.copy()


winname="vertical lines"
cv2.namedWindow(winname)
cv2.imshow(winname, img_d)
cv2.moveWindow(winname, 100,350)


# find horizontal lines
kernely = cv2.getStructuringElement(cv2.MORPH_RECT,(10,2))
dy = cv2.Sobel(res,cv2.CV_16S,0,2)
dy = cv2.convertScaleAbs(dy)
cv2.normalize(dy,dy,0,255,cv2.NORM_MINMAX)
ret,close = cv2.threshold(dy,0,255,cv2.THRESH_BINARY+cv2.THRESH_OTSU)
close = cv2.morphologyEx(close,cv2.MORPH_DILATE,kernely)


img_e, contour, hier = cv2.findContours(close,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)


for cnt in contour:
x,y,w,h = cv2.boundingRect(cnt)
if w/h > 5:
cv2.drawContours(close,[cnt],0,255,-1)
else:
cv2.drawContours(close,[cnt],0,0,-1)


close = cv2.morphologyEx(close,cv2.MORPH_DILATE,None,iterations = 2)
closey = close.copy()


winname="horizontal lines"
cv2.namedWindow(winname)
cv2.imshow(winname, img_e)
cv2.moveWindow(winname, 100,400)




# intersection of these two gives dots
res = cv2.bitwise_and(closex,closey)


winname="intersections"
cv2.namedWindow(winname)
cv2.imshow(winname, res)
cv2.moveWindow(winname, 100,450)


# text blue
textcolor=(0,255,0)
# points green
pointcolor=(255,0,0)


# find centroids and sort
img_f, contour, hier = cv2.findContours(res,cv2.RETR_LIST,cv2.CHAIN_APPROX_SIMPLE)
centroids = []
for cnt in contour:
mom = cv2.moments(cnt)
(x,y) = int(mom['m10']/mom['m00']), int(mom['m01']/mom['m00'])
cv2.circle(img,(x,y),4,(0,255,0),-1)
centroids.append((x,y))


# sorting
centroids = np.array(centroids,dtype = np.float32)
c = centroids.reshape((100,2))
c2 = c[np.argsort(c[:,1])]


b = np.vstack([c2[i*10:(i+1)*10][np.argsort(c2[i*10:(i+1)*10,0])] for i in range(10)])
bm = b.reshape((10,10,2))


# make copy
labeled_in_order=res2.copy()


for index, pt in enumerate(b):
cv2.putText(labeled_in_order,str(index),tuple(pt),cv2.FONT_HERSHEY_DUPLEX, 0.75, textcolor)
cv2.circle(labeled_in_order, tuple(pt), 5, pointcolor)


winname="labeled in order"
cv2.namedWindow(winname)
cv2.imshow(winname, labeled_in_order)
cv2.moveWindow(winname, 100,500)


# create final


output = np.zeros((450,450,3),np.uint8)
for i,j in enumerate(b):
ri = int(i/10) # row index
ci = i%10 # column index
if ci != 9 and ri!=9:
src = bm[ri:ri+2, ci:ci+2 , :].reshape((4,2))
dst = np.array( [ [ci*50,ri*50],[(ci+1)*50-1,ri*50],[ci*50,(ri+1)*50-1],[(ci+1)*50-1,(ri+1)*50-1] ], np.float32)
retval = cv2.getPerspectiveTransform(src,dst)
warp = cv2.warpPerspective(res2,retval,(450,450))
output[ri*50:(ri+1)*50-1 , ci*50:(ci+1)*50-1] = warp[ri*50:(ri+1)*50-1 , ci*50:(ci+1)*50-1].copy()


winname="final"
cv2.namedWindow(winname)
cv2.imshow(winname, output)
cv2.moveWindow(winname, 600,100)


cv2.waitKey(0)
cv2.destroyAllWindows()

提交答案