初涉二维码编码原理
基础常识
二维码发源于日本
有四种规范(参考ISO/IEC 18004:2006(E))
QRCode Model 1,QRCode Model 2,QRCode 2005,The Micro QRCode
Model1是最早的版本,数据量小而且在图像变形的时候无法读取
Model2是增强版本,增加了对齐位
QRCode 2005 和Model2完全兼容,只是增加了一些其他特性.(实在不知道怎么翻译).Model2可以被本规格译码器直接译码.,有1-40号的版本.是主流二维码标准
The Micro QRCode 只需要左上角一个寻象图形(1:1:3:1:1)和2码元的留白
MICRO QR
当然时代在发展,而且有不属于规范中的二维码,根据QRCODE官网 如果将MODEL 1 2分开,有共计6种规格,(温馨提示,请不要选择中文版本,中文版本不全,选择英日韩均可).分别是MODEL 1/2,Micro QR,IQR,SQRC,logoQ.
下面简单说说QRCode 2005的新特性
- 版本16以上的QRCODE支持结构链接,也就是一个数据文件拆分成多个QR码序列
- 支持更多的字符集,例如Arabic,Cyrillic, Greek
- 支持颜色反转,将黑白反转依然可以读取,例如b(经测试,不少二维码读取软件都不支持这样的读取)
- 支持图像水平反转,例如下图的c
颜色反转这种功能非常有用,例如你的电池,你的充电器,不少都是黑色的,上面有印着白色二维码(例如骚尼的充电器),请不要吐槽为什么不贴张白色贴纸然后用黑色二维码,或者是原本那塑料和包装纸就是白色的(不是所有的充电器都是水果牌
基本结构
若无特殊说明,一切基于QRCODE 2005说明(除了特殊说明,Model 2一般和QRCODE 2005相同)
QRCode版本1的码元数目为21 21(码元就是一个bit,黑点为1,白点为0,不考虑颜色反转).版本N的码元边长为17+4N.也就是说每增加一个版本,边长增加4.
寻象图形 Finder Pattern
寻象图形比例为1:1:3:1:1.无论何种规格,均为7个码元,颜色分别是黑白黑白黑,另外,寻象图形周围有1个码元宽度的分隔符Separator,全部为白色,如下图
定位图形 Timing pattern
水平和垂直定位图形均宽1个码元(one module wide),黑白相间,在两个寻象图形之间,与其中一边对齐.定位图形的意义在于二维码初次检测的时候便于确定两个寻象图形的距离,以计算该二维码的版本号.
校正图形 Alignment patterns
一个5*5的方块,外围的一圈黑色加上中心的一个黑色码元.版本2以上均有.(所以上方的图没有校正图形)
编码
- 数据分析 分析数据类型确定编码方式,可以进行混编,同时确定数据量,如果没有指定版本,那么按照当前纠正等级所匹配的最小版本来填充数据.
- 数据编码 数据转换成8bit流,并且在模式段前加入模式指示符(如果模式混编需要加入指定模式符)
- 纠错编码 按照标准将数据流分块,通过RS码进行校验编码.生成纠错码字(一般为系统码)
- 构造最终信息 按照标准将bit流放入数据块中,未填充完全则加入剩余位
- 布置模块 放入寻象图形,分隔符,校正图形,定位图形和码字(8bit)
- 掩模 根据4个罚分标准评价结果取掩模
- 放入格式信息(掩模,纠错级别).一些版本(>=7)还需要放入版本信息.
p.s. 系统码指信息位和校验位分别存放,还有对应的非系统码,均可以在QRCode中使用,非系统码的意义在于重新调整区域信息,以达到自己想要的图形,相信说道这里已经有人知道非系统码可以用来做什么了
~~6.4.2.1 ECI Designator 暂时没有全看懂,先说一下懂的东西,ECI扩展和ECI指定符暂时不会= = ~~
ECI可以简单认为是后续数据的编码模式,不过包含着其他数据.如果一个数据流最开始不是缺省ECI(0111)那么随后每一段(segment)最前端都需要有ECI标头,如果以缺省的ECI开始，位流的开头为第一个模式的指示符。
最终的位串由模式指示符（4位）,字符计数指示符(Character Count Indicator),数据位流组成.
ECI 0111
数字 0001
字母数字 0010
8位字节 0100
日本汉字 1000
中国汉字 1101
结构链接 0011
FNC1 0101 (第一位置)1001 (第二位置)(不懂FNC1,别问我= =)
终止符 0000
字符计数指示符用来表明随后的字符有多少位,字符计数指示符的长度可以查表得出.
注:中文汉字和日文汉字相同
数字模式
十进制数字,3个一组编码成10bit.
例如1-H版本.01234567分组012 345 67.那么
012->0000001100
345->0101011001
67->1000011
可以看到,如果数字只剩下3个,则用7bit编码,如果只剩下一个,则用4位编码.2^10=1024,可以表示0-999,2^7=128,用于表示0-99,2^4=16,用于表示0-9.
使用率将近97%,所以储存的数据量相比其他的二维码要大不少.
好,然后继续编码.数字的模式指示符为0001,01234567一共8个,根据查表字符计数指示符,1-9版本的数字,字符计数指示符都是10,对8进行编码,得到0000001000.
所以增加了ECI标头的最终数据为0001 0000001000 0000001100 0101011001 1000011
数字字母模式
两位一组编码成11bit
本模式拥有0-9,A-Z的 大写 和少数符号组成,一共45种.因此对于一个字符串AB,其结果为45A+B的二进制,最大恰好11位.2025种组合对应2048,利用率将近99%.以下为示例
AC-42
AC-42→(10,12,41,4,2)
(10,12)10*45+12→462→00111001110
(41,4)41*45+4→1849→11100111001
(2)→2→000010
模式指示符:0010
字符数字:5 --->查表得9位-->5->000000101
结果:0010 000000101 00111001110 11100111001 000010
字节流
直接8bit一个码字
汉字
中文汉字的编码,需要由日文编码JIS X 0208的值转换而来,太繁琐了,只能请参见各种论文了.
补足余位
当然,最终完成编码的时候还需要在后面补上0000这个终止符,这个终止符如果剩余位数不足4位,可以截短,如果大于等于4位,均补0000.补全结束以后,如果该编码不足长度能整除8,那么继续补0,补齐8位.随后会放上 thonky的例子.
补全以后如果编码还是太短未到当前版本要求容量,那就增加11101100 00010001直到填满容量.十进制是236和17,至此编码数据结束,可以开始编码纠错模块.
在1-Q版本中编码 HELLO WORLD这11个字母.
查表可知,1-Q一共有13个码字,总容量13*8=104bit.
模式指示符: 0010
字符位数指示符(9位): 00001011(十进制数字是11)
数据编码: 01100001011 01111000110 10001011100 10110111000 10011010100 001101
以上编码总计74位.由于未达到总容量,所以补全0000终止符(如果以上编码102位,那么就只需要补00)
终止符: 0000
以上编码结束后,需要分成8bit一个码字
00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 010000
发现最后一个码字只有6位,那么补全到8位0100000
由于容量目前是74+4+2=80,那么需要补全到104还需要24bit.填充11101100 00010001.
00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 01000000 11101100 00010001 11101100
编码结束.
纠错编码
纠错一共有4个等级,恢复容量分别是L 7% M 15% Q 25 % H 30%
恢复容量的计算:如果初始有100个bit,我们希望能够恢复其中50个bit,那么这50个bit需要2倍的bit才能够纠错(具体请查阅有关论文!),所以现在一共有100+50*2=200bit.恢复容量=50/200=25%.也就是Q级.
纠错码字可以纠正两种类型的错误，拒读错误（错误码字的位置已知,既无法扫描到或者无法译码,例如缺失了某一角）和替代错误（错误码字位置未知,既读取到了该模块,但是由于奇奇怪怪的问题导导致黑读成了白,白读成了黑）。
首先,你要知道什么是多项式除法,例如3x^2+x-1被x+1除,相信学过高中数学的都会.
然后,你要知道什么是The Galois Field伽罗瓦域,也叫有限域.这里取GF(2^8),将数字运算限定在8位数里面.
伽罗瓦域需要模二取余(也就是XOR),并且以绝对值进行运算
例如1+1=2%2=0,1 ^1=0(这个是抑或XOR).0+1=1;1 ^0=1;
加罗瓦域2^8以100011101 ( 285)表示主模块多项式x^8+x^4+x^3+x^2+1,用这个数字对超出255的数字进行XOR. 2^8=256^285=29
好了= =,如果连续两个星期熬夜到三四点的我还能活多几个星期的话,我会把这一段补完,重开一篇新的文章的…不然直接看原文error-correction-coding吧
跳过如果RS编码那一块,接着就是如何排列这一些数据块.又是查表,例如查询版本5-H.
5 H 88 2 (33,11,11)
2 (33,12,11)
(c, k, r): c =码字总数 k =数据码字数 r =纠错容量
计算公式:c=k+2r.这里也就是之前所说的纠错一个bit需要2bit.
5-H版本纠错码字数为88(这个数字可以由r和块数计算出来,这里是4*2r=88),纠错块数为4,分成前2个和后2个.分成不同大小的块数是因为总码字无法直接整除12.
块1 D1 D2 D3 … D11 E1 E2 … E22
块2 D12 D13 D14 … D22 E23 E24 … E44
块3 D23 D24 D25 … D33 D34 E45 E46 … E66
块4 D35 D36 D37 … D45 D46 E67 E68 … E88
版本5-H符号的最终码字序列为D1, D12, D23, D35, D2, D13, D24, D36, … D11, D22, D33, D45, D34, D46, E1, E23, E45, E67, E2, E24, E46, E68, … E22, E44, E66, E88。如果需要，在最后的码字后面加上剩余位（0）。
由于找不到5-H的编码图形,用GIMP自己画会死的= =,只好用其他版本的了.下面这个图形,对于码字,排列顺序是从左到右,以蛇行方式排列,对于bit,实际上是以z字形不断扩展的.
掩模
掩模要事先除去功能图形,但是评分却是对整个图形进行的.一共有8种掩模,掩模的编号对二维码解码来说可以说是最重要的,如果无法正确识别掩模就无法读取整个图形的信息.
罚分标准:不仅仅是使整个图形黑白比例接近1:1,还有其余的判分标准.
行/列中相临的模块的颜色相同
模块块的颜色相同--模块数 = (5 + i) 罚分:N1 + i
颜色相同的模块组成*块-块尺寸 = m×n 罚分:N2× (m - 1)×(n - 1)
在行/纵列中出现1:1:3:1:1图形 罚分:N3
整个符号中深色模块的比率-50±(5×k)% 到 50±(5×(k + 1))% 罚分:N4×k
N1到N4为对符合以上特征所罚分数的权重（N1=3，N2=3，N3=40，N4=10）
选择掩模结果中罚分最低的掩模图形用于符号掩模
格式信息
格式信息为15位，其中有5个数据位，10个是用BCH（15，5）编码计算得到的纠错位。
格式信息一共有两份,一份排布在左上角的寻象图形外围(需要去掉timing pattern交叉的两个点,恰好15位),另外一份拆分成两个部分,一部分在左下角寻象图形右侧,从低到高为0-7,另一部分在右上角寻象图形下方,有后7位,从右至左8-15
纠错等级指示符(1-2位):
L:01 M:00 Q:11 H:10
掩模图形指示符(3-5位):
000-111
将15位格式信息与掩模图形101010000010010进行XOR运算
L:11 M:10 Q:01 H:00
这个就是我们肉眼所见的能直观判断该图的纠错级别的符号.
版本信息
版本信息为18位，其中，6位数据位，通过BCH（18，6）编码计算出12个纠错位,放置在版本信息位.
只有版本7～40的符号包含版本信息
至此整个编码过程结束.各种个性化的二维码生成有机会再慢慢讲,当然前提是我看懂了那些论文和算法们.
部分图片,资料取自维基百科
部分图片,资料取自专利书ISO/IEC 18004:2006(E)
部分来源 thonky
