Zxing库下的二维码解码：技术原理揭秘

二维码现已深化日常生活的办法面面，但你有没有好奇过二维码背后的原理呢？今日让咱们来了解下二维码的原理，由于二维码的许多细节实在太精妙，今日无法一次性讲完，假如感兴趣，能够做更多期分享或自行翻阅更多材料。

二维码原理

二维码本质上是对字符串的编码规则，终究转化成二进制串。

基础介绍

QRCode：Quick Response Code；全称为快速响应矩阵图码

Zxing库下的二维码解码：技术原理揭秘

  • 定位图画：

    • 方位探测图画：用于标记二维码矩形的大小；用三个定位图画即可标识并确定一个二维码矩形的方位和方向了；
    • 方位探测图形分隔符：用白边框将定位图画与其他区域区别；
    • 定位图画：用于定位，二维码假如尺度过大，扫描时容易畸变，时序图画的效果便是避免扫描时畸变的产生；
    • 校对图形：只要在 Version 2 及其以上才会需求；

  • 功能数据：

    • 格局信息：存在于所有尺度中，寄存格局化数据；
    • 版别信息：用于 Version 7 以上，需求预留两块 36 的区域寄存部分版别信息；

  • 数据内容（剩下部分）：

    • 数据码；
    • 纠错码；

一些有意思的常识

版别信息

  • 二维码一共有40个尺度(也能够称为版别、Version)。Version 1是21 x 21的矩阵，Version 2是 25 x 25的矩阵。每添加一个version，长宽就添加 4，公式是：(V - 1) * 4 + 21
  • 最高版别是40，所以是177 x 177的正方形，单纯存储数字的话，能够存 7089 个；只存大写字母的话，能够存大约 4k 个，大约500个汉字

常用编码形式

  • 数字编码(Numeric Mode): 只支撑数字 0~9 的编码
  • 字符编码(Alphanumeric Mode)：支撑包括数字、大写的A-Z(不包括小写)、以及$ % * + – . / :和空格
  • 字节编码(Byte Mode): 支撑0x00~0xFF内所有的字符
  • 日文编码(Kanji Mode)： 也能够用于中文编码，只能支撑0x81400x9FFC、0xE0400xEBBF的字符

纠错码

为什么二维码有残缺也能扫出来，以及怎样确保扫描成果的正确性？

Zxing库下的二维码解码：技术原理揭秘

  • 纠错等级越高，恢复能力越强，代价是能存储的有用数据越少，因为纠错码的占比会越高。
  • 纠错办法选用的是**里德所罗门码（Reed-Solomon Error correction）** ，该算法运用比较广泛，在二维码中，为了反抗扫描过错或污点，在磁盘中，为了反抗媒体碎片的丢失，在高档存储系统中，比如谷歌的 gfs 和 bigtable ，为了反抗数据丢失。（网络协议中的过失操控）

转化为掩码图画

  • 为什么二维码黑白块看起来那么均匀？没有接连的 1/0 块吗？
  • 对数据区再进行 Masking 操作，也便是做 XOR 操作

Zxing库下的二维码解码：技术原理揭秘

Zxing库下的二维码解码：技术原理揭秘

艺术二维码

  • research.swtch.com/qart
  • vecg.cs.ucl.ac.uk/Projects/Sm…

zxing 库原理

github.com/zxing/zxing

数据预处理

在官方示例中，获取到 YUV 图画数据之后，进行解码的代码如下：

private void decode(byte[] data, int width, int height) {
  Result rawResult = null;
  // 构建 YUV 数据源
  PlanarYUVLuminanceSource source = activity.getCameraManager().buildLuminanceSource(data, width, height);
  if (source != null) {
    // 构造二值图画比特流，运用 HybridBinarizer 算法解析数据源
    BinaryBitmap bitmap = new BinaryBitmap(new HybridBinarizer(source));
    try {
      // 选用 MultiFormatReader 解析图画，能够解析多种数据格局
      rawResult = multiFormatReader.decodeWithState(bitmap);
     } catch (ReaderException re) {
      //解码失利
     } 
   }
  if (rawResult != null) {
    // 解析到二维码成果
   }
}

