本发明公开了一种二维条码的定位方法，码字由正方形的单元块排列组成，码字区域分为定位区、间隔区、数据区、图案区。对采样并预处理后的数字图像信号，采用最大类间方差算法进行二值化；再采用快速填充算法得到多个深色和浅色连通域；根据形状因子和面积因子，筛选出多个准正方形深色和浅色连通域；然后进行同心筛选，得到多个候选定位图形；接着进行正方形拓扑筛选，确定有效码字区域，最后进行空间采样，这样就完成了二维条码的定位。
1.一种二维条码的定位方法，其特征是：该二维条码，码字由正方形单元块排列组成，码字区域分为定位区、间隔区、数据区、图案区；定位区由4个相同的定位图形组成，定位图形位于码字的左上、右上、左下、右下4个角；数据区由表示数据信息的单元块组成，数据按纠错编码方法生成并按一定顺序排列；间隔区由浅色单元块组成，它将4个定位图形与数据区分隔开；图案区位于数据区的正中间；而该二维条码按以下步骤进行定位：
1)使用采集设备采集图像信号，并输出为数字图像信号；
2)对数字图像信号进行灰度转换、直方图均衡、边缘保持的预处理；
3)根据最大类间方差算法将预处理后的灰度图像转化为二值图像；
4)采用快速填充算法对深色连通域进行区域标记，得到多个深色连通域；
5)采用快速填充算法对浅色连通域进行区域标记，得到多个浅色连通域；
6)对每一个深色连通域进行形状筛选，计算形状因子，筛选出多个准正方形深色连通域；
7)对每一个浅色连通域进行形状筛选，计算形状因子和面积因子，筛选出多个准正方形浅色连通域；
8)进行同心筛选，从浅色连通域和深色连通域中分别选出一个区域，如果它们的中心很接近，且浅色连通域的外接矩形位于深色连通域的外接矩形之内，那么将这样一对浅色-深色连通域作为一个候选定位图形；
10)进行正方形拓扑筛选：从多个候选定位图形中依次选出4个，如果定位图形的中心点的相对位置满足正方形拓扑位置关系，那么这4个中心点就确定了一个有效的码字区域，否则再依次选出其他4个点进行成组筛选；所述正方形拓扑位置关系的判定准则为同时满足下列4个不等式：其中d1≥d2≥...≥d6
表示点 与点 之间的欧氏距离； 1≤i≤4，表示4个定位图形的中心点；
11)进行空间采样：根据步骤10)中得到的4个定位图形的中心点确定码字区域和数据区，即：根据4个中心点的位置，得到N×N个空间采样位置，将二值图像中数据区对应的2
N-64个位置的比特值作为数据区中的数据信息，其中，N为码字尺寸。
2.根据权利要求1所述的一种二维条码的定位方法，其特征是：转化为二值图像时采用最大类间方差方法得到二值化阈值：其中
w1＝1-w0c0＝#C0 C0＝{(x，y)|g(x，y)＜t}c1＝#C1 C1＝{(x，y)|g(x，y)≥t}
a(u′)＝#A(u′) A(u′)＝{(x，y)|g(x，y)＝u′}#C表示集合C中元素的个数，g(x，y)表示图像中坐标为(x，y)的象素的灰度值。
3.根据权利要求1所述的一种二维条码的定位方法，其特征是：计算形状因子和面积因子采用如下公式其中
(x，y)为连通域中的象素的坐标，#Wi表示集合Wi中元素的个数，其中Wi为第i个浅色连通域1≤i≤n′W，n′W为浅色连通域的个数；
对于深色连通域，当0.8≤r1≤1.2且0.8≤r2≤1.2时，将该连通域作为一个准正方形深色连通域；
对于浅色连通域，当0.8≤r1≤1.2且0.8≤r2≤1.2且0.67≤ra≤0.90时，将该连通域作为一个准正方形浅色连通域。
4.根据权利要求1所述的一种二维条码的定位方法，其特征是：根据同心筛选确定候选定位图形，所谓同心指的是：深色连通域的中心与浅色连通域的中心几乎重合，且深色连通域的外接矩形的边长大致等于浅色连通域的外接矩形的边长的1.5倍。
5.根据权利要求1所述的一种二维条码的定位方法，其特征是：根据4个定位图形的中心点确定N×N个空间采样位置采用如下公式：
公式中，(xp1，yp1)、(xp2，yp2)、(xp3，yp3)、(xp4，yp4)依次为左上、右上、左下、右下4个定位图形的中心点的坐标，δ为对角加载因子，N为码字尺寸。
6.根据权利要求1所述的一种二维条码的定位方法，其特征是：所述图案区为可选区域，如果不出现图案区，则图案区可以用于放置单元块表示数据信息。
一种二维条码的定位方法
技术领域
[0001] 本发明涉及条码技术，特别是一种二维条码的定位方法。
背景技术
[0002] 条形码是一种具有特殊形状和特殊排列方式的光学符号。
[0003] 目前，一维条码(以下简称一维码)已经广泛应用于物流仓储、生产制造、交通运输等各领域。一维条码存储数据量相对较少，需要依靠后台数据库的支持才能表达更多的信息。针对一维条码容量小、保密性差、纠错能力不强、保密性不高等缺点，产生了二维条码。
[0004] 二维条码简称二维条码，它借助不同颜色的图形单元表示特定的数据信息，图形单元按照矩阵形式排列，并加入特定的定位图形。不同于一维码只在水平方向上表示信息，二维条码在水平和竖直方向上同时存储信息，信息容量更大。
[0005] 二维条码的主要特点包括：
[0006] (1)信息容量大：二维条码的信息表示的空间维数增加到了二维，随着码字边长的增加，容量成平方量级增加。例如，在GB/T1828-2000国家标准中，版本40的QR码能容纳7089个数字，而最大的一维码最多只能表示十多个数字。
[0007] (2)强纠错能力：在编码算法上，一维码没有纠错功能。二维条码借助通信编码容错技术，使得二维条码图像在受损时，仍然可以部分或者全部识读出信息。例如，GB/T1828-2000国家标准中的QR码采用的RS算法在纠错等级为H时，纠错容量最高可达30％。
[0008] (3)编码范围广：可以表示常规的阿拉伯数字、英文字母、ASCII符；通过扩展编码，还可以表示中文字符、日文字符和未来更多的字符集。
[0009] (4)保密性强：二维条码中可以加入更多的加密信息，用于各种证件、卡片、商品等的防伪。
[0010] 二维条码有许多不同的码制，大致可分为堆叠式二维条码(如PDF417)和矩阵式二维条码(如QR码)两大类。
[0011] QR码是一种日本条码系统。QR码图形的左上侧、右上侧和左下侧有三个较复杂的定位图块，如图2所示。通过该定位图形，系统能迅速的找到码字图形区域和识读方向。QR码中使用RS算法和BCH算法用于纠错。QR码是一种功能强大、规范复杂的工业级二维条码技术。
[0012] DM码是另外一种优秀的二维条码系统。有别于QR码的正方形定位图形，DM码采用了L型的定位图形。
[0013] 目前，二维条码出现了一个重要的应用分支——手机二维条码。随着个人无线通信业务在全球的大规模普及应用以及微电子技术的发展，带摄像头、支持JAVA编程扩展、支持WAP无线上网技术和多媒体浏览技术的手机日益普及，手机用户可以使用手机摄像头作为二维条码的扫描设备，通过手机应用程序浏览和欣赏WAP网络甚至整个互联网中多媒体信息。手机二维条码已经凸显成为二维条码应用的一个崭新的、极具发展空间的应用领域。
[0014] 但是传统的工业级二维条码系统应用于手机二维条码有一些不足，例如QR码应用于手机二维条码应用时略显复杂。由于手机摄像头拍摄的静态图像精度较低，因此只能使用小尺寸的条码，大尺寸QR码在手机上的识别效果很差。然而，小尺寸的QR码的容量有限，且没有提供尺寸小于20×20的版本。此外，QR码的定位图形复杂、面积较大，因此占用了更多的空间，降低了信息容量，纠错能力很差。总而言之，在手机应用领域，QR码的容量和纠错等优点得不到充分体现。因此有必要为手机应用量身定制一种二维条码系统。
[0015] 将手机二维条码作为一个独立的分支进行研究和开发，Michael Rohs发明的Visual Code被视为经典的手机二维条码。该二维条码放置相互垂直一根长导航条和一根短导航条作为定位图形，属于典型的条状图形定位方式。长条形定位图形占用了更多的条码位置，降低了条码容量；条形区域周围分布的大面积浅色间隔区域也占用了更多的信息位置，且容易受到污染而影响定位效果。
[0016] 已有的二维条码定位图形及其识别方法包括：
[0017] 1.QR码的定位图形(也称寻像图形)由图形左上、右上、左下的三个复杂图形组成，每个图形的模块序列由深色-浅色-深色-浅色-深色次序构成，各元素的宽度比例为1∶1∶3∶1∶1。通过横向和竖向扫描，寻找比例为1∶1∶3∶1∶1的深色-浅色-深色-浅色-深色模式来确定定位图形。
[0018] 2.Visual Code借助水平放置的短轴和竖直放置的长轴作为定位图形。对长轴和短轴的判断采用不变矩方法。
[0019] 3.DM码采用L型的图形以及黑白单元块间隔组成的“轨道线”作为定位图形。
发明内容
[0020] 本发明的目的是一种二维条码的定位方法，使用四个特定形状的定位图形，充分利用定位图形的几何特征，实现快速准确定位码字区域并读取信息。
[0021] 一种二维条码系统，码字由正方形的单元块排列组成，码字区域分为定位区、间隔区、数据区、图案区；定位区由4个相同的定位图形组成，定位图形位于码字的左上、右上、左下、右下4个角；数据区由表示数据信息的单元块组成，数据按纠错编码方法生成并按一定顺序排列；间隔区由浅色单元块组成，它将4个定位图形与数据区分隔开；图案区位于数据区的正中间，图案区为可选区域，如果不出现图案区，则图案区可以用于放置单元块表示数据信息。
[0022] 本发明提供了前述二维条码的定位方法，它是这样实现的：一种二维条码系统的识别方法，按以下步骤进行：
[0023] 1)使用采集设备采集图像信号，并输出为数字图像信号；
[0024] 2)对数字图像信号进行灰度转换、直方图均衡、边缘保持的预处理；
[0025] 3)根据最大类间方差算法将预处理后的灰度图像转化为二值图像；
[0026] 4)采用快速填充算法对深色连通域进行区域标记，得到多个深色连通域；
[0027] 5)采用快速填充算法对浅色连通域进行区域标记，得到多个浅色连通域；
[0028] 6)对每一个深色连通域进行形状筛选，计算形状因子，筛选出多个准正方形深色连通域；
[0029] 7)对每一个浅色连通域进行形状筛选，计算形状因子和面积因子，筛选出多个准正方形浅色连通域；
[0030] 8)完成同心筛选，从多个浅色连通域和深色连通域中分别选出一个区域，如果它们的中心点很接近，且浅色连通域的外接矩形位于深色连通域的外接矩形之内，那么将这样一对浅色一深色连通域作为一个候选定位图形，
[0031] 9)反复执行步骤8)得到多个候选定位图形；
[0032] 10)完成正方形拓扑筛选：从多个候选定位图形中依次选出4个，如果定位图形的中心点的相对位置满足正方形拓扑位置关系，那么这4个中心点就确定了一个有效的码字区域；否则再依次选出其他4个点进行成组筛选；
[0033] 11)进行空间采样：根据步骤10)中得到的4个定位图形的中心点确定码字区域和数据区，即：根据4个中心点的位置，得到N×N个空间采样位置，将二值图像中数据区对2
应的N-64个位置的比特值作为数据区中的数据信息。
[0034] 通过以上步骤就完成了二维条码的定位。
[0035] 与现有二维条码相比，本发明的有益效果在于：定位图形简单且占用空间小、信息容量更大，提供的小尺寸版本码字特别适合手机二维条码应用，定位算法充分利用了定位图形的形状特征，算法简洁高效。
[0036] 条形定位的二维条码，例如Visual Code，定位图形和间隔区域面积较大，这使得定位图形被污染的可能性增大，容易影响定位效果；定位图形占用的空间随码字尺寸的增大而增大，降低了码字容量。QR码系统中，定位图形包含三个相同的定位图块，每一个定位图块可以看作由三个重叠的同心的正方形组成，定位图形较复杂且尺寸较大，在小尺寸版本时，信息容量很小(大部分空间被定位图形占用)，QR码的容量大、纠错强等优点很难体现。
[0037] 本发明中提出了一种新颖二维条码，该二维条码的定位图形简单，且定位图形不随码字尺寸的增加而增加。定位图形由方、圆两种不同的形状组成，码型更加美观。根据需要，码字中能够加入图片以便进一步增强码字的美感。定位图形占用较少的空间位置，相应的提高了码字的信息容量。在同等码字尺寸下，其容量远远大于QR码和Visual Code。在小版本码字中(低于20×20)仍然能够高效、正常工作。
[0038] 本发明中提出了一种新颖的二维条码定位方法，该方法充分利用了正方形图块和圆形图块的几何形状特征，计算形状因子时采用了大量的加减法和少量乘除法，极大的降低了算法复杂度和处理时间，识别方法简捷而高效。算法中采用了快速填充算法用于区域标记，与传统的区域标记算法相比，大大降低了处理时间。
附图说明
[0039] 图1为按照本发明的二维条码的码字示意图；
[0040] 图2-图3为按照本发明设计的较佳实施例的示意图；
[0041] 图4是现有QR码示意图；
[0042] 图5是现有DM码示意图；
[0043] 图6是现有Visual Code码示意图；
[0044] 图7是本发明二维条码的定位方法的程序流程图。
具体实施方式
[0045] 现结合附图及实施例对本发明中二维条码的定位方法作进一步详细说明。
[0046] 如图1～图7所示，其中，图1描述了本发明中的二维条码的码字结构。该二维条码图形包括定位区1、间隔区2、数据区3、图案区4。
[0047] 该二维条码的码字尺寸可以为任意的N×N大小，码字由正方形的单元块排列组成。
[0048] 定位区1由四个相同的定位图形组成，定位图形位于码字的左上、右上、左下、右下四个角，每一个定位图形由2个重叠的同心的图形组成，它们是3×3个深色的单元块和面积接近于3的浅色圆形图块。
[0049] 数据区由表示数据信息的单元块组成，数据按纠错编码方法生成并按一定顺序排列，数据区中的单元块通过不同的颜色表示特定的信息。
[0050] 间隔区2将定位区与数据区3分隔开。
[0051] 图案区位于数据区的正中间，图案区为可选区域，图案区用于增加码字美观度。如果二维条码不包含图案区，那么图案区可以用作数据区放置单元块。
[0052] 该二维条码通过设置掩膜方式减少数据区中出现伪定位图形的数量。伪定位图形由2个重叠的同心图形组成，较大一个图形为深色，较小一个为浅色，且2个图形都近似为正方形图块。
[0053] 在YUV颜色空间中，Y为灰度，表示色彩的亮度，所述浅色是指Y小于50％，所述深色是指Y大于等于50％。
[0054] 参照图7的流程图，对图2所示的二维条码进行定位，其详细流程如下：
[0055] 首先进行图像采集701。采集设备输出数字图像信号，以便后续的算法进行处理。在本实施例中，采用了手机摄像头作为采集设备。
[0056] 然后，进行数字图像的预处理702，包括灰度转换、直方图均衡、边缘保持。这些算法属于数字图像处理的通用算法，不属于本发明的内容。
[0057] 接着，进行二值化处理703，将灰度图转换为黑白二值图像。首先将步骤602中得到的灰度图像，根据最大类间方差算法将灰度图像转化为二值图像。由最大类间方差求二值化阈值表示为：
[0058]
[0059] 其中
[0060] w1＝1-w0
[0061] c0＝#C0 C0＝{(x，y)|g(x，y)＜t}
[0062] c1＝#C1 C1＝{(x，y)|g(x，y)≥t}
[0063]
[0064] a(u′)＝#A(u′) A(u′)＝{(x，y)|g(x，y)＝u′}
[0065] #C表示集合C中元素的个数，g(x，y)表示图像中坐标为(x，y)的象素的灰度值。根据Top，二值化操作描述为
[0066]
[0067] 接下来在步骤704中，采用快速填充算法对深色连通域进行区域标记，得到n′B个深色连通域{Bi}，1≤i≤n′B，n′B为深色连通域的个数。
[0068] 在步骤705中，使用同样的算法对浅色连通域进行区域标记，得到n′W个浅色连通域{Wi}，1≤i≤n′W，n′W为浅色连通域的个数。
[0069] 在步骤706中，先对每一个深色连通域Bi，1≤i ≤n′B，计算形状因子[0070]
[0071] 其中
[0072] x1＝max(x)
[0073] x0＝min(x)
[0074] y1＝max(y)
[0075] y0＝min(y)
[0076] k11＝max(y-x)
[0077] k10＝min(y-x)
[0078] k21＝max(y+x)
[0079] k20＝min(y+x)
[0080] (x，y)为深色连通域Bi中的象素的坐标。
[0081] 当0.8≤r1≤1.2且0.8≤r2≤1.2时，将区域Bi作为一个准正方形区域。对所有深色连通域计算上述的形状因子，筛选出nB个准正方形区域，并记录下对应的区域中心[0082] 1≤i≤nB
[0083] 和外接矩形的边长
[0084] 1≤i≤nB
[0085] 在步骤707中，对每一个浅色连通域Wi，1≤i≤n′W，计算形状因子[0086]
[0087] 和面积因子
[0088]
[0089] 其中
[0090] x1＝max(x)
[0091] x0＝min(x)
[0092] y1＝max(y)
[0093] y0＝min(y)
[0094] k11＝max(y-x)
[0095] k10＝min(y-x)
[0096] k21＝max(y+x)
[0097] k20＝min(y+x)
[0098] (x，y)为浅色连通域Wi中的象素的坐标。
[0099] 当0.8≤r1≤1.2且0.8≤r2≤1.2且0.67≤rα≤0.90时，认为区域Wi近似为一个准正方形区域。对所有浅色连通域计算上述的形状因子和面积因子，然后筛选出nW个准正方形区域，并记录下对应的区域中心
[0100] 1≤j≤nW
[0101] 和外接矩形的边长
[0102] 1≤j≤nW
[0103] 接下来，进行同心筛选708。所谓同心指的是：深色连通域的中心与浅色连通域的中心几乎重合，且深色连通域的外接矩形的边长大致等于浅色连通域的外接矩形的边长的1.5倍。
[0104] 依次从nB个深色准正方形区域中取出第i个区域，从nW个浅色准正方形区域中取出第j个区域，如果
[0105] 且
[0106] 那么第i个深色准正方形区域与第j个浅色准正方形区域配对组成一个准定位图形，且将浅色准正方形区域的中心点作为准定位图形的中心点。
[0107] 1≤k≤npair
[0108] 重复上述判断，得到npair个准定位图形，
[0109] 接着，完成正方形拓扑筛选709。从多个准定位图形中依次选出4个，如果其中心点的相对位置满足正方形拓扑位置关系，那么这4个点就确定了一个有效的码字区域；否则再依次选出其他4个点进行筛选。具体算法为：
[0110] 从npair个中心点中依次取出4个中心点，将中心点之间的欧氏距离进行排序得到[0111] d1≥d2≥...≥d6
[0112] 其中
[0113] 1≤k≤6
[0114] 表示点 与点 之间的欧氏距离。
[0115] 如果同时满足以下四个条件
[0116]
[0117]
[0118]
[0119]
[0120] 则认为满足正方形拓扑位置关系，转步骤710，否则重复上述筛选。如果4个中心点的所有的取法都不满足上述算法，则定位失败。
[0121] 最后，完成空间采样710。根据步骤709中得到的其中4个定位图形的中心点，确定数据区，根据4个定位点的位置，得到N×N个空间采样位置，将二值图像中数据区对应的N2-64个位置的比特值作为数据区中的数据信息；在N×N个空间采样位置中，有64个位置属于定位图形所占区域，不需要进行空间采样。
[0122] 假设4个定位图形中，左上、右上、左下、右下4个中心点的坐标分别为(xp1，yp1)、(xp2，yp2)、(xp3，yp3)、(xp4，yp4)，则根据以下公式确定N×N个空间采样位置的第m行第n列元素的坐标(xmn，ymn)。
[0123] 0≤m≤N-1，0≤n≤N-1
[0124] 其中
[0125]
[0126]
[0127]
[0128]
[0129] 为了防止矩阵求逆时出现奇异矩阵，在求逆前进行了对角加载处理，加载因子为δ，且δ为一个很小的实数。
[0130] 以上所述的实施例及实施方法仅为本发明的实施例，而本发明不限于上述实施例。对本领域的一般技术人员而言，在不违背本发明原理的前提下对它作出的任何显而易见的改动，都属于本发明的构思和所附权利要求的保护范围。
