原文：
towardsdatascience.com/lets-learn-a-little-about-computer-vision-via-sudoku-836065c0f07b
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/26f9dc7c8d6cc131bca8f78174a1c026.png
图片由作者使用 HubSpot AI 制作
简介
这一切最初只是一个有趣的实验，为了编写另一个谜题求解器，类似于我最近写的Wordle求解器。数独是一个完美的计算机可解问题。它是一种简单的迭代方法，用于寻找唯一性。可能有很多例子，所以虽然我会谈谈我是如何解决这个谜题的，但我更想专注于我对这个游戏采取的机器学习（ML）和人工智能（AI）方法。我想，让我们把计算机视觉（CV）和光学字符识别（OCR）加进来，你可以上传一个谜题的图片，机器会读取它，然后从那里解决剩下的部分。这最终成为了一次极好的学习经历，我非常愿意带你一起走过！
到现在为止，我们可能都已经熟悉了数独是什么，那么让我们深入了解从图像中提取数字的过程！
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/06ef6d55aac95a70c92f4adf4af5b613.png
图片由作者提供
第一步：预处理图像
解决这个谜题的第一步是将上传的图片处理成适合 OCR 的格式。这涉及到计算机视觉中的几个关键步骤。对于前几个部分，我使用了最流行的基于 Python 的 CV 库，OpenCV，它拥有大量适合此类应用的工具，如车牌识别、扫描文档等。
在我们寻找数字之前的过程将涉及三个不同的步骤，以便将图像转换成最适合 CV 的格式。首先，将其转换为灰度，调整图像以使其更一致，最后将其转换为纯黑白。
转换为灰度
将图像转换为灰度简化了寻找重要特征（如边缘、形状和模式）的过程。这个过程通过将图像减少到单色通道（黑色到白色）而不是三个（RGB）来消除图像中的大量额外数据。
gray=cv2.cvtColor(image,cv2.COLOR_BGR2GRAY)应用高斯模糊
高斯模糊使图像更加平滑，使其更干净、更一致。它通过检测干扰边缘检测的微小细节来帮助 CV。想象一下在点之间寻找边缘；高斯模糊忽略了它们，专注于真实的边缘。
blurred=cv2.GaussianBlur(gray,(3,3),0)自适应阈值
自适应阈值是一种将图像转换为黑白的智能方法。自适应阈值确保清晰的网格线和数字。通过关注高对比度元素，它创建了一个对去除网格线和读取谜题等任务至关重要的二值图像。
# Apply adaptive thresholdingthresh=cv2.adaptiveThreshold(blurred,255,cv2.ADAPTIVE_THRESH_GAUSSIAN_C,cv2.THRESH_BINARY_INV,11,2)第二步：去除网格线
数独网格通常有粗黑的线条，这会混淆 OCR 系统。我使用 CV 中的所谓形态学操作来移除网格线。形态学操作将帮助我们移除小物体或窄连接，同时保留较大的结构元素。
结构元素是在形态学操作中使用的小矩阵，它们定义了分析的像素邻域。它们的形状和大小决定了检测或移除的特征。下面这个方法使用了一个水平内核来检测水平线，以及一个垂直内核来检测垂直线。
提示：如果您运行提供的代码，您可以调整值并查看它如何影响找到或找不到网格线。
horizontal_kernel=cv2.getStructuringElement(cv2.MORPH_RECT,(40,1))vertical_kernel=cv2.getStructuringElement(cv2.MORPH_RECT,(1,40))horizontal_lines=cv2.morphologyEx(thresh,cv2.MORPH_OPEN,horizontal_kernel,iterations=2)vertical_lines=cv2.morphologyEx(thresh,cv2.MORPH_OPEN,vertical_kernel,iterations=2)最后，我们将识别出的线条组合起来，并从图像中减去它们。
grid_lines=cv2.add(horizontal_lines,vertical_lines)grid_removed=cv2.subtract(thresh,grid_lines)到这一阶段，图像已经去除了网格线，只留下数字。让我们看看最终的图像以及我们的所有处理是如何帮助的。您可以看到网格线留下的一点点噪声；进一步优化参数可能有助于我们完全移除它们，但我发现这已经足够了。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/60da30c796940ee6723ede1e15cb6f41.png
作者提供的图片
第 3 步：提取单个单元格
在清理后的图像中，下一步是隔离 9×9 网格并提取每个单元格。这部分相当直接。我根据图像尺寸将网格划分为 81 个单元格。
cell_size=grid_size//9forrowinrange(9):forcolinrange(9):# Extract each cellx_start,y_start=col*cell_size,row*cell_size x_end,y_end=x_start+cell_size,y_start+cell_size cell=processed_image[y_start:y_end,x_start:x_end]接下来，我使用了一些其他的 CV 工具来为每个单元格添加一些额外的填充，并将它们全部调整大小以保持一致性。填充确保数字是孤立的，图像的大小确保字符识别的一致性。您可以想象，如果您在这里添加太多的边框然后调整图像大小，单元格中的数字最终会变得非常小；不要添加太多。
cell=cv2.copyMakeBorder(cell,5,5,5,5,cv2.BORDER_CONSTANT,value=0)cell=cv2.resize(cell,(50,50))第 4 步：使用 OCR 识别数字
识别数字是解决方案的核心。我最终使用了Tesseract OCR，它在这一步中发挥了关键作用。Tesseract 是一个开源的光学字符识别（OCR）引擎，它将视觉信息（文本的图像）转换为机器可读的字符。
我们可以为数独的特定用例进行微调：识别单个数字（1–9）在单个网格单元内。这是通过配置 Tesseract 并使用适当的参数来实现的：
custom_config=r" - oem 3 - psm 10 -c tessedit_char_whitelist=123456789"text=pytesseract.image_to_string(cell,config=custom_config).strip()每个准备好的单元格都传递给 Tesseract 进行字符识别。如果 Tesseract 对一个单元格返回不可识别的字符（或误将噪声解释为字符），则在数独网格中将该单元格标记为空（0）。
让我们来看看最终结果。如果我们检查每一行，我们可以看到它做得相当不错。不是完美，但也不差。前两行是完美的，但第三行缺少了 2 后面的 1。第六行也缺少了一个 1，第七行缺少了第一个 3。如果再稍作调整，我们应该能够做到完美。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/15193973c5eff2c7f024601f7f02ed5e.png
图片由作者提供
第 5 步：解决数独
正如我一开始说的，我会保持这个部分简洁，因为这个是一个非常常见的问题。我使用了一个回溯算法来解决这个谜题。这个算法尝试不同的可能性，并在遇到死胡同时“回溯”。它从搜索第一个空单元格开始，尝试在其中放置 1 到 9 的数字，并检查其是否有效。一个数字是有效的，如果它不与行、列或 3×3 框中现有的数字冲突。这个代码出奇地简单！
defsolve_sudoku(board):forrowinrange(9):forcolinrange(9):ifboard[row,col]==0:fornuminrange(1,10):ifis_valid(board,row,col,num):board[row,col]=numifsolve_sudoku(board):returnTrueboard[row,col]=0returnFalsereturnTrue部署
就像我所写的所有应用程序一样，我使用 Streamlit，因为它真的可以快速为它开发某种用户界面。它不是最优雅的，但它让我能够证明这个方法的有效性。
对于部署，我除了本地运行之外，还设置了几种不同的方法。这里实际上有一些有趣的事情。首先是 Docker 文件，用于将此部署到容器中，其次是将其部署到 Streamlit 的社区云。通常，我们只需在 requirements.txt 文件中添加任何 Python 依赖项即可，但我了解到，你还可以在 packages.txt 文件中列出任何 Linux 包，这些包将在你的应用程序部署时安装。这对于我的应用程序运行至关重要，因为 Tesseract OCR 不是一个 Python 包，而是一个 Linux 包。
如果你想亲自尝试，你可以在Streamlit 社区云上看到它，但我也会鼓励你查看代码并尝试自己运行它。所有内容都在GitHub上的 README 中进行了说明。
我的经验教训
预处理至关重要：适当的图像预处理可以显著提高 OCR 的准确性。这个过程需要很多迭代才能正确完成，甚至接近正确。到目前为止，这个模型有时并不完美。这让我非常感激专业解决方案必须投入多少努力才能达到这些高度准确的结果！
我尝试了三种不同的 OCR 方法，以找到最好的一个。我首先尝试了选择正确的 OCR/CV 技术：EasyOCR，这是一个简单的 Python 包，但它的性能只能捕捉到大约 60%的网格中的数字。然后我使用了上面的解决方案，即谷歌的Tesseract OCR，但这需要额外的安装，这导致了版本依赖问题。我还尝试了一个基于流行的手写数字预训练模型的Tensorflow CNN。这既过度又是最差的性能，因为我们没有使用手写数字！长话短说，针对你的用例进行实验是关键！
结论
使用计算机视觉和 OCR 构建数独求解器是一个具有挑战性但很有趣的项目。我想分享我对这个项目以及预处理和选择正确工具重要性的看法。虽然这个解决方案并不完美，但它展示了如何结合这些技术来自动化复杂任务。这个项目让我对图像处理和 OCR 有了很多了解，并让我意识到实验和迭代是创造有效解决方案的关键。我希望这能激励你探索类似的项目，并推动技术可能性的边界。
如果你喜欢阅读这样的故事，并希望支持我作为一位作家，考虑注册成为 Medium 会员。每月仅需 5 美元，即可无限制地访问数千篇文章。如果你使用我的链接注册，我将获得一小笔佣金，而无需额外费用。