首要依据 YUV 图画创立亮度源，也便是经过 PlanarYUVLuminanceSource 类将数据构建为亮度源数据，该类承继于 LuminanceSource，用来构建 YUV 图画格局的数据源，一起供给了图片裁截功能， 将剩余图画去除，zxing 中还供给了构建 RGB 图画数据源的 RGBLuminanceSource 。深化到 PlanarYUVLuminanceSource 类中，该类界说了：getRow、getMatrix、crop、isCropSupported、isRotateSupported 等办法，其间getRow 与 getMatrix 都是将图画数据以像素为单位进行核算，再回来亮度值，使得之后的核算都是以 Y 分量得出的亮度数组进行核算。

YUV 是一种图画格局，“Y”表明亮度，“U” 与“V” 表明色度、浓度，图画数据还有许多其他格局，例如：JPEG、ARGB、NV21、YUY2等，这儿运用 YUV 格局优点是节约带宽，关于二维码解析来说，并不需求彩色的图片数据，将 YUV 数据单独显示如下图所示：

Zxing库下的二维码解码：技术原理揭秘

构建完图画数据源之后，需求将源图画进行二值化，也便是将 LuminanceSource 获取到的亮度数据源矩阵构建为黑白两部分，也便是使得图画非黑即白，zxing 自带两种二值化解析算法分别是 HybridBinarizer 、GlobalHistogramBinarizer ，其间 GlobalHistogramBinarizer 适用于低端设备，对手机 CPU 与内存要求不高，它挑选的悉数的黑点核算，因而无法处理阴影等类似情况。而 HybridBinarizer 算法在履行效率上要慢于 GlobalHistogramBinarizer ，但辨认相对更有用，它是专门以白色为背景的接连黑色块的二维码图画而规划的，适用于解析带有阴影和突变的二维码图画。

官方例子中运用的是 HybridBinarizer 算法，简略归纳下该算法流程，当获取到亮度矩阵之后，HybridBinarizer 会将矩阵分为依照 8 * 8 的像素为单位来核算像素平均值，再依照每个小矩阵与自身周边的 5 * 5 的小矩阵再核算一次平均值，得到的值作为这个矩阵块的分界点，这时将矩阵内的 8 * 8 个点都和这个分界点进行比较，小于则为黑点，这样经过运算每个像素点变为 bit 描述特征，非黑即白。这样 byte 代表的像素点变为 bit 表述，减少了许多的数据量，便利了之后解码运算。

终究构建为 BinaryBitmap 二进制位图，以上便是 zxing 对图画数据的预处理。

zxing 解码

将图画数据构建为黑白表明的 bit 矩阵之后，接下来便是对 BinaryBitmap 目标进行条码比对解析，然后出去出二维码坐标与数据，不同的条码类型对应不同的读取办法，zxing 中供给了许多这种 XXReader 类，它们都是完结了 Reader 接口，其间都有一个 decode 的办法，用来解析 BinaryBitmap 数据，官方示例中运用的是 MultiFormatReader 类，该类能够支撑多种解码格局，需求手动设置，假如只是扫描二维码，咱们只需求设置它的 hints 为 QR_CODE 格局即可，这样能够加速解码速度，二维码解码终究是运用的 QRCodeReader 类，下面剖析下 QRCodeReader 解码流程。

咱们来看 QRCodeReader 类中的 decode 办法，代码如下：

public final Result decode(BinaryBitmap image, Map<DecodeHintType,?> hints)
  throws NotFoundException, ChecksumException, FormatException {
 DecoderResult decoderResult;
 ResultPoint[] points;
 // 判别是否是纯二维码
 if (hints != null && hints.containsKey(DecodeHintType.PURE_BARCODE)) {
  BitMatrix bits = extractPureBits(image.getBlackMatrix());
  decoderResult = decoder.decode(bits, hints);
  points = NO_POINTS;
  } else {
  // 相机拍摄，首要判别是否有二维码
  DetectorResult detectorResult = new Detector(image.getBlackMatrix()).detect(hints);
  // 有二维码，持续解码
  decoderResult = decoder.decode(detectorResult.getBits(), hints);
  points = detectorResult.getPoints();
  }
​
 if (decoderResult.getOther() instanceof QRCodeDecoderMetaData) {
   ((QRCodeDecoderMetaData) decoderResult.getOther()).applyMirroredCorrection(points);
  }
​
 Result result = new Result(decoderResult.getText(), decoderResult.getRawBytes(), points, BarcodeFormat.QR_CODE);
 List<byte[]> byteSegments = decoderResult.getByteSegments();
 if (byteSegments != null) {
  result.putMetadata(ResultMetadataType.BYTE_SEGMENTS, byteSegments);
  }
 String ecLevel = decoderResult.getECLevel();
 if (ecLevel != null) {
  result.putMetadata(ResultMetadataType.ERROR_CORRECTION_LEVEL, ecLevel);
  }
 if (decoderResult.hasStructuredAppend()) {
  result.putMetadata(ResultMetadataType.STRUCTURED_APPEND_SEQUENCE,
            decoderResult.getStructuredAppendSequenceNumber());
  result.putMetadata(ResultMetadataType.STRUCTURED_APPEND_PARITY,
            decoderResult.getStructuredAppendParity());
  }
 return result;
}

