一种二维码识别定位算法

学号 20011210047  姓名 潘浩喆

【嵌牛导读】本文基于传统图像处理技术实现了一种二维码定位算法。算法分为图像预处理，二维码寻像图形检测，视图纠正三个步骤。图像预处理通过自适应阈值二值化方法使得算法适应于多种光照条件下的二维码识别；寻像图形检测算法以轮廓检测为基础，结合二维码的特性，检测准确度高；视图纠正分为投影视图纠正与旋转视图纠正两个步骤，为提高算法的鲁棒性，本文设计了投影视图手动选点纠正算法以及投影视图自动纠正算法。实验结果表明，对于不同拍摄条件下的二维码图像，本设计算法识别效果良好。

【嵌牛鼻子】二维码，图像预处理，寻像图形，视图纠正，鲁棒性

【嵌牛正文】

        二维码又称二维条码，常见的二维码为QR Code，是一个近几年来移动设备上超流行的一种编码方式，它比传统的条形码能存更多的信息，也能表示更多的数据类型。二维码使用特定的几何图形按一定规律在二维方向上分布以记录数据符号信息。在代码的编制上，二维码利用构成计算机内部逻辑基础的“0”、“1”比特流的概念，使用若干个与二进制相对应的几何形体来表示文字数值信息，二维码具有条码技术的一些共性：①每种码制有其特定的字符集；②每个字符占有一定的宽度；③具有一定的校验功能等；④具有对不同行的信息自动识别功能、及处理图形旋转变化点。

        二维码的结构组成较为简单，每个二维码符号都有一个正方形的模块阵列组成，其由编码区、分隔符、寻像图形、校正图形和定位图形等识别功能图形组成。其中，功能识别图形不用于编码，二维码符号四周为空白区域。

1.2二维码寻像图形

        在二维码的实际识别过程中，存在着相机位姿，光照环境等多种因素的影响，为了保证二维码的易识别性，同时保证识别准确率，二维码符号中含有寻像图形。

        在二维码符号的有效区域中的左上角、左下角和右上角的位置分别有一个有共同中心的图形，并且它们的边缘和编码区域有一个单位宽度的浅色间隔，这三个图形即为寻像图形。

        每个寻像图形由三个具有共同中心点的正方形组成，三个正方形的宽度为一个单位模块宽度，寻像图形中黑白相间图形的宽度之比为1：1：3：1：1。结合此比例关系，可以有效识别寻像图形。

      根据二维码符号的排列特征，可以大致确定二维码检测的思路。如前一小节所述，为方便二维码的识别，在符号的三个顶点处放置有寻像图形，因此，如果正确的识别寻像图形，便能顺利的识别二维码。由此，可将二维码的识别分为三个步骤：①图像的预处理；②寻像图形的检测；③二维码方向的纠正。

（1）图像的预处理，预处理通常包括图像灰度化，图像滤波，图像二值化等操作，目的是得到二值化处理的图像，方便后续寻像图形的检测，另外，需要特别注意的是，由于拍摄视角的不同，图像往往发生投影变换，在进行下一步检测前需进行畸变纠正。

