在二维码世纪,流传着这样一个传说,long long ago,武林一片混乱,这时魔教二长老创立了一门绝世武功——QR code,随后称霸武林。但同时也遭到武林中人的觊觎和反抗,各大武林正派掌门人一起修炼了一套对付二长老的神功。终于经历了七天七夜昏天地暗的恶战后,联盟取得了胜利,但二长老和各大掌门们却从此失踪,也在没有人知道他们的绝世武学。魔教因此隐匿,从此与武林井水不犯河水,武林风平浪静。直到互联网(没错,玩的就是穿越)的出现……
由于互联网的出现,武林中便又开始传起了关于武功秘籍的各种谣言,一场腥风血雨即将来临。各派各路人马以及魔教因此大打出手。此时各方势力同时盯上了谣言中当日恶战附近的小镇。整个小镇惨遭屠杀,一夜之间变成了废墟(果然谣言害死人)。唯独镇上一屌丝(一块”白布“啦)晕倒掉进溪流冲上了某个神秘的小岛……
幸存下来的屌丝在岛上活了下来,几个月后屌丝意外发现了一出秘密洞穴。找到了长老们留下的口诀(放心绝不会有”欲练此功……“):
1 校正图形(Alignment Pattern)用于确立矩阵符号位置的一个固定的参照图形,解码译码软件可以通过它在图象有中等程度损坏的情况下,再同步图像模块的坐标映象。
2 字符计数指示符(Character Count Indicator)定义某一模式下的数据串长度的位序列。
3 ECI 指示符(ECI designator)6 位数字,用于标识具体的 ECI 任务。
4 编码区域(encoding region)在符号中没有被功能图形占用,可以对数据或错误纠正纠错码字进行编码的区域。
6 扩展图形(Extension Pattern)
模式 1 中,不表示数据的一种功能图形。
7 格式信息(Format Information)一种功能图形,它包含符号使用的错误纠正纠错等级以及使用的掩模图形的信息,以便对编码区域的剩余部分进行译码。
8 功能图形(function pattern)包含帮助译码的符号定位或者它的特征识别信息的符号附加成分,。符号中用于符号定位与特征识别的特定图形。
9 掩模图形参考(Mask Pattern Reference)用于符号中的三位三位掩模图形标识符。
10 掩模(masking)在城内编码区域内,用掩模图形对在城内编码区的位图进行 XOR 操作,其目的是使符号中深色与浅色模块数的比例均衡,并且减少影响图像快速处理的图形出现。
11 模式(mode)将特定的字符集表示成位串的方法。
12 模式指示符(Mode Indicator)4 位标识符,指示随后的数据序列所用的编码模式。
13 填充位(Padding Bit)值为 0,不表示数据,用于填充数据位流最后一个码字中终止符后面的空位。
14 位置探测图形(Position Detection Pattern)组成寻象图形的三个相同的图形之一。
15 剩余位(Remainder Bit)值为 0,不表示数据,当编码区域不能正好被 8 位的码字填满时,用于填充最后一个码字后的空位。
16 剩余码字(Remainder Codeword)一种填充码字,当所有的数据码字和错误纠正纠错码字不能正好填满符号的容量时,用于填充一种填充码字所空码字位置,它们紧跟在最后一个错误纠正纠错码字之后。
17 段(segment)以同一 ECI 或编码模式编码的数据序列。
18 分隔符(Separator)全部由浅色模块组成的功能图形,宽度为一个模块,用于将位置探测图形与符号的其余部分分开。
19 终止符(Terminator)用于结束表示数据位流的位图 0000。
20 定位图形(Timing Pattern)深色与浅色模块交错的图形,便于决定符号中模块的坐标。
21 版本(Version)用于表示符号规格的系列。某一特定版本是根据它在所允许的规格系列中的位置来确定的。QR 码所允许规格系列为 21×21 模块(版本 1)~177×177 模块(版本40)。它也可同时指示符号所应用的纠错等级。
22 版本信息(Version Information)在模式 2 符号中,包含符号版本的信息及该数据错误纠正纠错位的功能图形。
(再次说明,口诀什么的可都是来自 上一篇的给出的链接文档 中)
说到口诀,都是为招式做铺垫。不知道口诀,可不好理解招式 。
看看什么地方该干嘛:
1. 3个黑色和黄色同心的正方块 ——Position Detection Pattern 位置探测图形(7*7,5*5,3*3)
坐标:{(0,0)(7,7)},{((21+(version-1)*4)-7,0),(21+(version-1)*4-1,7)}{(0,(21+(version-1)*4)-7),(7,21+(version-1)*4-1)}
2. 3个绿色直角 ——Separator 分隔符(1*8,8*1)
3. 蓝、白色正方块 ——Alignment Pattern 校正图形(5*5,3*3,1*1)
坐标:{((21+(version-1)*4)-9,(21+(version-1)*4)-9),((21+(version-1)*4)-4,(21+(version-1)*4)-4)}
4. 2条橙、灰色相间条 ——Timing Pattren 定位图形
作用:便于定位坐标
5. 品红和红色条 ——都是Format Information 格式信息(各15位)
由于格式信息和版本信息(图中没有,版本7以上有)很重要,因此都存储了两次,也就是品红条和红色条存储的15位是相同数据。
品红条上的黑点也属于格式模块,位置(4v+9,8),总是深色。其中v是版本号,4是每个版本增加的模块数。
15位中,前五位为数据位,分别为
第1、2位为纠错等级(L——01,M——00,Q——11,H——10)
第3~5位为掩模图形参数Mask Pattern Reference(选值下面介绍)
后10位为纠错数据(以上15位将是原始数据而不是最终存储数据)
6. 所有剩下白色区域 ——存放数据和纠错码字的区域
说明:上图只适用于版本2~6(7及以上都有两块存放版本信息的模块)
版本1——无版本信息、校正图形 版本7~13——3^2-3=6校正图形 版本21~27——5^2-3=22校正图形
版本2~6——与图中一样 版本14~20 ——4^2-3=13校正图形 版本28~34——6^2-3=33校正图形
版本35~41——7^2-3=46校正图形
第一层(步): 数据分析分析所输入的数据流, 确定要进行编码的字符的类型 。QR 码支持扩充解释,可以对与缺省的字符集不同的数据进行编码。QR 码包括几种不同的模式,以便高效的地将不同的字符子集转换为符号字符。必要时可以进行模式之间的转换更高效地将数据转换,以便为二进制串。 选择所需的错误检测和纠正等级 。如果用户没有指定所采用的符号版本,则 选择与数据相适应的最小的版本 。
第二层:数据编码对于采用的模式按照 定义的规则, 将数据字符转换为位流 。在当需要进行模式转换时,在新的模式段开始前加入模式指示符进行模式转换。在数据序列后面 加入终止符 。将产生的位流分为每 8 位一个码字。必要时加入 填充字符 以填满按照版本要求的数据码字数。
第三层:纠错编码按需要 将码字序列分块 ,以便按块 生成相应的错误纠正纠错码字 ,并将其 加入到相应的数据码字序列的后面 。
第四层: 构造最终信息 按 第三步的描述,在每一块中置入数据和纠错码字,必要时加剩余位 。
第五层:在矩阵中布置模块将寻象图形、分隔符、定位图形、校正图形与码字模块一起放入矩阵。
第六层:掩模依次将掩模图形用于符号的编码区域。评价结果,并 选择 其中使深色浅色模块比率 最优 且使不希望出现的 图形 最少化的结果。
第七步:格式和版本信息生成格式和版本信息(如果用到时),形成符号。
结论:前面的每一层都将成为后面操作的基础。
(上次给的那篇链接文档少了附录,找了很久才找到搭配的附录文档————> 这是链接 )
第1、2位为纠错等级(L——01,M——00,Q——11,H——10)
第3~5位为掩模图形参数Mask Pattern Reference
000——(x+y)%2=0 011——(x+y)%3=3 110——((x*y)%2+(x*y)%3)%2=0
001——x%2=0 100——((x/2)+(y/3))%2=0
010——y%3=0 101——(x*y)%2+(x*y)%3=0
以011为例:
当然,从入门内功中可以看到,这三位可不是好确定的,是需要大量运算后对比确定的(看入门内功)。下面介绍后十位的原始数据(最终数据是掩摸后的)计算方法——
BCH(15,5) (声明下面将会用到很多带次方的多项式,为了方便书写,因此“x"后面的数字就是次数)
BCH(15,5)码用于纠错。以数据位串为系数的多项式被生成多项式 G(x)(至于G(x)怎么求再说) 除,所得剩余多项式的系数串应追加到数据位串上形(15,5)BCH 码字符串。最后,通过与掩摸图形对位串进行异或(XOR)运算进行掩模,来保证掩模图形和纠错等级的任意组合的格式信息位图不全为 0。
附录中例子是这样的——
BCH(15,5)码用于纠错。以数据位串为系数的多项式被生成多项式 G(x) =X10+X8+X5+X4+X2+X+1 除,所得剩余多项式的系数串应追加到数据位串上形(15,5)BCH 码字符串。
例:纠错等级 M;掩模图形 101
二进制字符串: 00101
生成多项式: X2+1
将次数升至(15-5): X12+X10
被 G(X)除后得 = (x10 + x8 + x5 + x4 + x2 + x + 1)x2 + (x7 + x6 + x4 + x3 + x2)
把上面的剩余多项式的系数字符串附加至格式信息数据串。
00101+0011011100 → 001010011011100
那么从上面的例子中有这些疑问:
1. G(x)怎么来的?
2. 为什么要提升次数?
3. 怎么除?
下面将一一解决这些问题:
1. BCH(n,k)中
G(x)——生成多项式
C(x)——数据码生成多项式
R(x)——为C(x)/G(x)余式
三者关系:
R(x)={x^(n-k)*C(x)}/G(x)——————这就是为什么提升次数的原因,乘了x^(n-k),BCH(15,5)中乘x10。
2. G(x)的计算
循环码中定理:G(x)是(n,k)循环码的生成多项式当且仅当G(x)是x^n-1的r=n-k次因式。而BCH码是循环码的子类。
如:
(x15+1) = (x10+x8+x5+x4+x2+x+1)(x5+x3+x+1)……………………因此BCH(15,5)的G(x)=x10+x8+x5+x4+x2+x+1(101001101011)
(x15+1) = (x4+x+1)(x11+x8+x7+x5+x3+x2+x+1)……………………因此BCH(15,11)的G(x)=x4+x+1 (010011)
3. 模2多项式除法
{x^(n-k)*C(x)}/G(x)采用的是模2多项式除法——长除, 整式除法
多项式除以多项式一般用竖式进行演算
(1)把被 除式 、除式按某个字母作 降幂 排列,并把所缺的项用零补齐.
(2)用被除式的第一项除以除式第一项,得到商式的第一项.
(3)用 商式 的第一项去乘除式,把积写在被除式下面(同类项对齐),消去相等项,把不相等的项结合起来.
(4)把减得的差当作新的被除式,再按照上面的方法继续演算,直到余式为零或余式的次数低于除式的次数时为止
……………………………… 数据编码 ……………………………………………………
(以数字模式,模式1、2-L为例)
1 输入数据: 15162100138
2 分为三位一组: 151、621、001、38
3 转换为二进制(10位): 151——0010010111
621——1001100011
001——0000000001
38——0100110(最后一组1位用4bit,2位用7bit,3位用10bit)
4 Character Count Indicator字数计数指示符(10bit): 有11位 编码为 0000001011
5 模式指示符(4bit):数字模式的模式指示符为 0001
6 按模式指示符+字数计数指示符+数据+终止符0000(如果前面四项已经填满容量可缺省1,2,3,4位终止符)
0001 0000001011 0010010111 1001100011 0000000001 0100110 0000
7 分成8bit一段
0001 0000 001011 00 10010111 10011000 11 000000 0001 0100 110 0000 0 (最后一bit为填充位)
8 总量34,故需34-7=27填充码字(显然不科学,所以第一步是数据分析呢)
填充码字为 11101100 00010001交替填充
9 纠错编码
这是最蛋疼的事了,应该是计算量最大的部分了。用Seed-Solomon算法计算。具体可参照纠错码计算然后查表吧。
…………
神功已成
然而并没有什么卵用,屌丝仍然是屌丝。你都看到了,最困难的就是内功(算法)了。没有内功(算法)技能(二维码图)打出来没伤害(扫不出来),”白布“上就是一堆乱码。
当然剧本不可能就这么完了……
预知后事如何,请自个儿修炼(下回分解?别逗了,好难写了,草人桌子上两罐饮料了……)
附:草人写这博文时的代码(没什么用,除了关键地方没实现,代码也只是为了生成上面的图便于写文)
package zry.QRcode; import java.awt.Color; import java.awt.Graphics2D; import java.awt.image.BufferedImage; import java.io.FileOutputStream; import java.io.IOException; import javax.imageio.ImageIO; import spoofQRcode.CreatQRImage2; public class CreateQRcodeImage { private FileOutputStream fos = null; private BufferedImage buffImg = null; private Graphics2D gs = null; private Color m_deepColor = Color.black; private Color m_lightColor = Color.white; /** 构造函数,创建一块画布(“白布”) * @throws IOException */ public CreateQRcodeImage(int imgSize) throws IOException{ // TODO Auto-generated constructor stub buffImg = new BufferedImage(imgSize, imgSize, BufferedImage.TYPE_INT_RGB); gs = buffImg.createGraphics(); gs.setBackground(Color.WHITE); gs.clearRect(0, 0, imgSize, imgSize); System.out.println("画布已经被创建"); //drawMaskPattern(2,m_deepColor,8,"011"); //drawPatternBoundary(2,Color.black,8); //drawSeparator(2,Color.green,8); //drawPositionDetectionPattern(2,Color.black,8); //drawAlignmentPattern(2,Color.blue,8); //drawTimingPattern(2,Color.orange,8); //drawFormatInformation1(2,Color.magenta,8); //drawFormatInformation2(2,Color.red,8); drawPositionDetectionPattern(2,m_deepColor,8); drawAlignmentPattern(2,m_deepColor,8); drawTimingPattern(2,m_deepColor,8); gs.dispose(); buffImg.flush(); fos=new FileOutputStream("F:/zzzzzz027.png"); ImageIO.write(buffImg, "png", fos); } /* public void drawPatternBoundary(int version, Color patternColor,int patternSize){ gs.setColor(patternColor); for(int i = 0;i < 21+(version-1)*4;i++) for(int j = 0;j < 21+(version-1)*4;j++) gs.fillRect(i*patternSize,j*patternSize,1,1); } */ /** * 填充指定区域(x*width,y*height) * @param x 起始行坐标 * @param y 起始纵坐标 * @param width 行长度(长) * @param height 列长度(宽) * @param patternColor 填充颜色 * @param patternSize 每个块单位大小 */ public void drawPattern(int x,int y,int width,int height, Color patternColor,int patternSize){ gs.setColor(patternColor); for(int i = x;i < width+x;i++) for(int j = y;j < height+y;j++) gs.fillRect(i*patternSize,j*patternSize,patternSize,patternSize); } /** * 填充分隔符域,用浅色 * @param version * @param patternColor * @param patternSize */ public void drawSeparator(int version, Color patternColor,int patternSize){ drawPattern(0,0,8,8,patternColor,patternSize); drawPattern((21+(version-1)*4)-8,0,8,8,patternColor,patternSize); drawPattern(0,(21+(version-1)*4)-8,8,8,patternColor,patternSize); } /** * 填充位置探测图形 * @param version 版本 * @param patternColor 填充颜色 * @param patternSize 每个块单位大小 */ public void drawPositionDetectionPattern(int version, Color patternColor,int patternSize){ /**左上角*/ drawPattern(0,0,7,7,patternColor,patternSize); drawPattern(1,1,5,5,m_lightColor,patternSize); drawPattern(2,2,3,3,patternColor,patternSize); /**右上角*/ drawPattern((21+(version-1)*4)-7,0,7,7,patternColor,patternSize); drawPattern((21+(version-1)*4)-7+1,1,5,5,m_lightColor,patternSize); drawPattern((21+(version-1)*4)-7+2,2,3,3,patternColor,patternSize); /**左下角*/ drawPattern(0,(21+(version-1)*4)-7,7,7,patternColor,patternSize); drawPattern(1,(21+(version-1)*4)-7+1,5,5,m_lightColor,patternSize); drawPattern(2,(21+(version-1)*4)-7+2,3,3,patternColor,patternSize); } /** * 填充校正图形(校正图形需要版本来确定数量和位置的,这儿只写出了2-6版本,用到的每块单位大小也 * 要由版本和画布大小计算出,patternSize=imgSize/(21+(version-1)*4) * @param version 版本 * @param patternColor 填充颜色 * @param patternSize 每个块单位大小 */ public void drawAlignmentPattern(int version, Color patternColor,int patternSize){ drawPattern((21+(version-1)*4)-9,(21+(version-1)*4)-9,5,5,patternColor,patternSize); drawPattern((21+(version-1)*4)-8,(21+(version-1)*4)-8,3,3,m_lightColor,patternSize); drawPattern((21+(version-1)*4)-7,(21+(version-1)*4)-7,1,1,patternColor,patternSize); } /** * 填充定位图形 * @param version * @param patternColor * @param patternSize */ public void drawTimingPattern(int version, Color patternColor,int patternSize){ for(int x = 8;x < (21+(version-1)*4)-8; x++){ if(x%2==0) drawPattern(x,6,1,1,patternColor,patternSize); else drawPattern(x,6,1,1,m_lightColor,patternSize); } for(int y = 8;y < (21+(version-1)*4)-8; y++){ if(y%2==0) drawPattern(6,y,1,1,patternColor,patternSize); else drawPattern(6,y,1,1,m_lightColor,patternSize); } } /*************************以上是功能图形************************/ /** * 填充格式信息,为了好看图写 * @param version * @param patternColor * @param patternSize */ public void drawFormatInformation1(int version, Color patternColor,int patternSize){ for(int y = 0;y < 21+(version-1)*4;y++){ if(y!=6&&y<9||y>(21+(version-1)*4-8)){ drawPattern(8,y,1,1,patternColor,patternSize); } } drawPattern(8,(21+(version-1)*4-8),1,1,m_deepColor,patternSize); } /** * 填充格式信息,为了好看图写 * @param version * @param patternColor * @param patternSize */ public void drawFormatInformation2(int version, Color patternColor,int patternSize){ for(int x = 0;x < 21+(version-1)*4;x++){ if(x!=6&&x<8||x>(21+(version-1)*4-9)){ drawPattern(x,8,1,1,patternColor,patternSize); } } } public void drawMaskPattern(int version, Color patternColor,int patternSize,String maskPatternReference){ if(maskPatternReference == "000"){ } if(maskPatternReference == "001"){ } if(maskPatternReference == "010"){ } if(maskPatternReference == "011"){ for(int x = 0;x < 21+(version-1)*4;x++) for(int y = 0;y < 21+(version-1)*4;y++) if((x+y)%3 == 0){ //System.out.print(x); //System.out.println(y); gs.setColor(patternColor); gs.fillRect(x*patternSize,y*patternSize,patternSize,patternSize); //System.out.println("ok"); } } if(maskPatternReference == "100"){ } if(maskPatternReference == "101"){ for(int x = 0;x < 21+(version-1)*4-1;x++) for(int y = 0;y < 21+(version-1)*4-1;y++) if((x*y)%2+(x*y)%3 == 0){ //System.out.print(x); //System.out.println(y); gs.setColor(patternColor); gs.fillRect(x*patternSize,y*patternSize,patternSize,patternSize); //System.out.println("ok"); } } if(maskPatternReference == "110"){ } } public static void main(String[] args) throws IOException{ int imgSize = 200; CreateQRcodeImage obj = new CreateQRcodeImage(imgSize); } }View Code