ZXing无法解析某些二维码的问题分析

使用ZXingObjc 存在无法解析某些二维码的bug

一、问题描述

NtQRCode对MA68的部分分享图片中的二维码无法解析

示例：

一般是对一些分辨率比较高的图片才存在该问题

按照ZXing的示例代码，接口调用方法如下：

UIImage *image = [指定图片的UIImage对象];
ZXLuminanceSource *source = [[ZXCGImageLuminanceSource alloc] initWithCGImage:image.CGImage];
ZXBinaryBitmap *bitmap = [ZXBinaryBitmap binaryBitmapWithBinarizer:[ZXHybridBinarizer binarizerWithSource:source]];
NSError *error = nil;
[hints addPossibleFormat:kBarcodeFormatQRCode];
ZXMultiFormatReader *reader = [ZXMultiFormatReader reader];
ZXResult *result = [reader decode:bitmap hints:nil error:&error];

返回的result中对应的内容为空，error不为空

返回Error内容如下：
Error=Error Domain=ZXErrorDomain Code=1002 "A barcode was not found in this image" UserInfo={NSLocalizedDescription=A barcode was not found in this image}

这个问题在网上也可以看到其他人上报了该问题

github上ZXingObjC的issue
https://github.com/TheLevelUp/ZXingObjC/issues/245

"再见ZXing 使用系统原生代码处理QRCode"
http://adad184.com/2015/09/30/goodbye-zxing/

ZXingObjC can't decode image taken from UIImagePickerController
https://stackoverflow.com/questions/15575554/zxingobjc-cant-decode-image-taken-from-uiimagepickercontroller

对于很明显的二维码图片都无法识别

同时，测试中发现，如果对图片进行裁剪，可能只要减少图片一列像素，即可以识别出其中的二维码内容

使用摄像头扫码该图片可以解析出其中二维码，而使用指定图片扫描的方法则无法识别

二、问题背景

QRCode二维码的结构

根据上述结构图，可以逐步查找出现上述问题的原因

三、问题定位

可以定位为ZXing对部分图片进行解析时，无法正确判断其中是否有二维码。

在github上，作者建议设置ZXMultiFormatReader的hints，设置为tryHarder，但实际测试中发现，设置tryHarder或者其他任意限制都不能改善这个问题(在后面可以发现，主要是因为ZXing的图片二值化导致二维码识别问题，而不是二维码解析算法的问题，所以设置hints无法解决这个问题)

ZXing SDK对图片进行识别主要有下面的步骤

图片输入
```
 UIImage对象
```

获取图片像素点的灰度值

 像素点的灰度值范围 0x00 ~ 0xFF

根据灰度值，对图片进行二值化

 像素点的取值范围 [0x00, 0x01]
 因为只有两个值，ZXing中为了节省内存，在内存中用一个位的0/1 表示一个点

跟据 "1-1-3-1-1" 的规则搜索3个定位点

 如果能够搜索到定位点，则继续解析
 如果不能够搜索到定位点，则返回空结果并且报错(略过第5步，直接到第6步)

解析二维码的内容
输出结果

对于上述ZXing无法识别的二维码，实验中发现，主要在第4步搜索3个定位点出现失败，即便对于人眼认为很明显的二维码图片，ZXing在第4步时也无法搜索到定位点。所以，解析失败与第5步二维码的解析无关

问题在于第2~4步之间

四、二维码定位点的搜索方法

对应ZXing的ZXQRCodeFinderPatternFinder类

ZXing中是使用5个数组，自上而下，自左而右的进行逐行扫描去检测的。实际上并不是每一行都扫码，默认是隔3行扫描

示例：

########xxxxxxxx########################xxxxxxxx########

数据：

stateCount[0] = 8;
stateCount[1] = 8;
stateCount[2] = 24;
stateCount[3] = 8;
stateCount[4] = 8;

是一个 "1-1-3-1-1" 的规则模型，则会进一步搜索周边上下的内容，分别搜索上下方向+左右方向+倾斜45度方向

上述 "1-1-3-1-1" 的规则模型的容忍度为 50%