（2）寻像图形的检测，根据寻像图形“回”字形状以及黑白像素块的比例特征，可以考虑结合轮廓检测算法检测出寻像图形的检测。

  （3）二维码方向的纠正，一般情况下，二维码的三个寻像图形应当具有一定的相对位置关系，而经前两步处理后的图形可能仍然存在旋转变换，因此需要根据检测到的寻像图形相对位置关系纠正二维码图形方向。另外，根据算法设计的不同，对于投影变换的纠正同样可以在这一步骤完成。

      综合以上，二维码检测的步骤如图1.3所示：

        如上一章所述，二维码的检测分为图像预处理，寻像图形检测，图像纠正三个步骤。考虑到待处理图像具有不同的拍摄角度，如：图像发生刚体变换、仿射变换以及投影变换；同时可能处于不同的光照条件，如：光照不均、强光条件、弱光条件等。因此，需要合理设计预处理以及图像纠正步骤。针对不同的几何变换情况，本文设计了自动图像纠正与手动取点图像纠正的方案，其中，自动图像纠正基于图像发生仿射变换的假设，而手动取点方案同时适用于投影变换情况。

        图像的预处理包括图像灰度化，图像二值化的操作。图像灰度化的操作较为简单，在此不再介绍，而图像二值化的效果将直接影响到后续的检测。一般情况下，图像二值化操作分为固定阈值与可变阈值两种。

      此类二值化方法针对图像的全局像素采用相同的阈值，opencv提供了不同的二值化选项以实现不同的二值化效果，如图2.1所示：

      上述二值化操作需要预先确定阈值，且阈值时刻保持固定，因此难以适用于不同光照条件下的图像，为此，日本学者大津提出了一种自适应确定二值化阈值的算法，即：Otsu算法。

      简而言之，Otsu算法就是遍历所有可能的阈值，对每个阈值结果的两类像素计算方差因为此种算法需要遍历所有可能的阈值，因此这不是一个相对高效的算法。另外，Otsu算法对于每一个像素点采用相同阈值，因此，光照不均可能影响二值化的效果。

      正如名字所示，此种算法对于每个像素使用不同的阈值，对于全局图像而言，阈值呈现出自适应的特性。权值的确定通常有两种方法：①每一个像素点取相同的权值；②每一个像素点的权值根据其到中心点的距离计算得到。相对于全局固定阈值的二值化方法，此方法阈值选择更为灵活，对于明暗差异较大的图像具有很好的二值化效果。

    对于一幅光照不均匀的图片，分别进行固定阈值二值化以及自适应阈值二值化，输入图像如图2.2所示：

      使用不同二值化方法的输出结果如图2.3所示：

      如图2.3所示，左图为固定阈值的二值化结果，右图为自适应阈值的输出结果，由图可以看出，自适应阈值避免了明暗不均匀带来的干扰，获得的图像二值化效果较好。在二维码的检测中，图像不可避免的会出现光照不均匀的情况，若使用固定阈值二值化，可能将丢失部分二维码符号信息，因此采用自适应阈值的二值化操作。

      二维码检测的关键在于寻像图形的检测与正确定位。根据寻像图形的特点，考虑通过轮廓检测结合比例检测的方式实现寻像图形的定位。

      图像经二值化处理后，二维码的寻像图形由一个7×7单位的黑色像素块，一个5×5单位的白色像素块和一个3×3单位的黑色像素块嵌套组成，从轮廓上来看，寻像图形的轮廓包括三层轮廓，最外层轮廓包括两个子轮廓，且两个子轮廓亦为嵌套关系。设寻像图形的轮廓由外到内依次编号为1、2、3，以父轮廓为根节点，子轮廓为子节点，做出一个寻像图形轮廓的树形图如图2.4所示：

      如图2.4所示，寻像图形的轮廓树形图是整幅图像轮廓树形图的一部分，其中，轮廓3也是全局轮廓树形图的叶子结点.opencv提供了findContours函数从二维图像中计算轮廓。输入一幅二值图像，经合适的函数选项配置后，函数实现了各个轮廓包含点坐标的存储以及各轮廓包含的层次关系的存储。函数根据求得的轮廓结果赋予每个轮廓一个索引值，所有的轮廓形成轮廓树，每个轮廓包含的层次关系由一个四元数组存储。

      因此，根据轮廓层次数组便可遍历轮廓的子轮廓。然而，对于轮廓检测函数而言，二维码图案具有随机、复杂的轮廓，在非寻像图形区域，也可能存在与寻像图形轮廓特征相同的图形区域，为了准确的定位寻像图形，避免误检测，需要结合像素块1:1:3:1:1的比例进一步筛选出寻像图形。因此，寻像图形检测的程序步骤如图2.5所示：

      图像纠正分为投影变换视图纠正以及寻像图形的位置纠正。一方面，由于图像拍摄角度不一定为正视图，因此图像可能发生投影变换，需要将图像尽量纠正为正视图以方便寻像图形的检测；另一方面，经投影变换视图纠正后的图像中，寻像图形可能处于错误的位置，需要对图形进行旋转变换。考虑到拍摄视角的复杂性，本文设计了两种几何形变纠正算法。

      此算法假设图形发生了投影变换，对于形状为正方形的二维码图案而言，经投影变换后可能得到任意形状的凸四边形。

        根据数学原理，通过四个相应的像素点对即可求解出变换矩阵H，因此，可选择变换前后四边形的四个顶点作为相应的像素点对。由于变换后正方形的顶点坐标易于确定，因此，问题转换成对二维码图形四个顶点的求解，常见的求解思路流程如图2.6所示：

      在实际测试中采用此种思路，对于部分二维码图像的确获得了理想的顶点坐标提取效果，然而，此种方案不具有很强的鲁棒性，当图像场景更为复杂，甚至图像尺寸发生一定程度的变化时，此种方法难以正确提取顶点，经过分析是由以下原因造成：①形态学操作涉及闭运算、腐蚀、膨胀，需要确定邻域大小以及操作次数，当二维码部分的尺寸发生变化时，最优形态学操作的邻域大小会相应的发生变换，因此难以设置一个符合多种尺度二维码图像的操作参数；②对于仅含有二维码的图像，该方法经第二步后可以仅获得一个四边形并进行后续操作，但当对于图像组成复杂，如二维码周围还含有文字、图像的情况，难以提取正确的四边形轮廓，甚至由于形态学操作的原因，造成部分图像元素的融合，严重影响顶点提取结果；③Hough变换的阈值设置同样具有如①中所述的问题，另外，Hough变换提取出的直线往往不仅仅包含四边形的边，准确的筛选出四边形的边同时适用于各种场景难以实现。

      综合以上，使用此种方法鲁棒性不强，难以胜任各种情况下的投影视图纠正。因此，为保证鲁棒性，采用手动选点的四边形顶点提取方法，即：显示原始图像，用户通过鼠标手动选取四边形的顶点，而后进行投影变换。为了方便用户的操作，在手动选点时，必须引入合适的标识。

      手动选点的过程中，会绘制选取点间的连线，方便用户保持直线间的平行关系，实测结果表明，手动选点的纠正效果良好。手动选点纠正的算法流程如图2.7所示：

      手动选点纠正算法的优点在于选点准确，几何变换效果好，对于任何角度拍摄的图像，均可以转换为正视图，方便后续寻像图形的识别与定位。然而，手动选点需要交互操作，在要求速度的使用场景下，手动选点算法显得略为繁琐。因此，在不影响寻像图形识别的前提下，略微牺牲几何变形纠正的效果以提升算法效率很有必要。为此，本文设计了投影视图自动纠正算法。

      结合前文的分析，对于非规则且尺度不确定的变换视图，鲁棒地自动提取四个变换像素点对十分困难，因此，该自动纠正算法假设视图仅发生仿射变换，即：包含二维码符号的正方形区域，经几何变化后，仍为平行四边形。由于自适应阈值二值化以及寻像图形检测算法鲁棒性较好，考虑使用检测到的寻像图形中心点进行变换像素点对确认。

      根据检测到的3个寻像图形中心点，结合平行四边形的性质，则可求出四边形的第四个顶点，从而计算得到变换像素点对。执行过程伪代码如图2.8所示：

        由图2.8可以看出，此部分算法返回计算得到的四个原图像素点坐标，四个点顺时针或逆时针方向排列，因此，几何变换纠正后的四边形相对于原图可能还发生了旋转，不过在寻像图形位置纠正步骤可将其纠正。综合以上，几何形变自动纠正算法流程如图2.9所示：

      经过以上算法步骤，已经大致获得二维码图像经二值化后的正视图（若对投影变换的视图使用自动纠正算法，处理结果则不是正视图），同时也检测出了二维码图像中的三个寻像图形。然而，为使二维码能正确识别并解码，需要对可能发生了旋转的视图进行纠正。将三个寻像图形依次连接，我们称位于直角顶点的寻像图形为基准寻像图形，因此，旋转视图纠正的目的是使得基准寻像图形位于二维码图案的左上角。

      算法分为基准寻像图形定位以及图像旋转两个步骤。考虑此时待处理图像为正视图，因此基准寻像图形位于正方形的四个顶点之一，根据不同的情况分类进行图像旋转即可，部分算法流程如图2.10所示：

      由图2.10可以看出，算法使用三个寻像图形中心点构造三角形，使用余弦定理确定直角，从而确认基准寻像图形。在实际调试过程中发现，因为得到的图像不一定是正视图，因此，以基准寻像图形中心点为顶点的角近似为直角，相应的，需要设定合适的余弦值阈值范围。

      本章从图像预处理、投影视图纠正、旋转视图纠正三个方面叙述了算法的实现思想与实现过程。在整体程序设计过程中，设计通过鼠标交互实现手动选点视图纠正算法与自动视图纠正算法的选择，具体来看，当原图像显示时，双击鼠标则进入自动视图纠正算法，单击鼠标开始选点，进入手动选点视图纠正算法。

        本文中分析并实现了二维码图像的定位算法。首先，我从原理上了解了二维码的组成结构以及检测原理，而后结合图像处理的相关知识设计了二维码检测算法。在算法设计过程中，我起初尝试设计一个算法能自动处理所有情况下的二维码识别问题，但在程序调试过程中发现，设计一个具有鲁棒性的算法实属不易。此算法的难点在于对于不同视角拍摄得到的图像相对于正视图发生了复杂的投影变换，需要对于各种投影视图，实现向正视图的纠正。为保证鲁棒性，我设计通过手动选点的方式纠正投影视图，经测试，此种方案基本可以满足各种拍摄角度下的二维码识别问题，但手动选点的过程使得算法操作略显繁琐；因此，牺牲了部分投影视图纠正效果，设计了投影视图自动纠正算法，此方案不需手动选点，但是基于图像仅发生仿射变换的假设，因此，不能保证纠正结果为正视图。然而，测试结果表明，即使不一定得到正视图，对于二维码寻像图形的检测依然成功，分析这是因为仿射变换的纠正一定程度上减小了畸变程度，再加以二维码识别的容错性，此种算法也具有良好的检测效果。