实时网络摄像头数独求解器
4.97/5 (309投票s)
通过网络摄像头解决数独：一个不错的计算机视觉应用
引言
此应用程序可能没有实际价值，但从学习的角度来看它非常棒。我想学习计算机视觉。计算机视觉是现代计算中最令人兴奋的领域之一。它也是一个困难的领域。对人脑来说简单而显而易见的事情，对计算机来说却非常困难。以目前的 IT 发展水平，许多事情仍然是不可能的。
此应用程序是使用低级 C++ 实现的，因为我想了解底层是如何工作的。如果您想开始一个计算机视觉应用程序，应该先使用现有的库（如 OpenCV）并从那里开始。您可以在 CodeProject 上找到一些教程。摄像头图像采集源代码来自 Vadim Gorbatenko（AviCap CodeProject）。
摄像头一次采集一张图像（一帧）。帧的流动会给人运动的错觉。下一张图片将解释此应用程序在摄像头帧内的作用。
图像下方的数字是我用 2.8GHz PC、摄像头设置为 640x480 像素测得的延迟（毫秒）。毫秒数显示了一些有趣的结果。例如，最慢的步骤是摄像头图像采集。100 毫秒意味着您将获得每秒 10 帧。这很差。摄像头通常很慢。您可以通过牺牲质量来提高速度。较低的分辨率可以提高摄像头速度，但图像质量可能会变得无法使用。另一个令人惊讶的是为什么转换为黑白如此之慢（12 毫秒）。另一方面，预计会很慢的 OCR 和求解器，却出奇地快——只有 7 毫秒。我将详细解释每个步骤，并展示如何改进。调用上述过程的源代码函数是 DoSomeImageProcessing()。
黑白转换如何工作
阈值处理
每个计算机视觉应用程序都始于从彩色（或灰度）图像转换为单色图像。将来，可能有一些有用的彩色感知算法，但今天，计算机视觉应用程序都是基于单色的（色盲的）。
将彩色转换为单色的最简单方法是“全局阈值”。假设一个像素的红色强度为 200，绿色为 200，蓝色为 200。由于强度范围是 0 到 255，因此该像素的光强度非常高。黑白之间的阈值是中间值：256/2=128。我们像素的平均强度是 (200+200+200)/3 = 200，高于阈值 128，因此它将被转换为白色。但这种简单的全局阈值在实际应用中并不有用。下一张图片显示了这一点。
为了获得良好的单色转换，我们将使用自适应阈值。自适应阈值不使用固定的阈值 128。相反，它为每个像素单独计算阈值。它读取周围 11x11 像素并对它们的强度求和。然后，求和的平均值将成为该像素的阈值。像素的公式是 threshold = sum/121，其中 121=11x11，sum 是周围强度的总和。如果中心像素的强度大于计算出的平均阈值，它将变为白色，否则变为黑色。在下一张图片中，我们正在对标记为红色的像素进行阈值处理。对所有其他像素都需要进行相同的计算。这就是为什么它如此慢的原因。程序需要读取 width*height*121 个像素。
积分图像
可以使用“积分图像”来优化这一点。积分图像是一个整数数组 int[image width*image height]。概念简单而强大。下图是一个例子。假设我们有一个 12x12 像素的图像，为了简单起见，所有强度值都设置为 1（在实际应用中，样本图像不会如此简单）。积分图像是从该像素的上方和左侧所有像素的总和。
下一张图片是一个关于积分图像如何发挥作用的例子。目标是计算灰色矩形中所有像素的总和。
公式是：sum=D-C-B+A。在我们的例子中：110-44-40+16 = 42（请尝试手动计数）。
我们不需要读取灰色矩形中的所有像素（它可能比这个例子大得多），只需要进行四次内存读取。这是一个显著的优化。但即使有了这个优化，转换为黑白仍然是最繁重的工作之一。
如何检测旋转
摄像头不是扫描仪。摄像头图像永远不会完美对齐。我们必须预计图像会有倾斜和旋转。为了检测旋转角度，我们将利用数独图像总是包含一些水平线和垂直线的这个事实。我们将检测图像中心附近最明显的（最强）线。最明显的线不受噪声影响。在单色图像中检测线的算法称为霍夫变换。
工作原理：您必须回忆学校里的直线公式：y = (x * cos(theta) + rho) / sin(theta)。
其中 theta 是线的角度，rho 是线与中心坐标 (0, 0) 的距离。
需要注意的是，每条线都可以用两个变量表示：theta 和 rho。
程序遍历单色图像中的每个像素。它会跳过白色像素。当遇到黑色像素时，它会尝试绘制所有通过该像素的所有可能的直线（虚拟直线）。它以 1 度的分辨率工作。这意味着每个像素都有 180 条虚拟直线穿过。为什么不是 360？因为角度 180-360 是角度 0-180 的复制。
有一个称为累加器的虚拟线数组。累加器是一个二维数组，其维度称为 theta 和 rho。与线公式中的 theta 和 rho 相同。每条虚拟直线代表累加器中的一个值。顺便说一句，这就是为什么这种方法被称为变换——它将线从 [x, y] 转换为 [theta, rho] 数组。每条虚拟直线都会增加累加器中的一个值，从而提高该虚拟直线是真实直线的可能性。这是一种投票。真实的线将获得多数票。
在所有像素及其 180 条虚拟线投票后，我们必须找到累加器中的最大值。（顺便说一句，为什么叫“累加器”？因为它累积选票。）获胜者是最明显（最强）的线。它的 theta 和 rho 维度可以与上述直线公式一起用来绘制它。
下一张图片是一个简单的例子。左边是一条三像素的线。您的眼睛可以看到一条从左上角到右下角的对角线，但这对计算机来说并不明显。
线检测如何工作：看上面的图片。霍夫变换算法跳过白色像素。每个黑色像素都会绘制四条穿过该像素的绿色虚拟直线（实际上是 180 条，但为了简单起见，这里只取四条）。第一个像素投票给直线 A、B、C 和 D。第二个像素投票给 E、B、G、H。第三个像素将投票给直线 I、B、K、L。请注意，直线 B 是所有三个黑色像素的共同线。它将获得 3 票。所有其他直线在累加器中只获得一票。因此，虚拟直线 B 必须是获胜者——真实直线。
下一张图片是一个更复杂的例子。左边是数独网格线的图像。右边是霍夫变换算法执行后的累加器数组。累加器中的明亮区域表示有很多投票。黑色表示在那里找到线的可能性很小。只关注最亮的点。每条线（用字母 A-U 标记）在累加器中都有一个明亮的点。您可以看到所有线都有轻微的旋转（约 6 度）。线 A 比线 K 旋转得少。因为图像不仅旋转了，而且还歪斜了。另外，如果您仔细看，您可以看到线 A 和 B 比 B 和 C 更近。您可以在左图和右图中都看到。
如果您想学习一般的视觉模式识别，理解霍夫变换很重要。通过投票产生真实直线的虚拟直线概念可以扩展到任何其他几何形状。例如圆形或矩形。直线是最简单的几何形状，所以也应该是最容易理解的。
如果您需要定位圆形，您将需要一个三维累加器，其维度为：x、y 和 r，其中 x、y 是坐标，r 是虚拟圆的半径。同样，这种累加器中最高（最亮）的投票就是图像中的真实圆形。
可以通过限制原始图像的区域和角度来优化霍夫变换的执行。我们不需要源图像中的所有线。要检测旋转角度，我们只需要图像中心附近的一条线。从该线的角度，我们假设所有其他线都以相同的角度旋转。
如何检测网格线
为了从网格中提取数字，我们需要精确地定位数独网格的开始和结束位置。这一部分对人脑来说是最简单的，但出乎意料的是，这对计算机来说是最困难的。为什么？为什么不使用上一节所述的霍夫变换检测到的线条？答案是因为有很多噪声。在大多数情况下，印刷在杂志或报纸上的数独网格并非孤立存在。周围有其他网格和线条会产生噪声。例如，看看这个
计算机很难分辨哪些是数独线条，哪些是周围的噪声。一个网格的末端在哪里，另一个网格的开头在哪里。
为了解决这个问题，我们不检测黑线。相反，我们将检测数独网格周围的白色区域。在下一张图片中，您可以看到如何实现。绿线 1 从未被数独网格中的黑色像素中断，而线 2 至少被中断了 10 次。这意味着线 1 更有可能在网格外部。通过计算任何水平线和垂直线被黑色像素中断的次数，我们可以得出结论，下一张图片中的绿线可能是数独网格的边界。足够简单——只需计算有多少从白色到黑色像素的转换在线下方。您不需要以 1 像素的分辨率运行这些线。每隔 3 个像素跳过一次即可加快速度。
在检测到边界后，我们将在这些边界内部运行霍夫变换，以精确检测网格线。到目前为止，我们还没有关心图像的倾斜和其他图像缺陷。只关心粗略的图像旋转。这一步将对此进行改进。通过在网格的有限区域上运行霍夫变换，我们将获得所有网格线的精确位置。这将有助于定位单元格中的数字。
待办事项：这一步可以改进，使其对噪声不那么敏感。我计划在下一版本中将上述方法与“倾斜的 Haar 类特征”结合起来，以检测网格的角点。我希望这能提高质量。问题可能在于 Haar 类特征适用于实心区域，但我们处理的是线条。线条占据的区域较小，因此亮矩形和暗矩形之间的差异不是很大。
我想知道还有其他方法可以检测 10x10 网格吗？
OCR 如何工作
在定位网格单元格内的斑块后，我们需要识别它们。我们有一个相对容易的任务。只有数字 1 到 9。不是整个字母表。
理论
每个识别算法都有这些步骤
- 确定特征
- 训练（学习步骤）
- 分类（运行时识别）
确定特征是应用程序设计的一部分。例如，特征是：数字 1 高而细。这使其与其他数字不同。数字 8 有两个圆圈，一个在另一个之上，等等。
特征定义可能是一项非常困难且不直观的任务，具体取决于要识别的内容。例如，您会使用哪些特征来识别某人的脸？不是任何脸。特定的脸。
区域特征
在此应用程序中，我们将使用*区域密度特征*。下一步（已提前完成）是通过提供数字 1-9 的训练图片来训练应用程序。您可以在*.\res*文件夹中看到这些图片。图片被调整为 5x5 像素，进行归一化，并存储在静态数组 OCRDigit::m_zon[10][5][5] 中，该数组看起来像
调整为 5x5 称为*分块*。上述数组称为*密度特征*。
*归一化*意味着这些 5x5 图片的密度值范围是 0 到 1024。没有归一化，区域将无法进行比较。
运行时发生的情况：当一个斑块从摄像头的图像中分离出来时，它会被调整为 5x5 像素。然后，将这 25 个像素逐个与九个训练过的密度特征数组进行比较。目标是找到像素强度之间的最小差异。差异越小，相似度越高。
这种方法对斑块大小不敏感，因为我们总是使用 5x5 的区域。它对旋转敏感，但我们已经知道了旋转是多少，并且可以进行调整。问题是它对位置偏移敏感，而且它不适用于负像（黑底白字）和真正旋转的图像（例如颠倒的）。
宽高比特征
数字 1 是一个特殊情况。因为它与 4 和 7 相似，所以上述方法不可靠。数字 1 的特定特征是：如果斑块的宽度小于其高度的 40%，则必须是数字 1。没有其他数字如此纤细。除了上述 25 个区域特征之外，这是我们检查的第 26 个特征。
对于分类步骤，我们使用 k 最近邻，k=1，这意味着我们只检测一个最近邻。
待办事项
对于下一个版本，可以通过引入其他特征来提高 OCR 质量。例如，数字 5、6 和 9 在使用区域特征时非常相似。为了区分它们，我们可以使用轮廓特征。轮廓特征是斑块边界框与斑块边缘之间的像素数量（距离）。
在下一张图片中，您可以看到 5 和 6 的右侧轮廓相似，但 9 的不同。5 和 9 的左侧轮廓相似，但 6 的不同。
还有其他可能的改进。专业的 OCR 引擎使用许多不同的特征。其中一些可能非常奇特。
修复 OCR 结果
OCR 完成后，将根据数独规则对结果进行逻辑校正。同一个数字不能出现在同一行、列或 3x3 块中。如果违反此规则，则 OCR 结果必须是错误的，需要进行更正。我们将用下一个可能的结果替换错误的结果。例如，在上面的图 12 中，结果是 5，因为 diff=5210，这是最小的。下一个可能的结果是 6。因为它具有下一个 diff=5508。因此，我们将结果 5 替换为 6。要决定两个冲突的数字哪个需要更正，我们取第一个 diff 和第二个 diff 之间差值最小的那个。源代码在 SudSolver::Fixit() 中。
数独求解器如何工作
有更多不同的方法来解决数独谜题。在这里，我们将使用三种简单的方法协同工作并互相帮助：裸单、隐藏单和穷举法。
方法 1. 穷举法
也称为回溯。这是程序员最常用的方法，无论有多难，它总能给出解决方案。但穷举法可能会非常慢，取决于所需的递归迭代次数。您永远无法提前知道需要多少迭代。穷举法是一种“试错”方法。它尝试所有空单元格中可能的 1-9 值的所有组合，直到所有单元格都填满一致的值。可能有多个解决方案，但我们只找到第一个就好。
第一步是准备候选数表——每个空单元格的可能值。下图解释了什么是候选数。它们是蓝色的。根据数独规则，第一个单元格只能包含 1、4 或 8。例如，3 不能在那里，因为它已经出现在下面两个单元格中。
穷举法将尝试组合所有小的蓝色数字，直到找到解决方案。看第一个单元格。算法将从值 1 开始，然后在第五个单元格，它将取数字 3，依此类推。如果选择的任何数字与其他值不一致，算法将尝试使用不同的数字。例如，从左数第六个单元格也以 3 作为候选数，但由于这与第五个单元格不一致，算法将尝试下一个候选数，即 4，依此类推。
如果解决方案需要很多迭代，穷举法可能会非常慢。例如，下图是穷举算法的“接近最坏情况”的谜题（来源：Wiki）。因为它尝试了所有可能的值，而正确的值是候选序列中的最后一个。幸运的是，有一个解决方案——您不应该从左上角单元格开始。任何其他初始单元格都能更快地获得解决方案。我们将使用此技巧来加快穷举法的速度。
还有其他可能的优化可以使穷举法更快，例如按递归序列从候选数最少的单元格排序到候选数最多的单元格。但我们不使用此类优化，因为它们只是部分优化。它们都有一个“最坏情况”，即它们不足以满足实时应用程序的速度。相反，我们将使用时间受限、三次重试、随机序列优化。技巧是如果回溯花费的时间太长就中止。然后随机重新排列递归序列，并从头开始重试。
方法 2. 裸单候选
下图解释了这种方法。如果一个单元格只有一个候选数，我们 100% 确定这是该单元格的有效值。设置该值后，下一步是重建候选数列表。候选数列表逐渐减少，直到所有候选数都变为单数。这对计算机来说是一个显而易见且简单的方法。但对人类来说并不那么明显。人类玩家无法将候选数列表记在脑子里。
方法 3. 隐藏单
下图解释了这种方法。看看数字 7。如果您是数独玩家，您可能会立刻看出数字 7 必须在那里。
即使这个单元格有四个候选数：4、7、8、9（参见图 15），诀窍是我们搜索 3x3 块、列或行内的唯一候选实例。此方法可能无法解决整个谜题，但与方法 2 配合得很好。当方法 2 耗尽单个候选数时，方法 3 可以提供帮助。
整合所有方法
对于摄像头求解器来说，速度非常重要。穷举法不够快，无法满足我们的应用程序。因此，我们将结合使用这三种方法。方法 2 和 3 非常快，但只能解决简单的谜题。由于我们从嘈杂的摄像头获取输入，因此我们经常会遇到非常难甚至无法解决的谜题（由于 OCR 的不可靠性）。我们必须假设谜题通常会非常难解决。即使原始谜题的设计是一个简单的谜题。
如何阅读下一个图：左侧是快速方法 2 和 3。只有当它们不成功时，我们才会跳转到右侧，这是慢速的穷举法。即使方法 2 和 3 无法解决，它们在解决至少一些单元格方面也做得很好，从而减少了穷举法的任务。
只有当方法 2 和 3 无法解决时，程序才会落入穷举法。即使如此，穷举法也限制在 600,000 次迭代，以使算法保持时间受限。将有三次重试，之后程序将放弃。每次重试之间，递归序列会随机重新排列，希望新的序列能带来快速的解决方案。如果穷举法在三次重试后失败，并非完全失败。我们可能在下一个摄像机帧中运气更好。上述图是在 SudSolver::SolveMe() 中实现的。
缓冲解决方案
找到解决方案后，我们在类型为 SudResultVoter 的数组中跟踪最近的解决方案。需要缓冲是因为 OCR 的可靠性不是 100%，我们时不时会得到错误的解决方案。为了避免解决方案的波动，我们将始终显示最近找到的最强解决方案（确切地说，是最近 12 个解决方案中的一个）。数组会不时重置，忘记旧的解决方案，并为当前聚焦的新数独提供机会。
视频
待办事项
未来的一些想法
- 将程序重写为 Android。我想知道它在智能手机上会如何运行。
- 并行化一些函数以使用多核处理器。PC 通常至少有双核处理器。通常，并行任务用于提高性能。但在这里，我们不需要更高的速度，我们需要更高的质量。这个想法是，并行任务应该对相同的图像帧执行相同的操作，但设置不同。在所有任务完成后，我们将选择结果最好的任务，而放弃其他的。
历史
- 2011 年 8 月 8 日 - 首次发布