首要，判别 hints 信息中是否标记了 PURE_BARCODE 纯二维码，纯二维码表明除了二维码图片外没有其他的干扰信息，类似给定一张只要二维码的图片，进行扫码时即可设置该信息，zxing 给的官方示例是运用了相机预览扫码，所以这儿走到 else 中调用 new Detector(image.getBlackMatrix()).detect(hints) 办法，该 Detector 类中的 detect 办法首要检查图片中是否有二维码存在，再经过 decoder.decode() 办法进行解码，detect 办法代码如下：

public final DetectorResult detect(Map<DecodeHintType,?> hints) throws NotFoundException, FormatException {
 resultPointCallback = hints == null ? null :
    (ResultPointCallback) hints.get(DecodeHintType.NEED_RESULT_POINT_CALLBACK);
​
 FinderPatternFinder finder = new FinderPatternFinder(image, resultPointCallback);
 FinderPatternInfo info = finder.find(hints);
 return processFinderPatternInfo(info);
}

从代码可知这儿运用了 FinderPatternFinder 类中的 find 办法进行检查，进入到 find 源码，能够知道该办法是经过扫描图片，找到规则为黑白黑，并且像素份额为 1:1:3:1:1 ，也便是二维码特征中的 Position Detection Patterns 定位图画，若未找到这 3 个定位点将直接抛出 NotFoundException 异常，当找到 3 个定位图画之后，该办法一起还会经过 ResultPoint.orderBestPatterns() 办法对图画进行旋转排序，然后将二维码图画摆正，这便是咱们手机不管怎样倾斜，都会成功辨认二维码的原因。

当获取到排列有序的二维码坐标信息后，zxing 就可进行下一步操作，也便是经过 processFinderPatternInfo 办法将其间的二维码构建成正确的二维码矩阵，这儿构建的应该是与原图画二维码相对应的一个符号矩阵，主要是数据校验和生成终究的矩阵，然后便利之后的解码操作。

剖析相关代码可知，processFinderPatternInfo 办法首要进行版别信息的读取，也便是上方二维码特征图中的 Version Information 部分，二维码版别越高可包容的内容也就越多，版别与内容点数的核算公司为：17 + 4 * versionNumber ，读取到版别信息之后，假如版别大于 1 则会持续获取二维码的对齐形式，也便是二维码特征图中的 Alignment Patterns 部分，该部分用于对二维码中信息的辅佐定位。得到以上信息之后就能够重新构建与原图画中二维码相对应的符号矩阵，所做的处理便是透视转化算法，办法为 createTransform ，对图画像素进行一系列的转化修补，终究得到以 0 1 代表黑白所填充的矩阵。

此刻，Detector().detect() 判别是否有二维码的操作都已完结，得到一个 DetectorResult 目标，其间包括了构建好的二维码矩阵，此刻即可进行下一步 decoder.decode() 解码操作，剖析相关源码，首要会将上一步得到的 bit 矩阵经过 BitMatrixParser 进行简略判别是否包括二维码，接着经过 decode(BitMatrixParser parser, Map<DecodeHintType,?> hints) 办法，获取版别信息、格局信息、纠错码等，接着运用 DecodedBitStreamParser.decode() 办法解码内容部分，具体解码细节能够检查二维码的编码标准 ISO/IEC 16022-2006 ，终究得到 DecoderResult 目标，其间包括了二维码内容信息。

小结

  1. 获取图画帧的数据，格局为YUV；
  2. 将二维码扫码框中的图画数据进行灰度化处理；
  3. 将灰度化后的图画进行二值化处理；
  4. 依据二维码的特征寻找定位符；
  5. 寻找二维码的校对符；
  6. 解码；