我们确信，今天不会有一个不熟悉QR码的Habr阅读器。这些二维条形码无处不在。顺理成章的是，世界上有许多工具可以以一定程度的效率将QR码添加到您的项目中。整个问题是，提到的效率直接取决于用于识别QR码的工具的质量。这是经典的插件：您可以（非常）好（非常）昂贵地解决问题，或者可以免费获得某种方式。是否可以修改免费版本，从而很好地解决问题？如果有兴趣，请看猫下。识别照片中的QR码是机器视觉的一项恰当任务。首先，在任务中，研究了一个对象，该对象最初是专门为“便捷”识别而设计的。其次，任务本身分为几个独立的，可理解的子任务：QR码的本地化，QR码的方向和直接解码QR码。事实证明，公有领域长期以来都有良好的库，可以解决最后两个问题：二维码的定向和解码。一个问题：对于高质量解码，此类库期望直接输入条形码的良好二进制图像。相反，很少关注图像中条形码的定位。根据我们的经验，您对识别对象的定位越准确，就越容易选择正确的预处理工具并对其进行识别。因此，如果要提高项目中QR码的识别质量，请从现代化QR码本地化方法开始。的确，即使您以后需要对图像进行二值化处理，从条形码的角度对区域进行二值化处理（从计算和定性的角度来看）也要比整个原始图像有效得多。在本文中，我们将告诉您如何使用经典的图像处理方法轻松提高QR码的定位质量，并给出所提出算法有效性的数值特征。我们将讨论使用改进的Viola and Jones方法作为基础的在图像上定位QR码的原始方法。有关本文主题的信息说明
在本节中，我们将描述用于构造定位方法的QR码的主要功能，以及对Viola and Jones方法的原始版本的简要说明。二维码
QR码（Quick Response Code的缩写）是一种二维条形码，于90年代中期在日本开发出来，用于汽车行业。与线性条形码相比，由于具有快速读取的能力和更大的容量，QR码系统已在全球生活的各个领域中广受欢迎。与通常由硬件扫描的标准线性条形码不同，QR码通常由照相机扫描。QR码的结构在ISO / IEC 18004（ISO / IEC标准18004）中有完整描述。为了为此类图像构建鲁棒的识别算法，QR码具有一些形成功能模式的参考点：条形码图像角落的三个正方形（称为取景器模式）和整个条形码图像中较小的同步正方形（称为对齐模式） 。这些点使您可以标准化图像大小及其方向。
图。QR码结构
尽管在视觉上所有QR码彼此相似，但是根据编码数据量的不同，QR码的不同副本可能具有不同的内部元素布局。此外，所谓的设计者QR码非常流行，其中使用了第三方图形元素（徽标，标志，题词等）代替了保证条形码高质量识别的附加信息部分。在构造QR码的本地化和识别方法时，必须考虑QR码的所有这些功能。
图。不同的有效QR码选项
中提琴和琼斯方法
只是对Habré的懒惰还没有写关于Viola和Jones的方法。即使我们在我们的区块中也做了几次（例如，here，here或here）。而且，我们认为有必要在两个段落中非常简短地说明其含义。开发了Viola and Jones对象检测方法，可以实时搜索图像中的人脸。该方法将检测问题简化为在每个图像点的二元分类问题，即对于使用各种移位和缩放比例拍摄的每个矩形图像区域，使用预训练的分类器检查区域中是否存在所需对象的假设。作为特征空间，Viola and Jones方法使用矩形Haar特征，其值计算为相邻矩形内图像区域的像素亮度之和之间的差。为了有效地计算Haar特征的值，使用了积分图像，这在文献中也称为“求和面积表”。二进制“弱”分类器h（x）：Χ →{-1，+ 1}，通常表示为具有一个分支的识别树：
其中θ和p-属性的阈值和分类器的奇偶校验。接下来，使用AdaBoost机器学习方法，将“强”分类器构造为上述“弱”分类器的线性叠加。Viola and Jones方法的高速使用是通过使用“强”分类器的级联来确保的，该分类器可以对“空”（无对象）图像区域进行局部定位，以进行少量计算。QR码检测算法
在构造用于定位QR码的方法时，我们依赖于任务的以下功能。首先，所开发的方法必须具有高性能，可用于实时运行的识别系统。其次，该方法必须能够抵抗图像中条形码的允许变形。第三，该方法应考虑QR码的所有现有可变性。如上所述，我们选择了Viola和Jones的方法作为基本方法。该方法已在各种搜索刚性对象的任务中证明了自己，同时该方法提供了所需的性能。但是在原始版本中，由于以下原因，无法使用Viola and Jones方法：- 在Viola和Jones的经典方法中，使用了一系列“ Haar”属性来“强调”对象的纹理特征。在我们的案例中，尽管QR码由黑白条形码组成，但是条形码的分布与条形码之间存在很大差异；
- 经典的中提琴和琼斯方法是为给定方向上的物体的相同类型的检测而设计的，这在我们的任务中也没有观察到。
为了使用Viola and Jones方法解决问题，我们使用原始的边界特征族和决策树形式的高级分类器。第一修改将允许集中于研究对象的边界特征，而不是纹理。第二个修改将允许您构建一个可以检测变量对象的分类器。接下来，我们将告诉您有关每个修改的更多信息。Haar的渐变迹象。
为了构建有效的QR码检测器，我们使用了特殊的梯度特征族[1]。这些标志是在有向边界图的顶部计算的Haar矩形标志，可以显着提高其泛化能力。方向边界图是梯度模量的图像，它还考虑了在点（x，y）处的梯度的优选方向，定义为边界角向水平，垂直，+ 45°和–45°方向的离散化。为了构建QR码检测器，我们使用了两种类型的方向性边界图：直线边界图和对角面图。令原始图像f（x，y）。然后，您可以使用Sobel运算符沿水平和垂直方向计算导数的近似值：
此外，使用g x和g y，您可以计算图像每个点上的渐变方向：
直边界图主要包含水平边界和垂直边界，其计算方式如下：
地图对角线边界主要包含沿对角线的边界，其计算方法如下：
在构造的有向边界图（对角线或直线）图的顶部，计算矩形Haar标志。与经典的Haar特征不同，此类边界特征将包含大量边界的井对象泛化。
图。定向边界图的图示：（a）QR码的原始图像，（b）直边界图，（c）旋转QR码的图像（d）旋转QR码的对角线边界的地图
强大分类器的决定性树
强分类器树[2]是一种二元决策树：树节点是强分类器，在其右边缘上有可能包含对象的子窗口，而在左边则是未被识别为对象的子窗口。最终答案仅在叶子中给出。实际上，在Viola和Jones的原始著作中描述的经典级联分类器是一种仅包含一个“正”输出（叶）和许多“负”输出的树分类器。在[2]中，显示了从树分类器的根到最低节点的任何路径都可以表示为级联，其中各个强分类器以反向答案进入。因此，可以为树分类器构造学习算法，该算法使用经典级联分类器的训练过程来教授单个路径。基于树的分类器使您可以训练比经典级联分类器更有效的变量对象完整性分类器。实验结果
作为评估本文提出的条形码定位方法有效性的实验的一部分，准备了一组由264张图像组成的条形码图像。图像的物理大小约为1 MPix。每张图像在任意方向上仅包含一个QR码，条形码区域至少占图像总区域的10％。下图显示了组装后的图像示例。
图。组合条形码图像集中的图像示例
将准备好的图像集分为训练集和测试集。训练样本的大小为88张图像，测试样本的大小为176张图像。训练集既用于准备积极的例子，也用于准备消极的例子。由于阳性样本的初始数量很少，因此我们使用了数据增强技术[3]。特别是，我们绕条形码中心旋转了15⁰。扩充后，阳性实例的数量为2088个。使用相同的正例和负例，我们训练了三个QR码检测器：具有标准Haar特征的经典级联分类器，具有边界特征的经典级联分类器和具有边界特征的树型分类器。第一个级联分类器由12个级别组成，总共包含58个属性。第二个级联分类器由8个级别组成，总共包含39个属性。经过训练的树分类器由39个顶点组成，总共包含110个字符，并且从顶部到叶子的最大路径为9。下面是经过训练的树分类器的示意图。
图。训练好的树分类器方案
为了评估构造的QR码检测器的质量，我们使用了OpenCV开源计算机视觉库中的条形码解码模块。在准备好的图像测试集（如上所述，由176张图像组成）上，我们启动了解码模块，而无需进行任何特殊的预处理，以及在使用经过训练的探测器初步搜索QR码之后。以下是条形码的解码结果：该表表明，使用所描述的方法对QR码进行初步定位可以显着提高条形码解码的质量（解码错误的数量减少了44％）。此外，结果还证明，原始的Viola and Jones方法（具有经典的Haar特征和级联分类器）的应用在定位QR码的任务中无效。现在，让我们看一下每个分类器对条形码的定位精度。从左到右的图显示了使用具有标准Haar特征的经典级联分类器，具有边界特征的经典级联分类器和具有边界特征的树型分类器检测相同条形码的结果。可以看出，通过考虑QR码的可变性，树分类器提供了最佳的条形码定位精度。
图。在相同图像上训练有素的探测器的工作图示
结论
如今，QR码已用于生活的各个领域：广告行业中的URL编码，作为电子服务一部分的州段等。尽管此类条形码分布极高，但现有的开源库仍专注于解码过程，而不是本地化问题。但老实说，本文的真正目的不是描述一种有效的QR码本地化方法，而是试图告诉亲爱的读者，如何使用科学思维和系统分析方法，了解如何使用经典的数字图像处理工具，您可以免费图书馆达到了实际的工业水平。谢谢您的关注。使用的资料清单[1] A.A. Kotov, S.A. Usilin, S.A. Gladilin, and D.P. Nikolaev, “Construction of robust features for detection and classification of objects without characteristic brightness contrasts,” Journal of information technologies and computing systems, 1, 53-60, (2014).
[2] A. Minkina, D. Nikolaev, S. Usilin, and V. Kozyrev, “Generalization of the Viola-Jones method as a decision tree of strong classifiers for real-time object recognition in video stream,” in Seventh International Conference on Machine Vision (ICMV 2014), 9445, International Society for Optics and Photonics, (2015), doi:10.1117/12.2180941.
[3] D. P. Matalov, S. A. Usilin, and V. V. Arlazarov, “Modification of the viola-jones approach for the detection of the government seal stamp of the russian federation,” in Eleventh International Conference on Machine Vision (ICMV 2018), 11041, International Society for Optics and Photonics, (2019), doi:10.1117/12.2522793.