如何消除数独方块的凸性缺陷？

Question

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

我用OpenCV 2.3.1的Python API编程。

以下是我所做的：

1. 阅读图片
2. 找到轮廓
3. 选择面积最大的那个（也相当于正方形）。

4. 找到角点。

   例如，给出如下：

   

   （请注意，绿线与数独的真实边界正确重合，因此数独可以正确扭曲。检查下一张图片）

5. 将图像扭曲成一个完美的正方形

   例如图像：

   

6. 执行OCR（我使用了在Simple Digit Recognition OCR in OpenCV-Python中给出的方法）

而且这种方法很有效。

问题：

签出this image.

对该图像执行步骤4会得到以下结果：

画的红线是原来的轮廓线，是数独界的真实轮廓线。

绘制的绿线是近似轮廓线，它将是扭曲图像的轮廓线。

当然，在数独的上边缘，绿线和红线是有区别的。所以在扭曲的时候，我没有得到数独的原始边界。

我的问题：

如何在数独的正确边界（即红线）上扭曲图像，或者如何消除红线和绿线之间的差异？在OpenCV中有这个方法吗？

Answer 1

您可以尝试使用某种基于网格的任意扭曲建模。既然数独已经是一个网格，那就不难了。

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

Answer 2

我有一个可行的解决方案，但你必须自己将其翻译成OpenCV。它是用Mathematica写的。

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

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

下一步是找到数独区域，这样我就可以忽略（屏蔽）背景。为此，我使用连通分量分析，并选择凸面积最大的分量：

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

通过填充这张图片，我得到了一个数独网格的遮罩：

mask = FillingTransform[largestComponent]

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

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];

我再次使用连接组件分析从这些图像中提取网格线。网格线比数字长得多，所以我可以使用卡尺长度来选择网格线连接的组件。按位置排序，我得到图像中每个垂直/水平网格线的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]];

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

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}];

最后一步是定义通过这些点的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]

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

Answer 3

尼基的答案解决了我的问题，但他的答案是数学家的。所以我想我应该在这里给出它的OpenCV改编。但在实现之后，我可以看到OpenCV代码比nikie的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)

结果：

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()

结果：

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()

结果：

当然，这个不太好。

5。查找网格点

res = cv2.bitwise_and(closex,closey)

结果：

6个。修正缺陷

在这里，尼基做了一些插值，对此我不太了解。我找不到这个OpenCV对应的函数。（可能在那里，我不知道）。

看看这本书，它解释了如何使用SciPy，我不想使用它：Image transformation in 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))

但由此产生的质心不会被排序。请查看下图以查看他们的订单：

所以我们从左到右，从上到下分类。

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))

现在请看下面的顺序：

最后，我们应用转换并创建一个大小为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()

结果：

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

问候 方舟。