基于 OpenCV 及 Python 的数独问题识别与求解【100011308】

# 基于 OpenCV 及 Python 的数独问题识别与求解 本人平时比较喜欢玩数独，但比较难的数独经常一做就是半个多小时。这学期选了一门”计算机视觉”课，课程最后要做一个项目，正好我就想能不能写一个程序，用手机拍个照或者截个图，放进程序里跑一下，自动就把题目识别然后解出来了，and it was so. 先来看一个 [opencv](https://so.csdn.net/so/search?from=pc_blog_highlight&q=opencv) 里自带的数独图片：  程序的最终目的就是将这种图像转化为一个矩阵或者说二维数组，来要告诉计算机在 9x9 的方格中哪个位置有数字、数字是什么，就像下面的形式： ``` [[0 0 0 6 0 4 7 0 0] [7 0 6 0 0 0 0 0 9] [0 0 0 0 0 5 0 8 0] [0 7 0 0 2 0 0 9 3] [8 0 0 0 0 0 0 0 5] [4 3 0 0 1 0 0 7 0] [0 5 0 2 0 0 0 0 0] [3 0 0 0 0 0 2 0 8] [0 0 2 3 0 1 0 0 0]] ``` 在这个二维数组里，用 0 表示要填写的数字，用 1-9 表示识别出来的题目数字。 了解主要任务之后，下面就是具体的步骤了： 1. 图像预处理 2. 识别边框 3. 图像校正 4. 提取数字 5. 识别数字 6. 计算答案 这里使用的语言及版本如下，关于开发环境的配置可以参考本人[另一篇文章](http://blog.csdn.net/howlclat/article/details/78819760)： - Python 版本：**3.6.3** （Anaconda 3） - OpenCV 版本：**3.3.1** 第一篇文章主要讲解图像预处理部分，并给出使用 matplotlib 显示 OpenCV 图像的方法。 ## 图像预处理 首先是使用 cv2.imread() 函数读取原图片，然后使用 cv2.cvtColor() 灰度化，因为颜色信息不重要。之后是使用滤波算法进行降噪处理，因为滤波处理对于识别效果有很大影响。常用的有均值滤波、高斯滤波、中值滤波、双边滤波等，具体使用方法可以参考[这里](https://docs.opencv.org/master/d4/d13/tutorial_py_filtering.html)。本文使用高斯滤波及中值滤波，但是滤波参数不能适用于所有情况的图像， **必须根据图像尺寸和清晰度做调整** 。 ```python img_original = cv2.imread('./images/p1.png') img_gray = cv2.cvtColor(img_original, cv2.COLOR_BGR2GRAY) img_Blur = cv2.medianBlur(img_gray, 3) img_Blur = cv2.GaussianBlur(img_Blur, (3, 3), 0) ``` 可以看到，[Python](https://so.csdn.net/so/search?from=pc_blog_highlight&q=Python) 版本的 [OpenCV](https://so.csdn.net/so/search?from=pc_blog_highlight&q=OpenCV) 与 C++ 版本有个很大的区别，就是处理后的图像一般作为函数的返回值（之一），而 C++ 需要将原图像和处理后图像的地址作为参数传入，这是 [Python](https://so.csdn.net/so/search?from=pc_blog_highlight&q=Python) 中函数可以返回多个值的特点决定的。 此图片在预处理阶段要解决的主要问题是亮度不均衡，图像左下角比较暗，如果直接进行二值化效果较差，对滤波后图像取 100 作为阈值处理得到中间的图像，左下部分图像缺失；若进行自适应阈值操作，可以得到较好的效果，但左下部分线条亦有缺失：  参考 [stackflow](https://stackoverflow.com/questions/10196198/how-to-remove-convexity-defects-in-a-sudoku-square) 上一位大神的方法，以圆形作为结构化元素进行闭操作，将灰度图像除以闭操作后图像，再进行归一化。 ```python kernel = cv2.getStructuringElement(cv2.MORPH_ELLIPSE, (11, 11)) close = cv2.morphologyEx(img_Blur, cv2.MORPH_CLOSE, kernel) div = np.float32(img_Blur) / close img_brightness_adjust = np.uint8(cv2.normalize(div, div, 0, 255, cv2.NORM_MINMAX)) ``` 第一句使用 `cv2.getStructuringElement()` 获取结构元素，可以使用椭圆、矩形、十字形三种，这里使用椭圆。第二句使用 `cv2.morphologyEx()` 对原图使用刚才的结构元素进行闭操作。将灰度图像除以闭操作后图像，但要先转换成 float32 类型才能除，`/` 运算符相当于调用 numpy 中的 divide 函数，即点除，又即每个像素点分别相除，且只保留整数部分。最后将除的结果归一化到 [0, 255] 区间内，并转换回 无符号 8 位整数（uint8） 类型。 结果如下图，效果拔群：  下一步是二值化，[OpenCV](https://so.csdn.net/so/search?from=pc_blog_highlight&q=OpenCV) 中二值化有简单阈值、自适应阈值、Otsu’s 二值化等方法，可以参考[这里](https://docs.opencv.org/master/d7/d4d/tutorial_py_thresholding.html)。简单阈值是一种全局性的阈值，整个图像都和这个阈值比较。而自适应阈值可以看成一种局部性的阈值，通过规定一个区域大小，比较这个点与区域大小里面像素点的平均值（或者其他特征）的大小关系确定这个像素点是属于黑或者白。这里使用自适应阈值方法，代码如下： ```python img_thresh = cv2.adaptiveThreshold(img_brightness_adjust, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY_INV, 11, 7) ``` 使用 `cv2.adaptiveThreshold()` 函数， 其中 cv2.ADAPTIVE_THRESH_GAUSSIAN_C 代表在小区域内阈值选取为加权和，以高斯分布确定权重。cv2.THRESH_BINARY_INV 代表二值化的结果取反，为下一步形态学处理做准备。  ## 使用 matplotlib 显示 OpenCV 图像 Matplotlib 是 [Python](https://so.csdn.net/so/search?from=pc_blog_highlight&q=Python) 中最常用的可视化工具之一，可以非常方便地创建海量类型地 2D 图表和一些基本的 3D 图表。也可以方便地显示图像。 众所周知，OpenCV 中彩色图像的像素是以 Bule Green Red 为顺序的，也就是 BGR，而普通的图像则是采用 RGB 顺序，因此要在其他地方（如 Qt、matplotlib 中）使用 OpenCV 的彩色图像，就必须转换格式。 我将使用 matplotlib 显示 OpenCV 图像的功能写成了一个函数： ```python def plotImg(img, title=""): if img.ndim == 3: b, g, r = cv2.split(img) img = cv2.merge([r, g, b]) plt.imshow(img), plt.axis("off") else: plt.imshow(img, cmap='gray'), plt.axis("off") plt.title(title) plt.show() ``` 这里先判断输入图像是不是 3 维，即彩色图，是的话进行转换，不是的话作为灰度图显示。转换代码中分割再重新组合的方法，还可以使用 `img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)` 。注意如果灰度图不加 `cmap='gray'` 这个参数，会显示为“热度图”。 当然不要忘了开头加上： ```python import cv2 from matplotlib import pyplot as plt12 ``` matplotlib 还可以像 MATLAB 里一样方便的显示多个图像，例如这里并列显示两幅图像： ```python def plotImgs(img1, img2): if img1.ndim == 3: b, g, r = cv2.split(img1) img1 = cv2.merge([r, g, b]) plt.subplot(121), plt.imshow(img1), plt.axis("off") else: plt.subplot(121), plt.imshow(img1, cmap='gray'), plt.axis("off") if img2.ndim == 3: b, g, r = cv2.split(img2) img2 = cv2.merge([r, g, b]) plt.subplot(122), plt.imshow(img2), plt.axis("off") else: plt.subplot(122), plt.imshow(img2, cmap='gray'), plt.axis("off") plt.show() ``` 其中 `plt.subplot(121)` 就代表一行两列图像中的第一个。 编写计算机视觉程序时可以使用上述函数将中间过程图像显示出来，方便观察与调试。例如： ![](https://www.writebug.com/myres/static/uploads/2021/12/8/db63c3728b7175bebdb1816a1ce21ada.wri