详细谈谈二维码生成原理与编码(一)

本想一篇文章就解决的,后来发现需要介绍的有点多,一个晚上绝对写不完,看来又要开新坑了。

一、什么是二维码?

二维码有很多种,其中占据大半江山的主要有两种,一是以 PDF417 为代表的堆叠式条形二维码,另一个是以 QR Code 为代表的矩阵式二维码

PDF417 是“便携式数据文件”的缩写。它最少分为三层,最多 90 层。包括左右空白区、起始符、终止符、左右层指示符号字符等。它的具体架构如下图:

QR Code 分为编码区与功能区。编码区主要负责版本格式、数据和纠错编码;功能区主要负责位置探测图形、校正图像以及位置探测,其中位置探测图形是快速识别的关键。它的具体架构如下:

并且 QR Code 有有多种版本,版本与版本间的主要差别在于图形的尺寸,尺寸越大所能存储的信息越多。二维码一共有40个尺寸。官方叫版本Version。Version 1是21 x 21的矩阵,Version 2是 25 x 25的矩阵,Version 3是29的尺寸,每增加一个version,就会增加4的尺寸,公式是:(V-1)*4 + 21(V是版本号) 最高Version 40,(40-1)*4+21 = 177,所以最高是177 x 177 的正方形。

目前国内甚至世界范围内使用最为广泛的就是 QR Code,所以本篇文章具体介绍该二维码,并且下面的文章为方便大家理解,所有的二维码均指 QR Code。

二、怎样处理一个二维码?

这个部分我将分为两大部分来进行具体解释。第一部分是图像处理,第二部分是具体解码。

图像处理又可以细分为三个层次:

  1. 初级图像处理:图像去噪与图像锐化
  2. 中级图像处理:图像分割与边缘提取
  3. 高级图像处理:识别图像所包含的信息

解码过程也主要由三部分组成,这些部分的具体操作会在下文详细介绍:

  1. 二维码码字提取
  2. 纠错译码
  3. 信息译码

其中纠错译码是为了求解伴随因子,即判断正确码字的个数 [正确码字 = Yji错误码字]

信息译码 = 模式指示 + 字符段 + 数据位流。该功能一是为判断编码模式与字符个数,二是按照对应的编码进行解码

三、图像处理

先放一张图来大致表示一下图像处理的主要步骤

将上图文字化具象一下,可以得到一下具体步骤:

  • 拍摄图像输入
  • 预处理
  • 图像定位
  • 图像校正
  • 解码或译码

关于图像输入的渠道目前主要分为四种,该四种包含了几乎所有的信息码。

  1. 光管输入:主要采集一维码
  2. 激光输入:采集一维码与QR Code
  3. 线阵输入:即由LED组成的矩阵二维码
  4. 图像输入:即照片等形式的扫描

图像的采集与数字图像的质量由二维矩阵的形式存储与计算机中。其中该图像的对比度、清晰度等等都是图像质量的主要影响因素。清晰度是指所采集图像的亮度、对比度、尺寸大小、颜色饱和度(颜色饱和度越小,清晰度越高)。

用物理的方式表示图像采集可以抽象为下图所表示的模型:

接下来详细介绍一下预处理模块。这个模块是相当重要的,其主要功能就是将二维码从众多复杂信息中提取出来。可能你会问,二维码不就在那里嘛,一眼就可以看见,怎么个复杂法?也许对于人眼来说二维码很好辨认,但是对于计算机来说可不是这样。计算器需要一些列复杂的判断才能分辨出二维码的位置。

上图就是一个预处理所进行的步骤。咱们来一个个的分析。

图像的灰度化处理

摄像头采集到的二维条码图片是RGB格式的彩色图像,由红(Red)、绿(Green)、蓝(Blue)三种基本颜色按照一定的比例混合得到,每一种颜色分量有256个灰度级,三种颜色组合可以表示出多种颜色,几乎可以表示人类能够感知到的所有颜色。彩色图像包含了大量识别过程中不需要的色彩信息,这些信息都需要占用存储空间。在计算机中,R、G、B三个分量分别占用一个字节的内存,一个像素至少需要占用三个字节的内存。灰度图像只表示亮度信息,只需要占用一个字节内存。所以,在图像处理过程中,通常都先将彩色图像转换成灰度图像,这样不但可以减少存储开销,而且可以减少后续图像处理的计算量,加快二维条码识别速度。

假设灰度图像中灰度值用 Y 表示,彩色图像各分量的灰度值分别为 R、 G、 B,那么标准的灰度值Y的计算公式为:

Y = 0.30R+ 0.59G+0.11B

图像的中值滤波处理

普通CMOS摄像头采集到的二维条码图像中经常会含有一些噪声点,导致图像退化,对后续的条码识别产生严重的干扰,降低条码识别率。针对图像中普遍存在的高斯噪声、椒盐噪声采取了中值滤波降噪处理,能够有效的去除上述几种噪声,保护图像的边缘信息,不会对后续的边缘提取产生很大的影响。

中值滤波具有良好的噪声抑制能力,是一种非线性平滑技术。对于像素点,它统计其领域窗口内所有像素点的灰度值并进行排序,将这个像素点的灰度值设置为排序后的中间值。一般选取窗口像素点个数都为奇数,因此中值滤波的数学表达式如下:

PM = Median{ P1, P2, P3 … Pn } = Pi((n+1) / 2)

其中, P1, P2, P3 … Pn 是邻域内的像素灰度值,PM 就是邻域内的中指。

