Mythsman


乐极生悲,苦尽甘来。


QR二维码植入图片方法简析

我们平时都经常见到二维码,用手机扫一扫就会显示当中的内容,内容大多是url的格式,方便人们访问站点。不过对于人来说,直接看二维码却并没有任何良好的印象。因此很多商家为了让自家的二维码更加形象,会想方设法地让自家的二维码更加形象生动,于是也就诞生出了很多种图像植入的方法。今天就把这些方法稍微汇总一下。

二维码

二维码可以说是现今人们生活中经常接触到的东西,简单的讲其实就是把条形码中的竖线变成点,从而增加一个数据维度,达到增加数据内容的目的。事实上二维码的种类有很多,曾经流行的二维码规范大概有下面这几种:

不过,最终一直流行到现在的二维码规范就剩下一个日本公司率先搞出来的QR二维码(Quick Response)了。QR二维码最典型的特征就是在图片的三个角有三个定位用的正方形,信息容量大、定位方便、数据保密和恢复能力强。有个日本的网站简要介绍了他的构造,连接在这里。接下来的说明主要是围绕这种二维码进行的讨论。

直接插入图片

直接插入图片的方法就是在二维码的中间插入设计好的图片,比如下面这些:

这样插入的图片比较清楚,显然会使人们对二维码的辨识度变高很多,也更容易被人们接受。但是这中插入图片的方法完全是利用了二维码本身的容错处理,或多或少的影响了二维码本身的容错性,原则上是不安全的方法。

修改点阵形状

所谓修改点阵形状,就是用类似设计师的眼光看待这个二维码,把原本的黑点和白点进行艺术化的修饰。这种方法虽然很难添加自己想要的图片,但是却十分具有艺术美感,让人印象深刻。也可以适当结合插入图片的方法,更加具有表现力。

当然,这种方法会增加扫码器识别的难度,万一图像做的过火了,简陋的扫码器扫描不出来就很尴尬了。

增加背景图案

简而言之就是为二维码增加背景,不过随之而来的问题跟上面一样,就是如何能让普通的扫码器快速识别出来。作为几年前百度内部hacthon的优胜项目,百度的工程师对点阵图案也做了一些处理,使二维码能呈现这样的图案:

基本想法就是把二维码的每个点变小,中间漏出的空隙就用来呈现背景图案。对于某些特定的背景而言,呈现的效果还是很不错的,而且识别起来也相对准确一点。不过对图片的要求也比较高,否则可能会干扰图像的识别。

与这个方法效果看上取类似的还有一种生成方法,这种方法也结合了下面的修改编码的算法,而且已经发表在springer里,他能够呈现这样的效果:

看上去和百度的差不多,不过其实技术含量要高出不知道多少倍。。。

修改编码算法

上述的方法都或多或少的影响了图像本身的识别能力,虽然看上去效果不错,但是都会或多或少的影响扫码器的识别。而下面的方法能够利用一定的编码技术和小技巧将一个二值图嵌入到二维码中,完全不影响二维码的识别。虽然显示的图像有点抽象,但是拿出来装逼还是很能够体现出技术含量的。

上面这些图案的生成其实还是十分繁琐的,需要深入了解QR二维码的实现以及RS编码的特征的编码人员才能真正实现出将二值图和二维码进行融合的算法。

讲述算法的原理的原文在这里,有个简单(蹩脚)的中文翻译版本在这里,他们实现的程序发布在了这里(不知道怎么回事时而登的上时而登不上)。

下面就简要介绍一下这个算法的基本思想。

首先我们要稍微了解一下QR二维码的基本构造。QR二维码的一个经典构造就是下面的这张图:

简单区分下就是有三类东西,一类是类似小正方形的东西和图中那些黑白相间的条纹,他们主要是用来帮助扫码器定位用的的,所有的QR二维码都具有的部分;还有一类就是格式信息的控制部分,他们就像是配置文件一样,定义了这张二维码的基本信息格式,是必不可少的,主要分布在定位符旁边,毕竟他们是不容许出错的;最后一类就是数据了,当然是经过编码的数据,按照一定的排列规则填充在剩下的空间里,具有一定的容错能力。

很显然数据是以二进制串的形式存储在图里的,也就是黑点和白点了。一张固定大小的图能保存的数据量显然也是固定的,QR二维码也定义了数据的终止符,也就是说当我们的数据写完之后,写上终止符,编码程序会自动在后面加上一些无用的数据(其实是一个循环的数据串),使得总长度等于最大数据量。这些数据按照下面的顺序写入二维码中:

或者换一张图就是这样:

不过如果直接将这个数据就这么显示出来,那么对于只需要保存少量信息的二维码来说,很大的空间都是相同的内容(就是用来填充的字符串),这样显然不美观。因此在把数据写进去之后,我们还会对他做一个mask处理,也就是通过一定的选择算法拿下面这八张图片中的一张图和这个图片按位求异或,保证黑点和白点的总体分布最均匀。

当然,我们得在二维码的格式控制区域说明我们用的是哪个掩膜,保证能够恢复。

这就是QR二维码直观的构造了。

但是即使知道了这个构造,我们也无法随意改动某个像素点,因为这些数据都是经过精心处理的,我们首先得知道他的编码方式才能在不破坏编码信息的基础上寻找修改点阵的办法。

事实上QR二维码对数据采用的是Reed-Solomon编码,具体细节在之前的文章里有所介绍。简单的理解就是他把数据块$(d_1,d_2,d_3,...,d_n)$变成了$(d_1,d_2,d_3,...,d_n,c_1,c_2,...,c_m)$,增加了具有容错能力的冗余码。显然,我们只能直接操控数据,而不能直接决定冗余码。那么我们该怎么修改数据才能既保证数据意义不变,又显示期望的图案呢?这就用到了一个小trick。

我们知道QR二维码基本是用来表示URL的,而URL有个特点,就是可以任意添加锚点(#)而不影响显示的结果,比如https://blog.mythsman.comhttps://blog.mythsman.com#this_is_junk,这两个url在显示的时候是完全没有区别的。也就是说只要数据是url,我们就可以在他后面添加‘#’再加上任意的数据来控制二维码的图形。这样一来,经过编码后的数据就变成了三部分:开头是原始数据加上'#'符号,中间是我们用来绘图的数据,最后是校验数据块。对于图片而言就是两头是不可控的数据,中间是可控的数据。这样弄完之后,可以呈现的效果大概是这样:

可以很明显看到中间的图片显示的很清楚,只是两边都看不清。

可是这种图看上去还是太生硬了,很明显就是刻意修改的数据嘛。不过还好,我们还有另一个办法让他看上去更自然。

回顾下之前的Reed-Solomon编码,我们知道若将$b_1,b_2$的RS编码后的值$c_1,c_2$进行异或得到$c_3$,那么这个$c_3$恰好就是$b_1,b_2$异或后的值的RS编码。这样我们就可以在保证编码合法的情况下对数据矩阵进行初等变换。原本我们只能操作整个数据中间的区域,可是经过初等变换(也就是高斯约旦消元)之后,我们就可以把能够操作的区域和不能操作的区域进行混合,这样就能把图像的控制区域放大,只是这样会牺牲图像的清晰度。不过这种图像却会给人一种自然朦胧的感觉,还是非常炫的。

参考资料

二维码的生成细节和原理
二维码 QR码编码原理详解
QArt Codes
令人拍案叫绝的15个二维码
百度加入二维码之争,推出静态图像版、动态gif版“梦幻二维码”
百度百科-二维码