即是，从 X 轴方向：

定位到"1-1-3-1-1" 后，往上（Y轴方向）检查上一行是否服务格则，获取上边界，往下获取下边界，然后上下相减，获取中间的点。之后从该中间行获取到中间点，从中间点出发

从Y轴方向：

检查是否符合"1-1-3-1-1"规则，往左（X轴方向）检查左边一列是否服务格则，获取左边界，往右获取右边界，然后左右相减，获取中间的点

之后从中间点出发按照倾斜45度方向检查是否符合"1-1-3-1-1"规则

上述检查后，都在容忍度50%以内，则认为是一个定位点。依次按照这个搜索方法遍历一遍图片就可以发现3个定位点。发现定位点后，后续就可以对二维码的内容进行解析了

在ZXing对4k图片进行识别时，大部分识别失败的原因是在寻找定位点时，获取不到定位点，进而返回图片中没有二维码的错误结果

确认了ZXing的解析代码，解析逻辑正常，所以问题的查找转到图片的灰度转化和二值化部分

五、图片灰度转化和二值化

灰度转化后，图片每个像素点的值的范围： [0x00, 0xFF]

灰度转化后

图片示例如下：

从上面的结果可以看到ZXHybridBinarizer对图片进行二值化时，是可能转化错误的，进而导致二维码无法识别

ZXHybridBinarizer对图片进行二值化后，定位模块的中心颜色都变成白色的。

六、ZXHybridBinarizer的原理

二值化有固定阈值法和动态阈值法

ZXHybridBinarizer是用动态阈值法，先将图片进行 8x8 像素进行分块，先计算每个分块的灰度平均值，存起来

然后要判断某个点的是黑0x00还是白0xFF时，则取周边5x5个分块，取其平均值作为阈值，假设为 T ，如果大于T，则是白点，假设小于T，则为黑点

使用8x8划分，可以节省每次都计算这64个像素的平均值

七、问题修复

方法一

是针对大分辨率的图片，增大ZXHybridBinarizer的分块大小，可以提高二值化的准确率，进而解决识别问题

比如本来为 8x8 像素进行分块，修改64x64对于4k图片的二值化就没有问题

但增大分块大小会导致函数运行时间增加，这点原因还没有定位到

方法二

使用ZXGlobalHistogramBinarizer替代ZXHybridBinarizer，实测中ZXGlobalHistogramBinarizer二值化能够很好的解决问题

方法三

使用系统CIDector替代ZXing，CIDector运行效率比ZXing还快，要求是iOS8.0以上

八、二维码解析时间百分比

1. 对于小图片 300x300像素的图片

灰度+二值化时间很短，解析二维码也很快

从上图可以看出识别二维码的时间在10ms左右

2. 对于大图片 4000x4000像素的图片

ZXing的速度下降明显

ZXHybridBinarizer 二值化的解析时间百分比

ZXGlobalHistogramBinarizer 二值化的解析时间百分比

使用同一张测试图片，在iPhone6s iOS11.3设备上进行测试

ZXHybridBinarizer大概占用了 590ms
ZXGlobalHistogramBinarizer大概占用了 869ms
使用ZXHybridBinarizer无法解析出二维码内容，所以其实后续的ZXQRCodeDector detect:error:没有被调用到，所以少了230ms左右的时间

数	ZXHybridBinarizer	ZXGlobalHistogramBinarizer
度转化	344ms	377ms
值化	155ms	236ms
容解析	0ms	231ms

可见，ZXGlobalHistogramBinarizer与ZXHybridBinarizer二值化算法运算时间差不多，而且，在图片较大时，灰度和二值化算法的占用时间较多，运算时间是 O(n^2)，跟二维图片一致

九、ZXing解析与CIDector解析的时间对比

CIDector是iOS系统提供的解析库

下面使用一张典型的系统相册图片进行分析

CIDector解析2k图片的时间

ZXing解析2k图片的时间

从上图对比可以看出，ZXing还是比CIDector慢了大概 30%，主要差距在灰度转化