窗口选取对图像中值滤波的效果也将产生很大的影响。根据不同的应用场合需要采用不同的采样窗口,常见的采样窗口有十字形、米字型、棱形、矩形等,其中矩形窗口最为常用。本文主要是去除二维条码图像中含有的椒盐噪声,结合二维条码的特性,选用 3*3 的矩形窗口作为滤波窗口。

中值滤波是通过对邻域内像素的灰度值进行排序,能后选取排序结果的中间值作为该像素点的灰度值来实现的。图像中存在的椒盐噪声一般是随机分散分布的,在较小的领域内通常不会存在多个椒盐噪声,经过排序后,噪声点通常是排在靠前或者靠后的位置,因此,中值点的值比较能代表这个像素点的实际灰度值。中值滤波的具体操作过程如下:

  1. 遍历这个模板中所有像素点的灰度值
  2. 将这些灰度值从小到大进行排序
  3. 选取排序结果的中间值,并将其作为这个模板中心像素点的灰度值

图像的二值化处理

基于门限化的二值化方法。大津算法(Otsu)就是其中的代表,对光照均匀的图片具有良好的分割效果。但拍摄时,由于光源的不确定性经常会导致拍摄到的图像存在光照不均的现象,图像中靠近光源那边比较明亮,另一边则比较暗,对后续的图像二值化处理产生严重的影响。这里就采用了一种自适应亮度均衡化算法。

日本学者大津展之首先提出了最大类间方差理论,也叫做大津算法,简称 OTSU 算法。它的基本思想如下:设定一个阈值 t,它把一幅灰度图像分割成两组,一组灰度对应目标图像,另一组对应背景图像。假设灰度图像的灰度值为 0~k 级, t 从 0 开始取值,一直到 k,当 t=T 使得这两组灰度值的类间方差最大,类内方差最小时,目标图像和背景图像两部分的差别达到了最大化,若将此时的阈值 T 作为二值化的门限值,将获得最佳的二值化效果。

比如:一幅大小为 M*N 的 QR 条码图像,设阈值 t 将图像分割成前景色和背景色两组,ni 为图像中灰度值的像素个数, G 为灰度图的最大灰度级,8位灰度图的最大灰度级为255,则:

前景/背景色像素点占整个图像的比例 ω1 和 ω2 分别为:

前景/背景色像素点的平均灰度值 μ1 和 μ2 分别为:

整幅图像的平均灰度值 μ 为:

则两组图像的类间方差 σ2(t) 为:

σ2(t) = ω1μ1 - μ2 + ω2μ2 - μ2

当 0~k 之间改变 t,带入到上式中,当 t=T 使得 σ2(t) 取得最大值时,有由大津定律我们得知,T 即为最佳阙值,T = max[σ2(t)]。根据阙值 T 将图像数据分为大于阙值与小于阙值两部分。

由于大津算法是全局阈值法,图像分割阈值的选取是建立在整幅图片前景色和背景色的区分基础上的,当图像中存在比较严重的光照不均时,容易错误的将图像中较暗的部分认为是前景色,较亮的部分背景色,而不是把条码本身作为前景色,得到错误的门限阈值,得到的效果并不理想。

所以使用自适应亮度调节!

二维码预处理之自适应亮度均衡算法的介绍:

第一步:将条形码图像的第一行像素均等的分成 N 块,假设每一块含有 C 个像素,块内每个像素点分别标记为 pN1, pN2, pN3, …, pNC。则图像一行的像素点总数个数 K = N * C。pN1 和 pNC 分别为这个快中第一个和最后一个像素,计算出每块的灰度等级记为 SLN 为:

SLN = MAX_M(pN1~pNC) / M

其中,MAX_M(pN1~pNC) = ∑ Hpi。Hpi 为这个块中最大的 M 个像素点的灰度值,利用求平均值的方法来减小噪声点的干扰。

第二步:计算前后两块的插值为:

DiffN = | SLN - SLN+1 |

同时,不断将块的大小进行对等分裂,直至差值 DiffN 小于阙值或者块的大小不大于 M。

第三步:在相邻两个块之间使用线性插值计算,可以计算出块内每个点的像素灰度值,用 SNi 表示如下:

SNi = ( SLN ( C-1 ) + SLN i ) / C

其中,SNi 表示第 N 块中的第 i 个像素的灰度值。

第四步:基于上诉计算出的光照分布,就可以自适应的调整给各个像素点的增益。如果 SNi 的值较小,这个像素点的增益就可以适当加大,反之则减小。这样就可以将背景较暗的部分加量,背景明亮的部分则基本保持不变,达到光照补偿期望的效果。具体的增益公式如下:

AGCNi = BC / SNi

其中,AGCNi 为第 N 块第 i 个像素的增益。BC是经验值,用来控制图像亮度的系数值,通过反复试验,得出当 BC = 240 时能获得良好的效果。

处理后图像每个像素点的灰度值为:

pNi‘ = pNi * AGCNi

这里的 pNi 为原始灰度值,pNi‘ 为原图像中的像素点在经过自适应增益变换后的灰度值。同时,注意到,当 SLN 的灰度级比较大时,已经不需要对其进行增益处理,此时我们可以设定一个阙值 T,当 SLN 超过这个阙值时,不对该像素点进行增益处理。

第五步:采用大津算法对自适应亮度均衡后的图形进行二值化处理,效果如下图:

算法部分暂时到此结束。接下来将介绍二维码的定位方式与解码过程。