英语原文共 5 页，剩余内容已隐藏，支付完成后下载完整资料
基于FPGA和MATLAB的数独识别与数独破解
Snigdha Kamal，Simarpreet Singh Chawla，Nidhi Goel
德里理工大学电子与通信工程系（原DCE）
新德里 - 110042，印度
snigdhakamal17@gmail.com，chawla.simarpreet@gmail.com，nidhi.iitr@gmail.com
摘要 在本文中，我们提出了一种使用FPGA和基于视觉的技术对数独谜题中的数字进行检测识别，并随后利用暴力解决数独。该系统可识别从数码相机捕获的任何数独拼图，并且在采用适当的预处理算法（包括自适应阈值处理，霍夫变换和几何变换）之后，使用光学字符识别（OCR）识别数字，并基于它们的像素位置图像，将它们存储在9*9矩阵中的相应位置，然后进一步寄存到FPGA以生成解。随后，FPGA使用9*9矩阵为存储方式并在存储器中的每个行，列和块构建位图。用于解决数独的算法使用暴力算法，它以行方式填充空单元格，并在遇到不能分配数字的单元格时回溯。 该系统已经过各种数独谜题的测试，并被证明能够处理由非均匀照明，背景噪音和平移引起的问题，并且能够以353.61 MHz的最大频率工作，同时消耗314个切片，396个LUT和0.253瓦的功率。
索引术语 - 数独，图像处理，光学字符识别，FPGA，暴力算法
一、介绍
数独是一个非常容易上瘾的基于逻辑的难题，涉及组合和数字定位。这个经典的游戏往一个9*9网格中的部分填充1到9的数字。目标是填补这个难题，使得每一列，每行和3 3个子网格包含数字1到9而不重复或消除。 在开始填写的条目数量越少，解决这个难题就越困难。 此外，一个好的数独谜题只有一个解决方案。
数独检测器和求解器已经通过采用基于遗传算法的专用硬件[1]-[6]或模拟退火法或使用基于视觉的系统[7][8]来实现。由于硬件的固有速度和执行算法的专用逻辑电路，数独求解器的硬件实现极大地加快了求解过程并减少了生成求解所需的时间。 此外，解决数独也可以被视为二进制满意度，图着色或精准覆盖问题。
在本文中，我们提出了一种基于分区的方法，其中对谜题和数字使用图像处理技术进行了识别并以9*9矩阵存储的识别号码进行软件处理，然后将其转发至现场可编程门阵列（FPGA）。 因此，我们的系统结合了硬件和软件的优势来生成最佳解决方案
二、相关工作
数独是一个数字拼图游戏，在2005年获得了全球的关注。从那以后，已经有很多关于使用软件或硬件程序来检测和解决数独游戏的实现。 硬件实现比软件实现更受欢迎，因为硬件实现速度更快，并提供系统的实时分析。
文献[1]-[6]已经在FPGA上实现了数独解算器的体系结构。Thirer 在[1]中提出在FPGA上使用遗传算法实现一个数独求解器，并在染色体定义，变异和交叉相位，适应函数计算和群体定义等方面进行了一些改编。Malakonakis等人在[2]提出了一种基于模拟退火法的数独求解器，该方法能够求15*15*15*15阶的数独拼图。Gonza#39;lez et al.[3]使用分支定界技术和一些启发式技术，如隐藏的四重奏，隐藏的三重奏，隐藏的对，隐藏的单曲和单曲，实现了他们在Virtex-II Pro（硬件）和软件上解决数独的初始特定处理器。 Skliarova等人在[4]分析了三种不同的技术来解决Spartan-3E和Dittrich等人的数独问题。文献[5]通过使用关联矩阵将它作为精确覆盖问题来解决数独难题。文献[6]采用暴力破解方法解决FPGA上的数独拼图问题。
许多文献也利用图像处理或熵最小化的概念来识别或解决数独谜题[7]，[8]。 Wicht和Hennebert [7]通过使用Hough变换和Deep Belief Network（DBN）来检测数独拼图来分别检测网格线和识别字符。Simha等人在[8]分别使用模板匹配和回溯算法检测并解决数独拼图。
许多文献提出并采用了许多算法来解决数独谜题[9]-[12]。Wu和Lin[9]介绍一种新的算法，称为不相交的最小集（DMU），能够降低由单核心的计算机由128.67个因素解决数独谜题的时间，[10]采用改进的人造蜂群算法来解决数独谜题。[11]中一种基于遗传算法的方法，包含考虑有效构建模块来解决数独难题的遗传操作。Gunther等人[12]利用熵最小化的方法来解决数独谜题。
介于以上标准工作，我们打算采用上述文献的系统，使用标准尺寸，接口解决，9*9的数独游戏的检测后用暴力算法在FPGA中解决。这种在软件中解密的数字被委托给FPGA生成解决方案，加速了进程，因为算法是在专用硬件上实现的。
- 检测拼图
数独检测设计分为三个部分：首先，使用局部阈值分割并从周围环境中提取拼图。 然后，对图像进行几何变换并再次设置阈值以提取数字。 第三，使用光学字符识别（OCR）从拼图中提取数字，并根据它们在图像中的像素位置以9x9矩阵存储。
- 图像重新处理和拼图提取
第一步涉及图像获取和预处理步骤的应用，以补偿背景照明，背景噪声和拼图方向的不均匀性，如图1所示。
将图像1（从相机或预存文件中获取）采集到系统中并转换为灰度格式。 然后该图像需要转换为二进制格式以供进一步处理。 执行转换有一种方法是利用全局阈值方法将图像像素分类，高于特定阈值的白色，否则为黑色。 然而，当背景照明高度不规则时，这种方法失败，但当照相机获得拼图时这是可能的。另一种局部阈值方法，通过使用考虑局部对比局部描述符如标准偏差和均值其通过
图1.获取Sudoku拼图的图像 图2.局部阈值分割后的分割图像
计算图像1中每个邻域的中心点（x，y）处的局部阈值来对图像1进行阈值。零和1的数组指定邻域的大小，其中一些表示用于计算标准偏差和局部平均值的元素。 然后通过等式（1）给出二进制分段图像：
其中Txy=asigma;xy bmG
Txy是本地阈值
mG是全局图像的意思
sigma;xy是局部标准偏差
a和b是通过实验建立的非负常数
局部阈值处理有效地保留了所需的细节，从而使我们的系统更有效地用于数字识别，如图2所示。
因此，下一步就是从背景中提取出数独，消除所有多余的元素。为了实现这个目标，我们使用面积作为基准。 图像中所有连接的组件都被标记，并提取外框（具有最大面积的组件）。 然后应用霍夫变换来检测图像中四边形的边界并在
图3.提取拼图
盒子上绘制线条。四条线的交点产生数独谜题的角落，交点存储起来以供进一步使用。
所提取的框用于创建一个二进制掩码，应用到原来的数独时，去掉背景杂波，只留下图3所示。
- 图像转转换为二进制图像
将提取的数独拼图的空间变换，用来解决任何类型的透视畸变或凸面缺陷，并将拼图缩放到450 450像素的标准正方形。缩放是使用图像的投影变换实现的，其中在前一步骤中导出的四个交点被映射到预定义正方形的四个角。 这一步使我们的系统更加强大，因为它将不同大小的拼图映射为均匀的方形以供进一步处理。
然后使用自适应阈值将经几何变换的图像分割成二值图像，并移除边界和网格线，其突出显示在下一步中识别所需的数字，如图4所示。
图4.数字识别的二进制图像 图5.使用OCR识别号码后的结果图像
- 使用OCR识别数字
数字识别分两个阶段完成：
（1）阶段1：正方形网格的长度和宽度被分成9个相等的部分，给出81个较小的正方形。 计算每个小方块的对角线x和y坐标，并重新分配1到9的值，表示每个方块的行数和列数。 因此，计算拼图中存在的每个数字的质心值，并且通过将质心的x和y坐标与每个较小平方的坐标进行迭代比较，这些坐标值是从1到9的重新分配值。如果质心被发现位于正方形的x和y坐标内，它将采用该正方形的行和列号的值。此系统专为解决*9标准尺寸的拼图而设计，将软件中数独拼图的检测与FPGA中使用暴力方法生成的拼图解决方案相结合。这种方法可以用于检测数字位置，因为在前一步骤中所有的数独谜题已经转化为统一的四边形。
（2）阶段2：使用OCR识别图像中的数字并对其进行分类。当要读取的字符及其周围的噪声最小时，OCR会产生高度准确的结果。因此，噪声去除的图像处理步骤对于OCR检测产生清晰和清晰的图像是非常重要的，如图4所示。根据它们的新质心值将识别的数字存储在9times;9矩阵中，并将零分配给矩阵中未占用的地方。 最后，这个矩阵使用RS-232传递给FPGA。
- 数独解决方案
我们提出了一个基于暴力算法的数独求解器。这种强力方法已被采用[6]，并已相应修改以适应我们的需求。为了实施暴力算法，我们使用了五个存储器。 三个存储器用于存储三个位图，第四个存储阴影数独，第五个存储器表示哪个单元格被占用，哪个不存在。对于每个3*3块，1*9行和9*1列维持位图，阴影数独持续追踪哪些数独单元未被填充或者如果它们被填充，则使用哪个数字。 数独使用图6所示的有限状态机（FSM）来解决，其中包含四个状态：初始化，检查空单元，预测和回溯。 初始化状态初始化用于查找和填充空单元格的数独求解器。 检查空单元状态横向排列，直到遇到空单元格。 填充状态用有效的候选者填充空单元格，并且如果单元格不能填充任何有效的候选者，则回溯状态返回到具有多个可行分配的单元格。 拟议的数独求解器有三个主要组件：RS-232 单元，存储单元和处理器和控制器单元（PCU）。
图6.处理器和控制器单元的FSM
- RS-232单元
RS-232单元负责接收数独拼图并发送数独拼图。RS-232单元采用RS-232协议以位的形式发送数据。接收器和发送器使用相同起始位的表示字节开始，同一个停止字节表示同步数据的串行传输的结束。
- 存储单元
存储单元负责存储关于数独的所有数据。存储单元除了存储位图和阴影数独之外，还更新位图。存储单元有五个存储器：行位图，列位图，块位图，阴影数独和占用单元存储器。所有的存储器都是双端口随机存取存储器（RAM），因此可以读取或更新数据。被占用的单元内存通过#39;1#39;表示被填充的单元，#39;0#39;表示被空单元填充。阴影数独持有哪些数字符号占据填充的单元格，空单元格由#39;0#39;表示。位图是按块，行和列维护的。行，列和块存储器分别包含所有的行，列和块位图。所有的存储器都是相互独立的，因此可以并行读取或更新。提供读写信号和地址由控制器和处理器单元。此外，全局复位信号重置所有的存储器，并从RS-232单元等待新的数独难题。
- 处理器和控制器单元（PCU）
PCU负责所有计算，并为两个单元的其余部分生成所需的信号。当数独由RS-232单元接收时，PCU生成所需的信号以将所有数据存储在存储器中。PCU内部的FSM有三种状态：初始化，检查空单元，预测和回溯。 在接收到数独拼图后，FSM被启用并移动到初始化状态。 该状态负责检查初始化所有信号并重置所有计数器，从而使系统准备好解决数独难题。初始化之后，FSM移动以检查空单元状态。检查空单元状态检查单元是否为空或不使用占用的单元存储器进行行划分。如果发现整行被填充，则检查下一行是否有空单元。 同样，所有的行都检查一个空单元格。 基于如图4所示检测到的数独，将遇到的第一个空单元将是（1,1），即与第一列的第一行相对应的单元。 选择一个空单元之后，FSM移动以预测状态。然后，从表I中所示的存储单元访问所选空单元的位图。此外，在所访问的位图之间发生按位或运算，从而给出可以放置在该单元中的有效候选。如果按位或操作没有产生任何有效的候选，则会遇到冲突，如果是，则相应的单元填充最低有效候选。如表I所示，选择最低有效候数，即从有效候数1,2,5中选择1，不需要跟踪哪些有效符号已经过测试，因此不需要使用额外的存储器。当空单元格（1,1）填充1时，相应地更新位图，占用单元格和阴影数独，而与PCU无关。 而且，当一个空单元格被填满时，相应的行和列被推送到堆栈，并且堆栈指针增加1，并且FSM移动以检查空单元格状态，其中查找空单元格和填充空单元的整个过程再次重复使用位图。重复该过程直到整个数独拼图完成或遇到冲突。 在后一种情况下，FSM进入回溯状态。在回溯状态下，读取最后填充的单元格并使用通过递减保存在堆栈中的行和列清除在返回的状态，最后填充细胞读取和清除使用行和列的保存在栈的递减堆栈。读取的候选文件被保存，FSM移动来预测状态。预测状态将填充已清除的单元格，若其中一个有效的候选数大于保存的候选，就继续填充单元格，如果遇到另一冲突，则继续返回回溯状态。FSM横跨三个状态检查空单元格，预测和回溯并解决数独谜题，并最终使用RS-232单元发送解决的数独谜题。
表一
使用
全文共7274字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[15725]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
